Szemerédi's theorem

Remarks

An equivalent finite form reads as follows. For every $k \ge 1$ and $\delta > 0$ there is $N_0$ such that the following holds for all $N \ge N_0$. Each subset of $\set{1, \dots, N}$ with at least $\delta N$ elements contains an arithmetic progression of length $k$. Szemerédi's original proof is combinatorial and introduced the Szemerédi regularity lemma. Other proofs use ergodic theory (Furstenberg's multiple recurrence theorem), higher-order Fourier analysis with Gowers norms, and hypergraph regularity. The case $k = 3$ is Roth's theorem on arithmetic progressions. The density hypothesis cannot simply be dropped: the infinite set of powers of $2$ has density zero and contains no three-term arithmetic progression. The primes also have density zero, so the theorem does not apply to them directly; the Green–Tao theorem handles them separately.

Going deeper

For a student

Szemerédi's theorem is the density version of van der Waerden's theorem: in a finite colouring one colour class has positive upper density, so it contains long progressions. It is a central theorem of additive combinatorics, and the search for good quantitative bounds led to Gowers norms and much of the modern theory. The ergodic proof opened the field of ergodic Ramsey theory, with polynomial and multidimensional extensions.