5
$\begingroup$

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$?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
9
  • $\begingroup$ Excellent if it is $\geq \alpha\log_2n$ can the $\alpha$ be $1-O(1)$? $\endgroup$
    – VS.
    Commented Mar 29, 2019 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$ Commented Mar 29, 2019 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.
    Commented Mar 30, 2019 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.
    Commented Mar 30, 2019 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$ Commented Mar 30, 2019 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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