Pentagon Packings

by Thomas Hales and Wöden Kusner

 

outice
The pentagonal ice-ray is a dense packing.

A new preprint of ours proves the pentagonal ice-ray gives a densest packing of congruent regular pentagons in the plane.  It is a computer-assisted proof that will potentially take referees months to check.  Before describing the ideas of the proof, we give some history.

Pentagon packings in history.

ceiling-pyramid-unas-closeup
Pyramid of Unas

Patterns of five-pointed stars appear in the Egyptian pyramid of Unas (Fifth dynasty, 24th century BCE).  With a little imagination, we can enclose each star in a pentagon to obtain a periodic packing of regular pentagons.

out00
Dürer’s packing
out11
Shifted layers in Dürer’s packing.

In 1525, Albrecht Dürer described some pentagon arrangements, including one that is relevant to our work. Variants of Dürer’s packing can be obtained by translating its layers. Later, Kepler produced some pentagon arrangements, but they are of limited interest to us because of their low density.

majewski-wang-lattice-page-2-image-1
Chinese window lattices

Daniel Sheets Dye, who lived in Chengdu China, spent decades of his life collecting and cataloguing Chinese lattice designs. (Here we mean lattice in an architectural rather than mathematical sense.) Lattice designs were once a pervasive part of Chinese architecture, particularly in Sichuan province, reaching an artistic pinnacle around 1900 then fading somewhat from the urban landscape.

One type of lattice designs was called the ice-ray by Chinese artisans, a name possibly derived from patterns of cracks in sheets of ice.  The pentagon packing of optimal density (shown at top) is an ice-ray design that was known to the Chinese. It first appeared in Chinese lattice work in Chengdu around 1900. Dye’s book of 1937 calls the design a masterpiece. Writing of the symmetrical ice-rays as a whole, Dye observes that

In many ways it is the finest, richest, and most chaste group of Chinese lattice we have seen. -Dye 1937

penrose tiling
A Penrose tiling
blue-dome-maragha
The blue dome of Maragha

Interest in pentagon packings exploded in the 1970s with Penrose tilings. Retrospectively, pentagonal patterns in the twelfth-century blue dome of Maragha inspired new aperiodic pentagonal patterns. Schechtman et al. observed in 1982 and published in 1984 the first evidence of quasicrystals, which were soon connected with Penrose tilings. The physics of pentagons continues to be explored, including the self-assembly of pentagonal platelets. The 2011 announcement of Schechtman’s Nobel Prize in Chemistry noted that

An important discovery that helped pave the way for the understanding of the discovery of quasicrystals was the construction and analysis by Penrose of his famous pentagonal tiling. – 2011

Directly inspired by Schechtman’s quasicrystals and Penrose tilings, Henley published an article on pentagon packings in 1986 that includes both Dürer’s packing and the pentagonal ice-ray. Referring to the pentagonal ice-ray, which he calls 8(c), he writes

The packing in 8(c) seems to be the closest packing of pentagons. Indeed in a gas of hard pentagons which was slowly frozen, we find a large single domain of Fig. 8(c) packing. -Henley

Based on the Chinese name for the packing, we call this the pentagonal ice-ray conjecture. Our research proves the conjecture.

durer to ice rayIn 1990, Kuperberg and Kuperberg made a general study of high density packings of convex bodies in the plane. They showed that any convex body can be placed in a one-parameter family of double lattice packings and proved that this family always includes the densest of all double-lattice packings. The Kuperberg family of pentagon packings undulates between the shifting layers of Dürer’s packing and the pentagonal ice-ray. Based on these results, they too made the pentagonal ice-ray conjecture. The Kuperberg bathroom floor is a pentagonal ice-ray.

Proof Strategy: Delaunay triangles

outhexcircle
A Delaunay triangle in the optimal circle packing

Our proof of the pentagonal ice-ray conjecture is a modification of Fejes Tóth’s proof of the circle-packing problem in the plane. The circle-packing problem is to show that the hexagonal circle packing has the greatest density. For purposes of studying packings of greatest density, we can assume that the packings are saturated, meaning that there is no room to add further circles. The centers of the circles in any circle packing are the vertices of a triangulation called the Delaunay triangulation.

outft
The equilateral triangle minimizes area among triangles with fixed lower edge and upper vertex in the blue region.

Smaller triangles have higher circle density. The optimality of the hexagonal circle-packing follows if we show that the area of each triangle in an arbitrary saturated packing is at least that of the equilateral triangles in the hexagonal circle-packing. If we normalize the radius of each circle to be 1, then the edges of each triangle will have length at least 2. A minimizing triangle has an edge of length exactly 2, which we place along the x-axis. The other two sides have length at least 2 and the entire triangle has circumradius at most 2. (If the triangle has circumradius bigger than 2, there is room to pack an additional circle, which is contrary to the saturation condition.) This constrains the third vertex of the triangle to lie in the blue region. There are three points in this region that minimize the area of the triangle, and all three triangles have area equal to those in the hexagonal packing. One of the three triangles is equilateral and the other two are obtuse with angles 30-30-120. This completes Fejes Tóth’s proof.

