This is a much clearer restatement of an earlier question.

In section 1.8 of Hardy & Wright, An Introduction to the Theory of Numbers, it is proved that the function inverse to $ x ⁄ \log⁡ x$ is asymptotic to $x \log⁡ x$. “From this remark we infer,” they say, that:

(*) The prime number theorem, $\pi(x)\sim x⁄ \log ⁡x$ , is equivalent to the theorem $p_n \sim n \log ⁡n$, where $p_n$ denotes the $n^{\text{th}}$ prime.

That the theorems are equivalent is easy to prove by a different method, as in Apostol's Introduction to Analytic Number Theory, Theorem 4.5. But how does the equivalence follow from H & W’s “remark”? As they say in section 1.5, since $\pi(p_n ) = n$, “$\pi(x)$, as function of $x$, and $p_n$, as function of $n$, are inverse functions”; but the inverses of asymptotic functions are not usually themselves asymptotic to one another. Would someone please explain how H & W mean for us to deduce (*)?

  • $\begingroup$ You definitely need something more about the nature of the functions $y\log y$ and $\frac{x}{\log x}$ to prove it. $\endgroup$ – Thomas Andrews Mar 15 '13 at 15:57
  • $\begingroup$ @ThomasAndrews I think my new answer to the OP's other question should be applicable here. $\endgroup$ – Erick Wong Mar 15 '13 at 20:02
  • 1
    $\begingroup$ @ErickWong Yes, it is. There remains a mystery: at the outset of their book, after spelling out simpler arguments, why did H & W leave this one to the poor beginner? Did they have something else in mind? $\endgroup$ – Palafox Mar 15 '13 at 23:32
  • 1
    $\begingroup$ Note that, $\pi(p_n)=n$, and clearly $n\leq p_n$ , so that $\ln(n)\leq \ln(p_n)$ $$1=\lim_{n\to\infty}\frac{\pi(n)\ln(n)}{n}=\lim_{n\to\infty}\frac{n\ln(p_n)}{ p_{n} }=\lim_{n\to\infty}\frac{n\ln(n)}{p_n}\frac{\ln(p_n)}{\ln(n)}$$ $\endgroup$ – Ethan Mar 16 '13 at 4:38
  • $\begingroup$ @Ethan For that kind of argument see the proof of the theorem in Apostol cited above (or Landau's Handbuch der Lehre von der Verteilung der Primzahlen (1909), vol. 1, p. 214 -- visible at Google books). $\endgroup$ – Palafox Mar 16 '13 at 17:28

While I can't speak directly for Hardy and Wright, I think the following is a plausible explanation, based on a copy of the fourth edition of H&W. Just prior to claiming the equivalence of $\pi(x) \sim x/\log x$ and $p_n \sim n \log n$, they spell out the argument that the inverse function of $x/\log x$ is asymptotic to $x \log x$. For completeness, here is the brief argument, very mildly paraphrased:

If $y = x / \log x$ then $\log y = \log x - \log \log x$. Since $\log\log x = o(\log x)$ we have $\log y \sim \log x$ and thus $x = y \log x \sim y \log y$.

The point here is that this argument illustrates a "moral": the key observation is that once we establish that $x$ and $y$ are not too far apart (that is $\log x \sim \log y$) then we can justify shifting between them and that this allows us to (asymptotically) invert functions which do not have nice inverses. Imagine now $\pi(x)$ in the place of $y$, not in an exact copy of the above proof, but a modified version with this moral intact:

If $y \sim x / \log x$ then $\log y = \log x - \log \log x + o(1)$. Since $\log\log x = o(\log x)$ and $o(1) = o(\log x)$ we have $\log y \sim \log x$ and thus $x \sim y \log x \sim y \log y$.

This establishes Theorem 8 in a way that strongly echoes the preceding discussion (and without making any general claim of asymptotics of inverse functions). Likewise, the same argument goes through for $\asymp$ instead of $\sim$, with $O(1)$ replacing $o(1)$.

I do agree there is sloppiness in saying that this inference follows "from the remark" and not in a manner akin to the remark. It's also interesting that they take the trouble to write out a proof of Theorem 9 ($p_n \asymp n \log n$) from Theorem 7, but refer to Theorem 8 ($p_n \sim n \log n$) as a trivial consequence of Theorem 6 (the antecedent theorems in both cases being the corresponding estimate on $\pi(x)$). I'm inclined to chalk this up to human fallibility :).


If the authors assume the reader has had a course in analysis, I would say that their assumption of this to be straightforward is a fair one.

At integer $x$ there would be about $n=x/\log x$ [define $n = \lceil x/\log x\rceil$ and "about $n$" is $n(1 \pm o(1)]$ ] primes so $p_n$ would be $x(1\pm o(1))$ [by the Prime Number Theorem, otherwise there would be too many or too few primes by the integer $p_n$]. So $p_n$ is $x(1\pm o(1)) = (1\pm o(1))(\log x)(x/\log x) =(1\pm o(1))n \log x$.

I would then trust that the reader would be able to see that $\log x = (1+o(1)\log n$.

Nothing too slick here, just basic analysis.


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.