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 ; for integers with , denote by the infinite arithmetic progression of all integers congruent to modulo . I claim that is a basis for a topology on . Firstly, note that we can write , 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 so we don’t need to check anything here. But we do need to check whether intersections of two basic open sets can be expressed as unions of other basic opens of the form .

Firstly, if (i.e. and ) then we can vacuously write the intersection as an empty union, as agreed. So instead suppose and have nonempty intersection. Then without loss of generality we may assume they intersect at some point . “Re-centering” each arithmetic progression on (as they are only defined modulo their respective differences and anyway), we now need to compute . But it is not hard to see that this is just . But this is just another basic open set in – 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 and the empty set in terms of the basic opens . So we really have a basis for a topology on , whose open sets consist of unions of infinite arithmetic progressions.

Now the sets are open, but they are also closed! To see this, note that is just a union of all those arithmetic progressions of the same step-size but shifted throughout the whole interval . 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 are both closed and open.

Now consider the union . Since every integer except and is divisible by at least one prime (by the fundamental theorem of arithmetic), the above union gives . The complement of this set, namely , is finite – hence there is no way that it can be expressed as a union of arithmetic progressions of the form , which are all infinite sets. But therefore as these are the basic open sets in the topology, the set is not open. Hence its complement, , is not closed.

But 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 – 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 , indexed by infinitely many primes . 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.

Hey, I don’t have a lot to say about this entry in particular (or any of the others, really). However, I’m very happy to see you haven’t given up on this blog after the long silence! Just wanted to stop by to give you some encouragement 🙂 The topics you’re dealing with are at the very top of my pay-grade so I hope you won’t mind some stupid questions 😛

Like you, I’m also engaging in a long math blogging project (although mine is probably shorter than yours!) and I’m always looking to expand my support network and help other folks build theirs! Please reach out to me if you’d like an accountability partner or somesuch.

LikeLike

Hi Eric – thanks so much for your support with my blog! I hope to avoid another long blog silence now that I’ve come back after the summer holidays and there’s lots of maths to do 🙂 And of course I’d be happy to (attempt to) answer any questions on stuff I write, stupid or not.

I’ve had a look at your blog too (One Thousand Adventures In Mathematics, right?) and it looks really great. What’s your aim for it – is there a certain area you’re focusing on? I think keeping track of yours – and anyone else involved in a similar project you know of? – will help me to stick at mine too.

LikeLike

Hehe, great to hear, and looking forward to it!

I’m not sure I have an aim per se… just that, as I mentioned in the first post, I wanted to have a place where I regularly posted thoughts on math and the mathematical life. In practice it has primarily been notes on the Joint Meetings talks. Now that I’ve eaten through those notes, I haven’t really settled on a direction, but the content seems to keep flowing in anyway 😛 In seriousness, I think talk notes will always feature quite heavily, as well as those many-post-long explanations of basic things that I keep starting and not finishing XD

“Similar” might be a bit of a stretch, but mine was inspired by Alex Clark. He initially was doing a textbook challenge, but is now making a compilation of a different sort on his wiki at alexpclark.com. (You can pretend it is a blog if you follow the Recent Changes page XD)

LikeLike

I’ve been enjoying your blog for some time now! 🙂 I have two comments though:

1. You mentioned Euclid’s name, so I feel you should also say that this proof is due to Furstenberg (https://en.wikipedia.org/wiki/Furstenberg%27s_proof_of_the_infinitude_of_primes), especially given its celebrity.

2. Your comment about Furstenberg’s proof not being by contradiction is wrong. It *is* a contradiction proof, as shown by the second sentence in your second last paragraph. (Knowing that is a union of closed sets that is not closed, we then said “suppose it is a union of finitely many closed sets”, and then derived a contradiction.)

LikeLike

Also, it’s Euclid’s proof that’s not actually a proof by contradiction.

LikeLike

Thanks for the Furstenberg reference Josh – I wasn’t aware that he came up with this proof or even that it was well-known. I’ll make sure to put this in.And you’re right, I managed to muddle up both proofs w.r.t. contradictions. When I first saw Euclid’s proof it was presented as a contradiction (start with assuming there are only finitely many primes) but having looked it up I see that it’s supposed to prove the existence of another prime given *any* finite set of primes. I’ll edit the post accordingly.

LikeLike

Dear Alex, you shouldn’t call Euclid’s contradiction method silly: it will only affect YOUR reputation negatively. Also: this well known proof is not so topological nor different from Euclid’s than you think: http://math.stackexchange.com/a/93011/3217

LikeLike

Dear Attila, thanks very much for your comment – you’re absolutely right, and I’ve edited the post now to change this. To be honest if you’ve read the other comments on this post you might be able to tell I got myself quite confused about the logical structure of the two proofs, and Euclid’s one certainly isn’t silly. In fact I think although I liked the fact we could rephrase everything in topological terms Euclid’s one will still always be the benchmark because of its simplicity and flexibility e.g. to proving there are infinitely many primes of a certain shape.

Your MSE answer is also a good read, and I see that there has been much discussion of a similar nature in the comments!

LikeLike