legendre and riemann

[daniel tisdal]

I recall reading somewhere that Legendre's conjecture implies the Riemann Hypothesis. But the Wiki article suggests that Legendre imposes lighter bounds on the density of primes than does RH, so I would think the other way around, if anything. Thanks for any enlightenment.

[CRGreathouse]

They're of similar strength, but I don't believe either implies the other.

[daniel tisdal]

Thanks for the prompt reply. But if (say) RH entails a stronger boundary on the distance between primes, then wouldn't it imply Legendre? Or v.v.? There may be no formal relationship, but if, say, Proposition 1 implies a function is between (1,4) and Proposition 2 implies the function is on (1,8), we could safely say that Proposition 1 implies the truth of Proposition 2 but not conversely. Right? Thanks again.

[CRGreathouse]

Thanks for the prompt reply. But if (say) RH entails a stronger boundary on the distance between primes, then wouldn't it imply Legendre? Or v.v.?

But they don't. The Legendre conjecture says something about gaps and very little about the number of primes up to x, while the RH says a great deal about the number of primes up to x and not quite so much about gaps.

The Legendre conjecture could be used to establish a lower bound of about sqrt(x) on pi(x), but this is far weaker than the RH. The RH can be used to prove an upper bound in the neighborhood of 2sqrt(x) log^2 x for the gap between primes, but this is off by something like a log^2 factor from what you'd need for Legendre.

[daniel tisdal]

According to the Wiki article, Legendre implies prime gaps of the order O(sqrt[p]), while RH implies the (weaker) boundary for prime gaps O(sqrt[p]log[p]). The cite is

http://en.wikipedia.org/wiki/Legendre's_conjecture

Cramer is said to have proved the weaker boundary for RH. They seem to be comparing apples and apples--prime gaps...?

[daniel tisdal]

I see you were more specific in the second paragraph. That answers the question, thanks.

[CRGreathouse]

The RH can be used to prove an upper bound in the neighborhood of 2sqrt(x) log^2 x for the gap between primes

According to the Wiki article, Legendre implies prime gaps of the order O(sqrt[p]), while RH implies the (weaker) boundary for prime gaps O(sqrt[p]log[p]).

I see that Cramér managed to beat my back-of-an-envelope by a factor of log p, at least according to the article you cite. You're right, though -- it's still not enough.