The n-Category Café

Cool! Now I’m guessing there’s actually a continuous 1-parameter way to turn all those smoothed octagons from the first position you show to the second, while keeping their density constant.

Anyway, that’s my interpretation of the pictures from page 13 to page 19 here:

• Yoav Kallus, Worst packing shapes, July 17, 2013.

Okay, in this paper I mentioned:

• Yoas Kallus, Least efficient packing shapes.

he writes:

Reinhardt’s smoothed octagon possesses the property that its lattice packing density is achieved simultaneously by a one-parameter family of lattices (see Figure 1). In fact this property, common to all so-called irreducible domains (domains all of whose proper subdomains have admissible lattices of lower mean area), has long been a central organizing idea in the study of Reinhardt’s conjecture [16]. Therefore, it might be surprising to some that the heptagon, despite being irreducible with respect to double lattices, does not have a one parameter family of optimal admissible double lattices.

Here is part of Figure 1:

This property of smoothed octagons is clearly ‘miraculous’, and this miracle goes a long way toward persuading me that they might pessimize the packing density, even though I don’t see any logical connection! Before, I hadn’t seen what was special about them.

Ah, I’d skimmed that part of Kallus’s paper a couple of days ago, and then I managed to forget exactly what he was saying there! The next thing I was going to try to prove was that you could find packings of the smoothed octagon with equal densities that included points of contact at every point on the perimeter. Though Kallus doesn’t quite say that explicitly, I’m sure that’s what’s going on here.

Since you like making animated movies of mathematically interesting gears, I think your mission here is clear.

But I guess the lattice points on which the smoothed octagons are centered must move as the smooth octagons rotate? That would make all these ‘gears’ — except perhaps for a central fixed one — shift around in a disconcerting way as they turn.

But that could be interesting…

For those who haven’t been following Greg’s recent work on higher-dimensional gears and group representation theory, click here:

The motion of the lattice centres is quite disconcerting! But it does look plausible that those triangular-ish gaps are maintaining a constant area throughout the cycle.

Great, thanks! I’ll have to learn about the Banach–Mazur compactum; it sounds like a cool gadget.

If it’s really the quotient $Shapes/GL(2,\mathbb{R})$, we should be able to define the maximum packing density as a continuous function on it and use its compactness to see various things — for example, that this function has a minimum.

I also think it’s great that the space I was calling $Shapes$ is the moduli space of 2-dimensional Banach spaces. This makes it seem much more like a reputable mathematical object.

The point, of course, is that what I was calling a ‘shape’ is precisely the same as a unit ball for some norm on $\mathbb{R}^2$.

So, the packing pessimization problem I was discussing here, for which the smoothed octagon is the conjectured answer, can be rephrased as:

“find a norm on $\mathbb{R}^2$ that minimizes the maximum packing density”

where the packing density of a lattice $L \subseteq \mathbb{R}^2$ is the density of points that have distance $\le 1$ from some point in $L$, and the maximum packing density is maximum value of the packing density over all lattices $L \subseteq \mathbb{R}^2$ for which the nonzero lattice points have norm $\ge 2$.

And since we’re at the $n$-Category Café, I should mention that there’s also an interesting moduli stack of $n$-dimensional Banach spaces. The ‘stacky points’ are the Banach spaces with extra symmetry. Well, every Banach space has the symmetry $x \mapsto -x$, so there’s a kind of $\mathbb{Z}_2$ stackiness all over the place, but some Banach spaces have more symmetry. For example, the one corresponding to the smoothed octagon has a 16-element dihedral group acting as symmetries:

Thanks for this extra visualization, Greg, it definitely helps nail down the constant areas of the gaps. But I confess that my intuition is still failing me a little bit. I think it would help to see a bunch more rows of this rolling configuration. Do you think you’d be willing to produce a zoomed-out version of this animation? Or even an interactive version, though I recognize that’s probably more hackery than is really worthwhile…

Craig, here’s a version that’s zoomed out by a factor of three.

Greg, that’s a great visualization. Can you explain how you know the square has the same area as the triangle? Am I missing something obvious?

I wrote:

In the ordinary case when our norm comes from an inner product (aka quadratic form), does anyone know a formula to recover the density of some associated sphere packing from theta function $\Theta_L(\tau)$?

I bet the answer to this underlies the Minkowski–Hlawka bound that I mentioned. Here’s a way to get started.

We have a vector space with a lattice $L$ and a norm $\|\cdot \|$. Rescale one of them so that the shortest nonzero vector in the lattice has length $2$. Then $L$ gives a way of packing unit balls:

$$\{x : \|x - \ell\| \le 1 \} \qquad \ell \in L$$

