Legendre's conjecture

Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime number between $n^{2}$ and $(n+1)^{2}$ for every positive integer $n$ . The conjecture is one of Landau's problems (1912) on prime numbers; as of 2024^[update], the conjecture has neither been proved nor disproved.

Unsolved problem in mathematics:

Does there always exist at least one prime between $n^{2}$ and $(n+1)^{2}$ ?

(more unsolved problems in mathematics)

Prime gaps[edit]

If Legendre's conjecture is true, the gap between any prime p and the next largest prime would be $O({\sqrt {p}}\,)$ , as expressed in big O notation.^[a] It is one of a family of results and conjectures related to prime gaps, that is, to the spacing between prime numbers. Others include Bertrand's postulate, on the existence of a prime between $n$ and $2n$ , Oppermann's conjecture on the existence of primes between $n^{2}$ , $n(n+1)$ , and $(n+1)^{2}$ , Andrica's conjecture and Brocard's conjecture on the existence of primes between squares of consecutive primes, and Cramér's conjecture that the gaps are always much smaller, of the order $(\log p)^{2}$ . If Cramér's conjecture is true, Legendre's conjecture would follow for all sufficiently large n. Harald Cramér also proved that the Riemann hypothesis implies a weaker bound of $O({\sqrt {p}}\log p)$ on the size of the largest prime gaps.^[1]

By the prime number theorem, the expected number of primes between $n^{2}$ and $(n+1)^{2}$ is approximately $n/\ln n$ , and it is additionally known that for almost all intervals of this form the actual number of primes (OEIS: A014085) is asymptotic to this expected number.^[2] Since this number is large for large $n$ , this lends credence to Legendre's conjecture.^[3] It is known that the prime number theorem gives an accurate count of the primes within short intervals, either unconditionally^[4] or based on the Riemann hypothesis,^[5] but the lengths of the intervals for which this has been proven are longer than the intervals between consecutive squares, too long to prove Legendre's conjecture.

Partial results[edit]

It follows from a result by Ingham that for all sufficiently large $n$ , there is a prime between the consecutive cubes $n^{3}$ and $(n+1)^{3}$ .^[6] Dudek proved that this holds for all $n\geq e^{e^{33.3}}$ .^[7]

Dudek also proved that for $m=5.10^{9}$ and any positive integer $n$ , there is a prime between $n^{m}$ and $(n+1)^{m}$ . Mattner lowered this to $m=1438989$ ^[8] which was further reduced to $m=155$ by Cully-Hugill.^[9]

Baker, Harman, and Pintz proved that there is a prime in the interval $[x-x^{21/40},\,x]$ for all large $x$ .^[10]

A table of maximal prime gaps shows that the conjecture holds to at least $n^{2}=4\cdot 10^{18}$ , meaning $n=2\cdot 10^{9}$ .^[11]

Notes[edit]

^ This is a consequence of the fact that the difference between two consecutive squares is of the order of their square roots.

References[edit]

^ Stewart, Ian (2013), Visions of Infinity: The Great Mathematical Problems, Basic Books, p. 164, ISBN 9780465022403.
^ Bazzanella, Danilo (2000), "Primes between consecutive squares" (PDF), Archiv der Mathematik, 75 (1): 29–34, doi:10.1007/s000130050469, MR 1764888, S2CID 16332859
^ Francis, Richard L. (February 2004), "Between consecutive squares", Missouri Journal of Mathematical Sciences, 16 (1), University of Central Missouri, Department of Mathematics and Computer Science: 51–57, doi:10.35834/2004/1601051; see p. 52, "It appears doubtful that this super-abundance of primes can be clustered in such a way so as to avoid appearing at least once between consecutive squares."
^ Heath-Brown, D. R. (1988), "The number of primes in a short interval" (PDF), Journal für die Reine und Angewandte Mathematik, 1988 (389): 22–63, doi:10.1515/crll.1988.389.22, MR 0953665, S2CID 118979018
^ Selberg, Atle (1943), "On the normal density of primes in small intervals, and the difference between consecutive primes", Archiv for Mathematik og Naturvidenskab, 47 (6): 87–105, MR 0012624
^ OEIS: A060199
^ Dudek, Adrian (December 2016), "An explicit result for primes between cubes", Funct. Approx., 55 (2): 177–197, arXiv:1401.4233, doi:10.7169/facm/2016.55.2.3, S2CID 119143089
^ Mattner, Caitlin (2017). Prime Numbers in Short Intervals (BSc thesis). Australian National University. doi:10.25911/5d9efba535a3e.
^ Cully-Hugill, Michaela (2023-06-01). "Primes between consecutive powers". Journal of Number Theory. 247: 100–117. arXiv:2107.14468. doi:10.1016/j.jnt.2022.12.002. ISSN 0022-314X.
^ Baker, R. C.; Harman, G.; Pintz, J. (2001), "The difference between consecutive primes, II" (PDF), Proceedings of the London Mathematical Society, 83 (3): 532–562, doi:10.1112/plms/83.3.532, S2CID 8964027
^ Oliveira e Silva, Tomás; Herzog, Siegfried; Pardi, Silvio (2014), "Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$ " (PDF), Mathematics of Computation, 83 (288): 2033–2060, doi:10.1090/S0025-5718-2013-02787-1, MR 3194140.

External links[edit]

Weisstein, Eric W., "Legendre's conjecture", MathWorld

This number theory-related article is a stub. You can help Wikipedia by expanding it.

[1] This is a consequence of the fact that the difference between two consecutive squares is of the order of their square roots.

[2] Stewart, Ian (2013), Visions of Infinity: The Great Mathematical Problems, Basic Books, p. 164, ISBN 9780465022403.

[3] Bazzanella, Danilo (2000), "Primes between consecutive squares" (PDF), Archiv der Mathematik, 75 (1): 29–34, doi:10.1007/s000130050469, MR 1764888, S2CID 16332859

[4] Francis, Richard L. (February 2004), "Between consecutive squares", Missouri Journal of Mathematical Sciences, 16 (1), University of Central Missouri, Department of Mathematics and Computer Science: 51–57, doi:10.35834/2004/1601051; see p. 52, "It appears doubtful that this super-abundance of primes can be clustered in such a way so as to avoid appearing at least once between consecutive squares."

[5] Heath-Brown, D. R. (1988), "The number of primes in a short interval" (PDF), Journal für die Reine und Angewandte Mathematik, 1988 (389): 22–63, doi:10.1515/crll.1988.389.22, MR 0953665, S2CID 118979018

[6] Selberg, Atle (1943), "On the normal density of primes in small intervals, and the difference between consecutive primes", Archiv for Mathematik og Naturvidenskab, 47 (6): 87–105, MR 0012624

[7] OEIS: A060199

[8] Dudek, Adrian (December 2016), "An explicit result for primes between cubes", Funct. Approx., 55 (2): 177–197, arXiv:1401.4233, doi:10.7169/facm/2016.55.2.3, S2CID 119143089

[9] Mattner, Caitlin (2017). Prime Numbers in Short Intervals (BSc thesis). Australian National University. doi:10.25911/5d9efba535a3e.

[10] Cully-Hugill, Michaela (2023-06-01). "Primes between consecutive powers". Journal of Number Theory. 247: 100–117. arXiv:2107.14468. doi:10.1016/j.jnt.2022.12.002. ISSN 0022-314X.

[baker-11] Baker, R. C.; Harman, G.; Pintz, J. (2001), "The difference between consecutive primes, II" (PDF), Proceedings of the London Mathematical Society, 83 (3): 532–562, doi:10.1112/plms/83.3.532, S2CID 8964027

[12] Oliveira e Silva, Tomás; Herzog, Siegfried; Pardi, Silvio (2014), "Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$ " (PDF), Mathematics of Computation, 83 (288): 2033–2060, doi:10.1090/S0025-5718-2013-02787-1, MR 3194140.

[a]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]