Szemerédi's theorem

Szemerédi's theorem Any subset of the integers of positive upper density contains arbitrarily long arithmetic progressions.

Finite version. For every [math]\displaystyle{ \delta\gt 0 }[/math] and every positive integer k there exists n such that every subset [math]\displaystyle{ A\subset [n] }[/math] of size at least [math]\displaystyle{ \delta n }[/math] contains an arithmetic progression of length k.

It is known that for fixed [math]\displaystyle{ \delta }[/math] and n sufficiently large one can take k to be [math]\displaystyle{ \log\log\log\log\log\log n. }[/math] (This is not quite the best known bound but is easier to state.)

This implies Roth's theorem. The result was first proven by Szemerédi in 1975.

See also the Wikipedia entry for this theorem, or the Scholarpedia entry.