A counterexample to the Hirsch conjecture

Introduction

The Hirsch conjecture is the following fundamental statement about the combinatorics of polytopes. It was stated by Warren M. Hirsch in 1957 in the context of the simplex method, and publicized by G. Dantzig in his 1963 monograph on linear programming :

The (combinatorial) diameter of a polytope of dimension $d$ with $n$ facets cannot be greater than $n-d$.

Here we call combinatorial diameter of a polytope the maximum number of steps needed to go from one vertex to another, where a step consists in traversing an edge. Since we never refer to any other diameter in this paper, we will often omit the word “combinatorial”. We say that a polytope is Hirsch if it satisfies the conjecture, and non-Hirsch if it does not.

Our main result (Corollary 1.7) is the construction of a $43$-dimensional polytope with $86$ facets and diameter (at least) $44$. Via products and glueing copies of it we can also construct an infinite family of polytopes in fixed dimension $d$ with increasing number $n$ of facets and of diameter bigger than $(1+\epsilon)n$, for a positive constant $\epsilon$ (Theorem 1.8).

Linear programming (LP) is the problem of maximizing (or minimizing) a linear functional subject to linear inequality constraints. For more than 30 years the only applicable method for LP was the simplex method, devised in 1947 by G. Dantzig . This method solves a linear program by first finding a vertex of the feasibility region $P$, which is a facet-defined polyhedron, and then jumping from vertex to neighboring vertex along the edges of $P$, always increasing the functional to be maximized. When such a pivot step can no longer increase the functional, convexity guarantees that we are at the global maximum. (A pivot rule has to be specified for the algorithm to choose among the possible neighboring vertices; the performance of the algorithm may depend on the choice).

To this day, the complexity of the simplex method is quite a mystery: exponential (or almost) worst-case behavior of the method is known for most of the pivot rules practically used or theoretically proposed. (For two recent breakthrough additions see ). But on the other hand, as M. Todd recently put it, “the number of steps [that the simplex method takes] to solve a problem with $m$ equality constraints in $n$ nonnegative variables is almost always at most a small multiple of $m$, say $3m$” . Because of this “the simplex method has remained, if not the method of choice, a method of choice, usually competitive with, and on some classes of problems superior to, the more modern approaches” . This is so even after the discovery, 30 years ago, of polynomial time algorithms for linear programming by Khachiyan and Karmarkar . In fact, in the year 2000 the simplex method was selected as one of the “10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century” by the journal Computing in Science and Engineering .

It is also worth mentioning that Khachiyan and Karmarkar’s algorithms are polynomial in the bit model of complexity but they are not polynomial in the real number machine model of Blum et al. . Algorithms that are polynomial in both models are called strongly polynomial. S. Smale listed among his “mathematical problems for the next century” the question whether linear programming can be performed in strongly polynomial time. A polynomial pivot rule for the simplex method would answer this in the affirmative.

For information on algorithms for linear programming and their complexity, including attempts to explain the good behavior of the simplex method without relying on bounds for the diameters of all polytopes, see .

Brief history of the Hirsch conjecture

Warren M. Hirsch (1918–2007), a professor of probability at the Courant Institute, communicated his conjecture to G. Dantzig in connection to the simplex method: the diameter of a polytope is a lower bound (and, hopefully, an approximation) to the number of steps taken by the simplex method in the worst-case. Hirsch had verified the conjecture for $n-d\leq 4$ and Dantzig included this statement and the conjecture in his 1963 book [11, p. 160].

The original conjecture did not distinguish between bounded or unbounded feasibility regions. In modern terminology, a bounded one is a (convex) polytope while a perhaps-unbounded one is a polyhedron. But the unbounded case was disproved by Klee and Walkup in 1967 with the construction of a polyhedron of dimension $4$ with $8$ facets and diameter $5$. Since then the expression “Hirsch Conjecture” has been used referring to the bounded case.

In the same paper, Klee and Walkup established the following crucial statement. See a proof in Section 2:

For positive integers $n>d$, let $H(n,d)$ denote the maximum possible diameter of the graph of a $d$-polytope with $n$ facets. Then, $H(n,d)\leq H(2n-2d,n-d)$. Put differently:

$H(n,d)\leq n-d$ for all $n$ and $d$. (Hirsch Conjecture)

$H(2d,d)\leq d$ for all $d$. ($d$-step Conjecture)

The Hirsch conjecture holds for $n\leq d+6$: Klee and Walkup proved the $d$-step conjecture for $d\leq 5$, and the case $d=6$ has recently been verified by Bremner and Schewe . In a previous paper , Klee had shown the Hirsch conjecture for $d=3$. Together with the cases $(n,d)\in\{(11,4),(12,4)\}$ , these are all the parameters where the Hirsch conjecture is known to hold.

The best upper bounds we have for $H(n,d)$ in general are a quasi-polynomial one by Kalai and Kleitman and one linear in fixed dimension proved by Barnette and improved by Larman and then Barnette again . These bounds take the following form (the second one assumes $d\geq 3$):

In particular, no polynomial upper bound is known. Its existence is dubbed the polynomial Hirsch conjecture:

There is a polynomial $f(n)$ such that the diameter of every polytope with $n$ facets is bounded above by $f(n)$.

Of course, apart of its central role in polytope theory, the significance of this conjecture is that polynomial pivot rules cannot exist for the simplex method unless it holds. For more information on these and other results see the chapter that Klee wrote in Grünbaum’s book , and the survey papers .

Our counterexample

The $d$-step Theorem stated above implies that to prove or disprove the Hirsch conjecture there is no loss of generality in assuming $n=2d$. A second reduction is that, for every $n$ and $d$, the maximum of $H(n,d)$ is always achieved at a simple polytope (a $d$-polytope in which every vertex belongs to exactly $d$ facets). Simple polytopes are especially relevant for linear programming: they are obtained when the system of inequalities is sufficiently generic.

