Kepler's Sphere-Packing Conjecture Is Finally Proved

views updated

Kepler's Sphere-Packing Conjecture Is Finally Proved

Overview

For nearly four centuries, the Kepler conjecture regarding the most efficient geometrical arrangement for stacked spheres remained one of the most complex and vexing problems in mathematics. Kepler's conjecture—a mathematical expression of commonplace packing techniques—states that the most efficient (i.e., the densest arrangement with the least unused or empty space) packing of spheres results from placing a layer of spheres as tightly as possible on top of an underlying layer. Although Kepler's conjecture seemed proved by everyday experience, a mathematical proof that no better packing arrangement existed seemingly eluded mathematicians until the last decade of the twentieth century.

Background

Although stacking problems are an intuitively ancient exercise for mankind, the formal incorporation of stacking theory dates to the sixteenth century when Sir Walter Raleigh (1554?-1618) challenged his assistant, English mathematician Thomas Harriot (1560-1621), to find a reliable and efficient manner to estimate the number of cannonballs in a munitions pile. Such an estimate was important both to the efficient movement of an army, especially aboard ships, and to the strategic estimate of an opponent's ability to wage war. Although Harriot was quickly able to come up with a useable calculation he sought a deeper mathematical proof that the intuitive way to pack spherical objects such as cannonballs was indeed the best method available.

Harriot sought the advice of German mathematician and astronomer Johannes Kepler (1571-1630) who was also interested in such stacking problems. Kepler was attempting to reconcile the orbits of planets in the then controversial heliocentric universe proposed by Polish mathematician Nicholas Copernicus (1473-1543) . In asserting that the known planets traveled in orbits around the Sun rather than about the Earth, Copernicus challenged the longstanding Ptolemaic concepts (named after Alexandrian astronomer and mathematician Ptolemy who published his theories in approximately A.D. 140) of a universe consisting of stacked crystalline spheres upon which the heavens moved. Although he eventually made courageous and fundamental discoveries regarding the elliptical orbits of planets, Kepler spent a lifetime attempting to relate the orbits of planets to the shape of perfect solids. Kepler was convinced that the correct model for the universe consisted of tightly packed stacked perfect solids located within spheres having a common center located at the Sun. Kepler's passion to find the most efficient way to arrange these spheres drove him to study other stacking and crystalline arrangements in ice or snowflakes.

Although Kepler could not mathematically deduce a more efficient way to pack spherical objects he was able to determine that the intuitive method used for centuries was indeed the most efficient known manner to pack. In essence, Kepler's problem came from his inability to construct a mathematical proof that there were no other arrangements that might prove more efficient.

After studying the problem, in 1611 Kepler asserted that the so-called "face centered" cubic lattice was the most efficient packing arrangement for spheres. This assertion regarding the problems related to sphere packing became known as the Kepler's conjecture.

Kepler's conjecture stated that the tightest pack of any spherical objects (i.e., balls) of the same radius was achieved by stacking layers of spheres one upon the other. Each layer being added, however, was shifted to allow the new layer of spheres to partially fit into, and thus partially fill, the holes between spheres located in the lower layer.

Although efficiency with regard to packing problems is a simple mathematical concept, it is an economically critically concept to agriculture and industry. Spheres (e.g., grapefruit) can be laid in layers to form a crystal lattice wherein the centers of the spheres are directly on top of each other. Such an arrangement, however, is not nearly as an efficient means of packing as method suggested by Kepler's conjecture. When the centers of the upper layer of spheres are shifted to a position over the gaps between spheres in the first layer, almost twice the number of spheres (e.g., fruit, balls, spherical mechanical parts) can be packed into the same space. Moreover, without such shifting, the wasted space in a lattice nearly equals that of the space occupied by the spheres. A shift in the centers of the spheres located in the initial (i.e., lowest) base layer, however, so that neighboring rows also have centers filling the gaps in adjoining rows (upon which additional layers are then laid using the gap filling method) provides increased efficiency. Using such a packing arrangement, nearly three-fourths of the space in a box is comprised of spheres and only slightly more than a quarter of the space remains unused. (i.e., an efficiency of about 74%).

Although most people are unaware of the mathematics behind the proof of Kepler's conjecture, they deal with the conjecture on a practical basis almost daily. Grocers, for example, use this method to stack fruit for shipping and display.

Efficiency in sphere packing is also critically important to physicists and chemists trying to understand and predict the behavior of atoms and molecules. Because nature seeks the lowest entropic state, there is a drive toward efficiency in packing. Understanding the mathematics related to sphere packing allows physicists and chemists to study areas such as metal structure and the dispersion of gas molecules.

German mathematician and physicist Carl Friedrich Gauss (1777-1855) offered a partial two dimensional solution to the Kepler conjecture, by proving that the most efficient arrangement of circular disks was one that allowed a disk to be surrounded by six others in a hexagonal arrangement. At the close of the nineteenth century, mathematician David Hilbert (1862-1943) included Kepler's conjecture regarding the sphere-stacking problem in his famous list of 23 problems to be solved during the twentieth century.

Impact

Although Kepler's conjecture regarding sphere-packing seemed true to everyday experience and remained mathematically undisputed, a formal mathematical proof remained elusive. Kepler's conjecture vexed mathematicians well into the twentieth century when two independent solutions were put forth by mathematician Wu-Yi Hsiang of the University of California and mathematician Thomas Hales (1958- ) of the University of Michigan.

In 1993 Hsiang claimed a proof to Kepler's conjecture. Although well-constructed, Hsiang's proof eventually ran into problems because of the fundamental assumptions upon which it relied. Hales and his research student Samuel P. Ferguson subsequently announced another proof to Kepler's conjecture that avoided the problems found in Hsiang's proof. Although Hales himself refrains from actually claiming the Kepler conjecture as "proved," his proof led most, but certainly not all, mathematicians to consider the Kepler conjecture as probably proved. At the close of the twentieth century, the issue had not yet been finally settled.

Hales's work was based, in part, on the 1950's work of mathematician L. Fejes Tóth who proposed that the Kepler conjecture could be reduced to a finite but impossibly large calculation. With amazing foresight, Tóth proposed that computers might one day be used to construct a proof to the conjecture. In addition to the use of computers, Hales's work utilized the concept of hyperplanes to overcome the limitations of the attempting to maximize functions through the standard techniques used in calculus (e.g., taking derivatives) that are often too cumbersome for complex problems.

The proof of Kepler's conjecture did prove highly complex, requiring hundred of pages of analysis and equations with more than a hundred variables. Accordingly, proof that there was no more efficient arrangement than the standard "grocer's solution" proved difficult without the use of powerful computers. Similar to the 1976 solution put forth by Wolfgang Haken and Kenneth Appel (1932- ) regarding proof of the Four Color Conjecture (i.e., English mathematician Francis Guthrie's conjecture, put forth in 1852, that only four colors were required when attempting to color maps in such a way that no neighboring areas would be forced to have the same color), Hales's proof wasn't purely theoretical because it relied, in part, on computer-based algorithms.

Of special significance during the information revolution was the way Hales announced and argued his proof of Kepler's conjecture. Although he subsequently published in established journals, Hales initially set out his proof on the Internet. This was a radical departure from the traditional methods of submitting proofs to the mathematical community for review. Prior to late twentieth-century advancements in information technology, scholars were limited in ways to present new ideas. Essentially, scholars could submit articles for selected peer review and possible publication in a scholarly journal or they could present their work at scholarly (e.g., mathematical) conferences. Similar scrutiny had revealed the flaws in a previously offered proof of Kepler's conjecture put forth by Hsiang.

Such computer-reliant proofs remained a source of controversy in late twentieth-century mathematics. Critics of such proofs asserted that potentially undiscovered hardware or programming errors (e.g., potential flaws with linear inequalities used in the linear programs) cast a shadow of doubt over such proofs not usually present in traditional pen and paper proofs. Pure mathematicians claimed that such computer-dependent proofs lacked elegance (i.e., simplicity) required in theorems. More strident critics of computer usage classified such solutions as brutish methodology that attempted to prove theorems by volume of calculation. Other scholars, however, lauded the use of computers and the concurrent programming advancements as careful, rigorous, and realistic treatment of complex problems.

The potential proof of Kepler's conjecture excited researchers looking for potential solutions to other "stacking" problems. In particular, Hales's potential proof of the Kepler conjecture caught the interest and scrutiny of mathematicians and engineers concerned with coding theory (i.e., the branch of mathematics concerned with Keplerian-type packing problems). Hope ran high that the methodology developed to prove Kepler's conjecture might provide potentially new and innovative ways to stack (compress) electronic computer data without corrupting or damaging the data. Researchers in this field also speculated that advances in packing theories could allow for greater memory capacity, increased encryption security, and more efficient transmission of data over the burgeoning Internet.

Proof of packing theory impacts areas as diverse as the search for oil (e.g., through petrological analysis of reservoir capacity) and the quest for formulating theories regarding nature. Physicists seek to use methodologies derived from the proof of Kepler's conjecture to study how holes or voids are displaced in space relative to the positions of the spheres and how holes or voids are displaced relative to each other.

K. LEE LERNER