Warning: these balls may not be round, since the norm $\| \cdot \|$ may be funny: they’re just ‘shapes’ in the technical sense I’ve defined earlier. In the 2d case they could be squares, or octagons, or smoothed octagons, etc.

Let’s calculate the density of this packing. We’ll do this by considering a huge ball of radius $R$ and counting the number $n(R)$ of lattice points inside it. Up to some small error term, the density will be $n(R)$ times the volume of a unit ball divided by the volume of the big ball. The error term will go to zero as $R \to \infty$.

Let $V$ be the volume of a unit ball. Then by what I said, the density will be

$$density = \lim_{R \to \infty} \frac{n(R) V}{R^d V}$$

where $d$ is the dimension of our vector space. The volume of the unit ball cancels out, so we get

$$density = \lim_{R \to \infty} \frac{n(R)}{R^d}$$

So, how do we calculate $n(R)$? Since I’m trying to generalize the usual relation between lattices and modular forms, I want to use the ‘theta function’ of the lattice. I’ll switch to a better convention where this is defined to be

$$\theta_L(q) = \sum_{\ell \in L} q^{\|\ell\|^2}$$

getting rid of a $\frac{1}{2}$ that infests the usual definition.

The point is now that the coefficient of $q^s$ is the number of vectors in $L$ with norm $\sqrt{s}$. So, to calculate $n(R)$, we ‘just’ take the theta function and sum the coefficients of $q^s$ for all $s$ with $s \le r^2$.

This just shows that the density of the packing can in principle be recovered from the theta function of the lattice. It’s not very practical until we can more easily do what I said we should ‘just’ do.

I’m guessing Minkowski was smart enough to extract practical consequences from this idea.

Actually, it’s even simpler than I put it.

The point that traces out the smoothed corner is midway between the two vertices that are involved in the overlap of the octagons. But the whole setup is so symmetrical that this point is also midway between the centres of the two octagons in question. That makes it much clearer that there’s no overlap as the smoothed figures rotate: the borders here are simply defined to split the difference in the distance between the octagons’ centres.

Here’s a derivation of the shape of the smoothed octagon’s corners, starting from the assumption that the packing density remains constant as the figure rotates.

Suppose we begin with regular octagons of width 2. That is, the distance from the centre to the midpoint of each edge is 1. Then if we rotate the octagons shown in the animation in the previous comment by an angle $\theta$, keeping the bottom-left octagon’s centre fixed at $(0,0)$, the bottom-right octagon’s centre will move to $(2 \sec(\theta),0)$ in order for the edges to continue to make contact along a line segment.

The top octagon’s centre will move to:

$$\left(\frac{\sec(\theta+\pi/4)}{\sqrt{2}} - \left(2\sqrt{2}-1\right)\sin(\theta), \left(2\sqrt{2}-1\right)\cos(\theta)\right)$$

in order that it also has an edge that lies flush against one of the bottom-left octagon’s edges, and that the area of the triangle formed by the three octagons’ centres remains constant.

A vector that goes halfway from the top octagon’s centre to the bottom-right octagon’s centre is given by:

$$P=\left(\sec(\theta)-\frac{\sec(\theta+\pi/4)}{2\sqrt{2}}+\left(\sqrt{2}-\frac{1}{2}\right)\sin(\theta),-\left(\sqrt{2}-\frac{1}{2}\right)\cos(\theta)\right)$$

This takes us to the point that traces out the smoothed corner of the octagon.

If we re-express $P$ in a basis that rotates along with the top octagon, with our new x-axis pointing to the vertex that overlaps with the bottom-right octagon, and we change our parameter from $\theta$ to $t=\tan(\theta)$, we obtain:

$$x(t) = \cos \left(\frac{\pi }{8}\right) t+\frac{\csc \left(\frac{\pi }{8}\right)}{4 (t-1)}+\sin \left(\frac{\pi }{8}\right)+\frac{1}{2} \csc \left(\frac{\pi }{8}\right)$$ $$y(t) = -\sin \left(\frac{\pi }{8}\right) t +\frac{\left(\sqrt{2}-1\right) \csc \left(\frac{\pi }{8}\right)}{4 (t-1)}+\sin \left(\frac{\pi }{8}\right)$$

It’s not hard to eliminate $t$ from these equations, which gives us the hyperbola:

$$y^2 = \left(3-2 \sqrt{2}\right) \left(x-\csc \left(\frac{\pi }{8}\right)\right)^2-\sqrt{2}+1$$

As we follow the parameterised curve from $t=0$ to $t=1-\frac{1}{\sqrt{2}}$, $x(t)$ returns to its starting value, and $y(t)$ to the opposite of its starting value, completing the corner.