The first ingredient in our proof is the observation that if we start with a polytope which is at the same time non-simple and has $n>2d$, then the techniques used in these two reductions can be combined to get a simple $(n-d)$-polytope with $2n-2d$ facets and not only maintain its diameter (or, to be more precise, the distance between two distinguished non-simple vertices), but actually increase it. We call this the Strong $d$-step Theorem and prove it in Section 2. Although the theorem can be stated more generally (see Remark 2.7), the version we need has to do with the following class of polytopes:

A $d$-spindle is a $d$-polytope $P$ having two distinguished vertices $u$ and $v$ such that every facet of $P$ contains exactly one of them. See Figure 1. The length of a spindle is the graph distance between $u$ and $v$.

Equivalently, a spindle is the intersection of two polyhedral convex cones with apices at $u$ and $v$ and with both their interiors containing the open segment $uv$.

If $P$ is a spindle of dimension $d$, with $n$ facets and length $l$, then there is another spindle $P^{\prime}$ of dimension $n-d$, with $2n-2d$ facets and with length at least $l+n-2d$. In particular, if $l>d$ then $P^{\prime}$ violates the $d$-step conjecture, hence also the Hirsch conjecture.

The second ingredient in our disproof is the explicit construction of a spindle of dimension five and length six, that we describe in Section 3:

There is a $5$-dimensional spindle (with $48$ facets and $322$ vertices) of length six.

That our spindle has length six is easy to verify computationally. Still, we include two computer-free proofs in Sections 4 and 5. Putting Theorems 1.5 and 1.6 together we get:

There is a non-Hirsch polytope of dimension $43$ with $86$ facets.

Section 6 is devoted to show how to derive an infinite family of non-Hirsch polytopes from the first one:

There is a fixed dimension $d$, a positive $\epsilon>0$, and an infinite family of $d$-polytopes $P_{k}$ each with $n_{k}$ facets and with diameter bigger than $(1+\epsilon)n_{k}$.

For example, from the non-Hirsch polytope in this paper we get $\epsilon\simeq 1/86$ in dimension $86$ and $\epsilon\simeq 1/43$ in high $d$. With the one announced in (see Theorem 1.12 below) one gets $\epsilon\simeq 1/40$ in dimension $40$ and $\epsilon\simeq 1/20$ in high $d$.

Discussion

Our counterexample disproves as a by-product the following two statements, originally posed in the hope of shedding light on the Hirsch conjecture:

Provan and Billera introduced the hierarchy of $k$-decomposable simplicial complexes: $k$-decomposability is stronger than $(k+1)$-decomposability for every $k$ and the boundary of every simplicial $d$-polytope is $(d-1)$-decomposable (or shellable). They also showed that -decomposable (or vertex decomposable) complexes satisfy (the polar of) the Hirsch conjecture. Non-vertex-decomposable polytopes were previously found by Kleinschmidt [33, p. 742], but it would be interesting to explore whether our non-Hirsch polytope, besides not being -decomposable, fails also to be $1$-decomposable (or higher).

Todd showed that from any unbounded non-Hirsch polyhedron, such as the one previously found by Klee and Walkup, one can easily obtain a counterexample to the so-called monotone Hirsch conjecture. Still, the strict monotone Hirsch conjecture of Ziegler , stronger than the Hirsch conjecture, was open.

Still, our techniques leave the underlying problem–how large can the diameter of a polytope be–almost as open as it was before. In particular, we cannot answer the following question:

Is there a constant $c$ (independent of $d$) such that the diameter of every $d$-polytope with $n$ facets is bounded above by $cn$?

We suspect the answer to be negative, but our lack of knowledge somehow confirms the following sentence from : Finding a counterexample will be merely a small first step in the line of investigation related to the conjecture.

Another “small step” has recently been given by F. Eisenbrand, N. Hähnle, A. Razborov, and T. Rothvoß , with the introduction of certain abstract generalizations of boundary complexes of polyhedra and the construction of objects of super-linear diameter in this generalized setting. By further analyzing this setting, N. Hähnle has posed the following tempting and more explicit version of Conjecture 1.3:

The diameter of every $d$-polytope with $n$ facets is bounded above by $dn$.

Thanks to Remark 6.4 this conjecture is (almost) equivalent to:

The diameter of every $d$-polytope with $n$ facets is bounded above by $d(n-d)$.

To finish, let us mention two additional results that were obtained after the first version of this paper was made public: On the one hand, relying on the reductions that we introduce in Section 5.1, Santos, Stephen and Thomas have shown that all $4$-spindles have length at most $4$ . Hence, spindles of dimension five are truly needed to obtain non-Hirsch polytopes via Theorem 1.5. On the other hand, Matschke, Santos and Weibel have constructed a $5$-spindle of length $6$ with only $25$ facets, from which Theorem 1.6 gives:

There is a non-Hirsch polytope of dimension $20$ with $40$ facets and $36\,442$ vertices. It has diameter $21$.

Apart of the decrease in dimension, the smaller size of this example has allowed us to explicitly compute coordinates for the non-Hirsch polytope in question. Doing the same with the $43$-dimensional example presented in this paper seemed out of reach. We would need to apply $38$ times the operation of wedge followed by perturbation in the proof of Theorem 1.5 (see Section 2.2). Julian Pfeifle (personal communication) wrote a small program to automatically do this and, using a standard desktop computer with 2GB of RAM, was able to undertake the first nine iterations. Experimentally, he found that each iteration more or less doubled the number of vertices (and multiplied by four or five the computation time) indicating that the final non-Hirsch polytope has about $2^{40}$ vertices. To make things worse, the tower of $38$ perturbations would give rise to either huge rational coefficients or very delicate numerical approximation issues.

A strong d𝑑d-step theorem for spindles

We find it easier to work in a polar setting in which we want to travel from facet to facet of a polytope $Q$ crossing ridges (codimension-$2$ faces), rather than travel from vertex to vertex along edges. That is, we are interested in the following dual version of the Hirsch conjecture:

A $d$-polytope $Q$ with $n$ vertices is a dual-Hirsch polytope if $n-d$ dual steps suffice to travel from any facet of $Q$ to any other facet. A dual step consists in moving from one facet $F$ of $Q$ to an adjacent one $F^{\prime}$, meaning by this that $F$ and $F^{\prime}$ share a ridge of $Q$.

