On the Linear Extension Complexity of Regular n-gons

Arnaud Vandaele, Nicolas Gillis, François GlineurarXiv 2015 · arXiv

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.

An illustration of an extended formulation: a 2D polygon with 6 facets represented as a projection of a 3D polytope with only 5 facets.

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.

Comparison of the extension complexity bounds established in this paper against previous state-of-the-art methods.

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

Abstract

In this paper, we propose new lower and upper bounds on the linear extension complexity of regular $n$-gons. Our bounds are based on the equivalence between the computation of (i) an extended formulation of size $r$ of a polytope $P$, and (ii) a rank-$r$ nonnegative factorization of a slack matrix of the polytope $P$. The lower bound is based on an improved bound for the rectangle covering number (also known as the boolean rank) of the slack matrix of the $n$-gons. The upper bound is a slight improvement of the result of Fiorini, Rothvoss and Tiwary [Extended Formulations for Polygons, Discrete Comput. Geom. 48(3), pp. 658-668, 2012]. The difference with their result is twofold: (i) our proof uses a purely algebraic argument while Fiorini et al. used a geometric argument, and (ii) we improve the base case allowing us to reduce their upper bound $2 \left\lceil \log_2(n) \right\rceil$ by one when $2^{k-1} < n \leq 2^{k-1}+2^{k-2}$ for some integer $k$. We conjecture that this new upper bound is tight, which is suggested by numerical experiments for small $n$. Moreover, this improved upper bound allows us to close the gap with the best known lower bound for certain regular $n$-gons (namely, $9 \leq n \leq 13$ and $21 \leq n \leq 24$) hence allowing for the first time to determine their extension complexity.
BibTeX
@misc{vandaele2015linear,
  author = {Arnaud Vandaele and Nicolas Gillis and François Glineur},
  title = {{On the Linear Extension Complexity of Regular n-gons}},
  year = {2015},
  eprint = {1505.08031},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1505.08031},
}
Figure