Our strategy is to adapt Fejes Tóth’s proof to the pentagonal ice-ray conjecture. We take a saturated packing of pentagons and form the Delaunay triangulation with vertices at the centers of the pentagons.

outdurertri
Some Delaunay triangles in the Dürer packing are smaller than triangles in the pentagonal ice-ray.

Almost immediately we see that the proof falls apart when applied to pentagons. In contrast with Fejes Tóth’s proof for circle packings, the Delaunay triangles in the pentagonal ice-ray do not minimize area. In fact, if we track the area of the smallest triangle as we undulate through the Kuperberg family of packings, it turns out that the pentagonal ice-ray maximizes the area of the smallest triangle, which is exactly the opposite of what we would hope for. The minimum occurs for a packing very close to the Dürer packing. (We conjecture that the triangle that minimizes area among the Kuperberg double lattices is the triangle that minimizes area among all acute Delaunay triangles in any pentagon packing.)

This problem is easily fixed by pairing up Delaunay triangles along their longest edges. We call these pairs of Delaunay triangles dimers.   Wöden Kusner started serious calculations on pentagon packings in early 2013.  His 2014 thesis contains a proof of the local optimality of the dimer in the pentagonal  ice-ray among all pentagon packings.

outobtuse
Obtuse Delaunay triangle of small area

Yet, this is not the end of our headaches. Obtuse Delaunay triangles can have alarmingly small area. To handle this problem, again we combine triangles into larger clusters and show that on average these clusters have larger area than the ice-ray triangles.  In the end, we need to consider clusters containing at most four Delaunay triangles.

 

 

outknob1
Triangle with large knob
outknob2
Triangle with small knob

Another strategy is to modify the areas of triangles slightly by adding a knob along the longest edge of some triangles and cutting a corresponding hole in the adjacent triangle, like pieces from a jigsaw puzzle. Our knobs come in two sizes of areas about 0.008 and 0.055 as shown. The larger knob is barely large enough to make the Dürer triangle with one knob slightly larger than the ice-ray triangle with no knobs or holes. Our rules permit a triangle to have at most one knob and at most three holes (one on each edge).

We prove the pentagonal ice-ray conjecture by showing that the average area of each cluster of triangles (including their knobs and holes) is at least the area of the ice-ray triangle (with no knobs or holes).

Why Pentagons?

The most natural packing problem is perhaps the problem of determining the densest packing of spheres in n-dimensional Euclidean space. The two dimensional case (circles in the plane) is easy. The three dimensional problem is hard, and the problem in 8 and 24 dimensions is remarkably deep. Outside those dimensions, the sphere packing problem is still unsolved.

After spheres, the most natural shape to consider is regular polygons in the plane. Equilateral triangles tile, so there is nothing to do here. Squares and regular hexagons also tile. The regular polygon with the fewest edges that does not tile is the pentagon. This was a natural place for us to start. (Inspired by Beth Chen’s work, we played with the problem of regular tetrahedra, but quickly retreated to pentagons.)

The next unsolved case is seven edges: regular heptagons. The local optimality of the corresponding Kuperberg double lattice has been established. Kallus conjectures that among all convex disks in the plane, the heptagon is the shape whose densest packing has lowest density.  David Mount has shown that the densest double-lattice packing of a given convex polygon can be computed in linear time in the number of edges.

Computer Calculations

In the end, the solution of the pentagon-packing problem is a hefty 60 pages of text and 5000 lines of bespoke OCaml computer code that takes about 60 hours to run on a laptop computer. We use a wonderful interval arithmetic package to control for computer roundoff errors.  The proof is computer-assisted, but is not formally verified in a proof assistant.

We use automatic differentiation to prove the local optimality of the pentagonal ice-ray. First derivative calculations show that the area of dimers decrease as they are deformed into the Kuperberg family of dimers. Second derivative calculations show among dimers in the Kuperberg family, the ice-ray dimer has least area.

One novelty is our use of meet-in-the middle algorithms to simplify the computer calculations of cluster areas. Cryptography has had a direct influence on our work, through its frequent use of meet-in-the middle algorithms (MITM) algorithms. In particular, in 2015 Hales attended a lecture by Adi Shamir at the Royal Society that described applications of MITM outside cryptography (such as the Rubik’s cube). In our approach, information from each triangle is stored separately in a hashtable, and the condition that two adjacent triangles fit together is treated as a collision in the hashtables.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s