Clearly, $Q$ is dual-Hirsch if and only if its polar polytope is Hirsch. In the rest of the paper we omit the word dual from our dual paths and dual steps.

It is known since the 60’s that to prove or disprove the (dual) Hirsch conjecture it is enough to look at simplicial polytopes with twice as many vertices as their dimension. Since our strong $d$-step theorem is based in combining both reductions, let us see how they work.

For the first reduction, following Klee we use the operation of pushing vertices. Let $Q$ be a polytope with vertices $V$ and let $v\in V$ be one of them. We say that a polytope $Q^{\prime}$ is obtained from $Q$ by pushing $v$ if the vertices of $Q^{\prime}$ are $V\setminus\{v\}\cup\{v^{\prime}\}$ for a certain point $v^{\prime}\in Q$ and the only hyperplanes spanned by vertices of $Q$ that intersect the segment $vv^{\prime}$ are those containing $v$. Put differently, the vertex $v$ is pushed to a new position $v^{\prime}$ within the polytope $Q$ but sufficiently close to its original position. We emphasize that we admit $v^{\prime}$ to be in the boundary of $Q$. In the standard notion of pushing, $v^{\prime}$ is required to be in the interior of $Q$.

Let $Q^{\prime}$ be obtained from $Q$ by pushing $v$. Then:

Let $F^{\prime}$ be a facet of $Q^{\prime}$ with vertex set $S^{\prime}$ and let $S=S^{\prime}\setminus\{v^{\prime}\}\cup\{v\}$ or $S=S^{\prime}$ depending on whether $v^{\prime}\in F^{\prime}$ or not. Then, there is a unique facet $\phi(F^{\prime})$ of $Q$ such that $S\subset\phi(F^{\prime})$.

The map $F^{\prime}\mapsto\phi(F^{\prime})$ sends adjacent facets of $Q^{\prime}$ to either the same or adjacent facets of $Q$. (That is, $\phi$ is a simplicial map between the dual graphs of $Q^{\prime}$ and $Q$).

For part (1), consider what happens when we continuously move $v^{\prime}$ to its original position $v$ along the segment $vv^{\prime}$. We call $Q(t)$, $F(t)$, $S(t)$ and $v(t)$ the polytope, facet, vertex set, and vertex obtained at moment $t$, with $v^{\prime}=v(1)$ and $v=v(0)$. The assumption that no hyperplane spanned by vertices of $Q$ intersects $vv^{\prime}$ unless it contains $v$ implies that the combinatorics of $Q(t)$ remains the same at every moment $t>0$; changes will happen only at $t=0$. Now, every facet-defining hyperplane of $Q(t)$ will tend to a facet-defining hyperplane of $Q(0)$ (which implies part (1)) unless the vertex set $S(t)$ spanning a certain facet $F(t)$ collapses to lie in a flat of codimension two. Put differently, unless $F(t)$ is a pyramid with apex at $v(t)$ over a codimension two face $G^{\prime}$ of $Q^{\prime}$ with $v$ in the affine span of $G^{\prime}$. We claim that the assumption $v^{\prime}\in Q$ rules out this possibility. Indeed, in this situation the hyperplane $H^{\prime}$ spanned by $F(t)$ is independent of $t$ for $t>0$ and it contains the segment $vv^{\prime}$. Let $w$ be the last point where the ray from $v$ through $v^{\prime}$ meets $Q$. Then, $w$ is a convex combination of vertices of $Q$ different from $v$ and it lies in the hyperplane $H^{\prime}$, so it lies in the facet $F(t)$ for every $t>0$. Since $w$ is further from $G^{\prime}$ than $v(t)$, $F(t)$ cannot be a pyramid with apex at $v(t)$ and base $G^{\prime}$.

For part (2) we reinterpret (the proof of) part (1) as saying: when $t$ goes from $1$ to the combinatorics of $Q^{\prime}$ remains the same except that at $t=0$ some groups of facets of $Q^{\prime}$ merge to single facets of $Q$. This implies the claim. ∎

For every polytope $Q$ there is a simplicial polytope $Q^{\prime}$ of the same dimension and number of vertices and with the same or greater dual diameter. ∎

In this formula, $F*u$ denotes the pyramid over $F$ with apex at $u$. See or for more details, and Figure 2 for an illustration. One-point-suspensions appear in the literature also under other names, such as dual wedges or vertex splittings.

Let $F_{1}$ and $F_{2}$ be two facets of a polytope $Q$ and let $\widetilde{Q}:=\operatorname{S}_{v}(Q)$ for some vertex $v$. For $i=1,2$, let $\widetilde{F}_{i}\leq\widetilde{Q}$ denote the facet $\operatorname{S}_{v}(F_{i})$ if $v\in F_{i}$ or one of the facets $F_{i}*u$ or $F_{i}*w$ if $v\not\in F_{i}$. Then, the distance between $\widetilde{F}_{1}$ and $\widetilde{F}_{2}$ in the dual graph of $\widetilde{Q}$ is greater or equal than the distance between $F_{1}$ and $F_{2}$ in the dual graph of $Q$.

The dual graph of $\widetilde{Q}$ projects down to that of $Q$ by sending each facet $\operatorname{S}_{v}(F)$, $F*u$ or $F*w$ to the facet $F$ of $Q$ that it came from. Graph-theoretically, this projection amounts to contracting all the dual edges between $F*u$ and $F*w$, for each facet $F\leq Q$ not containing $v$. ∎

We prove that $H(n,d)\leq H(2n-2d,n-d)$ by induction on $|n-d|$ and separating the cases $n>2d$ and $n<2d$: If $n<2d$ then every pair $u,v$ of vertices of a $d$-polytope $P$ with $n$ facets lie in some common facet $F$. $F$ is a polytope of dimension $d-1$ with at most $n-1$ facets so the distance from $u$ to $v$ in $F$ is bounded by $H(n-1,d-1)$. If $n>2d$, apply Lemma 2.4 to a $d$-polytope $Q$ with $n$ vertices whose dual diameter achieves $H(n,d)$, to get $H(n,d)\leq H(n+1,d+1)$. ∎

