In Search of God’s Perfect Proofs
Martin Aigner, left, and Günter Ziegler at the Free University of Berlin.
Aubrey Wade for Quanta Magazine
Introduction
Paul Erdős, the famously eccentric, peripatetic and prolific 20th-century mathematician, was fond of the idea that God has a celestial volume containing the perfect proof of every mathematical theorem. “This one is from The Book,” he would declare when he wanted to bestow his highest praise on a beautiful proof.
Never mind that Erdős doubted God’s very existence. “You don’t have to believe in God, but you should believe in The Book,” Erdős explained to other mathematicians.
In 1994, during conversations with Erdős at the Oberwolfach Research Institute for Mathematics in Germany, the mathematician Martin Aigner came up with an idea: Why not actually try to make God’s Book — or at least an earthly shadow of it? Aigner enlisted fellow mathematician Günter Ziegler, and the two started collecting examples of exceptionally beautiful proofs, with enthusiastic contributions from Erdős himself. The resulting volume, Proofs From THE BOOK, was published in 1998, sadly too late for Erdős to see it — he had died about two years after the project commenced, at age 83.
“Many of the proofs trace directly back to him, or were initiated by his supreme insight in asking the right question or in making the right conjecture,” Aigner and Ziegler, who are now both professors at the Free University of Berlin, write in the preface.
The book, which has been called “a glimpse of mathematical heaven,” presents proofs of dozens of theorems from number theory, geometry, analysis, combinatorics and graph theory. Over the two decades since it first appeared, it has gone through five editions, each with new proofs added, and has been translated into 13 languages.
In January, Ziegler traveled to San Diego for the Joint Mathematics Meetings, where he received (on his and Aigner’s behalf) the 2018 Steele Prize for Mathematical Exposition. “The density of elegant ideas per page [in the book] is extraordinarily high,” the prize citation reads.
Quanta Magazine sat down with Ziegler at the meeting to discuss beautiful (and ugly) mathematics. The interview has been edited and condensed for clarity.
You’ve said that you and Martin Aigner have a similar sense of which proofs are worthy of inclusion in THE BOOK. What goes into your aesthetic?
We’ve always shied away from trying to define what is a perfect proof. And I think that’s not only shyness, but actually, there is no definition and no uniform criterion. Of course, there are all these components of a beautiful proof. It can’t be too long; it has to be clear; there has to be a special idea; it might connect things that usually one wouldn’t think of as having any connection.
For some theorems, there are different perfect proofs for different types of readers. I mean, what is a proof? A proof, in the end, is something that convinces the reader of things being true. And whether the proof is understandable and beautiful depends not only on the proof but also on the reader: What do you know? What do you like? What do you find obvious?
You noted in the fifth edition that mathematicians have come up with at least 196 different proofs of the “quadratic reciprocity” theorem (concerning which numbers in “clock” arithmetics are perfect squares) and nearly 100 proofs of the fundamental theorem of algebra (concerning solutions to polynomial equations). Why do you think mathematicians keep devising new proofs for certain theorems, when they already know the theorems are true?
These are things that are central in mathematics, so it’s important to understand them from many different angles. There are theorems that have several genuinely different proofs, and each proof tells you something different about the theorem and the structures. So, it’s really valuable to explore these proofs to understand how you can go beyond the original statement of the theorem.
An example comes to mind — which is not in our book but is very fundamental — Steinitz’s theorem for polyhedra. This says that if you have a planar graph (a network of vertices and edges in the plane) that stays connected if you remove one or two vertices, then there is a convex polyhedron that has exactly the same connectivity pattern. This is a theorem that has three entirely different types of proof — the “Steinitz-type” proof, the “rubber band” proof and the “circle packing” proof. And each of these three has variations.
Any of the Steinitz-type proofs will tell you not only that there is a polyhedron but also that there’s a polyhedron with integers for the coordinates of the vertices. And the circle packing proof tells you that there’s a polyhedron that has all its edges tangent to a sphere. You don’t get that from the Steinitz-type proof, or the other way around — the circle packing proof will not prove that you can do it with integer coordinates. So, having several proofs leads you to several ways to understand the situation beyond the original basic theorem.
You’ve mentioned the element of surprise as one feature you look for in a BOOK proof. And some great proofs do leave one wondering, “How did anyone ever come up with this?” But there are other proofs that have a feeling of inevitability.
I think it always depends on what you know and where you come from.
An example is László Lovász’s proof for the Kneser conjecture, which I think we put in the fourth edition. The Kneser conjecture was about a certain type of graph you can construct from the k-element subsets of an n-element set — you construct this graph where the k-element subsets are the vertices, and two k-element sets are connected by an edge if they don’t have any elements in common. And Kneser had asked, in 1955 or ’56, how many colors are required to color all the vertices if vertices that are connected must be different colors.
It’s rather easy to show that you can color this graph with n – k + 2 colors, but the problem was to show that fewer colors won’t do it. And so, it’s a graph coloring problem, but Lovász, in 1978, gave a proof that was a technical tour de force, that used a topological theorem, the Borsuk-Ulam theorem. And it was an amazing surprise — why should this topological tool prove a graph theoretic thing?
This turned into a whole industry of using topological tools to prove discrete mathematics theorems. And now it seems inevitable that you use these, and very natural and straightforward. It’s become routine, in a certain sense. But then, I think, it’s still valuable not to forget the original surprise.
Brevity is one of your other criteria for a BOOK proof. Could there be a hundred-page proof in God’s Book?
I think there could be, but no human will ever find it.
We have these results from logic that say that there are theorems that are true and that have a proof, but they don’t have a short proof. It’s a logic statement. And so, why shouldn’t there be a proof in God’s Book that goes over a hundred pages, and on each of these hundred pages, makes a brilliant new observation — and so, in that sense, it’s really a proof from The Book?
On the other hand, we are always happy if we manage to prove something with one surprising idea, and proofs with two surprising ideas are even more magical but still harder to find. So a proof that is a hundred pages long and has a hundred surprising ideas — how should a human ever find it?
But I don’t know how the experts judge Andrew Wiles’ proof of Fermat’s Last Theorem. This is a hundred pages, or many hundred pages, depending on how much number theory you assume when you start. And my understanding is that there are lots of beautiful observations and ideas in there. Perhaps Wiles’ proof, with a few simplifications, is God’s proof for Fermat’s Last Theorem.
But it’s not a proof for the readers of our book, because it’s just beyond the scope, both in technical difficulty and layers of theory. By definition, a proof that eats more than 10 pages cannot be a proof for our book. God — if he exists — has more patience.
Aubrey Wade for Quanta Magazine
Paul Erdős has been called a “priest of mathematics.” He traveled across the globe — often with no settled address — to spread the gospel of mathematics, so to speak. And he used these religious metaphors to talk about mathematical beauty.
Paul Erdős referred to his own lectures as “preaching.” But he was an atheist. He called God the “Supreme Fascist.” I think it was more important to him to be funny and to tell stories — he didn’t preach anything religious. So, this story of God and his book was part of his storytelling routine.
When you experience a beautiful proof, does it feel somehow spiritual?
It’s a powerful feeling. I remember these moments of beauty and excitement. And there’s a very powerful type of happiness that comes from it.
If I were a religious person, I would thank God for all this inspiration that I’m blessed to experience. As I’m not religious, for me, this God’s Book thing is a powerful story.
There’s a famous quote from the mathematician G. H. Hardy that says, “There is no permanent place in the world for ugly mathematics.” But ugly mathematics still has a role, right?
You know, the first step is to establish the theorem, so that you can say, “I worked hard. I got the proof. It’s 20 pages. It’s ugly. It’s lots of calculations, but it’s correct and it’s complete and I’m proud of it.”
If the result is interesting, then come the people who simplify it and put in extra ideas and make it more and more elegant and beautiful. And in the end you have, in some sense, the Book proof.
If you look at Lovász’s proof for the Kneser conjecture, people don’t read his paper anymore. It’s rather ugly, because Lovász didn’t know the topological tools at the time, so he had to reinvent a lot of things and put them together. And immediately after that, Imre Bárány had a second proof, which also used the Borsuk-Ulam theorem, and that was, I think, more elegant and more straightforward.
To do these short and surprising proofs, you need a lot of confidence. And one way to get the confidence is if you know the thing is true. If you know that something is true because so-and-so proved it, then you might also dare to say, “What would be the really nice and short and elegant way to establish this?” So, I think, in that sense, the ugly proofs have their role.
Aubrey Wade for Quanta Magazine
You’re currently preparing a sixth edition of Proofs From THE BOOK. Will there be more after that?
The third edition was perhaps the first time that we claimed that that’s it, that’s the final one. And, of course, we also claimed this in the preface of the fifth edition, but we’re currently working hard to finish the sixth edition.
When Martin Aigner talked to me about this plan to do the book, the idea was that this might be a nice project, and we’d get done with it, and that’s it. And with, I don’t know how you translate it into English, jugendlicher Leichtsinn — that’s sort of the foolery of someone being young — you think you can just do this book and then it’s done.
But it’s kept us busy from 1994 until now, with new editions and translations. Now Martin has retired, and I’ve just applied to be university president, and I think there will not be time and energy and opportunity to do more. The sixth edition will be the final one.
This article was reprinted on Wired.com.
