64

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?

Kim
  • 4,084

6 Answers6

66

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.

Terry Tao
  • 108,865
  • 31
  • 432
  • 517
  • 5
    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 https://users.renyi.hu/~p_erdos/1971-03.pdf – GH from MO Jan 17 '21 at 18:39
  • 3
    @GH from MO: this is, of course, open even for the primes, 50 years later. – Mark Lewko Jan 17 '21 at 18:46
30

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.

GH from MO
  • 98,751
Fedor Petrov
  • 102,548
  • 2
    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)$. – Ofir Gorodetsky Oct 17 '22 at 22:24
20

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.

GH from MO
  • 98,751
  • 11
    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 '21 at 17:04
  • This answer is wrong. The equality $\sum 1/p=\infty$ does not imply inequality $\pi(x)=o(x)$. – markvs Jan 17 '21 at 17:06
  • 2
    @dodd It does, using the Chinese remainder theorem to deduce that for any finite set $p_1,\dots, p_n$ of primes, the density of primes is at least $\prod_{i=1}^n (1-\frac{1}{p_i})$. – Will Sawin Jan 17 '21 at 17:08
  • 2
    @dodd this answer is correct, read it carefully – Fedor Petrov Jan 17 '21 at 17:09
  • Correction: one only gets zero logarithmic density (as opposed to zero natural density) of the primes with my version of the argument. – Terry Tao Jan 17 '21 at 17:09
  • 1
    @TerryTao I think, we get a genuine zero density. If $\pi(n)\geqslant 2\kappa\cdot n$ for a constant $\kappa>0$ and all $n$ from a certain infinite set $S$, then we may choose a subsequence $n_1<n_2<\ldots$ in $S$ such that $\pi(n_k)-\pi(n_{k-1})>\kappa n_k$ that implies $\sum_{n_{k-1}<p\leqslant n_k} 1/p>\kappa$, and totally $\sum 1/p=\infty$. – Fedor Petrov Jan 17 '21 at 17:11
  • 1
    @FedorPetrov: I have read it carefully. The answer is wrong. He claims that $\sum 1/p =\infty$ implies $\pi(x)=o(x)$. That is not true since $\sum 1/n=\infty$. Moreover $\sum n^2= \infty$. – markvs Jan 17 '21 at 17:12
  • @FedorPetrov Ah, of course, you're right (I am so used to a normalising factor like $1/\log x$ when summing reciprocals that I didn't notice that it is absent in this case!). – Terry Tao Jan 17 '21 at 17:16
  • 4
    @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 '21 at 17:18
  • 3
    In fact, what is really being proven here is that any sequence of mutually coprime natural numbers necessarily has zero natural density. – Terry Tao Jan 17 '21 at 17:20
  • @TerryTao: Thanks for your insightful and enlightening comments! – GH from MO Jan 17 '21 at 17:21
  • @TerryTao: So as a result of the two steps he "proves" that if $\sum_p 1/p=\infty$, then primes have zero density. That implication is wrong. – markvs Jan 17 '21 at 17:23
  • @WillSawin: By "at least" you meant "at most". – GH from MO Jan 17 '21 at 17:23
  • 5
    @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 '21 at 17:25
  • 5
    @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 '21 at 17:26
  • 4
    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 '21 at 17:27
  • 2
    @dodd: For any positive integer $n$, the density of integers coprime to $n$ exists and equals to $\phi(n)/n$. So the upper density of the primes is at most the infimum of $\phi(n)/n$ over all positive integers $n$. This infimum is precisely $\prod_p(1-1/p)$, which is zero by the upper bound $1-1/p<\exp(1/p)$ and $\sum 1/p=\infty$. – GH from MO Jan 17 '21 at 17:29
  • @dodd: At the end of my previous comment, I meant $\exp(-1/p)$ instead of $\exp(1/p)$. – GH from MO Jan 17 '21 at 17:52
  • @GHfromMO: assuming a version of this is correct, do you really think it is simpler than Erdos' proof? – markvs Jan 17 '21 at 18:19
  • @dodd: The proof is correct, as many of us tried to explain to you. Whether it is simpler than Erdős's proof of $\pi(x)\ll x/\log x$ is subjective. I would say it is not much simpler, but with Terry Tao's simplification (see his post), it is definitely simpler. – GH from MO Jan 17 '21 at 18:26
  • You are attempting a "proof by authority" and a "proof by majority". Next you will say that 97% of scientists consider the proof correct. The fact is that with all possible simpifications your "proof" if written completely is about 3 times longer than Edos' which the OP called "involved". – markvs Jan 17 '21 at 18:35
  • 2
    @dodd: Well, it is not clear why you think my proof is incorrect. I (and others) tried to argue with you, there was no authority involved. Majority, yes, but this happens with most correct proofs (majority agrees). I end the discussion here. (BTW my argument also relied, ultimately, on the work of Erdős.) – GH from MO Jan 17 '21 at 18:44
  • @FedorPetrov: I agree that proving $\prod_p(1-1/p)=0$ via $\sum_p 1/p=\infty$ was a bit silly. – GH from MO Jan 17 '21 at 20:08
