Green–Tao theorem

In number theory, the Green–Tao theorem, proven by Ben Green and Terence Tao in 2004, states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words, for every natural number $k$ , there exist arithmetic progressions of primes with $k$ terms. The proof is an extension of Szemerédi's theorem. The problem can be traced back to investigations of Lagrange and Waring from around 1770.{{cite journal|doi=10.4007/annals.2008.167.481|first1=Ben|last1=Green|author1-link=Ben J. Green|first2=Terence|last2=Tao|author2-link=Terence Tao|arxiv=math.NT/0404188 |title=The primes contain arbitrarily long arithmetic progressions|journal=Annals of Mathematics|volume=167|year=2008|issue=2|pages=481–547|mr=2415379|s2cid=1883951}}.

Statement

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} \frac$

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.

In their later work on the generalized Hardy–Littlewood conjecture, Green and Tao stated and conditionally proved the asymptotic formula

: $(\mathfrak{S}_k + o(1))\frac{N^2}{(\log N)^k}$

for the number of k tuples of primes $p_1 < p_2 < \dotsb < p_k \leq N$ in arithmetic progression.{{cite journal | last1=Green | first1=Ben | last2=Tao | first2=Terence | title=Linear equations in primes | journal=Annals of Mathematics | year=2010 | volume=171 | issue=3 | pages=1753–1850 | mr=2680398 | doi=10.4007/annals.2010.171.1753 | arxiv=math/0606088 | s2cid=119596965 }} Here, $\mathfrak{S}_k$ is the constant

: $\mathfrak{S}_k := \frac{1}{2(k-1)}\left(\prod_{p \leq k}\frac{1}p\left(\frac{p}{p - 1}\right)^{\!k-1}\right)\!\left(\prod_{p > k}\left(1 - \frac{k-1}p\right)\!\left(\frac{p}{p - 1}\right)^{\!k-1}\right)\!.$

The result was made unconditional by Green–Tao{{cite journal | last1=Green | first1=Ben | last2=Tao | first2=Terence | title=The Möbius function is strongly orthogonal to nilsequences | journal=Annals of Mathematics | year=2012 | volume=175 | issue=2 | pages=541–566 | mr=2877066 | doi=10.4007/annals.2012.175.2.3 | arxiv=0807.1736 }} and Green–Tao–Ziegler.{{cite journal | last1=Green | first1=Ben | last2=Tao | first2=Terence | last3=Ziegler | first3=Tamar | title=An inverse theorem for the Gowers $U^{s+1}[N]$ -norm | journal=Annals of Mathematics | year=2012 | volume=172 | issue=2 | pages=1231–1372 | mr=2950773 | doi=10.4007/annals.2012.176.2.11 | arxiv=1009.3998 }}

Overview of the proof

Green and Tao's proof has three main components:

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.
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.
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.{{cite journal | last1=Goldston | first1=Daniel A. | last2=Pintz | first2=János | last3=Yıldırım | first3=Cem Y. | title=Primes in tuples. I | journal=Annals of Mathematics | year=2009 | volume=170 | issue=2 | pages=819–862 | mr=2552109 | doi=10.4007/annals.2009.170.819| arxiv=math/0508185 | s2cid=1994756 }} 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 have been found. {{harvtxt|Conlon|Fox|Zhao|2014}} provide a modern exposition of the proof.

Numerical work

The proof of the Green–Tao theorem does not show how to find the arithmetic progressions of primes; it merely proves they exist. There has been separate computational work to find large arithmetic progressions in the primes.

The Green–Tao paper states 'At the time of writing the longest known arithmetic progression of primes is of length 23, and was found in 2004 by Markus Frind, Paul Underwood, and Paul Jobling: 56211383760397 + 44546738095860 · k; k = 0, 1, . . ., 22.'.

