= Solution
\b[Hales–Jewett and the arithmetic-progression consequence.] For a finite <alphabet> $[m]$ and a positive integer $r$, the <Hales-Jewett theorem> gives an integer $N$ such that every $r$-color <finite coloring> of $[m]^N$ contains a <monochromatic> <combinatorial line>. A <combinatorial line> has a nonempty active coordinate set: all those coordinates receive the same freely varying letter, and the remaining coordinates are fixed.
We first prove the <alphabet insensitivity lemma>. Fix two letters $a,b\in[m]$, with $m\geq2$, and a desired dimension $d$. There is a <combinatorial subspace> of dimension $d$ on which changing $a$ to $b$ in any variable coordinate, with all other variable coordinates arbitrary, preserves the color.
For the construction, divide the coordinates into $d$ consecutive blocks. Choose their lengths from left to right by
$$
P_i=\sum_{j<i}L_j,\qquad L_i=r^{\,m^{P_i+d-i}}.
$$
Process the blocks from right to left. When processing block $i$, the later blocks already form a $(d-i)$-dimensional <combinatorial subspace>. Color each word in block $i$ by the vector of its original colors for every prefix word of length $P_i$ and every assignment to those later variables. There are $m^{P_i+d-i}$ contexts, and at most $r^{m^{P_i+d-i}}=L_i$ such color vectors.
The $L_i+1$ words $a^j b^{L_i-j}$, $0\leq j\leq L_i$, contain two, indexed by $u<v$, with the same vector by the <pigeonhole principle>. Fix the first $u$ coordinates to $a$, the coordinates after $v$ to $b$, and make coordinates $u+1,\ldots,v$ the active set of one new variable. Its values $a,b$ now have identical colors for every prefix and later-variable context. The active set is nonempty. Insensitivity already obtained in later blocks survives, because it held for every unrestricted earlier prefix. After all $d$ blocks have been processed, changing $a,b$ in any of the $d$ variables preserves the color. This proves the lemma.
Now induct on $m$. For $m=1$, a one-coordinate <combinatorial line> is automatically <monochromatic>. For $m\geq2$, let $d$ be a length supplied by the theorem for <alphabet> $[m-1]$ and $r$ colors. Apply the <alphabet insensitivity lemma> for the letters $m-1,m$ to obtain a $d$-dimensional <combinatorial subspace>. Restrict its variables to $[m-1]$. Induction gives a <monochromatic> <combinatorial line> in those variables. Its values $1,\ldots,m-1$ have the same color, and its value $m$ has the same color as its value $m-1$ by successively switching the active variables. Lifting this line to the original coordinates proves
$$
\boxed{\text{every finite coloring of a sufficiently long word space has a monochromatic line}.}
$$
For the <Van der Waerden theorem>, fix a progression length $k\geq2$ and use the <alphabet> $\{0,\ldots,k-1\}$. Pull back an $r$-color <finite coloring> of $\{1,\ldots,1+(k-1)N\}$ along
$$
(x_1,\ldots,x_N)\longmapsto1+\sum_{j=1}^N x_j.
$$
A <combinatorial line> with active set $S$ maps to the <arithmetic progression> $a,a+q,\ldots,a+(k-1)q$, where $a\geq1$ and its <common difference> is $q=|S|>0$. The <Hales-Jewett theorem> makes this progression <monochromatic>. Length one is trivial, so every <finite coloring> of the <positive integers> contains <monochromatic> <arithmetic progressions> of every finite length.
\b[The active-coordinate obstruction.] Color a word red when its first coordinate is $1$, and blue otherwise. Any <combinatorial line> whose active coordinate set contains $1$ has a red word at variable value $1$ and a blue word at variable value $2$, since $m>1$. Thus
$$
\boxed{\{S\subseteq[n]:1\in S\}\text{ is not adequate}.}
$$
Here adequacy is the <adequate family of active coordinate sets> property; an active coordinate set is always nonempty.
Back to article page
