Bad Packings

Thomas C. Hales (Pittsburgh)

[This blog post is based on a colloquium I gave in the Pitt math department on February 3, 2017. The arXiv paper (1703.01352) giving technical details appeared March 7, 2017.]

Some shapes fill the plane more efficiently than others.

For example, some shapes tile the plane, so that there is no unoccupied space. Shapes that tile include the equilateral triangle, the square, the parallelogram, and the regular hexagon. Fish also tile the plane, as shown by Escher.

Shapes that do not tile the plane include circles and pentagons. It is known that the optimal density of a circle packing in the plane is \pi/\sqrt{12}\approx 0.9069. The pentagon packing problem was solved by Kusner and me in 2016. The optimal density is about 0.921.

When studying optimal packing densities, we exclude non-convex disks because otherwise we could hollow out the interior of the disks so that its best packing has arbitrarily small density. For example, hollowed out squares have low packing density.

hollow_square

Central Symmetry

A region in the plane is centrally symmetric if it is the same when rotated by 180 degrees. A camel is not centrally symmetric because we can tell which camel is upside down. Similarly,  triangles and generic quadrilaterals are not centrally symmetric.

Circles and parallelograms are centrally symmetric. Escher’s hands give an algorithm for drawing centrally symmetric figures.

Enter Reinhardt

This blog post is about the problem of bad packings: what centrally symmetric convex disk in the plane has the property that its densest packing is the worst? Reinhardt asked this question and conjectured an answer in 1934. The conjecture is still open.

The problem can be described as follows. A contract stipulates that a miser must make a payment with a tray of identical gold coins filling the tray as densely as possible. The contract requires the coins to be convex and centrally symmetric. What shape coin should the miser choose to part with as little gold as possible?

The answer is not a pentagon for two reasons: its best packing beats the circle, and because the pentagon is not centrally symmetric.

Tiling with hexagons

Centrally symmetric hexagons are obtained by cutting two opposite corners from a parallelogram.  Centrally symmetric hexagons always tile the plane.

hexagonally-symmetric

Fejes Toth found the best way to pack any centrally symmetric disk: put it in the smallest possible centrally symmetric hexagon, then tile the plane with the hexagons. (In degenerate cases, the hexagon might become a parallelogram.)  Reinhardt himself only considered lattice packings when he formulated his problem, but because of Fejes Toth’s result, the non-lattice and lattice densities are the same, so this does not matter.

The density is the ratio of the area of the disk to the area of the hexagon. This ratio is not affected by rescaling both the disk and the hexagon by the same factor. To normalize the problem, we rescale the hexagons so that they have area \sqrt{12}. This is convenient because it is the area of the smallest centrally symmetric hexagons that contain a circle of radius 1.

We see that Fejes Toth’s strategy works for circles: we obtain the densest packing of circles by fitting each circle as tightly as possible into a hexagon, then tiling the hexagons.

Could the answer to the Reinhardt problem be long and skinny, like the ellipses shown below? A simple argument allows us to restrict to disks that are close to circular. An invertible linear transformation of the plane does not change the ratio of areas (and hence the density). A linear transformation can be applied to make answer to the Reinhardt problem nearly round. In fact, by linear transformations, without loss of generality the boundary of the disk solving the Reinhardt problem passes through the six vertices of a regular hexagon.

ellps

Clipping Squares down to Octagons

Here is how Reinhardt might have discovered his conjecture. One way to search for the worst disk is to start with a square and start cutting away unneeded portions (in a centrally symmetric way). Let’s cut away two opposite corners. This doesn’t help, because a square with two clipped corners is a centrally symmetric hexagon and still tiles.

So let’s cut away all four corners of a square. As we cut away more and more from the corners,  its best packing density becomes worse and worse. Except if we cut away too much, we get smaller square and we are back where we started. So let’s stop midway at an octagon. Small further improvements are possible if you make tiny clips at the corners to smooth out the corners of the octagon.

Reinhardt’s conjecture (1934): The smoothed octagon is the worst centrally symmetric shape for packing.

This conjecture is still open.

