Combinatorics and discrete mathematics

Szemerédi's theorem

Any set of integers with positive density contains arbitrarily long arithmetic progressions.

IntuitionIntuition: arithmetic progressions hiding inside crowded sets

Pick any set of positive integers that is not too sparse — say it keeps a fixed fraction of all numbers up to every scale. Intuition suggests such a set cannot avoid all patterns forever: sooner or later it must contain three numbers spaced evenly apart, then four, then any number you like. Szemerédi's theorem makes this precise: it says that mere abundance — a positive fraction of the integers, with no algebraic structure assumed at all — already forces the set to contain arithmetic progressions of every finite length.

Szemerédi's regularity lemma: any large graph splits into a bounded number of parts so that almost every pair of parts looks pseudorandom

UndergraduateDensity and the precise statement

Definition: Upper density

For a set of positive integers $A$ , the upper density $d(A)$ measures the largest fraction of $\{1,\dots,N\}$ that $A$ can occupy, in the limit as $N$ grows without bound: $d(A) = \limsup_{N \to \infty} \frac{|A \cap [1,N]|}{N}$ .

d(A) = \limsup_{N \to \infty} \frac{|A \cap [1,N]|}{N}

Here $A \cap [1,N]$ is the part of $A$ inside the first $N$ integers, and $\limsup$ takes the largest value the ratio keeps returning to as $N$ grows — this way $d(A)$ is well defined even if the fraction oscillates instead of converging.

d(A) > 0 \implies \forall\, k \ge 1,\ \exists\, a, r > 0 : \{a, a+r, \dots, a+(k-1)r\} \subseteq A

This is the full statement: as soon as $d(A) > 0$ , the set contains an arithmetic progression $\{a, a+r, \dots, a+(k-1)r\}$ for every length $k$ — no matter how large $k$ is. Setting $k=3$ already recovers the hardest classical special case, Roth's theorem; letting $k$ grow gives progressions as long as anyone could ask for, all from the single hypothesis of positive density.

Comparing three theorems about arithmetic progressions
Theorem	Hypothesis on the set	Conclusion
Van der Waerden (1927)	Finite coloring of $\mathbb{Z}^+$	Some color class contains a length- $k$ progression for every $k$
Szemerédi (1975)	$d(A) > 0$	$A$ contains a length- $k$ progression for every $k$
Green–Tao (2004)	$A$ = the primes (density 0)	$A$ contains a length- $k$ progression for every $k$

AdvancedProof idea: the regularity method

Theorem: Szemerédi's theorem (finitary form)

For every integer $k \ge 3$ and every $\delta > 0$ , there is a threshold $N(k,\delta)$ such that every $A \subseteq \{1,\dots,N\}$ with $N \ge N(k,\delta)$ and $|A| \ge \delta N$ contains an arithmetic progression of length $k$ .

Why is it true?

This finite version is logically equivalent to the infinite density statement by a simple compactness argument, and it is the form that is actually proved: instead of one infinite set, one only needs to control finitely many configurations inside a large but finite window.

Proof

Step 1 (reduction to the finite window). Suppose the infinite statement fails for some $d(A_0) > 0$ with no length- $k$ progression at all. Then for every $N$ , the restriction $A_0 \cap [1,N]$ is a length- $k$ -AP-free subset of $\{1,\dots,N\}$ whose size grows like $\delta$ $N$ for a fixed $\delta$ > 0. If the finitary statement were true, no such family could exist for arbitrarily large $N$ , a contradiction — so the two statements stand or fall together.

Step 2 (regularity partition). View potential $k$ -term progressions in $\{1,\dots,N\}$ as edges of a $(k-1)$ -uniform hypergraph. The hypergraph regularity lemma partitions the underlying vertex set into a bounded number of pieces so that, apart from a small exceptional fraction, every tuple of pieces is pseudorandom: the density of hyperedges between them is essentially constant, with no denser or sparser sub-clusters.

