Van der Waerden's Theorem

Long colorings force monochromatic arithmetic progressions.

The idea

Theorem (Van der Waerden's theorem).

For every number of colors $r$ and every length $k$ there is a finite $N$ with this property: however $\{1, 2, \ldots, N\}$ is colored with $r$ colors, some color class contains $k$ evenly spaced numbers $a,\ a+d,\ \ldots,\ a+(k-1)d$ with common difference $d \ge 1$.

The smallest such $N$ is written $W(r, k)$. The theorem asserts that splitting cannot destroy this pattern. However the block is divided into $r$ classes — however unevenly, and however deliberately — at least one class contains an evenly spaced run of length $k$, provided the block is long enough. No class has to be large in any absolute sense; one of them simply has to contain a progression.

The theorem claims only finiteness. It gives no useful value for $W(r, k)$: only a handful of these numbers are known exactly, and the general upper bounds are enormous. The content is that past some threshold, evenly spaced structure is unavoidable.

It is the arithmetic counterpart of Ramsey's theorem, with a monochromatic progression in place of a monochromatic clique.

Ways to work on it

• Walkthrough. The statement, the pigeonhole toehold, and what the theorem promises.
• Practice. Read a small 2-coloring and count a color class.
• Hardest. Pin down an exact van der Waerden threshold.

Not sure where to start? Take the ten-question placement test.