Answer by Veit Elser for Jokes in the sense of Littlewood: examples?

2010-09-17T12:36:39Z

I can't say I share Littlewood's sense of humor, but here is a formula that made me grin the first time I saw it ($A$ and $B$ are non-commuting square matrices):

\begin{equation}\frac{d}{dt}e^{A+B t}=\int_0^1 e^{s(A+B t)}\ B\ e^{(1-s)(A+B t)} \ ds. \end{equation}

A circle packing conjecture

2010-09-08T18:44:37Z

Consider $n$ circles with variable radii $r_1,\ldots, r_n$ that pack inside a fixed circle of unit radius. In other words, all $n$ variable-radius circles are contained in the unit radius circle and their interiors have empty intersections. The tangency graph of a packing comprises $n+1$ vertices, one for each circle, and edges between vertices if the corresponding circles are tangent.

Conjecture: in a packing that maximizes $r_1+\cdots +r_n$, the corresponding tangency graph is planar and triangulated.

This conjecture looks like it might be related to the Koebe-Andreev-Thurston circle packing theorem. The latter states that for every planar triangulated graph there is a corresponding circle packing of the kind described and that this packing is unique up to conformal transformations. While it may turn out that the KAT theorem can provide some insights on proving the conjecture, I believe that something else is going on. For instance, the radius-sum objective function is not conformally invariant.

I have good numerical evidence in support of this conjecture. The optimum configurations I've found up to $n=20$ all have triangulated graphs. I'm posting this on MO because I also have something that looks like it may be "close" to a proof. Perhaps someone can close the gap or convince me that the gap is actually a bottomless chasm -- either would be helpful!

Here is my proof strategy:

Use convexity to show that an optimal configuration maximizes the number of edges in the tangency graph.
Use Euler's theorem to show that a tangency graph that maximizes the number of edges is triangulated.

This is a constrained optimization problem in $\mathbb{R}^{3n}$. Consider the constraint that applies to circles 1 and 2: $(x_1-x_2)^2+(y_1-y_2)^2 \ge (r_1+r_2)^2$. This type of constraint is called "reverse convex" (the feasible region is the complement of an open convex set). Feasible regions in reverse convex problems (intersection of open set complements) can be quite complex -- they may not even be connected. On the other hand, they have a very nice property when we are maximizing a convex function: an optimum can always be found at a "vertex" of the feasible region. In a reverse convex problem in $\mathbb{R}^{N}$, a vertex is a point of the feasible region where at least $N$ of the constraints are equalities. We can think of reverse convex problems as generalizing linear programming in a way that inherits all the nice local properties.

The existence of a global optimizer requires that the feasible region is non-empty and compact. This is not an issue for the circle packing problem since we can let the radii range over all the real numbers and add reverse convex constraints $r_1\ge 0,\ldots,r_n\ge 0$.

The alert reader will already have realized that not all of the constraints in the circle packing problem are reverse convex! The constraints that apply to the fixed unit circle have the wrong sense of the inequality, e.g. $x_1^2 + y_1^2 \le (1-r_1)^2$. One can try to fix this problem by replacing the fixed unit circle with a regular $M$-gon and taking the limit (in some sense) of large $M$. This has two nice consequences. First, the optimization is now truly reverse convex (half-plane constraint for every side of the polygon) and so there is an optimizer where exactly $3n$ constraints are active (at their equality value). To see the second nice feature we have to do some counting.

The tangency graph has one new feature when the fixed circle is replaced by a regular $M$-gon: it is no longer simple because it may have doubled edges between the variable-radius circles and the polygon (whenever a circle is tangent to adjacent polygon edges). Let the number of circles with double tangencies be $D$. If $E$ and $F$ are the number of edges and faces of the graph, and $\tilde{E}$ and $\tilde{F}$ are these quantities when the doubled edges are merged into single edges, then $E=\tilde{E}+D$ and $F=\tilde{F}+D$. Since our graph has $n+1$ vertices, and reverse convex programming tells us there is an optimum with $E=3n$ tangencies, Euler's theorem gives $n+1-3n+F=2$, or $F=2n+1$. We therefore have the following formulas for the "reduced graph" after merging doubled edges: $\tilde{E}=3n-D$, $\tilde{F}=2n+1-D$. The reduced graph is simple and planar and satisfies $2\tilde{E}\ge 3\tilde{F}$ where equality implies that the graph is triangulated. Using our formulas this inequality becomes $D\ge 3$.

