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] Dudek proved that this holds for all ${\displaystyle n\geq e^{e^{33.3}}}$ .^[7]

Dudek also proved that for ${\displaystyle m=5.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}$  ^[8] which was further reduced to ${\displaystyle m=155}$  by Cully-Hugill.^[9]

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

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}}$ .^[11]

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