Szemerédi's Theorem

Szemerédi's theorem states that every sequence of integers that has positive upper Banach density contains arbitrarily long arithmetic progressions. The theorem resolves problem 139 in the Erdős problems collection (Bloom 2026).

A corollary states that, for any positive integer and positive real number , there exists a threshold number such that for every subset of with cardinal number larger than contains a -term arithmetic progression. van der Waerden's theorem follows immediately by setting . The best bounds for van der Waerden numbers are derived from bounds for in Szemerédi's theorem.

Szemerédi's theorem was conjectured by Erdős and Turán (1936). Roth (1953) proved the case , and was mentioned in his Fields Medal citation. Szemerédi (1969) proved the case , and the general theorem in 1975 as a consequence of Szemerédi's regularity lemma (Szemerédi 1975a), for which he collected a $1000 prize from Erdos. Fürstenberg and Katznelson (1979) proved Szemerédi's theorem using ergodic theory. Gowers (1998ab) subsequently gave a new proof, with a better bound on , for the case (mentioned in his Fields Medal citation; Lepowsky et al. 1999).