Recently i took Algebra 1. Since my goal this September is to take cryptography as a complementary exam, Algebra 1 was not mandatory but strongly advised. Now, someone may ask: “Why showing a calculus result in an algebra class?”. That’s a fair question and let me answer by saying that my professor believed this is one of those result someone should see once in their lifetime. I believe it too. The proof i was shown is Erdös’s. I find the proof elegant and remarkably straightforward, so i wanted to share it with you.
Statement#
$$ \sum_{p\ \text{prime}} \frac{1}{p} = \infty $$Proof (by absurdity)#
Let \(p_1 < p_2 < \cdots \) enumerate the primes in increasing order.
Assume, for the sake of contradiction, that:
$$ \sum_{p\ \text{prime}} \frac{1}{p} < \infty $$By assuming that the above formula is true, then there exists an index k such that
$$ \sum_{i=k+1}^{\infty} \frac{1}{p_i} < \frac{1}{2} $$Fix this \( k \).
Now we arbitrary choose a natural number, \(l\) such that \( l > 1 \).
Let’s introduce the set:
\[ S_l = \left\{ n \in \mathbb{N} : 1 \leq n \leq l,\; n = p_1^{h_1} \cdots p_k^{h_k} \right\}. \]What is this set all about? \(S_l\) contains the natural numbers \(n \leq l\) whose prime factorization only uses the first \(k\) primes.
The following is proof’s heart. We want to find two upper bounds for these cardinalities:
- \[ |S_l| \]
- \[ |\{1, \cdots , l\}\setminus S_l| \]
Bound 1 - \(|S_l| \leq \sqrt{l}2^k \)#
Take an element which belongs to \(S_l\), call it x. We can write x as follow:
$$ x = p_1^{2s_1+r_1}\cdots p_k^{2s_k+r_k} = \left(p_1^{s_1}\cdots p_k^{s_k}\right)^2 \cdot \left(p_1^{r_1}\cdots p_k^{r_k}\right) = a^2 b. $$We called
$$ p_1^{2s_1} \cdots p_k^{2s_k} = a^2 $$and
$$ p_1^{r_1} \cdots p_k^{r_k} = b $$Therefore, \(x = a^2b\). We now observe that \(a^2 \in \{1,4,9,\ldots,m\}\), where \(m\) is the largest square less than or equal to \(l\).
So,
$$ a \in \{1, \cdots, \lfloor \sqrt{l} \rfloor \} $$We call this set X.
What can we say about b? Well, as for \(b\) it belongs to
$$ Y = \left\{ p_1^{r_1}\cdots p_k^{r_k} : r_i \in \{0,1\} \right\} $$Putting our results together:
$$ |S_l| \leq |X|\cdot|Y| \leq \sqrt{l}\cdot 2^k. $$Bound2 - \( \left | \{1, \ldots, l \} \setminus S_l \right| \leq \frac{l}{2} \)#
To find the second upper bound take \( y \in \{1, \dots, l\} \setminus S_l \). By definition of \(S_l\) \(y\) must be divisible by some prime greater than \(p_1, \dots, p_k\).
Consider now the following set:
$$ N_{il} := \{ n: 1 \leq n \leq l, \space divisible \space by \space p_i \} $$where \(i \ge k+1\).
I claim that
$$ \{1, \ldots, l\} \setminus S_l = \bigcup_{i=k+1}^{\infty} N_{il} $$NB: the sets \( N_{il} \) can overlap or even be empty.
I would like to spend a few words about \( \bigcup_{i=k+1}^{\infty} N_{il} \).
In
$$ \{1, \ldots, l\} \setminus S_l $$belongs those numbers less or equal to l which are divisible by some prime \(p_i\) with \(i >= k+1\): if i take one element that lives outside \(S_l\), i can place it in one of the sets
$$N_{il}$$that is being contained in \( \{1, \ldots, l\} \setminus S_l\)
Now we can write the following inequality:
$$ |\{1, \ldots, l\} \setminus S_l| = |\bigcup_{i=k+1}^{\infty} N_{il}| \leq \sum_{i=k+1}^{\infty}|N_{il}| $$Since the number of integers in \( N_{il} \) is at most \( l/p_i \) we get \( |N_{il}| \leq l/p_i \).
Therefore, \( |\{1, \ldots, l\} \setminus S_l| \leq \sum_{i=k+1}^{\infty}l/p_i = l\sum_{i=k+1}^{\infty}1/p_i \leq \frac{l}{2} \)
We found an upper bound to \( |\{1, \cdots, l\} \setminus S_l| \leq \frac{l}{2} \)
Ending the proof#
$$ l = |\{1, \ldots, l\}| = |S_l| + |\{1, \cdots, l\} \setminus S_l| \leq \sqrt{l}2^k + \frac{l}{2} $$In the end we obtain that for every \(l\):
$$ \frac{l}{2} \leq \sqrt{l}\cdot 2^k \quad \Longrightarrow \quad \sqrt{l} \leq 2^{k+1} \quad \Longrightarrow \quad l \leq 2^{2k+2}. $$\(k\) was fixed at the start, while \(l\) was arbitrary. Choosing \(l > 2^{2k+2}\) gives a contradiction.