Step 3 (counting lemma). Once the partition is regular, a matching counting lemma shows that any tuple of pieces with positive relative density must contain the expected number of complete configurations — in particular, at least one genuine length- $k$ progression, because a regular pseudorandom structure with positive density cannot avoid the pattern it is being tested against.

Step 4 (removal argument). If $A$ had no length- $k$ progression at all, the counting lemma would force almost all of the configurations counted by the regular partition to be degenerate, which in turn would let one delete a vanishingly small number of elements from $A$ to kill every approximate progression — contradicting that $A$ keeps density $\delta$ on a set of size $N$ as large as we like. Hence a length- $k$ progression must exist. (Furstenberg's 1977 ergodic-theoretic proof and Gowers' higher-order Fourier-analytic proof reach the same conclusion by entirely different routes, each yielding explicit but astronomically large bounds on $N(k,\delta)$ .)

Theorem: The special case

k=3

: Roth's theorem

If $A \subseteq \{1,\dots,N\}$ has $|A| \ge \delta N$ and $N$ is large enough relative to $\delta$ , then $A$ contains a nontrivial 3-term arithmetic progression.

Why is it true?

This is the first nontrivial case of Szemerédi's theorem, proved by Roth in 1953 using Fourier analysis instead of the heavy regularity machinery needed for general $k$ . Its "density increment" strategy — either find the pattern, or show the set is unexpectedly structured and pass to a denser sub-progression — became the blueprint later reused, in vastly more sophisticated form, for the general theorem and for Green–Tao.

Proof

Step 1 (Fourier count of progressions). Suppose $A \subseteq \{1,\dots,N\}$ has density $\delta$ and no nontrivial 3-term progression. Writing $\hat{1_A}(\theta) = \sum_{n \in A} e(\theta n)$ for the Fourier transform of the indicator of $A$ , the number of triples $(x, x+r, x+2r) \in A^3$ can be written as an integral of $\hat{1_A}(\theta)^2 \, \overline{\hat{1_A}(2\theta)}$ over $\theta$ .

Step 2 (the pseudorandom case). If every nonzero Fourier coefficient of $1_A$ were small compared to $\delta^2$ , the integral would be dominated by the $\theta = 0$ term alone, which already forces roughly $\delta^3 N^2$ triples — far more than the trivial ones — contradicting the assumption that $A$ has none.

Step 3 (density increment). So some nonzero coefficient must be large; this means $1_A$ correlates with the linear phase $e(\theta n)$ , i.e. $A$ is noticeably biased on some arithmetic progression (or Bohr set). Restricting to that sub-progression produces a shorter interval on which the density of $A$ has increased by a fixed multiplicative factor.

Step 4 (iteration and conclusion). Density cannot increase past 1, so after finitely many rounds of this density-increment step the process must terminate — meaning the pseudorandom case of Step 2 is eventually forced, which produces the missing 3-term progression and contradicts the no-progression assumption. Roth's original bookkeeping gives $N(3,\delta) \lesssim \exp(\exp(1/\delta))$ -type thresholds; this was improved over decades, and Kelley and Meka's 2023 argument pushes the bound down to nearly Behrend's classical construction, $N(3,\delta) \lesssim \exp\!\big(-c(\log N)^{1/12}\big) N$ -type density, essentially closing the gap for this case.

UndergraduateReal-World Applications and Worked Examples

Szemerédi's own regularity lemma, invented as a tool inside this proof, went on to become one of the most-used tools in theoretical computer science: it underlies graph property testing algorithms (deciding whether a huge graph is close to satisfying a property by inspecting only a bounded-size random sample), gives lower bounds in communication complexity, and shows up in combinatorial design and coding theory. On the number-theory side, the theorem sits at one end of a spectrum whose other end is the Behrend construction of dense progression-free sets, and its finite form gives the combinatorial engine behind the Green–Tao theorem on primes.

