Proof and Beauty

Mathematical proofs used to be short and sweet: these days they read more like War and Peace or, worse, a phone directory. Is the elegant proof a lost art, asks Ian Stewart.

IT IS OFTEN said that there are only seven narrative lines for a novel, all known to the ancient Greeks. There seem to be even fewer ways to write a mathematical proof, and the ancient Greeks knew only one of these narrative lines. That was the short, sweet, compellingly clever kind of argument that made Euclid's reputation. No one ever asks why such proofs are necessary. You set out an interesting mathematical statement, prove that it's right by some brilliant, concise insight that occupies just a few lines of maths, and your reputation is made. Everyone exclaims at the elegance of the maths, the beauty of the mathematical world. Everyone now understands exactly why your statement is right. Everyone is happy.
Paul Erdös, the eccentric but brilliant mathematician who collaborated with more people than anyone else on the planet, thought the same way. He reckoned that up in heaven God had a book that contained all the best proofs. If Erdös was really impressed by a proof, he declared it to be "from The Book". In his view, the mathematician's job is to sneak a look over God's shoulder and pass on the beauty of His creation to the rest of His creatures. (See "Short and sweet".)
But now it seems that this simple, elegant approach is just one of a number of possible narrative lines for mathematical proofs. Take the proofs that have been hitting the headlines in the past year or two. Rather than the short, compelling story line known to the Greeks, these are blockbusters, running to hundreds or even thousands of pages. What happened to the beauty of God's creation? Are these mammoth proofs really necessary? And are they so vast only because mathematicians are being too stupid to find the really short, really clever versions written in The Book?
Well, one answer is that there's nothing to say that every short, simple and true statement should have a short, simple proof. In fact, there's good reason to believe the opposite. The Austrian-born mathematician Kurt Gödel proved in principle that short statements can sometimes require long proofs. He just didn't know which statements these were-and neither does anyone else. Many of the most significant proofs of the past few years have certainly been long and complicated. Take Fermat's last theorem, famously cracked in 1996 by British-born mathematician Andrew Wiles, working at Princeton University in New Jersey. To solve the problem, Wiles had to use massive mathematical machinery, battering the question into submission like a gnat beneath a steam hammer. But far from being boring and unnecessary, the resulting proof is rich and beautiful-not a short story, like the proofs in The Book, but a War and Peace.
The tale of how Fermat's theorem came into being bears retelling. In 1637, Pierre de Fermat, a French lawyer with more mathematical ability in his little fingernail than most of us have in our entire heads, made a fateful annotation in his personal copy of the Arithmetica of Diophantus. His note relates to Pythagoras's theorem that a2 + b2 = c2 for certain whole numbers a,b and c. There are plenty of different values of a,b and c for which this works fine. Each combination, in fact, makes up the sides of right-angled triangles, with c as the hypotenuse.
Fermat tried to do the same kind of thing with cubes or fourth powers, and couldn't find any examples. In other words, he couldn't find an equation of the form an + bn = cn, where a,b and c are any whole numbers at all, and n is a whole number bigger than 2. Did that mean that no such equation could possibly exist? In the margin of his book, Fermat wrote that he had found a marvellous proof that the Pythagorean relationship only worked for powers of 2, but added that "this margin is too small to contain it".

Secret strategy
Such a proof, even though it couldn't fit in a margin, would surely be concise and elegant enough to earn a place in God's aesthetic book wouldn't it? Yet for three and a half centuries mathematician after mathematician came a cropper trying to find it. Then, in the late 1980s, British mathematician Andrew Wiles at Princeton University in New Jersey 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 before him, was to assume that the equation with a, b, c and n existed, and then play with the numbers algebraically in the hope that they would lead him to a contradiction. His starting point was an idea emanating from, among others, Gerhard Frey of the University of Essen in Germany. Frey realised that you can construct a type of cubic equation known as an elliptic curve from the three roots a,b and c of Fermat's "impossible" equation. This was a brilliant idea, because mathematicians had been playing with elliptic curves for more than a century, and had developed plenty of ways of manipulating them. What's more, mathematicians then realised that the elliptic curve made from Fermat's roots would have such strange properties that it would contradict another conjecture- known as the Taniyama-Shimura-Weil conjecture-which governs the behaviour of such curves.

'Wiles's proof is over 100 pages long. Was it worth the effort? Absolutely. The machinery that he developed to crack Fermat's last theorem is extremely rich and beautiful'

