Cramér's conjecture

Template:Log(x) In number theory, Cramér's conjecture, formulated by the Swedish mathematician Harald Cramér in 1936,<ref name="Cramér1936">Template:Citation</ref> 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

<math>p_{n+1}-p_n=O((\log p_n)^2),</math>

where p_n 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

<math>\limsup_{n\rightarrow\infty} \frac{p_{n+1}-p_n}{(\log p_n)^2} = 1,</math>

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.

The strongest form of all, which was never claimed by Cramér but is the one used in experimental verification computations and the plot in this article, is simply

<math>p_{n+1}-p_n < (\log p_n)^2.</math>

None of the three forms has yet been proven or disproven.

Conditional proven results on prime gaps

Cramér gave a conditional proof of the much weaker statement that

<math>p_{n+1}-p_n = O(\sqrt{p_n}\,\log p_n)</math>

on the assumption of the Riemann hypothesis.<ref name="Cramér1936" /> The best known unconditional bound is

<math>p_{n+1}-p_n = O(p_n^{0.525})</math>

due to Baker, Harman, and Pintz.<ref>Template:Citation </ref>

In the other direction, E. Westzynthius proved in 1931 that prime gaps grow more than logarithmically. That is,<ref>Template:Citation.</ref>

<math>\limsup_{n\to\infty}\frac{p_{n+1}-p_n}{\log p_n}=\infty.</math>

His result was improved by R. A. Rankin,<ref>Template:Cite journal</ref> who proved that

<math>\limsup_{n\to\infty}\frac{p_{n+1}-p_n}{\log p_n}\cdot\frac{\left(\log\log\log p_n\right)^2}{ \log\log p_n \log\log\log\log p_n} > 0.</math>

Paul Erdős conjectured that the left-hand side of the above formula is infinite, and this was proven in 2014 by Kevin Ford, Ben Green, Sergei Konyagin, and Terence Tao,<ref>Template:Cite journal</ref> and independently by James Maynard.<ref>Template:Cite journal</ref> The two sets of authors eliminated one of the factors of <math>\log \log \log p_n</math> later that year,<ref>Template:Cite journal</ref> showing that, infinitely often,

<math>\ {p_{n+1}-p_n} { > } \frac{c\cdot\log p_n \cdot\log\log p_n \cdot\log\log\log\log p_n}{\log\log\log p_n} </math>

where <math>c > 0</math> is some constant.

Template:Anchor Heuristic justification

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.<ref>Terry Tao, 254A, Supplement 4: Probabilistic models and heuristics for the primes (optional), section on The Cramér random model, January 2015.</ref>

In the Cramér random model,

<math>\limsup_{n\rightarrow\infty} \frac{p_{n+1}-p_n}{\log^2 p_n} = 1</math>

with probability one.<ref name="Cramér1936" /> However, as pointed out by Andrew Granville,<ref>Template:Citation.</ref> 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 the limit should not be 1, but a constant <math>c \ge 2e^{-\gamma}\approx1.1229\ldots</math> (Template:OEIS2C), where <math>\gamma</math> is the Euler–Mascheroni constant. János Pintz has suggested that the limit sup may be infinite,<ref>Template:Cite journal</ref> 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 <math>c>2</math>, there is a constant <math>d>0</math> such that there is a prime between <math>x</math> and <math>x+d(\log x)^c</math>.<ref>Template:Cite book</ref>

Similarly, Robin Visser writes

In fact, due to the work done by Granville, it is now widely believed that Cramér's conjecture is false. Indeed, there [are] some theorems concerning short intervals between primes, such as Maier's theorem, which contradict Cramér's model.<ref>Robin Visser, Large Gaps Between Primes, University of Cambridge (2020).</ref>

(internal references removed).

Related conjectures and heuristics

File:Primegaps-new.png

Prime gap function

Daniel Shanks conjectured the following asymptotic equality, stronger than Cramér's conjecture,<ref>Template:Citation.</ref> for record gaps: <math>G(x)\sim \log^2 x.</math>

J.H. Cadwell<ref name="Cadwell1971">Template:Citation</ref> has proposed the formula for the maximal gaps: <math>G(x)\sim \log^2 x - \log x\log\log x,</math> which is formally identical to the Shanks conjecture but suggests a lower-order term.

Marek Wolf<ref name="Wolf2014">Template:Citation</ref> has proposed the formula for the maximal gaps <math>G(x)</math> expressed in terms of the prime-counting function <math>\pi(x)</math>:

<math>G(x)\sim \frac{x}{\pi(x)}(2\log\pi(x)-\log x+c),</math>

where <math>c=\log(2C_2)=0.2778769...</math> and <math>C_2=0.6601618...</math> is the twin primes constant; see Template:OEIS2C, A114907. This is again formally equivalent to the Shanks conjecture but suggests lower-order terms

<math>G(x) \sim \log^2 x - 2\log x\log\log x - (1-c)\log x.</math>.

Thomas Nicely has calculated many large prime gaps.<ref>Template:Citation.</ref> He measures the quality of fit to Cramér's conjecture by measuring the ratio

<math>R = \frac{\log p_n}{\sqrt{p_{n+1}-p_n}}.</math>

He writes, "For the largest known maximal gaps, <math>R</math> has remained near 1.13."

See also

• 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

References

• Template:Cite book
• Template:Cite journal
• Template:Cite book

External links

• Template:Mathworld
• Template:Mathworld