FOM: 115:Aspects of Coloring Integers
Harvey Friedman
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
formulation.
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
1 white
2 black
3 white
4 black
etcetera
As another example, take R(x,y,z) if and only if x = y+z. We obtain
1 white
2 black
3 white
4 black
etcetera
For another example, take R(x,y,z,w) if and only if x = y+z+w. We obtain
1 white
2 white
3 black
4 black
5 black
6 black
7 white
8 white
9 black
10 black
11 black
12 black
etcetera
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
mailing list