A Topological Proof of Euclid’s Theorem

The twelve-line topological proof of Euclid’s Theorem by Hillel Furstenberg.

Theorem (Euclid): There are infinitely many prime numbers.

Euclid’s proof of this result is a classic. It is often described as a proof by contradiction but, in fact, Euclid shows how, given a list of primes up to any point, we can find, by a finite process, another prime number; so, the proof is constructive.

In a recent article in Quanta Magazine, Anna Kramer (2023) wrote about why mathematicians continue to look for new proofs of results that are known to be true. One example she considered was Euclid’s Theorem on the infinitude of prime numbers. Hundreds of proofs of this theorem have been found, a most remarkable one being the 1955 proof by Hillel Furstenberg, which used point-set topology.

Unlike Euclid’s classical proof, Furstenberg’s proof is a proof by contradiction. The proof was published in 1955, when Furstenberg was still an undergraduate student at Yeshiva University in New York.

Furstenberg’s Proof

Furstenberg defines a topology ${\mathscr{O}}$ on the integers ${\mathbb{Z}}$ , the evenly spaced integer topology, using as a basis the (doubly infinite) arithmetic sequences

$\displaystyle S(a,b)=\{an+b\mid n\in\mathbb{Z} \} = a\mathbb{Z} + b \,.$

A subset ${U \subseteq \mathbb{Z}}$ is open if and only if it is a union of arithmetic sequences ${S(a, b)}$ for ${a \ne 0}$ , or is an empty set. It is clear that ${U}$ is open if and only if, for every ${x\in U}$ , there is some non-zero integer ${a}$ such that ${S(a, x) \subseteq U}$ .

The axioms for a topology are easily shown to hold for ${\mathscr{O}}$ :

By definition, ${\varnothing}$ is open. ${\mathbb {Z}}$ is equal to the sequence ${S(1,0)}$ , and so is open.
Any union of open sets is open: for any collection of open sets ${U_i}$ and ${x}$ in their union ${U}$ , any of the numbers ${a_i}$ for which ${S(a_i, x) \subseteq U_i}$ also shows that ${S(a_i, x) \subseteq U}$ .
The intersection of two open sets is open: let ${U_1}$ and ${U_2}$ be open sets and ${x \in U_1 \cap U_2}$ , with numbers ${a_1}$ and ${a_2}$ such that ${x\in S(a_1,x)\cap S(a_2,x)}$ . Let ${a}$ be the least common multiple of ${a_1}$ and ${a_2}$ . Then ${S(a, x) \subseteq S(a_i,x) \subseteq U_i}$ .

There are two key properties of the topology ${\mathscr{O}}$ that are used in the proof:

Every non-empty open set contains an infinite sequence; therefore, no non-empty finite set is open. Thus, the complement of any such set cannot be closed.
The basis sets ${S(a,b)}$ are both open and closed. They are open by definition, and we can write
$\displaystyle S(a,b) = \mathbb{Z} \setminus \bigcup_{n=1}^{a-1}S(a,b+n).$

so that ${S(a,b)}$ is the complement of an open set.

Now Furstenberg observes that the only integers that are not integer multiples of prime numbers are ${+1}$ and ${-1}$ . Therefore

$\displaystyle \bigcup_{p\,\mathrm{prime}} S(p,0) = \mathbb{Z} \setminus \{-1,+1\} \,. \ \ \ \ \ (1)$

Now the first property above — that the complement of a non-empty finite set cannot be closed — implies that the set ${\mathbb{Z} \setminus \{-1,+1\}}$ cannot be closed. By the second property, the sets ${S(p,0)}$ are closed. But, if there were only finitely many primes, the finite union ${\bigcup_p S(p,0)}$ of closed sets would also be closed. Then (1) would imply equality between a closed set (on the left) and a non-closed set (on the right). This contradiction forces us to the conclusion that there is an infinitude of prime numbers.

The argument above is essentially that presented by Furstenberg, and is similar to the proof given in the Wikipedia article “Furstenberg’s proof of the infinitude of primes.”

Discussion

Mercer (2009) gave a variation of Furstenberg’s proof that avoids topological language. This shows that the essential techniques used in the proof are arithmetical, and do not require any advanced topological ideas. However, Mercer’s proof lacks the directness of Furstenberg’s (although this is largely a matter of taste).

Hillel (aka Harry) Furstenberg (b. 1935).

Furstenberg was still in college when his proof was published. It is just twelve lines in length and has a property of elegance greatly valued by mathematicians. Of course, we must acknowledge that Euclid’s original proof was also remarkable for its elegance, and was constructive, whereas Furstenberg’s topological proof was by contradiction.

Furstenberg had a sparkling career, making contributions in several disciplines In 1955, he graduated from Yeshiva College having been awarded both a BA and an MSc. He had already published a number of papers with his Note on one type of indeterminate form (1953) and On the infinitude of primes (1955) both appearing in the American Mathematical Monthly.

Furstenberg studied at Princeton University for his doctorate, supervised by Salomon Bochner, and was awarded his doctorate in 1958. This thesis was published in 1960 as Stationary processes and prediction theory. Furstenberg worked as an Instructor at Massachusetts Institute of Technology, and at the Mathematics Department in the University of Minnesota, where he was a member of a group working on probability theory. In 1965, he was appointed Professor of Mathematics at the Hebrew University of Jerusalem. Furstenberg remained at the Hebrew University until his retirement in 2003.

Furstenberg won numerous awards for his mathematical work: the Israel Prize, an award made by the State of Israel and regarded as the state’s highest honour, in 1993 and, in the same year, the Harvey Prize, awarded annually by Technion in Haifa, for “ground-breaking work in ergodic theory and probability, Lie groups and topological dynamics.” In 2007, he won the Wolf Prize “for his profound contributions to ergodic theory, probability, topological dynamics, analysis on symmetric spaces and homogenous flows.”

Sources

${\bullet}$ Furstenberg, Harry Furstenberg, 1955: On the Infinitude of Primes. Amer. Math. Monthly, 62(5), pg. 353 (1 page).

${\bullet}$ Golomb, Solomon W., 1959: A Connected Topology for the Integers Amer. Math. Monthly, 66(8), pp. 663-665.

${\bullet}$ Anna Kramer, 2023: Why Mathematicians Re-Prove What They Already Know. Quanta Magazine.

${\bullet}$ Mercer, Idris D. (2009). On Furstenberg’s Proof of the Infinitude of Primes. Amer. Math. Monthly, 116(4), pp. 355 – 356.

${\bullet}$ MacTutor biography of Hillel Furstenberg.

${\bullet}$ Wikipedia article: Furstenberg’s proof of the infinitude of primes.

ThatsMaths