Legendre's conjecture

As of 2026 Legendre's conjecture remains open. Setting $x = n^2$, the interval $(n^2, (n+1)^2)$ has length $2x^{1/2} + 1$, so Legendre's conjecture requires guaranteeing a prime in every short interval $[x, x + 2x^{1/2}]$. The strongest unconditional short-interval prime theorem is due to Baker, Harman, and Pintz (2001), who combined Harman's sieve with Watt's mean-value theorem for Dirichlet polynomials to prove that $[x, x + x^{0.525}]$ contains a prime for all sufficiently large $x$. Even the Riemann hypothesis only gives $p_{k+1} - p_k = O(p_k^{1/2} \log p_k)$ (Cramér, 1920), which misses Legendre's threshold by a logarithmic factor. In the almost-prime direction, Chen (1975) proved that $[x, x + x^{1/2}]$ — and in particular $[n^2, (n+1)^2]$ for large $n$ — always contains a $P_2$ number with at most two prime factors. Numerically, maximal prime gaps have been checked past $2^{64} \approx 1.84 \times 10^{19}$, verifying Legendre's conjecture well beyond $n = 4 \times 10^9$.