# 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.

• Please use the edit link on your question to add additional information. The Post Answer button should be used only for complete answers to the question. – apnorton Sep 28 '14 at 4:22
• My question has been answered. However, the answer has caused me to wonder about something other than what I initially asked. So the answer to my initial question seems to be a no, because the statement which I initially asked about is not equivalent to Legendre's conjecture, but slightly stronger. Now, I am seeking an equivalent to Legendre's conjecture. This is a different matter than what I initially asked about and might become a separate question. The initial question is answered in full. – Jeffrey Young Sep 30 '14 at 1:16
• oops, sorry. I must have clicked a wrong button on the review queue (which automatically places comments like that). Sorry. – apnorton Sep 30 '14 at 12:10
• Human error is a standard part of mathematics. It's fine. I had to do some editing any way. I had asked a question and the answer I received led me to further investigate to find what I was looking for. I am now formulating something new which will have to be a separate question. – Jeffrey Young Oct 2 '14 at 3:32
• @JeffreyYoung: answers are not the place to ask new questions; new questions are the perfect place for that. At best this should be a comment to your question. – robjohn Oct 2 '14 at 7:57