In this article on extension complexity of regular polygons https://arxiv.org/pdf/1505.08031.pdf it is mentioned that extension complexity of $n$ regular polygons should be $\theta(\log n)$. This is an exponential gap.

  1. Can the gap be more than exponential for some non-trivial classes of polytopes such as $n$ inequalities being replaced by projection of $o(\log n)$ inequalities? What are the best known examples?

  2. If the lower bound is $\alpha\log_2 n-\beta$ what are the sharpest tradeoffs and bounds on $\alpha$ and $\beta$?


I think that the gap is at most exponential, and this follows from a simple duality argument. (My original answer used the upper bound theorem: thanks to Emil Jeřábek for pointing out that this is completely unnecessary.)

Let $K$ be a polytope with $m$ facets in $d$-dimensional space ($d \le m-1$), whose orthogonal projection on some subspace $W$ of dimension $k$ is the polytope $L$ with $n$ facets. Without loss of generality, we can assume that $K$ and $L$ contain the origin $0$. Let $K^\circ = \{y: \langle y, x \rangle \le 1 \ \ \forall x \in K\}$ be the polar (dual) polytope to $K$. The vertices of $K^\circ$ are exactly the normal vectors to the facets of $K$, so $K^\circ$ has $m$ vertices. Then $$L = \{x: \langle y, x \rangle \le 1 \ \ \forall y \in K^\circ \cap W\},$$ and the vertices of $K^\circ \cap W$ are exactly the normals to the $n$ facets of $L$. (In other words, $L^\circ = K^\circ \cap W$.) Every $(d-k)$-dimensional face of $K^\circ$, when intersected with $W$, gives at most one vertex of $K^\circ \cap W$, so, $n \le f_{d-k}(K^\circ)$, where the right hand side is the number of $(d-k)$-dimensional faces of $K^\circ$. Since any face of $K^\circ$ is the convex hull of the set of vertices it contains, so it is uniquely determined by them, we have $f_{d-k}(K^\circ) \le 2^m$. So, an upper bound is $n \le 2^{m}$, i.e. the extension complexity of a polytope with $n$ facets is at least $\lceil\log_2(n)\rceil$.

  • $\begingroup$ Excellent if it is $\geq \alpha\log_2n$ can the $\alpha$ be $1-O(1)$? $\endgroup$
    – VS.
    Mar 29 '19 at 21:59
  • $\begingroup$ I think that sounds plausible, and, if true, it must also follow from the upper bound theorem, which bounds the $h$-vector of the polytope. $\endgroup$ Mar 29 '19 at 22:13
  • $\begingroup$ I feel it is unlikely that either $\alpha\leq1$ or $\alpha=1$ and $\beta>0$ is possible for any finite facet polytope since it seems to me that we make $n$ 'decisions' from $\log_2n$ 'measurements'. I might be wrong. $\endgroup$
    – VS.
    Mar 30 '19 at 0:09
  • $\begingroup$ I think $\lceil-1+\log_2n\rceil$ might be doable leaving no information theoretic gap. However I do not know lower value is allowable although I would be interested in knowing. $\endgroup$
    – VS.
    Mar 30 '19 at 6:12
  • 1
    $\begingroup$ I may be missing something, but each face of $K^\circ$ is uniquely determined by the set of its vertices, hence the total number is at most $2^m$ (without using any sophisticated theorem). $\endgroup$ Mar 30 '19 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.