The roots of Fermat's equation would contravene the Taniyama-Shimura-Weil conjecture, which means that proving the conjecture was right would show that the roots could not exist. So for seven years, Wiles brought every big gun of number theory to bear on the conjecture, until he 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 own contribution is massive, and it is propelling the subject into exciting new territory.
Wiles's proof has now been published in full. It is a little over 100 pages long-certainly too long to fit into a margin. Was it worth the effort? Absolutely. The machinery that Wiles developed to crack Fermat's last theorem is extremely rich and beautiful. His ideas are opening up whole new areas of number theory. Agreed, the story he had to tell was long, and only experts in the area can understand it in any detail. But it makes no more sense to complain about that than it would to complain that to read Tolstoy in the original you have to be able to understand Russian.
There is a third narrative style for proofs-one that has appeared only in the past 30 years or so. This is the computer-assisted proof, and it is like a 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 job is to reduce the problem to a massive, routine, calculation. This is then entrusted to a computer, and if the computer says "yes" then the proof is complete.

Pack 'em in
An example of this kind of proof turned up last year. In 1611, Johannes Kepler was considering the ways that spheres could be packed together. He came to the conclusion that the most efficient method-the one that packed as many balls as possible into a given region - was the one that greengrocers use to stack oranges. Make a flat layer in a honeycomb pattern, then stack another such layer on top, 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-centred cubic lattice.

'Johannes Kepler came to the conclusion that the most efficient method for packing spheres into a given region was the one that greengrocers use to stack oranges'

It is often said that Kepler's statement is "obvious", but anyone who thinks this way doesn't appreciate the subtleties. For example, it is not even clear that the most efficient arrangement includes a flat plane of spheres. Greengrocers start their stacking from a flat surface, but you don't have to start like that. Even the two-dimensional version of the problem, which shows that a honeycomb pattern is the most efficient way to pack equal circles in a plane, wasn't proved until 1947, by a Hungarian mathematician called Laszlo Fejes Tóth. About ten years ago Wu-Yi Hsiang from the University California at Berkeley announced a proof of the three-dimensional version, some 200 pages long, but gaps emerged in the proof and eventually other mathematicians refused to accept it. Last year, however, Thomas Hales from the University of Michigan in Ann Arbor announced a computer-assisted proof that involved hundreds of pages of mathematics plus a vast quantity of supporting computer calculations. It was initially published on his Web page, and is now undergoing peer review for in a mathematical journal.
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-entred cubic lattice it can be compressed by rearranging the spheres slightly. 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 50 possibilities. Hales had to deal with thousands, and the computer had to verify an enormous list of inequalities that took up 3 gigabytes of computer memory.
One of the earliest proofs to use this brute-force computer method was the proof of the four-colour theorem. Almost a century and a half ago, the British mathematician Francis Guthrie asked whether every possible two-dimensional map containing any arrangement of countries can be coloured using only four colours, with neighbouring countries always getting different colours. It sounds simple, but the proof turned out to be elusive. Eventually, in 1976, American mathematicians Kenneth Appel and Wolfgang Haken found it. By trial and error and hand calculations they first came up with a list of nearly 2000 configurations of countries. Then they enlisted 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, a part of each configuration can be shrunk down until it disappears, leaving a simpler map. Crucially, the shrinking must ensure that if the simpler map left behind can be coloured with four colours, the original one can be as well.
Now imagine the simplest possible map that would require five or more colours-the so-called "minimal criminal". Like all maps, this must contain at least one of the 2000 reducible configurations. Shrink this configuration and you obtain a map that is simpler than the minimal criminal, and must therefore be law-abiding, needing only four colours. But that means the minimal criminal would only need four colours too. The only way out of this contradiction is if no criminals exist.

