Legendre's conjecture

Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime number between ${\displaystyle n^{2}}$ and ${\displaystyle (n+1)^{2}}$ for every positive integer ${\displaystyle n}$. The conjecture is one of Landau's problems (1912) on prime numbers, and is one of many open problems on the spacing of prime numbers.

Unsolved problem in mathematics:

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

(more unsolved problems in mathematics)

If Legendre's conjecture is true, the gap between any prime p and the next largest prime would be ${\displaystyle 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 ${\displaystyle n}$ and ${\displaystyle 2n}$, Oppermann's conjecture on the existence of primes between ${\displaystyle n^{2}}$, ${\displaystyle n(n+1)}$, and ${\displaystyle (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 ${\displaystyle (\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 ${\displaystyle 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 ${\displaystyle n^{2}}$ and ${\displaystyle (n+1)^{2}}$ is approximately ${\displaystyle 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 ${\displaystyle 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.

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

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

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

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

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

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

• v
• t
• e