Hales-Jewett theorem

We consider some classical theorems in arithmetic Ramsey theory, where one wants to find some monochromatic arithmetic structure (an arithmetic progression, for example) when a large set of integers or lattice points in $\mathbb{Z}^d$ is colored with several colors. Many such results follow from the Hales-Jewett theorem from 1963, stating that given any $k$ and $r$, there is a dimension $N$ such that when the lattice points of a cube of side length $k$ and dimension $N$ are colored with $r$ colors, there is a monochromatic combinatorial line. A combinatorial line is a line of length $k$ which is constant in some coordinates and increases with slope $1$ in the others.

We will prove the Hales-Jewett theorem, as its corollary the van der Waerden theorem, and a generalization of the latter, the Gallai-Witt theorem. The van der Waerden theorem from 1927 states that, given $k$ and $r$, there is $N$ such that if $\{1,2,...,N\}$ is colored with $r$ colors, there is a monochromatic arithmetic progression of length $k$. The smallest such $N$ is the van der Waerden number $W(k,r)$, and although they seem to grow fairly rapidly, the bounds given by the traditional double induction proofs are unimaginably large compared to what is expected. However, in 1988, Shelah found a one variable induction proof of the Hales-Jewett theorem in Primitive Recursive Bounds for Van Der Waerden Numbers, and this implied a bound that is still large but nothing compared to the previous bounds, which were functions that grow faster than any function defined by primitive recursion. We present in this post a proof of the Hales-Jewett theorem similar to Shelah's proof, and consider its consequences to the van der Waerden theorem and related results.