Can You Do Better?
Recently, there has been a great deal of activity concerning the case of packing regular tetrahedra in space, which is what motivated me to put together this column...
Bill Casselman
University of British Columbia, Vancouver, Canada
Email Bill Casselman
Introduction
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.
A hierarchy of difficulty
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:
-
Which lattice packings of $C$ have the highest density?
-
Under what circumstances is the densest packing of $C$ a lattice packing?
-
Are there modifications of lattice packings that also give rise to densest packings?
A convex figure $C$ is called
symmetric if $C = -C$. This means that if if $c$ is in $C$ then so is $-c$. Thus a regular hexagon is symmetric, but a regular pentagon is not. The main result about dense plane packing is that
if $C$ is symmetric then its densest packing is a lattice packing.
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.
-
Any lattice packing of $C$ must be permissible in the sense that all translates of $C$ on the lattice are disjoint from each other. There is a very simple criterion for whether this happens or not. The Minkowski sum of two regions $C$ and $D$ is the set of all vectors $c + d$ with $c$ in $C$ and $d$ in $D$. In practice it is quite feasible to compute it. If $C$ and a translate $C + v$ with $v \ne 0$ in the lattice overlap, there exists $c$ and $d$ in $C$ such that $c + v = d$, or equivalently there exists $v \ne 0$ in the lattice and also in the difference $D = C - C$, which contains $0$ and is symmetric. The lattice is permissible if and only if the only point of the lattice in $D$ is $0$. The set $D$ is not only the difference set of $C$, but also of $D/2$, which is also symmetric. Therefore a lattice is permissible for $C$ if and only if it is permissible for $D/2$, which is symmetric. Densest packings of $C$ and $D/2$ also correspond.
-
This allows one, for some purposes, to assume $C$ symmetric, which generally simplifies things. Sometimes it renders them remarkably easy. For example, suppose $C$ to be an equilateral triangle, which we can assume to be centred at the origin. Its difference set $D = C-C$ is a regular hexagon, as is $(1/2)D$. A regular hexagon tiles the plane, and the optimal packing for $C$ is determined by that:
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.
Comments?
Packing tetrahedra in three dimensions
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.
Comments?
Open questions
I summarize here some of what is and is not known about packings in the plane and in space.
-
There exist non-convex figures for which the densest packing is not a lattice packing.
-
The densest packing for a symmetric convex figure is a lattice packing.
-
Efficient algorithms to find the densest lattice packing or double-lattice packing of an arbitrary convex polygon can be found in the papers by David Mount and Ruth Silverman listed below.
-
It is conjectured but not known that the densest congruent packing of regular pentagons is the double-lattice packing pictured earlier.
-
The densest lattice packing of a regular tetrahedron is described in the paper by Hoylman listed below.
-
The densest packing of a regular tetrahedron is not known, although the paper by Chen et al. constructs a candidate. It has density 4000/4671.
There are two other related problems, about as easy to state and as difficult to solve, as the packing problem: covering and tiling. The first asks, how efficiently can one cover the plane by copies of a given figure $C$? It is in a sense dual to the packing problem, and receives about as much attention, but I shan't say anything more about it. The second is, given a figure $C$, can we cover the plane or space by copies of it whose interiors do not intersect? I have shown above that any triangle can be made to tile the plane, and in fact any quadrilateral can be made to tile the plane, as well. The major open question in the subject is,
which pentagons can tile the plane?
In 3D, the analogous question is, which tetrahedra can tile space?
Acknowledgements
I wish to thank Beth Chen and Greg Kuperberg for much help, with the usual proviso that if I have misunderstood them it is my fault, not theirs.
Where to read more
Web sites
Books and journal articles
-
A. Bezdek and G. Kertesz, Counter-examples to a packing problem of L. Fejes Toth, pp. 29--36 in the book Intuitive Geometry, North Holland Publishing Company, 1985.
This constructs a polygon (necessarily not convex) for which the densest packing is not a lattice packing.
-
Bill Casselman, Packing pennies in the plane. A previous AMS Feature Column.
This offers an interactive proof of Thue's theorem on packing disks.
-
Elizabeth Chen, Michael Engel, and Sharon Glotzer, Dense crystalline packings of regular tetrahedra, Discrete and Computational Geometry 44 (2010), 253-280.
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.
-
Douglas J. Hoylman, The densest lattice packing of tetrahedra, Bulletin of the American Mathematical Society 76 (1979), 135-137.
This constructs the densest packing in space by translates of a regular tetrahedron.
-
G. Kuperberg and W. Kuperberg, Double-lattice packings of convex bodies in the plane, Discrete and Computational Geometry 5 (1990), 389-397.
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.
-
Jeffrey Lagarias and Chuanming Zong, Mysteries in packing regular tetrahedra, in the December issue of the Notices of the American Mathematical Society.
This is a survey, spanning over 2000 years.
-
Hermann Minkowski, Dichteste gitterförmige Lagerung kongruenter Körper, pages 311-355 in the 1904 volume of the Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen.
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.
-
David Mount, The densest double-lattice packing of a convex polygon, pp. 245-261 in Volume 6 of the DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1981.
-
David Mount and Ruth Silverman, Packing and covering the plane with translates of a convex polygon, Journal of Algorithms 11 (1990), 564-580.
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.
-
C. A. Rogers, Packing and covering, Cambridge University Press, 1964.
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.
Bill Casselman
University of British Columbia, Vancouver, Canada
Email Bill Casselman
