Legendre's Conjecture

Legendre's Conjecture

Definitions and mathematical statement

A prime is an integer $p>1$ whose only positive divisors are $1$ and $p$. Legendre's conjecture is \[ \forall n\in{\mathbb{Z}}_{\ge1}\ \exists p\text{ prime}, \qquad n^2<p<(n+1)^2. \] Both inequalities are strict. Equivalently, if $\pi(x)=\#\{p\le x:p\text{ prime}\}$, one asks $\pi((n+1)^2)-\pi(n^2)\ge1$ for every $n\ge1$, since the upper endpoint is composite. The interval width is $2n+1$, but the assertion is a prime in every one of these specific intervals, not merely an average statement about intervals of this size.

Formulation and concept references: [S1].

Short English statement

Is there always a prime strictly between one positive integer's square and the next integer's square?

Research attempt

Status: UNRESOLVED. The problem is reduced exactly to a short-interval sieve count, and the amount of prime-gap control that would suffice is identified. Every interval with $1\le n\le2000$ is checked by an exact sieve with saved prime witnesses. Neither that finite computation, the prime number theorem, nor the standard consequences of the Riemann hypothesis proved in the cited literature cover all remaining intervals.

Source audit and endpoints.

The inherited MathWorld reference [S1] was consulted on 27 September 2026. Its retained update date is catalogue provenance; the live site's footer is not an independent theorem date. The primary paper of Chamberland and Straub [E1], dated February 2026, studies weaker larger-power intervals and explicitly retains the square case as a conjecture. Its conditional results for exponents greater than two must not be specialized to exponent two by taking a limit in an exponent-dependent threshold.

The integers strictly inside $(n^2,(n+1)^2)$ are \[ I_n=\{n^2+1,\ldots,n^2+2n\}, \] so there are $2n$ candidate integers, although the real interval has length $2n+1$. For $n=1$, both 2 and 3 are witnesses. The upper endpoint is composite for every $n\ge1$, and the lower endpoint is not prime either. Thus the prime-counting formulation in the statement has exactly the required strict interpretation.

1. An exact sieve with no probabilistic assumptions.

