Take any set of whole numbers that is "not too thin" — say, every number you like, as long as you keep a fixed positive fraction of them. Colour the integers with a handful of crayons, or grab all the odd numbers, or all the numbers whose first digit is 7. However you do it, a startling promise holds: hidden inside your set are arithmetic progressions — evenly spaced runs like 5, 11, 17, 23, 29 — and not just short ones, but runs of every length you could ask for.

This is the world of additive combinatorics: the study of additive structure inside dense sets of integers, where you care about sums a+b and progressions a, a+d, a+2d, \dots rather than products and primes. Its crown jewel is Szemerédi's theorem (1975), and the machinery built to prove it — the regularity lemma, ergodic recurrence, the Gowers norms — reshaped three whole fields and ultimately powered the the Green–Tao theorem on primes in progression. Let's build up to it.

Warm-up: van der Waerden's theorem

Before density, there was colour. Imagine painting every positive integer with one of r colours — red, blue, green, however many you like. Bartel van der Waerden proved in 1927 that you can never avoid a monochromatic arithmetic progression.

Worked example. Take r = 2 colours and target length k = 3. The claim is that you cannot two-colour a long enough initial block without creating a monochromatic 3-term progression. Try to two-colour 1,\dots,9 avoiding one: colour \{1,4,5,8\} red and \{2,3,6,7\}... but now 9 must be coloured, and either choice completes a progression (with 1,5,9 or 3,6,9). In fact W(2,3) = 9 exactly — nine is the breaking point.

Van der Waerden's theorem is a colouring (or "partition") statement: split the integers into finitely many pieces and one piece must be rich. But it says nothing about which piece. If you two-colour and one colour is used for 99\% of the integers, surely the fat colour class should be the rich one? Making that intuition precise is a much deeper question — and its answer is Szemerédi's theorem.

From colour to density: Szemerédi's theorem

The right notion of "not too thin" is upper density. For a set A \subseteq \mathbb{N}, look at what fraction of \{1, \dots, N\} lands in A, and take the \limsup as N \to \infty:

If \bar{d}(A) > 0, we say A has positive upper density — it keeps at least a fixed slice \delta > 0 of the integers, no matter how far out you look. Erdős and Turán conjectured in 1936 that this alone forces long progressions. In 1975, Endre Szemerédi proved it.

Notice how this upgrades van der Waerden: if you finitely colour \mathbb{N}, at least one colour class must have positive upper density (the densities of the pieces sum to 1), and Szemerédi hands that fat class its progressions directly. So Szemerédi's theorem implies van der Waerden's — it says the rich class is exactly a dense one, which is the intuition we wanted.

Seeing a progression appear

Here are the numbers 1 to 35 laid on a grid. The filled dots are a dense set A. Step forward and watch two evenly-spaced runs — 3, 12, 21 with common difference 9, then 5, 15, 25 with common difference 10 — light up inside it. Szemerédi's theorem promises this can never fail: pack in a fixed fraction and the runs are forced to be there.

The picture also flags the difficulty. Finding one progression is easy; Szemerédi's theorem says you get arbitrarily long ones, uniformly, for every dense set at once — and that uniformity is what makes it hard.

The k = 3 case first: Roth's theorem

Long before Szemerédi, Klaus Roth cracked the first non-trivial case in 1953 — three-term progressions — with a beautiful Fourier-analytic argument.

Roth's method is the template for the whole field, so it is worth seeing its engine. Work in \mathbb{Z}/N\mathbb{Z} and let 1_A be the indicator of A. The number of 3-term progressions in A is captured by a Fourier sum over the characters \widehat{1_A}(r) = \sum_{x} 1_A(x)\, e^{-2\pi i rx/N}:

The r = 0 term is the "main term": it equals \delta^3 N^2, exactly the count you would expect if A were a random set of density \delta. Every other r is an "error" term controlled by the large Fourier coefficients. That split is the seed of the entire subject.

Worked example: one density-increment step

Here is the argument's heartbeat — the density-increment step — run heuristically. Suppose A \subseteq \{1, \dots, N\} has density \delta and, for contradiction, contains no 3-term progression.

