Grocers stacking oranges demonstrate intuitive grasp of sphere-packing math
They may not know it, but grocers face some of the most difficult questions in mathematics when stacking produce each day.
Four centuries ago, the astronomer and mathematician Johannes Kepler guessed that the standard grocers’ method of piling oranges packs the most fruit into the least space. Confirming he was right had to wait until 1998, when mathematician Thomas Hales of the University of Pittsburgh, working with his student Samuel Ferguson, proved Kepler’s conjecture with the aid of 180,000 lines of computer code.
But even that achievement didn’t settle all the grocers’ dilemmas. Researchers have known that other sphere-stacking methods can be equally dense. So how does one recognize when a stack is the densest possible? A partial answer appears in a paper posted October 3 at arXiv.org.
Back in 1969, Hungarian mathematician László Fejes Tóth thought he’d figured out one simple method: If each sphere is in contact with as many others as possible, the packing would be the densest achievable. But he couldn’t prove it, and even the techniques that Hales and Ferguson used to settle the formidable Kepler conjecture weren’t powerful enough to crack it. But now Hales himself has shown that Tóth’s guess was accurate.
“This is really a major advance,” says Henry Cohn of Microsoft Research in Cambridge, Mass. “As with the Kepler conjecture, if you mess around with ping-pong balls, you can convince yourself that there isn’t another way to do it. But proving it is another matter entirely.”
Tóth started with what mathematicians call the “kissing number.” Imagine placing a penny on a table and putting as many pennies as you can touching it — or, in mathematical parlance, “kissing” it. You’ll find that exactly six pennies fit, forming a hexagonal pattern. As a result, the kissing number in two dimensions is six. This pattern can be extended to cover the entire table, with each penny surrounded by six others.
Now do the same thing in three dimensions: Take an orange and arrange as many oranges as possible kissing it. It turns out that you can’t fit more than 12, so the kissing number in three dimensions is 12. Unlike with pennies, though, the 12 oranges won’t fit snugly around the central one; there’s a bit of room to spare, so the oranges can jiggle into different positions. As a result, if you extend this pattern out to fill space, with each ball surrounded by 12 others, the jiggliness will give you a lot of choices about how to arrange the balls.
Tóth’s idea was that no matter what choices you make, the balls will have the densest possible packing — that is, their arrangement will fit the most oranges possible into a given space. Furthermore, he figured that he knew every possible arrangement the oranges could have: They’d all be variations on the way grocers do it. In particular, they would be arranged in layers, and each layer would have a hexagonal pattern just like the pennies.
Grocers stack fruit by laying the bottom row of the bottom layer first. They then put the next row in the crevices between the oranges of the first row, the following row in the crevices of the second row, and so on. This process ends up creating a hexagonal pattern, with each orange touching six others in its layer. The next layer goes in the pockets created between the oranges in the first layer. But only half the pockets are filled, because placing an orange in every pocket would force the oranges to overlap. So the grocer has a choice of which of the two sets of pockets to fill with each layer. This means that there are infinitely many possible ways to stack the oranges (assuming, of course, that you start with an infinite orange supply). The upshot of Tóth’s guess is that if each orange touches 12 others, then the overall packing must be laid according to this pattern.
Hales’ confirmation, available at http://arxiv.org/abs/1110.0402, grew out of his effort to settle a lingering uncertainty about his proof of the Kepler conjecture. Because that proof relied on such extensive computer code, mathematicians couldn’t guarantee that no hidden bug had led to an error. Inspired by the way that Georges Gonthier of Microsoft Research verified his proof of a different theorem, Hales has been formally checking his own work by spelling out each step explicitly and using a computer to check the logical deductions. “The constraints of doing everything rigorously force you to understand the structure of a problem and simplify it,” Gonthier says. “And in this case, that led to a very nice advance.”
