This StackExchange question -- Is the $n$-th prime smaller than $n(\log n + \log\log n-1+\frac{\log\log n}{\log n})$? -- assumes the following statement: $$\log n + \log\log n -1 \leq \frac{p_n}{n} \leq \log n + \log\log n.$$ My question is: how can we prove that statement?

Using the version of the Prime Number Theorem that states $$\pi (n) \sim \frac{n}{\log n},$$ we can quite easily show that $$p_n \sim n\log n,$$ or in other words $$p_n = n\log n + o(n\log n),$$ but this doesn't seem to get us any closer to a big-O estimate of the kind assumed in the above question. Is there a standard, quick method of obtaining such an estimate?

  • 2
    $\begingroup$ These estimates are, according to Wikipedia [which provides references] ( en.m.wikipedia.org/wiki/Prime-counting_function ), 20-th century math, the lower bound being from 1999. I haven’t tried to look at the articles, but they’re likely to be quite technical. $\endgroup$ – Mindlack Jan 15 at 12:18
  • 1
    $\begingroup$ This is bases on the prime number theorem. Statements related to this theorem are usually not easy to derive. Even the "elementary proofs" of the prime number theorem are difficult and far from "elementary" in the sense of "simple" or "easy". Dusart established useful bounds, perhaps you google for papers of him. $\endgroup$ – Peter Jan 15 at 13:23
  • $\begingroup$ @SPS This does not answer OP's question which is on the explicit bound $$\log n + \log\log n -1 \leq \frac{p_n}{n} \leq \log n + \log\log n$$ $\endgroup$ – Nilotpal Kanti Sinha Feb 5 at 11:26

The question you are asking especially the lower limit was proved by Pierre Dusart using the first 3.5 million zeroes of the Riemann zeta function so don't expect an easy answer. Here is the full solution.

The $k$-th prime is greater than $k(\ln k + \ln \ln k − 1)$ for $k \ge 2$

  • $\begingroup$ I think the answer I've given (which I don't take credit for) provides an easier way. $\endgroup$ – SPS Feb 4 at 23:14
  • $\begingroup$ @SPS YOu answer is not correct in the sense that you have only shown that $$p_n = n\log n + n\log\log n + O(n)$$ where as the OP asked for the explicit inequality $$\log n + \log\log n -1 \leq \frac{p_n}{n} \leq \log n + \log\log n$$ and this cannot be proved form what you have provided untill you show how to cotrol the error in the $O$ term. Thats why you need the Riemann zeroes. Unfortunately, OP himself didn't realize this since he has accepted your answer. $\endgroup$ – Nilotpal Kanti Sinha Feb 5 at 11:22
  • $\begingroup$ Hi Nilotpal, actually I'm the OP, and I guess I phrased the question badly. The explicit estimate obviously implies the Big-Oh one I've found, and the question title asks for that Big-Oh estimate -- because that's all I needed. I was in error to ask for a proof of the explicit estimate in the body of the question. $\endgroup$ – SPS Feb 5 at 12:21
  • $\begingroup$ @SPS Ok that clarifies it ... $\endgroup$ – Nilotpal Kanti Sinha Feb 5 at 20:34

(Answering my own question because I was given the solution elsewhere.)

By a known result and simple logarithm laws we have

$$\begin{align} p_n &\sim n\log n \\ \log p_n &= \log n + \log \log n + o(1). \end{align}$$

We also know that $\pi (n) = \frac{n}{\log n} + O\left(\frac{n}{(\log n)^2}\right),$ and therefore $$n = \pi (p_n) = \frac{p_n}{\log p_n} + O\left(\frac{p_n}{(\log p_n)^2} \right).$$

Meanwhile $O\left(\frac{p_n}{(\log p_n)^2} \right)$ simplifies, using the little-o estimates above, to $O\left(\frac{n}{\log n} \right)$. Plugging this in gives $$n= \frac{p_n}{\log n +\log\log n + o(n)} +O\left(\frac{n}{\log n} \right),$$

and therefore, just by rearranging terms and cancellation, $$p_n = n\log n + n\log\log n + O(n).$$


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.