Reinhardt made an important observation. A shape can be clipped further (and so is not the worst) unless a centrally symmetric hexagon of smallest area passes through each point of the boundary. Reinhardt conjectured that the optimal smoothing of the corners is by arcs of hyperbolas.

smoothed_octagon1

This means that the solution to the Reinhardt problem, whatever it is, is hexagonally symmetric in this sense: each point on the boundary can be associated with five other points, for a total of six points.  If we take any of these sets of six points and draw the tangents to the curve at these six points, we get a centrally symmetric hexagon, and its area does not depend on the six points.  We can imagine this as an Escher print with six hands in a ring drawing the figure.

The smoothed octagon has this hexagonal symmetry. (Hexagonal symmetry is a surprising property of an octagon.)  To draw the smoothed octagon with six hands, at any moment, two opposite hands are drawing rounded corners and the remaining four hands are drawing straight edges.    Greg Egan has produced some spectacular animated graphics of this.  The density of the packing does not change as the smoothed octagons roll.

egan_octagon_gears

The circles roll in a circle packing in the similar way as the smoothed octagons roll in a packing, except that as the circles roll, there is no visual change in the packing because of their symmetry.

Digression: Ulam conjecture

We can ask the same question in three dimensions: what is the worst shape for packing?

Ulam conjectured that in three dimensions the sphere is the worst shape for packing. Nobody knows if this is true (but some recent progress has been made). The conjecture first became known through a column by Martin Gardner.

Why is the Ulam problem hard? You first have to solve the sphere packing problem to know the density of sphere packings. Then you have to show everything else is worse.  In that sense, the Reinhardt/Ulam problem is much harder than any packing problem.

The sphere packing problem has only been solved in dimensions 2,3,8,24. (For more about packings in 8 and 24 dimensions, see Cohn’s article.)

Some non-Euclidean geometry

(I’m going to make a few digressions, but we will eventually tie up the loose ends.)

In his Elements, Euclid proposed the parallel postulate for the geometry of the plane: given a line L and a point not on that line, there exists a unique line through the point that is parallel to L.

Students of Euclid tried for centuries to give a proof of the parallel postulate. Finally, mathematicians started to believe that no proof of the parallel postulate is possible.

To prove that no proof of the parallel postulate is possible, it was necessary to construct a model of non-Euclidean geometry. In these models, all of the fundamental postulates hold except for the parallel postulate, which fails. In these models, the meaning of primitive terms such as point and line is changed.

Eventually several models of non-Euclidean geometry were found.

The first was the upper-half plane. A second model is the open unit disk. A third model is a branch of the hyperboloid.  As it turns out, all three of these models are useful for the Reinhardt problem.

Dubins car problem

Here is a seemingly unrelated problem in the plane that will turn out to be the key to understanding the Reinhardt conjecture.

The Dubins problem is to take a car that is at a certain position and direction in the plane and navigate it to an ending position and direction in such a way that the absolute value of the curvature of the path is at most 1, and to find the shortest such path.  (See the illustration below.)

In 1957, Dubins showed that the shortest path always consists of straight segments and segments of maximum curvature. According to Wikipedia,

The Dubins path is commonly used in the fields of robotics and control theory as a way to plan paths for wheeled robots, airplanes and underwater vehicles.

Let us juxtapose a solution to the Dubins car problem with its straight edges and circular arcs and a few segments of a smoothed polygon (with its straight edges and hyperbolic-arc-rounded corners). See any similarity?

dubins_vs_polygon

Dubins car solutions have straight segments and segments of maximum curvature.

Reinhardt’s smoothed octagon has straight segments and segments of maximum curvature, subject to the hexagonal symmetry constraints. (It is an easy fact that the segments of maximum curvature subject to hexagonal symmetry constraints are exactly arcs of hyperbolas.)  We can think of Reinhardt’s problem as a variant of Dubins car problem, where hexagonal symmetry is imposed and the steering wheel turns only to the left.

We now have a well-defined research program to resolve the Reinhardt conjecture: solve the Reinhardt conjecture in the same way that the Dubins car problem was solved.

