5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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$
    – efs
    Commented Apr 19, 2019 at 15:52
  • 1
    $\begingroup$ (..and please stop editing your question). $\endgroup$
    – efs
    Commented Apr 19, 2019 at 15:53
  • 1
    $\begingroup$ There is also a proof in Landau's Handuch, $\S15$. $\endgroup$
    – efs
    Commented Apr 19, 2019 at 18:03

1 Answer 1

Reset to default
4
$\begingroup$

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.

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

You must log in to answer this question.

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