20

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.

Yuval Peres
  • 13,995
  • 4
    I think, this goes back to Euler as a proof of the infinitude of primes. – Fedor Petrov Jan 17 '21 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 '21 at 20:13
9

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.

José Hdz. Stgo.
  • 8,732
  • 3
    I guess this is the proof Kim talked about when he mention the binomial coefficients. – RaphaelB4 Jan 28 '21 at 08:59
  • 3
    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 '21 at 10:18
  • 4
    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. https://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 '21 at 10:20
  • 4
    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 '21 at 13:46
  • 4
    If that is not a simple, beautiful, strong and exact answer to the question, I don't know what is! – Yaakov Baruch Jan 28 '21 at 13:48
  • 1
    Could you elaborate a bit more on "as an immediate consequence"? – Kim Feb 12 '21 at 21:18
  • 3
    Of course... By taking log of both sides of the ineq., we obtain $\sum_{p \leq n} \log p < n\log 4$; then, by shortening the range over which we are summing, we get $\sum_{\sqrt{n} < p \leq n} \log p < n \log 4$ and whence $(\log \sqrt{n})(\pi(n)-\pi(\sqrt{n}))< n \log 4$... – José Hdz. Stgo. Feb 12 '21 at 22:28
  • Btw, is this "the simplest proof" you had in mind as you were composing your post? – José Hdz. Stgo. Feb 12 '21 at 22:32
  • 2
    @JoséHdz.Stgo. It isn't exactly the same proof, as you set it up, but the basic ingredients do seem to smell the same. The proof I had in mind is in Baker's Comprehensive Introduction to Number Theory under the heading "Tchebyshev's estimates". But I think that name refers to the result; the actual argument feels like something from Erdos. Maybe that's why it smells the same. Same lion, same paw. – Kim Feb 13 '21 at 14:34
  • @JoséHdz.Stgo. Sorry, could you elaborate even more? From what you've already said I got the clumsy bound $\log \log n / \log n$ on the density, which is already enough to see it goes to zero. But I would like to know how you got the simpler bound above. – Kim Feb 13 '21 at 14:39
  • 3
    @JoséHdz.Stgo. I forgot to add that the starting point of the proof in Baker is not Erdos-Kalmar, though. – Kim Feb 13 '21 at 14:43
  • 1
    If you accept that $(\log \sqrt{n})(\pi (n) - \pi(\sqrt{n})) < n\log 4$, then $\pi(n)-\pi(\sqrt{n}) < (2n \log 4)/(\log n)$; thus, $\pi(n) < (2n\log 4)/(\log n)+\pi(\sqrt{n})<(2n \log 4)/(\log n) + (n/\log n)$ and we are done... – José Hdz. Stgo. Feb 13 '21 at 17:25
2

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

Salvo Tringali
  • 9,617
  • 2
  • 25
  • 56