Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 14 / 2

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: