Misplaced Pages

Cramér's conjecture

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Cramér conjecture) This article uses technical mathematical notation for logarithms. All instances of log(x) without a subscript base should be interpreted as a natural logarithm, also commonly written as ln(x) or loge(x).

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

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

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

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

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

p n + 1 p n < ( log p n ) 2 . {\displaystyle p_{n+1}-p_{n}<(\log p_{n})^{2}.}

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

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

on the assumption of the Riemann hypothesis. The best known unconditional bound is

p n + 1 p n = O ( p n 0.525 ) {\displaystyle p_{n+1}-p_{n}=O(p_{n}^{0.525})}

due to Baker, Harman, and Pintz.

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

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

His result was improved by R. A. Rankin, who proved that

lim sup n p n + 1 p n log p n ( log log log p n ) 2 log log p n log log log log p n > 0. {\displaystyle \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.}

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, and independently by James Maynard. The two sets of authors eliminated one of the factors of log log log p n {\displaystyle \log \log \log p_{n}} later that year, showing that, infinitely often,

  p n + 1 p n > c log p n log log p n log log log log p n log log log p n {\displaystyle \ {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}}}}

where c > 0 {\displaystyle c>0} is some constant.

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.

In the Cramér random model,

lim sup n p n + 1 p n log 2 p n = 1 {\displaystyle \limsup _{n\rightarrow \infty }{\frac {p_{n+1}-p_{n}}{\log ^{2}p_{n}}}=1}

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 the limit should not be 1, but a constant c 2 e γ 1.1229 {\displaystyle c\geq 2e^{-\gamma }\approx 1.1229\ldots } (OEISA125313), where γ {\displaystyle \gamma } 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 c > 2 {\displaystyle c>2} , there is a constant d > 0 {\displaystyle d>0} such that there is a prime between x {\displaystyle x} and x + d ( log x ) c {\displaystyle x+d(\log x)^{c}} .

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 some theorems concerning short intervals between primes, such as Maier's theorem, which contradict Cramér's model.

(internal references removed).

Related conjectures and heuristics

Prime gap function

Daniel Shanks conjectured the following asymptotic equality, stronger than Cramér's conjecture, for record gaps: G ( x ) log 2 x . {\displaystyle G(x)\sim \log ^{2}x.}

J.H. Cadwell has proposed the formula for the maximal gaps: G ( x ) log 2 x log x log log x , {\displaystyle G(x)\sim \log ^{2}x-\log x\log \log x,} which is formally identical to the Shanks conjecture but suggests a lower-order term.

Marek Wolf has proposed the formula for the maximal gaps G ( x ) {\displaystyle G(x)} expressed in terms of the prime-counting function π ( x ) {\displaystyle \pi (x)} :

G ( x ) x π ( x ) ( 2 log π ( x ) log x + c ) , {\displaystyle G(x)\sim {\frac {x}{\pi (x)}}(2\log \pi (x)-\log x+c),}

where c = log ( 2 C 2 ) = 0.2778769... {\displaystyle c=\log(2C_{2})=0.2778769...} and C 2 = 0.6601618... {\displaystyle C_{2}=0.6601618...} is the twin primes constant; see OEISA005597, A114907. This is again formally equivalent to the Shanks conjecture but suggests lower-order terms

G ( x ) log 2 x 2 log x log log x ( 1 c ) log x . {\displaystyle G(x)\sim \log ^{2}x-2\log x\log \log x-(1-c)\log x.} .

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

R = log p n p n + 1 p n . {\displaystyle R={\frac {\log p_{n}}{\sqrt {p_{n+1}-p_{n}}}}.}

He writes, "For the largest known maximal gaps, R {\displaystyle R} has remained near 1.13."

See also

References

  1. ^ Cramér, Harald (1936), "On the order of magnitude of the difference between consecutive prime numbers" (PDF), Acta Arithmetica, 2: 23–46, doi:10.4064/aa-2-1-23-46, archived from the original (PDF) on 2018-07-23, retrieved 2012-03-12
  2. Baker, R. C., Harman, G., Pintz, J. (2001), "The Difference Between Consecutive Primes, II", Proceedings of the London Mathematical Society, 83 (3), Wiley: 532–562, doi:10.1112/plms/83.3.532
  3. Westzynthius, E. (1931), "Über die Verteilung der Zahlen die zu den n ersten Primzahlen teilerfremd sind", Commentationes Physico-Mathematicae Helsingsfors (in German), 5 (5): 1–37, JFM 57.0186.02, Zbl 0003.24601.
  4. Rankin, R. A. (December 1938). "The difference between consecutive prime numbers". J. London Math. Soc. 13 (4): 242–247. doi:10.1017/S0013091500025633.
  5. Ford, Kevin; Green, Ben; Konyagin, Sergei; Tao, Terence (2016). "Large gaps between consecutive prime numbers". Annals of Mathematics. Second series. 183 (3): 935–974. arXiv:1408.4505. doi:10.4007/annals.2016.183.3.4.
  6. Maynard, James (2016). "Large gaps between primes". Annals of Mathematics. Second series. 183 (3): 915–933. arXiv:1408.5110. doi:10.4007/annals.2016.183.3.3.
  7. Ford, Kevin; Green, Ben; Konyagin, Sergei; Maynard, James; Tao, Terence (2018). "Long gaps between primes". Journal of the American Mathematical Society. 31: 65–105. arXiv:1412.5029. doi:10.1090/jams/876.
  8. Terry Tao, 254A, Supplement 4: Probabilistic models and heuristics for the primes (optional), section on The Cramér random model, January 2015.
  9. 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, archived from the original (PDF) on 2015-09-23, retrieved 2007-06-05.
  10. Pintz, János (April 1997). "Very large gaps between consecutive primes" (PDF). Journal of Number Theory. 63 (2): 286–301. doi:10.1006/jnth.1997.2081.
  11. Adleman, Leonard; McCurley, Kevin (6 May 1994). "Open Problems in Number Theoretic Complexity, II". ANTS-I: Proceedings of the First International Symposium on Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 877. Ithaca, NY: Springer. pp. 291–322. CiteSeerX 10.1.1.48.4877. doi:10.1007/3-540-58691-1_70. ISBN 3-540-58691-1.
  12. Robin Visser, Large Gaps Between Primes, University of Cambridge (2020).
  13. 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, Zbl 0128.04203.
  14. Cadwell, J. H. (1971), "Large Intervals Between Consecutive Primes", Mathematics of Computation, 25 (116): 909–913, doi:10.2307/2004355, JSTOR 2004355
  15. Wolf, Marek (2014), "Nearest-neighbor-spacing distribution of prime numbers and quantum chaos", Phys. Rev. E, 89 (2): 022922, arXiv:1212.3841, Bibcode:2014PhRvE..89b2922W, doi:10.1103/physreve.89.022922, PMID 25353560, S2CID 25003349
  16. Nicely, Thomas R. (1999), "New maximal prime gaps and first occurrences", Mathematics of Computation, 68 (227): 1311–1315, Bibcode:1999MaCom..68.1311N, doi:10.1090/S0025-5718-99-01065-0, MR 1627813.

External links

Prime number conjectures
Categories: