Optimal Control Theory to Settle Reinhardt’s Conjecture

The 2010’s are a Golden Age for packing problems. In 2014, Hales announced the long-awaited completion of a high-profile machine proof project called FlySpeck, which verified his proof of Kepler’s conjecture. Johannes Kepler, in 1600, conjectured that the densest way to pack spheres is in cannonball stacks. This was Hilbert’s 18th problem. The final proof was quite involved and its correctness needed massive computer checking. For example, verifying the nonlinear inequalities took 5000 hours on the Microsoft Azure cloud. Other optimal packing problems have been solved recently too—with simpler methods. Cohn–Kumar–Miller–Radchenko–Viazovka [3] and Viazovka [8] found optimal sphere packings in dimensions 8 and 24. Viazovka was awarded a 2017 Clay Research Prize for this work.

 

The corresponding lattices are the E8 and Leech lattices, which are important in several areas of mathematics and physics. Viazovka’s argument is simple, elegant, and canonical. The paper can be read by any person understanding only the rudiments of harmonic analysis. Stanford University’s Akshay Venkatesh has made the comment that “it seems to me much more likely than not that this function is also part of some richer story” (see the full Quanta article).

To date, optimal sphere packings are known in dimensions $2,3,8$ and $24$; with densities of $\pi/\sqrt{12}, \pi/\sqrt{18}, \pi^4/\sqrt{384}$ and $\pi^{12}/12!$, respectively. In any other dimension, it is yours for the taking!

Now, spheres are not very good packers as far as shapes go. In fact, it is conjectured that spheres are the worst (convex) packers in dimension $3$. This idea is known as Ulam’s Packing Conjecture. Is the same true in dimension $2$? No. The optimal circle packing has density $\pi/\sqrt{12} = 9068996$… and the optimal packing of regular octagons is $(4+4\sqrt{2})/(5+4\sqrt{2}) = 0.9061636$….

The problem is only interesting for convex bodies. One could take rings with arbitrarily large radii to get packings with arbitrarily small density. It is conjectured that the packing pessimum for convex disks is the regular heptagon. However, it is not even known what the optimal packings of regular heptagons is! The densest known packing is the double lattice pictured below:

This packing has density $297\left(-111+492\cos^2\left(\frac{\pi}{7}\right) – 356\cos^{22}\left(\frac{\pi}{7}\right)\right) =0.89269…$ [2]. Without knowing the optimal heptagon packing, progress on this conjecture is halted (unless, of course, the conjecture turns out to be false).

Fejes Tóth proved that for centrally symmetric convex bodies, optimal packings are always lattice packings [4]. This makes the pessimal centrally symmetric convex disk packing problem more tractable than the pessimal arbitrary convex disk problem. A body is called centrally symmetric if is in invariant under the transformation $x \mapsto -x.$ This is the same as possessing a 180 degree rotational symmetry. Heptagons and triangles do not exhibit this symmetry, whereas octagons and hexagons are centrally symmetric bodies.

Conjecture (Reinhardt, 1934). The smoothed octagon

(with its optimal packing) is a pessimum for packings of centrally symmetric convex bodies in the plane.

In March 2017, Hales posted a preprint on the arXiv “The Reinhardt Conjecture as an Optimal Control Problem” [5]. This paper lays out possible ways to resolve the Reinhardt problem by translating it into a problem in Optimal Control Theory (OTC). In what follows, we showcase this program as it presently stands.

Why the Smoothed Octagon?

Why did Reinhardt expect the smoothed octagon to be the worst packer? This is an unusual guess. I have never heard the smoothed octagon mentioned except as a candidate solution to the 2-D packing pessimization problem. Reinhardt himself, as I understand it, never much explained the guess. The following philosophizing was relayed to me by Hales:

Let’s start with a square. It tiles the plane with 100% density—bad guess. Maybe cutting a corner off the square will help? If we cut off its upper right corner, by central symmetry, we must also cut off its lower left corner. This is the centrally symmetric hexagon, which still tiles with 100% density. Cutting off the upper left hand corner (and therefore the lower right corner too) gives an octagon. 

Moreover, solutions of the problem must be hexagonally symmetric [6]. 

