Misplaced Pages

Revision as of 23:30, 1 March 2014

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 can be. It states that

${\displaystyle p_{n+1}-p_{n}=O((\log p_{n})^{2}),\ }$

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 argument actually supports the stronger statement

${\displaystyle \limsup _{n\rightarrow \infty }{\frac {p_{n+1}-p_{n}}{(\log p_{n})^{2}}}=1,}$

and this formulation is often called Cramér's conjecture in the literature.

Neither form of Cramér's conjecture has yet been proven or disproven.

Conditional proven results on prime gaps

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

${\displaystyle p_{n+1}-p_{n}=O({\sqrt {p_{n}}}\,\log p_{n})}$

on the assumption of the Riemann hypothesis.

In the other direction, E. Westzynthius proved in 1931 that prime gaps grow more than logarithmically. That is,

${\displaystyle \limsup _{n\to \infty }{\frac {p_{n+1}-p_{n}}{\log p_{n}}}=\infty .}$

Heuristic justification

Cramér's conjecture is based on a probabilistic model (essentially a heuristic) of the primes, in which one assumes that the probability of a natural number of size x being prime is 1/log x. This is known as the Cramér model of the primes. Cramér proved that in this model, the above conjecture holds true with probability one.

Heuristics of Shanks and Cramér–Granville conjectures

Daniel Shanks conjectured asymptotic equality of record gaps, a somewhat stronger statement than Cramér's conjecture.

In the random model,

${\displaystyle \limsup _{n\rightarrow \infty }{\frac {p_{n+1}-p_{n}}{(\log p_{n})^{2}}}=c,}$ with ${\displaystyle c=1.}$

But this constant, ${\displaystyle c}$, may not apply to all the primes, by Maier's theorem. As pointed out by Andrew Granville, a refinement of Cramér's model taking into account divisibility by small primes suggests that ${\displaystyle c\geq 2e^{-\gamma }\approx 1.1229\ldots }$, OEIS: A125313 where ${\displaystyle \gamma }$ is the Euler–Mascheroni constant. OEIS: A001620

Thomas Nicely has calculated many large prime gaps. He measures the quality of fit to Cramér's conjecture by measuring the ratio

${\displaystyle R={\frac {\log(p_{n})}{\sqrt {p_{n+1}-p_{n}}}}.}$

He writes, “For the largest known maximal gaps, ${\displaystyle R}$ has remained near 1.13.” However, ${\displaystyle 1/R^{2}}$ is still less than 1, and it does not provide support to Granville's refinement that c should be greater than 1.

Wolf's conjecture

In the paper Marek Wolf has proposed the formula for the maximal gaps ${\displaystyle G(x)}$ expressed directly by the counting function of prime numbers ${\displaystyle \pi (x)}$: ${\displaystyle G(x)\sim {\frac {\pi (x)}{x}}(2\ln(\pi (x))-\ln(x)+c_{0}),}$

where ${\displaystyle c_{0}=\ln(C_{2})=0.2778769...}$, here ${\displaystyle C_{2}=1.3203236...}$ is the twin primes constant. Putting Gauss's approximation ${\displaystyle \pi (x)\sim x/\ln(x)}$ gives ${\displaystyle G(x)\sim \ln(x)(\ln(x)-2\ln(\ln(x)))}$ and for large ${\displaystyle x}$ it goes into the Cramer's conjecture ${\displaystyle G(x)\sim \ln ^{2}(x)}$. As it is seen on Fig. Prime gap function no one of conjectures of Cramer, Granville and Firoozbakht crosses the actual plot of maximal gaps while the Wolf's formula shows over 20 intersection with currently available actual data up to ${\displaystyle 1.43\times 10^{18}}$.

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

1. ^ Cramér, Harald (1936), "On the order of magnitude of the difference between consecutive prime numbers" (PDF), Acta Arithmetica, 2: 23–46
2. Westzynthius, E. (1931), "Über die Verteilung der Zahlen die zu den n ersten Primzahlen teilerfremd sind", Commentationes Physico-Mathematicae Helingsfors, 5: 1–37, JFM 57.0186.02, Zbl 0003.24601.
3. Shanks, Daniel (1964), "On Maximal Gaps between Successive Primes", Mathematics of Computation, 18 (88), American Mathematical Society: 646–651, doi:10.2307/2002951, JSTOR 2002951.
4. Granville, A. (1995), "Harald Cramér and the distribution of prime numbers" (PDF), Scandinavian Actuarial Journal, 1: 12–28.
5. 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.
6. Wolf, Marek (2014), "Nearest-neighbor-spacing distribution of prime numbers and quantum chaos", Phys. Rev. E, 89: 022922

• 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. 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. Vol. 237. Dordrecht: Springer-Verlag. pp. 59–83. ISBN 978-1-4020-5403-7. Zbl 1141.11043.

External links

• Weisstein, Eric W. "Cramér Conjecture". MathWorld.
• Weisstein, Eric W. "Cramér-Granville Conjecture". MathWorld.

• Analytic number theory
• Conjectures about prime numbers