= Solution
For a finite alphabet $K$, a <combinatorial line> in $K^N$ has a nonempty active set $J\subseteq\{1,\ldots,N\}$, fixed letters outside $J$, and the same variable letter at every coordinate in $J$. The <Hales-Jewett theorem> states that for every alphabet size $k\ge1$ and number of colours $r\ge1$, some $N$ makes every r-colouring of $\{1,\ldots,k\}^N$ contain a <monochromatic> <combinatorial line>.
We first prove the <alphabet insensitivity lemma> with a concrete bound. Fix two distinct letters $a,b$, a desired dimension $d$, and a colouring $\chi:K^N\to\{1,\ldots,r\}$. A <combinatorial subspace> of dimension $d$ has disjoint nonempty active blocks $J_1,\ldots,J_d$ and fixed other coordinates. It is $(a,b)$-insensitive when exchanging $a,b$ in any one variable leaves the colour unchanged, whatever the other variable letters are.
Choose consecutive blocks of lengths $L_1,\ldots,L_d$ recursively by
$$
P_i=\sum_{j<i}L_j,\qquad L_i=r^{\,k^{P_i+d-i}},\qquad N=\sum_{i=1}^dL_i.
$$
Process these blocks from right to left. When block $i$ is reached, the later blocks already have one variable each; the earlier $P_i$ coordinates are still entirely unrestricted. For each of the $L_i+1$ words $a^t b^{L_i-t}$ in block $i$, form its complete <colour profile> over all $k^{P_i}$ earlier words and all $k^{d-i}$ assignments to the later variables. There are at most $r^{k^{P_i+d-i}}=L_i$ profiles. The <pigeonhole principle> gives $s<t$ with equal profiles. Fix the first $s$ coordinates of this block to $a$, the coordinates after $t$ to $b$, and make the interval from $s+1$ to $t$ variable. Substitution of $b$ gives the chain word indexed by $s$, and substitution of $a$ gives the one indexed by $t$; they have identical profiles. Thus this variable is insensitive to $a,b$ for every remaining context. Previously constructed later variables remain insensitive, because their colour equalities held for every possible earlier word. After all $d$ blocks, we have the required insensitive <combinatorial subspace>. This proves the <explicit block bound for alphabet insensitivity>.
Now induct on $k$, simultaneously for every $r$. The case $k=1$ is immediate with $N=1$. For $k\ge2$, assume the <Hales-Jewett theorem> for the alphabet of size $k-1$, and take $d$ large enough for that theorem with $r$ colours. Apply the proved <alphabet insensitivity lemma> to the letters $k-1,k$, obtaining a d-dimensional <combinatorial subspace> $\phi:K^d\to K^N$. On $\{1,\ldots,k-1\}^d$, the induced colouring $\chi\circ\phi$ has a <monochromatic> <combinatorial line>. Its value at letter $k$ has the same colour as its value at $k-1$: change the active variables one at a time and use insensitivity. The <union> of their nonempty active blocks is the active set of a <combinatorial line> in the original word space. All its k points have one colour, completing the induction and the proof.
To deduce the <Van der Waerden theorem>, take $K=\{0,\ldots,m-1\}$ and pull a colouring of the <positive integers> back through
$$
\pi(w)=1+\sum_{j=1}^Nw_j.
$$
A <combinatorial line> with active set $J$ maps to
$$
a,a+d,\ldots,a+(m-1)d,\qquad
a=1+\sum_{j\notin J}w_j,\quad d=|J|>0.
$$
Hence \b[every <finite colouring> has a <monochromatic> <arithmetic progression> of every prescribed finite length]. In finite form, if $H(k,r)$ is a word-length bound for the <Hales-Jewett theorem>, then $W(r,m)\le1+(m-1)H(m,r)$ is a valid interval bound.
The <Strengthened Van der Waerden theorem> also puts the <common difference> in the colour class:
$$
\boxed{\{d,a,a+d,\ldots,a+(m-1)d\}\text{ is monochromatic for some }a,d>0.}
$$
Here is a finite proof by induction on the number $r$ of colours. For $m=1$ choose $a=d=1$. For $r=1$ choose $a=d=1$ in $[m]$. For $m\ge2,r\ge2$, let $M$ be a bound for the strengthened theorem with $r-1$ colours, put $L=(m-1)M+1$, and let $W=W(r,L)$ be an ordinary <Van der Waerden theorem> bound. Work in $[MW]$. Its first $W$ points contain a <monochromatic> progression
$$
a,a+d,\ldots,a+(L-1)d
$$
of colour $c$. Every $jd$, $1\le j\le M$, lies in $[MW]$. If some $jd$ has colour $c$, then $a,a+jd,\ldots,a+(m-1)jd$, together with its difference $jd$, gives the answer. Otherwise the colouring of $\{d,2d,\ldots,Md\}$ uses only $r-1$ colours. Pull it back to $[M]$ and apply the induction hypothesis to get a <monochromatic> set $\{e,b,b+e,\ldots,b+(m-1)e\}$. Multiplication by $d$ gives the required configuration in the original colouring. This proves the strengthened theorem, including finite bounds.
The <Gallai theorem for an integer lattice> states that every <finite colouring> of $\mathbb Z^h$ contains a <monochromatic> <homothetic copy> $u+tF$ of every prescribed finite nonempty pattern $F\subseteq\mathbb Z^h$, where $t$ is a <positive integer>. The positive-lattice version holds for finite $F\subseteq\mathbb N^h$ as well. Write $F=\{v_1,\ldots,v_k\}$ and colour $w\in\{1,\ldots,k\}^N$ by the colour of
$$
\pi(w)=b+\sum_{j=1}^Nv_{w_j}.
$$
A <monochromatic> <combinatorial line> maps to $u+|J|F$, with $u=b+\sum_{j\notin J}v_{w_j}$. Thus the <Hales-Jewett theorem> supplies the copy, with nonzero dilation $|J|$. Choosing $b$ large and positive places all these word sums in the positive lattice if required. This <sum map from words to homothetic copies> also proves the real-vector-space version: replace $\mathbb Z^h$ by $\mathbb R^h$ and allow an arbitrary finite real pattern, while retaining <positive integer> dilations.
Back to article page