Image: SAMUEL P. FERGUSON,
University of Michigan |

By now, it's a classic tale. A genius makes an assertion; scientists spend ages trying to confirm it. In 1611, astronomer Johannes Kepler penned what he thought was a self-evident fact: the most dense arrangement of spheres is face-centered cubic packing. In other words, to fit the most spheres in the least space, do as grocers do with oranges: Make layers in which each orange touches six others, and stack these layers so that the fruit in one fits into the holes between those below.

On the face of it, Kepler's Conjecture--also called the sphere-packing problem--seems simpler to prove than other legendary teasers, such as Pierre de Fermat's famed Last Theorem, jotted down sometime before his death in 1665. But it's taken a bit longer to do so. Now, three years after Princeton mathematician Andrew Wiles finally put Fermat's puzzle to rest, Kepler's conundrum may also be resolved.

Image: ERIC WEISSTEIN,
University of Virginia |

In August, Thomas C. Hales the University of Michigan announced by email that he had found a solution. Hales's is not the first such claim. In 1993, Wu-Yi Hsiang of University of California at Berkeley published a proof of Kepler's conjecture, but his arguments did not stand up to scrutiny. Hales's work, although it has not yet been submitted to a scholarly journal or thoroughly reviewed, has many mathematicians excited because much of the proof rests on solid work that Hales and others have published over the years.

In fact, many mathematicians have contemplated sphere packing. Perhaps one of the first was Thomas Harriot, who first called Kepler's attention to the problem. In his role as mathematical assistant to discoverer Sir Walter Raleigh, Harriot was assigned to develop formulas for counting stacked cannonballs--which got him wondering about what arrangement would take up the least space.

The problem drew particular attention in 1900 after David Hilbert challenged his peers at the International Congress of Mathematicians in Paris with a list of unsolved problems. Hilbert's problem 18 asked: "How can one arrange most densely in a space an infinite number of equal solids of a given form, e.g., spheres with given radii....; that is, how can one so fit them together that the ratio of the filled to the unfilled space may be as great as possible?"

Image:
Clark University |

Several 20th-century mathematicians who took up the challenge set upper bounds on this ratio of filled to unfilled space. But they could not prove that it was as low as the ratio for face-centered cubic packing, or about 74 percent. Notably, in 1958, C.A. Rogers of the University of Birmingham showed that no packing of spheres could have a density greater than about 0.7796. That is, given any volume filled with spheres, no more than 78 percent of it can contain solid spheres; the rest of the volume comprises the spaces between them. But, as Rogers wrote, "Many mathematicians believe, and all physicists know, that the density cannot exceed 0.7404."

Perhaps the greatest boost for Hales's efforts occurred in 1953 when the Hungarian mathematician L. Fejes Toth demonstrated that the proof could be reduced to a finite--though impossibly complicated--calculation. This result, like Rogers's, offered no immediate gratification, but Toth predicted that increasing computing power would soon bring the necessary calculation within reach.

Brute-force computing is exactly what paid off for Hales. In short, his approach can be expressed as the maximizing of a nonlinear function of about 150 variables--no simple task. He subdivided the attack into five steps: Step one was solved in 1994, and step two, a year later. Two years ago, Hales had partial results to steps three and four. The final, fifth step was recently completed as part of a doctoral thesis written by his student Samuel P. Ferguson. The total argument takes up more than 250 pages.

So what happens if Hales's proof withstands scholarly scrutiny: Has he simply proved something that grocers and gunners have known for years? The results will, in fact, have important implications. Sphere-packing problems have a number of applications when they are extended into other dimensions. For instance, the packing of circles in two dimensions--called the kissing problem --was solved by R. Hoppe in 1874. In three dimensions, densely arranged spheres serve as useful models for the interaction of atoms in liquids and solids, such as crystalline materials. And in unlimited dimensions, sphere packing is equivalent to designing efficient digitally encoded messages.

Like Fermat, Kepler had no idea what he started.