![]() |
![]() |
There is one class of problems in geometry that is remarkably easy to state and hellishly difficult to solve. One problem in this class that is at once both especially easy to state and almost certainly impossible to solve in any practical span of time is this: How many pennies can one pack onto a rectangular table? For very small tables, the answer is strongly dependent on the exact shape of the table ...
... but as the size of the table grows, the density of the best assembly of pennies (the ratio of the area covered by the pennies to the total area of the table) has a limiting value, and the associated layout of the pennies also has a limit, as one can see from the following figure:
The maximum number of pennies one can lay out on small tables has been computed, but the difficulty of the computation grows very, very rapidly with the size of the table. For medium-sized tables, the answer will probably never be known. But if one asks about what happens for an infinite table---i.e. the whole plane---the problem becomes accessible. Nasty boundary effects are avoided. It has in fact been proved rigorously that the packing pictured above is the best possible, although the proof is by no means trivial. (The original proof was first claimed by the Norwegian mathematician A. Thue. A version of his proof can be found in a previous Feature Column on this topic.)
Very generally, one can ask similar questions about an arbitrary figure in either two or three dimensions. Recently, there has been a great deal of activity concerning the case of a regular tetrahedron in space, which is what motivated me to put together this column. The point is that in order to appreciate the recent work it helps to know earlier work in the subject, both in two and three dimensions.
From now on I'll look only at the problem of packing copies of a figure $C$ in all of the plane or all of space, rather than in a finite region such as a table top. This is called congruent packing of $C$ (as opposed to packing copies of $C$ that are allowed to be scaled). This eliminates the difficulties involved in dealing with boundary effects. But even here, certain restrictions have been imposed in order to make progress.
Convex figures. A figure in the plane or in space is said to be convex if, loosely speaking, it bulges out. The formal characterization of a convex object is that if points $P$ and $Q$ are in it then so is the entire line segment between $P$ and $Q$. Thus the figure on the left below is convex, that on the right is not.
Circles and triangles are certainly convex.
In general very little is known about the densest packing of non-convex figures, and what is known suggests that there are some peculiar phenomena lurking somewhere. So from now on I'll assume that $C$ is convex.
Lattices. The optimal packing of pennies is on a lattice spanned by two vectors in the plane:
This suggests that one consider the problem of finding optimal packings of the figure $C$ that are invariant under a lattice, or at least related to lattices. In fact, almost all that is known about dense packings relates them to lattices in one way or another.
Lattice packings. A lattice packing of a figure $C$ is one that is obtained by placing translated copies of $C$ on the points of a lattice. These are certainly much simpler to analyze than arbitrary ones. For one thing, the density of lattice packings is easy to compute---it is just the ratio of the area of $C$ to that of the parallelogram spanned by the two generating vectors. For the optimal packing of pennies it is $\pi/\sqrt{12}$. As this suggests, problems involving lattice packings generally reduce to problems dealing only with finite regions in the plane, with periodic boundary conditions.
We are thus led to the formulation of several related but distinct problems:
The theory of lattice packings was begun by Hermann Minkowski (famous for his dictum that with the discovery of relativity, time and space cease to be separate entities), and one of the basic results in the subject is rather simple and due to him. In the plane it breaks up the problem of finding densest packings clearly into simpler steps.
Allowing rotations. It is known that the densest packing of any symmetric convex figure in the plane is a lattice packing, But if $C$ is not symmetric this is of course not true, as we can see for the equilateral triangle. We must allow rotations of the figure. This changes the situation dramatically. For one thing, any triangle can be made to fill up, or tile, the plane, by first joining two copies, one a rotated version of the other, into a parallelogram:
Some other figures can also be made to tile the plane, but there are many more that cannot be made to do so. In general, the densest packing might not be obvious, and even when it does appear obvious it can be non-trivial to verify one's intuition rigorously.
Pentagons. The simplest example, which remains even now something of a mystery, is the regular pentagon. I picture below the densest known packing of regular pentagons, which is conjectured---but only conjectured---to be the densest possible.
Note that for both triangles and pentagons the densest (known) packings are obtained by placing in alternate layers the original figure and its inversion. They are examples of what the Kuperbergs call double-lattice packings. In their paper listed later, they conjecture that the densest packings of both the regular pentagon and the regular heptagon are double-lattice packings. Very little has been done on this problem.
Exercise. Read the paper by David Mount and Ruth Silverman, and then figure out the densest lattice packing of the regular pentagon.
Analogous questions can be asked about solids in three dimensions, but it is in just about all cases much more difficult to answer. Kepler conjectured that the grocers' method of stacking fruit is the optimal packing of spheres, but it was only recently that Tom Hales proved this conjecture to be correct. The cube can be made to fill space, but that is the only regular solid that does so. The simplest solid (with the possible exception of the cube) is the regular tetrahedron, which has four faces, each one an equilateral triangle, all of the same size.
Very little is known about packing regular tetrahedra in space. It was falsely asserted by Aristotle that the regular tetrahedron could tile space, but this is not correct. (In fact, it is not easy to see how he acquired this misconception, since the Greek mathematicians of his time certainly had at hand all they needed to contradict him.)
What is known is the densest lattice packing of regular tetrahedra. This is a relatively simple problem. It is one that Hermann Minkowski might have solved, and in fact thought that he had solved, but he made a simple error in his treatment.
Recently there has been a kind of race to find the densest packing of regular tetrahedra. The current leader is the recent paper by Chen, Engel, and Glotzer listed below. It is a 3D analogue of a double-lattice packing---not of copies of the regular tetrahedron, but of a closely related convex solid they call a dimer. It is assembled by gluing two regular regular tetrahedra together, face-to-face:
First these are spread out in space in layers on a lattice:
Then, layered in between these layers are placed layers of the inversion of the dimer:
In effect, we have a lattice packing of the (non-convex) union of two dimers glued together in a somewhat complicated way.
The difficult part is to figure out how to construct the original layers of dimers. After that, the inverse dimer layers are squeezed in as tightly as possible. The problem seems very difficult at first glance, but Chen et al. reduce the calculation to finding the maximum density in a relatively simple three-dimensional family of configurations that squeeze together tightly, but not necessarily in an optimal fashion. In effect, all configurations in their family are obtained from one another by sliding faces against each other in a suitable fashion.
I summarize here some of what is and is not known about packings in the plane and in space.
In 3D, the analogous question is, which tetrahedra can tile space?
This constructs a polygon (necessarily not convex) for which the densest packing is not a lattice packing.
This offers an interactive proof of Thue's theorem on packing disks.
This describes what is currently the densest packing by regular tetrahedra. An appendix (by Elizabeth Chen) contains a large and impressive collection of diagrams helping to visualize the construction.
This constructs the densest packing in space by translates of a regular tetrahedron.
This constructs double-lattice packings of convex figures in the plane, and conjectures that the ones they have found of the regular pentagon and the regular heptagon are the densest packings possible.
This is a survey, spanning over 2000 years.
This is the first systematic discussion of packing problems in space. Minkowski started out as a number theorist and came into geometry as a tool for proving theorems in this subject, which are in fact classics. But he eventually quickly fell in love with convexity as a subject of interest in itself.
This and the previous article contain explicit constructions leading to lattice and double-lattice packings of convex polygons. These were probably well known to experts, but it is very useful to have them published.
This is the classic text in English, although now somewhat out of date. It is very short. Depending on your point of view, you could call it lamentably brief or admirably succinct.
The AMS encourages your comments, and hopes you will join the discussions. We review comments before they're posted, and those that are offensive, abusive, off-topic or promoting a commercial product, person or website will not be posted. Expressing disagreement is fine, but mutual respect is required.