American Scientist

As a graduate student in mathematics, I often found that lectures by visiting speakers exercised my eyelids more than my brain. I'd struggle to understand the subject for five minutes, fail, then struggle to stay awake for 55 minutes longer. But one talk was decidedly different. The speaker walked in, emptied his pockets of a large quantity of ball bearings, which rolled with a tremendous clatter all over the desk at the front of the room, and asked, "What's the best way to pack these things together?"

The speaker was Neil Sloane of Bell Laboratories (now AT&T Research), and his question—how to pack balls together in the densest possible way—was one of the oldest unsolved problems in mathematics. In 1611, the German physicist Johannes Kepler stated what he felt to be the obvious solution: You make a triangular array, then fit another layer into the interstices between the balls in the first layer, and so on. In this arrangement, called the face-centered cubic lattice, just over 74 percent of the volume of the space is taken up by balls, and 26 percent by the spaces between the balls. Kepler never even tried to prove that this was the densest packing. But later mathematicians questioned his assumption, now called the Kepler Conjecture. For all Sloane knew, his ball bearings might one day settle into a configuration with only 25 percent empty space.

Now, it appears, Sloane can put his ball bearings away. Tom Hales of the University of Michigan claims to have a proof that no sphere packing can be denser than the face-centered cubic lattice. Like the proof of the Four-Color Conjecture, another notorious problem that was solved in the 1970s, his argument relies heavily on computer calculations: roughly 100,000 of them, virtually all of them too lengthy to do by hand. Consequently, mathematicians are unlikely to pronounce the problem solved for at least several months.

One way to understand what makes the sphere-packing problem so hard is to contrast it with the problem of finding the densest lattice packing of spheres. Lattices, the most regular arrangement of spheres, can be constructed by choosing a single "crystal" shape, placing a sphere at each of the imaginary crystal's corners and repeating that motif ad infinitum. Because the positions of all the other crystals depend on the first one, the entire lattice is determined by the position of the first set of spheres. Finding the maximum density then becomes a calculus problem with a finite number of variables. "It's not exactly a trivial calculus problem," says John Conway of Princeton University. "But it's something that could be done in 1831," which is when Karl Friedrich Gauss solved it.

By contrast, in the full sphere-packing problem, the position of every sphere becomes a variable—and it takes infinitely many spheres to fill up all of abstract mathematical space. A problem with a finite number of variables can be solved by hand if the number is small enough, or by computer otherwise. No computer, though, can solve unaided a problem with infinitely many variables, because it would require the storage of an infinite amount of data.

The trick, then, is to reduce the problem somehow to a finite one—to divide space up into small regions or "cells" and analyze each one separately. If the face-centered cubic pattern could be proved superior or equal to any challenger in every single cell, then it would be best in all of space, too. Unfortunately, this is a hard way to defend a championship—analogous to requiring the champion to win or at least draw every round of a boxing match. And, indeed, early attempts to prove Kepler's Conjecture this way fell short.

In the 1950s, Hungarian mathematician Lászlo Fejes Tóth suggested defining a cell as the set of points that are closer to one particular sphere's center than any other. Each cell thus defined (called a Voronoi cell) contains one spherical "nucleus." In the face-centered cubic packing, every Voronoi cell is a rhombic dodecahedron, whose nucleus fills up 74 percent of the cell. But some less-regular packings can contain denser Voronoi cells—for example, regular dodecahedra, whose nuclei occupy 75 percent of the volume. Thus these packings would beat the face-centered cubic pattern in some regions.

In 1990, Wu-Yi Hsiang of the University of California at Berkeley attempted to show that the Voronoi cells surrounding any extra-dense cell would have to compensate by containing more empty space. (In our analogy, the champion would be allowed to lose a round if he could win the rounds before and after.) Although his argument aroused spirited discussion, most mathematicians who read it felt that it fell short of being a convincing proof of the conjecture. Fejes Tóth's son Gábor wrote in Mathematical Reviews, "The greater part of the work has yet to be done."

Hales kept the rule that the champion has to win every round, and changed the scoring system instead. He found a delicate "splicing" of the Voronoi cells with a second type of decomposition, called the Delaunay decomposition. The shapes of the spliced regions depend on the positions of no more than 50 spheres, so the problem is still finite and solvable by computer. Although the computation was automatic, Conway emphasizes that the outcome—that the face-centered cubic is densest in every one of Hales's regions—never was. "I found it very surprising that a scheme like this could work," Conway says.

Since Wolfgang Haken and Kenneth Appel's proof of the Four Color Theorem rocked the mathematical world in 1976, mathematicians have gotten a little more used to the idea of computer proofs. Still, checking a "mega-proof" like Hales's will be a serious challenge. Robert Connelly of Cornell University suggests that it may require something more like the replication of an experiment than a line-by-line scrutiny. In the long run, Conway believes that such computer proofs are "not part of the permanent furniture of mathematics." Someday, he predicts, mathematicians will find a computer-free proof of the Kepler Conjecture—although it might take another 400 years.