# Is this statement equivalent to Legendre's conjecture?

The maximum distance from any given number n to the next prime is less than twice the square root of n.

Is this statement equivalent to Legendre's conjecture? Is this statement worded correctly? If this statement were to be proven, would Legendre's conjecture be proven?

Is there another way to express Legendre's conjecture, a way which states that the upper bound on the prime gap above any perfect square is related to the square root of that perfect square, such that the statement is equivalent to Legendre's conjecture?

Taking into consideration the fact that 3 is the only prime of the form n^2-1, can we restate Legendre's conjecture to say the following?:

There will always be a prime in the interval between n^2 and n^2+2n.

Note that for n=1, 2 is between 1 and 3.

• At first it seems stronger. The statement is clear. Yes, if this were shown, then Legendre's conjecture would follow. – André Nicolas Sep 27 '14 at 7:55
• The answer of Prometheus explains the issue clearly. I do not see a way to prove your conjecture in any easy way if I am told I can assume Legendre's Conjecture. – André Nicolas Sep 27 '14 at 17:48

Let's say $r^2 \leq n < (r+1)^2$. If Legendre's conjecture is true, there is a prime $p$ in the interval $(r^2,(r+1)^2)$, and another prime $q$ in $((r+1)^2,(r+2)^2)$.

If you were asking about the distance between $n$ and the nearest prime, then it follows that since $n$ and $p$ are in the interval $[r^2,(r+1)^2]$ which has $2r$ integers in its interior, then $|n-p| < 2r \leq 2\sqrt{n}$. So Legendre's conjecture implies that the distance between $n$ and the nearest prime is less than $2\sqrt{n}$.

But if you ask about the next prime after $n$, it would seem consistent with Legendre's conjecture if $p=r^2+1$, $n=r^2+2$, and the next prime after $n$ is $q=(r+2)^2-2$. In that case $|n-q| = 4r$ and that's greater than $2\sqrt{n}=2\sqrt{r^2+2}$.

If your conjecture were true, then the next prime after $r^2$ would be less than $r^2+2r$, so it would fall within $(r^2,(r+1)^2)$. Therefore your conjecture implies Legendre's, but it's not clear if Legendre's implies yours.

The answer to my question is no.

The answer to the first question which I asked was answered. Indeed, if the upper bound for the prime gap above n is < (2)(the square root of n), then Legendre's conjecture is true. However, Legendre's conjecture does not imply the statement which I asked about. The statement which I initially asked about is not exactly equivalent to Legendre's conjecture.