Lisa Howie MB&B 452a Final Project December 9, 1999 SOLUTION OF THE SPHERE-PACKING PROBLEM Sphere-packing is a key element of structure determination in bioinformatics. The issue, however, has roots dating back long before the days of bioinformatics. In 1611, Johannes Kepler determined that the densest packing of spheres is the face-centered cubic lattice arrangement, filling 74% (pi/sqrt 18) of the space (1-4). In the face-centered cubic arrangement, the first layer is formed by staggering lines of spheres so that each line is in the cracks of its neighboring lines of spheres. Layers are added in the dimples of the layer beneath, much like the stacking of fruit at the grocery store (5). Unfortunately, Kepler did not give a proof that face-centered cubic packing is more efficient than any other regular lattice or random arrangement. The Kepler conjecture has gone unproven until now. Almost 400 years after the assertion was made, Thomas Hales of the University of Michigan has announced a solution, believed to be accurate. Hales is not the first mathematician to propose a solution to the Kepler conjecture. In 1953, L. Fejes Toth made progress by reducing the problem to a finite, extremely large calculation. He knew that he did not have the capabilities to solve the calculation but hoped that computers might someday be able to aid in the solution (4). In 1991, however, Wu-Yi Hsiang looked toward a different method of proof. Using spherical geometry, vector algebra and calculus and using only a pocket calculator, Hsiang proposed a solution to the sphere-packing problem (1). Unfortunately, his proof did not stand up to rigorous scrutiny. Experts, including Hales, found several flaws and unsupported claims in both Hsiang's original proof and his revised 1993 version and his results have since been dismissed (2, 4). Thomas Hales follows the approach favored by Toth, reducing the conjecture to a local, finite, complex calculation and using computers to solve it. A key factor in his solution is the innovative "hybrid decomposition" method used to allocate empty space to particular spheres. The standard method had been the formation of Voronoi polyhedra, created by including all points that are closer to the given sphere center than to any other center. Dual to the Voronoi decomposition is the Delaunay decomposition. The faces of Voronoi polyhedra contain points equidistant from two sphere centers. Under the Delaunay method, these sphere centers are connected by an edge, which divides the space into Delaunay simplices. The union of all Delaunay simplices around a common vertex forms a Delaunay star, essentially a Voronoi polyhedron with "tetrahedral protuberances" (3, 4). Hales's hybrid decomposition allocates some parts of the empty space using the Voronoi decomposition and some parts using the Delaunay decomposition. The choice of decomposition is made on an individual basis (4). Another key element in the proof is the score associated with each sphere and the empty space assigned to it. Using Hales's calculations, the stars in the face-centered cubic lattice arrangement each have a score of eight points (3). Thus, any arrangement disproving the Kepler conjecture must include at least one star with a score greater than 8, meaning that a more efficient packing method is possible. So in order to prove the Kepler conjecture, Hales set out to show that the score of every star in every other packing combination was less than 8. This lead to a nonlinear function describing every possible sphere-packing arrangement: a 150-variable equation that needed to be maximized. Because this approach was nearly impossible, Hales changed the problem by drawing a number of hyperplanes above the function and looking for the highest point lying under all of the hyperplanes. This simplified the original optimization problem by requiring only a linear maximum, which can be determined using linear programming (4). The horribly complex nonlinear function was reduced to a simpler exercise in linear programming computer methods, although the linear function still contained about 150 variables. A main concern then became ensuring the quality of the data. The large scale of the problem required extreme care because even a small inefficiency could lead to a large miscalculation. The rigorous technique of interval arithmetic was used to ensure that no rounding errors would eliminate possible high scores. Of the 5094 possible types of stars, these computer techniques eliminated all arrangements except about 50 that required extra work. One of the most difficult cases was a pentahedral prism, made of 12 spheres around a central sphere. Samuel P. Ferguson, a graduate student working on his doctoral dissertation, finally solved this case (3). After refining techniques and conducting further analysis, the scores for all possible arrangements were below 8. Thus, Thomas Hales proves that the face-centered cubic lattice arrangement is the most efficient sphere-packing method. Kepler's conjecture finally has a proof. Hales's proof has not yet been subject to rigorous scrutiny. His solution is extremely lengthy, consisting of 250 pages of text and three gigabytes of computer files. Because mathematicians are not experienced in analyzing the accuracy of computer software and hardware, it may take time for the proof to be completely scrutinized. According to Princeton mathematician John Conway, however, "For the last decade Hales's work on sphere-packing has been painstaking and credible. If he says he's done it, then he's probably right (5)." Obviously, Hales's solution is not similar to any proof Johannes Kepler would have written. The question of how Kepler would have gone about solving this problem still remains. Did Kepler know how to prove that the face-centered cubic lattice arrangement was the most efficient method of sphere-packing? How would he have done it? Is it possible to prove the Kepler conjecture using Hsiang's methods of geometry, algebra and calculus? Rather than focusing on these questions, however, mathematicians will use Hales's work to answer more complex questions, involving sphere packing in four dimensions and beyond. References 1. Cipra, B. (1991). Music of the Spheres. Science, 251, 1028. 2. Cipra, B. (1993). Gaps in a Sphere-Packing Proof? Science, 259, 895. 3. Cipra, B. (1998). Packing Challenge Mastered At Last. Science, 281, 1267. 4. An Overview of the Kepler Conjecture, http://www.math.lsa.umich.edu/~hales/countdown/holyoke.html 5. Singh, Simon. "Mathematics 'Proves' What the Grocer Always Knew." New York Times 25 August 1998.