Need help understanding Erdős' proof about divergence of $\sum\frac1p$
I'm looking at proofs from Proofs from the Book (Martin Aigner, Günter M. Ziegler). The proof I'm having trouble is the sixth proof of the infinitude of the primes they give (on page 5; although I'll be reconstructing it here). I'll be highlighting the areas I'm having trouble with. They set out to prove two things; namely, and letting $P$ be the set of all primes:
- $P$ is infinite.
- $\sum_{p \in P} {1 \over p}$ diverges.
They begin by assuming the sum in 2. is convergent and letting $P = \{p_1, p_2, ...\}$ The first problem comes up here. By assuming the given form for $P$, haven't they already assumed that it is infinite? Then, by assumption,
$$\sum_{i > k} {N \over p_i} < {N \over 2}, \ \ (N \in \mathbb{Z}^+). \tag{1}$$
They then define $p_1, p_2, ..., p_k$ to be the small primes, and $p_{k + 1}, p_{k + 2}, ...$ to be the large primes, and define $N_b$ to be the number of positive integers $n \leq N$ which are divisible by at least one of the big primes; and, similarly, $N_s$ the number of positive integers $n \leq N$ which only have small prime divisors. By definition, $N_b + N_s = N$, and the intended contradiction will hinge on showing $N_b + N_s < N$.
Note, since $\left \lfloor {N \over p_i} \right \rfloor$ gives the number of positive integers $n \leq N$ which are multiples of $p_i$,
$$N_b \leq \sum_{i > k} \left \lfloor {N \over p_i} \right \rfloor < {N \over 2}. \tag{2}$$
Then, they let $n = a_n b_n^2$, where $n \leq N$ such that it has only small prime divisors. Here $a_n$ is the square free part. Then, every $a_n$ is a product of different small primes. Assuming that by this it is simply meant that every factor of $a_n$ is distinct, they assert there are exactly $2^k$ different square free parts. Notice, also, $b_n \leq \sqrt{n} \leq \sqrt{N} \implies b_n \leq \sqrt{N}$, and as such,
$$N_s \leq 2^k \sqrt{N}. \tag{3}$$
Here, is the second problem for me. I can see intuitively how $(3)$ holds; but, I'm not really sure, and I'd like to see it through a more rigorous approach, and also, why it's relevant. I'm not really sure, and I'd like a more rigorous approach.
They conclude the proof by showing that, since $(2)$ holds for any $N$, $2^k \sqrt{N} \leq {N \over 2}$ holds for $N = 2^{2k + 2}$. This is the third area I'm having trouble. I'm not really sure why this is relevant and how the contradiction $N_s + N_b < N$ follows from it. Maybe I missed it, but I also didn't see a proof of the infinitude of primes here.
Finally, I have a question as well. Looking back, how could one have guessed that this approach will lead us to a proof of the two claims above? In other words, what's the insight behind taking this particular approach?
Thanks to all in advance!
Note: I wasn't really sure what tags relating to "Proofs" would be appropriate here, so I've only used tags concerning number theory and primes. Please feel free to tag away.
First Problem
Initially, no assumption is made about $P = \{p_1, p_2 \dots \}$ being finite or infinite. The aim of the proof is to show that $\sum_{p \in P} 1/p$ diverges. Once this is established, it follows immediately that $P$ is infinite, since otherwise, $\sum_{p \in P} 1/p$ would be a finite sum.
Second Problem
Every element $n \le N$ with only small prime divisors is of the form $a_nb_n^2$. The numer of distinct $a_n$ is given by the number of subsets of $\{p_1, \dots, p_k\}$ which is exactly $2^k$. The inequality, $b_n \le \sqrt{N}$ implies there are at most $\sqrt{N}$ distinct $b_n$. So putting the two together, we get
$$N_s \le (\text{# of choices of } a_n) \times (\text{# of choices of } b_n) \le 2^k\sqrt{N}$$
Third problem
By letting $N = 2^{2k + 2}$, we have the bound $N_s \le 2^k\sqrt{N} \le N/2$. Since $N_b < N/2$,
$$N_s + N_b < \frac{N}{2} + \frac{N}{2} = N$$
However, by construction $N_b + N_s = N$, and so we have reached a contradiction. Therefore, $\sum_{p \in P} 1/p$ must diverge.
The first issue is just notational. Just agree to stop the sums and so forth if you run out of primes. Assuming what you've given here is their notation I'll agree that they probably didn't write the proof in the most reasonable way.
For point (2), there are exactly $2^k$ squarefree numbers whose prime factors are $p_1, \ldots, p_k$, so there are at most $2^k$ squarefree numbers satisfying that condition AND which are less than some number $N$. And there are at most $\sqrt{N}$ numbers $b$ such that $b^2 < N$, so there are certainly at most $\sqrt{N}$ numbers $b$ satisfying that condition AND such that $b$ is only divisible by $p_1, \ldots, p_k$.
For the rest, just plug all your equations together to get the contradiction you described at the beginning.
As for the motivation, since numbers are made up of prime factors, it makes sense to see what we can learn about them by starting from prime factors and multiplying them out rather than vice versa. Of course the distributional information we get will usually just be inequalities, so we want to combine them with something that lets us get meaningful results out of inequalities -- in this case, something like the pigeonhole principle.
-
By writing $P = \{p_1, p_2, ...\}$, have they assumed the infinitude of primes
It is not specified whether this is an infinite or finite sequence. We often (and usually, for that matter) assume that $...$ means there are infinitely many items. But we could just as well assume that there are only finitely many terms, and they just don't know what number to give the last one. In particular, it does not impact the proof in any way to suppose instead that $P = \{p_1, p_2, \ldots, p_k\}$ for some unknown $k$, except to transform the proof into a proof by contradiction.
As a brief aside, I'd like to point out that Euclid's proof of the infinitude of primes was not by contradiction. Rather, given any finite set of primes, he produced another, showing that no finite set contains all the primes. This is slightly different than assuming there are finitely many primes and arriving at a contradiction. This same subtlety almost seems to be at work here - we don't assume there are finitely many or infinitely many - we just enumerate the sequence of primes as much as we can.
(Daniel McLaury just posted his answer, and he addresses this point just fine so I leave it to him)
The final contradiction they arrive at is by showing that $N_b + N_s < \frac{N}2 + \frac N2 = N$, which is a contradiction as $N_b + N_s = N$. Their estimates of $N_b$ and $N_s$ are just to get to this contradiction.
(1) The proof does not assume $P$ is infinite, an explicit upper bound is simply omitted.
(1*) To prove not one but two claims, we choose to prove something equivalent, and we rephrase the problem of proving them both as follows: "either the sum diverges hence primes are infinite, or else we may assume the sum converges and we arrive at a contradiction." It is necessary to set the stage this way so that we are proving something logically equivalent to "(1) and (2)," and the first case being trivial is an artifact of this reformulation.
(2) If $X\to Y$ is surjective then $|X|\ge|Y|$. We have a surjection
$$\overbrace{\{n\le N~{\rm sqrfree~only~divisible~by~small~primes}\}}^{\Large{\rm size~}S\,\le\, 2^k}\times\{1,2,\cdots,\lfloor \sqrt{N}\rfloor\}$$
$$\longrightarrow\underbrace{\{n\le N~{\rm only~divisible~by~small~primes}\}}_{\Large {\rm size}\,=\,N_s}:(s,x)\mapsto sx^2 $$
and hence $2^k\sqrt{N}\ge S \lfloor\sqrt{N}\rfloor\ge N_s$.
(3) Suppose $2^k\sqrt{N}\le \frac{N}{2}$ for some $N$ (choosing $N=2^{2k+2}$ works). Then
$$N=\underbrace{N_s}_{\le N/2}+\underbrace{N_b}_{<N/2}<\frac{N}{2}+\frac{N}{2}=N,$$
i.e. $N<N$, a contradiction.
(4) Instead of there being one overarching insight (other than "count a quantity in two ways that disagree"), the process behind this proof seems to be developed in a number of distinct stages, and each stage progresses to the next one by asking an isolated but natural question to which there are many possible answers but the right configuration of answers yields a complete proof. (Like choosing doors or turns in a maze.) This is very much dependent on guesswork, hindsight, and discarding routes that didn't seem to lead anywhere.