<p>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.)</p>

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

CC BY-SA 4.0
2019-03-29T21:59:55.723Z
Excellent if it is $\geq \alpha\log_2n$ can the $\alpha$ be $1-O(1)$?
VS.
CC BY-SA 4.0
2019-03-29T22:13:32.883Z
I think that sounds plausible, and, if true, it must also follow from the upper bound theorem, which bounds the [$h$-vector](https://en.wikipedia.org/wiki/H-vector) of the polytope.
Sasho Nikolov
CC BY-SA 4.0
2019-03-30T00:09:48.907Z
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.
CC BY-SA 4.0
2019-03-30T06:12:20.387Z
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.
CC BY-SA 4.0
2019-03-30T07:52:04.700Z
Posted related problem https://mathoverflow.net/questions/326722/gap-between-number-of-vertices-and-extension-complexity.
VS.
CC BY-SA 4.0
2019-03-30T10:43:20.517Z
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).
Emil Jeřábek
CC BY-SA 4.0
2019-03-30T16:38:28.470Z
@EmilJeřábek oh, of course.. I should've realized the upper bound theorem is only useful when you want dimension-dependent bounds. I will simplify my answer, thanks!
Sasho Nikolov
CC BY-SA 4.0
2019-04-01T19:51:18.017Z
@EmilJeřábek As far as I know the upper bound theorem is for convex polytopes. (I am not even sure there is a universally accepted definition of a non-convex polytope.) However, it implies an upper bound of about $n^{\lfloor d/2 \rfloor}$, which is quadratically better than the one in your nice simple argument. Good to know that $n^{O(d)}$ can be proved in such a simple way, though.
Sasho Nikolov
CC BY-SA 4.0
2019-04-02T07:04:55.343Z
Hmm, I guess I’m confused about the actual statement of the theorem. Anyway, the simple argument shows that the number of $k$-dimensional faces of a polytope with $n$ vertices is at most $\binom n{k+1}$.
Emil Jeřábek
CC BY-SA 4.0
2019-03-29T21:41:27.133Z
2019-03-30T16:46:14.577Z
2019-03-30T16:46:14.577Z
Sasho Nikolov
<p>In this article on extension complexity of regular polygons <a href="https://arxiv.org/pdf/1505.08031.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1505.08031.pdf</a> it is mentioned that extension complexity of <span class="math-container">$n$</span> regular polygons should be <span class="math-container">$\theta(\log n)$</span>. This is an exponential gap.</p>
<blockquote>
<ol>
<li><p>Can the gap be more than exponential for some non-trivial classes of polytopes such as <span class="math-container">$n$</span> inequalities being replaced by projection of <span class="math-container">$o(\log n)$</span> inequalities? What are the best known examples?</p>
</li>
<li><p>If the lower bound is <span class="math-container">$\alpha\log_2 n-\beta$</span> what are the sharpest tradeoffs and bounds on <span class="math-container">$\alpha$</span> and <span class="math-container">$\beta$</span>?</p>
</li>
</ol>
</blockquote>

<cc.complexity-theory><linear-programming>
How small can extension complexity be?
VS.
# How small can extension complexity be?

(Asked by: username_0 on 2019-03-29)

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

**Tags:** cc.complexity-theory, linear-programming

---

## 1 answers

### Answer by username_1 on 2019-03-29. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: Excellent if it is $\geq \alpha\log_2n$ can the $\alpha$ be $1-O(1)$?  
> **username_1**: I think that sounds plausible, and, if true, it must also follow from the upper bound theorem, which bounds the [$h$-vector](https://en.wikipedia.org/wiki/H-vector) of the polytope.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: Posted related problem https://mathoverflow.net/questions/326722/gap-between-number-of-vertices-and-extension-complexity.  
> **username_2**: 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).  
> **username_1**: @EmilJeřábek oh, of course.. I should've realized the upper bound theorem is only useful when you want dimension-dependent bounds. I will simplify my answer, thanks!  
> **username_1**: @EmilJeřábek As far as I know the upper bound theorem is for convex polytopes. (I am not even sure there is a universally accepted definition of a non-convex polytope.) However, it implies an upper bound of about $n^{\lfloor d/2 \rfloor}$, which is quadratically better than the one in your nice simple argument. Good to know that $n^{O(d)}$ can be proved in such a simple way, though.  
> **username_2**: Hmm, I guess I’m confused about the actual statement of the theorem. Anyway, the simple argument shows that the number of $k$-dimensional faces of a polytope with $n$ vertices is at most $\binom n{k+1}$.  

---

