Szemerédi's theorem

Every subset of the integers with positive upper density contains arithmetic progressions of every finite length. It establishes that sufficient largeness forces arbitrarily long additive patterns.

Density increment argument: A proof strategy that finds a denser structured region whenever a set lacks a desired pattern. Szemerédi's original proof repeatedly raises density on structured subsets until progression-free sets become impossible.
Upper density: The limit superior of the proportions of a set found in increasingly large intervals. The theorem's hypothesis measures largeness using upper density rather than requiring a natural density.
Endre Szemerédi: A Hungarian mathematician known for foundational work in combinatorics and number theory. He proved the theorem in 1975 using a combinatorial density-increment argument.
Green–Tao theorem: A theorem stating that the prime numbers contain arithmetic progressions of every finite length. It combines Szemerédi's dense-set principle with relative methods to handle primes.
Regularity lemma: A theorem that partitions a large graph into pieces whose pairwise connections are nearly uniform. Szemerédi's proof uses a regularity principle to extract organized structure from a dense set.
Arithmetic progression: A sequence of numbers in which consecutive terms differ by the same fixed amount. The guaranteed configurations are progressions of every finite length.
Klaus Roth: A German-born British mathematician whose work includes the first proof of the three-term case. His theorem established the first nontrivial case and influenced later density arguments.
Szemerédi's theorem for finite groups: Finite-group versions asserting long progressions or analogous configurations in sufficiently dense subsets. Finite settings provide a common framework for proofs, extensions, and quantitative bounds.
Gowers uniformity norms: A family of norms measuring higher-order additive structure in functions on finite groups. They quantify the structured patterns that generalized proofs must detect to find longer progressions.
Van der Waerden's theorem: A theorem stating that every finite coloring of the integers has monochromatic arithmetic progressions of any fixed length. It supplied an earlier combinatorial guarantee, while Szemerédi's theorem strengthens it through density.

Linked from 5 pages

Erdős–Szemerédi theoremRelated: Szemerédi's earlier work established the collaborator's role in the surrounding combinatorial landscape.