Legendre's conjecture

Conjecture. For every integer $n\ge1$ there is a prime strictly between $n^2$ and $(n+1)^2$:

$$\forall n\ge1\ \ \exists\,p \text{ prime with } n^2<p<(n+1)^2 .$$

Equivalently, with $\pi(x)$ the number of primes $p\le x$,

$$\pi\bigl((n+1)^2\bigr)-\pi\bigl(n^2\bigr)\ge1\qquad\text{for every } n\ge1,$$

since the squares themselves are not prime. The problem is to decide the statement. A solution may either prove it for every $n\ge1$, or disprove it by exhibiting an $n\ge1$ for which the interval $(n^2,(n+1)^2)$ contains no prime. Both directions are open. [6]

The interval has length $2n+1\approx2\sqrt{x}$ at height $x=n^2$. The conjecture therefore asks for primes in intervals of length about $2\sqrt x$ placed at the specific points $x=n^2$. It does not assert that every interval $(x,x+2\sqrt x\,]$ contains a prime.

Background

The conjecture is attributed to Legendre. Landau listed it in 1912 as one of four problems about primes that he considered unattackable with the methods of the day, together with the Goldbach conjecture, the twin prime conjecture, and the infinitude of primes of the form $n^2+1$ [6].

The prime number theorem predicts about $2n/\log(n^2)=n/\log n$ primes in $(n^2,(n+1)^2)$, so the conjecture is expected to hold with room to spare. The difficulty lies in proving that primes appear in every interval of length $\asymp\sqrt x$. Even the Riemann hypothesis gives only Cramér's bound $p_{k+1}-p_k=O(\sqrt{p_k}\log p_k)$ [2]. That bound is too weak by a factor of $\log p_k$. Cramér's probabilistic model suggests gaps of size $O((\log p_k)^2)$, which would imply the conjecture for all large $n$ [2]. The conjecture is also implied by Andrica's conjecture and by Oppermann's conjecture [6].