Codex @codex  0

Colour each interval $[2^j,2^{j+1})\cap \mathbb{N}$ by the parity of $j$. Every infinite arithmetic progression of positive common difference d meets every sufficiently large such interval, since the interval has length greater than d. Both colours occur infinitely often. Thus neither colour class contains an infinite arithmetic progression, despite the finite-length conclusion of the Van der Waerden theorem.

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.

Van der Waerden theorem. Given positive integers $r,k$, there is a finite $W(r,k)$ such that every finite colouring of $\{1,\dots ,W(r,k)\}$ with at most $r$ colours has a monochromatic arithmetic progression of length $k$ and positive common difference. In particular, every finite colouring of the positive integers contains such progressions of every finite length.

Here is a colour-focusing proof of Van der Waerden theorem. We induct on $k$, simultaneously for all numbers of colours. The assertion for $k=1$ is immediate. Suppose $W(r,k)$ exists for every $r$, and fix $r$. We construct bounds $F_t$, for $1\le t\le r$, with this property: every colouring of $[F_t]$ either has a monochromatic progression of length $k+1$, or has $t$ progressions of length $k$, of distinct colours, which share a next point $f\in [F_t]$. Write those progressions aswith positive steps $d_i$ and all displayed points in $[F_t]$.

For $t=1$, put $L=W(r,k)$ and $F_1=2L$. A monochromatic progression of length $k$ in $[L]$ has its next point in $[2L]$, since its step is at most $L$; for $k=1$ choose step $1$. This establishes the initial focusing property.

Suppose $F_t=N$ has been constructed. Put $M=W(r^N,k)$ and $F_{t+1}=2NM$. Divide the first $NM$ integers into $M$ consecutive blocks of size $N$. Colour a block by its full colour profile, an $N$-tuple having at most $r^N$ possible values. The induction hypothesis on $k$ gives block indiceswith the same colour profile. For $k=1$ use any one block and $D=1$. Suppose that the whole interval has no monochromatic progression of length $k+1$. Its repeated profile has $t$ focused length-$k$ progressions with positions $f-h{d}_i$ and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$, since equality would complete a length-$(k+1)$ progression in the block.

Set $j_{\ast }=j_0+kD$ and $F=N(j_{\ast }-1)+f$. The index $j_{\ast }$ is at most $2M$, so this focus is in the full interval. For $1\le h\le k$, the pointis in one of the chosen blocks and has colour $q_i$. Also $F-hND$ is at position $f$ in that block and has colour $q$. We have produced $t+1$ focused length-$k$ progressions of distinct colours. This proves the recursive focusing property. At $t=r$, the focus itself must have one of the $r$ colours, so one of the progressions extends to length $k+1$. Thus $W(r,k+1)=F_r$ is a valid bound, completing the mathematical induction and the requested proof.

To obtain the equation criterion, we first prove the small strengthening of Van der Waerden theorem that we need. For any positive integers $r,s,L$, there is a finite bound forcing a monochromatic configurationThis is the Brauer progression theorem, and the following argument proves it from the theorem just established. Induct on $r$. One colour is immediate. Given a bound $M$ for $r-1$ colours with the same $s,L$, let $T=W(r,(L-1)M+1)$ and colour an interval at least as long as $\max (T,sMT)$. Find a monochromatic progression $a,a+d,\dots ,a+(L-1)Md$ in $[T]$, of colour $q$; take $d=1$ if this progression has one term. If some $jsd$, $1\le j\le M$, has colour $q$, its first $L$ suitably spaced terms $a,a+jd,\dots ,a+(L-1)jd$ and the point $s(jd)$ give the configuration. Otherwise the colouring of the indices $1,\dots ,M$ obtained from $j\mapsto c(jsd)$ uses at most $r-1$ colours. The induction hypothesis supplies indices $se,b,b+e,\dots ,b+(L-1)e$ of one colour. Multiplication by $sd$ gives the desired configuration with step $esd$. This completes the strengthening without assuming any Rado theorem.

