# What was the first elementary proof that $\pi(x)=o(x)$?

Denote by $$\pi(x)$$ the number of primes $$\leq x$$. I'm interested in knowing who came up with the first elementary proof that $$\pi(x)=o(x)$$.

I know that Chebyshev demonstrated elementarily before Hadamard and de la Vallee-Poussin the slightly stronger result that $$\pi(x)=O(x/\log x)$$.

• According to Hardy and Wright (sixth edition, p.498), the divergence of the product $\prod(1-p^{-1})$ was proved by Euler. They show in $\S 22.7$ that this implies that $\pi(x)=o(x)$. – EFinat-S Apr 19 '19 at 15:52
• (..and please stop editing your question). – EFinat-S Apr 19 '19 at 15:53
• There is also a proof in Landau's Handuch, $\S15$. – EFinat-S Apr 19 '19 at 18:03

Leonhard Euler knew that the infinite product:

$$\prod_{p \textrm{ prime}} \left(1 - \frac{1}{p} \right)^{-1} = \sum_{n=1}^{\infty} \frac{1}{n}$$

is divergent (and used this to prove the infinitude of primes), so would have also known that the product:

$$\prod_{p \textrm{ prime}} \left(1 - \frac{1}{p} \right)$$

tends to zero. In other words:

$$\lim_{n \rightarrow \infty} \prod_{p < n\textrm{ prime}} \left(1 - \frac{1}{p} \right) = 0$$

Observe that the product in the last expression is the density of integers which are coprime to the set $$\{ p < n \textrm{ such that } p \textrm{ is prime} \}$$; this trivially implies that primes have zero upper density.

• So, Euler would have known the answer if he asked the question, but did he actually make this connection? – Emil Jeřábek Apr 19 '19 at 16:17
• @EmilJeřábek Apparentely it was Legendre. See his "Essai sur la théorie des nombres" (1808 edition) p.394. He cites Euler. – EFinat-S Apr 19 '19 at 18:08
• @EmilJeřábek Excellent point. He couldn't have asked this question as stated, because little-O notation didn't exist at the time of Euler. The main issue rests on whether the idea of (upper) density existed. – Adam P. Goucher Apr 19 '19 at 20:36