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.
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.
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."
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.
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."
Simon Singh is a TV producer and author of Fermat's Last Theorem, published by Fourth Estate.