 |
Packing them in
|
THIS week a puzzle that has confounded mathematicians for over three centuries is officially laid to rest. In the 17th century, the French mathematician Pierre de Fermat casually noted in the margin of a book that he had a proof of an apparently simple theorem. Unfortunately, the mischievous French man also wrote that there was not enough space in the margin to contain the proof, and in fact he never got round to committing it to paper.
After Fermat's death, the frustrating margin note was discovered and, ever since, mathematicians have tried to prove Fermat's Last Theorem. Fermat's brainteaser tickled some of the greatest minds on the planet. It attracted tremendous prizes and generated intense rivalries. This week, on 27 June, Fermat's challenge to the world officially comes to an end when Andrew Wiles, an Englishman working at Princeton University, goes to Göttingen to collect the prestigious Wolfskehl Prize (see "Last will and testament"), for his proof of the Last Theorem.
But this has left mathematicians twiddling their thumbs. Now that Fermat's riddle has been solved, what next? "There is a sense of melancholy," says Wiles. "We've lost something that's been with us for so long, and some thing that drew a lot of us into mathematics." Fortunately for despondent mathematicians, there are still plenty of conundrums left to be solved (see "Mathematical mystery tour"). How ever, a worthy successor for Fermat's Last Theorem must match its charm and allure. Kepler's sphere-packing conjecture is just such a problem-it looks simple at first sight, but reveals its subtle horrors to those who try to solve it.
Sorting spheres
Kepler's conundrum is even older than Fermat's-it first reared its head when Sir Walter Raleigh, explorer and Spanish Armada veteran, asked his mathematical friend Thomas Harriot if there was a formula for identifying the number of cannonballs in a stack. This led Harriot to ponder the different ways that spheres of all kinds can be arranged. In 1606, he wrote to Johannes Kepler, famed for his astronomical discoveries, outlining different possibilities.
| Last will and testament |
| IN THE 19th century,
a German industrialist called Paul Wolfskehl became obsessed by
Fermat's Last Theorem, and eventually bequeathed
100000 marks (equivalent to £1 million in today's money) to whoever
could find a proof. Wolfskehl's legacy inspired thousands of amateur mathematicians to take up Fermat's challenge. The Wolfskehl Committee was inundated with flawed proofs, and monitoring the entries soon became a nuisance. Edmund Landau, a member of the committee and head of the department of mathematics at the University of Göttingen, dealt with the matter by handing entries to his students along with a card which read: "Thank you for your entry. The first error occurs on page . . . line . . It was the student's task to fill in the gaps. Hyperinflation after the First World War devalued the prize considerably, but Wiles will still collect £30 000 for penning what has been called the proof of the century. |
Intrigued, Kepler wrote a paper in 1611 exploring how the way spheres arrange themselves could explain the formation of natural shapes and structures. As part of this research he began to investigate the most efficient way to stack spheres so they occupy the least possible space. He quickly realised that however they are arranged there will always be gaps between them. The challenge was to minimise the gaps.
After much trial and error, Kepler concluded that the most efficient arrangement is the face-centred cubic lattice (see Diagram). It's the way greengrocers stack oranges. First you make a bottom layer with each sphere surrounded by six others, then you make the second layer by putting spheres in the dimples of the lower layer. The second layer looks just like the first but it has been shifted sideways so that it fits snug;y into position. Other layers are formed in a similar way.
Just because the face-centred cubic lattice was the best Kepler could come up with, that doesn't mean there isn't a better way. The sphere-packing problem has turned out to be even more intractable than Fermat's Last Theorem-is the face-centred cubic lattice really the most efficient method of packing spheres?
It's a real poser-you have to check so many arrangements before you can be sure. And you can't limit yourself to neat regular arrangements-there is an infinite number of random ways to pack spheres, too. Which is why, in nearly 400 years nobody has been able to prove Kepler's conjecture. On the other hand, since nobody has discovered a more efficient way to pack spheres, most people assume that the conjecture is true. As the sphere- packing expert Claude Ambrose Rogers from University College London puts it, Kepler's claim is one that "most mathematicians believe, and all physicists know".
Mathematicians are never really satisfied without a rigorous proof, and so they have been sweating over their notepads for centuries. Progress was painfully slow until the summer of 1990, when the mathematical world was rocked by the news that the Kepler conjecture had been "proved".
Wu-Yi Hsiang of the University of California at Berkeley published a paper that seemed to succeed where generations of others had failed. All that remained was for a team of referees to go over his calculation with a fine- tooth comb.
Previously, mathematicians had projected the infinite box of spheres onto a conventional Cartesian system of coordinates with three perpendicular axes-x, y and z. Hsiang's apparent breakthrough involved analysing the problem using a different system of coordinates.
He employed spherical coordinates in which each point in space is defined by the length of a radius and its direction measured from the origin.
This seemed to be a far more natural approach for a problem involving spheres. Hsiang then broke down the infinite space into manageable chunks. He began by looking at a small cluster of spheres, rather than the infinite problem. Having tackled the local problem, he then developed a semi-global argument. Then, after a hundred pages of geometrical gymnastics, the argument matured into a truly infinite solution. This step-by-step extension from a local to a global solution was the key.
Although the proof was still being examined by other mathematicians, there was so much confidence in Hsiang's method that he was invited to give a lecture entitled "The proof of Kepler's conjecture on the sphere-packing problem" at the joint meeting of the American Mathematical Society and the Mathematical Association of America.
However, as time passed, experts in the field began to discover flaws in the proof, which forced Hsiang to issue a revised proof in the summer of 1991. Although the obvious errors were now fixed, the new proof was viewed with greater scepticism and scrutinised intently. Some mathematicians identified steps in the revised proof which they believed were unsubstantiated (New Scientist, Science, 2 May 1992, p 16). For instance, in a letter to Hsiang, Thomas Hales, now at the University of Michigan, wrote: "You state that 'the best way (that is, volume minimising) of adding a second layer of packing is to cap as many holes as possible . . .' Your argument seems to rely heavily and essentially on this assumption. Nowhere is there even a hint of a proof."
The argument has tumbled on. While Hsiang claims that he has cleared up all the glitches and that his proof is rigorous, his critics maintain that it is still incomplete. After attending a major conference in 1996 to discuss breakthroughs in geometry in 1996, Doug Muder, of the Mitre Corporation based in Massachusetts, who had been work ing on the sphere-packing problem since the 1980s, declared: "The community has reached a consensus on [Hsiang's proof]: no one buys it - . . At best it is a sketch (a 100-page sketch!) of how such a proof might go."
| Mathematical mystery tour |
| SOME of the most profound problems in
mathematics involve some of the simplest concepts. For example, there are
still mysteries surrounding "perfect
numbers". The factors of perfect numbers add up to the number itself.
For example, 28 is a perfect number because 1, 2, 4,7, and 14 divide into
28 and 28 = 1 + 2+ 4 + 7 + 14. Rene' Descartes said that "perfect numbers,
like perfect men, are very rare". Over the last few thousand years only 30
have been discovered. But is there an inexhaustible supply of perfect numbers
for mathematicians to find? Whoever succeeds in answering this question will
earn a place in history. Another ancient area of mathematics rich in unsolved problems is the theory of prime numbers. A prime number can only be divided by 1 and itself. For example, 2,3,5,1,11,13,17, 19,23,29 are all primes. The sequence of primes forms no obvious pattern, and they have been described as weeds growing randomly among the other numbers. For centuries mathematicians have searched for an underlying pattern, but it could be that no pattern exists, in which case mathematicians would be advised to tackle another less ambitious prime problem-the Twin Prime Conjecture. Twin primes are pairs of primes which differ by only two, for example 17 and 19, and 1000 000000061 and 1000000000063. Two thousand years ago Euclid proved that there is an infinite quantity of prime numbers, but no-one has yet managed to prove that there is also an infinite number of twin primes. |
Hsiang's proof is still shrouded in controversy-some say it has been discredited. Either way, the door is still open for anybody who wants to prove Kepler's conjecture beyond doubt. If you want to claim your place in the mathematicians' hall of fame, you could try patching up Hsiang's proof to everyone's satisfaction. Alternatively, you could follow the strategy being developed by his rival Hales.
Hales's research is based on the work of Lázló Fejes-Tóth, a Hungarian mathematician who spearheaded research into Kepler's conjecture in the 1950s. Fejes-Tóth suggested that the most efficient stacking arrangement could be identified by examining a finite cluster of spheres, rather than an infinite number of spheres. Unlike Hsiang's approach, Fejes-Tóth's method did not even require the gradual extension to a global cluster. Having analysed 50 spheres, the proof would be complete. This seemed to bring a proof within reach, but the calculation required to analyse this finite cluster in enough detail was beyond Fejes-Tóth.
The calculation involves looking at all the positions of the 50 spheres within the cluster. For each set of positions, you can then calculate a packing efficiency. Because the position of each sphere is defined by three coordinates, the equation you need to calculate the packing efficiency contains 150 variables. The task is to find the maximum value for this equation. If the maximum efficiency turns out to be 74.04 per cent, the efficiency for the face-centred cubic, Kepler's conjecture would be proved.
But how do you find the maximum value? For an equation this complex, standard methods would be pretty hopeless. Hales's approach is to plot the efficiency on a "graph" of 150 variables, building a hilly landscape in 150-dimensional hyperspace. All he needs then is a way to find the height of the tallest hill.
His approach to this involves constructing hyperplanes-rather like mathematical beams -which form a roof over the landscape. He checks that every hyperplane is clear above the landscape, so that he can be confident that the tallest hill sits below the tallest point of the hyperplane roof. Next, he calculates the highest point of the hyperplane roof. The skill is in lowering the roof until it just touches the tallest hill-which would give the value for the maximum possibly packing efficiency.
 |
| Packing problem: different ways to pack oranges in two dimensions (left and right); according to Kepler, the most efficient way to pack spheres in three dimensions is the face-centred cubic arrangement (centre) |
In recent decades, others have tried to lower the roof, and in 1958 Rogers calculated an upper limit of 77.97 per cent. This meant that there was a 4 per cent space in which a rogue hill (or arrangement) could exist and prove Kepler wrong. Reducing the upper limit further has turned out to be a slow and difficult process, and in 1993 Muder had only managed to reduce it to 77.31 per cent. Its a painstaking process, because lowering the ceiling involves introducing new, lower hyperplanes. For each new one you introduce, you need to ensure that it is completely clear of every hill, which takes a colossal amount of calculation. However, Hales believes he has discovered shortcuts which speed up the checking procedure. Instead of checking the entire hyperplane, he just tests certain points in each region of the landscape. Even with these short cuts, Hales has to resort to hefty computer power to perform his calculations.
This computational approach may eventually succeed where paper-and-pencil logic has failed, but many feel that such a proof is less illuminating than traditional proofs. A mathematical proof, the argument goes, should not just answer a question, it should also provide some insight. When a computer was used to solve the Four-Colour Problem (which poses the question, are four colours enough to colour any conceivable map, such that no two bordering regions are coloured the same?) some mathematicians were dismayed. Philip Davis from Brown University in Providence, Rhode Island, described his response to the news that a proof had been found: "My first reaction was. 'Wonderful! How did they do it?' I expected some brilliant new insight, a proof which had in its kernel an idea whose beauty would transform my day. But when I received the answer: 'they did it by break ing it down into thousands of cases, and then running them all on the computer, one after the other', I felt disheartened."
So while the smart money is backing Hales's approach, many experts in the field are hoping that a more traditional proof will emerge. But time is running out. Hales confidently predicts that a complete proof is on the horizon: "If I haven't done it by the year 2000, I'll be disappointed."
|
