If the upper bound for the prime gap above $n$ is such that $n$+4$\sqrt{n-1}$$\geq p$, where $n$ is any given natural number and $p$ is the next prime after $n$, then Legendre's conjecture is true. If Legendre's conjecture is true, then $n$+4$\sqrt{n-1}$$\geq p$ is not implied by Legendre's conjecture.

Have I correctly stated these two things and are they both proven facts? If not, then the answer to my question would be a correction of these two statements. Does there exist such an inequality that would both be implied by and prove Legendre's conjecture? Is this impossible because Legendre's conjecture does not imply any bound on prime gaps?

So Legendre's conjecture can be proven if a tight enough bound were proven, but no bound can be proven by proving Legendre's conjecture. Is this right?

Is it the case that a bound on prime gaps above $n$ could prove Legendre's conjecture up to a point and then beyond that, assuming Legendre's conjecture, as $n$ goes to infinity, the bound would not always work as the gaps between consecutive perfect squares grow?


Legendre's conjecture (the assertion that there is a prime between every two perfect squares) implies that there's always a prime between $n$ and $n+4\sqrt{n-1}$. (The worst case would be if $n$ were one more than a perfect square $m^2$, and the next prime weren't until $(m+2)^2-1$. Small constants could be improved throughout.)

On the other hand, if it's true that there's always a prime between $n$ and $n+2\sqrt n$, then there would always be a prime between two perfect squares. (Take $n=m^2$.)

In fact, we believe it's true that for any $\epsilon>0$, there's always a prime between $n$ and $n+\epsilon\sqrt n$ when $n$ is sufficiently large. Indeed, we believe there's a constant $C$ such that there's always a prime between $n$ and $n+C\log^2n$. So in my opinion, it's not an important question whether one exact inequality is equivalent to Legendre's conjecture, when both of them are probably weaker than the truth.

  • $\begingroup$ I know what the truth actually is and indeed both the inequality which I asked about and Legendre's conjecture are weaker than it. What I am wondering about here is insignificant compared to the truth about bounded prime gaps, but I still want to know if it is really the case that Legendre's conjecture can be proven by a tight enough bound but cannot prove that same bound by which it was proven (assuming Legendre's conjecture). $\endgroup$ – Jeffrey Young Oct 3 '14 at 22:59
  • 1
    $\begingroup$ Yes, it really is the case. It's very common for Fact A to imply Fact B while Fact B doesn't imply Fact A. $\endgroup$ – Greg Martin Oct 3 '14 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.