Furstenberg’s topological proof of the infinitude of primes

I just returned from a 10-day trip to India. It was my first visit there. I gave a talk at the ICM Satellite Conference: Various Aspects of Dynamical Systems. The conference was hosted by the Department of Mathematics at the M. S. University, Baroda, which is in Vadodara (formerly Baroda) in the Indian state of Gujarat. Unfortunately, I wasn’t able to go early to attend the ICM (International Congress of Mathematicians) in Hyderabad.

My talk was on some joint work with my friend and long-time collaborator, Jim Wiseman. There were a lot of good speakers at the conference (including Jim, who spoke about the research on which we’re currently working). The most well-known mathematician at the conference was Hillel Furstenberg. He treated us to an hour-long talk, a presentation of some open problems, and the valedictory address at the end of the conference. I also had the pleasure of eating one dinner with him and his wife.

So I thought I’d take a moment to share one of Furstenberg’s coolest (and shortest) proofs. He published a one-paragraph note in the May 1955 issue of the American Mathematical Monthly, entitled “On the Infinitude of Primes.” It is a topological proof that there are infinitely many primes. (Note: apologies to my readers who have not take a course in point-set topology.)

Theorem. There are infinitely many primes.

Suppose, for the sake of contradiction, that there are finitely many primes.

We create a topology for the integers ( ${\mathbf{Z}}$ ) by defining a basis, ${\mathcal{B}}$ . The basis consists of all arithmetic progressions. For example, the following sets are elements of ${\mathcal{B}}$ :

${\mathbf{Z}=\{\ldots,-1,0,1,2,3,4,\ldots\}}$ ,

${\{\ldots,-3,-1,1,3,5,\ldots\}}$ , and

${\{\ldots, 101, 151, 201, 251,\ldots\}}$ .

How do we know that ${\mathcal{B}}$ is a basis? We must check two things. First, it must cover ${\mathbf{Z}}$ , which it does. Second, if ${B_{1}}$ and ${B_{2}}$ are in ${\mathcal{B}}$ and ${n\in B_{1}\cap B_{2}}$ , then there must be an element ${B_{3}\in \mathcal{B}}$ such that ${x\in B_{3}\subset B_{1}\cap B_{2}}$ . Indeed, suppose ${a_{1}}$ and ${a_{2}}$ are the differences between successive terms in the sequences ${B_{1}}$ and ${B_{2}}$ , respectively. Let ${a}$ be the least common multiple of ${a_{1}}$ and ${a_{2}}$ . Then ${B_{3}=\{\ldots,n-a, n, n+a, n+2a,\ldots\}}$ is the required basis element.

Thus ${\mathcal{B}}$ generates a unique topology on ${\mathbf{Z}}$ . (Furstenberg points out that this topology happens to be normal and hence metrizable.)

Observe that every arithmetic progression is a closed set: the complement of each arithmetic progression is an open set since it is the union of (finitely many) arithmetic progressions, each having the same difference. For example,

${\{\ldots,1,5,9,\ldots\}^{c}=\{\ldots,2,6,20,\ldots\}\cup\{\ldots,3,7,11,\ldots\}\cup\{\ldots,4,8,12,\ldots\}}$ .

For each prime ${p}$ , let ${A_{p}=\{\ldots,-p,0,p,2p,3p,\ldots\}}$ and let ${A=\bigcup A_{p}}$ . We assumed that there are finitely many primes, so ${A}$ is the union of finitely many closed sets. Thus ${A}$ is closed and its complement ${A^{c}}$ is open.

However, ${A^{c}=\{-1,1\}}$ , which is clearly not open (every open set is either empty or infinite). This is a contradiction. So there are infinitely many primes.

[Update: here’s a reworked version of Furstenberg’s proof that avoids all topological language.]

3 Comments

Cathy says:

September 9, 2010 at 2:11 am

Yes, it is a very cute proof. I think there is something similar in the first chapter of Martin Aigner’s Proofs from the Book.
Charlie says:

September 14, 2010 at 4:54 pm

Hi,

Just curious, but I don’t quite follow the proof – when I suppose I have the finite list of just ‘2’, I get as A the even numbers, and the complement the odd which if I follow is open and so I get no contradiction.

Similarly I can’t see how to get that the complement is {-1,1} without implicitly assuming an infinite number of primes – am I missing something (probably, only have 2nd year topology..)

Like the blog, keep up the good work!

Cheers,
Charlie
1. Dave Richeson says:
  
  September 14, 2010 at 5:06 pm
  
  Charlie,
  The first observation is that the complement of A is open—that by itself is not a contradiction. The “hidden assumption” (which I thought about stating explicitly when I wrote the post, but didn’t) is that every integer other than 1 and -1 is divisible by some prime. That’s why the complement of A is {-1,1}. That 2-element set is not open, and this is gives the contradiction.

Comments are closed.

Share this:

Like this:

Related

3 Comments