Hales-Jewett Theorem

— 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 {3\times3\times3} 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 {4\times4\times4} cube and a player wins if he can get {4} 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 {d}-dimensional cube {[k]^d} and the idea is to make {k} 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 {k\in{\mathbb N}} there is a dimension {d\in{\mathbb N}} such that a game of tic-tac-toe on the cube {[k]^d} never ends in a draw?

To make things even more interesting, what if we have {r} players instead? The Hales-Jewett theorem answers affirmatively to this problem.

— 3. Definitions —

For an integer {n\in{\mathbb N}} we denote by {[n]} the set {\{1,2,...,n\}}. Our first definition is that of a variable word. This is some variable element of the cube {[k]^d}, so a variable word looks like {(3,5,1,*,4,2,*,5,8)}. More precisely

Definition 1 (Variable word) Given {k,d\in{\mathbb N}}, a {d}-dimensional variable word on {k} letters is an element of

\displaystyle \left([k]\cup\{*\}\right)^d\setminus[k]^d

In the same way as polynomials are both algebraically defined and functions, combinatorial words define functions in the usual way. Thus if {w} is a combinatorial word (we will often omit the parameters {d} and {k} as they are usually clear) we denote by {w(i)} the element of {[k]^d} that agrees with {w} in all the coordinates of {w} that are in {[k]} and {i} in the coordinates of {w} that are {*}. For instance, if {w=(2,6,*,2,*,2)} then {w(4)=(2,6,4,2,4,2)} and {w(9)=(2,6,9,2,9,2)}. Note that a {d}-dimensional variable word on {k} letters maps {[k']} to {[k']^d} for any {k'>k}.

We will also need an extension to words with several variables:

Definition 2 (Multi-variable word) Given {k,d,m\in{\mathbb N}}, a {d}-dimensional {m}-variable word on {k} letters is an element of {\left([k]\cup\{*_1,...,*_m\}\right)^d\setminus[k]^d} that “uses” all the symbols {*_i} at least once.

For instance {(1,*_1,4,*_2,5)} is a {2}-variable word, but {(1,3,4,*_2,5)} is not because {*_1} does not appear. Like {1}-variable words, we can also see {m}-variable words as maps {[k]^m\rightarrow[k]^d}, and more generally as maps {[k']^m\rightarrow[k']^d} for any {k'\geq k}. An almost obvious property of this maps is that the composition of two {m}-variable words (not necessarily the same {m}) is again a {m}-variable word.

Definition 3 (Combinatorial Line and subspace)

  • A {m}-dimensional combinatorial subspace of {[k]^d} is the image of a {m}-variable word.
  • A combinatorial line is a {1}-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 {r\in{\mathbb N}} and {A} be a set. A {r}-coloring of {A} is a function {c:A\rightarrow[r]}. A subset {B\subset A} is monochromatic (with respect to the coloring {c}) if {c(b)} is the same for all {b\in B}.

We can now state the Hales-Jewett Theorem:

Theorem 5 (Hales-Jewett) For each {k,r\in{\mathbb N}} there exists some {d=d(k,r)} such that any for any {r}-coloring of {[k]^d}, there is a monochromatic combinatorial line.

In order to prove this theorem we end up proving its multidimensional version, namely:

Theorem 6 (Multidimensional Hales-Jewett) For each {k,r,m\in{\mathbb N}} there exists some {d=d(k,r,m)} such that any for any {r}-coloring of {[k]^d}, there is a monochromatic {m}-dimensional combinatorial subspace.

We will need to use some additional notation in the proof of this Theorem: if {x=(x_1,...,x_d)\in[k]^d} and {y=(y_1,...,y_g)\in[k]^g}, then we denote by {x^\frown y} the element {(x_1,...,x_d,y_1,...,y_g)\in[k]^{d+g}}.

— 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 {k}. The case {k=1} is trivial, however for each next {k} we need to make an induction on {r}. Again for {r=1} the result is trivial, but here is where things get trick; it turns out that to induce on {r} we need to use not only the Hales-Jewett but actually the multidimensional Hales-Jewett for previous {k}.

If we call {HJ(k,r,m)} to the statement that the Theorem 6 holds for {k,r,m} then the chain of implications goes like this

\displaystyle  \begin{array}{rcl} (\forall r,m)HJ(1,r,m)&\Rightarrow& HJ(2,2,1)\Rightarrow HJ(2,3,1)\Rightarrow...\Rightarrow(\forall r)HJ(2,r,1)\\&\Rightarrow&(\forall r)HJ(2,r,2)\Rightarrow...\Rightarrow(\forall r,m)HJ(2,r,m)\\&\Rightarrow&(\forall r,m)HJ(2,r,m)\Rightarrow...\Rightarrow(\forall k,r,m)HJ(k,r,m) \end{array}

I first prove the implications in the second line, but with {k=2} replaced by any {k\in{\mathbb N}}. This is the content of the Lemma 7 and is an induction on {m}. Then we prove the implications in the first line, again for a general {k\in{\mathbb N}}. That is done in the Lemma 8 and is an induction on {r}. Finally we conclude the proof with an induction on {k}.

Lemma 7 Let {k\in{\mathbb N}}. If for all {r\in{\mathbb N}} we have {HJ(k,r,1)} then we have {HJ(k,r,m)} for all {r,m\in{\mathbb N}}.

In other words this Lemma states the the Hales-Jewett Theorem implies the multidimensional hales-Jewett Theorem.

Proof: We proceed by induction on {m}. For {m=1} there is nothing to prove. Now assume that {m>1} and we have {HJ(k,r,m-1)} for all {r\in{\mathbb N}}. Fix {r\in{\mathbb N}}. Let {d_1=d(k,r,1)}, let {\tilde r=r(k+1)^d_1} and let {d_2=d(k,\tilde r,m-1)} (here {d} is the function defined in the statement of there Theorem 6). I claim that {d(k,r,m)\leq d:=d_1+d_2} (and in particular it exists and hence {HJ(k,r,m)} exists as desired).

Let {c:[k]^d\rightarrow[r]} be an arbitrary {r}-coloring of {[k]^d}. For each {y\in[k]^{d_2}}, let {c_y[k]^{d_1}\rightarrow[r]} be given by {c_y(x)=c(x^\frown y)}. Thus for each {y\in[k]^{d_2}} there is monochromatic combinatorial line in {[k]^{d_1}} with respect to {c_y}. Let {L} be the set of all combinatorial lines in {[k]^{d_1}}. Since combinatorial lines are indexed by variable words, we have {|L|\leq (k+1)^{d_1}}. We now assign to each {y\in[k]^{d_2}} the pair {\tilde c(y)=(i_y,\ell_y)\in[r]\times L} such that for each {x\in\ell_y} we have {c(x^\frown y)=i_y}.

This induces a {\tilde r}-coloring {\tilde c:[k]^{d_2}\rightarrow[r]\times L}, thus there exists a monochromatic {m-1}-dimensional combinatorial subspace. Let {w} be the {m-1}-variable word that generates that subspace, let {i\in[r]} and {\ell\in L} be such that {\tilde c(y)=(i,\ell)} for all {y} in the subspace generated by {w}. Also let {z} be the variable word that generates {\ell}. Then {w^\frown y} is a {m}-variable word that generates a {m}-dimensional combinatorial subspace with color {i}. \Box

Next lemma shows how {HJ(k,r-1,1)} together with {HJ(k-1,r,m)} for all {r,m\in{\mathbb N}} imply {HJ(k,r,1)}.

Lemma 8 Let {k\in{\mathbb N}}. If for all {m,r\in{\mathbb N}} we have {HJ(k-1,r,m)}, then we also have {HJ(k,r,1)} for all {r\in{\mathbb N}}.

Proof: We prove this by induction on {r}. For {r=1} the result is trivial. Now assume that we have {HJ(k,r-1,1)}, let {m=d(k,r-1,1)} and let {d=d(k-1,r,m+1)}. Let {c:[k]^d\rightarrow[r]} be an arbitrary coloring, note that this induces a coloring on {[k-1]^d\subset[k]^d}. Thus we can find a {m+1}-variable word {w\in\left([k-1]\cup \{*_1,...,*_{m+1}\}\right)^d} such that {w([k-1]^{m+1})} is monochromatic, say {c(w(x))=r} for each {x\in[k-1]^{m+1}}.

We now separate into two cases: in the first case there is some {x\in[k]^{m+1}} such that at least one of the coordinates {x_i=k} and {c(w(x))=r}; in the second case we have that for all {x\in[k]^{m+1}} such that at least one of the coordinates {x_i=k}, then {c(w(x))\in[r-1]}.

For the first case choose such an {x} and consider the variable word {y=(y_1,...,y_{m+1})\in\left([k]\cup\{*\}\right)^{m+1}} by {y_i=x_i} if {x_i\in[k-1]} and {y_i=*} if {x_i=k}. Note in particular that {y(k)=x}. Then {w(y([k])} is a combinatorial line on {[k]^d} and then {c(w(y(k)))=c(w(x))=r} and for each {i\in[k-1]} we have that {y(i)\in[k-1]^{m+1}}, so {c(w(y(i)))=r}. Thus {c(w(y([k]))=1} and we are done.

For the second case, we define a {[r-1]} coloring of {[k]^m} by {\tilde c(x)=c(w(x^\frown k))}. Let {z\in\left([k]\cup\{*\}\right)^m} be a variable word that gives a monochromatic combinatorial line for {\tilde c}, say {\tilde c(z([k])=1}. Then {z([k])^\frown k} is also a combinatorial line of {[k]^{m+1}} and hence {w(z([k])^\frown k)} is also a combinatorial line of {[k]^d}, and by construction it is easy to see that it is monochromatic. \Box

Finally we put both lemmas together to conclude the proof of the Theorem 6:

Proof: (of the Theorem 6) We proceed by induction in {k}. For {k=1} the result is trivial, now let {k>1} and assume that we have {HJ(k-1,r,m)} for all {r,m\in{\mathbb N}}. By the Lemma 8 we also have {HJ(k,r,1)} for all {r\in{\mathbb N}}. But now by the Lemma 7 we ge that we also have {HJ(k,r,m)} for all {m,r\in{\mathbb N}} and this completes the induction. \Box

One of the most interesting things to me is that in order to prove {HJ(k,2,1)} one actually has to prove {HJ(k,r,m)} for every {r,m\in{\mathbb N}}, the point is that we need stronger hypothesis for induction. I don’t know if someone found a proof that proves directly {HJ(k,2,1)} 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 {k,r\in{\mathbb N}} there is some {N\in{\mathbb N}} such that for any coloring {c:[N]\rightarrow[r]} there is a monochromatic arithmetic progression with length {k} ({k}-AP for short).

Proof: The idea is to write natural numbers in base {k}, in other words, consider the bijection {f:[k]^d\rightarrow[k^d]} (assuming now that {[k]=\{0,1,...,k-1\}}) given by

\displaystyle f(x_0,...,x_{d-1})=x_0+x_1k+...+x_{d-1}k^{d-1}

Then given any variable word {y\in\left([k]\cup\{*\}\right)^d}, the combinatorial line generated by {y} is mapped (through {f}) to the {k}-AP {\{a+is:i\in[k]\}} where {a=f(y(0))} and {s=\sum k^i} where the sum goes through all {i\in[k]} such that {y_i=*}. To finish we just need to take {N=k^d}. \Box

Another interesting application of the Hales-Jewett Theorem answers the following question: For each fixed {k\in{\mathbb N}}, is it possible to find some subset {A_k\subset{\mathbb N}} without any {(k+1)}-AP but such that any finite coloring of {A} contains a monochromatic {k}-AP? The answer is yes:

Corollary 10 Let {k\in{\mathbb N}} and {B\geq2k}. Then the set

\displaystyle A=\left\{\sum_{i=0}^na_iB^i:n=0,1,...; a_i=0,1,...,k-1\right\}

has no {(k+1)}-AP but for any finite coloring it contains a monochromatic {k}-AP.

For instance if we put {k=5} then {A} is the set of all integers that only use the digits {0,...,4} (when written in base {10}) It may clarify the second part of the proof bellow to use this as a model. Proof: Given any coloring of {A} into {r} colors, let {d=d(k,r,1)} given by the Hales-Jewett Theorem and let {f:[k]\rightarrow A} be defined by

\displaystyle f(x_0,...,x_{d-1})=\sum_{i=0}^{d-1}x_iB^i

Since {f} is injective, the {r}-coloring of {A} induces a {r}-coloring of {[k]^d}, which contains a monochromatic combinatorial line. But this combinatorial line is mapped into a {k}-AP by {f}.

To prove that {A} has no {(k+1)}-AP we prove by induction on {N} that the set

\displaystyle A_N=\left\{\sum_{i=0}^Na_iB^i: a_i=0,1,...,k-1\right\}

doesn’t have and the result follows from the observation that {A=\bigcup A_N}. That {A_0} doesn’t have any {(k+1)}-AP is trivial because {|A_0|=k}. Now assume that {N\in{\mathbb N}} and {A_{N-1}} doesn’t contain any {(k+1)}-AP. Also note that

\displaystyle \displaystyle A_N=\bigcup_{i=0}^{k-1}\left(A_{N-1}+iB^N\right)

If a {(k+1)}-AP, say {P=\{a+js:s\in[k+1]\}}, is contained in {A_N}, then (by pigeonhole principle) it has two elements in the same shift {A_{N-1}+iB^N} and so

\displaystyle s\leq\max(A_{N-1})=(k-1)\frac{B^N-1}{B-1}<\frac{k-1}{B-1}B^N\leq\frac12B^N

On the other hand, by the induction hypothesis, {P} has two elements (hence consecutive) in different shifts of {A_{N-1}}, thus

\displaystyle s\geq B^N-\max(A_{N-1})=B^N-(k-1)\frac{B^N-1}{B-1}\geq B^N\left(1-\frac{k-1}{B-1}\right)\geq \frac12B^N

The strict inequality in the previous equation makes this a contradiction, hence {A} has no {(k+1)}-AP as we wanted to show. \Box

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.

This entry was posted in Combinatorics, Ramsey Theory and tagged , , . Bookmark the permalink.

3 Responses to Hales-Jewett Theorem

  1. Pingback: Hales-Jewett and a generalized van der Warden Theorems | I Can't Believe It's Not Random!

  2. Pingback: A proof of Deuber’s theorem using Hales-Jewett’s theorem | I Can't Believe It's Not Random!

  3. Pingback: An arithmetic van der Corput trick and the polynomial van der Waerden theorem | I Can't Believe It's Not Random!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s