Somebody help me remember here please: In fcc lattices the (111) planes are
stacked abcabcabc, but isn't there a hex lattice which has the comparable
planes stacked abababab -- which has the same stacking efficiency? Why=
don't
mathematicians ever talk to physicists? =20
Jim Green
----------------------
August 25, 1998, Tuesday Section: Science Desk
Mathematics 'Proves' What the Grocer Always Knew
By SIMON SINGH
THIS 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, Dr.
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 Dr. 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, Dr. Hales's announcement of a proof of the
Kepler conjecture has been greeted with some surprise and a great deal of
euphoria. Dr. 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 Dr. 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 Dr. 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.
Dr. 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 Dr. 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 Dr. 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, Dr. Haken and Dr.
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 Dr. 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.''