TheoremProved

Green–Tao theorem

Statement

The sequence of prime numbers contains arithmetic progressions of every finite length: for every $k$ , there exist primes $a, a+d, a+2d, \dots, a+(k-1)d$ with $d>0$ .

Why is it true?

Even though primes become sparser as numbers grow, they are not so irregular as to avoid forming long, evenly-spaced patterns — a consequence of the primes being 'pseudorandom enough' relative to Szemerédi-type density results, which guarantee long progressions in any sufficiently dense set of integers.

Proof sketch

Combine Szemerédi's theorem (any subset of the integers of positive relative density contains arbitrarily long arithmetic progressions) with a transference principle: although the primes have density $0$ in $\mathbb{N}$ , embed a suitable weighted majorant of the primes inside a pseudorandom set of positive relative density (built from primes in residue classes together with an auxiliary pseudorandom measure), transferring Szemerédi's theorem from the dense pseudorandom setting to the primes themselves.

Proved by

proved 2004Terence Tao

Topics that use this theorem

The Green–Tao theorem Szemerédi's theorem

Related theorems

Szemerédi's theorem Dirichlet's theorem on primes in arithmetic progressions Infinitude of primes (Euclid)

Step-by-step proofs

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

References

Ben Green, Terence Tao (2008). The primes contain arbitrarily long arithmetic progressions · arXiv:math/0404188
Terence Tao, Van H. Vu (2006). Additive Combinatorics · DOI:10.1017/CBO9780511755149