FOM: 115:Aspects of Coloring Integers
friedman at math.ohio-state.edu
Thu Jan 3 22:02:46 EST 2002
For those interested in the first section of the posting 113:Coloring
Integers, 12:42PM 12/31/01, I want to mention a more general and flexible
1'. COLORING THE POSITIVE INTEGERS USING A RELATION.
Let k >= 1 and R be a k+1-ary relation on the positive integers. We say
that x is related by R to y1,...,yk if and only if R(x,y1,...,yk).
Consider the following simple condition:
1a'. Every positive integer is black if it is related by R to k smaller
positive integers; white otherwise.
EXERCISE 1.1'. For all k+1-ary R, there is a white/black coloring
satisfying condition 1a. For all k+1-ary R, there is at most one
white/black coloring satisfying condition 1a. What happens if we delete
"smaller" in condition 1a'?
As a simple example, take R(x,y) if and only if x = y+1. We obtain
As another example, take R(x,y,z) if and only if x = y+z. We obtain
For another example, take R(x,y,z,w) if and only if x = y+z+w. We obtain
EXERCISE 1.1'. Explore further with additional linear relations, and with
relations given by one or more linear inequalities. Explore further with
relations given by a disjunction of such systems of linear inequalities.
Explore further with simple polynomial relations. Using experimental
results, make up conjectures about the behavior, and then prove your
conjectures. A certain amount can be done by hand without computer. Write
efficient computer code for experimental studies using simple functions.
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 115th in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones counting from #100 are:
100:Boolean Relation Theory IV corrected 3/21/01 11:29AM
101:Turing Degrees/1 4/2/01 3:32AM
102: Turing Degrees/2 4/8/01 5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01 11:10AM
104:Turing Degrees/3 4/12/01 3:19PM
105:Turing Degrees/4 4/26/01 7:44PM
106.Degenerative Cloning 5/4/01 10:57AM
107:Automated Proof Checking 5/25/01 4:32AM
108:Finite Boolean Relation Theory 9/18/01 12:20PM
109:Natural Nonrecursive Sets 9/26/01 4:41PM
110:Communicating Minds I 12/19/01 1:27PM
111:Communicating Minds II 12/22/01 8:28AM
112:Communicating MInds III 12/23/01 8:11PM
113:Coloring Integers 12/31/01 12:42PM
114:Borel Functions on HC 1/1/02 1:38PM
More information about the FOM