Professor Thomas Hales of the Massachusetts Institute of Technology announced last year that he had posted on the Internet the solution to a seemingly simple problem that has taxed the brains of some of the finest mathematicians for 300 years. If the proof is accepted as complete (which now seems likely), Kepler's Stacking Problem will have been solved through a combination of human ingenuity and the power of modern computers. The solution, posted by Professor Hales at http://www.math.lsa.umich.edu/~hales/countdown contains 250 pages of logic, and the use of mathematical programs requiring huge amounts of storage space.
The problem is to prove that there is no way of fitting more spheres into a given space than that which a grocer would use to stack oranges in a crate. Starting by covering the floor of the box, new layers are added by fitting them in the hollows formed by the layer underneath.
This arrangement is known as face-centred cubic packing. The problem of proving it to be the most efficient possible is known as Kepler's Stacking Problem, after the famous German scientist Johannes Kepler (1571-1630) who first proposed it.
History of the problem
The problem is the oldest in discrete geometry (the geometry of separate shapes). It was first posed at the beginning of the seventeenth century, when Sir Walter Raleigh asked the mathematician Thomas Harriot to study the stacking of cannon balls. After preparing a chart from which the number of cannon balls in a stack could be read off, the Englishman wrote to Johannes Kepler in Germany.
Kepler was a great astronomer and physicist, in addition to being a brilliant mathematician. He discovered the laws governing the orbits of the planets around the sun by studying the observations of Tycho Brahe, the Danish astronomer. Based on these laws, he wrote tables (published in 1627) from which the positions of the planets could be predicted. Kepler's work on planetary motion was the direct precursor to Newton's discovery of gravitation and the laws of motion. Kepler also studied and wrote on other questions of geometry.
Kepler and Harriot had their differences--Harriot held that solid matter was made of closely packed atoms, and that this could explain properties such as the partial reflection of light falling on a transparent surface, but Kepler initially disagreed. This was the subject of several letters between the two. Despite his initial reluctance to adopt an atomic theory of matter, Kepler eventually did so, publishing an essay in 1611 on the implications of the theory that matter was composed of small, spherical particles.
The relevance of the stacking of spheres to such theories is clearer today, knowing as we do that matter is indeed made up of atoms, and that determining the arrangements in which atoms are packed is vital in understanding the properties of matter.
Kepler was the first to describe the face-centred cubic packing of spheres and to propose that, in this arrangement, "the packing will be the tightest possible". However, he was unable to provide a proof for this belief, as were all the subsequent generations of mathematicians until today. It has become known as "the Kepler conjecture".
The problem resurfaced in a debate between Isaac Newton and David Gregory over the greatest number of spheres of equal radius that can be made to touch a given sphere, a problem known as the "touching spheres problem". An example of the same kind of problem in two dimensions (that is, on a flat surface) is that of finding the greatest number of equally sized coins which can be placed on a table so as to touch the coin in the centre. The answer in this simple case is clearly six, but with spheres arranged in three dimensions, the answer is not so clear. Newton said the maximum number was 12 spheres, whilst Gregory thought that 13 would be possible. It was Newton who turned out to be right. In the case of face-centred cubic packing, the 12 spheres consist of the 3 spheres forming the hollow in the bottom layer and the corresponding 3 above, together with another 6 around the outside. Proving rigorously that this was the maximum possible number was more difficult, however, even though it involved a total of only 13 spheres. This took until 1953, when B.L. van Waerden and Schutte solved it. The proof of the Kepler Stacking Problem put forward by Thomas Hales draws upon their work.
The earliest progress on solving Kepler's Stacking Problem was made by Carl Friedrich Gauss, another brilliant German mathematician, who demonstrated that of all the regular arrangements of spheres, known as lattices, the face-centred cubic arrangement gave the greatest density.
The earliest attempt to draw up a strategy to solve the Kepler Stacking Problem was made in 1953--the same year as the solution of the touching spheres problem by Waerden and Schutte--when L. Fejes Toth made this the first step of a strategy to prove the Kepler conjecture. L. Fejes Toth also made many other contributions, such as his proposal, in 1964, to use computers to facilitate a proof. He said, "We are far from attempting to determine the exact [solution]. But, mindful of the rapid development of our computers, it is imaginable that the [solution] may be approximated with great exactitude."
Other great mathematicians have also played a part in the search for a solution, and their difficulties have underlined the complexity lurking in this apparently simple problem. David Hilbert, the foremost mathematician at the turn of the century, included it as part of his eighteenth problem in his famous "Mathematische Probleme" of 1901.
In 1976 J. Milnor wrote in a review of Hilbert's eighteenth problem "The corresponding problem in three dimensions remains unsolved. This is a scandalous situation since the (presumably) correct answer has been known since the time of Gauss ... all that is missing is a proof."
Now that we have been presented with a proof, however, it is clear that a great deal of progress was needed in the use of computers to solve mathematical problems, as well as in the mathematical concepts for analysing arrangements of spheres, to make this solution possible.
At the time L. Fejes Toth put forward his strategy to solve the Kepler Stacking Problem, sphere packings were analysed as follows: Choose one particular sphere in the given arrangement and draw straight lines out from its centre. Set the length of each line so that all the points along it are closer to the centre of the chosen sphere than they are to the centres of the other spheres. Drawing many such lines builds up a solid shape around the centre of the sphere. When this is done for all the spheres, the arrangement is divided into separate cells, containing one sphere in each.
Using this method--known as a "Voronoi decomposition"--L. Fejes Toth asserted that the smallest possible such shape (giving the tightest possible packing) would be one with 12 equal sides. If he had been able to prove this, it would have set a limit to the highest possible density at 75.5 percent. In other words, the spheres could take up not more than just over three-quarters of the available space. It has not been possible to prove this result until now. Until recently, the lowest value for the maximum possible density was 77.3 percent, a result proven by D. J. Muder in 1993. To prove the Kepler conjecture requires a proof that the maximum possible density of spheres is that of face-centred cubic packing, 74.0 percent, a figure which may not seem much different than Muder's, but is far more difficult to achieve.
To get closer to proving this value, a new method of breaking down the packing into unit cells, containing one sphere in each, had to be found. The next attempt to find such a method was the "Delaunay decomposition," and this was used to show (by using computers) that two forms of packing, the face-centred cubic packing and another called hexagonal-close packing, give better densities than any similar arrangements. Hales found that even using this more sophisticated approach, the Kepler conjecture could still not be proven.
Hales tells us in his "Overview of the Kepler Conjecture" that the complexities of his work caused him to set aside his program until 1994, when he developed a new way of decomposing the problem into cells, which combined the Voronoi decomposition with the Delaunay decomposition. The resulting method then had to be refined over a number of years, eventually leading to the model used in his proof of the Kepler conjecture.
The development of computers
Alongside this work on mathematics, great advances in computer software have been made, so that computers can now be used to provide exact solutions to complex equations. This has meant that previously intractable problems are now within reach for mankind to solve.
The use of computers in mathematical proofs is a relatively recent development. The first time was in 1976, in solving the problem of the minimum number of colours needed for colouring any map--another deceptively simple problem which had been outstanding for over a century. The solution devised by Kenneth Appel and Wolfgang Haken relied on computers to analyse a large number of special cases. In their book on the "The Four Colour Problem" published in 1977, Thomas Saaty and Paul Kainen commented prophetically that "much more important than the initial stimulus [for using computers in a mathematical proof], the computer-assisted analysis of cases employed by Haken and Appel may lead to fundamental changes in our perception of mathematics and its role in solving complex problems. The symbiosis between mathematician and machine required for this proof points towards an exciting future."
Not everyone was convinced of this at the time. Two major objections were advanced to the use of computers in this field:
1. Computers are prone to make errors (resulting from faults in the computer programs or from faults in the computer hardware itself).
2. Human verification of the results was not possible (to manually go through the execution of the computer program line by line as was performed by the computer would take a prohibitive length of time--it took 1,200 hours for the computer itself in the solution of the Four Colour Problem).
The first objection was answered by the argument that computers are actually less prone to errors than are human beings themselves. The second by the argument that while it is not possible for humans to replicate the execution of the program, it is possible for the method of its execution to be analysed, so long as the computer code is published as part of the proof. (Thomas Hales has complied with this requirement, by posting the computer code developed by himself and Dr. Samuel P. Ferguson on the Internet as part of their proof).
Because of the objections, this use of computers remains quite controversial, although it is now widely accepted as a valid technique. In 1976, the computer-aided analysis of 1,936 special cases taking 1,200 hours of computer time was considered groundbreaking. The exponential progress in both computer hardware and software since then can be glimpsed by the much greater complexity of the Kepler Stacking Problem.
To prove the Kepler conjecture, about 5,000 different packings (in which the centres of the spheres form triangles or four-sided shapes, as shown in the diagrams) were classified, and 100 were analysed in detail.
A particularly difficult arrangement to analyse was one in which the centres of the spheres form a five-sided shape, this being the arrangement which prevented earlier attempts at a proof using the Delaunay decomposition. Even the simpler cases required solving equations with between 100 and 200 variables and between 1,000 and 2,000 constraints (conditions which the solution has to fulfil). In performing the proof, nearly 100,000 such equations had to be solved. Despite the large number of calculations required to solve the problem using this approach, it does enable the division of all the possible arrangements into a finite (though very large) number of categories. Hales's computer programs required more than three gigabytes (3,000 million bytes) of storage space, an amount that would have been impossible a few decades ago, but which is now commonly available in desktop computers.
Even if the solution as first posted on the Internet was found to require modifications or additions to meet the standards of mathematical rigour demanded of such proofs, there is no doubt that a major step forward has been taken in mathematics. It is a matter of time before this leads to advances in the sciences. Since the packing of spheres is such a recurring theme in nature, practical applications are possible in such fields as communications technology amongst others.
The solution to this 300-year-old problem shows the potential for human ingenuity to overcome seemingly insuperable obstacles, especially if problems can be reduced to a large number of mathematical equations, which can be solved by computers. Once considered important only in areas of applied mathematics such as fluid flow, computers are now becoming accepted as an essential tool in an increasing number of fields. They enhance the ability of mathematicians to tackle problems whose complexity has previously put them beyond the reach of scientific analysis.