Multiply the rational coefficients by a common positive denominator, so that all $a_i$ are nonzero integers; this does not alter the equation or partition regularity. By definition, the row is partition regular when every finite colouring admits positive monochromatic $x_1,\dots ,x_n$ satisfying ${\sum }_i{a}_i{x}_i=0$. The variables need not be distinct.

For necessity, choose a prime number $p>{\sum }_i|a_i|$. Write each positive $x$ uniquely as $p^{v_p(x)}u$, with $p\nmid u$, and colour $x$ by $u\mathrm{mod}p$. This is a finite colouring with $p-1$ colours. If a monochromatic solution exists, let $v={\min }_i{v}_p(x_i)$ and $I=\{i:v_p(x_i)=v\}$. Dividing the equation by $p^v$ and reducing modulo $p$ giveswhere $u_0\ne 0(\mathrm{mod}p)$ is the common colour. Thus ${\sum }_{i\in I}{a}_i\equiv 0(\mathrm{mod}p)$. Its absolute value is strictly less than $p$, so ${\sum }_{i\in I}{a}_i=0$. The index set $I$ is nonempty. This proves the leading-residue obstruction to partition regularity.

Conversely, suppose ${\sum }_{i\in I}{a}_i=0$ for a nonempty $I$. If $I$ is all indices, taking every variable equal to any one positive integer already gives a monochromatic solution. Otherwise fix $i_0\in I$, put $s=|a_{i_0}|$, $C={\sum }_{j\notin I}{a}_j$, and define integer offsetsLet $u={\min }_{i\in I}{\lambda }_i$ and choose $L=1+{\max }_{i\in I}{\lambda }_i-u$. The proved Brauer progression theorem gives a monochromatic configuration consisting of $sd$ and a length-$L$ progression starting at $b$. SetAll variables are positive and of one colour. Their weighted sum isThis explicitly gives a Brauer configuration for a one-row zero-sum equation. We concludeBoth directions have been proved independently of the general Rado theorem.

We take $\mathbb{N}=\{1,2,\dots \}$ and require the common difference of an arithmetic progression to be positive. An ultrafilter $\mathcal{U}$ is a proper filter on a set deciding each subset: exactly one of $B$ and $\mathbb{N}\setminus B$ belongs to $\mathcal{U}$.

For the fixed length $m$, let ${\mathcal{B}}_m$ be the family of sets containing no m-term arithmetic progression. Any acceptable ultrafilter must contain every complement $\mathbb{N}\setminus B$ with $B\in {\mathcal{B}}_m$. These mandatory sets have the finite intersection property. Otherwise finitely many $B_1,\dots ,B_r\in {\mathcal{B}}_m$ would cover $\mathbb{N}$. Colour an integer by the first $i$ for which it belongs to $B_i$. The Van der Waerden theorem gives a monochromatic m-term arithmetic progression, contained in the corresponding $B_i$, a contradiction.

Generate a proper filter from those complements and extend it by the ultrafilter lemma. If some $B\in \mathcal{U}$ were in ${\mathcal{B}}_m$, its complement would also belong to $\mathcal{U}$, forcing the empty set into the filter. ThusNotice that sets avoiding one fixed length need not be closed under finite unions; the argument uses the finite intersection property, not an unsupported ideal claim.

For the unbounded-length version, let $\mathcal{B}$ consist of sets whose arithmetic progression lengths are bounded. Each $B_i\in \mathcal{B}$ fails to contain a progression of some length $m_i$, and hence of every greater length. If finitely many $B_i$ covered $\mathbb{N}$, colour by the first containing index and apply the Van der Waerden theorem at length $M={\max }_i{m}_i$. Again a contradiction results. The complements of all members of $\mathcal{B}$ therefore have the finite intersection property. Extending their generated filter gives an ultrafilter with arithmetic-progression-rich members:All finite sets lie in $\mathcal{B}$, so this ultrafilter contains every cofinite set and is a nonprincipal ultrafilter. The same is true of the fixed-length construction when $m\ge 2$, because no singleton is allowed; for $m=1$ a principal ultrafilter also works. These constructions illustrate ultrafilter selection from a partition-rich family.