2 The strong d𝑑d-step Theorem

The following class of polytopes are the polars of the spindles mentioned in Theorem 1.5:

A prismatoid is a polytope having two parallel facets $Q^{+}$ and $Q^{-}$ that contain all vertices. We call $Q^{+}$ and $Q^{-}$ the base facets of $Q$. The width of a prismatoid is the dual graph distance between $Q^{+}$ and $Q^{-}$.

The “base facets” of a prismatoid may not be unique, but they are part of the definition. For example, a cube or an octahedron are prismatoids with respect to any of their pairs of opposite facets. Observe that the requirement of $Q^{+}$ and $Q^{-}$ to be parallel is not especially relevant, as long as they are disjoint. If $Q^{+}$ and $Q^{-}$ are disjoint facets of an arbitrary polytope $Q$ then a projective transformation can make them parallel without changing the combinatorics of $Q$ (see, e. g., [45, p. 69]). The following statement is equivalent to Theorem 1.5:

If $Q$ is a prismatoid of dimension $d$ with $n$ vertices and width $l$, then there is another prismatoid $Q^{\prime}$ of dimension $n-d$, with $2n-2d$ vertices and width at least $l+n-2d$. In particular, if $l>d$ then $Q^{\prime}$ violates the (dual) $d$-step conjecture, hence also the (dual) Hirsch conjecture.

We call the number $s=n-2d$ the asimpliciality of $Q$ and prove the theorem by induction on $s$. Since every facet of a $d$-polytope has at least $d$ vertices, $s$ is always non-negative. The base case of $s=0$ is tautological. For the inductive step, we show that if $s>0$ we can construct from $Q$ a new prismatoid $\widetilde{Q}$ with dimension one higher, one vertex more (in particular, the “asimpliciality” has decreased by one), and width at least one more than $Q$.

Since $s>0$, at least one of $Q^{+}$ and $Q^{-}$, say $Q^{+}$, is not a simplex (the other one, $Q^{-}$, may or may not be a simplex). Let $v$ be a vertex of $Q^{-}$, and let $\operatorname{S}_{v}(Q)$ be the one-point-suspension of $Q$ over $v$. Let $\widetilde{Q}^{-}=\operatorname{S}_{v}(Q^{-})$ be the one-point-suspension of $Q^{-}$, which appears as a facet of $\operatorname{S}_{v}(Q)$. Observe that $\operatorname{S}_{v}(Q)$ is almost a prismatoid: its faces $\widetilde{Q}^{-}$ and $Q^{+}$ contain all vertices and they lie in two parallel hyperplanes. The only problem is that $Q^{+}$ is not a facet, it is a ridge; but since we know that $Q^{+}$ is not a simplex, moving its vertices slightly in the direction of the segment $uw$ creates a new facet $\widetilde{Q}^{+}$ parallel to $\widetilde{Q}^{-}$, and these two facets contain all the vertices of the new polytope, that we denote $\widetilde{Q}$ and is a prismatoid. (In fact, moving a single vertex of $Q^{+}$ is enough to achieve this). See Figure 3 for an illustration. In the figure, we draw several points along the edge $Q^{+}$ to convey the fact that $Q^{+}$ is not a simplex; these points have to be understood as vertices of $Q$.

By Lemma 2.4, the distance from $\widetilde{Q}^{-}$ to any of $Q^{+}*u$ and $Q^{+}*w$ in $\operatorname{S}_{v}(Q)$ is (at least) $l$. To make sure that the width of $\widetilde{Q}$ is at least $l+1$ we do the perturbation from $\operatorname{S}_{v}(Q)$ to $\widetilde{Q}$ in the following special manner: let $a$ be a vertex of $Q^{+}$ and assume that the only non-simplicial facets of $\operatorname{S}_{v}(Q)$ containing $a$ are $Q^{+}*u$ and $Q^{+}*w$ (if that is not the case, we first push $a$ to a point in the interior of $Q^{+}$ but otherwise generic, which maintains all the properties we need and does not decrease the dual distances, by Lemma 2.2). We now get $\widetilde{Q}$ by moving only $a$, in a direction parallel to $Q^{-}$ and away from $Q^{+}$, to a position $a^{\prime}$. Then $Q^{+}$ will be replaced by a pyramid $\widetilde{Q}^{+}:=\operatorname{conv}(\operatorname{vertices}(Q^{+})\setminus a)*a^{\prime}$.

The genericity assumption on $a$ implies that apart from the creation of $\widetilde{Q}^{+}$, the only change to the face lattice of $\operatorname{S}_{v}(Q)$ is that the two facets $Q^{+}*u$ and $Q^{+}*w$ get refined as two complexes $U*u$ and $W*w$ where $U$ and $W$ are the lower and upper envelopes of the facet $\widetilde{Q}^{+}$ (here we are considering the direction $uw$ as vertical, with $w$ above $u$). The width of $\widetilde{Q}$ is at least $l+1$ since in order to get out of $\widetilde{Q}^{+}$ the first step will send us to a facet in either $U*u$ or $W*w$, and that facet is at least at the same distance from $\widetilde{Q}^{-}$ as $Q^{+}*u$ or $Q^{+}*w$ were, by the same arguments as in the proof of Lemma 2.2. ∎

The following version of the strong $d$-step theorem is also true, with essentially the same proof: Let $Q$ be a $d$-polytope with $n$ vertices and containing two disjoint facets $Q^{+}$ and $Q^{-}$ that use in total $m$ of the vertices, for some $m>2d$. Let $l$ be the dual graph distance from $Q^{+}$ to $Q^{-}$. Then, there is a $(m-d)$-polytope $Q^{\prime}$ with $n+m-2d$ vertices and having two facets ${Q^{+}}^{\prime}$ and ${Q^{-}}^{\prime}$ at distance $l+m-2d$. In particular, if $l>(n-m)+d$ then $Q^{\prime}$ is non-Hirsch. The prismatoid version is the case $n=m$.

