What's the simplest and/or shortest proof that $\lim_{x \to \infty} \frac{\pi(x)}{x} = 0$, where $\pi(x)$ is the prime counting function? I'm curious to see if there's a slick proof that is simpler and shorter than Chebyshev's proof that $\pi(x) \asymp \frac{x}{\log x} \ (x \to \infty)$. Of course, using the prime number theorem to prove it is cheating. In particular, can it be proved using a simple idea like the sieve of Eratosthenes?


1 Answer 1


Fix a positive integer $n$ and consider the canonical map $f:\Bbb N \rightarrow \Bbb Z / n \Bbb Z$.

It is clear that any prime number $p > n$ lies in the inverse image $f^{-1}((\Bbb Z/n\Bbb Z)^\times)$, which shows that $\limsup_{x\rightarrow\infty} \frac{\pi(x)}x \leq \frac{\phi(n)}n$, where $\phi(n)$ is the Euler totient function.

Taking $n$ to be the product of the first $k$ prime numbers, we are reduced to showing that $S = \prod_p (1 - \frac 1 p)$ is equal to $0$, where the product ranges over all prime numbers $p$.

But $S^{-1}$ is the sum of the harmonic series $\sum_{m \geq 1}\frac 1 m$, which is $\infty$. Therefore $S = 0$, finishing the proof.

The last steps could be written more rigorously, but here I emphasize on the idea.

  • $\begingroup$ I see how to make the last step rigorous, but I'm still thinking on how to make the limsup statement so. The upper natural density of the primes is at most $\phi(n)/n$ for any $n$? I wonder, can you do a similar analysis with the harmonic numbers? $\endgroup$ Oct 10, 2021 at 2:18
  • 3
    $\begingroup$ In rigorous terms: $\pi(x) \leq n + \lceil \frac x n\rceil\phi(n)$, as all prime numbers up to $x$ must be either $\leq n$ or prime to $n$. Now divide by $x$ and let $x$ tend to $\infty$. $\endgroup$
    – WhatsUp
    Oct 10, 2021 at 2:22
  • 1
    $\begingroup$ Beautiful! Thank you! I'll wait some time to accept your answer, just to see if there are other slick proofs out there. I think it's a good question, one that I've never seen addressed anywhere in the literature. $\endgroup$ Oct 10, 2021 at 2:24
  • $\begingroup$ Sure, I'd also be curious to see other creative answers. $\endgroup$
    – WhatsUp
    Oct 10, 2021 at 2:25
  • 2
    $\begingroup$ "Handbuch der Lehre von der Verteilung der Primzahlen" Landau showed $π(x)=o(x)$(In page 69) and some other related theorems to primes in case you are interested. $\endgroup$
    – RAHUL
    Oct 10, 2021 at 4:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .