= Colour-focusing proof of Van der Waerden theorem
= Color-focusing proof of Van der Waerden theorem
{synonym}
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-hd_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,\ldots,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_*=j_0+kD\le2M$, put $F=N(j_*-1)+f$. For each $i$, the points $F-h(ND+d_i)$ have colour $q_i$: they lie in the selected block $j_*-hD$ at position $f-hd_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>.
Back to article page