Definition. Let $e_j = (\cos(2\pi j/6),\sin(2\pi j/6))$ be six equidistant points on the unit circle. Then, a disk $D \subset \mathbb{R}^2$ is hexagonally symmetric if it can be written as the union of six arcs $t \mapsto g(t)e_j$, $j = 0,1,…,5$ where $g : [0,t_f] \to \text{SL}_2(\mathbb{R})$ is a path in $\text{SL}_2(\mathbb{R}).$

The octagon is not hexagonally symmetric. There is only one way to round out the corners of an octagon to make it hexagonally symmetric and that is with hyperbolic arcs. This, in conjunction with failure to find a worse centrally symmetric convex packer, is our intuition for Reinhardt’s guess.

Optimal Control Theory

Optimal control theory is a generalization of the calculus of variations. The calculus of variations began with Johann Bernoulli’s proposal of the Brachistochrone Problem.

Problem (Bernoulli, 1696). Suppose that a particle of mass $m$ moves along some curve $\gamma$, in two dimensions, under the influence of gravity. Write $a,b \in \mathbb{R}^2$ for the endpoints of $\gamma$. For what $\gamma$ is the time to get from $a$ to $b$ minimized?

For a given curve $\gamma$, the time of descent is computed as $$J[y]=\int\frac{\sqrt{1+\gamma'(t)}}{\sqrt{2g\gamma(t)}}dt.$$ So, the problem is to find a function $\gamma = \gamma(t)$ which minimizes the functional $J$. Such $J$ are called costs. 

In solving this problem, Legendre created the calculus of variations. He saw you could take a reference curve $\gamma$ and give it a slight first-order perturbation $\gamma + \epsilon \nu.$ Then, critical points of the map $\gamma \mapsto J[\gamma]$ are curves stable under small perturbations. It is a classical mathematical proof that such critical points are given by solutions to the Euler–Lagrange equations $$\frac{\partial L}{\partial f} – \frac{d}{dt} \frac{\partial L}{\partial \gamma’} = 0.$$

Optimal control theory addresses more general situations. Solutions to OTC problems are control functions. Control functions are prescriptions for an agent to act on the system and achieve an optimal result. For example, one can ask about the fastest way to park a car. Well, you slam on the accelerator and then slam on the break! This is not safest, but it is fastest. Of course, additional constraints can be added to the problem for safety.

An optimal control problem in finance could ask for a time-dependent control function that buys and sells stock options. In medicine, we can ask for a control function that optimally administers chemotherapeutic drugs.

The point is that the solution to the problem is a set of instructions. For car parking, it is a control function $$u(t) = \begin{cases} a_{\text{max}}, & 0 \leq t < t_0 \\ a_{\text{min}}, & t_0 \leq t \leq t_f, \end{cases}$$ where $a_{\text{max}} > 0$ denotes the maximum possible acceleration for the car, $a_{\text{min}} <0$ denotes the maximum (in absolute value) possible deceleration, $t_f$ denotes the final time and $t_0$ denotes a switching time.

The values $a_{\text{max}}$ and $a_{\text{min}}$ are determined by the makeup of the car. So, each car has a corresponding interval $[a_{\text{min}},a_{\text{max}}].$ This is called the control set. Our control function $u$ takes values only in extreme points of the control set. Such solutions are called bang-bang.

With the right eyes, smoothed octagons look like bang-bang solutions. Consider a control function for curvature, with control set $[0, \kappa_{\text{max}}].$ Smoothed polygons consist of segments of zero curvature followed abruptly by arcs of curvature $\kappa_{{max}}.$ So, smoothed polygons are described by $u$ that take values only in extreme points on $[0, \kappa_{\text{max}}].$

We have a classical OTC problem [1]:

Dubin’s Car Problem. Consider a car with initial position given by a vector $v \in \mathbb{R}^2.$ How does one drive the car so as to get it in some final position $w \in \mathbb{R}^2$ in minimal time?

If $v$ and $w$ are colinear, then the solution is to acceleration maximally. But, if the initial and terminal directions differ moving in a straight line is not possible. Rather the solution is to move to turn the steering wheel as hard as possible when turning and otherwise move in straight segments with maximum acceleration. In other words, we have a control set $U \subset \mathbb{R}^2$, where a point $(a,\kappa) \in U$ corresponds to acceleration at $a\text{ m/s}^2$ and turning in an arc of curvature $\kappa$. Further, the solution is bang-bang.

Restricting to a steering wheel that only turns left, there is a striking resemblance to smoothed polygons [5].

In the figure above on the left is a Dubin car trajectory and the one of the right is a hyperbolically smoothed polygon arc.

Enter Hyperbolic Geometry

It has been shown [6] that the trajectory $g : [0,t_f] \to \text{SL}_2(\mathbb{R})$ must satisfy the equation $g=g’X$, for $X \in \mathfrak{sl}_2(\mathbb{R})$ with determinant $1$. Write $$X= \begin{pmatrix} c_{11} & c_{12} \\ c_{21} & -c_{11}. \end{pmatrix}$$ Then, if $X$ solves the Reinhardt problem $c_{21} > 0$ [6]. The set of trace $0$, determinant $1$ matrices with $c_{21}$ is the adjoint orbit of $J = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ e.g. $$X=X(x,y) = \begin{pmatrix} x/y & -x^2/y – y \\ 1/y & -x/y \end{pmatrix} = \hat{z}J\hat{z}^{-1},$$ where $\hat{z} = \begin{pmatrix} y & x \\ 0 & 1\end{pmatrix}$ [6, Lemma 2.2.1]. This gives us upper half-plane coordinates $\hat{z}J\hat{z}^{-1} \mapsto x +iy \in\mathfrak{h}$, because of the condition $1/y > 0$.

The upper-half plane is a well-known model of hyperbolic geometry. There is also a disk model $\mathbb{D} = \{w \in \mathbb{C} | |w| < 1\}$, with translation given by $w = (z-i)/(z+i) \in \mathbb{D}.$ Without loss of generality, additional constraints can be imposed on $X$: $$\sqrt{3}|c_{11}| < c_{21},\quad 3c_{12} + c_{21} < 0.$$ These are the star inequalities. The star region (in both the upper-half plane and the disk models) is shown below

Through the magic of Fillipov’s lemma [1], trajectories in the base manifold $\text{SL}_2(\mathbb{R}) \times \mathfrak{H}^\ast$ lift to the cotangent bundle. The problem is easier there.

Consider the star region in the upper-half plane $\mathfrak{H}^\ast.$ The path giving the smoothed octagon is following 4 edges around a triangular path centered at $i \in \mathfrak{H}^\ast$ (below, right).

The constant path at $i$ corresponds to the circle. Conjecturally, near the edges of  the star region the disks approach parallelograms—computational evidence suggests this. Triangular paths with $4+3k$ edges correspond to the smoothed $(6+2k)$-gon. They all come from bang-bang controls.

This information is teased out from Pontryagin’s Maximum Principle (PMP). The PMP was discovered in 1956 by a group of Soviet mathematician’s lead by the celebrated Lev Pontryagin. It, like the Euler-Lagrange equations, is a first-order necessity condition. And it is derived in a similar way: look for trajectories for which the cost functional is stable under movements across the control set.

Theorem (PMP). Let $(g,z)$ be a minimizing trajectory for some measurable control $u ; [0,t_f] \to U$. Then,

  • The Hamiltonian of the system vanishes along the lifted trajectory $(\lambda,u)$
  • The lifted trajectory $\lambda : [0,t_f] \to T^\ast M$ is Lipschitz continuous and satisfies the ODE $$\Lambda’ = [\Lambda,X],$$ $$\nu_1′ = \frac{\partial H^+}{\partial x},$$ $$\nu_2′ = -\frac{\partial H^+}{\partial y},$$ where $H^+$ is the pointwise maximum over the control set: $$H^+(\lambda_{\text{cost}},\lambda) = \text{max}_{u \in U} H(\lambda_\text{cost},\lambda;u)$$
  • Tranversality at the endpoints

This list gives us a necessity condition. Trajectories satisfying the PMP conditions are called Pontryagin extremal. Indeed, all smoothed $(6+2k)$-gons are Pontryagin extremals. In particular, the maximized Hamiltonian portion shows that solutions to Reinhardt’s problem must be bang-bang. To prove the Reinhardt conjecture it remains only to show there are no other extremals.

A Topological Endgame

This could end in a few ways. There are higher-order generalizations of the PMP [7]. Perhaps higher-order necessity information could eliminate all other trajectories. Optimal control theory does have sufficiency tests such as Hamilton–Jacobi–Bellman’s theorem. In fact, the HJB method was used to prove global minimality for the 3-dimensional Dubin’s car problem. Yet, tragically, the Reinhardt problem does not satisfy hypothesis required to use the HJB technique. As a last resort, calculations with a supercomputer could do the job too.

My heart is with a certain topological strategy. First, by rotational symmetry of the problem, we quotient the phase space out by the group of rotations $\langle R = e^{2\pi i /3}\rangle$ around $i$. The point $i$ is the only one with isotropy, so after passing through the quotient, we remove this “orbifold singularity” to obtain an honest smooth manifold $$M = (\text{SL}_2(\mathbb{R}) \times \mathfrak{H}^\ast / \{i\}) / \langle R \rangle.$$ Because SL$_2(\mathbb{R})$ is parallelizable,  the cotangent bundle projection $$\pi :((\text{SL}_2(\mathbb{R}) \times \mathfrak{sl}_2(\mathbb{R})) \times (\mathfrak{H}^\ast / \{i\} \times \mathbb{R}^2)) / \langle R \rangle \to(\text{SL}_2(\mathbb{R}) \times \mathfrak{H}^\ast / \{i\}) / \langle R \rangle$$ has contractible fibers. So, $\pi$ induces an isomorphism on homologies.

Because $\mathfrak{H}^\ast/\{i\}$ deformation retracts onto $S^1$ and $\pi_1(\text{SL}_2\mathbb{R}) = \mathbb{Z}$, we have $$H_1(T^\ast M) = \mathbb{Z} \times \mathbb{Z},$$ where $M = \text{SL}_2(\mathbb{R}) \times \mathfrak{H}^\ast/\{i\}.$ There is an evident inclusion $H_1(\mathfrak{H}^\ast/\{i\}) \to \mathbb{Z} \times \mathbb{Z}.$

The smoothed $(6k+2)$-gon lies in homology class $(1,3k+1) \in \mathbb{Z} \times \mathbb{Z}.$ Let us split by cases on the second component:

  • Case $n = 3k+1, k > 0:$ The smoothed $(6+2k)$-gon lies in this class. Using Jacobi fields, one may be able to show that the smoothed polygons are pessimal in their homology class.
  • Case $n \neq 1$ (mod $3$): This violates the boundary conditions of our problem. There are no extremals in these homology classes.
  • Case $n = 3k + 1, k < 0:$ These are conjectured to be local maximums.
  • Case $n = 1:$ This would correspond to the “homological $2$-gon.” It is conjectured these are all pathological and can be ruled out some reasons of not being a closed curve, etc.

There is the strategy. As a final remark I would like to note that if the $2$-gon exists, then it would be the global pessimum and not the smoothed octagon! Dream of homological $2$-gons.

Acknowledgements. Most of all I would like to thank Prof. Thomas C. Hales for teaching me everything I know about this problem. The colors images are produced by Greg Egan and the black and white images are taken from [2]. John Baez’s nlab post on this subject helped outline the first section.

References

[1] Agrachev, A.A. and Sachkov, L. Control theory from the geometric viewpoint, Encyclopedia of Mathematical Sciences, 87. Control Theory and Optimization, II. Springer-Verlag, Berlin (2004)

[2] Baez, J. & Egan, G. A packing pessimization problem, 9 2014. https://golem.ph.utexas.edu/category/2014/09/a_packing_pessimization_proble.html.

[3] Cohn, H., Kumar, A., Miller, S.D., Radchenko, D., & Viazovka, M. The sphere packings problem in dimension 24, https://arxiv.org/abs/1603.06518. March, 2016.

[4] Fejes Tóth, L. On the densest packing of domains, Proc. Kon. Ned. Akad. Wet.51 (1948), 189—192.

[5] Hales, T.C. The Reinhardt Conjecture as a Problem in Optimal Control Theory, https://arxiv.org/abs/1703.01352 March 3, 2017.

[6] Hales, T.C. On the Reinhardt conjecture, Vietnam Journal of Mathematics, 39(3):287–307, 2011. arXiv:1103.4518.

[7] Krener, A., The high order maximal principle and its application to singular extremals, SIAM J. Control and Opt. 15(2) (1977), pp. 256-293.

[8] Viazovska, M.S. The sphere packing problem in dimension 8, Annals of Mathematics, pages 991-1015 Volume 185 (2017), Issue 3.

About Jacob A. Gross

In October 2017, Jacob A. Gross begins a DPhil in Geometry at Oxford University, under the supervision of Prof. Dominic D. Joyce FRS. He is interested in Donaldson-Thomas invariants and G2 manifolds.
This entry was posted in General, Math and tagged , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

HTML tags are not allowed.