A 555-prismatoid without the d𝑑d-step property

In the light of Theorem 2.6, we say that a prismatoid has the $d$-step property if its width does not exceed its dimension. It is an easy exercise to show that every $3$-dimensional prismatoid has this property. For $4$-dimensional ones, the result is still true is true, although not obvious anymore . In dimension five, however, we have the following statement, which implies Theorem 1.6:

The $5$-dimensional prismatoid with the $48$ rows of the matrices of Table 1 as vertices has width six.

$Q$ is small enough for the statement of Theorem 3.1 to be verified computationally, which has been done independently by Edward D. Kim and Julian Pfeifle with the software polymake . Still, in sections 4 and 5 we give two computer-free (but not “computation-free”) proofs. Before going into details we list some properties of $Q$ which follow directly from its definition:

The first $24$ vertices (labeled $\mathit{1}^{+}$ to $\mathit{24}^{+}$) and the last $24$ vertices (labeled $\mathit{1}^{-}$ to $\mathit{24}^{-}$) span two facets of $Q$, that we denote $Q^{+}$ and $Q^{-}$, lying in the hyperplanes $\{x_{5}=+1\}$ and $\{x_{5}=-1\}$. Hence, $Q$ is indeed a prismatoid.

$Q$ is symmetric under the orthogonal transformation $(x_{1},x_{2},x_{3},x_{4},x_{5})\mapsto(x_{4},x_{3},x_{1},x_{2},-x_{5})$, and this symmetry sends $Q^{+}$ to $Q^{-}$, with the vertex labeled $\mathit{i}^{+}$ going to the one labeled $\mathit{i}^{-}$. (Observe, however, that this symmetry is not an involution).

$Q^{+}$ and $Q^{-}$ (hence also $Q$) are themselves invariant under any of the following $32$ orthogonal transformations:

That is, they are symmetric under changing the sign of any of the first four coordinates and also under the simultaneous transpositions $x_{1}\leftrightarrow x_{2}$ and $x_{3}\leftrightarrow x_{4}$.

In what follows we denote $\Sigma$ the symmetry group of $Q$ (of order $64$) and $\Sigma^{+}$ the index-two subgroup that preserves $Q^{+}$ and $Q^{-}$.

First proof of Theorem 3.1

The first proof of Theorem 3.1 goes by explicitly describing the adjacency graph between orbits of facets of $Q$ which, thanks to symmetry, is not too difficult:

The $2+20\times 16=322$ inequalities of Table 2 define facets of $Q$. $\rm A$ and $\rm L$ are the bases of the prismatoid. Among the rest, the $32$ labeled with the same letter form a $\Sigma^{+}$-orbit. There are six $\Sigma$-orbits, obtained as the $\Sigma^{+}$-orbit unions $\rm A\cup L$, $\rm B\cup K$, $\rm C\cup J$, $\rm D\cup I$, $\rm E\cup H$, and $\rm F\cup G$.

The only adjacencies between facets of $Q$ in different $\Sigma^{+}$-orbits of facets of $Q$ are the ones shown in Figure 4.

Part 3 implies Theorem 3.1: in Figure 4 it is clear that six steps are necessary (and sufficient) to go from the facet $Q^{+}$ to the facet $Q^{-}$ (labeled $\rm A$ and $\rm L$).

In part one, the assertions about $\Sigma$ and $\Sigma^{+}$-orbits are straightforward, from the aspect of the inequalities. To check that these $322$ inequalities define facets, we need to consider a single representative from each $\Sigma$-orbit. For the base facets this is obvious, and for the rest we choose the following representatives:

We leave it to the reader to check that these five inequalities are satisfied on all $48$ vertices of $Q$, and with equality precisely in the vertices listed for each in Table 3. This task is not as hard as it seems since only the vertices with non-negative coordinates $x_{1}$, $x_{2}$, $x_{3}$ and $x_{4}$ need to be checked (there are sixteen of them). The five matrices have rank five, which shows that the vertices in each of them span at least an affine hyperplane. Hence, they all define facets of $Q$.

For parts 2 and 3 we look more closely at the matrices in Table 3 and observe that:

The facets of types $D$, $E$ and $F$ are simplices, since they have five vertices: three in $Q^{+}$ and two in $Q^{-}$ or vice-versa.

The facets of type $C$ are iterated pyramids, with two apices in $Q^{-}$, over a quadrilateral in $Q^{+}$. Indeed, the vertices $\mathit{9}^{+}$, $\mathit{13}^{+}$, $\mathit{17}^{+}$ and $\mathit{21}^{+}$ form a planar quadrilateral, since

The facets of type $B$ are pyramids, with apex in $Q^{-}$ over a triangular prism in $Q^{+}$. Indeed, the six vertices in $Q^{+}$ form a triangular prism since the rays $\overrightarrow{v_{\mathit{1}^{+}}v_{\mathit{5}^{+}}}$, $\overrightarrow{v_{\mathit{9}^{+}}v_{\mathit{17}^{+}}}$, and $\overrightarrow{v_{\mathit{21}^{+}}v_{\mathit{13}^{+}}}$ collide at the point $o=(-30,0,120,0,1)$. This follows from the following equalities, and is illustrated in Figure 5.

With this information, we can prove parts 2 and 3 together by simply constructing the dual graph, that is, by looking at adjacencies between facets. The simplices of types $D$, $E$ and $F$ need to have five neighboring facets, the double pyramid of type $C$ needs six, and the pyramid over a triangular prism needs six too. So, it suffices to check the following adjecencies, which can be done by tracking the vertices in the five representative facets and the permutations of facets within each $\Sigma$-orbit induced by the symmetries of $Q$:

The following facets are neighbors of $B_{+,+,+,+}$:

The following facets are neighbors of $C_{+,+,+,+}$:

The following facets are neighbors of $D_{+,+,+,+}$:

The following facets are neighbors of $E_{+,+,+,+}$:

The following facets are neighbors of $F_{+,+,+,+}$:

Second proof of Theorem 3.1

The second proof of Theorem 3.1 reduces the study of the combinatorics of $d$-prismatoids to that of pairs of geodesic maps in the $(d-2)$-sphere.

