# Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?

Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets. Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.

Can $\text{Proj}(P)$ have more than $f$ facets?

In the general case, each successive projection can increase the number of facets from $f$ to $\left\lfloor \frac{f^2}{2} \right\rfloor$, but I'm wondering if $\mathbb{R}^2$ is a special case.

Consider the polytope in $\mathbb{R}^3$ with $8$ vertices at coordinates $(\pm 1, \pm 2, 1), (\pm 2, \pm 1, -1)$. Geometrically this looks like a cube where the top face is stretched in the direction of the $y$-axis and the bottom face is stretched in the direction of the $x$-axis, but it still has the face structure of a cube and in particular has $6$ facets.

It's projection onto the first two coordinates is clearly an octagon, and hence has two more facets than the original polytope.

• Thanks for the counterexample. Does requiring $P$ to be facet-transitive and vertex-transitive have an effect? Jan 20 '17 at 19:05
• That I'm not sure about. I'll note that that example is vertex transitive (but not facet transitive). I will say that this does hold for all regular (i.e. flag transitive) polytopes, with the possible exception of the 120-cell, which is unlikely but I don't want to take the time to analyze it.
– Nate
Jan 20 '17 at 21:21
• So more generally, the analogous deformed prism with base an n-gon shows that one can obtain a 2n-gon as a projection of a polyhedron with n+2 facets. Sep 4 at 6:01

Your question is essentially about extension complexity. In general, the extension complexity of a polytope $$P$$ is the minimum number of facets over all polytopes $$Q$$ which project to $$P$$. You are interested in the extension complexity of polygons. Fiorini, Rothvoß, and Tiwary proved that regular $$n$$-gons have extension complexity $$O(\log n)$$. For lower bounds, they give examples of $$n$$-gons which have extension complexity $$\sqrt{2n}$$.

It is an open question if there exists for infinitely many $$n$$, an $$n$$-gon with extension complexity $$\Omega(n)$$. Edit. Shitov has recently shown that every convex $$n$$-gon has extension complexity at most $$147 n^{2/3}$$, which resolves the open question in the negative.

As a bonus, here is a picture of the polytope in Nate's answer (courtesy of Samuel Fiorini). Another, combinatorially minimal, counterexample of such a polytope $P$ (with only five facets) is the convex hull of the six vertices $(\pm2, 0, 0)$, $(\pm1, \pm1, 1)$. Its projection to the $xy$-plane is a hexagon. The minimality of the number of vertices and the number of facets is easy to prove.

• --------------- ---- Nice! ---- --------------- Sep 4 at 6:51