FOM: 115:Aspects of Coloring Integers

[Harvey Friedman]

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