The intersection of a prismatoid with an intermediate hyperplane equals the Minkowski sum $Q^{+}+Q^{-}$ of its two bases. More precisely:

If $Q$ is a prismatoid with base facets $Q^{+}$ and $Q^{-}$ and $H$ is an intermediate hyperplane parallel to $Q^{+}$ and $Q^{-}$ then

where $\lambda_{1}+\lambda_{2}=1$ and $\lambda_{1}:\lambda_{2}=\operatorname{dist}(H,Q^{+}):\operatorname{dist}(H,Q^{-})$ (the ratio of distances from $H$ to $Q^{+}$ and $Q^{-}$). ∎

Every face $F$ (facet or not) of a Minkowski sum $Q^{+}+Q^{-}$ decomposes uniquely as a sum $F^{+}+F^{-}$ of faces of $Q^{+}$ and $Q^{-}$. We call bi-dimension of $F$ the pair $(\dim(F^{+}),\dim(F^{-}))$. Proposition 5.1 implies that every facet of $Q$ other than the two bases induces a facet in the Minkowski sum $Q^{+}+Q^{-}$. More precisely, the dual graph of $Q^{+}+Q^{-}$ equals the dual graph of $Q$ with the two base facets removed. Since the facets of $Q^{+}+Q^{-}$ corresponding to facets of $Q$ adjacent to $Q^{+}$ (respectively, to $Q^{-}$) are those of bi-dimension $(d-1,*)$ (respectively, $(*,d-1)$), the $d$-step property for $Q$ translates to the following property for the pair of polytopes $(Q^{+},Q^{-})$:

Let $Q^{+}$ and $Q^{-}$ be two polytopes of dimension $d-1$ with the same or parallel affine spans. The pair $(Q^{+},Q^{-})$ has the $d$-step property if there is a sequence $F_{1},F_{2},\dots,F_{k}$ of facets of $Q^{+}+Q^{-}$, with $k\leq d-1$, such that:

The bi-dimension of $F_{1}$ and the bi-dimension of $F_{k}$ are $(d-1,*)$ and $(*,d-1)$.

$F_{i}$ is adjacent to $F_{i+1}$ for all $i$.

That is to say, we ask whether we can go from an $F$ to an $F^{\prime}$ in $d-2$ steps, where $F$ and $F^{\prime}$ are facets of $Q^{+}+Q^{-}$ of a special type.

A prismatoid with base facets $Q^{+}$ and $Q^{-}$ has the $d$-step property if, and only if, the pair $(Q^{+},Q^{-})$ has the $d$-step property. ∎

The good thing about Proposition 5.3 is that it reduces the dimension by one. In order to study our prismatoid of dimension five we only need to understand its two bases, of dimension four. Before doing this let us make one more translation, to the language of normal fans or normal maps.

The normal cones of faces of $P$ form a complex $\mathcal{N}(P)$ of polyhedral cones called the normal fan of $P$. We call the intersection of this fan with the unit sphere the normal map of $P$. (This is called the gaussian map of $P$ in . Incidentally, the reading of was our initial inspiration for attempting to disprove the Hirsch conjecture via prismatoids). The normal map of a $d$-polytope $P$ is a polyhedral complex of spherical polytopes decomposing $S^{d-1}$. We call such objects geodesic maps. (A priori, a geodesic map may not be the normal map of any polytope).

The following definition and theorem translate Proposition 5.3 into the language of geodesic maps. Note that since our polytopes $Q^{+}$ and $Q^{-}$ are meant to be facets of a $d$-polytope, their normal maps lie in the sphere $S^{d-2}$.

Let $\mathcal{G}^{+}$ and $\mathcal{G}^{-}$ be two geodesic maps in the sphere $S^{d-2}$.

The common refinement of $\mathcal{G}^{+}$ and $\mathcal{G}^{-}$ is the geodesic map whose cells are all the possible intersections of a cell of $\mathcal{G}^{+}$ and a cell of $\mathcal{G}^{-}$.

The pair $(\mathcal{G}^{+},\mathcal{G}^{-})$ has the $d$-step property if the 1-skeleton of their common refinement contains a path of length at most $d-2$ from a vertex of $\mathcal{G}^{+}$ to a vertex of $\mathcal{G}^{-}$.

Using the formalism of geodesic maps, Santos, Stephen and Thomas have shown that $4$-prismatoids have the $d$-step property. That is to say, they show that if a pair of graphs is embedded in the $2$-sphere it is always possible to go from a vertex of one to a vertex of the other traversing at most two edges of their common refinement. The following example, which can be understood as a pair of geodesic maps in the flat torus, shows that the reason for this is not “local”.

Figure 6 shows (portions of) two maps drawn in the plane, one with its 1-skeleton in black and the other in grey. They are meant to be periodic and have the same symmetry group, vertex-transitive in both. The pair does not have the $d$-step property. We cannot go in two steps from a vertex $v$ of the black map to a vertex of the grey map.

$Q^{+}$ has 32 facets, given by the following inequalities:

The symmetry group $\Sigma^{+}$ of $Q^{+}$ acts transitively on them.

Observe that Lemma 5.7 describes $Q^{+}$ as the intersection of two cross-polytopes, so its polar is the common convex hull of two combinatorial $4$-cubes. This partially explains why this polar is a cubical polytope (see Remark 5.8 below).

That $\Sigma^{+}$ acts transitively on these inequalities is clear from the form of them and the description of $\Sigma^{+}$ in Section 3. Symmetry has the consequence that in order to prove that all the inequalities define facets we just need to consider one of them. Take for instance:

Direct inspection shows that the inequality is valid on the $24$ vertices of $Q^{+}$, and that it is met with equality precisely in the following six:

Since the top $4\times 4$ submatrix is regular, these six points span the affine hyperplane $5x_{1}+x_{2}+2x_{3}+x_{4}=90$, hence they define a facet $F$.

We still need to check that there are no other facets apart from the $32$ in the statement. For this consider the following equalities, in which $v_{i^{+}}$ represents (the actual vector of coordinates of) the vertex labeled ${i}^{+}$:

These equalities say that the rays $\overrightarrow{v_{\mathit{1}^{+}}v_{\mathit{5}^{+}}}$, $\overrightarrow{v_{\mathit{9}^{+}}v_{\mathit{17}^{+}}}$, and $\overrightarrow{v_{\mathit{21}^{+}}v_{\mathit{13}^{+}}}$ collide at the point $o=(-30,0,120,0,1)$, so that $F$ is combinatorially a triangular prism, as was shown in Figure 5. So, we only need to check that the five neighbors of $F$ are in our stated list of facets. This is true since:

$v_{\mathit{5}^{+}},v_{\mathit{13}^{+}},v_{\mathit{17}^{+}}\in\{-5x_{1}+x_{2}+2x_{3}+x_{4}=90\}$ ($x_{1}=0$ in these points).

$v_{\mathit{1}^{+}},v_{\mathit{5}^{+}},v_{\mathit{13}^{+}}v_{\mathit{21}^{+}}\in\{5x_{1}-x_{2}+2x_{3}+x_{4}=90\}$ ($x_{2}=0$ in them).

$v_{\mathit{1}^{+}},v_{\mathit{9}^{+}},v_{\mathit{21}^{+}}\in\{5x_{1}+x_{2}-2x_{3}+x_{4}=90\}$ ($x_{3}=0$ in them).

$v_{\mathit{1}^{+}},v_{\mathit{5}^{+}},v_{\mathit{9}^{+}},v_{\mathit{17}^{+}}\in\{5x_{1}+x_{2}+2x_{3}-x_{4}=90\}$ ($x_{4}=0$ in them).

$v_{\mathit{9}^{+}},v_{\mathit{13}^{+}},v_{\mathit{17}^{+}},v_{\mathit{21}^{+}}\in\{x_{1}+5x_{2}+x_{3}+2x_{4}=90\}$.

This description of the facets of $Q^{+}$ translates nicely to the normal map $\mathcal{G}^{+}$ of $Q^{+}$. For the sake of having nice integer coordinates, we consider this map as lying in the sphere of radius $\sqrt{31}$ rather than radius $1$ (but we still denote this dilated sphere $S^{3}$, for simplicity). That is, the vertices of $\mathcal{G}^{+}$ are the following points:

Observe they all lie in a torus $\{x_{1}^{2}+x_{2}^{2}=26,x_{3}^{2}+x_{4}^{2}=5\}$, which we denote $T^{+}$ It is quite natural then to picture them on the flat torus. This is what we do in Figure 7, where the horizontal and vertical coordinates represent the angle along the circles $\{x_{1}^{2}+x_{2}^{2}=26\}$ and $\{x_{3}^{2}+x_{4}^{2}=5\}$, respectively.

The grey dashed lines divide the torus into its sixteen octants. The 32 dots are the vertices of $\mathcal{G}^{+}$, and the segments joining them represent its edges. Of course, the true edges in $S^{3}$ do not go along $T^{+}$. In particular, the crossings we see in the picture are an artifact.

As seen in the matrix defining $Q^{+}$, there are five orbits of facets of $\mathcal{G}^{+}$ (i.e., vertices of $Q^{+}$) modulo $\Sigma^{+}$. Representatives of them are, for example, the normal cones of vertices $\mathit{3}^{+}$, $\mathit{7}^{+}$, $\mathit{9}^{+}$, $\mathit{13}^{+}$, and $\mathit{22}^{+}$ which we highlight in Figure 8. The eight “vertical strips” in the orbits of $\operatorname{cone}(\mathit{3}^{+})$ and $\operatorname{cone}(\mathit{9}^{+})$ glue together to form a (polyhedral) solid torus subdivided into eight slices, each of which is combinatorially a $3$-cube. The eight horizontal strips form a second solid torus. These two tori are glued along the sixteen diagonal edges and eight of the vertical rectangles in the pictures, leaving eight empty regions in between. These regions are filled in by the other eight cones, in the orbit of $\operatorname{cone}(\mathit{22}^{+})$.

All the facets of $\mathcal{G}^{+}$ are combinatorially equivalent to the $3$-cube. That is, $Q^{+}$ is polar to a cubical polytope. In fact, it was communicated to us by M. Joswig and G. Ziegler that the polar of $Q^{+}$ is one of the neighborly cubical polytopes (with the graph of the $5$-cube) that they constructed in and had been previously found by Blind and Blind .

Now that we understand $\mathcal{G}^{+}$, let us draw the normal map $\mathcal{G}^{-}$ of $Q^{-}$, whose vertices are (remember the symmetry that sends $Q^{+}$ to $Q^{-}$):

Every vertex of $\mathcal{G}^{-}$ lies in the interior of one of the four facets of $\mathcal{G}^{+}$ of the orbit of $\operatorname{cone}(\mathit{7}^{+})$.

Similarly, every vertex of $\mathcal{G}^{+}$ lies in the interior of one of the four facets of $\mathcal{G}^{-}$ of the orbit of $\operatorname{cone}(\mathit{7}^{-})$.

If $v$ is a vertex of $\mathcal{G}^{+}$ and $C$ the facet of $\mathcal{G}^{-}$ containing it, no vertex of $C$ lies in a facet of $\mathcal{G}^{+}$ having $v$ as a vertex.

Since both maps have the same symmetry group (the group $\Sigma^{+}$ of the previous section) and the group is transitive on the vertices, we only need to prove the lemma for a single vertex $v$. We take $v=(5,1,2,1)$ and show that it is contained in the interior of the facet $\operatorname{cone}(\mathit{5}^{-})$. By definition, the vertices of $\mathcal{G}^{-}$ on this facet are those satisfying the equation $45x_{1}=90$, that is, $x_{1}=2$. They are the eight vertices of the form:

Hence, the facet inequality description of $\operatorname{cone}(\mathit{5}^{-})$ is:

The proof of part one (and two) finishes by noticing that $(5,1,2,1)$ satisfies these six inequalities strictly.

