Many equiprojective polytopes

In 1968, Geoffrey Shephard asked a number of questions related to the combinatorics of Euclidean polytopes—convex hulls of finitely many points from $\mathbb{R}^{d}$ [19, 20]. Among them, Question IX asks for a method to construct every equiprojective polytope. A $3$-dimensional polytope $P$ is $k$-equiprojective when its orthogonal projection on any plane (except for the planes that are orthogonal to a facet of $P$) is a polygon with $k$ vertices. A straightforward example of equiprojective polytopes is provided by prisms: a prism over a polygon with $k-2$ vertices is $k$-equiprojective. Hallard Croft, Kenneth Falconer, and Richard Guy recall Shephard’s question in their book about unsolved problems of geometry [3, Problem B10]. While a practical criterion (see Theorem 3.2 to follow) and an algorithm to recognise equiprojective polytopes have been proposed by Masud Hasan and Anna Lubiw [11], the problem is still open.

Some equiprojective polytopes have been recently constructed by truncating Johnson solids ($3$-dimensional polytopes whose facets are regular polygons) and by gluing two well-chosen prisms along a facet [10]. The latter construction shows, in particular, that the number of different combinatorial types of $k$-equiprojective polytopes is at least a linear function of $k$ (recall that two polytopes have the same combinatorial type when their face lattices are isomorphic). Here, this result is improved as follows.

Our proof of Theorem 1.1 is split into two cases depending on the parity of $k$. Recall that a zonotope $Z$ is a Minkowski sum of line segments. It can be assumed without loss of generality that these segments are pairwise non-collinear, in which case their number is the number of generators of $Z$. As observed in [11], a $3$-dimensional zonotope with $n$ generators is a $2n$-equiprojective polytope. When $k$ is even, this observation is the first ingredient in the proof of Theorem 1.1. The second ingredient is the following estimate for the number of combinatorial types of zonotopes that may be of independent interest.

We establish Theorem 1.2 as a consequence of the Goodman–Pollack bound the number of order types [9] and its refinement by Noga Alon [1].

When $k$ is odd, Theorem 1.1 requires a different construction that uses a Minkowski sum with a triangle. In order to analyse how equiprojectivity behaves under Minkowski sums, we rely on the notion of an aggregated cone of a polytope at one of its edge directions. Roughly, an edge direction of a polytope $P$ contained in $\mathbb{R}^{3}$ is a vector $u$ in the unit sphere $\mathbb{S}^{2}$ parallel to an edge of $P$. The aggregated cone $C_{P}(u)$ of $P$ at $u$ is the union of the $2$-dimensional normal cones of $P$ contained in the plane $u^{\perp}$ through the origin of $\mathbb{R}^{3}$ and orthogonal to $u$. We obtain the following characterization of equiprojectivity.

Since in practice, computing the faces of a Minkowski sum of polytopes is done via their normal fans, Theorem 1.3 provides a way to prove Theorem 1.1 in the case when $k$ is odd. More generally, Theorem 1.3 allows to construct new classes of equiprojective polytopes. For instance, we prove the following.

More generally, we will provide a condition under which a Minkowski sum of equiprojective polytopes, polygons, and line segments (that are allowed to share edge directions) is equiprojective (see Theorem 4.3). We will also explain how the value of $k$ such that this Minkowski sum is $k$-equiprojective can be computed from the aggregated cones of the summands (see Theorem 4.4).

The article is organized as follows. We prove Theorem 1.2 and derive from it the special case of Theorem 1.1 when $k$ is even in Section 2. We introduce the aggregated cones of a polytope and establish Theorem 1.3 in Section 3. We give the announced Minkowski sum constructions of equiprojective polytopes and prove Theorem 1.4 in Section 4. We provide the proof of Theorem 1.1 in the case when $k$ is odd in Section 5. Finally, we conclude the article with Section 6, where some questions in the spirit of Shephard’s are stated about the decomposability of equiprojective polytopes.

Up to translation, a zonotope is any subset of $\mathbb{R}^{d}$ of the form

where $\mathcal{G}$ is a finite, non-empty set of pairwise non-collinear vectors from $\mathbb{R}^{d}\mathord{\setminus}\{0\}$, which we refer to as a set of generators of $Z$. Note that $Z$ admits several sets of generators, each obtained from $\mathcal{G}$ by negating a part of the vectors it contains. In particular, $Z$ has $2^{|\mathcal{G}|}$ sets of generators, each of the same cardinality. We will refer to this common cardinality as the number of generators of $Z$.

Recall that the face lattice of a polytope is the set of its faces ordered by inclusion and that two polytopes have the same combinatorial type if their face lattices are isomorphic (here, by an isomorphism, we mean a bijection that preserves face inclusion). The goal of this section is to estimate the number of combinatorial types of zonotopes in terms of their number of generators. This will allow to prove Theorem 1.1 when $k$ is even thanks to the following statement from [11], which we provide an alternative proof for.

