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.

Use $[m]=\{1,\dots ,m\}$. A combinatorial line in $[m{]}^n$ has one nonempty active set of coordinates, all carrying the same variable letter, with every other coordinate fixed. The Hales-Jewett theorem states that for every finite alphabet size $m$ and number of colours $k$, some $n$ makes every $k$-finite colouring of $[m{]}^n$ contain a monochromatic combinatorial line.

Here is a complete proof through the alphabet insensitivity lemma. A $d$-dimensional combinatorial subspace is obtained from $d$ pairwise disjoint nonempty coordinate blocks, one independently variable letter on each block, and fixed letters elsewhere. For two distinct letters $a,b$, a colouring restricted to such a combinatorial subspace is $(a,b)$-insensitive if switching $a$ and $b$ in any of its parameter coordinates leaves the colour unchanged, with all other letters and coordinates arbitrary.

We first prove that any desired dimension $d$ admits such an insensitive combinatorial subspace, using only the pigeonhole principle. Define finite bounds recursively bySplit the ambient coordinates into a prefix of length $L$ and a suffix of length $N$. For $0\le j\le L$, let the prefix $p_j$ consist of $j$ copies of $b$ followed by $L-j$ copies of $a$. Give it the entire colour profileThere are at most $k^{m^N}=L$ such profiles, but $L+1$ prefixes. Hence two prefixes $p_s,p_t$, $s<t$, have the same profile. Replace their differing coordinates $s+1,\dots ,t$ by one variable letter, obtaining a prefix word $v(x)$ with $v(a)=p_s$ and $v(b)=p_t$. Then $c(v(a)u)=c(v(b)u)$ for every suffix $u$.

Colour the suffixes by the vectorwhich has at most $k^m$ colours. By the dimension-$d-1$ induction hypothesis, there is a $(d-1)$-dimensional suffix combinatorial subspace on which this vector colouring is $(a,b)$-insensitive. Combining it with the variable block of $v$ gives dimension $d$. Switching the first parameter between $a,b$ preserves colour by the equal prefix profiles; switching any other parameter preserves every entry of $c^{\prime }$ by induction. This proves the alphabet insensitivity lemma, including $d=1$, where the suffix is empty.

Now induct on $m$ to prove the Hales-Jewett theorem. For $m=1$, any one-variable word gives a one-point monochromatic combinatorial line. Suppose the theorem holds for $m-1$, and let $d$ be a sufficient dimension for $k$ colours on $[m-1{]}^d$. The lemma supplies a $d$-dimensional combinatorial subspace insensitive to $(m-1,m)$. Restrict its parameter colouring to $[m-1{]}^d$. By the alphabet induction hypothesis it contains a monochromatic combinatorial line. Its $m$th point has the same colour as its $(m-1)$st point: switch the active parameter coordinates from $m-1$ to $m$, one at a time. Therefore the full line over $[m]$ is monochromatic. Its actual active coordinate set is the nonempty union of the active parameter blocks. This completes both inductions.

To deduce the Van der Waerden theorem, choose the dimension $n$ for alphabet size $m$ and pull back a colouring of a sufficiently long integer interval alongAll images lie in $[N]$ for $N=m{\sum }_{j=1}^n{m}^{j-1}$. A combinatorial line with active coordinates $D$ maps towhere $a$ is the contribution of the fixed coordinates. Thus every finite colouring of the positive integers contains monochromatic arithmetic progressions of every finite length. The argument also provides the finite-interval version. Length one is immediate.

The Strengthened Van der Waerden theorem requires the common difference itself to have the progression's colour. We prove a useful stronger, scaled version, the Brauer progression theorem: for every $k,t,\ell \ge 1$, a finite bound $B(k,t,\ell )$ guarantees a monochromatic setThe desired strengthening is $t=1$. For $\ell =1$ choose $a=t,d=1$; for one colour any interval covering the displayed configuration suffices. For the induction on $k$, assume $M=B(k-1,t,\ell )$ and $\ell \ge 2$. Put $L=(\ell -1)M+1$, let $W$ be a Van der Waerden theorem bound for $k$ colours and length $L$, and take $B(k,t,\ell )=tMW$. Inside $[W]$, obtain a one-colour progression $a+j\delta$ for $0\le j<L$, of colour $c$.

All numbers $tj\delta$, $1\le j\le M$, lie in the larger interval because $\delta \le W$. If one has colour $c$, then the subsequence $a,a+j\delta ,\dots ,a+(\ell -1)j\delta$, together with $tj\delta$, is the desired configuration with $d=j\delta$. Otherwise the colouring $j\mapsto c(t\delta j)$ of $[M]$ uses at most $k-1$ colours. Apply the induction hypothesis to obtain a one-colour configuration $\{te,b,b+e,\dots ,b+(\ell -1)e\}$ there. Multiplication by $t\delta$ gives common difference $d=t\delta e$ and distinguished point $td=t^2\delta e$, all of the same original colour. This proves the scaled theorem using only the Van der Waerden theorem.

The fixed-active-size strengthening is false. It already fails for $m=k=2$. For any proposed positive $n,d$, if $d>n$ there is no eligible line. Otherwise colour a word byThe two points of a line with exactly $d$ active coordinates have counts $q$ and $q+d$ of the letter $2$. Their quotient floors differ by exactly one, so their colours differ. This fixed-active-size obstruction for combinatorial lines is valid for every proposed $n,d$. The colouring may depend on $d$, since the assertion chooses $n,d$ before demanding the conclusion for every colouring.

The Strengthened Van der Waerden theorem says that every finite coloring contains, for each prescribed $m$, a monochromatic setWe prove the finite form by induction on the number $k$ of colors. The case $k=1$ is immediate. Let $n$ work for $m$ and $k-1$ colors, and apply the ordinary Van der Waerden theorem to obtain a monochromatic progressionIf one of $d,2d,\dots ,nd$ has the progression's color, say $rd$, thenworks. Otherwise $d,2d,\dots ,nd$ use at most $k-1$ colors. By the induction hypothesis their indices contain $b,b+r,\dots ,b+(m-1)r$ together with $r$ in one color. Multiplying by $d$ yieldswhich is the required progression together with its common difference.