Large gaps between consecutive prime numbers

Abstract

Let $G(X)$ denote the size of the largest gap between consecutive primes below $X$. Answering a question of Erdős, we show that \[ G(X) \geq f(X) \frac{\log X \log \log X \log \log \log \log X}{(\log \log \log X)^2},\] where $f(X)$ is a function tending to infinity with $X$. Our proof combines existing arguments with a random construction covering a set of primes by arithmetic progressions. As such, we rely on recent work on the existence and distribution of long arithmetic progressions consisting entirely of primes.

  • [balog] Go to document A. Balog, "The prime $k$-tuplets conjecture on average," in Analytic Number Theory, Boston: Birkhäuser, 1990, vol. 85, pp. 47-75.
    @incollection{balog, mrkey = {1084173},
      author = {Balog, Antal},
      title = {The prime {$k$}-tuplets conjecture on average},
      booktitle = {Analytic Number Theory},
      venue = {{A}llerton {P}ark, {IL},
      1989},
      series = {Progr. Math.},
      volume = {85},
      pages = {47--75},
      publisher = {Birkhäuser},
      address = {Boston},
      year = {1990},
      mrclass = {11P32 (11N25 11P55)},
      mrnumber = {1084173},
      mrreviewer = {D. R. Heath-Brown},
      doi = {10.1007/978-1-4612-3464-7_5},
      zblnumber = {0719.11066},
      }
  • [BHP] Go to document R. C. Baker, G. Harman, and J. Pintz, "The difference between consecutive primes. II," Proc. London Math. Soc., vol. 83, iss. 3, pp. 532-562, 2001.
    @article{BHP, mrkey = {1851081},
      author = {Baker, R. C. and Harman, G. and Pintz, J.},
      title = {The difference between consecutive primes. {II}},
      journal = {Proc. London Math. Soc.},
      fjournal = {Proceedings of the London Mathematical Society. Third Series},
      volume = {83},
      year = {2001},
      number = {3},
      pages = {532--562},
      issn = {0024-6115},
      coden = {PLMTAL},
      mrclass = {11N05 (11N36)},
      mrnumber = {1851081},
      mrreviewer = {D. R. Heath-Brown},
      doi = {10.1112/plms/83.3.532},
      zblnumber = {1016.11037},
      }
  • [deB] N. G. de Bruijn, "On the number of positive integers $\leq x$ and free of prime factors $>y$," Nederl. Acad. Wetensch. Proc. Ser. A., vol. 54, pp. 50-60, 1951.
    @article{deB, mrkey = {0046375},
      author = {de Bruijn, N. G.},
      title = {On the number of positive integers {$\leq x$} and free of prime factors {$>y$}},
      journal = {Nederl. Acad. Wetensch. Proc. Ser. A.},
      volume = {54},
      year = {1951},
      pages = {50--60},
      mrclass = {10.0X},
      mrnumber = {0046375},
      mrreviewer = {P. T. Bateman},
      zblnumber = {0042.04204},
      }
  • [cfz] Go to document D. Conlon, J. Fox, and Y. Zhao, "A relative Szemerédi theorem," Geom. Funct. Anal., vol. 25, iss. 3, pp. 733-762, 2015.
    @article{cfz, mrkey = {3361771},
      author = {Conlon, David and Fox, Jacob and Zhao, Yufei},
      title = {A relative {S}zemerédi theorem},
      journal = {Geom. Funct. Anal.},
      fjournal = {Geometric and Functional Analysis},
      volume = {25},
      year = {2015},
      number = {3},
      pages = {733--762},
      issn = {1016-443X},
      mrclass = {11B30 (11B25)},
      mrnumber = {3361771},
      doi = {10.1007/s00039-015-0324-9},
      zblnumber = {06466325},
      }
  • [Cra1920] H. Cramér, "Some theorems concerning prime numbers," Ark. Mat. Astr. Fys., vol. 15, pp. 1-33, 1920.
    @article{Cra1920,
      author = {Cramér, H.},
      title = {Some theorems concerning prime numbers},
      journal = {Ark. Mat. Astr. Fys.},
      volume = {15},
      year = {1920},
      pages = {1--33},
      jfmnumber = {47.0156.01},
      }
  • [Cra] H. Cramér, "On the order of magnitude of the difference between consecutive prime numbers," Acta Arith., vol. 2, pp. 23-46, 1936.
    @article{Cra,
      author = {Cramér, H.},
      title = {On the order of magnitude of the difference between consecutive prime numbers},
      journal = {Acta Arith.},
      volume = {2},
      year = {1936},
      pages = {23--46},
      zblnumber = {0015.19702},
      }
  • [Da] H. Davenport, Multiplicative Number Theory, Third ed., New York: Springer-Verlag, 2000, vol. 74.
    @book{Da, mrkey = {1790423},
      author = {Davenport, Harold},
      title = {Multiplicative Number Theory},
      series = {Graduate Texts in Math.},
      volume = {74},
      edition = {Third},
      publisher = {Springer-Verlag},
      year = {2000},
      pages = {xiv+177},
      isbn = {0-387-95097-4},
      mrclass = {11-02 (11-01 11Mxx 11Nxx)},
      mrnumber = {1790423},
      address = {New York},
      zblnumber = {1002.11001},
      }
  • [dickson] L. E. Dickson, History of the Theory of Numbers, Vol. III, Washington, DC: Carnegie Inst. of Washington, 1919, 1920, 1923.
    @book{dickson,
      author = {Dickson, L. E.},
      title = {History of the Theory of Numbers, Vol. III},
      publisher = {Carnegie Inst. of Washington},
      address = {Washington, DC},
      year = {1919, 1920, 1923},
      note={ \jfm{47.0100.04},
      \jfm{47.0100.04},
      \jfm{49.0100.12},
     }
    }
  • [erdos-gaps] Go to document P. Erdös, "On the difference of consecutive primes," Q. J. Math, vol. 6, pp. 124-128, 1935.
    @article{erdos-gaps, mrkey = {0001759},
      author = {Erd{ö}s, P.},
      title = {On the difference of consecutive primes},
      journal = {Q. J. Math},
      fjournal = {The Quarterly Journal of Mathematics},
      volume = {6},
      year = {1935},
      pages = {124--128},
      zblnumber = {0012.01102},
      doi = {10.1093/qmath/os-6.1.124},
      }
  • [Erd90] Go to document P. ErdHos, "Some of my favourite unsolved problems," in A Tribute to Paul Erdős, Cambridge: Cambridge Univ. Press, 1990, pp. 467-478.
    @incollection{Erd90, mrkey = {1117038},
      author = {Erd{ő}s, Paul},
      title = {Some of my favourite unsolved problems},
      booktitle = {A Tribute to {P}aul {E}rdős},
      pages = {467--478},
      publisher = {Cambridge Univ. Press},
      address = {Cambridge},
      year = {1990},
      mrclass = {11-02 (05-02 52C10)},
      mrnumber = {1117038},
      mrreviewer = {Matti Jutila},
      zblnumber = {0709.11003},
      doi = {10.1017/CBO9780511983917.039},
      }
  • [FGKMT] K. Ford, B. Green, S. Konyagin, J. Maynard, and T. Tao, Long gaps between primes.
    @misc{FGKMT,
      author = {Ford, K. and Green, B. and Konyagin, S. and Maynard, J. and Tao, T.},
      title = {Long gaps between primes},
      note = {preprint},
      arxiv = {1412.5029},
      }
  • [FI] J. Friedlander and H. Iwaniec, Opera de Cribro, Providence, RI: Amer. Math. Soc., 2010, vol. 57.
    @book{FI, mrkey = {2647984},
      author = {Friedlander, John and Iwaniec, Henryk},
      title = {Opera de Cribro},
      series = {Ameri. Math. Soc. Colloq. Publ.},
      volume = {57},
      publisher = {Amer. Math. Soc.},
      address = {Providence, RI},
      year = {2010},
      pages = {xx+527},
      isbn = {978-0-8218-4970-5},
      mrclass = {11N35 (11-02 11N05 11N13 11N25 11N36)},
      mrnumber = {2647984},
      mrreviewer = {D. R. Heath-Brown},
      zblnumber = {1226.11099},
      }
  • [gowers-4] Go to document W. T. Gowers, "A new proof of Szemerédi’s theorem for arithmetic progressions of length four," Geom. Funct. Anal., vol. 8, iss. 3, pp. 529-551, 1998.
    @article{gowers-4, mrkey = {1631259},
      author = {Gowers, W. T.},
      title = {A new proof of {S}zemerédi's theorem for arithmetic progressions of length four},
      journal = {Geom. Funct. Anal.},
      fjournal = {Geometric and Functional Analysis},
      volume = {8},
      year = {1998},
      number = {3},
      pages = {529--551},
      issn = {1016-443X},
      coden = {GFANFB},
      mrclass = {11B25 (11N13)},
      mrnumber = {1631259},
      mrreviewer = {D. R. Heath-Brown},
      doi = {10.1007/s000390050065},
      zblnumber = {0907.11005},
      }
  • [Gra] Go to document A. Granville, "Harald Cramér and the distribution of prime numbers," Scand. Actuar. J., iss. 1, pp. 12-28, 1995.
    @article{Gra, mrkey = {1349149},
      author = {Granville, Andrew},
      title = {Harald {C}ramér and the distribution of prime numbers},
      journal = {Scand. Actuar. J.},
      fjournal = {Scandinavian Actuarial Journal},
      year = {1995},
      number = {1},
      pages = {12--28},
      issn = {0346-1238},
      mrclass = {01A05 (11-03)},
      mrnumber = {1349149},
      mrreviewer = {S. L. Segal},
      doi = {10.1080/03461238.1995.10413946},
      zblnumber = {0833.01018},
      }
  • [gt-thm] Go to document B. Green and T. Tao, "The primes contain arbitrarily long arithmetic progressions," Ann. of Math., vol. 167, iss. 2, pp. 481-547, 2008.
    @article{gt-thm, mrkey = {2415379},
      author = {Green, Ben and Tao, Terence},
      title = {The primes contain arbitrarily long arithmetic progressions},
      journal = {Ann. of Math.},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {167},
      year = {2008},
      number = {2},
      pages = {481--547},
      issn = {0003-486X},
      coden = {ANMAAH},
      mrclass = {11N13 (11A41 11B25 37A45)},
      mrnumber = {2415379},
      mrreviewer = {Tamar Ziegler},
      doi = {10.4007/annals.2008.167.481},
      zblnumber = {1191.11025},
      }
  • [gt-nilmobius] Go to document B. Green and T. Tao, "The quantitative behaviour of polynomial orbits on nilmanifolds," Ann. of Math., vol. 175, iss. 2, pp. 465-540, 2012.
    @article{gt-nilmobius, mrkey = {2877065},
      author = {Green, Ben and Tao, Terence},
      title = {The quantitative behaviour of polynomial orbits on nilmanifolds},
      journal = {Ann. of Math.},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {175},
      year = {2012},
      number = {2},
      pages = {465--540},
      issn = {0003-486X},
      mrclass = {37A15},
      mrnumber = {2877065},
      mrreviewer = {Tamar Ziegler},
      doi = {10.4007/annals.2012.175.2.2},
      zblnumber = {1251.37012},
      }
  • [gt-linearprimes] Go to document B. Green and T. Tao, "Linear equations in primes," Ann. of Math., vol. 171, iss. 3, pp. 1753-1850, 2010.
    @article{gt-linearprimes, mrkey = {2680398},
      author = {Green, Benjamin and Tao, Terence},
      title = {Linear equations in primes},
      journal = {Ann. of Math.},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {171},
      year = {2010},
      number = {3},
      pages = {1753--1850},
      issn = {0003-486X},
      coden = {ANMAAH},
      mrclass = {11N13 (11B30 11P32)},
      mrnumber = {2680398},
      mrreviewer = {Tamar Ziegler},
      doi = {10.4007/annals.2010.171.1753},
      zblnumber = {1242.11071},
      }
  • [GTZ-4] Go to document B. Green, T. Tao, and T. Ziegler, "An inverse theorem for the Gowers $U^4$-norm," Glasg. Math. J., vol. 53, iss. 1, pp. 1-50, 2011.
    @article{GTZ-4, mrkey = {2747135},
      author = {Green, Ben and Tao, Terence and Ziegler, Tamar},
      title = {An inverse theorem for the {G}owers {$U\sp 4$}-norm},
      journal = {Glasg. Math. J.},
      fjournal = {Glasgow Mathematical Journal},
      volume = {53},
      year = {2011},
      number = {1},
      pages = {1--50},
      issn = {0017-0895},
      mrclass = {11B30 (11N13 11P70)},
      mrnumber = {2747135},
      mrreviewer = {Julia Wolf},
      doi = {10.1017/S0017089510000546},
      zblnumber = {1262.11013},
      }
  • [GTZ] Go to document B. Green, T. Tao, and T. Ziegler, "An inverse theorem for the Gowers $U^{s+1}[N]$-norm," Ann. of Math., vol. 176, iss. 2, pp. 1231-1372, 2012.
    @article{GTZ, mrkey = {2950773},
      author = {Green, Ben and Tao, Terence and Ziegler, Tamar},
      title = {An inverse theorem for the {G}owers {$U\sp {s+1}[N]$}-norm},
      journal = {Ann. of Math.},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {176},
      year = {2012},
      number = {2},
      pages = {1231--1372},
      issn = {0003-486X},
      coden = {ANMAAH},
      mrclass = {11B30},
      mrnumber = {2950773},
      mrreviewer = {Julia Wolf},
      doi = {10.4007/annals.2012.176.2.11},
      zblnumber = {1282.11007},
      }
  • [HR] H. Halberstam and H. -E. Richert, Sieve Methods, New York: Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], 1974, vol. 4.
    @book{HR, mrkey = {0424730},
      author = {Halberstam, H. and Richert, H.-E.},
      title = {Sieve Methods},
      series = {London Math. Soc. Monogr.},
      volume = {4},
      publisher = {Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers]},
      address = {New York},
      year = {1974},
      pages = {xiv+364 pp. (loose errata)},
      mrclass = {10H30},
      mrnumber = {0424730},
      mrreviewer = {J. W. Porter},
      zblnumber = {0298.10026},
      }
  • [heath] D. R. Heath-Brown, "Gaps between primes, and the pair correlation of zeros of the zeta function," Acta Arith., vol. 41, iss. 1, pp. 85-99, 1982.
    @article{heath, mrkey = {0667711},
      author = {Heath-Brown, D. R.},
      title = {Gaps between primes, and the pair correlation of zeros of the zeta function},
      journal = {Acta Arith.},
      fjournal = {Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica},
      volume = {41},
      year = {1982},
      number = {1},
      pages = {85--99},
      issn = {0065-1036},
      coden = {AARIA9},
      mrclass = {10H15 (10H05)},
      mrnumber = {0667711},
      mrreviewer = {Matti Jutila},
      zblnumber = {0414.10044},
      }
  • [hl] Go to document G. H. Hardy and J. E. Littlewood, "Some problems of `Partitio numerorum’; III: On the expression of a number as a sum of primes," Acta Math., vol. 44, iss. 1, pp. 1-70, 1923.
    @article{hl, mrkey = {1555183},
      author = {Hardy, G. H. and Littlewood, J. E.},
      title = {Some problems of `{P}artitio numerorum'; {III}: {O}n the expression of a number as a sum of primes},
      journal = {Acta Math.},
      fjournal = {Acta Mathematica},
      volume = {44},
      year = {1923},
      number = {1},
      pages = {1--70},
      issn = {0001-5962},
      coden = {ACMAA8},
      mrclass = {Contributed Item},
      mrnumber = {1555183},
      doi = {10.1007/BF02403921},
      jfmnumber = {48.0143.04},
      }
  • [Iw] H. Iwaniec, "On the problem of Jacobsthal," Demonstratio Math., vol. 11, iss. 1, pp. 225-231, 1978.
    @article{Iw, mrkey = {0499895},
      author = {Iwaniec, Henryk},
      title = {On the problem of {J}acobsthal},
      journal = {Demonstratio Math.},
      fjournal = {Demonstratio Mathematica},
      volume = {11},
      year = {1978},
      number = {1},
      pages = {225--231},
      issn = {0420-1213},
      coden = {DEMADO},
      mrclass = {10H32},
      mrnumber = {0499895},
      mrreviewer = {H. Halberstam},
      zblnumber = {0378.10029},
      }
  • [MP] Go to document H. Maier and C. Pomerance, "Unusually large gaps between consecutive primes," Trans. Amer. Math. Soc., vol. 322, iss. 1, pp. 201-237, 1990.
    @article{MP, mrkey = {0972703},
      author = {Maier, Helmut and Pomerance, Carl},
      title = {Unusually large gaps between consecutive primes},
      journal = {Trans. Amer. Math. Soc.},
      fjournal = {Transactions of the American Mathematical Society},
      volume = {322},
      year = {1990},
      number = {1},
      pages = {201--237},
      issn = {0002-9947},
      coden = {TAMTAM},
      mrclass = {11N05 (11N35)},
      mrnumber = {0972703},
      mrreviewer = {Jean-Marie De Koninck},
      doi = {10.2307/2001529},
      zblnumber = {0706.11052},
      }
  • [maynard-small] Go to document J. Maynard, "Small gaps between primes," Ann. of Math., vol. 181, iss. 1, pp. 383-413, 2015.
    @article{maynard-small, mrkey = {3272929},
      author = {Maynard, James},
      title = {Small gaps between primes},
      journal = {Ann. of Math.},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {181},
      year = {2015},
      number = {1},
      pages = {383--413},
      issn = {0003-486X},
      mrclass = {11N05 (11N36)},
      mrnumber = {3272929},
      mrreviewer = {Ya Ming Lu},
      doi = {10.4007/annals.2015.181.1.7},
      zblnumber = {1306.11073},
      }
  • [maynard] Go to document J. Maynard, "Large gaps between primes," Ann. of Math., vol. 183, pp. 915-933, 2016.
    @article{maynard,
      author = {Maynard, James},
      title = {Large gaps between primes},
      journal = {Ann. of Math.},
      volume = {183},
      year = {2016},
      pages = {915--933},
      doi={10.4007/annals.2016.183.3},
      }
  • [P] Go to document J. Pintz, "Very large gaps between consecutive primes," J. Number Theory, vol. 63, iss. 2, pp. 286-301, 1997.
    @article{P, mrkey = {1443763},
      author = {Pintz, J{á}nos},
      title = {Very large gaps between consecutive primes},
      journal = {J. Number Theory},
      fjournal = {Journal of Number Theory},
      volume = {63},
      year = {1997},
      number = {2},
      pages = {286--301},
      issn = {0022-314X},
      coden = {JNUTA9},
      mrclass = {11N05 (11N36)},
      mrnumber = {1443763},
      mrreviewer = {Gunter Dufner},
      doi = {10.1006/jnth.1997.2081},
      zblnumber = {0870.11056},
      }
  • [R1] Go to document R. A. Rankin, "The difference between consecutive prime numbers," J. London Math. Soc., vol. S1-13, iss. 4, pp. 242-247, 1938.
    @article{R1, mrkey = {1574971},
      author = {Rankin, R. A.},
      title = {The difference between consecutive prime numbers},
      journal = {J. London Math. Soc.},
      fjournal = {The Journal of the London Mathematical Society},
      volume = {S1-13},
      number = {4},
      pages = {242--247},
      year={1938},
      mrclass = {Contributed Item},
      mrnumber = {1574971},
      doi = {10.1112/jlms/s1-13.4.242},
      jfmnumber = {64.0982.01},
      }
  • [rankin-1963] Go to document R. A. Rankin, "The difference between consecutive prime numbers. V," Proc. Edinburgh Math. Soc., vol. 13, pp. 331-332, 1962/1963.
    @article{rankin-1963, mrkey = {0160767},
      author = {Rankin, R. A.},
      title = {The difference between consecutive prime numbers. {V}},
      journal = {Proc. Edinburgh Math. Soc.},
      fjournal = {Proceedings of the Edinburgh Mathematical Society. Series II},
      volume = {13},
      year = {1962/1963},
      pages = {331--332},
      issn = {0013-0915},
      mrclass = {10.42},
      mrnumber = {0160767},
      mrreviewer = {N. G. de Bruijn},
      doi = {10.1017/S0013091500025633},
      zblnumber = {0121.04705},
      }
  • [schonhage] Go to document A. Schönhage, "Eine Bemerkung zur Konstruktion grosser Primzahllücken," Arch. Math. $($Basel$)$, vol. 14, pp. 29-30, 1963.
    @article{schonhage, mrkey = {0146154},
      author = {Sch{ö}nhage, Arnold},
      title = {Eine {B}emerkung zur {K}onstruktion grosser {P}rimzahllücken},
      journal = {Arch. Math. $($Basel$)$},
      fjournal = {Archiv der Mathematik},
      volume = {14},
      year = {1963},
      pages = {29--30},
      issn = {0003-889X},
      mrclass = {10.42},
      mrnumber = {0146154},
      mrreviewer = {R. A. Rankin},
      doi = {10.1007/BF01234916},
      zblnumber = {0108.04504},
      }
  • [numerical-tos] Go to document T. Oliveira e Silva, S. Herzog, and S. Pardi, "Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$," Math. Comp., vol. 83, iss. 288, pp. 2033-2060, 2014.
    @article{numerical-tos, mrkey = {3194140},
      author = {Oliveira e Silva, Tom{á}s and Herzog, Siegfried and Pardi, Silvio},
      title = {Empirical verification of the even {G}oldbach conjecture and computation of prime gaps up to {$4\cdot 10\sp {18}$}},
      journal = {Math. Comp.},
      fjournal = {Mathematics of Computation},
      volume = {83},
      year = {2014},
      number = {288},
      pages = {2033--2060},
      issn = {0025-5718},
      mrclass = {11P32 (11A41 11N05 11N35 11Y35)},
      mrnumber = {3194140},
      mrreviewer = {Christian Elsholtz},
      doi = {10.1090/S0025-5718-2013-02787-1},
      zblnumber = {1290.11161},
      }
  • [szegedy] B. Szegedy, Gowers norms, regularization and limits of functions on abelian groups.
    @misc{szegedy,
      author = {Szegedy, B.},
      title = {Gowers norms, regularization and limits of functions on abelian groups},
      note = {preprint},
      arxiv = {1010.6211},
      }
  • [West] E. Westzynthius, "Über die Verteilung der Zahlen, die zu den $n$ ersten Primzahlen teilerfremd sind," Commentationes Physico–Mathematicae, Societas Scientarium Fennica, Helsingfors, vol. 5, pp. 1-37, 1931.
    @article{West,
      author = {Westzynthius, E.},
      title = {Über die Verteilung der Zahlen, die zu den $n$ ersten Primzahlen teilerfremd sind},
      journal = {Commentationes Physico--Mathematicae, Societas Scientarium Fennica, Helsingfors},
      volume = {5},
      year = {1931},
      pages = {1--37},
      zblnumber = {0003.24601},
      }

Authors

Kevin Ford

University of Illinois at Urbana-Champaign Urbana, IL

Ben Green

Mathematical Institute Oxford England

Sergei Konyagin

Steklov Mathematical Institute Moscow, Russia

Terence Tao

University of California Los Angeles CA