It is well known that the combinatorial types of zonotopes are determined by the oriented matroids of their sets of generators [2]. Let us recall what the oriented matroids of a finite subset $\mathcal{X}$ of $\mathbb{R}^{d}\mathord{\setminus}\{0\}$ are. First pick a bijection

whose role is to order the vectors of $\mathcal{X}$ so that each of them corresponds to a coordinate of $\mathbb{R}^{|\mathcal{X}|}$. A vector $z$ from $\{-1,0,1\}^{|\mathcal{X}|}$ is a covector of $\mathcal{X}$ with respect to $\sigma$ when there exists a non-zero vector $y$ in $\mathbb{R}^{d}$ such that $z_{i}$ is the sign of $\sigma(i)\mathord{\cdot}y$ for every $i$. The set $M_{\sigma}(\mathcal{X})$ of all the covectors of $\mathcal{X}$ with respect to $\sigma$ is an oriented matroid of $\mathcal{X}$. Note that the other oriented matroids of $\mathcal{X}$ can be obtained by varying $\sigma$ or, equivalently, by letting the isometries of $\mathbb{R}^{|\mathcal{X}|}$ that permute the coordinates act on $M_{\sigma}(\mathcal{X})$. For more details on oriented matroids, see for instance [2] or [17]. Two finite subsets $\mathcal{X}$ and $\mathcal{X}^{\prime}$ of $\mathbb{R}^{d}\mathord{\setminus}\{0\}$ are called oriented matroid equivalent when they have at least one oriented matroid in common. It is easy to check that oriented matroid equivalence is indeed an equivalence relation on the finite subsets of $\mathbb{R}^{d}\mathord{\setminus}\{0\}$.

The following statement is proven in [2] (see Corollary 2.2.3 therein). It provides the announced correspondence between the combinatorial type of a zonotope and the oriented matroids of its sets of generators.

According to Proposition 2.2, counting the number of combinatorial types of $d$-dimensional zonotopes with $n$ generators amounts to counting the number of oriented matroids of $d$-dimensional sets of $n$ vectors from $\mathbb{R}^{d}\mathord{\setminus}\{0\}$. Estimates on these numbers have been given by Jacob Goodman and Richard Pollack [9] and by Noga Alon [1] in the terminology of order types [5, 6, 7, 8, 13]. Theorem 4.1 from [1] can be rephrased as follows in terms of oriented matroids. Observe that the lower bound in that statement is established in [9, Section 5].

Combining Proposition 2.2 and Theorem 2.3 makes it possible to provide estimates on the number of combinatorial types of zonotopes in terms of their dimension and number of generators. We prove Theorem 1.2 when $d$ is fixed and $n$ grows large instead of when $n/d$ grows large as in the statement of Theorem 2.3 because we will only need it in the $3$-dimensional case.

When $k$ is even, one obtains from Proposition 2.1 and Theorem 1.2 that the number of $k$-equiprojective polytopes is at least

The special case of Theorem 1.1 when $k$ is even follows from this inequality and the observation that, if $k$ is greater than $1$, then

In order to prove Theorem 1.1 when $k$ is odd, we will use a construction of equiprojective polytopes via Minkowski sums. The behavior of equiprojectivity with respect to Minkowski sums will be determined via Theorem 1.3, whose proof is given in this section. Our starting point for this proof is the article by Masud Hasan and Anna Lubiw [11]. Let us recall some of the terminology introduced in that article. In the following definition, given at the beginning of Section 2 in [11], an edge-facet incidence of a $3$-dimensional polytope $P$ is a pair $(e,F)$ such that $F$ is a facet of $P$ and $e$ an edge of $F$.

The following theorem is Theorem 1 from [11].

Now recall that, given a polytope $P$ contained in $\mathbb{R}^{d}$ (of dimension possibly less than $d$) and a face $F$ of $P$, the normal cone of $P$ at $F$ is defined as

The normal cone of a $j$-dimensional face of $P$ is a $(d-j)$-dimensional closed polyhedral cone. In particular, if $P$ is a polytope of any dimension contained in $\mathbb{R}^{3}$, then a normal cone of $P$ is $2$-dimensional if and only if it is a normal one of $P$ at one of its edges. Moreover, the normal cones of $P$ at two of its edges span the same plane when these edges are parallel. Recall that the plane through the origin of $\mathbb{R}^{3}$ orthogonal to a non-zero vector $u$ is denoted by $u^{\perp}$.

