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)$.

  • 2
    $\begingroup$ 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)$. $\endgroup$ – EFinat-S Apr 19 '19 at 15:52
  • 1
    $\begingroup$ (..and please stop editing your question). $\endgroup$ – EFinat-S Apr 19 '19 at 15:53
  • 1
    $\begingroup$ There is also a proof in Landau's Handuch, $\S15$. $\endgroup$ – 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.

| cite | improve this answer | |
  • 5
    $\begingroup$ So, Euler would have known the answer if he asked the question, but did he actually make this connection? $\endgroup$ – Emil Jeřábek Apr 19 '19 at 16:17
  • 5
    $\begingroup$ @EmilJeřábek Apparentely it was Legendre. See his "Essai sur la théorie des nombres" (1808 edition) p.394. He cites Euler. $\endgroup$ – EFinat-S Apr 19 '19 at 18:08
  • 1
    $\begingroup$ @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. $\endgroup$ – Adam P. Goucher Apr 19 '19 at 20:36

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.