Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 130 / 2

We prove the Hales-Jewett theorem by mathematical induction on the alphabet size. A combinatorial line has a nonempty active coordinate set, with one common letter in all those coordinates. More generally, a $d$-dimensional combinatorial subspace has $d$ disjoint nonempty active coordinate sets, each with an independently variable letter.

First prove the alphabet insensitivity lemma, rather than assume it. Fix distinct letters $a,b\in [m]$, $k$ colors, and dimension $d$. Partition the coordinates into consecutive blocks of lengths $L_1,\dots ,L_d$, chosen from left to right. Put $S_0=0$ and chooseConstruct the variable blocks from right to left. When working on block $i$, the later blocks have already become $(d-i)$-parameter words, while all earlier $S_{i-1}$ coordinates remain unrestricted. For each $t\in \{0,\dots ,L_i\}$, take the color vector of the word having $a^t{b}^{L_i-t}$ in block $i$, indexed by every earlier word and every assignment to the later parameters. There are $m^{S_{i-1}+d-i}$ entries and hence at most $L_i$ different vectors. The pigeonhole principle gives $t<s$ with identical vectors. Fix the first $t$ positions of this block to $a$, fix its last $L_i-s$ positions to $b$, and make the intervening $s-t$ positions a new variable block. Substituting $a$ or $b$ there gives exactly the two equal color vectors.

This equality holds for every earlier word and every later parameter assignment. Restricting the earlier coordinates in subsequent steps therefore preserves it. Likewise, the insensitivity already proved in a later block survives every restriction of earlier coordinates. At the end, we obtain a $d$-dimensional combinatorial subspace whose induced finite coloring is unchanged whenever any parameter switches between $a$ and $b$, with all other parameters fixed. Multiple switches preserve the color by successive single switches. This is the alphabet insensitivity lemma in full.

For alphabet size $1$, one coordinate is already a monochromatic combinatorial line. Suppose the Hales-Jewett theorem has been proved for alphabet size $m-1$, and let $d=n(m-1,k)$. Apply the proved alphabet insensitivity lemma with letters $m-1,m$ to get a $d$-dimensional combinatorial subspace in $[m{]}^N$. Restrict its parameter words to $[m-1{]}^d$. The induction hypothesis gives a monochromatic combinatorial line in these parameters. The union of its active parameter blocks is nonempty, so its image is a combinatorial line in the original coordinates. Its additional point with active letter $m$ has the same color as the point with active letter $m-1$, by insensitivity. Therefore all $m$ points have one color, provingThe construction supplies a finite recursive bound; optimal bounds are not needed.

Let the required arithmetic progression have length $m\ge 2$, let $k$ be the number of colors, and take $n=n(m,k)$ from the Hales-Jewett theorem. Given any finite coloring $\chi$ of $[mn]$, color a word over an alphabet $w\in [m{]}^n$ by $\chi (w_1+\cdots +w_n)$. For a monochromatic combinatorial line, let $A\ne \varnothing$ be its active coordinate set and let $C$ be the sum of its fixed coordinates. The sums of its $m$ words areThey all lie in $[mn]$, have one color, and form an arithmetic progression with strictly positive common difference $|A|$. Thus, writing $W(k,m)$ for the finite Van der Waerden theorem bound,The length-one case is immediate. Restricting a finite coloring of the positive integers to this finite integer interval gives the infinite-domain formulation of the Van der Waerden theorem as well.

A run of a word is a maximal consecutive block of equal letters. For every $N\ge 1$, use the following finite coloring of $[3{]}^N$, with at most nine colors:We show that this run-count obstruction to interval-active lines excludes every monochromatic combinatorial line with an interval active set $[a,b]$. If $a=1$, its three words already have different first coordinates, so their colors differ. Suppose $a>1$ and denote the letter immediately to the left by $p$. All contributions to $R(w)$ away from the two possible boundaries of $[a,b]$ are independent of its active letter $x$; no internal active boundary contributes a change.

If $b=N$, the only variable contribution is $1_{\{p\ne x\}}$, which is $0$ at $x=p$ and $1$ at another letter. If $b<N$, write $q$ for the letter immediately to the right. The variable contribution isWhen $p=q$, its values are $0$ and $2$. When $p\ne q$, it equals $1$ at $x=p$ or $x=q$, and equals $2$ at the third letter. In every case these values are distinct modulo $3$. Hence no dimension works for alphabet size three and nine colors, which disproves the proposed universal strengthening. For the PDF's illustrative line, choosing either adjacent letter merges one active run with a neighboring run, while choosing any other letter merges neither; this is exactly the boundary effect measured above. Recording the first letter also handles active intervals meeting the beginning, including the entire coordinate set.