The result of this analysis is that optimum configurations in the $M$-gon have at least 3 circles with double tangency, and that the reduced graph is triangulated when this minimum holds. The number 3 is interesting. I believe it corresponds to the fact that the conformal transformations are fixed by specifying 3 points on the boundary of the region (the $M$-gon) where the circles are mapped. Sacrificing the symmetry of the fixed circle paid off because it allowed the optimization problem to have discrete solutions (whose existence follow from reverse convex programming).

There are two gaps in the proof. How do we take results for the $M$-gon and by some limiting process prove a theorem about the circle? Second, how do we prove $D=3$? Optimal configurations with $D>3$ become more unlikely as $M$ becomes large because in that case more than the minimum number of active constraints arise from double tangencies. After all, the pair of constraints at a double tangency become degenerate at $M=\infty$.

I believe the conjecture is true for the class of objective functions $r_1^p+\cdots + r_n^p$ where $1\le p < 2$. The case $p\ge 2$ is uninteresting because the optima degenerate into a single circle that completely fills the fixed circle, the rest having zero radius.

How to define a Voronoi reduced basis?

2010-02-15T18:17:12Z

Let $\Lambda$ be an $n$-dimensional lattice with basis $b_1,\ldots,b_n$. The problem of finding a "good" basis for $\Lambda$, or reducing a "bad" basis into a good one, is a very active area of research. Most basis reduction schemes try to optimize the norms of the basis vectors and their inner products. The goal is to have a basis that is as nearly orthogonal as possible. A more ambitious goal might be for the basis to make the specification of the Voronoi region (i.e. its face vectors) as simple as possible. The expression "Voronoi reduction" is taken from a publication by Conway and Sloane (Proc. Royal Soc. London A, 436 (1992), 55-68) where it is applied to lattices in dimensions $n\le 3$.

What exactly should be the definition of a Voronoi reduced basis?

Central to the construction of the Voronoi region of $\Lambda$ are the $2^n$ cosets of $2\Lambda$. In particular, for any $x\in \Lambda$ one is interested in the set of minimal norm elements in $x+2\Lambda$. Call this set $S(\Lambda,x)$. One definition of a Voronoi reduced basis might therefore be the following:

A basis $b_1,\ldots,b_n$ for $\Lambda$ is Voronoi reduced if, for any $x\in \Lambda$ and any $y\in S(\Lambda,x)$ the integers $y_1,\ldots,y_n$ in the expansion $y=\sum_{i=1}^n y_i b_i$ always satisfy the bound $|y_i|\le c_n$.

If this is a good definition, then what is the best constant $c_n$?

The Conway-Sloane paper shows that $c_n=1$ for $n\le 3$. In other words, in dimension three and lower there always exists a basis such that the minimal norm vectors of the $2\Lambda$ cosets can be expressed as sums with coefficients limited to $-1, 0, 1$. How fast does $c_n$ grow with $n$? Does it grow at all?

Comment by Veit Elser

2010-09-24T12:06:06Z

Well, it's true -- do you need a proof? I thought it was funny because integrals are in a sense the opposite of derivatives and yet here the result of a derivative is an integral.

Comment by Veit Elser

2010-04-20T01:52:11Z

The enclosing parallelepiped is an interesting idea but I don't see how it brings us closer to a bound on $c$. And unless someone comes up with a lattice for which $c>1$, we should probably try to prove $c=1$.

User veit elser - MathOverflow

Answer by Veit Elser for Jokes in the sense of Littlewood: examples?

A circle packing conjecture

How to define a Voronoi reduced basis?

Comment by Veit Elser

Comment by Veit Elser