This post is entirely unrelated to what I’ve been talking about involving sheaves and ringed spaces. But I saw it today in class and thought it was so fitting with the name and purpose of this blog that I’d present it anyway, because I love it so much. It’s a proof that there are infinitely many prime numbers (due to Furstenberg) – but instead of Euclid’s more direct approach, it uses topology!

Let’s create a basis for a topology on \mathbb{Z}; for integers m, d with d > 0, denote by A(m,d) = \left\{ m + d n : n\in\mathbb{Z}\right\} the infinite arithmetic progression of all integers congruent to m modulo d. I claim that \mathcal{B} = \left\{ A(m,d) : m\in\mathbb{Z}, d\in\mathbb{N}\right\} is a basis for a topology on \mathbb{Z}. Firstly, note that we can write \mathbb{Z} = A(0,1), and we can agree that the empty set is equal to an empty union of arithmetic progressions. As we’re defining a basis our open sets are just unions of the A(m,d) so we don’t need to check anything here. But we do need to check whether intersections of two basic open sets A(m_1,d_1), A(m_2, d_2) can be expressed as unions of other basic opens of the form A(m,d).

Firstly, if A(m_1, d_1)\cap A(m_2, d_2) = \varnothing (i.e. d_1 = d_2 and m_1 \neq m_2) then we can vacuously write the intersection as an empty union, as agreed. So instead suppose A(m_1, d_1) and A(m_2, d_2) have nonempty intersection. Then without loss of generality we may assume they intersect at some point m. “Re-centering” each arithmetic progression on m (as they are only defined modulo their respective differences d_1 and d_2 anyway), we now need to compute A(m,d_1)\cap A(m,d_2). But it is not hard to see that this is just A(m,\text{lcm}(d_1, d_2)). But this is just another basic open set in \mathcal{B} – it’s not even a union of more than one open set! So the whole construction works very well – we can take arbitrary unions of these sets, take finite intersections, and we know that we can express the whole space \mathbb{Z} and the empty set in terms of the basic opens A(m,d). So we really have a basis for a topology on \mathbb{Z}, whose open sets consist of unions of infinite arithmetic progressions.

Now the sets A(m,d) are open, but they are also closed! To see this, note that A(m,d)^c = \bigcup_{m'\not\equiv m \pmod d} A(m',d) is just a union of all those d-1 arithmetic progressions of the same step-size d but shifted throughout the whole interval \left\{m+1, \dots, m+d-1\right\}. So the complement of a basic open set is a (finite, even) union of basic open sets, and thus is open too. Hence the basic open sets A(m,d) are both closed and open.

Now consider the union \bigcup_{p \text{ prime}} A(0,p). Since every integer except 1 and -1 is divisible by at least one prime (by the fundamental theorem of arithmetic), the above union gives \bigcup_{p \text{ prime}} A(0,p) = \mathbb{Z} \backslash \left\{1,-1\right\}. The complement of this set, namely \left\{1,-1\right\}, is finite – hence there is no way that it can be expressed as a union of arithmetic progressions of the form A(m,d), which are all infinite sets. But therefore as these are the basic open sets in the topology, the set \left\{1,-1\right\} is not open. Hence its complement, \mathbb{Z}\backslash \left\{1,-1\right\} =\bigcup_{p \text{ prime}} A(0,p), is not closed.

But \bigcup_{p \text{ prime}} A(0,p) is a union of closed sets (as I showed, each arithmetic progression is both open and closed). If this was a union of a finite number of closed sets – and therefore if it were indexed by finitely many primes p – then it would itself be closed, because in a topology finite unions of closed sets are always closed. And we definitely have a base for a topology, as shown above. Therefore, the union must involve an infinite number of closed sets A(0,p), indexed by infinitely many primes p. And therefore, there are infinitely many primes!!

Do you prefer Furstenberg’s topological proof or Euclid’s streamlined proof? The latter has the advantage that it’s a lot more direct, quicker, and probably seems like it’s more related to prime numbers. Furstenberg’s proof, on the other hand, takes a long time to set up and it feels very removed from anything to do with primes, using a lot more abstract machinery and a proof by contradiction, while Euclid’s proof is direct. However, the contradiction is very easy to understand, while many people (myself included, until I was wisely advised to the contrary) believe that Euclid’s proof uses a contradiction. I guess this subtlety in Euclid’s proof – depending on how it’s presented – can make it slightly confusing. The topological proof seems more simple in each individual step it takes, and for this reason I prefer it. But both proofs rest on the fundamental fact that every one of the infinitely many integers (except the units) are divisible by at least one prime.


Edit: This post has generated a lot of comments with great advice and helpful pointers, for which I’m really grateful! I have made several changes to the post accordingly.

Advertisements