TheoremProved

Szemerédi's theorem

Statement

Every subset $A \subseteq \mathbb{N}$ of positive upper density ( $\limsup_{N\to\infty} |A \cap [1,N]|/N > 0$ ) contains arbitrarily long arithmetic progressions: for every $k \ge 1$ and $\delta > 0$ , there exists $N(k,\delta)$ such that any subset of $\{1,\dots,N\}$ of size at least $\delta N$ with $N \ge N(k,\delta)$ contains a $k$ -term arithmetic progression.

Why is it true?

If a subset of the integers takes up a fixed positive fraction of all numbers, it cannot avoid evenly spaced patterns forever — no matter how you try to scatter the chosen numbers, any desired length of arithmetic progression must eventually appear. Density alone forces arithmetic structure.

Proof sketch

A set $A \subseteq [1,N]$ of density $\delta$ either behaves pseudorandomly — in which case it contains roughly the expected number $\delta^k N^2$ of $k$ -term progressions — or fails to be pseudorandom, which correlates $A$ with a structured configuration and allows passing to a subprogression on which $A$ has strictly larger density $\delta + c(\delta)$ . Since density cannot exceed 1, this density-increment iteration must terminate, and Szemerédi's regularity lemma (or, in later proofs, higher-order Fourier analysis, ergodic theory or hypergraph regularity) provides the decomposition into structured and pseudorandom pieces.

Proved by

proved 1975Endre Szemerédi

Topics that use this theorem

Szemerédi's theorem

Related theorems

Ramsey's theorem Green–Tao theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Endre Szemerédi (1975). On sets of integers containing no k elements in arithmetic progression