Abstract: A geometric inequality among three triangles, originating in circle packing problems, is introduced. In order to prove it, we reduce the original formulation to the nonnegativity of a particular polynomial in four real indeterminates. Techniques based on sum of squares decompositions, semidefinite programming, and symmetry reduction are then applied to provide an easily verifiable nonnegativity certificate.
Introduction
In the study of circle packings—arrangements of circles with specific tangency patterns—the theory often relies on the properties of relaxation mappings. One such fundamental property is the "super-additivity" of the $\bar{a}$-mapping, a variant of Thurston’s relaxation mapping. This paper, a collaboration between Pablo A. Parrilo and Ronen Peretz, provides a rigorous proof of a geometric inequality that underpins this property.
While the inequality describes the relationship between the angles and side lengths of three specific triangles, the paper’s primary contribution is its methodology. It demonstrates how a classical geometry problem, notoriously difficult to solve via traditional synthetic or trigonometric methods, can be transformed into a high-degree polynomial optimization problem and solved using Semidefinite Programming (SDP) and symmetry reduction.
The Geometric Problem
The core challenge involves three Euclidean triangles defined as follows:
- Triangle 1: Sides $X, Y, Z$ with angle $\alpha$ between $X$ and $Y$.
- Triangle 2: Sides $U, V, W$ with angle $\beta$ between $U$ and $V$.
- Triangle 3: Sides $(X+U), (Y+V), (Z+W)$ with angle $\gamma$ between the first two sides.
The authors aim to prove the following inequality: $$\alpha(X+Y-Z) + \beta(U+V-W) \leq \gamma((X+U)+(Y+V)-(Z+W))$$
This expression relates the perimeters and angles of the triangles in a way that is essential for circle packing algorithms but lacks a straightforward geometric proof.
Methodological Framework
To resolve the inequality, the authors move the problem from the realm of geometry into computational algebra through a multi-step process.
1. Algebraic Reduction
Using a series of lemmas and trigonometric substitutions, the geometric inequality is transformed into a requirement that a specific real polynomial $P(x, y, z, w)$ must be non-negative for all real inputs. This reduction clears denominators and simplifies the trigonometric constraints into a purely algebraic form.
2. Sum of Squares (SOS) Decomposition
A standard technique to prove a polynomial is non-negative is to represent it as a sum of squared polynomials ($P = \sum f_i^2$). If such a representation exists, the polynomial is guaranteed to be non-negative for all real values. Finding this decomposition is equivalent to finding a positive semidefinite matrix, known as the Gram matrix.
3. Symmetry Reduction
The resulting polynomial is degree 20 with four variables. A direct approach via Semidefinite Programming (SDP) would require solving a massive problem with over 10,000 constraints, which was near the limits of generic solvers at the time of the research.
The authors overcome this by identifying that the polynomial is invariant under a symmetry group $G$ with 32 elements. This group reflects the interchangeable nature of the triangles and the signs of the sides. By applying representation theory (specifically Schur’s Lemma), the authors decompose the massive SDP into 14 much smaller, coupled problems. This symmetry reduction makes the computation highly accurate and computationally feasible, reducing a problem of dimension 1001 down to small blocks, the largest being only 11x11.
Results and Verification
The authors successfully prove the geometric inequality (Theorem 1), establishing the super-additivity of the $\bar{a}$-mapping. Beyond the existence of the proof, the paper provides a "computational certificate." The target polynomial $P(x, y, z, w)$ is shown to be a sum of exactly five squares. The authors provide the specific polynomials that constitute this SOS decomposition, allowing any reader to verify the proof algebraically without needing to re-run the SDP solver.
Conclusion
This work serves as a high-profile case study for the application of the Gram matrix method and symmetry-adapted coordinate transformations in polynomial optimization. It demonstrates that "brute-force" algebraic proof via SOS is a viable alternative to classical geometric proofs when the latter prove elusive. While the specific inequality is solved, the framework of using group theory to "shred" computationally intractable optimization problems into manageable pieces remains a powerful tool for discrete geometry and beyond.
Summary updated