Step 1 — no progressions kills the main term. If A were Fourier-uniform (all coefficients \widehat{1_A}(r) small for r \neq 0), the sum above would be dominated by its main term \delta^3 N^2 > 0, forcing many progressions. But we assumed there are none. So A cannot be uniform:

Step 2 — a big coefficient means structure. A large |\widehat{1_A}(r)| says A correlates with the wave x \mapsto e^{2\pi i rx/N}. That wave is roughly constant along stretches of an arithmetic progression P (choose P so the phase rx/N barely moves across it). On such a P, the correlation forces A to be denser than average:

for an absolute constant c > 0. The density has jumped by c\delta^2 on a long subprogression.

Step 3 — iterate. Rescale P to look like \{1, \dots, N'\} and repeat. Each pass increases the density by at least c\delta^2, but density can never exceed 1, so the process must halt after O(1/\delta) steps. When it halts, uniformity wins and a progression appears — contradiction. Hence A had a 3-AP all along.

This dichotomy — a set is either uniform (and has the expected count) or has structure you can exploit for a density gain — is the beating heart of additive combinatorics.

The organizing idea: structure vs randomness

Every proof of Szemerédi's theorem is a way of formalizing a single dichotomy. Given a dense set, one of two things is true, and each is good news:

If the set is random-like (uniform), the expected count of progressions is essentially correct — you are done immediately. If it is structured, you extract that structure to pass to a denser, smaller sub-object and recurse. The three great proofs differ only in how they measure uniformity and what structure they extract.

Three proofs, three languages

Szemerédi's theorem is famous for being proved three completely different ways, each of which founded a research programme.

(1) Szemerédi's combinatorial proof introduced the regularity lemma: every large graph can be partitioned into a bounded number of pieces so that, between most pairs of pieces, the edges look random (pseudorandom). This is the "structure vs randomness" split rendered in the language of graphs — a bounded structured skeleton plus quasirandom noise. The lemma is now a cornerstone of combinatorics in its own right, quite apart from progressions.

(2) Furstenberg's ergodic proof re-cast the whole problem. He showed Szemerédi's theorem is equivalent to a statement about dynamical systems — the multiple recurrence theorem: for a measure-preserving transformation T and a set E of positive measure,

The set returns to overlap itself at evenly spaced times n, 2n, \dots — a progression in time. This "Furstenberg correspondence" turned a counting problem into a recurrence problem and launched ergodic Ramsey theory. Its one drawback: being a soft, infinitary argument, it gives no explicit bounds at all.

(3) Gowers's analytic proof (2001) returned to Roth's Fourier method and asked: what is the right notion of uniformity for length-k progressions? Ordinary Fourier coefficients control k=3, but they are blind to "quadratic" structure that matters for k \ge 4. Gowers defined the uniformity norms U^k to fix exactly this, and — crucially — gave the first quantitative bounds.

The Gowers uniformity norms

The Gowers U^k norm measures how much a function correlates with polynomial phases of degree k-1. It is built from additive derivatives. For a function f : \mathbb{Z}/N\mathbb{Z} \to \mathbb{C}, the U^2 norm is

which turns out to equal \big(\sum_r |\widehat{f}(r)|^4\big)^{1/4} — so a small U^2 norm is exactly Roth-style Fourier uniformity. The higher norm U^k stacks k derivatives, controlling (k+1)-term progressions. The key facts:

Together these are the structure-vs-randomness dichotomy made quantitative for every k: small norm gives the count directly; large norm gives structure to iterate on. This is the exact package Green and Tao would later carry over to the primes.

How this feeds Green–Tao

The pieces now assemble. Green and Tao wanted arbitrarily long progressions of primes. They could not use Szemerédi directly (zero density), so they built a transference principle:

• Wrap the primes in a pseudorandom majorant \nu (a sieve weight) inside which the primes have positive relative density.
• Prove a relative Szemerédi theorem: any set of positive relative density in a sufficiently pseudorandom set contains long progressions.
• The engine of that relative theorem is Gowers-norm control — showing the prime-carrying weight is uniform enough that the U^k machinery still fires.

The conclusion — the the Green–Tao theorem — is that the primes contain arithmetic progressions of every length: 3, 5, 7; 5, 11, 17, 23, 29; and on forever. It is Szemerédi's theorem, relativized to a set that Szemerédi himself could not reach — the payoff of every idea on this page.