The primes contain arbitrarily long arithmetic progressions

2004/04/08 by Ben Green, Terence Tao, Green, Ben +1 · 36 citations
Mathematics · #Algorithm #Analytic Number Theory Research #Arithmetic #Arithmetic progression #Combinatorics #Computer science #Discrete mathematics #Dynamical Systems (math.DS) #FOS: Mathematics #Finite Group Theory Research #Ingredient #Limits and Structures in Graph Theory #Mathematics #Number Theory (math.NT) #Pseudorandom number generator #Set (abstract data type) #math.DS #math.NT

paper · pdf · doi:10.48550/arxiv.math/0404188

published in arXiv (Cornell University) (Cornell University) · 56 pages. Further minor corrections

openalex publication_date 2004/04/08 · arxiv created 2007/09/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We prove that there are arbitrarily long arithmetic progressions of primes. There are three major ingredients. The first is Szemeredi's theorem, which asserts that any subset of the integers of positive density contains progressions of arbitrary length. The second, which is the main new ingredient of this paper, is a certain transference principle. This allows us to deduce from Szemeredi's theorem that any subset of a sufficiently pseudorandom set of positive relative density contains progressions of arbitrary length. The third ingredient is a recent result of Goldston and Yildirim. Using this, one may place the primes inside a pseudorandom set of ``almost primes'' with positive relative density.

Citations

• Higher correlations of divisor sums related to primes III: k-correlations
• On Some Sequences of Integers
• On Certain Sets of Integers

Cited by

• Roth-type theorems in additive combinatroics
• An Intuitionistic Glance at Primes
• A random polynomial with multiplicative coefficients is almost surely irreducible
• Roth's Theorem in Super Smooth Numbers
• On infinite sumsets and sets of multiple recurrence
• Learning stabilizer structure of quantum states
• The trigonometric polynomial on sums of two squares, an additive problem and generalisation
• Finding arithmetic progressions in dense sets of integers
• Supersimulators
• Small Composite Numbers in Orbits of Linear Maps
• Arithmetic progressions of primes in short intervals beyond the 17/30 barrier
• Quantum Higher Order Fourier Analysis and the Clifford Hierarchy
• On the density version of quadratic Waring's problem and the quadratic Waring--Goldbach problem
• Finite field models in additive combinatorics
• A Simple Regularization of Hypergraphs
• Obstructions to uniformity, and arithmetic patterns in the primes
• Martin Davis: An Overview of his Work in Logic, Computer Science, and Philosophy
• Sublattices of finite index
• Some geometric and spectral aspects of restriction problems
• Schreier Sets in Ramsey Theory
• Polynomial progressions in the generalized twin primes
• Combinatorial theorems relative to sparse sets
• On a particular case of the Dirichlet's theorem and the Midy's property
• The Solecki submeasures and densities on groups
• A variant of the hypergraph removal lemma
• Polynomial configurations in dense subsets of the prime lattice
• Quasipolynomial bounds for the corners theorem

Related

• The primes contain arbitrarily long arithmetic progressions
• Narrow arithmetic progressions in the primes
• Progressions arithmétiques dans les nombres premiers, d'après B. Green et T. Tao
• Arithmetic progressions and the primes - El Escorial lectures
• Long arithmetic progressions of primes