Cute Proofs: Topological Proof of the Infinitude of Primes.

January 29, 2011

On my website (linked from somewhere here) I asked the question, "I want a more topological proof of the infinitude of primes."  A peer of mine (I don’t know if he wants his name on this blog) took one look at my site in passing and as soon as he got to that part, he looked over to me without missing a beat and noted not only that he knew of such a proof — but he knew exactly where the book which had it was in the library.  More impressive: this student is not even studying things related to topology!

The proof is from the book Proofs from THE BOOK by Aigner and Ziegler, which is a great book to read over, so I will not reproduce it exactly here.  What I will do is try to explain it a little slower than they do.  Let’s state exactly what we’re proving.

Theorem.  There are an infinite number of primes in ${\mathbb N}$.

As with a number of topological proofs of algebraic things, we’re going to give a weird topology to a usual set.  We’re going to use the set of integers, ${\mathbb Z}$ in this case, and our topology on this set is going to be to be as follows:

For $a,b\in {\mathbb Z}$ with $b > 0$, we define the set

$N_{a,b} = \{a + nb \, |\, n\in {\mathbb Z}\}$.

Now, what is in this set?  Let’s take a few examples to get the feel.

$N_{0,1} = \{\dots -2, -1, 0, 1, 2, \dots\}$

$N_{1,1} = \{\dots -1, 0, 1, 2, 3, \dots\}$

$N_{2,1} = \{\dots 0, 1, 2, 3, 4, \dots\}$

So, okay, these are all the same set.  Let’s try a different value of $b$.

$N_{0,2} = \{\dots -4, -2, 0, 2, 4, \dots\}$

$N_{1,2} = \{\dots -3, -1, 1, 3, 5, \dots\}$

$N_{2,2} = \{\dots -2, 0, 2, 4, 6, \dots\}$

So this time, we’ve partitioned the set of integers into two different sets; the evens and the odds.  Or, the multiples of 2, and then the multiples of 2 shifted "up" by one.

The same sort of thing will happen for all of these sets.  $N_{a,b}$ will partition the set of integers into multiples of $b$ and translate the values over $a$ units.  Okay?  Okay.

Now, we need to define the open sets in this topology.  No, those were not it.  But we will use them!  Let’s call a set $U$ open if either $U$ is empty or for every $a\in U$ there is some $b > 0$ such that $N_{a,b}$ is in $U$

Clearly, the whole space is open.  Every $N_{a,b}$ is open.  What about the set

$\{\dots -7, -6, -4, -3, -1, 0, 2, 3, 5, 6 \dots\}$?

Notice that the sequence $\{\dots -6, -3, 0, 3, 6\dots\}$ is in there, so that’s $N_{3n,3}$ for any $n$.  Similarly, the sequence $\{\dots -7, -4, -1, 2, 5,\dots\}$ is just $N_{3n+1, 3}$ for any $n$.  So, we have that this set is open.  And you can sort of see that it’s the union of two pieces of this partition into 3rds of ${\mathbb Z}$

This brings us to another point: each set $N_{a,b}$ is also closed.  Can you see why?  If this divides ${\mathbb Z}$ into $b$ pieces, then just union together $b-1$ of them to get the remaining $b$-th piece, which will be of the form $N_{a,b}$

Alright.  Let’s sum up.  $N_{a,b}$ is open and closed.  Can we have a finite non-empty set which is open?  No, we cannot: prove this for yourself.  It’s easy to see that if $N_{a,b}$ is "inside" of it, then it must be infinite.  Thus, every non-empty open set is infinite.

Now, what about primes?  Well, think about any number besides $-1$ and $1$.  What do we know about it?  It has a prime decomposition!  This means that if some number $n = pd$ for some prime $p$ and some other number $d$ then $n\in N_{0,p}$.  Do you see why?  Expand out what $N_{0,p}$ is if you don’t see it right off.

Since every number besides $1$ and $-1$ has at least one prime divisor (yes, even 0), we conclude that every integer is in at least one set $N_{0,p}$, for some $p$.  This is the crucial point here.  This means, if ${\mathbb P}$ is the set of all primes:

$\displaystyle {\mathbb Z} - \{-1,1\} = \bigcup_{p\in {\mathbb P}}N_{0,p}$.

Okay?  Okay.  Now, what are we trying to prove?  The set of primes is infinite.  So suppose it’s finite.  What do we know about finite unions of closed sets?  This is also closed.  Thus, ${\mathbb Z} - \{-1,1\}$ is also closed.  Which means that $\{-1,1\}$ is open.

But.  We can’t have a finite open set.  Contradiction.  $\Box$

Let me just finish by noting that I’m not sure who this proof is due to, but it’s quite an elegant and surprising use of topology.  If we imagine open sets to be "things which are close to one-another" we get a nice visual interpretation of this theorem: there are always new things which are "not close" to everything that came before it, which is exactly the motivation in the usual proof: we construct a new number which must be prime since nothing before it divides into it.  So sweet.