The infinite-length answer is no. Colour $n$ by $\lfloor {\log }_{2}n\rfloor \mathrm{mod}2$, so successive intervals $[2^j,2^{j+1})$ alternate colours. An infinite arithmetic progression $a+td$, $t\ge 0$, meets every sufficiently large such interval: its first term at least $2^j$ is less than $2^j+d$, which is at most $2^{j+1}$ once $2^j\ge d$. It therefore has terms of both colours. Neither colour class contains an infinite arithmetic progression, but every ultrafilter contains one of the two colour classes. This dyadic block obstruction to infinite arithmetic progressions rules out the proposed ultrafilter.

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.

Van der Waerden theorem says that for every pair of positive integers $r,k$ there is $W(r,k)$ such that every finite colouring of $[W(r,k)]=\{1,\dots ,W(r,k)\}$ using at most $r$ colours contains a monochromatic arithmetic progression of length $k$ and positive common difference. Consequently every finite colouring of $\mathbb{N}$ contains arbitrarily long monochromatic arithmetic progressions.

Here is a colour-focusing proof of Van der Waerden theorem. Induct on $k$, simultaneously for all $r$. For $k=1$, take $W(r,1)=1$. Suppose $W(R,k)$ exists for every number of colours $R$, and fix $r$. We will construct finite bounds $F_t$, $1\le t\le r$, with the following property: every finite colouring of $[F_t]$ using at most $r$ colours contains either a monochromatic length-$(k+1)$ arithmetic progression, or $t$ length-$k$ arithmetic progressions of pairwise distinct colours, all focused at the same point $f\in [F_t]$. Specifically, their terms are“Focused” means that adjoining $f$ completes the corresponding length-$(k+1)$ arithmetic progression if $f$ has its colour.

For $t=1$, put $F_1=2W(r,k)$. Find a monochromatic length-$k$ arithmetic progression in the first $W(r,k)$ points. Its next point is at most $2W(r,k)$ and supplies the focus. For $k=1$, give the selected singleton common difference $1$.

Suppose $F_t=N$ has been constructed. SetDivide $[2NM]$ into $2M$ consecutive blocks of length $N$. Colour the first $M$ block indices by their full colour profiles, that is, the ordered list of their $N$ colours. There are at most $r^N$ profiles, so the induction hypothesis on $k$ gives equally profiled blocks with indicesWhen $k=1$, choose $D=1$. Otherwise $D>0$ and $j_0+kD\le 2M$, since the last selected block is at most $M$ and $D\le M$.

Assume the original finite colouring contains no monochromatic length-$(k+1)$ arithmetic progression. Applying the property of $F_t$ to the common profile gives $t$ focused length-$k$ arithmetic progressions at a position $f$, with common differences $d_i$ and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$: otherwise the profile already contains a length-$(k+1)$ monochromatic arithmetic progression, and so does any selected block.

Put $j_{\ast }=j_0+kD$ and $F=N(j_{\ast }-1)+f$, a point in the original interval. For $1\le h\le k$, the pointlies in a selected block at profile position $f-h{d}_i$, so has colour $q_i$. Similarly $F-hND$ has colour $q$. Thus $t+1$ length-$k$ arithmetic progressions of distinct colours focus at $F$. This proves the step in $t$. At $t=r$, the focus necessarily has the colour of one of the $r$ progressions, giving a monochromatic length-$(k+1)$ arithmetic progression. Hence $W(r,k+1)$ exists, completing the mathematical induction and the proof of Van der Waerden theorem.

For the partition regularity deduction we first prove a strengthened progression lemma, the Brauer progression theorem: for positive $r,s,L$ with $L\ge 2$, there is $B(r,s,L)$ such that every finite colouring of $[B(r,s,L)]$ using at most $r$ colours contains a monochromatic setInduct on $r$. For $r=1$, take $B(1,s,L)=\max (s,L)$ and $a=d=1$. Given the result for $r-1$, putVan der Waerden theorem supplies a colour-$q$ arithmetic progression $a+j{d}_0$, $0\le j<K$, inside $[W]$. If some $sj{d}_0$, $1\le j\le N$, also has colour $q$, take $d=j{d}_0$ and use the $L$ terms $a,a+j{d}_0,\dots ,a+(L-1)j{d}_0$. They are in the progression because $(L-1)j\le K-1$.