On January 18, 2007, Jarosław Wróblewski found the first known case of 24 primes in arithmetic progression:{{cite web | first=Jens Kruse| last=Andersen | url=http://primerecords.dk/aprecords.htm | title=Primes in Arithmetic Progression Records | access-date=2015-06-27}}

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

The constant 223,092,870 here is the product of the prime numbers up to 23, more compactly written 23# in primorial notation.

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 · 23# · 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 {{OEIS|id=A204189}}:

:43,142,746,595,714,191 + 23,681,770 · 23# · n, for n = 0 to 25.

In September 2019 Rob Gahan and PrimeGrid found the first known case of 27 primes {{OEIS|id=A327760}}:

:224,584,605,939,537,911 + 81,292,139 · 23# · n, for n = 0 to 26.

Extensions and generalizations

Many of the extensions of Szemerédi's theorem hold for the primes as well.

Independently, Tao and Ziegler{{cite journal | last1=Tao | first1=Terence | last2=Ziegler | first2=Tamar | author2link=Tamar Ziegler | title=A multi-dimensional Szemerédi theorem for the primes via a correspondence principle | journal=Israel Journal of Mathematics | volume=207 | year=2015 | issue=1 | pages=203–228 | mr=3358045 | doi=10.1007/s11856-015-1157-9 | doi-access=free | arxiv=1306.2886 | s2cid=119685169 }} and Cook, Magyar, and Titichetrakun{{cite journal | last1=Cook | first1=Brian | last2=Magyar | first2=Ákos | title=Constellations in $\mathbb P^d$ | journal=International Mathematics Research Notices | volume=2012 | issue=12 | pages=2794–2816 | mr=2942710 | doi=10.1093/imrn/rnr127 | year=2012}}{{cite journal | last1=Cook | first1=Brian | last2=Magyar | first2=Ákos | last3=Titichetrakun | first3=Tatchai | title=A Multidimensional Szemerédi Theorem in the primes via Combinatorics | arxiv=1306.3025 | journal=Annals of Combinatorics | volume=22 | pages=711–768 | year=2018 | issue=4 | doi=10.1007/s00026-018-0402-4| s2cid=126417608 }} derived a multidimensional generalization of the Green–Tao theorem. The Tao–Ziegler proof was also simplified by Fox and Zhao.{{cite journal | last1=Fox | first1=Jacob | last2=Zhao | first2=Yufei | title=A short proof of the multidimensional Szemerédi theorem in the primes | arxiv=1307.4679 | year=2015 | journal=American Journal of Mathematics | volume=137 | issue=4 | pages=1139–1145 | mr=3372317 | doi=10.1353/ajm.2015.0028| s2cid=17336496 }}

In 2006, Tao and Ziegler extended the Green–Tao theorem to cover polynomial progressions.{{cite journal|first1=Terence|last1=Tao|author1-link=Terence Tao|first2=Tamar|last2=Ziegler|author2link=Tamar Ziegler|title=The primes contain arbitrarily long polynomial progressions|journal=Acta Mathematica|volume=201|year=2008|pages=213–305 |arxiv=math/0610050|doi=10.1007/s11511-008-0032-5|doi-access=free|mr=2461509|issue=2|s2cid=119138411}}{{cite journal|first1=Terence|last1=Tao|author1-link=Terence Tao|first2=Tamar|last2=Ziegler|author2link=Tamar Ziegler|title=Erratum to "The primes contain arbitrarily long polynomial progressions"|journal=Acta Mathematica|volume=210|year=2013|pages=403–404 |doi=10.1007/s11511-013-0097-7|mr=3070570|issue=2|doi-access=free}} More precisely, given any integer-valued polynomials $P_1, \ldots, P_k$ in one unknown $m$ all with constant term 0, there are infinitely many integers $x, m$ such that $x + P_{1} (m), \ldots, x + P_{k} (m)$ are simultaneously prime. The special case when the polynomials are $m, 2m, \ldots, km$ implies the previous result that there arithmetic progressions of primes of length $k$ .

Tao proved an analogue of the Green–Tao theorem for the Gaussian primes.{{cite journal | last=Tao | first=Terence | title=The Gaussian primes contain arbitrarily shaped constellations | journal= Journal d'Analyse Mathématique | year=2006 | volume=99 | pages=109–176 | mr=2279549 | doi=10.1007/BF02789444 | doi-access=free | issue=1| arxiv=math/0501314 | s2cid=119664036 }}

Green–Tao theorem

Statement

Overview of the proof

Numerical work

Extensions and generalizations

See also

References

Further reading