— 1. Introduction —
One of the earliest posts I wrote on this blog contained a proof of the van der Waerden’s Theorem on arithmetic progressions. That proof was topological in nature and illustrated the interesting relation between some problems in combinatorics and recurrence in dynamical systems. Of course the original proof given by van der Waerden was purely combinatorial, you can read a nicely explained combinatorial proof on this other blog. As I understand it, the same ideas explained in that post were somehow behind the original approach.
It turns out that the combinatorial proof can be adapted to prove the generalization of the van der Waerden’s Theorem now known as Hales-Jewett Theorem. I learned this proof recently, and it was the first time I truly understood the combinatorial proof of the van der Waerden’s Theorem. In this post I will present that combinatorial proof of the Hales-Jewett Theorem.
— 2. Motivation —
In this section I give some motivation for why the Hales-Jewett Theorem is interesting on its own, thus this section is not necessary to understand the proof (or formulation) of the Theorem.
Everyone has played the Tic-Tac-Toe, but the main frustrations with that game is that almost all games end in a draw. What if we try an extension of the game? To make things more interesting we can play in a cube. But here it is easy to see that the first player has a winning strategy.
Now we may want to try to play on a cube and a player wins if he can get marks in a row (it was shown in this paper that such a game has always a winner). More generally we can play in the -dimensional cube and the idea is to make marks in a row. We are interested only in generalizations that don’t allow for ties, thus the question that arises is: whether for any there is a dimension such that a game of tic-tac-toe on the cube never ends in a draw?
To make things even more interesting, what if we have players instead? The Hales-Jewett theorem answers affirmatively to this problem.
— 3. Definitions —
For an integer we denote by the set . Our first definition is that of a variable word. This is some variable element of the cube , so a variable word looks like . More precisely
Definition 1 (Variable word) Given , a -dimensional variable word on letters is an element of
In the same way as polynomials are both algebraically defined and functions, combinatorial words define functions in the usual way. Thus if is a combinatorial word (we will often omit the parameters and as they are usually clear) we denote by the element of that agrees with in all the coordinates of that are in and in the coordinates of that are . For instance, if then and . Note that a -dimensional variable word on letters maps to for any .
We will also need an extension to words with several variables:
Definition 2 (Multi-variable word) Given , a -dimensional -variable word on letters is an element of that “uses” all the symbols at least once.
For instance is a -variable word, but is not because does not appear. Like -variable words, we can also see -variable words as maps , and more generally as maps for any . An almost obvious property of this maps is that the composition of two -variable words (not necessarily the same ) is again a -variable word.
Definition 3 (Combinatorial Line and subspace)
- A -dimensional combinatorial subspace of is the image of a -variable word.
- A combinatorial line is a -dimensional combinatorial space, equivalently is the image of a variable word.
Note that a combinatorial line is a winning configuration for the generalized tic-tac-toe game described in the previous section.
Finally we need the notion of coloring and monochromatic set:
Definition 4 Let and be a set. A -coloring of is a function . A subset is monochromatic (with respect to the coloring ) if is the same for all .
We can now state the Hales-Jewett Theorem:
In order to prove this theorem we end up proving its multidimensional version, namely:
We will need to use some additional notation in the proof of this Theorem: if and , then we denote by the element .
— 4. Proof of the Hales-Jewett Theorem —
In this section we give the proof of the Theorem 5. The idea is to prove by induction on . The case is trivial, however for each next we need to make an induction on . Again for the result is trivial, but here is where things get trick; it turns out that to induce on we need to use not only the Hales-Jewett but actually the multidimensional Hales-Jewett for previous .
If we call to the statement that the Theorem 6 holds for then the chain of implications goes like this
I first prove the implications in the second line, but with replaced by any . This is the content of the Lemma 7 and is an induction on . Then we prove the implications in the first line, again for a general . That is done in the Lemma 8 and is an induction on . Finally we conclude the proof with an induction on .
In other words this Lemma states the the Hales-Jewett Theorem implies the multidimensional hales-Jewett Theorem.
Proof: We proceed by induction on . For there is nothing to prove. Now assume that and we have for all . Fix . Let , let and let (here is the function defined in the statement of there Theorem 6). I claim that (and in particular it exists and hence exists as desired).
Let be an arbitrary -coloring of . For each , let be given by . Thus for each there is monochromatic combinatorial line in with respect to . Let be the set of all combinatorial lines in . Since combinatorial lines are indexed by variable words, we have . We now assign to each the pair such that for each we have .
This induces a -coloring , thus there exists a monochromatic -dimensional combinatorial subspace. Let be the -variable word that generates that subspace, let and be such that for all in the subspace generated by . Also let be the variable word that generates . Then is a -variable word that generates a -dimensional combinatorial subspace with color .
Next lemma shows how together with for all imply .
Proof: We prove this by induction on . For the result is trivial. Now assume that we have , let and let . Let be an arbitrary coloring, note that this induces a coloring on . Thus we can find a -variable word such that is monochromatic, say for each .
We now separate into two cases: in the first case there is some such that at least one of the coordinates and ; in the second case we have that for all such that at least one of the coordinates , then .
For the first case choose such an and consider the variable word by if and if . Note in particular that . Then is a combinatorial line on and then and for each we have that , so . Thus and we are done.
For the second case, we define a coloring of by . Let be a variable word that gives a monochromatic combinatorial line for , say . Then is also a combinatorial line of and hence is also a combinatorial line of , and by construction it is easy to see that it is monochromatic.
Finally we put both lemmas together to conclude the proof of the Theorem 6:
Proof: (of the Theorem 6) We proceed by induction in . For the result is trivial, now let and assume that we have for all . By the Lemma 8 we also have for all . But now by the Lemma 7 we ge that we also have for all and this completes the induction.
One of the most interesting things to me is that in order to prove one actually has to prove for every , the point is that we need stronger hypothesis for induction. I don’t know if someone found a proof that proves directly without proving more.
— 5. Some consequences of the Hales-Jewett Theorem —
The first consequence is the van der Waerden Theorem:
Theorem 9 (van der Waerden) For each there is some such that for any coloring there is a monochromatic arithmetic progression with length (-AP for short).
Proof: The idea is to write natural numbers in base , in other words, consider the bijection (assuming now that ) given by
Then given any variable word , the combinatorial line generated by is mapped (through ) to the -AP where and where the sum goes through all such that . To finish we just need to take .
Another interesting application of the Hales-Jewett Theorem answers the following question: For each fixed , is it possible to find some subset without any -AP but such that any finite coloring of contains a monochromatic -AP? The answer is yes:
Corollary 10 Let and . Then the set
has no -AP but for any finite coloring it contains a monochromatic -AP.
For instance if we put then is the set of all integers that only use the digits (when written in base ) It may clarify the second part of the proof bellow to use this as a model. Proof: Given any coloring of into colors, let given by the Hales-Jewett Theorem and let be defined by
Since is injective, the -coloring of induces a -coloring of , which contains a monochromatic combinatorial line. But this combinatorial line is mapped into a -AP by .
To prove that has no -AP we prove by induction on that the set
doesn’t have and the result follows from the observation that . That doesn’t have any -AP is trivial because . Now assume that and doesn’t contain any -AP. Also note that
If a -AP, say , is contained in , then (by pigeonhole principle) it has two elements in the same shift and so
On the other hand, by the induction hypothesis, has two elements (hence consecutive) in different shifts of , thus
The strict inequality in the previous equation makes this a contradiction, hence has no -AP as we wanted to show.
I plan to post soon about the infinitistic and density versions of the Hales-Jewett Theorem and connections with the analog versions of the van der Waerden Theorem.