In our previous post, we gave three elementary number-theoretic proofs of the infinitude of the prime numbers. Today, in an unforgivably delayed second installment, we provide two proofs using machinery from more distant fields of mathematics: analysis and topology.

A small word of warning: today’s proofs, though not difficult, require a bit more mathematical sophistication than those of the previous post. The first proof will involve some manipulation of infinite sums, and the second proof uses rudiments of topology, which we introduced here.

Without further ado, let us begin. Our first proof today dates to the 18th century and is due to the prolific Leonhard Euler, of whom Pierre-Simon Laplace, an exceptional mathematician in his own right, once said, “Read Euler, read Euler, he is the master of us all.”

Proof Four (Euler): Suppose there are only finitely many prime numbers, \{p_1, p_2, \ldots, p_n\}. For each prime number p, consider the infinite series \sum_{i = 0}^\infty \frac{1}{p^i} = 1 + \frac{1}{p} + \frac{1}{p^2} + \ldots . As you probably learned in a precalculus class, the value of this infinite sum is precisely \frac{1}{1-\frac{1}{p}}.

Now recall that every natural number greater than 1 can be written in a unique way as a product of prime numbers. Since \{p_1, \ldots, p_n\} are all of the primes, this means that, for each natural number m \geq 1, we can express \frac{1}{m} as \frac{1}{p_1^{s_1}} \cdot \frac{1}{p_2^{s_2}} \cdot \ldots \cdot \frac{1}{p_n^{s_n}} for some natural numbers s_1, s_2, \ldots, s_n. Moreover, it is clear that this gives a one-to-one correspondence between natural numbers m \geq 1 and the corresponding n-tuples of natural numbers, \langle s_1, s_2, \ldots, s_n \rangle. Putting this all together, we obtain the following remarkable formula:

\sum_{m=1}^\infty \frac{1}{m} = \prod_{k=1}^n \frac{1}{1-\frac{1}{p_k}}.

The sum on the left hand of this equation is the famous harmonic series, and it is well-known and easily verified that this sum diverges to infinity. On the other hand, the product on the right hand is a finite product of finite numbers and is therefore finite! This gives a contradiction and concludes the proof.

Our next proof was published in 1955 by a young Hillel Furstenburg, who is still active at the Einstein Institute of Mathematics here in Jerusalem.

Proof Five (Furstenberg): For all integers a and b, let U_{a,b} be the set \{a + bk \mid k \in \mathbb{Z} \}, i.e., U_{a,b} contains a and all integers that differ from a by a multiple of b.

Claim: For all pairs of integers (a_0, b_0) and (a_1, b_1), either U_{a_0,b_0} \cap U_{a_1, b_1} = \emptyset or there are a_2, b_2 such that U_{a_0,b_0} \cap U_{a_1, b_1} = U_{a_2, b_2}.

Proof of Claim: If U_{a_0, b_0} \cap U_{a_1, b_1} \neq \emptyset, then let a_2 be any element of the intersection, and let b_2 be the least common multiple of b_0 and b_1. It is easily verified that U_{a_0,b_0} \cap U_{a_1, b_1} = U_{a_2, b_2}, thus finishing the proof of the claim.

It now follows that we can define a topology on \mathbb{Z} by declaring that a set U \subseteq \mathbb{Z} is open if and only if U = \emptyset or U is a union of sets of the form U_{a,b}. In particular, for each prime number p, the set U_{0,p}, which is the set of all multiples of p, is open. However, U_{0,p} is also closed, since it is the complement of the set \bigcup_{0 < a < p} U_{a,p}, which is an open set.

Now suppose that there are only finitely many prime numbers, \{p_1, \ldots, p_n\}. Since each set U_{0,p_k} is closed and a finite union of closed sets is closed, we have that \bigcup_{k = 1}^n U_{0,p_k} is a closed set. Notice that every integer that is not 1 or -1 is a multiple of some prime number, so \bigcup_{k = 1}^n U_{0,p_k} is precisely the set of all integers except 1 and -1. Since it is closed, its complement, which is \{-1,1\}, is open. But every non-empty open set is a union of sets of the form U_{a,b}, each of which is clearly infinite, so there can be no finite non-empty open sets. This is a contradiction and concludes the proof.

Cover Image: Passio Musicae by Eila Hiltunen, a monument to Jean Sibelius in Helsinki, Finland. Photograph by the author.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s