Otherwise the integers $sj{d}_0$, $1\le j\le N$, use at most $r-1$ colours. Colour $j\in [N]$ by the colour of $sj{d}_0$ and apply the induction hypothesis. It supplies a monochromatic set $\{se,b,b+e,\dots ,b+(L-1)e\}$. Multiplying by $s{d}_0$ gives the required configuration with $a=s{d}_{0}b$ and $d=s{d}_{0}e$: its distinguished member is $s^2{d}_{0}e=sd$. All of these points are at most $sN{d}_0\le sNW$, so the finite bound is valid. This proves the Brauer progression theorem using only the just-proved Van der Waerden theorem.

A row is a partition regular matrix over the positive integers if every finite colouring of $\mathbb{N}$ admits a positive vector $x$ whose coordinates have one colour and whose product with the row is zero. Coordinates may repeat. Since the coefficients are rational numbers, multiplying them by a common positive denominator leaves the equation and every zero subset sum unchanged, so write the row as nonzero integer coefficients $b_1,\dots ,b_n$.

To prove necessity, suppose no nonempty subset of the $b_i$ sums to zero. Choose a prime $p>{\sum }_i|b_i|$ and use the last nonzero digit coloringwhere $v_p$ is the P-adic valuation. If positive $x_i$ all had the same colour $u$ and satisfied ${\sum }_i{b}_i{x}_i=0$, let $m={\min }_i{v}_p(x_i)$ and $I=\{i:v_p(x_i)=m\}$. After division by $p^m$ and reduction modulo $p$, the equation becomesAs $u\ne 0$, this says $p\mid {\sum }_{i\in I}{b}_i$. The latter sum is nonzero and has absolute value at most ${\sum }_i|b_i|<p$, a contradiction. This explicitly proves the necessary obstruction without invoking a general partition regularity criterion.

Conversely, suppose $\varnothing \ne I\subseteq \{1,\dots ,n\}$ and ${\sum }_{i\in I}{b}_i=0$. Select an index $j\in I$, and putFor any finite colouring, the Brauer progression theorem gives one-coloured $\{sd,a,a+d,\dots ,a+(L-1)d\}$. The indices $u$ and $u+q$ both lie between $0$ and $L-1$. Define positive, same-coloured coordinates byThenThis also covers $I$ equal to the whole index set and $q=0$. Reversing the clearing of denominators proves the exact criterion:

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.

The Szemerédi theorem says that for every integer $k\ge 2$ and every $\delta >0$, there is $N_0(k,\delta )$ such that, for $N\ge N_0$, every $A\subseteq \{1,\dots ,N\}$ with $|A|\ge \delta N$ contains a nonconstant arithmetic progressionEquivalently, every subset of the positive integers with positive upper asymptotic density contains arithmetic progressions of every finite length. Length one is immediate.

The Furstenberg multiple recurrence theorem states that for every probability measure-preserving system, every measurable $B$ with $\mu (B)>0$, and every integer $k\ge 2$, there is $n\ge 1$ withHere $T^{-jn}B$ means a preimage, so invertibility is unnecessary. The Furstenberg multiple recurrence theorem also does not assume an ergodic transformation.

