The n-Category Café (2024)

You see, in 2 dimensions the disk is not the worst. The disk has maximum packing density of

$$\frac{\pi}{\sqrt{12}} = 0.9068996 \dots$$

However, the densest packing of regular octagons has density

$$\frac{4 + 4 \sqrt{2}}{5 + 4 \sqrt{2}} = 0.9061636 \dots$$

This is a tiny bit less! So, the obvious 2-dimensional analogue of Ulam’s packing conjecture is false.

By the way, the densest packing of regular octagons is not the one with square symmetry:

It’s this:

which is closer in spirit to the densest packing of discs:

The regular octagon is not the worst convex shape for packing the plane! Regular heptagons might be even worse. As far as I know, the densest known packing of regular heptagons is this ‘double lattice’ packing:

studied by Greg Kuperberg and his father. They showed this was the densest packing of regular heptagons where they are arranged in two lattices, each consisting of translates of a given heptagon. And this packing has density

$$\frac{2}{97}\left(-111 + 492 \cos\left(\frac{\pi}{7}\right) - 356 \cos^2 \left(\frac{\pi}{7}\right)\right) = 0.89269 \dots$$

But I don’t know if this is the densest possible packing of regular heptagons.

Unlike the heptagon, the regular octagon is centrally symmetric: if we put its center at the origin, a point $x$ is in this region iff $-x$ is in the region.

The great thing about convex centrally symmetric regions of the plane is that their densest packing is always a lattice packing: you take your region $R$ and form a packing by using all its translates $R + L$ where $L \subseteq \mathbb{R}^2$ is a lattice. This is an old result of László Fejes Tóth and C. A. Rogers. For convex centrally symmetric regions, it reduces the search for the densest packing to a finite-dimensional maximization problem!

I said the regular octagon wasn’t the worst convex shape for densely tiling the plane. Then I said the regular heptagon might be worse, but I didn’t know. So what’s worse?

A certain smoothed octagon is worse:

Since it’s centrally symmetric, we know its densest packing is a lattice packing, so it’s not miraculous that someone was able to work out its density:

$$\frac{ 8-4\sqrt{2}-\ln{2} }{2\sqrt{2}-1} = 0.902414 \dots$$

and the way it looks:

In fact this shape is believed to be the worst centrally symmetric convex region for densely packing the plane! I don’t really know why. But Thomas Hales, who proved the Kepler conjecture, has an NSF grant based on a proposal where he says he’ll prove this:

In 1934, Reinhardt considered the problem of determining the shape of the centrally symmetric convex disk in the plane whose densest packing has the lowest density. In informal terms, if a contract requires a miser to make payment with a tray of identical gold coins filling the tray as densely as possible, and if the contract stipulates the coins to be convex and centrally symmetric, then what shape of coin should the miser choose in order to part with as little gold as possible? Reinhardt conjectured that the shape of the coin should be a smoothed octagon. The smoothed octagon is constructed by taking a regular octagon and clipping the corners with hyperbolic arcs. The density of the smoothed octagon is approximately 90 per cent. Work by previous researchers on this conjecture has tended to focus on special cases. Research of the PI gives a general analysis of the problem. It introduces a variational problem on the special linear group in two variables that captures the structure of the Reinhardt conjecture. An interesting feature of this problem is that the conjectured solution is not analytic, but only satisfies a Lipschitz condition. A second noteworthy feature of this problem is the presence of a nonlinear optimization problem in a finite number of variables, relating smoothed polygons to the conjecturally optimal smoothed octagon. The PI has previously completed many calculations related to the proof of the Reinhardt conjecture and proposes to complete the proof of the Reinhardt conjecture.

This research will solve a conjecture made in 1934 by Reinhardt about the convex shape in the plane whose optimal packing density is as small as possible. The significance of this proposal is found in its broader context. Here, three important fields of mathematical inquiry are brought to bear on a single problem: discrete geometry, nonsmooth variational analysis, and global nonlinear optimization. Problems concerning packings and density lie at the heart of discrete geometry and are closely connected with problems of the same nature that routinely arise in materials science. Variational problems and more generally control theory are have become indispensable tools in many disciplines, ranging from mathematical finance to robotic control. However, research that gives an exact nonsmooth solution is relatively rare, and this feature gives this project special interest among variational problem. This research is also expected to further develop methods that use computers to obtain exact global solutions to nonlinear optimization problems. Applications of nonlinear optimization are abundant throughout science and arise naturally whenever a best choice is sought among a system with finitely many parameters. Methods that use computers to find exact solutions thus have the potential of finding widespread use. Thus, by studying this particular packing problem, mathematical tools may be further developed with promising prospects of broad application throughout the sciences.

