van der Waerden's theorem

Remarks

The least such $N$ is the van der Waerden number $W(r, k)$. For example $W(2, 3) = 9$: the colouring $1, 2, 5, 6$ red and $3, 4, 7, 8$ blue of $\set{1, \ldots, 8}$ has no monochromatic three-term progression, while every $2$-colouring of $\set{1, \ldots, 9}$ has one. The classical proof is a double induction with "colour focusing" and gives bounds that grow like the Ackermann function. The theorem also follows from the Hales–Jewett theorem: a combinatorial line in $\set{0, \ldots, k-1}^n$ is sent to an arithmetic progression by the map $w \mapsto w_1 + \cdots + w_n$. Shelah gave primitive recursive bounds, and Gowers gave the bound $W(r, k) \le 2^{2^{r^{2^{2^{k + 9}}}}}$ through his proof of Szemerédi's theorem.

Going deeper

For a student

Van der Waerden's theorem is a cornerstone of Ramsey theory in the integers. Its density form is Szemerédi's theorem: a set of integers of positive upper density contains arbitrarily long progressions. The colour classes of a colouring cannot all have density zero, so the density form implies the colouring form. The Green–Tao theorem gives progressions in the primes, which have density zero. Exact values of $W(r, k)$ are known only for a few small cases.