Legendre's conjecture

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

Unsolved problem in mathematics:

Does there always exist at least one prime between n2 and (n+1)2?

Prime gaps

Legendre's conjecture is one of a family of results and conjectures related to prime gaps, that is, to the spacing between prime numbers.

Plot of the number of primes between n2 and (n + 1)2

The prime number theorem suggests that the actual number of primes between n2 and (n + 1)2 () is asymptotic to n/ln(n). Since this number is large for large n, this lends credence to Legendre's conjecture.

If Legendre's conjecture is true, the gap between any prime p and the next largest prime would always be at most on the order of ${\displaystyle {\sqrt {p}}}$;[a] in big O notation, the gaps are ${\displaystyle O({\sqrt {p}})}$. Two stronger conjectures, Andrica's conjecture and Oppermann's conjecture, also both imply that the gaps have the same magnitude.

Harald Cramér conjectured 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. 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]

A counterexample near 1018 would require a prime gap fifty million times the size of the average gap.

Legendre's conjecture implies that at least one prime can be found in every half revolution of the Ulam spiral.

Partial results

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

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

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

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