FOM: 113:Coloring Integers

[Harvey Friedman]

COLORING THE POSITIVE INTEGERS
by
Harvey M. Friedman
December 31, 2001

This is a exposition of aspects of Boolean Relation Theory that is intended
to be attractive for gifted high school students, undergraduate mathematics
students, mathematicians allergic to logical matters, and nonmathematician
scientists. Everything is stated in terms of coloring the positive integers
with (two or) four colors.

In these reformulations, new considerations come into play, for what is
most natural here is not always the same as what is most natural in
Boolean Relation Theory.

It now appears that "coloring the positive integers" will have a life
somewhat independent of Boolean Relation Theory. In fact, it now appears
that the first presentable examples of discrete combinatorial statements
that require large cardinals like measureables and above (I haven't
announced any such) may look most natural in the context of "coloring the
positive integers".

**************************************************************

INSTRUCTIONS: In the exercises, some statements made are true and some
statements made are false. Determine which are true and give proofs.
Determine which are false and give refutations.

1. COLORING THE POSITIVE INTEGERS USING A FUNCTION.

Throughout these exercises, we will be using functions of several variables
from the positive integers into the positive integers. The number of
variables can be any positive integer, and the values are positive
integers.

We say that f is strictly dominating if and only if the value of f at any
arguments is greater than each of the arguments.

In this section, we use only the colors white and black. We wish to color
the positive integers, where each positive integer has a unique color,
which is either white or black. We call these white/black colorings of the
positive integers.

Consider the following simple condition:

1a. Every positive integer is black if it is the value of f at whites;
white otherwise.

EXERCISE 1.1. For all f, there is a white/black coloring satisfying
condition a. For all f, there is at most one white/black coloring
satisfying condition 1a. For all strictly dominating f, there is a
white/black coloring satisfying condition a. For all strictly dominating f,
there is at most one white/black coloring satisfying condition 1a.

As a simple example, take f(x) = x+1. We obtain

1 white
2 black
3 white
4 black
etcetera

As another example, take f(x,y) = x+y. We obtain

1 white
2 black
3 white
4 black
etcetera

For another example, take f(x,y,z) = x+y+z. 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.2. Explore further with additional linear and affine functions.
Explore further with simple piecewise linear functions. Explore further
with simple polynomials. 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.

2. COLORING THE POSITIVE INTEGERS USING TWO FUNCTIONS - SINGLE CONDITION.

Let f,g be strictly dominating. We impose the following conditions on a
red/white/blue/black coloring of the positive integers.

2a. Every value of f at reds is black if it is also the value of g at reds
and whites; white otherwise.
2b. Every value of f at whites is black if it is also the value of g at
reds, whites, and blues; white or blue otherwise.

NOTE: These conditions are special cases of a more general coloring
condition in section 5.

NOTE: To avoid any possible misunderstanding, we rewrite these in
cumbersome detail:

2a. For every positive integer x, if x is the value of f at arguments all
of which are red, then
	i) if x is also the value of g at arguments each one of which is
either red or white (zero or more arguments are red, and zero or more
arguments are white), then x is black;
	ii) otherwise, x is white.

2b. For every positive integer x, if x is the value of f at arguments all
of which are white, then
	i) if x is also the value of g at arguments each one of which is
either red or white or blue (zero or more arguments are red, zero or more
arguments are white, zero or more arguments are blue), then x is black;
	ii) otherwise, x is white or x is blue.

EXERCISE 2.1. Let f,g be strictly dominating. There is a
red/white/blue/black coloring satisfying 2a with infinitely many reds,
whites, blues, and blacks. There is a red/white/blue/black coloring
satisfying 2b with infinitely many reds, whites, blues, and blacks. Same
for any f,g. Same for f strictly dominating and any g. Same for g strictly
dominating and any f.

3. COLORING THE POSITIVE INTEGERS USING TWO FUNCTIONS - TWO CONDITIONS.

Recall the two conditions from section 2 on a red/white/blue/black coloring
of the positive integers. We now want to consider red/white/blue/black
colorings of the positive integers satisfying both of these conditions
simultaneously:

2a. Every value of f at reds is black if it is also the value of g at reds
and whites; white otherwise.
2b. Every value of f at whites is black if it is also the value of g at
reds, whites, and blues; white or blue otherwise.

