In number theory, Cramér's conjecture, formulated by the Swedish mathematician Harald Cramér in 1936, is an estimate for the size of gaps between consecutive prime numbers: intuitively, that gaps between consecutive primes are always small, and the conjecture quantifies asymptotically just how small they must be. It states that
where pn denotes the nth prime number, O is big O notation, and "log" is the natural logarithm. While this is the statement explicitly conjectured by Cramér, his heuristic actually supports the stronger statement
and sometimes this formulation is called Cramér's conjecture. However, this stronger version is not supported by more accurate heuristic models, which nevertheless support the first version of Cramér's conjecture. Neither form has yet been proven or disproven.
Conditional proven results on prime gaps
In the other direction, E. Westzynthius proved in 1931 that prime gaps grow more than logarithmically. That is,
Cramér's conjecture is based on a probabilistic model—essentially a heuristic—in which the probability that a number of size x is prime is 1/log x. This is known as the Cramér random model or Cramér model of the primes.
In the Cramér random model,
with probability one. However, as pointed out by Andrew Granville, Maier's theorem shows that the Cramér random model does not adequately describe the distribution of primes on short intervals, and a refinement of Cramér's model taking into account divisibility by small primes suggests that (OEIS: A125313), where is the Euler–Mascheroni constant. János Pintz has suggested that the limit sup may be infinite, and similarly Leonard Adleman and Kevin McCurley write
- As a result of the work of H. Maier on gaps between consecutive primes, the exact formulation of Cramér's conjecture has been called into question [...] It is still probably true that for every constant , there is a constant such that there is a prime between and . 
Related conjectures and heuristics
J.H. Cadwell has proposed the formula for the maximal gaps: which is formally identical to the Shanks conjecture but suggests a lower-order term.
which for large is also asymptotically equivalent to the Cramér and Shanks conjectures: .
He writes, “For the largest known maximal gaps, has remained near 1.13.” However, is still less than 1.
- Prime number theorem
- Legendre's conjecture and Andrica's conjecture, much weaker but still unproven upper bounds on prime gaps
- Firoozbakht's conjecture
- Maier's theorem on the numbers of primes in short intervals for which the model predicts an incorrect answer
- Cramér, Harald (1936), "On the order of magnitude of the difference between consecutive prime numbers" (PDF), Acta Arithmetica, 2: 23–46
- R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II. Proc. London Math. Soc. (3), 83 (2001), no. 3, 532-562
- Westzynthius, E. (1931), "Über die Verteilung der Zahlen die zu den n ersten Primzahlen teilerfremd sind", Commentationes Physico-Mathematicae Helsingsfors (in German), 5: 1–37, JFM 57.0186.02, Zbl 0003.24601.
- R. A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13 (1938), 242-247
- K. Ford, B. Green, S. Konyagin, and T. Tao, Large gaps between consecutive prime numbers. Ann. of Math. (2) 183 (2016), no. 3, 935–974
- Terry Tao, 254A, Supplement 4: Probabilistic models and heuristics for the primes (optional), section on The Cramér random model, January 2015.
- Granville, A. (1995), "Harald Cramér and the distribution of prime numbers" (PDF), Scandinavian Actuarial Journal, 1: 12–28, doi:10.1080/03461238.1995.10413946.
- János Pintz, Very large gaps between consecutive primes, Journal of Number Theory 63:2 (April 1997), pp. 286–301.
- Leonard Adleman and Kevin McCurley, Open Problems in Number Theoretic Complexity, II. Algorithmic number theory (Ithaca, NY, 1994), 291–322, Lecture Notes in Comput. Sci., 877, Springer, Berlin, 1994.
- Shanks, Daniel (1964), "On Maximal Gaps between Successive Primes", Mathematics of Computation, American Mathematical Society, 18 (88): 646–651, doi:10.2307/2002951, JSTOR 2002951, Zbl 0128.04203.
- Cadwell, J. H. (1971), "Large Intervals Between Consecutive Primes", Mathematics of Computation, 25 (116): 909–913, doi:10.2307/2004355, JSTOR 2004355
- Wolf, Marek (2014), "Nearest-neighbor-spacing distribution of prime numbers and quantum chaos", Phys. Rev. E, 89: 022922, arXiv:1212.3841, Bibcode:2014PhRvE..89b2922W, doi:10.1103/physreve.89.022922
- Nicely, Thomas R. (1999), "New maximal prime gaps and first occurrences", Mathematics of Computation, 68 (227): 1311–1315, doi:10.1090/S0025-5718-99-01065-0, MR 1627813.
- Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. A8. ISBN 978-0-387-20860-2. Zbl 1058.11001.
- Pintz, János (2007). "Cramér vs. Cramér. On Cramér's probabilistic model for primes". Functiones et Approximatio Commentarii Mathematici. 37: 361–376. doi:10.7169/facm/1229619660. ISSN 0208-6573. MR 2363833. Zbl 1226.11096.
- Soundararajan, K. (2007). "The distribution of prime numbers". In Granville, Andrew; Rudnick, Zeév (eds.). Equidistribution in number theory, an introduction. Proceedings of the NATO Advanced Study Institute on equidistribution in number theory, Montréal, Canada, July 11--22, 2005. NATO Science Series II: Mathematics, Physics and Chemistry. 237. Dordrecht: Springer-Verlag. pp. 59–83. ISBN 978-1-4020-5403-7. Zbl 1141.11043.