by Ian Stewart
11
Going for the Jugular
Dear Meg,
If you want to make a real name for yourself as a mountaineer, you have to conquer a peak that no one else has climbed. If you want to make a real name for yourself as a mathematician, there is no better way than to vanquish one of the subject’s long-standing unsolved problems. The Poincaré conjecture, the Riemann hypothesis, the Goldbach conjecture, the twin primes conjecture.
I don’t advise being that ambitious when you are working for a PhD! Big problems, like big mountains, are dangerous. You could spend three or four years doing extremely clever things, but fail to achieve your goal and end up with nothing. Math differs from the other sciences in this regard: if you carry out a series of chemistry experiments, you can always write up the results whether or not they confirm your thesis adviser’s theories. But in math, you normally can’t write a thesis saying, “Here’s how I tried to solve the problem, and here’s why it didn’t work.”
Even professionals have to treat big problems with considerable respect. Universities nowadays expect their faculty to be productive, and they tend to measure productivity in terms of publications per year. If you publish nothing for five years and then solve the Poincaré conjecture, you’ll be set for life, assuming you are allowed to keep your job while you are doing it. If you publish nothing for five years and then fail to solve the Poincaré conjecture, you’ll be out on your ear.
The sensible compromise is to spend some of your time working on a big problem and the rest working smaller, solvable, but still worthwhile problems. It would be wonderful to live in a world where it was possible to focus solely on the big issues, but we don’t. Nevertheless, a few brave souls have managed to find a way to do just that, and succeed. In their hands, the time-honored conjecture acquires a proof, and becomes a theorem.
In my last letter I told you that a proof is a story. It is often said that there are basically only seven plots for a novel, and the ancient Greeks knew them all. There seem to be relatively few narrative lines for mathematical proofs, too, but the ancient Greeks knew only one: the short, sweet, compellingly clever argument of Euclid’s that made QED a household word.
What, then, are we to make of mathematical proofs that are hundreds or even thousands of pages long? Or proofs that involve months of calculation on a big network of computers? More and more of these daunting beasts are coming into existence, usually as solutions to one of those big, open problems. Instead of the short, compelling story line known to the Greeks, these proofs are epics, or worse, long cycles of stories whose main thread may be submerged in intricate subplots for chapters at a time. What happened to Erd~s’s vision of the beauty of God’s mathematical creation? Are these mammoth proofs really necessary? Are they so vast only because mathematicians are too stupid to find the short, elegant versions written in The Book?
Wiles’s landmark proof of Fermat’s last theorem amounted to about one hundred pages of highly technical mathematics, prompting the science journalist John Horgan to write a provocative article titled “The Death of Proof.” Horgan assembled a variety of reasons why proofs were becoming obsolete, including the rise of the computer, the disappearance of proofs from school math, and the existence of blockbusters like Wiles’s. It was an interesting attempt to wrench defeat from the jaws of victory, to treat a historic achievement as bad news. Yes, we put a man on the moon, but look at all the valuable rocket fuel we had to use up.
Wiles’s proof may be a blockbuster, but it tells a ripping yarn. He had to use massive mathematical machinery for so simple a question, much as a physicist needs a particle accelerator many miles in circumference to study a quark. But far from being sloppy and unwieldy, his proof is rich and beautiful. Those hundred pages have a plot, a story line. An expert can skim through the details and follow the narrative, with its twists and turns of logic, and its strong element of suspense: will the hero overcome the last theorem in the final pages, or will the ghost of Fermat continue to taunt the mathematical profession? No one declared literature dead because War and Peace was rather long or because Finnegans Wake was not being read in schools. Professional mathematicians can handle a hundred pages of proof. Even ten thousand pages—the total length of the classification theorem for finite simple groups, combining the work of dozens of people over a decade or more—does not daunt them.
There is no reason to expect every short, simple, and true statement to have a short, simple proof. In fact, there is good reason to expect the opposite. Gödel also proved that in principle, some short statements sometimes require long proofs. But we can never know, in advance, which short statements these are.
Pierre de Fermat was born in 1601. His father sold leather; his mother was the daughter of a family of parliamentary lawyers. In 1648 he became a king’s councilor in the local parliament of Toulouse, where he served for the rest of his life, dying in 1665, just two days after concluding a legal case. He never held an academic position of any kind, but mathematics was his passion. The mathematical historian Bell called him “the Prince of amateurs,” but most of today’s professionals would be happy with half his ability. Though he worked in many fields of mathematics, Fermat’s most influential ideas were in number theory, a subject that grew out of the work of Diophantus of Alexandria, who flourished around AD 250 and wrote a book called Arithmetica. It was about what are now called Diophantine equations, equations that must be solved in whole numbers.
One problem to which Diophantus gave a completely general answer is that of finding “Pythagorean triangles”: two perfect squares whose sum is also a perfect square. Pythagoras’s theorem tells us that such triples are the lengths of sides of a right triangle. Examples are 32 + 42 = 52 and 52 + 122 = 132. Fermat owned a copy of Arithmetica, which inspired many of his investigations, and he used to write down his conclusions in the margin. Sometime around 1637 he must have been thinking about the Pythagorean equation, and he asked himself what happens if instead of squares you try cubes or higher powers, for instance, x4 + y4 = z4. But he couldn’t find any examples. In the margin of his copy of Arithmetica he made the most famous note in the history of mathematics: “To resolve a cube into the sum of two cubes, a fourth power into two fourth powers, or in general any power higher than the second into two of the same kind, is impossible; of which fact I have found a remarkable proof. The margin is too small to contain it.”
This statement has come to be known as his “last theorem,” because for many years it was the only assertion of his that his successors had neither proved nor disproved. Nobody could reconstruct Fermat’s “remarkable proof,” and it seemed increasingly doubtful that he had really found one. But if he had possessed a proof, even though it couldn’t fit in a margin, it would surely be concise and elegant enough to earn a place in God’s Book? No one was writing blockbuster proofs in the seventeenth century. Yet for three and a half centuries, mathematician after mathematician failed to find Fermat’s missing proof. Then, in the late 1980s, Wiles began an extended attack on the problem. He worked alone in the attic of his house, telling only a few select colleagues who were sworn to secrecy.
Wiles’s strategy, like that of many mathematicians before him, was to assume that a solution existed and then play with the numbers algebraically in the hope that this would lead to a contradiction. His starting point was an idea emanating from the German mathematician Gerhard Frey, who realized that you could construct a type of cubic equation known as an elliptic curve from the three numbers occurring in the purported solution of Fermat’s “impossible” equation. This was a brilliant idea, because mathematicians had been playing around with elliptic curves for more than a century and had developed plenty of ways of manipulating them. What’s more, mathematicians then realized that the elliptic curve made from Fermat’s roots would have such strange properties that it would contradict another conjecture—the so-called Taniyama–Shimura–Weil conjecture—that governs the behavior of such curves.
No one had ever
proved the Taniyama–Shimura–Weil conjecture, though most mathematicians thought it was probably right. If it were right, of course, the roots of Fermat’s equation would lead to a contradiction, showing that they could not exist. So Wiles took a deep breath and set about trying to prove the Taniyama–Shimura–Weil conjecture. For seven years, he brought every big gun of number theory to bear on it, until he eventually came up with a strategy that cracked it wide open. Although he worked alone, he didn’t invent the whole area by himself. He kept in close touch with all new developments on elliptic curves, and without a strong community of number theorists creating a steady stream of new techniques, he probably would not have succeeded. Even so, his contribution is massive, and it is propelling the subject into exciting new territory.
Wiles’s proof has now been published in full, and in print it comes to a bit over one hundred pages. Certainly too long to fit into a margin. Was it worth it?
Absolutely.
The machinery that Wiles developed to crack Fer-mat’s last theorem is opening up entire new areas of number theory. Agreed, the story he had to tell was lengthy, and only experts in the area could hope to understand it in any detail, but it makes no more sense to complain about that than it would to complain that in order to read Tolstoy in the original, you have to be able to understand Russian.
12
Blockbusters
Dear Meg,
No, I was not joking when I said that the classification of the finite simple groups runs to ten thousand pages. It is currently being simplified and reorganized, though. With luck and a following wind, it might shrink to only two thousand. Most of the proof was carried out by hand, and the ideas behind it were entirely the product of the human mind. But some key parts required computer assistance.
This is a growing trend, and it has led to a new kind of narrative style for proofs, the computer-assisted proof, which has come into existence only in the last thirty years or so. This is like the fast-food outlet that serves billions of dull, repetitive burgers: It does the job, but not prettily. There are often some clever ideas, but their role is to reduce the problem to a massive—but in principle routine—calculation. This is then entrusted to a computer, and if the computer says “yes,” the proof is complete.
An example of this kind of proof turned up recently in relation to the Kepler problem. In 1611 Johannes Kepler was considering how spheres can be packed together. He came to the conclusion that the most efficient method—the one that packs as many balls as possible into a given region—is the one that greengrocers often use to stack oranges. Make a flat layer in a honeycomb pattern, then stack another such layer on top, with the oranges sitting in the depressions of the first layer, and continue like this forever. This pattern shows up in lots of crystals, and physicists call it the face-centered cubic lattice.
It is often said that Kepler’s statement is “obvious,” but anyone who thinks so does not appreciate the subtleties. For example, it is not even clear that the most efficient arrangement includes a flat plane of spheres. Greengrocers start stacking on a flat surface, but you don’t have to. Even the two-dimensional version of the problem—showing that a honeycomb pattern is the most efficient way to pack equal circles in the plane— wasn’t proved until 1947, when László Fejes Tóth finally did it. His proof is too complicated to belong in The Book, but it’s all we have.
In 1998, Thomas Hales announced a computer-assisted proof of the Kepler conjecture that involved hundreds of pages of mathematics plus three gigabytes of supporting computer calculations. It has since been published in the Annals of Mathematics, the world’s premier math journal, with one important reservation: the referees state that they have not been able to check every single step in the computations.
Hales’s approach was to write down a list of all the possible ways to arrange suitable small clusters of spheres; then prove that whenever the cluster is not what you find in the face-centered cubic lattice, it can be “compressed” by rearranging the spheres. Conclusion: the only incompressible arrangement—the one that fills space most efficiently—is the conjectured one. This is how Tóth handled the two-dimensional case, and he needed to list about fifty possibilities. Hales had to deal with thousands, in three dimensions, and the computer had to verify an enormous list of inequalities—those three gigabytes of memory are what’s needed to tabulate them all.
One of the earliest proofs to use this brute-force computer method was the proof of the four color theorem. About a century ago Francis Guthrie asked whether every possible two-dimensional map containing any arrangement of countries can be colored using only four colors, so that neighboring countries always get different colors. It sounds simple, but the proof was highly elusive. Eventually, in 1976, Kenneth Appel and Wolfgang Haken proved the four color theorem. By trial and error and hand calculations, they first came up with a list of nearly two thousand configurations of “countries” and invoked the computer to prove that the list is “unavoidable,” meaning that every possible map must contain countries arranged in the same way as at least one configuration in the list.
The next step was to show that each of these configurations is “reducible.” That is, each configuration can be shrunk down until a part of it disappears, leaving a simpler map. Crucially, the shrinking must ensure that if the simpler map left behind can be colored with four colors, the original one can be as well. Now remember that every possible map must contain at least one of the two thousand configurations. So even the simpler map that you have just created by this process must have another configuration that can be shrunk again and so on. The upshot is that if you can find a way to shrink every possible configuration, you have your proof. Matching every configuration with a way to “shrink” it like this involved a huge but routine computer calculation, which in those days took about two thousand hours on the fastest available computer. (Nowadays it takes maybe an hour.) But in the end, Appel and Haken had their answer.
Computer-assisted proofs raise issues of taste, creativity, technique, and philosophy. Some philosophers feel that with their brute-force methods, they are not proofs in the traditional sense. Yet this kind of massive but routine exercise is what computers were invented to do. It’s what they’re good at, and it’s what humans are very poor at. If a computer and a human being both carry out a huge calculation and get different answers, the smart money is on the computer. But it must be said that any one bit of the proof, any one calculation by the computer, is usually trivial and extremely dull. It’s only when you string them together that they’re worth anything. If Wiles’s proof of Fermat’s last theorem is rich in ideas and form—like War and Peace—the computer proofs are more like telephone directories. In fact, for the Appel–Haken proof, and even more so Hales’s proof, life is—literally—too short to read the whole thing in full detail, let alone check it.
Still, these proofs are not devoid of elegance and insight. You have to be pretty clever about how you set up the problem for the computer to tackle. What’s more, once you know the conjecture is right, you can set about trying to find a more elegant way to prove it. This might sound strange, but it’s well known among mathematicians that it’s much easier to prove something you already know is true. In mathematical common rooms worldwide, you will occasionally hear someone suggest— only partly as a joke—that it might be a good idea to spread rumors that some important problem has been solved, in the hope that this might speed up its actual solution. It’s a bit like crossing the Atlantic. For Christopher Columbus this was desperately hard, but it was easier for John Cabot, sailing just five years later, because he knew what Columbus had found.
Does this mean that eventually mathematicians may find God’s proofs for Kepler and the four color theorem? Maybe, but maybe not. It’s a bit naive to imagine that every theorem that is simple to state must therefore have a simple proof. We all know that many tremendously difficult problems are deceptively easy to state: “land on the moon,” “cure cancer.” Why should math be different
?
Experts often get rather passionate about proofs, either that the best-known one can’t be simplified, or that alternative methods that someone is proposing can’t possibly work. Often they’re right, but sometimes their judgment can be affected by knowing too much. If you’re an experienced mountain climber proposing to scale a high peak, with glaciers and crevasses and the like, the “obvious” path may be exceedingly long and complicated.
It’s natural, too, to assume that the sheer cliff face, which seems to be the only alternative route, is simply unclimbable. But it may be possible to invent a helicopter that can swing you quickly and easily up to the top. The experts can see the crevasses and the cliff, but they may miss a good idea for the design of a helicopter. Occasionally someone invents such a piece of machinery out of the blue, and proves all the experts wrong.
On the other hand, think of Gödel. We know that some proofs simply have to be long, and perhaps the four color theorem and Fermat’s last theorem are examples. For the four color theorem, it is possible to do some back-of-the-envelope calculations that show that if you want to use the current approach—finding a list of “unavoidable” configurations and then eliminating them one at a time by some “shrinking” process—then nothing radically shorter is possible. But that, in effect, is just counting the likely crevasses. It doesn’t rule out a helicopter. So if these massive tomes are the best we can do, why did Fermat write what he did? Surely he can’t have stumbled across a hundred-page proof, including within it a proof of a conjecture about elliptic curves that hadn’t even been proposed yet, and scribbled down that it didn’t quite fit into the margin.