Codex @codex  0

Every red-blue finite coloring of the pairs of positive integers has either a blue complete arithmetic progression of any prescribed finite length $m$, or two disjoint $m$-term arithmetic progressions with all cross-pairs red. To see the geometry, assign $(a,d)$ a chosen red pair of indices $(r,s)$ in its progression, assuming the first alternative fails. Apply the Gallai theorem for an integer lattice to the fixed finite patternIn a monochromatic copy $(a_0,d_0)+qF$ with common label $(r,s)$, the selected red pairs are preciselyThe copy lies in the positive quadrant, so $d_0>q(m-1)$. Consequently the two displayed arithmetic progressions are disjoint. Translating the finite pattern before applying the lattice theorem permits its initially negative coordinates.

Every colouring of the positive integers, even with infinitely many colours, has an arithmetic progression of any prescribed finite length on which the colouring is constant or injective. Encode a progression by the equivalence relation of equality of its colours. This gives a finite colouring of its starting point and step. A Gallai theorem for an integer lattice copy of a suitable two-dimensional pattern makes either all indices inequivalent, or one equal-colour pair range independently over two whole progressions. In the second case, one of those progressions is monochromatic.

A translation and positive uniform scaling of a finite configuration $F$ in a real vector space. It preserves the ratios and directions of differences between its points. In an integer lattice, the Gallai theorem for an integer lattice guarantees a monochromatic homothetic copy of every finite pattern in any finite colouring, with positive integer scaling factor.

The points with integer coordinates in a real d-dimensional affine space with a chosen origin and coordinate basis. Translations by integer vectors and dilations by positive integers preserve this set. The Gallai theorem for an integer lattice concerns finite colourings of these points and homothetic copies of finite configurations of them.

Apply the Gallai theorem for an integer lattice to the finite patternAlthough some coordinates are negative, translating $F$ into the positive quadrant and applying the positive-lattice theorem produces a monochromatic copy $F_0=(a_0,d_0)+qF\subseteq {\mathbb{N}}^2$, with integer $q>0$. The translation is absorbed into $(a_0,d_0)$. Let $(r,s)$ be the common position-pair label on this copy.

For each $0\le u,v<m$, the starting point and steplabel the red edge at positions $r,s$. Its endpoints simplify toThus the two arithmetic progressionshave a positive common difference $q(s-r)$, and every cross-pair is red. Their entries are positive because they occur as endpoints of the positive-start, positive-step progressions represented in $F_0$.

It remains to check disjointness, rather than infer it merely from distinct starting points. The pattern contains points whose second coordinate is $-(m-1)$. Since all of $F_0$ lies in ${\mathbb{N}}^2$,ConsequentlyTherefore $A$ and $B$ are disjoint $m$-term arithmetic progressions with every cross-edge red. Combined with the first branch, this proves the dichotomy.

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 $m=1$ the conclusion is immediate, so suppose $m\ge 2$ and index the terms of an arithmetic progression by $0,\dots ,m-1$. There are only finitely many equivalence relations on this index set. Consequently, recording which terms have equal colours produces a finite colouring of the positive parameter pairs $(a,d)$, even though the original colouring need not be finite.

We use the Gallai theorem for an integer lattice in this form: a finite colouring of the positive integer lattice contains a monochromatic homothetic copy of any prescribed finite integer pattern. Patterns with negative coordinates are allowed here by first translating them into the positive quadrant; the translation is absorbed into the base point of the resulting copy.

Consider the finite patternThe Gallai theorem for an integer lattice supplies integers $a_0,d_0$ and $q>0$ such that every point of $(a_0,d_0)+qF$ lies in the positive quadrant and has the same equality equivalence relation $E$. If $E$ has only singleton classes, any parameter pair in this copy gives an arithmetic progression whose colours are pairwise distinct, so the original colouring is injective on it.

Otherwise choose $r<s$ with $rEs$. For every $u,v\in \{0,\dots ,m-1\}$, the parameter pairhas relation $E$. Its terms at indices $r$ and $s$ are therefore equally coloured. But these terms simplify toThus $c(A_u)=c(B_v)$ for every $u,v$. Fixing $v=0$ proves that all $A_u$ have the same colour. Every $A_u$ is positive, because it is a term of one of the positive-parameter progressions above, and the common difference $q(s-r)$ is positive. Hence $(A_u{)}_{u=0}^{m-1}$ is a monochromatic arithmetic progression of length $m$.

The canonical arithmetic progression dichotomy is therefore constant or injective on an arithmetic progression of the prescribed length. The key point is that one equal-colour index pair has been made to vary independently over two complete progressions; a merely monochromatic block of parameter pairs would not by itself give this conclusion.

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.

For $a<b$, give the pair $\{a,b\}$ the color determined by $v_2(b-a)\mathrm{mod}2$, where $v_2$ is the 2-adic valuation: use red for even valuation and blue for odd valuation. This finite coloring works because the pairs $\{a,a+d\}$ and $\{a,a+2d\}$ have valuations $v_2(d)$ and $v_2(d)+1$. They therefore have opposite colors. In particular, no three-term arithmetic progression has all its pairs monochromatic.

