What is the simplest proof that the density of primes goes to zero?

Question

By density of primes, I mean the proportion of integers between $1$ and $x$ which are prime. The prime number theorem says that this is asymptotically $1/\log(x)$.

I want something much weaker, namely that the proportion just goes to zero, at whatever rate. And I want the easiest proof possible.

The simplest proof I know uses estimates involving the binomial coefficient $\binom{2n}{n}$, but the argument still feels a bit involved.

Does anyone know an even simpler proof that the density of primes goes to zero?

Answer 1

I'm summarising the discussion in GH from MO's answer as a separate answer for clarity.

The fact that the primes have (natural) density zero can be deduced from a (seemingly) more general statement:

Theorem Let $1 < n_1 < n_2 < \dots$ be a sequence of natural numbers that are pairwise coprime. Then this sequence has zero (natural) density.

Proof There are two cases, depending on whether the sum $\sum_{k=1}^\infty \frac{1}{n_k}$ diverges or not.

Case 1: $\sum_{k=1}^\infty \frac{1}{n_k} < \infty$. Then for any $\varepsilon>0$, the density of $n_k$ inside a dyadic block $[2^j,2^{j+1})$ must be less than $\varepsilon$ for all but finitely many $j$. From this one easily verifies that the $n_k$ have natural density zero.

Case 2: $\sum_{k=1}^\infty \frac{1}{n_k} = \infty$. Then $\prod_{k=1}^\infty (1-\frac{1}{n_k})=0$. Thus for any $\varepsilon > 0$, there exists a finite $K$ such that $\prod_{k=1}^K (1 - \frac{1}{n_k}) \leq \varepsilon$. On the other hand, by the Chinese remainder theorem and the pairwise coprimality hypothesis, the set of natural numbers coprime to all of $n_1,\dots,n_K$ has density at most $\prod_{k=1}^K (1 - \frac{1}{n_k}) \leq \varepsilon$. Since this set contains all but finitely many of the $n_j$ by hypothesis, the $n_j$ have zero natural density. $\Box$

Informally, the pairwise coprimality hypothesis produces a competition between the small values of $n_k$ and the large values of $n_k$; if there are too many small values then there can't be too many large values. In particular pairwise coprimality is incompatible with positive (upper) natural density. (If one tries to occupy any dyadic block $[2^j,2^{j+1})$ with $n_k$'s to density at least $\varepsilon$, this will thin out the set of possible candidates for (much) larger $n_k$ by a factor of approximately $1-\varepsilon$. So if enough dyadic blocks attain this density, the set of candidates will eventually have its density reduced to at most $\varepsilon$. So having a non-zero density in this sequence is in ultimately "self-defeating", and so one has no choice but to eventually concede the density to be zero.)

In the specific case that $n_k$ is the sequence of primes, one can skip Case 1 by supplying a separate proof of Euler's theorem $\sum_p \frac{1}{p} = \infty$ (or equivalently $\prod_p (1-\frac{1}{p}) = 0$). For instance one can use the Euler product identity $\prod_p (1-\frac{1}{p})^{-1} = \sum_n \frac{1}{n}$.

Remark This argument is completely ineffective as it does not provide any explicit decay rate on the density of the $n_k$ inside any fixed large interval $[1,x]$. However, effective bounds for this theorem can be obtained by other means. Indeed, by replacing each of the $n_k$ with an arbitrary prime factor we see that the number of $n_k$ in $[1,x]$ cannot exceed the number $\pi(x)$ of primes in $[1,x]$, and this bound is of course optimal.

Answer 2

Here is a very much self-contained version of the argument discussed in the posts by GH from MO and Terry Tao.

The claim immediately follows from $H_k:=1+1/2+\ldots+1/k\to \infty$ and the following

Lemma. For a positive integer $k$, and any positive integer $N$, we have $\pi(N)\leqslant N/H_k+k+\text{lcm}(1,\ldots,k)$.

Proof. Choose the maximal integer $M\leqslant N$ divisible by $\text{lcm}(1,\ldots,k)$. Let $p_1,\ldots,p_m$ be all the primes in the interval $[k+1,M]$. For each $j=1,\ldots,k$ partition the semiinterval $(0,M]$ onto $j$ equal semiintervals and choose a semiinterval $(r\cdot M/j,(r+1)\cdot M/j]$ which contains at least $m/j$ our primes $p_i$'s. For every such prime $p_i$ consider the number $jp_i-rM$. They all belong to $[1,M]$, are distinct, and their greatest common divisors with $\text{lcm}(1,\ldots,k)$ are equal to $j$. Thus we get at least $m+m/2+\ldots+m/k=mH_k$ mutually distinct integers in $[1,M]$ that yields $m\leqslant M/H_k\leqslant N/H_k$. Obviously $\pi(N)\leqslant m+k+(N-M)\leqslant m+k+\text{lcm}(1,\ldots,k)$, and we are done.

