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.
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:
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 3 Let with and let . We define the set
Also 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 4 Let , let be a finite set and let be an element not in .
- A variable word in 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 line induced by is the set .
— 2. Proof of Deuber’s theorem —
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 6 Let with . A coloring of an -set is called -regular if 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:
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
I claim that is a -regular subset of . I will separate this into 3 claims:
Claim 1 For 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 2 The 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 3 For each , the line is contained in .
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.
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.