NOTE: One of the difficulties in getting both conditions to hold
simultaneously is that conflicts may arise. Specifically, an integer may be
both a value of f at reds and a value of f at whites.

EXERCISE 3.1. Let f,g be strictly dominating. There is a
red/white/blue/black coloring satisfying 2a,2b with infinitely many
i) blacks;
ii) blues;
iii) whites;
iv) whites and blues;
v) whites and blacks;
vi) blues and blacks;
vii) whites, blues, and blacks.

EXERCISE 3.2*. Let f,g be strictly dominating. There is a
red/white/blue/black coloring satisfying 2a,2b with infinitely many
i) reds;
ii) reds and whites;
iii) reds, whites, and blues;
iv) reds, whites, blues, and blacks.

EXERCISE 3.3*. Same as Exercise 3.2 for any f,g. For strictly dominating f,
any g. For strictly dominating g, any f.

Perhaps to make things easier or more interesting, let us impose a stronger
condition on f,g. We say that f is 2,3-trapped if and only if the value of
f at any arguments is at least twice each of those arguments and at most
three times the largest of those arguments.

EXERCISE 3.4.**. Let f,g be 2,3-trapped. There is a red/white/blue/black
coloring satisfying 2a,2b with infinitely many
i) reds;
ii) reds and whites;
iii) reds, whites, and blues;
iv) reds, whites, blues, and blacks.

HINT: Some of these exercises need more than the usual axioms and rules for
the whole of mathematics!

4. GAPS IN THE RED/WHITE/BLUE/BLACK COLORINGS.

Consider a red/white/blue/black coloring. We can study the spacing between,
say, reds. I.e., how many numbers are there between the first and second
reds, the second and third reds, etcetera. This turns out to be something
that we cannot control in the coloring problems 2a,2b without knowing what
f and g are.

However, we can ask how many whites are there between the first and second
reds, the second and third reds, etcetera. This turns out to be something
that we can control in the coloring problems 2a,2b, just knowing the number
of variables of f,g.

Let us first consider condition 1a on white/black colorings of the positive
integers.

EXERCISE 4.1. For all strictly dominating f there is a white/black coloring
satisfying condition 1a such that the following holds. The gaps between
successive whites is bounded by an infinite geometric progression.

EXERCISE 4.2.  Let f,g be strictly dominating. There is a
red/white/blue/black coloring satisfying 2a where the number of whites
between successive reds is of the form {r,r^2,r^3,...}. There is a
red/white/blue/black coloring satisfying 2b where the number of whites
between successive reds is of the form {r,r^2,r^3,...}.

EXERCISE 4.3.** Let f,g be 2,3-trapped. There is a red/white/blue/black
coloring satisfying 2a,2b where the number of whites between successive
reds is of the form {r,r^2,r^3,...}.

Exercise 4.3 leads immediately to a corresponding statement with finite
conclusion.

EXERCISE 4.4.** Let f,g be 2,3-trapped and r,n are sufficiently large.
There is a red/white/blue/black coloring of some finite initial segment of
the positive integers satisfying 2a,2b where the number of whites between
successive reds is {r,r^2,r^3,...,r^n} and 1 is red. In fact, it suffices
to assume that r,n are sufficiently large relative to the number of
variables in f,g.

We can go further and deal entirely with finite objects.

EXERCISE 4.5.** Let r,n,t be sufficiently large relative to k >= 1 and
f,g:[1,t]^k into [1,3t] be 2,3-trapped. There is a red/white/blue/black
coloring of [1,3t] satisfying 2a,2b where the number of whites between
successive reds is {r,r^2,r^3,...,r^n} and 1 is red.

HINT: Some of these exercises need more than the usual axioms and rules for
the whole of mathematics!

5. GENERAL COLORING CONDITION.

Here we color the positive integers with p colors 1,2,...,p, where p >= 2.
Here is the condition:

5a. For all 1 <= i <= p-2, every value of f at arguments of color i is of
color p if it is the value of g at arguments of  colors <= i+1; of color <=
i+1 and >= 2 otherwise.

EXERCISE 5.1.**  Let f,g be 2,3-trapped and p >= 2. There is a 1,...,p
coloring of the positive integers satisfying 5a where the number of
integers of each color is infinite.

HINT: Some of these exercises need more than the usual axioms and rules for
the whole of mathematics!

We can also study gaps between successive reds in 1,...,p colorings
satisfying 5a.

**********************************************

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.

This is the 113th 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