# How small can extension complexity be?

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

• Excellent if it is $\geq \alpha\log_2n$ can the $\alpha$ be $1-O(1)$?
– VS.
Mar 29 '19 at 21:59
• 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. Mar 29 '19 at 22:13
• 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.
– VS.
Mar 30 '19 at 0:09
• 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.
– VS.
Mar 30 '19 at 6:12
• 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). Mar 30 '19 at 10:43