It should be noted that, while an aggregated cone of $P$ is not necessarily convex, it is still a cone in the sense that it is invariant upon multiplication by a positive number. Further observe that in the statement of Definition 3.3, if there is no edge of $P$ parallel to $u$, then $C_{P}(u)$ is empty. For this reason, we are only really interested in the vectors that model the edge directions of a polytope. In addition, it will be useful in the sequel to have just one vector for each possible edge direction and we propose the following definition.

Note that edge directions could alternatively be defined as a finite subset of the real projective plane $\mathbb{RP}^{2}$. The aggregated cones of a polygon or a line segment at their edge directions are particularly well-behaved.

The notion of an aggregated cone at an edge direction is illustrated in Figures 2 and 1. Figure 1 shows a triangular prism $P$ and two of its aggregated cones. At the top of the figure, $u$ is the edge direction of $P$ parallel to the three edges $e$, $e^{\prime}$, and $e^{\prime\prime}$ of $P$ that are not contained in a triangular face. The orthogonal projection of $P$ along $u$ is depicted at the center of the figure. In that case, $C_{P}(u)$ coincides with $u^{\perp}$ as shown on the right of the figure. At the bottom of Figure 1, $u$ is an edge direction parallel to two edges $e$ and $e^{\prime}$, each contained in one of the triangular faces of $P$ and $C_{P}(u)$ is the half-plane depicted on the right of the figure. Again, the orthogonal projection of $P$ along $u$ is shown at the center of the figure. Note that $P$ has exactly three edge directions parallel to the edges of its triangular faces. In particular, up to symmetry, Figure 1 shows all the aggregated cones of a triangular prism.

A regular dodecahedron $P$ and two of its opposite edges $e$ and $e^{\prime}$ are depicted on the left of Figure 2. Both of these edges are parallel to the same edge direction $u$. The orthogonal projection of $P$ on $u^{\perp}$ is shown at the center of the figure and the aggregated cone $C_{P}(u)$ is depicted on the right. It can be seen that $C_{P}(u)$ is the union of two opposite cones that do not entirely cover $u^{\perp}$. In particular, this illustrates that, while $C_{P}(u)$ is always a cone, this cone is not always convex. It should be noted that $P$ is not equiprojective: its orthogonal projection on a plane parallel to a facet is a decagon while its orthogonal projection along a line through two opposite vertices is a dodecagon. However, an example of an equiprojective polytope with a non-convex aggregated cone—the equitruncated tetrahedron [10]—will be discussed in Section 6. Observe that, by the symmetries of the regular dodecahedron, the aggregated cones at the edges of this polytope are all equal up to isometry. In particular, Figure 2 depicts all the aggregated cones of the regular dodecahedron.

Note that a facet $F$ of $P$ has at most two edges parallel to any given edge direction $u$ of $P$. Moreover, $F$ has exactly one edge parallel to $u$ if and only if the normal cone of $P$ at $F$ is one of the half-lines that compose the relative boundary of $C_{P}(u)$. We will use this in the proof of Theorem 1.3. This theorem is an equivalence and we shall prove two separate implications.

The following lemma states the other implication from Theorem 1.3. It will be proven via Theorem 3.2 by constructing an explicit partition of the set of all edge-facet incidences into compensating pairs.

Theorem 1.3 is obtained by combining Lemmas 3.6 and 3.7. Let us illustrate this theorem on our examples from Figures 1 and 2. It is well known that a triangular prism is equiprojective [10, 11]. This can be immediately be recovered from Theorem 1.3 by observing that the aggregated cones of a triangular prism at its edge directions are either planes or half-planes as shown in Figure 1. In contrast, a regular dodecahedron is not equiprojective and this can also be obtained from Theorem 1.3. Indeed, the aggregated cones of a regular dodecahedron at its edge directions, depicted in Figure 2, are the union of two opposite cones that do not collectively cover the plane that they span.

In this section, we exploit Theorem 1.3 in order to study the equiprojectivity of Minkowski sums. We will also determine the value of $k$ for which a polytope or a Minkowski sum of polytopes is $k$-equiprojective.

Note that, in Definition 4.1, $P$ can be a $3$-dimensional polytope, a polygon or a line segment. From now on, we denote by $\kappa(P)$ the value of $k$ such that an equiprojective polytope $P$ is $k$-equiprojective.

Now recall that the faces of the Minkowski sum of two polytopes $P$ and $Q$ can be recovered from the normal cones of these polytopes (see for instance Proposition 7.12 in [22]): the faces of $P+Q$ are precisely the Minkowski sums of a face $F$ of $P$ with a face $G$ of $Q$ such that the relative interiors of $N_{P}(F)$ and $N_{Q}(G)$ are non-disjoint. For this reason, Theorem 1.3 provides a convenient way to determine how equiprojectivity behaves under Minkowski sums.