I don’t have the know-how to guess what Hales will do. I haven’t even read the proof of that theorem by László Fejes Tóth and C. A. Rogers! It seems like a miracle to me.

But here are some interesting things that it implies.

Let’s say a region is a relatively compact open set. Just for now, let’s say a shape is a nonempty convex centrally symmetric region in the plane, centered at the origin. Let $Shapes$ be the set of shapes. Let $Lattices$ be the set of lattices in the plane, where a lattice is a discrete subgroup isomorphic to $\mathbb{Z}^2$.

We can define a function

$$density: Shapes \times Lattices \to [0,1]$$

as follows. For each shape $S \in Shapes$ and lattice $L \in Lattices$, if we rescale $S$ by a sufficiently small constant, the resulting shape $\alpha S$ will have the property that the regions $\alpha S + \ell$ are disjoint as $\ell$ ranges over $L \subseteq \mathbb{R}^2$. So, for small enough $\alpha$, $\alpha S + L$ will be a way of packing the plane by rescaled copies of $S$. We can take the supremum of the density of $\alpha S + L$ over such $\alpha$, and call it

$$density(S,L)$$

Thanks to the theorem of László Fejes Tóth and C. A. Rogers, the maximum packing density of the shape $S$ is

$$\sup_{L \in Lattices} density(S,L)$$

Here I’m taking advantage of the obvious fact that the maximum packing density of $S$ equals that of any rescaled version $\alpha S$. And in using the word ‘maximum’, I’m also taking for granted that the supremum is actually attained.

Given all this, the pessimization problem for packing centrally symmetric convex regions is all about finding

$$\inf_{S \in Shapes} \; \sup_{L \in Lattices} density(S,L)$$

But there’s more nice symmetry at work here. Linear transformations of the plane act on shapes, and lattices, and packings… and the concept of density is invariant under linear transformations!

One thing this instantly implies is that the maximum packing density for a centrally symmetric convex region doesn’t change if we apply a linear transformation to that region.

This is quite surprising. You might think that stretching or shearing a region could give a radically new way to pack it as densely as possible. And indeed that’s probably true in general. But for centrally symmetric convex regions, the densest packings are all lattice packings. So if we stretch or shear the region, we can just stretch or shear the lattice packing that works best, and get the lattice packing that works best for the stretched or sheared region. The packing density is unchanged!

We can say this using jargon. The group of linear transformations of the plane is $GL(2, \mathbb{R})$. This acts on $Shapes$ and $Lattices$, and for any $g \in GL(2, \mathbb{R})$ we have

$$density(g S, g L) = density(S,L)$$

So, the function

$$density: Shapes \times Lattices \to [0,1]$$

is $GL(2,\mathbb{R})$-invariant. And thus, the maximum packing density is invariant:

$$\sup_{L \in Lattices} density(S,L) = \sup_{L \in Lattices} density(g S,L)$$

for all $g \in GL(2,\mathbb{R})$.

As mentioned before, we also have

$$density(\alpha S, L) = density(S, L)$$

where $\alpha$ is any nonzero scalar multiple of the identity matrix (and thus a rescaling if $\alpha > 0$). So, we can replace $Shapes$ by the quotient spaces $Shapes/\mathbb{R}^*$, and work with

$$density: Shapes/\mathbb{R}^* \times Lattices \to [0,1]$$

$GL(2,\mathbb{R})$ still acts on the first factor here, with scalar multiples of the identity acting trivially, and this map is still $GL(2,\mathbb{R})$-invariant.

I think there should be a topology on $Shapes$ that makes the quotient space $Shapes/\mathbb{R}^*$ compact and makes

$$density: Shapes \times Lattices \to [0,1]$$

continuous. Something like the Hausdorff metric, maybe. Can anyone help me here?

None of this goes far in solving the packing pessimization problem for convex centrally symmetric regions in the plane. We’ve reduced the number of degrees of freedom, but they’re still infinite.

But still, it’s fun. I like how it’s vaguely reminiscent of the theory of modular functions, which can be seen as $SL(2,\mathbb{R})$-invariant functions of a lattice together with an ellipse centered at the origin.

References and Addenda

For more on packing pessimization problems, see:

• Yoav Kallus, Least efficient packing shapes.

To see who drew the pretty pictures, click on the pictures.

There’s a lot of good stuff in the comments. Most notably:

• The set $Shapes/GL(2,\mathbb{R})$ has a nice topology making it a compact space. This is the moduli space of 2-dimensional real Banach spaces! In general, the moduli space of $n$-dimensional real Banach spaces is called a Banach–Mazur compactum; click the link for details on its topology.

• Amazingly, there is a one-parameter family of maximally dense packings of the smoothed octagon! Greg Egan has made a movie showing all these packings:

As the smoothed octagons turn, their centers move but the area in each space between them stays the same!