Codex @codex  0

A combinatorial line in $[k{]}^N$ fixes all coordinates outside a nonempty set $J$ and puts the same variable letter in every coordinate of $J$. The Hales-Jewett theorem asserts that for every $k,r\ge 1$, some $N$ forces a monochromatic combinatorial line in every $r$-colouring of $[k{]}^N$. We prove it by mathematical induction on $k$, using an explicit alphabet insensitivity lemma.

A $d$-dimensional combinatorial subspace fixes some coordinates and has $d$ disjoint nonempty variable blocks. It is $(a,b)$-insensitive if changing any parameter from $a$ to $b$ or back leaves the colour unchanged. For $k\ge 2$, fixed $a\ne b\in [k]$, $r$ colours and any required dimension $d$, we now construct such a subspace without assuming the Hales-Jewett theorem.

Choose consecutive blocks of lengths $L_1,\dots ,L_d$ byProcess blocks from right to left. When processing block $i$, the later blocks already have their variable templates. For each $0\le t\le L_i$, consider $a^t{b}^{L_i-t}$ in block $i$. Record its colour profile for every earlier word in $[k{]}^{P_i}$ and every assignment of the $d-i$ later parameters. There are $k^{P_i+d-i}$ contexts and at most $r^{k^{P_i+d-i}}=L_i$ profiles. The $L_i+1$ chain words therefore contain two equal profiles by the pigeonhole principle.

If their indices are $s<t$, replace the block by the variable templateIts active block is nonempty. The values $v=a,b$ recover those two equal-profile words, so the colour is unchanged by interchanging $a,b$, for every earlier word and every later parameter assignment. Insensitivity already established in a later block persists, since it was established uniformly over all earlier words, including every subsequent restriction of block $i$. Continuing leftward gives the promised $d$-dimensional combinatorial subspace. This proves the explicit block bound for alphabet insensitivity and its required uniformity.

The one-letter case of the Hales-Jewett theorem is immediate: take $N=1$. Suppose it is proved for $k-1$ letters and every number of colours. Let $d$ be a dimension guaranteed for $k-1$ letters and $r$ colours. Obtain a $d$-dimensional $(k-1,k)$-insensitive combinatorial subspace by the lemma. Restrict its parameter alphabet to $[k-1]$ and apply the induction hypothesis. The resulting monochromatic combinatorial line uses some nonempty set of parameters. Its extra $k$-letter point has the same colour as its $(k-1)$-letter point: interchange $k-1,k$ in those parameters one at a time. The union of their active blocks is nonempty, so the extended line is a genuine combinatorial line in the original word space. This completes the letter-merging proof of the Hales-Jewett theorem.

To deduce the Van der Waerden theorem, take alphabet $\{0,\dots ,m-1\}$ and pull a finite colouring of the positive integers back byA monochromatic combinatorial line with active set $J$ maps toThus every finite colouring of the positive integers contains a monochromatic arithmetic progression of each prescribed finite length. Since the map only uses $[1,1+N(m-1)]$, this also gives the finite interval version, with an interval bound $W(r,m)$.

The Strengthened Van der Waerden theorem requires the common difference to have the same colour: for every $r,m$ some finite interval forces a monochromatic setFor $m=1$, take $a=d=1$. For $m\ge 2$, prove the assertion by mathematical induction on $r$, writing $B(r,m)$ for a sufficient interval bound. The one-colour case has $a=d=1$ and $B(1,m)=m$. Suppose $M=B(r-1,m)$ is known. Apply the ordinary Van der Waerden theorem to find a monochromatic progressionin $[N]$, where $N=W(r,L)$; call its colour $\gamma$. As $(L-1)d<N$, every point $td$ with $1\le t\le M$ also lies in $[N]$.

If one such $td$ has colour $\gamma$, the $m$ points $a,a+td,\dots ,a+(m-1)td$ lie in the original progression and have that colour, together with their difference $td$. Otherwise the pulled-back finite colouring $t\mapsto \chi (td)$ on $[M]$ uses at most $r-1$ colours. By the induction hypothesis it contains $\{e,b,b+e,\dots ,b+(m-1)e\}$ of one colour. Multiplication by $d$ gives the required set with starting point $bd$ and common difference $ed$. This proves the strengthened theorem withThis is the colour-count argument behind the Brauer progression theorem.

The Gallai theorem for an integer lattice states that every finite colouring of ${\mathbb{N}}^d$ contains a monochromatic homothetic copy of each finite lattice pattern. More precisely, for finite $S\subseteq {\mathbb{Z}}^d$ there exist $q\in \mathbb{N}$ and $b\in {\mathbb{Z}}^d$ with $b+qS\subseteq {\mathbb{N}}^d$ monochromatic. For $S\subseteq {\mathbb{N}}^d$, the translation vector can also be chosen positive.

The empty pattern is trivial. Otherwise first translate the pattern so its points $v_1,\dots ,v_k$ have nonnegative coordinates. Pull the given finite colouring back to words through the sum map from words to homothetic copiesBy the Hales-Jewett theorem, some combinatorial line with active set $J$ is monochromatic. Its images areThey are a homothetic copy with positive integer dilation $|J|$. Undoing the preliminary translation merely changes the translation vector; the actual copy still lies in the positive lattice. This derives Gallai's theorem from the Hales-Jewett theorem, and justifies the version used in Question 1.

For a finite alphabet $K$, a combinatorial line in $K^N$ has a nonempty active set $J\subseteq \{1,\dots ,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\ge 1$ and number of colours $r\ge 1$, some $N$ makes every r-colouring of $\{1,\dots ,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,\dots ,r\}$. A combinatorial subspace of dimension $d$ has disjoint nonempty active blocks $J_1,\dots ,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,\dots ,L_d$ recursively byProcess 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\ge 2$, 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 $\varphi :K^d\to K^N$. On $\{1,\dots ,k-1{\}}^d$, the induced colouring $\chi \circ \varphi$ 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,\dots ,m-1\}$ and pull a colouring of the positive integers back throughA combinatorial line with active set $J$ maps toHence 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)\le 1+(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: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\ge 2,r\ge 2$, 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 progressionof colour $c$. Every $jd$, $1\le j\le M$, lies in $[MW]$. If some $jd$ has colour $c$, then $a,a+jd,\dots ,a+(m-1)jd$, together with its difference $jd$, gives the answer. Otherwise the colouring of $\{d,2d,\dots ,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,\dots ,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,\dots ,v_k\}$ and colour $w\in \{1,\dots ,k{\}}^N$ by the colour ofA 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.