Green–Tao theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In number theory, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004,[1] states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words there exist arithmetic progressions of primes, with k terms, where k can be any natural number. The proof is an extension of Szemerédi's theorem.

In 2006, Terence Tao and Tamar Ziegler extended the result to cover polynomial progressions.[2] More precisely, given any integer-valued polynomials P1,..., Pk in one unknown m all with constant term 0, there are infinitely many integers x, m such that x + P1(m), ..., x + Pk(m) are simultaneously prime. The special case when the polynomials are m, 2m, ..., km implies the previous result that there are length k arithmetic progressions of primes.


Let \pi(N) denote the number of primes less than or equal to N. If A is a subset of the prime numbers such that

\limsup_{N\rightarrow\infty} \dfrac{|A\cap [1,N]|}{\pi(N)}>0,

then for all positive integers k, the set A contains infinitely many arithmetic progressions of length k. In particular, the entire set of prime numbers contains arbitrarily long arithmetic progressions.

Overview of the proof[edit]

Green and Tao's proof has three main components:

  1. Szemerédi's theorem, which asserts that subsets of the integers with positive upper density have arbitrarily long arithmetic progressions. It does not a priori apply to the primes because the primes have density zero in the integers.
  2. A transference principle that extends Szemerédi's theorem to subsets of the integers which are pseudorandom in a suitable sense. Such a result is now called a relative Szemerédi theorem.
  3. A pseudorandom subset of the integers containing the primes as a dense subset. To construct this set, Green and Tao used ideas from Goldston, Pintz, and Yıldırım's work on prime gaps.[3] Once the pseudorandomness of the set is established, the transference principle may be applied, completing the proof.

Numerous simplifications to the argument in the original paper[1] have been found. Conlon, Fox & Zhao (2014) provide a modern exposition of the proof.

Numerical work[edit]

The proof of the Green–Tao does not show how to find the progressions of primes; it merely proves they exist. There has been separate computational work to find large arithmetic progressions in the primes. On January 18, 2007, Jarosław Wróblewski found the first known case of 24 primes in arithmetic progression:[4]

468,395,662,504,823 + 205,619 · 223,092,870 · n, for n = 0 to 23.

The constant 223092870 here is the product of the prime numbers up to 23 (see primorial).

On May 17, 2008, Wróblewski and Raanan Chermoni found the first known case of 25 primes:

6,171,054,912,832,631 + 366,384 · 223,092,870 · n, for n = 0 to 24.

On April 12, 2010, Benoãt Perichon with software by Wróblewski and Geoff Reynolds in a distributed PrimeGrid project found the first known case of 26 primes (sequence A204189 in OEIS):

43,142,746,595,714,191 + 23,681,770 · 223,092,870 · n, for n = 0 to 25.

See also[edit]


  1. ^ a b Green, Ben; Tao, Terence (2008). "The primes contain arbitrarily long arithmetic progressions". Annals of Mathematics 167 (2): 481–547. arXiv:math.NT/0404188. doi:10.4007/annals.2008.167.481. MR 2415379. .
  2. ^ Tao, Terence; Ziegler, Tamar (2008). "The primes contain arbitrarily long polynomial progressions". Acta Mathematica 201: 213–305. arXiv:math.NT/0610050. doi:10.1007/s11511-008-0032-5. MR 2461509. .
  3. ^ Goldston, Daniel A.; Pintz, János; Yıldırım, Cem Y. (2009). "Primes in tuples. I". Ann. of Math. 170 (2): 819–862. doi:10.4007/annals.2009.170.819. MR 2552109. 
  4. ^ Andersen, Jens Kruse. "Primes in Arithmetic Progression Records". Retrieved 2015-06-27. 

Further reading[edit]