Example: A 3-term progression inside a concrete set

Let $A = \{1,2,4,5,7,8,10,11\} \subseteq \{1,\dots,12\}$ — this is exactly the numbers from 1 to 12 that are not multiples of 3, so $d$ restricted to this window is $|A|/12 = 2/3$ . Find an explicit arithmetic progression of length 3 inside $A$ .

Solution

Step 1: since $A$ excludes exactly the multiples of 3, every element of $A$ has residue 1 or 2 modulo 3.

Step 2: pick common difference $r=3$ (a multiple of 3) so that $a, a+r, a+2r$ all share the same residue class modulo 3, hence all avoid the missing residue 0.

Step 3: taking $a=1$ gives $1, 4, 7$ , and indeed $1,4,7 \in A$ — a genuine 3-term progression, matching what Szemerédi's theorem guarantees for any set of positive density once the window is large enough.

Example: Pigeonhole forces a dense — hence structured — color class

Color the integers red if odd and blue if even. Among $\{1,\dots,9\}$ the red class is $\{1,3,5,7,9\}$ , already $5/9$ of the window. Explain why this pigeonhole-style argument, combined with Szemerédi's theorem, guarantees a monochromatic 3-term progression whenever finitely many colors are used on a long enough interval — and exhibit the progression here.

Solution

Step 1: with 2 colors partitioning 9 integers, the color sizes sum to 9, so by pigeonhole the larger class has at least $\lceil 9/2 \rceil = 5$ elements — here the red class $\{1,3,5,7,9\}$ has exactly 5.

Step 2: 5 elements inside a window of 9 means the red class already has density $5/9 > 0$ on this finite window, and in fact the odd numbers have density exactly $1/2$ over all of $\mathbb{Z}^+$ .

Step 3: since the odd numbers have positive density, Szemerédi's theorem (applied with $k=3$ ) guarantees they contain 3-term progressions — and indeed the red class itself, $1,3,5$ , is one, with common difference 2. This is exactly the mechanism (positive density forced by pigeonhole, then Szemerédi's theorem) that recovers van der Waerden's finite-coloring theorem as a corollary.

Research frontier as of 2026

The regularity/hypergraph method proves the theorem but with bounds on $N(k,\delta)$ that are tower-type in $k$ (a stack of exponentials whose height grows with $1/\delta$ ); Gowers showed in the late 1990s/2000s that his higher-order Fourier analysis gives much better, though still enormous, bounds for general $k$ . The quantitative frontier has moved fastest for $k=3$ : Kelley and Meka's 2023 breakthrough gives a bound of the shape $N(3,\delta) \lesssim \exp\!\big(-c(\log N)^{1/12}\big) N$ , nearly matching Behrend's 1946 lower-bound construction. Getting comparably tight bounds for $k \ge 4$ remains open, as does finding the true growth rate of $N(k,\delta)$ for each $k$ . A separate frontier links back to number theory: the transference principle behind the Green–Tao theorem, and its extensions to polynomial progressions and other sparse pseudorandom sets, is an active research direction connecting this theorem directly to the primes.

Using $d(A) = \limsup_{N \to \infty} \frac{|A \cap [1,N]|}{N}$ , what is the upper density $d(A)$ of the set $A$ of all even positive integers?

What does Szemerédi's theorem conclude about a set $A \subseteq \mathbb{Z}^+$ with $d(A) > 0$ ?

Why does Szemerédi's theorem imply van der Waerden's theorem on finite colorings?

Why can't Szemerédi's theorem be applied directly to show the primes contain arbitrarily long arithmetic progressions?

References

Endre Szemerédi (1975). On sets of integers containing no k elements in arithmetic progression
Hillel Furstenberg (1977). Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions · DOI:10.1007/BF02813304
Zander Kelley, Raghu Meka (2023). Strong bounds for 3-progressions · arXiv:2302.05537