MANY proofs do have all the characteristics they would need to appear in God's book - a brilliant incisive idea creating a short, snappy proof that you can digest at a single sitting like an exquisitely written short story. John Milnor from the State University of New York at Stony Brook is a virtuoso at such proofs. For example, he found an answer to a question first raised in the 1960s: can you hear the shape of a drum - that is, can you reconstruct the shape of an object from the pattern of its vibrations? In 1992, Milnor proved that the answer, in high dimensions at least, is no. He found two distinct 16-dimensional tori which give rise to the same vibrational pattern, and his entire proof occupies one short journal page.
Another example is the solution to the Seifert conjecture arrived at by Krystyna Kuperberg of Auburn University in Alabama. This concerns a mathematical object known as a 3-sphere, which sounds bizarre but is very familiar (and entirely unremarkable) to mathematicians. It is like the surface of an ordinary sphere, except that everything is beefed up by one dimension. In other words, it is the three-dimensional "hypersurface" of a hypersphere in four-dimensional space. Now imagine a fluid flowing through the 3-sphere in such a way that the paths followed by the fluid particles are smooth curves with no sharp corners. Several decades ago, Seifert asked whether every possible smooth flow like this would necessarily include either a fixed point where the speed of flow is zero, or a closed loop. His conjecture was that the answer is yes, and most mathematicians were convinced that he was right. The main evidence was negative: a lot of mathematicians had tried to find a smooth flow without fixed points and closed loops, but nobody had succeeded.
Kuperberg proved them wrong. The answer to Seifert's question is no. Her solution overcame what everyone considered to be the biggest obstacle-dealing with smoothness-with a brilliant trick in which she made the flow "eat its own tail", as a result of which smoothness ceased to be an issue. Armed with this key idea, any professional could reconstruct the entire proof from the half-page description of it published in New Scientist ("Hairy balls in higher dimensions", 13 November1993, p 18).

Actually, the process involves more general techniques than just shrinking regions, but you get the idea. Matching every configuration with a way to shrink it involved a huge computer calculation, which took about 2000 hours on the fastest computer then available, but nowadays takes maybe an hour. But at the end, Appel and Haken had their answer.
Computer-assisted proofs raise a number of problems: issues of taste, of creativity, of technique, and of philosophy. Some philosophers feel that the brute-force methods of computer proofs mean they are not actually proofs at all, in the traditional sense. Others point out that this kind of massive but routine exercise is what computers do very well, and human beings very badly. If a computer and a human being both carry out a huge calculation and get different answers, the smart money is on the computer.

'Some philosophers feel that the brute-force methods of computer proofs mean that they are not proofs at all'

Any one calculation by the computer is usually trivial and dull. It's only when you string them together that they are worth anything at all. 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. And who would ever want to read those? In fact, for the Appel-Haken and Hales proofs life is, quite literally, too short for anyone to read, let alone check them.
But the proofs are not devoid of elegance and insight. After all, you have to be 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 try to find a more elegant way to prove it. This might sound strange, but it is much easier to prove something you already know is right. In mathematical common rooms you will occasionally overhear conversations in which someone suggests -only partly as a joke-that it might be a good idea to spread rumours that some important problem has been solved, in the hope that this might make a proof easier for someone else to find. Does this mean that eventually mathematicians may find God's proofs for Kepler, Fermat and the rest? It would be wonderful if they did. But maybe they won't. Perhaps there are no proofs of those theorems in The Book. There is no reason why every theorem that is simple to state must have a simple proof. We all know that many other tremendously difficult problems are deceptively easy to state: "land on the Moon", "cure cancer". Why should maths be different?
Experts often get rather strong feelings about possible 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 are right, but sometimes their judgment can be affected by knowing too much. Think of a mountain. Zigzag paths up its slopes are the natural way to climb it, but if it's a high mountain, with glaciers and crevasses and the like, the "obvious" path maybe 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. Just occasionally, someone invents such a piece of machinery and proves all the experts wrong.

Shrink to fit
On the other hand, remember Gödel and his discovery that some proofs simply have to be long. Perhaps the four-colour theorem and Fermat's last theorem are examples of these. For the four-colour theorem, it is possible to do some back-of-the-envelope calculations which 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.
Which brings us back to Fermat's scribbled note. If these massive tomes are the best we can do, why did he write what he did? Surely he can't have stumbled across a 200-page proof, and jotted down that it didn't quite fit into the margin.

I have an alternative theory. Godfrey Hardy, a brilliant Cambridge mathematician, was definitely no atheist, but he was not conventionally religious either. Hardy was convinced God had it in for him. So whenever he travelled by boat-which he hated-he would send a telegram: "Have just proved Reimann hypothesis. No room to give details here." The Reimann hypothesis, which relates prime numbers to complex analysis, was, and still is, the most important unsolved problem in mathematics. Hardy was convinced God would not let the boat sink, because if that happened Hardy might be given posthumous credit for possibly having found the proof.
Perhaps Fermat had a similar idea. Or maybe he just wanted to be famous. If so, it certainly worked.





Chaos Quantum Logic Cosmos Conscious Belief Elect. Art Chem. Maths

New Scientist26 June 1999  File Info: Created 23/6/2002 Updated 15/12/2010   Page Address: