Quanta Magazine

April 26, 2023

Kristina Armitage/Quanta Magazine

Contributing Writer

April 26, 2023

The first proof that many people ever learn, early in high school, is the ancient Greek mathematician Euclid's proof that there are infinitely many prime numbers. It takes just a few lines and uses no concepts more complicated than integers and multiplication.

His proof relies on the fact that, if there were a finite number of primes, multiplying them all together and adding 1 would imply the existence of another prime number. This contradiction implies that the primes must be infinite.

Mathematicians have a curiously popular pastime: proving it over and over again.

Why bother to do this? For one thing, it's fun. More importantly, "I think the line between recreational math and serious math is very thin," said William Gasarch, a professor of computer science at the University of Maryland and author of a new proof posted online earlier this year.

Gasarch's proof is only the latest in a long succession of novel proofs. In 2018, Romeo Meštrović of the University of Montenegro compiled nearly 200 proofs of Euclid's theorem in a comprehensive historical survey. Indeed, the whole field of analytic number theory, which uses continuously varying quantities to study the integers, arguably originated in 1737, when the mathematical giant Leonhard Euler used the fact that the infinite series 1 + 1/2 + 1/3 + 1/4 + 1/5 + … diverges (meaning that it doesn't sum to a finite number), to again prove that there are an infinite number of primes.

Christian Elsholtz, a mathematician at Graz University of Technology in Austria and author of another recent proof, said that instead of proving hard results from many smaller results — what mathematicians do when they systematically assemble lemmas into theorems — he did the opposite. "I use Fermat's Last Theorem, which is really a nontrivial result. And then I conclude a very simple result." Working backward like this can reveal hidden connections between different areas of math, he said.

"There's a little competition out there for people to have the most ridiculously difficult proof," said Andrew Granville, a mathematician at the University of Montreal and author of two other proofs. "It has to be amusing. Doing something technically awful is not the point. The only way you want to do something difficult is that it's amusing."

Granville said that there is a serious point to this friendly one-upmanship. Researchers aren't just fed questions that they try to solve. "The creation process in mathematics is not about, you just set a task to a machine and the machine resolves it. It's about somebody taking what they’ve done in the past and using that to create a technique and create a way to develop ideas."

As Gasarch puts it, "All the papers, they segue from a cute new proof that primes are infinite into serious math. One day you’re just looking at primes, and the next day you are looking at densities of squares."

Get Quanta Magazine delivered to your inbox

William Gasarch, a professor at the University of Maryland, is the latest in a long line of mathematicians to come up with a new proof that the primes are infinite.

Evan Golub

Gasarch's proof begins with the fact that if you color the integers with a finite number of colors, there will always be a pair of numbers with the same color whose sum is also that color, which was proved in 1916 by Issai Schur. Gasarch used Schur's theorem to show that, if there were a finite number of primes, then there would exist a perfect cube (an integer, like 125, that is equal to some other integer multiplied by itself three times) that is the sum of two other perfect cubes. But back in 1770, Euler had proved no such cube exists — the n = 3 case of Fermat's Last Theorem, which posits that there are no integer solutions to an + bn = cn for n larger than 2. Based on that contradiction, Gasarch reasoned that there must be an infinite number of primes.

One of Granville's 2017 proofs used a different theorem of Fermat's. Granville mainly relied on a 1927 theorem by Bartel Leendert van der Waerden, which showed that if you color the integers with a finite number of colors, there always exist arbitrarily long chains of evenly spaced integers with the same color. Like Gasarch, Granville started with the assumption that primes are finite. He then used van der Waerden's theorem to find a sequence of four evenly spaced, identically colored perfect squares. But Fermat had proved that no such sequence can exist. Contradiction! Since such a sequence could exist were there a finite number of primes, but it can't exist, there must be an infinite number of primes. Granville's proof was the second recent prime proof to draw on van der Waerden's theorem — Levent Alpöge, now a postdoc at Harvard University, had also used the result in a 2015 paper, published while he was still in college.

Granville is a particular fan of Elsholtz's paper, which also applies Fermat's Last Theorem and the counterfactual assumption that there are only finitely many primes. Like Gasarch, Elsholtz incorporated Schur's theorem, though in a somewhat different way. Elsholtz also gave a second proof using a 1953 theorem by Klaus Roth, which says that sets of integers over a certain size must contain groups of three evenly spaced numbers.

Some deeper — and even practical — mathematical questions might be answered by building on this work. For example, public key encryption that relies on the difficulty of factoring large numbers would be very easy to break if we lived in a world with finitely many primes. Elsholtz wonders if there might therefore be some connection between the proofs of infinitely many primes and proving how hard it is to crack such encryption schemes. There is "some weak connection to Euclid's theorem," Elsholtz said. "It would be interesting to see the deeper connections."

Granville said the best math can grow from strange combinations of different areas and subjects and often emerges after mathematicians have spent years noodling over lower-level but amusing problems. He is fascinated by the fact that seemingly remote subjects could be applied to number theory. In a recent survey, Granville praised the "sparse elegance" of a 1955 proof by Hillel Furstenberg, which used point-set topology. Like Alpöge, Furstenberg was still in college when his proof was published. He would go on to an illustrious career in a variety of mathematical disciplines.

Granville rhetorically asked if new proofs of Euclid's old result are "just curiosity or something that has some long-term importance." Answering his own question, he said: "I can't tell you."

Contributing Writer

April 26, 2023

Get Quanta Magazine delivered to your inbox

Get highlights of the most important news delivered to your email inbox

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.