In number theory, the Green–Tao theorem, proved 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.
Let denote the number of primes less than or equal to . If is a subset of the prime numbers such that
then for all positive integers , the set contains infinitely many arithmetic progressions of length . 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
for the number of k tuples of primes in arithmetic progression. Here, is the constant
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. Once the pseudorandomness of the set is established, the transference principle may be applied, completing the proof.
The proof of the Green–Tao theorem 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.
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.'.
- 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.
- 43,142,746,595,714,191 + 23,681,770 · 223,092,870 · n, for n = 0 to 25.
Extensions and generalizations
Many of the extensions of Szemerédi's theorem hold for the primes as well.
Independently, Tao and Ziegler and Cook, Magyar, and Titichetrakun derived a multidimensional generalization of the Green–Tao theorem. The Tao–Ziegler proof was also simplified by Fox and Zhao.
In 2006, Tao and Ziegler extended the Green–Tao theorem to cover polynomial progressions. 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.
- Erdős conjecture on arithmetic progressions
- Dirichlet's theorem on arithmetic progressions
- Arithmetic combinatorics
- 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..
- Green, Ben; Tao, Terence (2010). "Linear equations in primes". Annals of Mathematics. 171 (3): 1753–1850. arXiv:math/0606088. doi:10.4007/annals.2010.171.1753. MR 2680398.
- Green, Ben; Tao, Terence (2012). "The Möbius function is strongly orthogonal to nilsequences". Annals of Mathematics. 175 (2): 541–566. arXiv:0807.1736. doi:10.4007/annals.2012.175.2.3. MR 2877066.
- Green, Ben; Tao, Terence; Ziegler, Tamar (2012). "An inverse theorem for the Gowers Us+1[N]-norm". Annals of Mathematics. 172 (2): 1231–1372. arXiv:1009.3998. doi:10.4007/annals.2012.176.2.11. MR 2950773.
- Goldston, Daniel A.; Pintz, János; Yıldırım, Cem Y. (2009). "Primes in tuples. I". Annals of Mathematics. 170 (2): 819–862. arXiv:math/0508185. doi:10.4007/annals.2009.170.819. MR 2552109.
- Andersen, Jens Kruse. "Primes in Arithmetic Progression Records". Retrieved 2015-06-27.
- Tao, Terence; Ziegler, Tamar (2015). "A multi-dimensional Szemerédi theorem for the primes via a correspondence principle". Israel J. Math. 207 (1): 203–228. arXiv:1306.2886. doi:10.1007/s11856-015-1157-9. MR 3358045.
- Cook, Brian; Magyar, Ákos (2012). "Constellations in ". Int. Math. Res. Not. IMRN. 2012 (12): 2794–2816. doi:10.1093/imrn/rnr127. MR 2942710.
- Cook, Brian; Magyar, Ákos; Titichetrakun, Tatchai (2015). "A Multidimensional Szemerédi Theorem in the primes". arXiv:1306.3025 [math.NT].
- Fox, Jacob; Zhao, Yufei (2015). "A short proof of the multidimensional Szemerédi theorem in the primes". Amer. J. Math. 137 (4): 1139–1145. arXiv:1307.4679. doi:10.1353/ajm.2015.0028. MR 3372317.
- Tao, Terence; Ziegler, Tamar (2008). "The primes contain arbitrarily long polynomial progressions". Acta Mathematica. 201 (2): 213–305. arXiv:math.NT/0610050. doi:10.1007/s11511-008-0032-5. MR 2461509.
- Tao, Terence; Ziegler, Tamar (2013). "Erratum to “The primes contain arbitrarily long polynomial progressions”". Acta Mathematica. 210 (2): 403–404. doi:10.1007/s11511-013-0097-7. MR 3070570.
- Tao, Terence (2006). "The Gaussian primes contain arbitrarily shaped constellations". J. Anal. Math. 99 (1): 109–176. arXiv:math/0501314. doi:10.1007/BF02789444. MR 2279549.
- Conlon, David; Fox, Jacob; Zhao, Yufei (2014). "The Green–Tao theorem: an exposition". EMS Surveys in Mathematical Sciences. 1 (2): 249–282. arXiv:1403.2957. doi:10.4171/EMSS/6. MR 3285854.CS1 maint: ref=harv (link)
- Gowers, Timothy (2010). "Decompositions, approximate structure, transference, and the Hahn–Banach theorem". Bulletin of the London Mathematical Society. 42 (4): 573–606. arXiv:0811.3103. doi:10.1112/blms/bdq018. MR 2669681.
- Green, Ben (2007). "Long arithmetic progressions of primes". In Duke, William; Tschinkel, Yuri (eds.). Analytic number theory. Clay Mathematics Proceeding. 7. Providence, RI: American Mathematical Society. pp. 149–167. ISBN 978-0-8218-4307-9. MR 2362199.
- Host, Bernard (2006). "Progressions arithmétiques dans les nombres premiers (d'après B. Green et T. Tao)" [Arithmetical progressions in the primes (after B. Green and T. Tao)] (PDF). Astérisque (in French) (307): 229–246. MR 2296420.
- Kra, Bryna (2006). "The Green–Tao theorem on arithmetic progressions in the primes: an ergodic point of view". Bulletin of the American Mathematical Society . 43 (1): 3–23. doi:10.1090/S0273-0979-05-01086-4. MR 2188173.
- Tao, Terence (2006). "Arithmetic progressions and the primes". Collectanea Mathematica. Vol. Extra: 37–88. MR 2264205. Archived from the original on 2015-08-05. Retrieved 2015-06-05.
- Tao, Terence (2006). "Obstructions to uniformity and arithmetic patterns in the primes". Pure and Applied Mathematics Quarterly. 2 (2): 395–433. arXiv:math/0505402. doi:10.4310/PAMQ.2006.v2.n2.a2. MR 2251475.
- Tao, Terence (2008-01-07). "AMS lecture: Structure and randomness in the prime numbers".