I'm trying to follow the proof in Wikipedia that the PNT is equivalent to the assertion $\psi(x)\sim x$, by proving that $\psi(x)\sim\pi(x)\log x$, which it claims is a very simple proof. One direction of inequality is an actual bound, $\psi(x)\le\pi(x)\log x$, but the other inequality has a fuzz factor:

$$\psi(x) \ge \sum_{x^{1-\epsilon}\le p\le x} \log p\ge\sum_{x^{1-\epsilon}\le p\le x}(1-\epsilon)\log x=(1-\epsilon)(\pi(x)+O(x^{1-\epsilon}))\log x.$$

But this doesn't actually complete the proof, because we want $\psi(x)\ge(1-\epsilon)\pi(x)\log x$ without the fuzz factor. If we take large enough $x$ and use $\epsilon/2$ in the above equation we get

$$\psi(x)\ge(1-\epsilon/2)\pi(x)\log x+Ax^{1-\epsilon/2}\log x,$$ so it is sufficient to prove that $Ax^{1-\epsilon/2}\le\frac{\epsilon}2\pi(x)$ for sufficiently large $x$, i.e. $x^{1-\epsilon/2}\in o(\pi(x)),$ and although I am sure there is a proof of this, it's not so simple that the proof can be completely omitted, at least as far as I can see. Is there an easy proof to be found here? The only one I am seeing is Chebyshev's weak version of the PNT, $\frac x{\log x}\in O(\pi(x))$, which takes some significant work to prove.

  • $\begingroup$ IMO, the lower bounds are far more elegantly obtained by using $\frac{x}{(\log x)^k}$ as the cut-off point than with $x^{1-\epsilon}$. $\endgroup$ – Daniel Fischer Nov 25 '17 at 22:23
  • $\begingroup$ @DanielFischer Could you elaborate? It seems that this would only make the fuzz factor worse in the equation. $\endgroup$ – Mario Carneiro Nov 26 '17 at 2:35
  • $\begingroup$ $$\pi(x)\log x\leqslant \sum_{p \leqslant \frac{x}{(\log x)^2}} \log x+ \log x \sum_{\frac{x}{(\log x)^2} <p \leqslant x} \frac{\log p}{\log p}\leqslant \frac{x}{(\log x)^2}\log x+ \frac{\log x}{\log x - 2\log \log x} \sum \log p \leqslant \frac{x}{\log x} + \frac{1}{1 - 2\frac{\log \log x}{\log x}}\vartheta(x)$$ for $x \geqslant 3$, using the trivial $\pi(y) \leqslant y$ and $\vartheta(x)- \vartheta(y) \leqslant \vartheta(x)$, and $\log p > \log \frac{x}{(\log x)^2} = \log x - 2\log \log x$ for $p > \frac{x}{(\log x)^2}$. You get explicit bounds (which one could make sharper), no fuzz factor. $\endgroup$ – Daniel Fischer Nov 26 '17 at 14:15

You have: $$\psi(x)\geq (1-\varepsilon)\sum_{x^{1-\varepsilon}<p<x}\log x \geq (1-\varepsilon)(\pi(x)-\pi(x^{1-\varepsilon}))\log x$$ but, by the Chebyshev bound: $$\frac{\pi(x^{1-\varepsilon})}{\pi(x)}\leq\frac{1.11\frac{x^{1-\varepsilon}}{(1-\varepsilon)\log x}}{0.92\frac{x}{\log x}}\leq \frac{1.21}{1-\varepsilon}\, x^{-\varepsilon}\tag{1}$$ is enough to prove that: $$\psi(x)\geq (1-\tilde{\varepsilon})\,\pi(x)\log x.$$ To replace $(1)$ with something easier to prove than the Chebyshev bound, you can use $\pi(x^{1-\varepsilon})\leq x^{1-\varepsilon}$ and any suitable lower bound for $\pi(x)$.

  • $\begingroup$ And what are the "suitable lower bounds"? I think that's where I'm sticking. The wikipedia page doesn't mention a proof of the Chebyshev bound, do you know where I could find such? $\endgroup$ – Mario Carneiro Sep 18 '14 at 17:53
  • $\begingroup$ @MarioCarneiro: it is not necessary, but it is necessary to prove that the density of the primes in $[1,x]$ does not drop to zero too fast. Any bound like $\pi(x)\geq\frac{x}{(\log x)^{\eta}}$ for a positive $\eta$ does the job. $\endgroup$ – Jack D'Aurizio Sep 18 '14 at 17:54
  • 1
    $\begingroup$ For instance, it is not difficult to prove that $$\pi(x)\geq \frac{x}{\log^2 x}$$ with elementary sieve methods and the Buchstab identity. $\endgroup$ – Jack D'Aurizio Sep 18 '14 at 17:59
  • 2
    $\begingroup$ Update: This excellent answer was used as the basis for my Metamath formalization of this result. (FYI, I used the Chebyshev bound to get that last step.) $\endgroup$ – Mario Carneiro Oct 1 '14 at 3:41

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.