 |
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.
| SHORT AND SWEET 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.