For part three, we look at what facets of $\mathcal{G}^{+}$ contain the vertices of $\operatorname{cone}(\mathit{5}^{-})$. They have to be in the $\Sigma^{+}$-orbit of $\operatorname{cone}(\mathit{7}^{+})$ and the pictures (see Figure 10) tell us that they are the facets $\operatorname{cone}(\mathit{7}^{+})$ and $\operatorname{cone}(\mathit{8}^{+})$, none of whose vertices is the original $v$. ∎

Part 3 of Lemma 5.9 is the key to finishing the proof of Theorem 3.1. In the following statement we say that a pair $(\mathcal{G}^{+},\mathcal{G}^{-})$ of geodesic maps on $S^{d-2}$ are transversal if whenever respective cells $C_{1}$ and $C_{2}$ of them intersect we have

Let $(\mathcal{G}^{+},\mathcal{G}^{-})$ be a transversal pair of geodesic maps in the $(d-2)$-sphere. If there is a path of length $d-2$ between a vertex $v_{1}$ of $\mathcal{G}^{+}$ and a vertex $v_{2}$ of $\mathcal{G}^{-}$, then the facet of $\mathcal{G}^{-}$ containing $v_{1}$ in its interior has $v_{2}$ as a vertex and the facet of $\mathcal{G}^{+}$ containing $v_{2}$ in its interior has $v_{1}$ as a vertex.

For every cell $C_{1}\cap C_{2}$ of the common refinement of $\mathcal{G}^{+}$ and $\mathcal{G}^{-}$ we call $(\dim(C_{1}),\dim(C_{2}))$ the bi-dimension of $C_{1}\cap C_{2}$. Let $v=C_{1}\cap C_{2}$ be a vertex incident to an edge $e=D_{1}\cap D_{2}$. Transversality implies that if the bi-dimension of $v$ is $(i,j)$, then the bi-dimension of $e$ is one of $(i+1,j)$ or $(i,j+1)$. (The former occurs if $C_{1}\leq D_{1}$ and $C_{2}=D_{2}$, and the latter if $C_{1}=D_{1}$ and $C_{2}\leq D_{2}$). As a consequence, the bi-dimension of the other end of $e$ is one of $(i+1,j-1)$, $(i,j)$ or $(i-1,j+1)$. That is, bi-dimensions of consecutive vertices on a path differ by at most one unit on each coordinate.

Since $v_{1}$ and $v_{2}$ have bi-dimensions $(0,d-2)$ and $(d-2,0)$, along a path of $d-2$ steps connecting them the first coordinate of the bi-dimension always increases and the second coordinate always decreases. This means that we move along a flag (a chain of cells each contained in the next) of $\mathcal{G}^{+}$, and at the end we finish in a facet having $v_{1}$ as a vertex. Similarly, the facet of $\mathcal{G}^{-}$ where we started has $v_{2}$ as a vertex. ∎

So, Theorem 3.1 follows from Lemma 5.9 and Proposition 5.10 if we show that the pair $(\mathcal{G}^{+},\mathcal{G}^{-})$ we are dealing with is transversal. The pair being transversal is equivalent to every proper face $F$ of $Q$ satisfying

This needs only be checked for facets, and was actually implicitly shown in the description of the facets of $Q$ given in Section 4 (see Figure 4, and the proof of parts 2 and 3 of Theorem 4.1). Alternatively, this second proof can be finished with a perturbation argument: Even if $(\mathcal{G}^{+},\mathcal{G}^{-})$ was not transversal, any sufficiently generic and sufficiently small rotation of one of the maps will make the pair transversal without destroying the property stated in part 3 of Lemma 5.9.

An infinite family of non-Hirsch polytopes

In this section we show general procedures to construct new non-Hirsch polytopes from old ones. All the techniques we use are quite standard. Our result is that there is a fixed dimension $d$ in which we can build an infinite sequence of non-Hirsch polytopes with diameter exceeding the Hirsch bound by a fixed fraction.

If we do not ask for a fixed dimension the result is straightforward (see, e.g., [34, Prop. 1.3]):

If $P$ is a a $d$-polytope with $n$ facets and with diameter $(1+\epsilon)(n-d)$ for a certain $\epsilon>0$ then the $k$-fold product $P^{k}$ is a $kd$-polytope with $kn$ facets and with diameter $(1+\epsilon)(kn-kd)$. ∎

In fixed dimension we use the following glueing lemma. It appears, for example, in :

Let $P_{1}$ and $P_{2}$ be simple polytopes of the same dimension $d$, having respectively $n_{1}$ and $n_{2}$ facets, and with diameters $l_{1}$ and $l_{2}$. Then, there is a simple $d$-polytope with $n_{1}+n_{2}-d$ facets and with diameter at least $l_{1}+l_{2}-1$. ∎

If $P$ is a simple $d$-polytope with $n$ facets and diameter $l$, then for each $k$ there is a $d$-polytope $P_{k}$ with $k(n-d)+d$ facets and diameter at least $k(l-1)+1$. In particular, if $P$ is non-Hirsch then $P_{k}$ is non-Hirsch as well.

By induction on $k$, applying Lemma 6.2 to $P_{k-1}$ and $P_{1}:=P$. For the second part, assume that $P$ is non-Hirsch. That is, $l\geq n-d+1$. Then:

It is a consequence of Corollary 6.3 that if there is a linear bound, say $H(n,d)\leq an+b$, for the diameters of polytopes of a fixed dimension $d$, then one has also the bound $H(n,d)\leq a(n-d)+1$ (in the same dimension). Indeed, from a $d$-polytope with $n$ facets and diameter $a(n-d)+2$ (or higher), the corollary above gives $d$-polytopes in which the ratio of diameter to number of facets tends to (at least)

As one referee pointed out to us, this remark is reminiscent of Lemma 2 in : let $F_{1}(n,d)$ denote the maximum number of edges of all simplicial $d$-polytopes with $n$ vertices. If $F_{1}(n,d)\geq dn-b$ holds all $n$ and $d$ and some constant $b$, then $F_{1}(n,d)\geq d(n-d)+{d\choose 2}$ also holds.