We can’t continue to use the same functions of $\theta$ as the coordinates for the centres of the three octagons for larger values of $\theta$ than $\tan ^{-1}\left(1-\frac{1}{\sqrt{2}}\right)$, because beyond that point the bottom octagons begin to make contact along smoothed corners rather than the original flat edges. But the shape we’ve found for those smoothed corners and the symmetry of the figures guarantees that we can maintain the constant area of the triangle formed by the three octagon centres, as $\theta$ continues through a full rotation.

That’s intriguing! Is it correct that this path $\phi:[t_0,t_1]\to SL(2, \mathbb{R})$ will map a basis for the $A_2$ lattice into the 1-parameter family of optimal packings for the convex body that $\phi$ generates from the hexagon vertices?

Thomas wrote:

For example, you can continuously deform the circle into a smoothed octagon in such a way that every intermediate convex body optimally packs in a 1-dimensional family.

Nice! Watching this slowly happen while having each body rotate would be fun to see: at first it would look like nothing is happening, since a rotated circle is a circle, but at the end we’d get this:

But this would probably be unreasonably long for an animated gif.

Thanks for stopping by, and good luck on your pessimal packing project! You really tackle some hard geometry problems.

I don’t understand how a hexagon built from the tangents to the six curves can yield an optimal packing of the convex body.

Suppose $\phi:[t_0,t_1]\to\mathrm{SL}_2(\mathbb{R})$, and we construct the convex body from the six arcs $\phi(t) v_i, t\in[t_0,t_1]$, where the six vectors $v_i$ are the shortest non-zero vectors in the $A_2$ lattice, which lie on the vertices of a regular hexagon.

Then, at least for the example of the smoothed octagon, the 1-parameter family of optimal packings can be found using $2 \phi(t) A_2$ as the lattice. That’s what I used here:

In this construction, for a given value of the parameter $t$, the copy of the smoothed octagon centred at the origin makes contact with six neighbours whose centres are found simply by doubling the six vectors $\phi(t) v_i$, which lie on the perimeter of the octagon at the origin.

But I can’t see how the six tangents $\phi'(t) v_i$ relate to this. I’ve tried constructing a hexagon from these tangents and packing the plane with that hexagon, but when I do this, neither the centres nor the vertices of that packing (multiplied by any scaling factor) seem to form a lattice that gives an optimal packing for the smoothed octagon.

Oh, I was being obtuse, I understand now!

I was constructing hexagons in the tangent space, i.e. hexagons whose vertices were (proportional to) the tangent vectors to the six curves. I thought there was some mysterious duality going on that would make sense of this, but there wasn’t, I was just missing the point entirely.

The tangents that Thomas Hales was referring to are just tangent lines to the curves, and they form the sides of the hexagons that tile the plane. They are shown as dashed lines here:

Okay, I take it back—thanks!

I’ve changed the image from one based on a packing of the plane solely with hexagons to one based on a packing of the plane with hexagons and triangles. The same $A_2$ lattice underlies everything, but this way there’s a single hexagon associated with every smoothed octagon.

Are you hoping the friction between the smoothed octagons will be low enough that as you turn one or two around, the rest will follow suit and their centers will move along the paths cut out in the board?

When my friend Matt McIrvin first saw the rotating smoothed octagons, he said he imagined a horrible screeching sound. Friction might be a problem.

How would you get the octagons to rotate? (other than giving each a synchronized motor).

It may be possibler to turn each into a toothed gear (which involves even more math) and then put something like a big rubber band around a group of them to keep them in contact while the centers move around.

This is what the paths of the centres look like. This image is an SVG, and if you inspect the element on the web page you’ll see that it’s basically just a list of coordinates for a lot of points on each curve. (Fancier methods are possible where shapes are approximated with Bezier curves rather than line segments.)

You can compute as many points on these curves as you want by using the matrix $\phi(\theta)$ described here, applied to points of the form $(i, \sqrt{3} j)$ for integers $i$ and $j$, followed by a counterclockwise rotation around the origin by the angle that the vector $\phi(\theta) (1,0)$ makes with the $x$ axis; this undoes the rotation of the octagons around the central one in that version of the motion. You can get the outline of one smoothed octagon (at a scale that’s compatible with these curves) by applying $\phi(\theta)$ to each of the six vertices of a regular hexagon of radius 1, with vertices $(cos (k \pi/3), sin (k \pi/3))$ for $k=0,1,2,3,4,5$.

So getting SVG files for these things is the easy part. Getting any kind of physical version of this to work sounds like the hard part to me!

I was curious as to whether there’s a (non-pessimal) shape with a 1-parameter family of equally dense lattice packings where the lattice points follow linear paths as the shape rotates.

The answer seems to be: only piecewise-linear, as in this example.