Van der Waerden theorem

Every finite coloring of the positive integers contains monochromatic arithmetic progressions of every prescribed finite length.

For positive $r,k$, let $W(r,k)$ bound the interval needed to force a monochromatic length-$k$ arithmetic progression in every finite colouring using at most $r$ colours. The colour-focusing proof of Van der Waerden theorem inducts on $k$, simultaneously for every number of colours, and then creates progressions of distinct colours with a common next point.

Assume $W(r,k)$ exists for every $r$. For fixed $r$, construct $F_t$ such that a 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 of the form $f-h{d}_i$, $1\le h\le k$, with a common focus $f\in [F_t]$. Take $F_1=2W(r,k)$: a length-$k$ arithmetic progression in its first half has its next point inside the whole interval. For $k=1$, give a singleton step $1$.

Given $N=F_t$, put $M=W(r^N,k)$ and $F_{t+1}=2NM$. Regard the first $M$ length-$N$ blocks as coloured by their full colour profiles. Some block indices $j_0,j_0+D,\dots ,j_0+(k-1)D$ share a profile. If there is no monochromatic length-$(k+1)$ arithmetic progression, this profile supplies $t$ focused progressions with focus position $f$, steps $d_i$, and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$. In the later block $j_{\ast }=j_0+kD\le 2M$, put $F=N(j_{\ast }-1)+f$. For each $i$, the points $F-h(ND+d_i)$ have colour $q_i$: they lie in the selected block $j_{\ast }-hD$ at position $f-h{d}_i$. The points $F-hND$ have colour $q$. Thus $t+1$ distinct colours focus at $F$. For $t=r$, its own colour completes one of the $r$ focused progressions. The base case $W(r,1)=1$ completes the mathematical induction.

For positive integers $k,s,\ell$, some $N$ ensures that every $k$-color finite coloring of $[N]$ contains a monochromatic setIt follows from the Van der Waerden theorem by mathematical induction on the number of colors. If $M$ is a bound for $k-1$ colors, take a long one-color arithmetic progression of length $(\ell -1)M+1$ and step $d$. Either one of $sd,2sd,\dots ,Msd$ has its color, giving the result immediately, or these multiples use only $k-1$ colors. Pull back their finite coloring to $[M]$ and use mathematical induction, then multiply the resulting configuration by $sd$. Enlarge the ambient finite integer interval to include all these multiples. The cases $k=1$ and $\ell =1$ are immediate. The parameter $s$ makes this useful for positive monochromatic solutions of a partition regular equation with arbitrary integer coefficients.

For all positive integers $k,m$, some $n$ has the following property: every $k$-coloring of $[n]$ contains $a,d>0$ for whichis monochromatic. Thus the common difference has the same color as the progression.

Several monochromatic arithmetic progressions are color-focused when they have different colors and extend by one further term to the same point. Such focused families give an elementary induction proof of the length-three case of the Van der Waerden theorem.