Legendre's conjecture is that there exists a prime number between $n^2$ and $(n+1)^2$. This has been shown to be very likely using computers, but this is merely a heuristic. I have read that if this conjecture is true, the biggest gap between two consecutive primes is $O(\sqrt{p})$; the Riemann Hypothesis, on the other hand, implies that this gap is $O(\sqrt{p}\log{p})$, which is a wider gap for sufficiently large inputs. This leaves me asking the following question, which I am aware may be a bit naive, but I want to be sure:

Would a proof of Legendre's conjecture also be considered a proof of Riemann's hypothesis?

EDIT: I am aware that the way the asymptotic above were expressed was in terms of prime numbers, and that the Riemann Hypothesis is concerned about everything in between as well; would a proof of this sort need to show this upper bound for all inputs, or would the prime numbers be sufficient?

EDIT 2: It seems to me that, if a proof of Legendre's conjecture could result in a proof of the Riemann hypothesis, that this would come from the $\log{x}$ term of the asymptotic, showing that this term is never smaller than what results from the distance between primes. In other words, this would have to be an inductive proof, showing an initial case and, as a result of that initial case and the fact that the gap is $O(\sqrt{p})$ for that case, all future cases must therefore be $O(\sqrt{p} \log{p})$. I hate to add to my question once again, but please tell me if this is completely off.


1 Answer 1


The Riemann hypothesis (RH) implies that $p_{k+1}-p_k=O(\sqrt{p_k}\log p_k)$, which was shown by Cramer in $1919$. However, this corollary is much weaker than RH. A proof of Legendre's conjecture would imply that $p_{k+1}-p_k=O(\sqrt{p_k})$, which is indeed better than Cramer's result. But this does not necessarily mean that it implies RH. It only means that Legendre is better than a consequence of RH. In fact, it is conjectured that the gap $p_{k+1}-p_k$ is even better than $O(\sqrt{p_k})$, i.e., $O(\log^2 p_k)$ which is much smaller, and that between $n^2$ and $(n+1)^2$ there lies not only one prime but quite a lot of primes.

  • 2
    $\begingroup$ Good answer; along the same lines, would showing that $p_{k+1} - p_k = O(\log^2{p_k})$ prove the Riemann hypothesis? In other words, is it possible to prove the Riemann hypothesis by finding any upper bound on the distance between consecutive primes? $\endgroup$
    – Adam
    Commented Sep 3, 2013 at 13:54
  • 2
    $\begingroup$ No, I do not think that a proof of $p_{k+1}-p_k=O(\log^2 p_k)$ would give a proof of RH, because the relation between RH and the gaps is not sufficiently strong. $\endgroup$ Commented Sep 3, 2013 at 14:36
  • 3
    $\begingroup$ I have since read that the Riemann hypothesis has been proven to be equivalent to stating that the absolute value of the difference between the pi function and the logarithmic integral is smaller than $c(\sqrt{p} \log{p})$ for some constant $c$. When I read "equivalent", my immediate conclusion is that proving one proves the other, both ways. Is this not the case? Is there anything about the distribution of the primes that, if proven, would prove the Riemann Hypothesis? $\endgroup$
    – Adam
    Commented Sep 5, 2013 at 6:03
  • 2
    $\begingroup$ Okay, so the two problems are not the same: showing the prime gap is asymptotic to something is not the same as showing the error term on the prime number theorem (using the logarithmic integral) is asymptotic to root x log x. They are two different problems. Thanks for the help Dietrich, this has pointed me in the right direction. $\endgroup$
    – Adam
    Commented Sep 5, 2013 at 6:48
  • 1
    $\begingroup$ @user477343 No, for the same reason. $\endgroup$
    – Charles
    Commented Sep 21, 2018 at 12:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .