64
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ The ( Erdős ) proof involving $2n\choose n$ is the simplest known. $\endgroup$
    – markvs
    Jan 17, 2021 at 16:54
  • 9
    $\begingroup$ 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/… . $\endgroup$ Jan 17, 2021 at 19:25
  • 2
    $\begingroup$ 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.) $\endgroup$ Jan 17, 2021 at 21:25
  • 1
    $\begingroup$ Just musing - does anyone prove the complement, i.e. that the density of nonprimes approaches 100% ? $\endgroup$ Jan 18, 2021 at 13:28
  • 2
    $\begingroup$ @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. $\endgroup$ Jan 19, 2021 at 8:39

6 Answers 6

66
$\begingroup$

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.

$\endgroup$
2
  • 5
    $\begingroup$ 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 $\endgroup$
    – GH from MO
    Jan 17, 2021 at 18:39
  • 3
    $\begingroup$ @GH from MO: this is, of course, open even for the primes, 50 years later. $\endgroup$
    – Mark Lewko
    Jan 17, 2021 at 18:46
30
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Might be worthwhile to mention that your Lemma is strong enough to recover $(\star)\, \pi(N)\ll N/\log \log N$, which was proved originally by Legendre using the Legendre--Eratosthenes sieve (and $\sum_{p \le x} 1/p \sim \log\log x$). Indeed, choosing $k=\log N/(2\log\log N)$ and using $H_k \sim \log k$ and $\mathrm{lcm}(1,…,k) \le k! \le k^k$ gives $(\star)$. $\endgroup$ Oct 17, 2022 at 22:24
20
$\begingroup$

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.

$\endgroup$
23
  • 11
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Jan 17, 2021 at 17:04
  • 4
    $\begingroup$ @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. $\endgroup$
    – Terry Tao
    Jan 17, 2021 at 17:18
  • 5
    $\begingroup$ @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. $\endgroup$
    – Terry Tao
    Jan 17, 2021 at 17:25
  • 5
    $\begingroup$ @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. $\endgroup$ Jan 17, 2021 at 17:26
  • 4
    $\begingroup$ 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$. $\endgroup$ Jan 17, 2021 at 17:27
20
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ I think, this goes back to Euler as a proof of the infinitude of primes. $\endgroup$ Jan 17, 2021 at 19:29
  • $\begingroup$ 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). $\endgroup$
    – GH from MO
    Jan 17, 2021 at 20:13
9
$\begingroup$

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.

$\endgroup$
12
  • 3
    $\begingroup$ I guess this is the proof Kim talked about when he mention the binomial coefficients. $\endgroup$
    – RaphaelB4
    Jan 28, 2021 at 8:59
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 28, 2021 at 10:18
  • 4
    $\begingroup$ 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")... $\endgroup$ Jan 28, 2021 at 10:20
  • 4
    $\begingroup$ 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. $\endgroup$ Jan 28, 2021 at 13:46
  • 4
    $\begingroup$ If that is not a simple, beautiful, strong and exact answer to the question, I don't know what is! $\endgroup$ Jan 28, 2021 at 13:48
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.