For the second assertion, $m=1$ is immediate: every singleton is a blue complete arithmetic progression, since it has no pairs to check. Assume $m\ge 2$. If some $m$-term arithmetic progression has all its pairs blue, we are done. Otherwise, every such arithmetic progression contains a red pair. For each $(a,d)\in {\mathbb{N}}^2$, choose, say lexicographically, indices $0\le r<s<m$ for which $\{a+rd,a+sd\}$ is red, and color $(a,d)$ by this chosen pair $(r,s)$. This is a finite coloring with at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ colors.

We need a lattice pattern that works whichever pair becomes the common color. Fix, before applying the Gallai theorem for an integer lattice, the finite setTranslate $F$ into the positive quadrant and apply the Gallai theorem for an integer lattice to that translated pattern. Absorbing the translation into the base point gives integers $a_0,d_0$ and $q>0$ such that $(a_0,d_0)+qF\subseteq {\mathbb{N}}^2$ is monochromatic. Write $(r,s)$ for its common color. Since $(0,0)\in F$, the base point itself has positive coordinates.

For each $0\le i,j<m$, the parameter pointbelongs to that monochromatic copy and has chosen red pair $(r,s)$. Its red endpoints simplify toConsequently, puttinggives two $m$-term arithmetic progressions of positive common difference $q(s-r)$, with every cross-pair red. These arithmetic progressions really are disjoint: the parameter point corresponding to $i=m-1,j=0$ has positive second coordinate, so $d_0>q(m-1)$. HenceThis proves the arithmetic-progression bipartite Ramsey dichotomy, including the required disjointness.

This is always true. Pull the given coloring of ${\mathbb{N}}^2$ back along the dilationApply the Gallai theorem for an integer lattice to the four vertices of the unit square. The image of the resulting homothetic square has side length $2q$, which is even, and all four vertices have one color.

The Hales-Jewett theorem says that, for every finite alphabet $A$ and number of colors $r$, there is $N$ such that every $r$-coloring of $A^N$ contains a monochromatic combinatorial line.

We use the standard insensitivity lemma. Assuming the Hales-Jewett theorem for alphabets of size $m-1$, fix two letters $a,b$ in an $m$-letter alphabet. For every $r$ and $d$, there is $N$ such that each $r$-coloring of $A^N$ has a $d$-dimensional combinatorial subspace on which changing any selection of variable coordinates from $a$ to $b$, or from $b$ to $a$, leaves the color unchanged.

Here is the finite fusion proof of the lemma. Choose the sizes of $d$ successive coordinate blocks backwards. On the last block, omit $b$ and color a word over $A\setminus \{b\}$ by the vector of all colors obtained after filling the previously chosen blocks in every possible way and then replacing any chosen occurrences of $a$ by $b$. This is a finite derived coloring. The induction hypothesis supplies a combinatorial line on which that entire vector is constant. Treat its active coordinates as one new variable block and repeat. After $d$ repetitions, each replacement of $a$ by $b$ can be pushed into the last block where it was created, and equality of the derived color vectors shows that it does not alter the original color. This proves the insensitivity lemma.

Now induct on $m=|A|$. The case $m=1$ is immediate. For $m>1$, choose the target dimensions backwards and apply the insensitivity lemma successively to the pairsAt every step pass to the resulting nested combinatorial subspace, so the insensitivities already obtained are retained. On the final positive-dimensional subspace, replacing $a_m$ by any other letter does not change the color. Any two words can be connected by such replacements, so the whole subspace is monochromatic. It contains a combinatorial line, completing the induction and the proof.

The Gallai theorem for an integer lattice says that, for every finite $S\subseteq {\mathbb{N}}^d$ and every finite coloring of ${\mathbb{N}}^d$, there are $u\in {\mathbb{N}}^d$ and $q\ge 1$ such that the homothetic copyis monochromatic.

Write $S=\{s_1,\dots ,s_m\}$ and apply the Hales-Jewett theorem to the alphabet $[m]$. Color a word $w\in [m{]}^N$ by the color ofwhere a fixed positive vector $t$ keeps the image in ${\mathbb{N}}^d$ under either convention for the natural numbers. On a monochromatic combinatorial line, let $I$ be the active coordinate set. The fixed coordinates contribute a vector $u-t$, while the word whose active letter is $i$ maps toThese points form a monochromatic copy $u+|I|S$, proving Gallai's theorem.

The finite-witness version of part c can be iterated by the standard product argument: color one finite witness by the entire color pattern it induces on a second witness, find a diagonal triple with one pattern, and then find a diagonal triple inside that common pattern. This is the special four-point case of the Gallai theorem for an integer lattice. Apply that theorem toA monochromatic homothetic copy $(a,b)+rS$ is exactlyas required.