In my previous post I explained how Rado’s theorem follows from Deuber’s theorem (which in turn gives a little more than Rado’s theorem, in one direction). The main purpose of this post is to give a full proof of Deuber’s theorem, which will then complete the proof of Rado’s theorem.

I will follow the proof presented in this survey by Gunderson (available here). According to the survey, this proof was first suggested by Leeb and later worked out by Prömel. The main tool for the proof is the Hales-Jewett theorem. I wrote about this theorem twice before in this blog, including a complete proof. In particular I showed how van der Waerden’s theorem on arithmetic progressions, which is an important corollary of Deuber’s theorem, follows from Hales-Jewett’s theorem.

However, Deuber’s theorem (which I will formulate precisely below) implies also Schur’s theorem, and it is not at all clear how to derive Schur’s theorem from Hales-Jewett theorem directly. Thus it is somewhat surprising that one can leverage the Hales-Jewett theorem to deduce Deuber’s theorem.

** — 1. Precise definitions and statements — **

For completeness I will give, in this section, the precise statements of Deuber’s theorem and Hales-Jewett theorem, starting with the former.

Definition 1Let and let . For each , the -set generated by is the set

Thus an -set is a set of the form and a -set is a set of the form . Deuber’s theorem says, roughly speaking, that in a partition of a large -set there exists a smaller -set contained in a single cell of the partition:

Theorem 2Let . Then there exist such that for any coloring of a -set into colors, there exists a monochromatic subset which is an -set.

For the proof of this theorem it will be convenient to deal with each line of an -set at a time. For clarity we need another definition:

Definition 3Let with and let . We define the setAlso define .

Observe that, whenever , the line is a subset of the -set . In fact, an -set is the union of lines of the form with .

Now we give the definitions needed to formulate the Hales-Jewett theorem.

Definition 4Let , let be a finite set and let be an element not in .

- A
variable wordin is an element which is not in (so the must appear somewhere in ).- Given a variable word and a letter we denote by the element of obtained from by replacing each instance of with .
- Given a variable word , the
combinatorial lineinduced by is the set .

Theorem 5 (Hales-Jewett)For any finite set and any there exists some such that for any finite partition of into pieces, one of the pieces contains a combinatorial line.

** — 2. Proof of Deuber’s theorem — **

The first observation towards the proof of Deuber’s theorem is that for any , if are integers and , then the union

contains an -set, namely where .

Next observe that if and an -set is colored into colors in such a way that each line is monochromatic, then, by the pigeonhole principle there are lines all of the same color, and by the observation in the previous paragraph we deduce that there exists a monochromatic -set.

The strategy we will use is to start with a -coloring of a huge -set and find (using the Hales-Jewett theorem) a smaller -set with the last line monochromatic. Then (using again the Hales-Jewett theorem) we find a smaller -set whose last line is contained in the last line of the -set (and hence is monochromatic) and such that the second to last line is also monochromatic, and we iterate this process until we have a not so huge (but still pretty large) -set with each line monochromatic, at which point we can finish the proof as outlined above.

To isolate the important steps it is convenient to give a name to colorings of -sets that have certain lines monochromatic:

Definition 6Let with . A coloring of an -set is called-regularif each of the last lines are monochromatic. More precisely, if for each the -th line is monochromatic.

The main step in the proof is the following lemma, which will later be iterated:

Lemma 7Let and let . Then there exist such that whenever a -set is given a -regular -coloring, there exists a subset which is a -set with a -regular -coloring.

*Proof:* We will apply the Hales-Jewett with and the same from this lemma. Let be given by Theorem 5. It will be convenient to denote by , and let , and .

We will show that given any -set one can extract a subset which is a -set whose line is contained in for each , and such that the line is a monochromatic subset of the line (note that , and hence the -th line of a -set has the same cardinality as any combinatorial line in . This hints at how the Hales-Jewett theorem will be used).

Given and a -regular -coloring (where, as usual, we denote by the set ) of the -set we can induce a coloring of as follows: let with each

and then define

From the choice of one can now find a variable word which generates a -monochromatic combinatorial line in . Let be the (nonempty) set of positions of the wild car in and let . Since for each we have , we can write

Next let be the vector defined by

I claim that is a -regular subset of . I will separate this into 3 claims:

Claim 1For we have the inclusion

*Proof:* We have

From the definition of we see that each with depends on disjoint coordinates of . Thus for any we have

for some with , and this means that

Claim 2The line is contained in and is monochromatic.

*Proof:* We have

Since both and are in , it is clear that this line is contained in . Moreover, this is the set in correspondence with the monochromatic combinatorial line generated by and hence it is monochromatic itself.

Claim 3For each , the line is contained in .

*Proof:*

Let and . Observe that for any we have

This finishes the proof.

Since we assumed that the coloring on is -regular, it follows that is -regular and this finishes the proof of the lemma.

Using Lemma 7 we can now finish the proof of Theorem 2:

Let . Let and let , and . For each apply Lemma 7 to find such that for any -regular -coloring of a -set there exists a subset which is a -set with a -regular -coloring.

Now let , and and consider an -coloring of a an arbitrary -set. Observe that this is trivially a -regular coloring. By construction there exists a subset which is a -set with a -regular coloring. Iterating this reasoning one can eventually find a subset which is a -set with a -regular coloring. Since , this means that each line of this -set is monochromatic. Let be the generator for this -set. By the pigeonhole principle one can find lines which are all of the same color, say such that the set

is monochromatic. Finally let be defined by for each . Since we deduce that , and hence the set (2) contains the -set , which is then monochromatic as desired.

Pingback: New polynomial and multidimensional extensions of classical partition results | I Can't Believe It's Not Random!