Put $P_n=\prod_{p\le n}p$, with the empty product equal to one. If $m\in I_n$ is composite, it has a prime factor at most $\sqrt m<n+1$, hence at most $n$. Conversely, no member of $I_n$ can itself be one of the primes at most $n$. Therefore \[ m\in I_n\text{ is prime}\quad\Longleftrightarrow\quad \gcd(m,P_n)=1. \] The equivalence also holds at $n=1$ by direct inspection. Inclusion-exclusion gives the exact identity \[ \#\{p\in I_n:p\text{ prime}\} =\sum_{d\mid P_n}\mu(d) \left(\left\lfloor\frac{n^2+2n}{d}\right\rfloor -\left\lfloor\frac{n^2}{d}\right\rfloor\right), \] where $\mu(d)=(-1)^r$ for a product of $r$ distinct primes. Thus Legendre's assertion is precisely strict positivity of this particular alternating floor sum for every $n$.

Replacing every floor difference by $2n/d$ suggests the main term \[ 2n\prod_{p\le n}(1-1/p). \] But each replacement has an error of absolute value less than one, and there are $2^{\pi(n)}$ squarefree divisors. The direct error estimate is exponentially larger than the desired positive main term. Consequently the existence of coprime residue classes modulo $P_n$ says nothing by itself about whether one lies in this interval of only $2n$ consecutive integers. The location of the interval inside a much longer residue period matters.

2. A sufficient prime-gap bound.

Suppose that for every sufficiently large prime $p$ its successor $p^+$ satisfies \[ p^+-p\le2\sqrt p. \] For a large integer $n$, let $p$ be the largest prime at most $n^2$. Since $n^2$ is composite for $n\ge2$, we have $p<n^2<p^+$. The proposed bound gives \[ p^+\le p+2\sqrt p<n^2+2n<(n+1)^2. \] This would prove Legendre's assertion for all sufficiently large $n$. A finite verification would still be needed below a specified threshold. More generally a bound $p^+-p\le C p^\theta$ with $\theta<1/2$, or with $\theta=1/2$ and $C\le2$, is sufficient eventually.

A square-root bound with an arbitrary constant is not automatically sufficient. The interval width has leading constant two in the variable $n$, so losing a factor in a purported comparison can destroy the implication. The stronger inequality $\sqrt{p^+}-\sqrt p<1$ also suffices by the same choice of preceding prime, but it is an additional conjectural input.

3. What Legendre itself would imply about gaps.

Conversely assume Legendre's statement and let $n=\lfloor\sqrt p\rfloor$. There is a prime in $((n+1)^2,(n+2)^2)$. The successor of $p$ is no larger than that prime, so \[ p^+-p<(n+2)^2-p\le4n+4\le4\sqrt p+4. \] Thus the conjecture would give square-root-size gaps, with this explicit constant. It does not follow from this argument that gaps are at most $2\sqrt p$, nor that each real interval of length $2\sqrt x+1$ contains a prime. The catalogue tests square boundaries with integer indices, whereas a uniform statement about arbitrary real intervals is stronger.

4. Why known asymptotic scales leave room for empty intervals.

The prime number theorem gives an average count on a long block of square intervals: \[ \sum_{n=1}^N\#\{p\in I_n\} =\pi((N+1)^2)\sim\frac{N^2}{2\log N}. \] Its mean over $N$ intervals therefore grows like $N/(2\log N)$. A large average of nonnegative integers does not force each integer to be positive. The sum is consistent with exceptions unless an additional uniform estimate rules them out. Infinitely many nonempty square intervals follow already from infinitely many primes, because each interval is finite; that is much weaker than every interval being nonempty.

The February 2026 primary discussion [E1] recalls the external Baker--Harman--Pintz short-gap exponent $0.525$. Substituting $x=n^2$ in a bound of order $x^{0.525}$ produces order $n^{1.05}$, which eventually exceeds $2n+1$. Likewise a usual RH gap estimate of order $\sqrt x\log x$ becomes order $n\log n$. Neither comparison reaches the needed width. These are statements about the scope of those estimates, not proofs that RH could never imply Legendre by a different argument.

Under a conjectural bound $p^+-p=O((\log p)^2)$, the ratio of the allowed gap to $\sqrt p$ tends to zero, so the sufficient criterion above holds eventually. This proves a conditional implication, not the input bound or a computable finite threshold when the constant is unspecified.

5. The exponent calculation for larger powers.

The gap calculation can be made explicit for a different family of intervals. Assume $p^+-p\le C p^\theta$ eventually, with fixed $\theta<1$. Suppose that no prime lies strictly between $n^a$ and $(n+1)^a$, where $a>1$ is fixed and the endpoints are treated separately if prime. A preceding prime and its successor then have a gap at least \[ (n+1)^a-n^a\ge a n^{a-1}. \] The assumed upper bound is at most $C n^{a\theta}$. These are incompatible for sufficiently large $n$ whenever \[ a-1>a\theta,\qquad\text{equivalently }a>\frac1{1-\theta}. \] At equality of exponents one would also need the constants to have the correct ordering. Taking $\theta=0.525$ gives threshold $40/19>2$. This explains directly why a result for a fixed exponent somewhat greater than two does not prove the square case. For general real $a$, endpoints that happen to be prime can be avoided by formulating the weaker conclusion with closed intervals; for the selected integer-square target both endpoints are nonprime and the issue disappears.

6. Long composite blocks do not give a counterexample.

For every integer $L\ge1$, the numbers \[ (L+1)!+2,\ldots,(L+1)!+(L+1) \] are composite, each divisible by its indicated offset. This proves arbitrarily long prime-free blocks. It does not put such a block over an entire consecutive-square interval. Their length is only $L$, while square intervals near the factorial have width comparable to the square root of that factorial, far larger than $L$ as $L$ grows.

Similarly, covering a fixed list of offsets by congruences does not automatically cover the growing list of $2n$ offsets associated with the constructed square $n^2$. A counterexample construction would have to synchronize the location and the full square-interval length, not merely produce a long composite string somewhere.

7. Exact finite verification and the missing positivity estimate.

The offline script sieves all integers through $2001^2$ by marking multiples of every prime through the integer square root of that bound. It records the first surviving prime in each strict interval for $1\le n\le2000$, checks the inequalities, and verifies each saved witness again by trial division. For small $n$ it also evaluates the complete inclusion-exclusion formula and compares it with the sieve count. The primality witnesses and cutoffs are saved with the results.

This proves the finite statement through the stated cutoff. The script has no claim to an asymptotic theorem and uses no floating primality heuristic. To complete the argument one needs, for all larger $n$, either positivity of the exact sifted interval count with an error smaller than its main term, a sufficiently sharp prime-gap theorem, or a different existence argument. None is obtained here, so the universal assertion remains unresolved.

Sources

• S1 Weisstein, E. W., Legendre's Conjecture, From MathWorld - A Wolfram Resource, updated 16 August 2026. https://mathworld.wolfram.com/LegendresConjecture.html. Formulation source.
• E1 Marc Chamberland and Armin Straub, Weakening the Legendre Conjecture, 25 February 2026, especially the introduction and Proposition 1.3. https://arminstraub.com/downloads/pub/legendre-riemann.pdf. Primary discussion of larger-power intervals and the limits of the cited gap estimates.