Recall that the multiplicity of edge directions is defined for polygons and line segments and not just for $3$-dimensional polytopes. From now on, if $P$ is a polygon or a line segment contained in $\mathbb{R}^{3}$, we denote

by analogy with Theorem 4.2, where the sum is over the edge directions $u$ of $P$. It should be noted that when $P$ is a polygon, $\kappa(P)$ is equal to the number of edges of $P$ and when $P$ is a line segment, $\kappa(P)$ is always equal to $2$.

Consider two polytopes $P$ and $Q$ contained in $\mathbb{R}^{3}$. If each of them is an equiprojective polytope, a polygon, or a line segment, then we denote

where $s$ is the number of edge directions $u$ common to $P$ and $Q$ such that both $C_{P}(u)$ and $C_{Q}(u)$ are equal to $u^{\perp}$ while $r$ is the number of edge directions $u$ common to $P$ and $Q$ such that the cones $C_{P}(u)$ and $C_{Q}(u)$ are not both equal to $u^{\perp}$ and one of them is contained in the other.

Observe that when two polytopes $P$ and $Q$ do not share an edge direction, $\lambda(P,Q)$ vanishes. Hence, we obtain the following corollary from Theorems 4.3 and 4.4. In turn, that corollary immediately implies Theorem 1.4.

The goal of this section is to build many $k$-equiprojective polytopes when $k$ is a large enough odd integer. This will be done using Minkowski sums between zonotopes with $(k-3)/2$ generators and well-chosen triangles. In this section, all the considered polytopes are contained in $\mathbb{R}^{3}$.

For any $3$-dimensional zonotope $Z$, we consider a triangle $t_{Z}$ whose edge directions do not belong to any of the planes spanned by two edge directions of $Z$ and such that the plane spanned by the edge directions of $t_{Z}$ does not contain any edge direction of $Z$. Note that such a triangle always exists because $Z$ and $t_{Z}$ have only finitely many edge directions. A consequence of these requirements is that $t_{Z}$ does not share any edge direction with $Z$. Moreover, the normal cones of $Z$ at its facets are never contained in the normal cone of $t_{Z}$ at itself or in the plane spanned by the normal cone of $t_{Z}$ at one of its edges (see Figure 4 for an illustration of the normal cones of a triangle at its edges and at itself). Inversely, the normal cone of $t_{Z}$ at itself is not contained in the plane spanned by the normal cone of $Z$ at any of its edges. It should be noted that there are many possible choices for $t_{Z}$ but we fix that choice for each zonotope $Z$ so that $Z\mapsto{t_{Z}}$ defines a map that sends a zonotope to a triangle.

It follows from the results of Section 4 that the Minkowski sum of $Z$ with $t_{Z}$ is always an equiprojective polytope.

Recall that the normal cones of a polytope $P$ ordered by reverse inclusion collectively form a lattice $\mathcal{N}(P)$, called the normal fan of $P$ and that

is an isomorphism (see for instance Exercise 7.1 in [22]). Note that in this context, an isomorphism is a bijective morphism between two lattices. It will be important to keep in mind that $N_{P}$ reverses inclusion. This correspondence between the face lattice and the normal fan of a polytope will be useful in order to determine the combinatorial type of the Minkowski sum between a $3$-dimensional zonotope $Z$ and its associated triangle $t_{Z}$.

Further recall that a face $F$ of $Z+t_{Z}$ is uniquely written as the Minkowski sum of a face of $Z$ with a face of $t_{Z}$. We will denote by $\tau_{Z}(F)$ the face of $t_{Z}$ that appears in this Minkowski sum. Note that $\tau_{Z}$ defines a morphism from the face lattice of $Z+t_{Z}$ to that of $t_{Z}$ in the sense that it preserves face inclusion. This is a consequence, for instance of Proposition 7.12 from [22].

The remainder of the section is mostly devoted to proving that if $Z+t_{Z}$ and $Z^{\prime}+t_{Z^{\prime}}$ have the same combinatorial type, then so do $Z$ and $Z^{\prime}$. This will be done via two lemmas. The first of these lemmas is the following.

Recall that, for an arbitrary $3$-dimensional zonotope $Z$, a face $F$ of $Z+t_{Z}$ is the Minkowski sum of a unique face of $Z$ with $\tau_{Z}(F)$. We will denote by $\zeta_{Z}(F)$ the face of $Z$ that appears in this sum. This defines a morphism $\zeta_{Z}$ from $\mathcal{F}(Z+t_{Z})$ to $\mathcal{F}(Z)$. We will derive a statement similar to Lemma 5.2 regarding $\zeta_{Z}$. In order to do that, we first establish the following proposition as a consequence of our requirements for the choice of $t_{Z}$.