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

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?

• The ( Erdős ) proof involving $2n\choose n$ is the simplest known. – dodd Jan 17 at 16:54
• Let me mention the Eratosthenes–Legendre Sieve. It is less involved than Erdős' argument, but more involved than the answers given below. It tells us that the density of primes is O(1/log log x); it is explained e.g. in this blog post - jonismathnotes.blogspot.com/2014/09/… . – Ofir Gorodetsky Jan 17 at 19:25
• Mathematics: Percentage of primes among the natural numbers, Specifically, Pete L. Clark's answer gives a proof which basically shows that $\liminf\frac{\varphi(n)}n=0$. And the details are given in robjohn's answer. (The OP accepted my answer, but Pete L. Clark's answer is definitely better.) – Martin Sleziak Jan 17 at 21:25
• Just musing - does anyone prove the complement, i.e. that the density of nonprimes approaches 100% ? – Carl Witthoft Jan 18 at 13:28
• @Carl: it's the same. The density of composites is bounded from below by $1 - \prod_{p \le n} \left( 1 - \frac{1}{p} \right)$ where the product is over primes and then you take $n \to \infty$, but this is just $1$ minus the same density for primes. – Qiaochu Yuan Jan 19 at 8:39

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 $$\sum_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.

• Erdős and Selfridge investigated how many pairwise coprime integers can be given in an interval of length $k$. They say that "by Selberg's sieve we easily obtain that" the number is less than $(2+o(1))k/\log k$. They add that "it appears likely that" $2+o(1)$ can be improved to $1+o(1)$. See page 5 in users.renyi.hu/~p_erdos/1971-03.pdf – GH from MO Jan 17 at 18:39
• @GH from MO: this is, of course, open even for the primes, 50 years later. – Mark Lewko Jan 17 at 18:46

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.

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.

• If $\sum_p 1/p < \infty$ then one already has that the density of primes goes to zero by comparison with the harmonic series $\sum_n 1/n = \infty$. So one can give a self-contained proof by splitting into the two cases $\sum_p 1/p = \infty$, $\sum_p 1/p < \infty$ and treating the two cases separately. – Terry Tao Jan 17 at 17:04
• @dodd The argument is in two steps. The first is that $\sum_p 1/p=\infty$ implies $\prod_p (1-1/p)=0$. This step is general and would also apply to the natural numbers $n$. The second is to use the Chinese remainder theorem (and the sieve of Eratosthenes) to show that $\prod_p (1-1/p)=0$ implies that the primes have density zero. Here we use the fact, specific to the primes, that large primes are coprime to all small primes. – Terry Tao Jan 17 at 17:18
• @dodd Actually, the material implication is true (true implies true). The proof you have in mind is invalid, but that isn't the proof used here. Please reread all the discussion carefully. – Terry Tao Jan 17 at 17:25
• @dodd the implication $A\Rightarrow B$ is true whenever $A$ and $B$ are both true, and this is so. Note that we do not prove "if $\sum 1/n_k=\infty$ then $n_k$'s have zero density" for any sequence of positive integer numbers. Only for primes. It is bit counterintuitive (we deduce that are few primes from the fact that there are many primes), but it works. – Fedor Petrov Jan 17 at 17:26
• I would say $\prod(1-1/p)=0$ follows from $\prod_{p\leqslant n}(1-1/p)\leqslant 1/(1+1/2+\ldots+1/n)$, you do not need the detour via $\sum 1/p=\infty$. – Fedor Petrov Jan 17 at 17:27

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.

• I think, this goes back to Euler as a proof of the infinitude of primes. – Fedor Petrov Jan 17 at 19:29
• Thanks for your support! I agree that proving $\prod_p(1-1/p)=0$ via $\sum_p 1/p=\infty$ was a bit silly. I guess I was in "Erdős mode" when I wrote my response. For some reason Hardy-Wright (which was the first math book I purchased, and also the first one I read) contains Erdős's proof for $\sum_p 1/p=\infty$ instead of Euler's. The proof by Euler is arguably simpler, and leads to more precise bounds (and the whole idea of zeta functions). – GH from MO Jan 17 at 20:13

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.

• I guess this is the proof Kim talked about when he mention the binomial coefficients. – RaphaelB4 Jan 28 at 8:59
• Quite possibly... However, if the OP referred to the proof involving the middle binomial coefficient as "a bit involved", it is possible that he had in mind a somewhat different approach. – José Hdz. Stgo. Jan 28 at 10:18
• The original proof that Erdös gave of the ineq. in * appeared in 1932 and he did resort to the middle binomial coefficient $\binom{2n}{n}$ there (cf. users.renyi.hu/~p_erdos/1932-01.pdf). In the proof from THE BOOK of *, the binomial coefficient that is invoked is $\binom{2k+1}{k}$; this proof is cleaner (in my opinion) and, according to Erdös himself, it was found in 1939 independently and almost simultaneously by him and L. Kalmár (seven years after the apparition of Erdös' „Beweis eine Satzes von Tschebyschef")... – José Hdz. Stgo. Jan 28 at 10:20
• Verbatim from Ramanujan and I. $\displaystyle\prod_{p \le n} p \leq 4^{n-1}$. Proof. We use induction. Clearly it holds for $n=2$ and $n=3$ and we will prove that it holds for $n+1$ by assuming that it holds for all integers $\le n$. If $n+1$ is even, there is nothing to prove. Thus assume $n+1=2m+1$. Observe that $\binom{2m+1}{m}<4^m$ and that $\binom{2m+1}{m}$ is a multiple of all primes $p$ satisfying $m+2\le p \le 2m+1$. Now we evidently have $\displaystyle\prod_{p \le 2m+1} p\le \binom{2m+1}{m}\prod_{p \le m+1} p< 4^{2m}$ by the induction assumption. – Yaakov Baruch Jan 28 at 13:46
• If that is not a simple, beautiful, strong and exact answer to the question, I don't know what is! – Yaakov Baruch Jan 28 at 13:48