Proposition: If p is the r^th prime, then there exists R such that for every r>R, the number of primes between p and its square p^2 is greater than r^2.

I have a proof for this, but am completely ignorant of how trivial/important the result it is. May someone please let me know if it's a well-known fact, and if so, what are some implications of it? Is there a better lower bound than r^2? It seems that for any positive number k, we can find large enough r so that the number of primes in the interval is greater than kr^2. Can this be proved?

  • $\begingroup$ I think it follows for large enough r from known facts about the error term in the prime number theorem. However, an independent proof would probably be interesting nevertheless. $\endgroup$ – zeb Jan 12 '12 at 0:32
  • $\begingroup$ Wont this follow from the Prime Number Theorem $\pi(n)\approx n/\ln(n)$? $\endgroup$ – Mahdi Majidi-Zolbanin Jan 12 '12 at 0:36
  • 2
    $\begingroup$ ... or even Čebyšev's elementary bound $c n / \log n < \pi(n) < C n / \log n$? $\endgroup$ – Noam D. Elkies Jan 12 '12 at 0:55
  • $\begingroup$ Adam, do you have a different proof? $\endgroup$ – Johan Wästlund Jan 14 '12 at 17:04

Let $r$ be sufficiently large (which you assume). It is known that the $r$-th prime has size at least $r \log r$. It is also known that the number of primes below $x$, $x$ large enough, is at least $x/\log x$.

So the number of primes below your $p^2$ is at least

\[\frac{(r \log r)^2}{ \log ( (r \log r)^2)} =\frac{(r \log r)^2}{ 2\log r + 2 \log \log r)}\ge \frac{r^2 \log r}{3} \ge 2 r^2 .\]

Since by definition $p$ is the $r$-th prime one has $2 r^2 - r \ge r^2$ in between.

To make the size condition explict and or sharpen the approach the results from Dusart's thesis will be useful.

Addition in view of the Edit. The argument above also yields a better bound of $(1/2 - \epsilon) r^2 \log r$. Using similar results in the converse direction one can get $(1/2 + \epsilon) r^2 \log r$ as upper bound. I guess also an ansymptotic equality but I did not really check. So you have an extra logarithmic factor, which also explains why, as said by Noam Elkies, not even the full strength of PNT is needed to get what you claim. As alluded to if you want to optimize this check the linked document for results. But to exclude those belowe $p$ is essentially irrelevant as the contribution is minimal.


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.