Hales–Jewett theorem

Remarks

Example: for $k = 2$ and $r = 2$ one can take $N = 2$. The square $[2]^2$ has the five lines $\set{11, 21}$, $\set{12, 22}$, $\set{11, 12}$, $\set{21, 22}$ and $\set{11, 22}$. In a $2$-colouring, either $11$ and $22$ have the same colour, or the word $12$ has the colour of one of them and lies on a line with it. For $n = 1$ the only line is $\set{1, 2}$, which is not monochromatic when $1$ and $2$ get different colours. The original proof, by induction on $k$, gives very large bounds; Shelah found a proof with primitive recursive bounds. The theorem implies van der Waerden's theorem. Use the alphabet $\set{0, \ldots, k-1}$ and map a word $w$ to $w_1 + \cdots + w_n$. A combinatorial line goes to an arithmetic progression of length $k$ whose common difference is the number of $*$ symbols. The density version says that, for large $n$, every set containing a fixed positive fraction of $[k]^n$ contains a combinatorial line. It was proved by Furstenberg and Katznelson, and later by an elementary method in the Polymath project.

Going deeper

For a student

The Hales–Jewett theorem is the abstract core of many Ramsey statements about arithmetic structure. It needs no arithmetic at all: only words and substitution. From it follow van der Waerden's theorem and its multidimensional form, the Gallai–Witt theorem. Its density version similarly implies Szemerédi's theorem.