Introduction: The Efficiency of Extended Formulations
In the field of combinatorial optimization, a fundamental challenge is representing complex geometric shapes—polytopes—using the minimum number of linear inequalities. While a regular $n$-gon in two dimensions naturally possesses $n$ facets, it is often possible to represent it as the projection of a higher-dimensional polytope that has significantly fewer facets. This higher-dimensional representation is known as an extended formulation.
The "size" of such a formulation is defined by the number of facets in the higher-dimensional shape. The minimum possible size for a given polytope $P$ is its extension complexity, denoted $xc(P)$. For regular $n$-gons, it has long been known that $xc(P)$ scales logarithmically with $n$, but determining exact values and tight bounds has remained an open problem. This paper provides significant advancements in closing the gap between theoretical lower and upper bounds.
Methodology: Slack Matrices and Nonnegative Rank
The authors approach the problem through the lens of matrix factorization. The extension complexity of a polytope is mathematically equivalent to the nonnegative rank of its slack matrix $S$. A slack matrix records the "slack" or distance between every vertex and every facet of the polytope; specifically, $S_{ij}$ is the value of the $i$-th linear inequality evaluated at the $j$-th vertex.
Improving Lower Bounds
To establish what is impossible, the authors utilize combinatorial techniques. They frame the problem as a "rectangle covering" task, seeking the minimum number of monochromatic rectangles required to cover the positive entries of the slack matrix. By applying a generalization of Sperner’s Theorem—a classic result concerning the maximum size of an antichain in a power set—to the sparsity pattern of the $n$-gon's slack matrix, they derived a stronger lower bound on the boolean rank, which in turn bounds the nonnegative rank.
Refining Upper Bounds
On the constructive side, the paper moves away from traditional geometric arguments based on successive reflections. Instead, the authors propose a purely algebraic recursive factorization of the slack matrix. They identified that the efficiency of existing recursive bounds was limited by their base cases. By optimizing the base case and stopping the recursion earlier, the authors successfully reduced the facet count for specific ranges of $n$.
Key Results and Comparative Analysis
The primary contribution of this work is the determination of exact extension complexities for several previously unsolved cases. Specifically, the authors proved exact values for $n = 9$ through $13$ and $n = 21$ through $24$. For instance, they established that a regular 9-gon has an extension complexity of exactly 7.
The paper establishes a new general upper bound for all $n \ge 2$:
- $xc(S_n) \le 2\lceil \log_2(n) \rceil - 1$ when $2^{k-1} < n \le 2^{k-1} + 2^{k-2}$
- $xc(S_n) \le 2\lceil \log_2(n) \rceil$ otherwise.
Numerical experiments conducted by the authors for $n$ up to 78 suggest that these new upper bounds may actually represent the exact values for all small $n$, leading to a new "Tightness Conjecture" in the field.
Conclusion and Future Directions
While this research significantly narrows the uncertainty surrounding the complexity of regular polygons, gaps persist for values such as $n=14$ and $n=17$ through $20$. The authors highlight that the primary bottleneck remains the difficulty of proving tight lower bounds for nonnegative rank—a problem known to be computationally hard. Future work may involve exploring deeper combinatorial properties of slack matrices or leveraging new convex relaxations to provide stronger numerical evidence for lower bounds.
Summary updated