I’m willing to bet that this 1934 conjecture will soon be solved because of this connection with the Dubins car problem.

Here are some features of the Dubins car problem (and now features of the Reinhardt problem).

  • It is a problem in optimal control theory. Until recently noticing the analogy with Dubins, we did not even know that the Reinhardt problem is an optimal control problem.  It was misclassified for decades as a problem in discrete geometry, which impeded progress towards a solution.
  • It is a bang-bang solution.
  • It is studied using Pontryagin’s maximum principle (PMP). In particular, the smoothed octagon is a Pontryagin extremal.

I will explain each of these points in turn.

A Problem in Optimal Control Theory

An optimal control problem has the form of minimizing the cost of x, where x is a solution to a differential equation that depends on a control function u.  The problem of optimal control is to pick the control function u, such that after solving the differential equation for x with given boundary conditions, the cost of x is minimized.

To make this concrete, here is an example of a control problem that we take from non-Euclidean geometry.

The solution x to the differential equation will be a path in the hyperboloid model of non-Euclidean geometry.  We take the cost of x to be the number we get by integrating the height function on the hyperboloid along the path x.

We take the control function u:[0,T]\to U to take values in an equilateral triangle (shown here with a control stick).  The differential equation is shown, and the coefficients (a,b,c) depend on the control u.

ode-hyperbolic

Here is the connection between the Reinhardt problem and non-Euclidean geometry.

Theorem: The solution to this optimal control problem in non-Euclidean geometry gives the solution of the Reinhardt problem. 

The connection between non-Euclidean geometry and bad packings comes through the group SL(2,R) which acts on both the Euclidean and non-Euclidean planes.

In particular (and quite remarkably) the integral of the height function on the hyperboloid is equal to the area of the convex disk D in the plane (up to a fixed constant 1.5).

Also,  the motion along the path x gives the animation of the rolling disks D (in Egan-style animations).

Bang-bang controls

Suppose U is a convex set. A bang-bang control u:[0,T]\to U is one that take values in the set of extreme points of U. A feature of many optimal control problems is that the control that minimizes cost is a bang-bang control.

Here are some standard examples of bang-bang solutions.

Parking a car in a garage in minimal time

The optimal control problem is to park a car in a garage in minimal time.  The car is directly in front of the garage so no turning is needed.  There is a single control variable with range [-1,1] for acceleration (negative values for the break pedal and positive values for the gas pedal).  The optimal solution is bang-bang: to park a car as fast as possible, floor the gas pedal, driving at reckless speed towards the garage. Then just at the moment when  crashing into the back wall of the garage seems inevitable, slam on the breaks, coming to a screeching halt just as the front bumper touches the wall.

Think of bang-bang control as the extreme stuff of Hollywood movies: the bomb that is deactivated just as the timer is reaching zero; the getaway car that evades police on its tail by flying across the train track the instant before the long freight train blocks all further traffic; and the lover who professes love and saves the imperiled relationship when it is all but too late.  (In fact, Bang-Bang is a film title.)

Dubins Car Problem

The circular segments in the Dubins car problem are given by bang-bang controls: the signed curvature is as large or as small as possible.  (However,  The straight-edge segments in Dubins care problem are not bang-bang.  They are called singular arcs.)

Optimal investment strategies

Think of bang-bang optimal financial strategies as the Bill Gates lifetime investment strategy.   Bill Gates the Microsoft CEO ruthlessly builds a corporate empire. Then bang, positions change, and Bill and Melinda Gates the philanthropists plan to donate 95 percent of their wealth to charity.

Many financial investment strategies come as solutions to control problems, jumping from one extreme position to another in an optimal way, according to a bang-bang control.

The smoothed octagon has a bang-bang control

The smoothed octagon has a bang-bang control with finitely many switches.  The smoothed octagon is divided into segments, each of which is  as straight as possible or as curved as possible, with abrupt transitions between the segments.  In terms of the control triangle U described above, the control remains at one vertex for a time, then suddenly jumps to another vertex, and so on.

