# prime counting function $\pi(x)$ is $o(x)$

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?

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.

• 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? Oct 10, 2021 at 2:18
• 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$. Oct 10, 2021 at 2:22
• 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. Oct 10, 2021 at 2:24
• Sure, I'd also be curious to see other creative answers. Oct 10, 2021 at 2:25
• "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. Oct 10, 2021 at 4:20