Subject: Science -- Cipra 281 (5381): 1267 [clip] Date: Mon, 31 Aug 1998 11:04:09 -0400 From: "Mark B. Gerstein" Organization: Yale MB&B Bioinformatics (http://bioinfo.mbb.yale.edu) To: "all@bioinfo" CC: fleming@csb.yale.edu http://www.sciencemag.org/cgi/content/full/281/5381/1267 -- Mark.Gerstein@yale.edu * 203 432-6105 * http://bioinfo.mbb.yale.edu --------------------------------------------------------------------- [Journal of Nutrition] [Image] [Eppendorf] [Image] [Image] [Image] [Image] [Image] [Image] [Image] [Image] [Image] MARK GERSTEIN || Change Password || View/Change User Information || CiteTrack Personal Alerts || Subscription HELP || Sign Out --------------------------------------------------------- MATHEMATICS: Packing Challenge Mastered At Last Barry Cipra Johannes Kepler is best known for his elliptic laws of planetary motion. But mathematicians also remember him for a vexing problem in geometry: proposing--but not proving--that the densest possible packing of same-sized spheres is the arrangement familiar today to anyone who's ever admired a pyramid of oranges in a grocery store. Known to crystallographers as the face-centered cubic lattice packing, it fills a little over 74%--p/sqrt18, to be precise--of space. For nearly four centuries Kepler's conjecture has remained one of those mathematical Everests, like Fermat's Last Theorem, that people tackle for the sheer challenge of it. There's never been much doubt that the conjecture is true; the question has always been whether anyone can prove it. The answer, finally, appears to be Yes. Thomas Hales, a mathematician at the University of Michigan, Ann Arbor, recently announced the completion of a lengthy analysis that appears to provide a rigorous proof of Kepler's conjecture. Hales's analysis, parts of which have already been published, combines 250 pages of mathematical reasoning with computer programs that enumerate and check thousands of crucial details. "It's really an amazing achievement," says Neil Sloane, a sphere-packing expert at AT&T Laboratories. Hales's proof has yet to undergo close scrutiny, but Sloane is impressed with what he's seen so far. "He's documented everything very carefully," Sloane says. "Nobody's raised a single doubt about his work." That's important, in light of the Kepler conjecture's recent history. In 1990, Wu-Yi Hsiang, a mathematician at the University of California, Berkeley, announced that he had solved the sphere-packing problem (see Science, 1 March 1991, p. 1028). However, Hsiang's proof encountered a buzz saw of criticism from experts, including Hales, who said there were numerous flaws and gaps in the proof's reasoning (see Science, 12 February 1993, p. 895). In 1994, Hales wrote a detailed critique of Hsiang's proof for The Mathematical Intelligencer, calling on Hsiang to withdraw his claim. (Hsiang reportedly stands by the correctness of his proof, but could not be reached for comment.) Hales's own proof follows a strategy first outlined by the Hungarian mathematician László Fejes Tóth in 1953. The strategy is to reformulate the conjecture in "local" terms, reducing it from a question about infinitely many spheres filling all of space to a series of questions about how certain finite arrangements of spheres fit together. To carry out that strategy, Hales invented a new way to allocate the empty space in a packing to individual spheres. The standard approach assigns to each sphere its "Voronoi cell," consisting of the points that are closer to it than to any other sphere. If every sphere in any other packing simply occupied no more than 74% of its Voronoi cell, the Kepler conjecture would follow immediately. But Voronoi cells don't give a consistent measure of a packing's density. The spheres in some packings occupy as much as 75.5% of their Voronoi cells, although this high density is invariably canceled out by the low density of nearby cells. Hales calls his alternative a "star decomposition." Roughly speaking, a star is a modified Voronoi cell with a batch of tetrahedral protuberances. A second key ingredient of his proof is a novel way to "score" the local density of each star. In Hales's convention, the stars in the face-centered cubic lattice packing all have a score of 8 points. Any counterexample to the Kepler conjecture would have to include stars with a score greater than 8. "The proof gives a classification of all the stars that can potentially be a counterexample to the Kepler conjecture," Hales says. The list is a long one, but finite: A computer program found 5094 different types of stars, any one of which could conceivably have a score greater than 8. Each type then had to be ruled out, by showing that the largest score for each type of star stayed less than 8. To do so, Hales had a computer convert each inequality estimate into a series of problems in linear programming, a mathematical method that is widely used for optimization problems in industry. So that no star with a winning score would slip through the gaps of round-off error, the computer did the conversions using a mathematically rigorous technique called interval arithmetic. Most of the cases were easily disposed of, but some required extra care. "At the very end, it came down to 50 or so cases that the general arguments didn't rule out," Hales recalls. Hales and a graduate student, Sam Ferguson, looked at those cases one by one. One particularly problematic case, a local arrangement called a pentahedral prism, consisting of 12 spheres surrounding a 13th central sphere, became the subject of Ferguson's doctoral dissertation. "I only handled one case," Ferguson notes proudly. "It just ended up being the worst case." Initial calculations only said the pentahedral prism had a score less than 10. Ferguson had to refine the analysis to get a bound below 8. Early this month, the final pieces fell into place: The last potential counterexamples had been eliminated. Hales is careful not to claim too much. "This is not a refereed paper, and so it should be taken accordingly," he says. "I think [the experts] should be able to judge the overall strategy and methods and that sort of thing quite quickly, but I expect it'll be several months before the details will have been carefully checked." Assuming all goes well, proofs of other sphere-packing conjectures might follow. "I'll be curious to see what other problems can be solved by similar methods," Hales says. One possibility: A computationally intensive approach could suffice to prove the Kepler conjecture in four dimensions rather than three--a packing you'll never see at the grocer's. Search Medline for articles by: Cipra, B. Alert me when: New articles cite this article Collections under which this article appears: Computers/Mathematics Volume 281, Number 5381 Issue of 28 Aug 1998, p 1267 ©1998 by The American Association for the Advancement of Science. --------------------------------------------------------- [Image] [Image] [Image] [Image] [Image] [Image] [Image] [Image] [Image] [Image] Copyright © 1998 by the American Association for the Advancement of Science. Subject: NYT: Mathematics `Proves' What the Grocer Always Knew [clip] Date: Wed, 26 Aug 1998 00:07:51 -0400 From: "Mark B. Gerstein" Organization: Yale MB&B Bioinformatics (http://bioinfo.mbb.yale.edu) To: Note to myself http://www.nytimes.com/library/national/science/082598sci-stack.html -- Mark.Gerstein@yale.edu * 203 432-6105 * http://bioinfo.mbb.yale.edu --------------------------------------------------------------------- [banner] [toolbar] [Mayo ClinicHealth Oasis] August 25, 1998 Mathematics `Proves' What the Grocer Always Knew -------------------------------------------------------- Graphic * After Four Centuries, an Answer -------------------------------------------------------- By SIMON SINGH his month, Dr. Thomas Hales, a professor of mathematics at the University of Michigan, announced a solution to a problem that had plagued mathematicians for almost four centuries: What is the best way to stack oranges? It turns out that the classic arrangement used by greengrocers around the world is undoubtedly the most efficient way to stack oranges. While greengrocers reached their conclusion through experience and intuition, Hales spent 10 years developing a complex 250-page argument, which relies on three gigabytes of computer files. Although greengrocers may not be impressed by Hales's result, other mathematicians are already considering its implications for related stacking problems. These problems are linked to an area of research known as coding theory, which involves trying to compress data without corrupting it. In some ways, stacking data is much like stacking oranges, and understanding of both could lead to more efficient and accurate transmission of information. The orange-stacking problem can be traced to the latter half of the 16th century, when Sir Walter Raleigh wrote to the English mathematician Thomas Harriot, asking him to find a quick way to estimate the number of cannonballs in a pile. In turn, Harriot wrote to Johannes Kepler, the great German astronomer, who was already interested in stacking, but at the most fundamental level. A staunch believer in the Greek idea of atomism, Kepler wondered how water particles stacked themselves to form symmetrical snowflakes. All this speculation about stacking spheres, be they water particles or cannonballs, caused Kepler to investigate which was the most efficient way to arrange spheres to minimize the gaps among them. For example, imagine a layer of spheres arranged so that the centers of four neighboring spheres form a square. Other identical layers are placed so that the spheres are directly above each other, the centers of eight clustered spheres forming a cube. This arrangement is known as the simple cubic lattice, and it has a packing efficiency of only 52 percent; that is, the gaps among the spheres are almost as big as the space occupied by the spheres. Kepler experimented and could not find any more efficient arrangement than the so-called face-centered cubic lattice, which has a packing efficiency of 74 percent. In this arrangement, the first layer is formed by placing each line of spheres in the cracks of its neighboring line of spheres so that the centers of four neighboring spheres form a diamond. Each successive layer is built by placing spheres in the dimples of the former layer. This happens to be the arrangement used by greengrocers to stack oranges. Although Kepler could find no arrangement with a higher packing efficiency, he could not prove that no such arrangement existed. After all, there are an infinite number of possible arrangements, including random ones as well as regular lattices. Hence, his claim that the face-centered cubic lattice was the most efficient arrangement became known as the Kepler conjecture. By the 20th century, generations of mathematicians had failed to demonstrate categorically that the Kepler conjecture was true, but no one had discovered a more efficient arrangement. For all practical purposes, the conjecture was undisputed. But mathematicians demand absolute certainty, achieved by a logical series of arguments, otherwise known as a proof. Because mathematicians do not rely on experimentation nor imperfect measurement of the real world, their logic can lead to a truth that is far more certain than that which can be obtained by the other sciences. Mathematicians will not accept anything, unless it has been formally proved. This led the British sphere-packing expert C.A. Rogers to comment that the Kepler conjecture was one that "most mathematicians believe, and all physicists know." The scale of the problem can be judged by the fact that it has remained unsolved for so long. Karl F. Gauss, the most brilliant mathematician of the 19th century, failed to prove the Kepler conjecture, but he solved the two-dimensional version of the problem, finding that the best way to arrange disks in two dimensions was to surround each disk by six others. In 1900, the sphere-stacking problem was included in a hit list of 23 great unsolved problems compiled by David Hilbert. This raised the profile of the problem, but Kepler's conjecture remained inviolate. After four centuries of failure, Hales's announcement of a proof of the Kepler conjecture has been greeted with some surprise and a great deal of euphoria. Hales has been obsessed with the problem for more than a decade. To solve it, he set out to analyze one equation consisting of 150 variables, which can be changed to describe every conceivable arrangement. The challenge for Hales was to confirm that there was no combination of variables leading to a packing efficiency that was higher than that of the face-centered cubic lattice. Traditional pencil-and-paper techniques for performing this task fail because of the complexity of the equation and the large number of variables. Even computers would be confounded by a straightforward analysis of the equation. But Hales and his research student Samuel P. Ferguson discovered short cuts, then made use of great computer power to bring the problem within the realm of the possible. He announced his result on the Internet (www.math.lsa.umich.edu/Ähales) -- no arrangement beats the face-centered cubic for efficiency. Hales acknowledged that his work needed to be reviewed by other mathematicians before Kepler's conjecture officially turned into a theorem. "These results are still preliminary in the sense that they have not been refereed," he said, "but the proof is to the best of my knowledge correct and complete." The importance of refereeing was underscored in 1990, when Wu-Yi Hsiang of the University of California at Berkeley said that he had proved Kepler's conjecture. Later checking of his manuscript revealed flaws in logic, which invalidated his proof. Although Hsiang tried to correct the mistakes, the consensus was that he had failed to meet the strict demands of absolute mathematical proof. In 1993, Andrew Wiles of Princeton University announced a proof of the last theorem of the French mathematician Pierre de Fermat. Within a few weeks, colleagues pointed out a subtle error, which effectively destroyed seven years of work. But this story has a happier ending, because Dr. Wiles, collaborating with his former student Richard Taylor, bypassed the error and published a corrected proof in 1995. In the case of Hales's proof, the process of refereeing will be particularly exacting, because, in addition to the 250 pages of logic, three gigabytes of computer files must be scrutinized. Mathematicians are experienced in checking conventional mathematical arguments, but looking for errors in computer software is a relatively new part of refereeing. And errors could exist in hardware running a computer program. The first significant problem to succumb to the power of the computer was the so-called four-color conjecture, solved in 1976 by Wolfgang Haken and Kenneth Appel. In 1852, the English mathematician Francis Guthrie asserted that only four colors were necessary to color all maps so that no neighboring regions were colored the same. All the maps he examined did indeed require only four colors, but he could not be sure that there was not a map that would require five colors. Although the number of conceivable maps is infinite, Haken and Appel showed that the colorability of all these maps depended only on the colorability of a large, but finite, set of fundamental maps. Using computers, they set about testing these fundamental maps, and proved that Guthrie's conjecture was correct. But mathematicians were split over the computer proof. Some mathematicians celebrated the solution to a 19th-century problem, while others were concerned about how the certainty of such a proof could be verified. Some also worried that the computer proof lacked the elucidation of a traditional proof -- the brute-force checking of the large finite group of maps proves that Guthrie's conjecture is true, but it does not explain why. The refereeing process on the Kepler conjecture could take several months. Meanwhile, experts are generally optimistic that Hales has cracked one of the most well-known problems in mathematics. As John Conway, a mathematician at Princeton University and co-author of the standard text on sphere packing puts it: "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 quite probably right." Simon Singh is the author of "Fermat's Enigma," to be published next month in paperback by Anchor. [Mayo ClinicHealth Oasis] ----------------------------------------------------------- Home | Site Index | Site Search | Forums | Archives | Marketplace Quick News | Page One Plus | International | National/N.Y. | Business | Technology | Science | Sports | Weather | Editorial | Op-Ed | Arts | Automobiles | Books | Diversions | Job Market | Real Estate | Travel Help/Feedback | Classifieds | Services | New York Today Copyright 1998 The New York Times Company