Legendre’s Conjecture

Legendre's conjecture, going back to his Essai sur la théorie des nombres of 1798 [Legendre1798], asserts that between any two consecutive squares $n^2$ and $(n+1)^2$ there is always a prime. Since the interval has length $2n+1$, which is about $x^{1/2}$ at $x=n^2$, the conjecture amounts to saying that gaps between consecutive primes near $x$ never exceed roughly the square-root scale.

The prime number theorem and its refinements guarantee primes in progressively shorter intervals; the strongest unconditional result, due to Baker, Harman and Pintz, produces a prime in $(x-x^{0.525},x]$ for all sufficiently large $x$ [BakerHarmanPintz2001], close to the $x^{1/2}$ scale but short of it. Even the Riemann hypothesis yields intervals only slightly longer than $x^{1/2}$, so the conjecture is not known to follow from RH; the relevant machinery is laid out by Iwaniec and Kowalski [IwaniecKowalski2004].

Since no finite computation can settle all $n$, a proof must break the $0.525$ barrier down to the square-root scale for every large $x$. The conjecture remains open.