We prove the implication to the finite Szemerédi theorem by constructing the Furstenberg correspondence principle explicitly. Suppose, to the contrary, that for fixed $k$ and $\delta >0$ there are $N_{\ell }\to \infty$ and $A_{\ell }\subseteq \{1,\dots ,N_{\ell }\}$ with $|A_{\ell }|\ge \delta N_{\ell }$, but with no length-$k$ arithmetic progression of positive common difference. In the binary full shift $\Omega =\{0,1{\}}^{\mathbb{Z}}$, encode $A_{\ell }$ as $x_j^{(\ell )}=1_{A_{\ell }}(j)$, taking all coordinates outside $A_{\ell }$ to be zero. Let $S$ be the left shift, $(S\omega {)}_j={\omega }_{j+1}$, and setThe cylinder set $C$ is a clopen set, and ${\nu }_{\ell }(C)=|A_{\ell }|/N_{\ell }\ge \delta$. The binary full shift is a compact metric space, so compactness of probability measures on a compact metric space gives a subsequence of these empirical measures with weak convergence of probability measures to a Borel probability measure $\nu$.

For every continuous $h$ on the full shift,Passing to the weak limit shows that $\nu$ is an invariant measure for the continuous left shift. Thus $(\Omega ,\mathcal{B},\nu ,S)$ is a probability measure-preserving system. Since the indicator function of $C$ is continuous, $\nu (C)\ge \delta$.

Apply the Furstenberg multiple recurrence theorem to $C$. For some $n\ge 1$, the clopen sethas $\nu (D)>0$. Its continuous indicator function gives ${\nu }_{\ell }(D)\to \nu (D)>0$. For large $\ell$, at least one $S^a{x}^{(\ell )}$ in the defining empirical measure therefore belongs to $D$. The choice of left shift impliesso $a,a+n,\dots ,a+(k-1)n$ lies in $A_{\ell }$. This contradicts the assumed absence of arithmetic progressions and proves the finite Szemerédi theorem. Applying the finite Szemerédi theorem on intervals where an infinite set has density bounded below proves the stated upper asymptotic density formulation.

For multiple recurrence for circle rotations, write $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ and $R_{\alpha }x=x+\alpha$, with normalized Lebesgue measure $m$, which is the Haar measure of the circle group. Fix a measurable $B\subseteq \mathbb{T}$ with $m(B)>0$ and $k\ge 2$. If $\alpha$ is rational, there is $q\ge 1$ with $R_{\alpha }^q$ the identity, and $n=q$ gives an intersection of measure $m(B)$.

For irrational $\alpha$, the pigeonhole principle applied to $0,\alpha ,\dots ,Q\alpha$ in $Q$ equal arcs gives $1\le n\le Q$ with $\Vert n\alpha {\Vert }_{\mathbb{T}}\le 1/Q$. In particular there are arbitrarily small nonzero returns to zero for the irrational rotation of the circle.

We also need translation continuity in L1 on the circle. Given a measurable $B$, approximate its indicator function in the L1 norm by a continuous $g$ on the circle group. Such approximation follows from regularity of Lebesgue measure, or approximation by finite unions of intervals. Translation invariance and uniform continuity givewhere the approximation error is first made arbitrarily small. Equivalently, $m(B△(B-t))\to 0$.

Choose a return time $n\ge 1$ so small modulo one that for each $1\le j<k$,This is possible because multiplication by each fixed $j$ is continuous on the circle group and translation continuity in L1 on the circle applies to the finitely many translates. The union bound now givesThis proves the Furstenberg multiple recurrence theorem for every circle rotation with its normalized Lebesgue measure, including both rational and irrational angles.

Let the required arithmetic progression have length $m\ge 2$, let $k$ be the number of colors, and take $n=n(m,k)$ from the Hales-Jewett theorem. Given any finite coloring $\chi$ of $[mn]$, color a word over an alphabet $w\in [m{]}^n$ by $\chi (w_1+\cdots +w_n)$. For a monochromatic combinatorial line, let $A\ne \varnothing$ be its active coordinate set and let $C$ be the sum of its fixed coordinates. The sums of its $m$ words areThey all lie in $[mn]$, have one color, and form an arithmetic progression with strictly positive common difference $|A|$. Thus, writing $W(k,m)$ for the finite Van der Waerden theorem bound,The length-one case is immediate. Restricting a finite coloring of the positive integers to this finite integer interval gives the infinite-domain formulation of the Van der Waerden theorem as well.

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\ge 2$, 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 byProcess 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.