Enter Pontryagin

Pontryagin gave some necessary conditions that the optimal solution to a control problem must have.

Pontryagin’s conditions are similar to the method of Lagrange multipliers taught to calculus students.  The typical problem is to minimize a function f of x subject to constraints G(x)=0. Lagrange tells us to write \lambda_0 f + \lambda\cdot G with Lagrange multipliers: (\lambda_0,\lambda).  (Generally, \lambda_0=1 and is omitted, but for optimal control which we turn to next, it cannot be omitted.)

The approach is to calculate all critical points and to pick the best. The computation of the multipliers is part of calculating the critical points.

The same idea applies to optimal control, with some small adaptations.  The function f to be minimized is called the cost.  Now, x is a path rather than a point in Euclidean space, and the constraints G(x)=0 are differential equations.  No matter.  Now the multiplier \lambda is also a path rather than a point in Euclidean space, and is itself a solution to a differential equation.

The multiplier \lambda takes values in the cotangent bundle T^*M of M=SL(2) x H, where H is the hyperboloid model.   Cotangent bundles of manifolds are examples of symplectic manifolds, and we can specify the differential equation that \lambda satisfies by giving a real-valued function h on T^*M, called the Hamiltonian.  (Recall that a function h on  has a differential dh, which becomes a vector field on T^*M using the canonical symplectic form.  The integral curves \lambda of that vector field are the solutions to the differential equation.)

Pontryagin maximum principle is a list of  necessary conditions for optimality.  These conditions include an explicit Hamiltonian, which is used to describe the differential equation \lambda must satisfy.  We call \lambda a Pontryagin extremal if it satisfies all the necessary conditions enumerated in the Pontryagin maximum principle.

Theorem: The smoothed octagon is a Pontryagin extremal.

Theorem: The smoothed octagon is a (micro) local minimum.

By micro-local, I mean that the neighborhoods we consider are in the cotangent bundle.

The differential equations are solved exactly and explicitly in Mathematica as part of the proofs. We have used a second derivative test of local minimality.  Briefly put, interval arithmetic was used on a computer to show that the second derivative is positive.

There are in fact infinitely many Pontryagin extrema (smoothed 6k+2-gons) converging to the circle of radius 1. The circle is also a Pontryagin extremal trajectory (a singular arc).  A switch in a bang-bang solution is defined as the jump that the control function u makes from one extreme point of the control space to another.  The the number of switches in these smoothed polygons tends to infinity with k.

If, for example, we could prove that the smoothed 6k+2-gons are the only extrema, (and this seems plausible to me), then that would complete the proof of the Reinhardt conjecture.

There also appear to be infinitely many Pontryagin extrema for local cost maximization (smoothed 6k+4-gons), also converging to the circle. (The  4-gon is degenerate and has corners.)

We graph the cost of the known extrema as a function of the number of straight edges in the smoothed polygon.  The smoothed octagon is the deep dip at n=8.

smoothed_polygon_cost_grraph

Summary

I have done many calculations in the paper that I have not described in this blog post.

Here is a summary of our main points.

  • In 1934 Reinhardt proposed that the smoothed octagon is the worst packer among centrally symmetric convex disks.
  • The Reinhardt problem can be formulated and studied as a problem in optimal control.
  • In this formulation, the problem is to minimize the total height of paths in the hyperboloid model of non-Euclidean geometry.
  • The shape of the smoothed octagon is completely explained by a bang-bang control.
  • The Reinhardt problem is very similar to other problems in optimal control theory that have been solved (such as Dubins car).
  • The smoothed octagon is a Pontryagin extremal trajectory and a micro-local minimizer.
  • The solution has been confined to a 5-dimensional manifold (which can be searched numerically).
  • I’m willing to wager that the Reinhardt problem will be solved using optimal control theory and that this will happen soon!

Acknowledgements

Our indebtedness to Escher is apparent.  The spectacular animated graphics of smoothed octagons were developed by Greg Egan.  I have used graphics from a wide varieties of sources.  We acknowledge earlier funding from NSF grant 1104102.

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