Answer 3

The proof by GH from MO is, of course, correct. As noted in the comment of Fedor Petrov, there is no need to pass to the series $\sum_p 1/p$ and it is easier to analyze the product $\prod_p (1-1/p)$ directly. Expanding its inverse as a geometric series gives $$\prod_{ p \; {\rm prime}} (1-1/p)^{-1}=\prod_{ p \; {\rm prime}}(1+1/p+1/p^2 + \ldots)=\sum_{n \ge 1} \frac{1}{n}=\infty$$ Since each integer $n \ge 1 $ has a unique expression as a product of prime powers. I think this argument goes back to Euler.

Answer 4

Using the Chinese Remainder Theorem, one can reduce the statement to $\prod_p(1-1/p)=0$, which in turn is equivalent to $\sum_p 1/p=\infty$. For the last statement a short (but clever) proof was given by Erdős (1938), see Theorem 19 and its proof in Hardy-Wright: An introduction to the theory of numbers.

Answer 5

In my opinion, the simplest way to establish that $$\lim_{n \to +\infty} \frac{\pi(n)}{n}=0$$ is via the elementary inequality

$$ \prod_{p \leq n} p \leq 4^{n-1} \qquad \mbox{(*)}$$

which holds for every $n \in \mathbb{Z}^{+}$.

In 1939, Erdös and Kalmár found a proof of this inequality "which comes out of THE BOOK" (cf. P. Erdös, Ramanujan and I. In: K. Alladi (ed.), Number Theory - Madras 1987. Lecture Notes in Mathematics, vol. 1395. Springer Verlag, p. 2.). Clearly enough, as an immediate consequence of the Erdös-Kalmár ineq. we have that

$$ \pi(n) < (2\log 4+1)\frac{n}{\log n}$$

for every integer $n>2$ and whence the result on the natural density of the primes.

Answer 6

Terry Tao's proof can be slightly reworked to give a little more — that $\mu^\ast(P) = 0$ for every arithmetic upper quasi-density $\mu^\ast$ on $\mathbb N$, where $P$ is the set of primes. And a refinement of the unnumbered theorem in Terry Tao's post is Theorem 1 in [R.C. Buck, The Measure Theoretic Approach to Density, Amer. J. Math. 68 (1946), No. 4, 560-580], whose proof is as simple as it could be. (To apply Buck's theorem, one has to know that the series of reciprocals of all primes is divergent, but this is in turn as easy to prove as the divergence of the harmonic series, see [J.A. Clarkson, On the series of prime reciprocals, Proc. Amer. Math. Soc. 17 (1966), 541]).

---

An arithmetic upper quasi-density (on $\mathbb N$) is a $[0,1]$-valued function $\mu^\ast$ defined on the whole power set of $\mathbb N$ such that, for all $X, Y \subseteq \mathbb N$ and $h, k \in \mathbb N^+$, the following hold:

1. $\mu^\ast(X) \le \mu^\ast(\mathbb N) = 1$.

2. $\mu^\ast(X \cup Y) \le \mu^\ast(X) + \mu^\ast(Y)$.

3. $\mu^\ast(k \cdot X + h) = k^{-1} \mu^\ast(X)$ , where $k \cdot X + h := \{kx + h \colon x \in X\}$.

An arithmetic upper density is then a $\subseteq$-monotonic arithmetic upper quasi-density; and an arithmetic [quasi-]density is the restriction $\mu$ of an arithmetic upper [quasi-]density $\mu^\ast$ to the family of all sets $X \subseteq \mathbb N$ such that $\mu^\ast(X) = 1 - \mu^\ast(\mathbb N \setminus X)$. We refer to such a restriction as the arithmetic [quasi-]density induced by $\mu^\ast$.

Examples of arithmetic upper densities are the upper asymptotic (or upper natural) density (link to Wiki.en), the upper Banach density (link to MathWorld), the upper logarithmic density (link to OEIS), the upper Pólya density, the upper analytic (or upper Dirichlet) density (link to OEIS), and the upper Buck density. The arithmetic density induced by the upper asymptotic density is the asymptotic density, that induced by the upper Banach density is the Banach density, etc.

All of this and a bit more is discussed in joint work with Paolo Leonetti, where arithmetic upper [quasi-]densities are just called upper [quasi-]densities. In particular, Corollary 3.4 in [Leonetti & T., On small sets of integers, Ramanujan J. 57 (2021), 275-289] has a proof of the statement from the first paragraph of this answer (that $\mu^\ast(P) = 0$ for every arithmetic upper quasi-density).