Alphabet insensitivity lemma

For a finite coloring of $[m{]}^N$, a combinatorial subspace is $(a,b)$-insensitive if replacing $a$ by $b$, or conversely, in any of its variable coordinates leaves the color unchanged. For every number of colors, alphabet size $m\ge 2$, and dimension $d$, sufficiently large $N$ guarantees such a $d$-dimensional combinatorial subspace for any specified distinct letters $a,b$.

A proof uses the pigeonhole principle on chains $a^j{b}^{L-j}$ in consecutive coordinate blocks. Choose block lengths from left to right, making each long enough to pigeonhole the vector of colors for every earlier word and every later variable assignment. Process the blocks from right to left. Two equal color vectors give a nonempty variable interval insensitive to $a,b$. Insensitivity already obtained in later blocks survives all restrictions of earlier coordinates. This lemma proves the Hales-Jewett theorem by induction on alphabet size.

For r colours, k letters and d variable blocks, set $P_i={\sum }_{j<i}{L}_j$ and $L_i=r^{k^{P_i+d-i}}$. Process blocks from right to left. In block i, the $L_i+1$ words $a^t{b}^{L_i-t}$ have colour profiles indexed by all $k^{P_i}$ earlier words and $k^{d-i}$ later variable assignments. Two profiles agree, giving a nonempty variable interval insensitive to exchanging a and b. Previously obtained insensitivity holds for all earlier words and survives their restriction. This constructs the combinatorial subspace required by the alphabet insensitivity lemma.