What’s The Worst Way To Pack?

While reading that biography of Donald Coxeter that brought up that lovely triangle theorem, I ran across some mentions of the sphere-packing problem. That’s the treatment of a problem anyone who’s had a stack of oranges or golf balls has independently discovered: how can you arrange balls, all the same size (oranges are near enough), so as to have the least amount of wasted space between balls? It’s a mathematics problem with a lot of applications, both the obvious ones of arranging orange or golf-ball shipments, and less obvious ones such as sending error-free messages. You can recast the problem of sending a message so it’s understood even despite errors in coding, transmitting, receiving, or decoding, as one of packing equal-size balls around one another.

The “packing density” is the term used to say how much of a volume of space can be filled with balls of equal size using some pattern or other. Patterns called the cubic close packing or the hexagonal close packing are the best that can be done with periodic packings, ones that repeat some base pattern over and over; they fill a touch over 74 percent of the available space with balls. If you don’t want to follow the Mathworld links before, just get a tub of balls, or crate of oranges, or some foam Mystery Science Theater 3000 logo balls as packing materials when you order the new DVD set, and play around with a while and you’ll likely rediscover them. If you’re willing to give up that repetition you can get up to nearly 78 percent. Finding these efficient packings is known as the Kepler conjecture, and yes, it’s that Kepler, and it did take a couple centuries to show that these were the most efficient packings.

While thinking about that I wondered: what’s the least efficient way to pack balls? The obvious answer is to start with a container the size of the universe, and then put no balls in it, for a packing fraction of zero percent. This seems to fall outside the spirit of the question, though; it’s at least implicit in wondering the least efficient way to pack balls to suppose that there’s at least one ball that exists.

So, take again a container the size of the universe, and put one ball in it, and that’s it, for again, a packing fraction of zero percent. We again seem to be falling outside the spirit of the question, which is the sort of thing that makes you figure more exactly what you mean by a packing. This question is, to me anyway, the heart of mathematics: the initial question is neat enough but figuring out the collection of possible answers, and how to know whether you have a good one, is the real work.

It seems to me what we’re assuming, as part of the ball packing, is that we have some arrangement of balls that reach from one end of the container to another, and that there are enough balls to lead in a continuous chain from one end to another. If we put those requirements in, then we probably come up with packings, efficient and inefficient, that get to the spirit of what efficient and inefficient packings are.

The obvious candidate to me seemed to be what’s called the cubic lattice: arrange the balls in rows and columns as if they were cubes all of the same size, for which it’s easy to see that only π/6 or about 52 percent of the available space will be filled with balls. Perhaps other arrangements based on nice simple shapes like cubes would do well at packing inefficiently too; and, yes, that turns out to be so. Mathworld notes that, according to Hilbert and Cohn-Vossen, a tetrahedral lattice — the kind of lattice that carbon atoms in a diamond form — has a packing fraction of just over 34 percent, which is impressively little, barely a third of its space being the balls.

And yet it turns out we can do worse. In 1966’s New Mathematical Diversions Martin Gardner brought to the Internet’s vague attention a 1933 result by Dutch mathematicians Heinrich Heesch and Fritz Laves which manages a packing fraction of just over five and a half percent. This pattern has incredible amounts of empty space, and looks more like a cobweb or a lace curtain made of spheres rather than, like, a stack of oranges. I find a handful of pictures of this Heesch-Laves packing, although not ones that I can too easily link to directly. The 3doro.de web site I just linked to, though, has a couple shapes that appear to pack even worse, including one made apparently of a string of diamonds with a packing fraction under three and a half percent, for which, unfortunately, I don’t know a name.

I could imagine coming around to the tetrahedral lattice, but I’m not sure I would have gotten to this Heesch-Laves sort of loose packing anytime soon. It doesn’t seem like, if you could set up a set of oranges or golf balls in this configuration, that they wouldn’t immediately fall apart under their own weight, but then, is that a necessary part of a packing? Am I right in thinking they would fall immediately apart? (I’m not right, if I understand my reading correctly: the Heesch-Laves shape at least would stand if you could build it, though I wouldn’t sneeze near it. I don’t have any information about that even emptier configuration mentioned after it.) Should we add in “must be stable” to the requirements? (If we shouldn’t, then, wouldn’t just three lines of balls, one for each spatial dimension, suffice, and give us as tiny a packing fraction as you like just by making the balls small enough?)

So I ended up surprised when I went looking for more information about the question, but after all, isn’t being surprised what questions are for?