1 Introduction
A lot of work has gone into the characterization of the sets of all
$f$
-vectors
$(f_{0},f_{1},\ldots ,f_{d-1})$
of convex
$d$
-polytopes, which we denote by
$f({\mathcal{P}}^{d})$
. In 1906, Steinitz [Reference Steinitz30] characterized the
$f$
-vectors of
$3$
-polytopes as
$$\begin{eqnarray}f({\mathcal{P}}^{3})=\{(f_{0},f_{1},f_{2})\in \mathbb{Z}^{3}:f_{0}-f_{1}+f_{2}=2,f_{2}\leqslant 2f_{0}-4,f_{0}\leqslant 2f_{2}-4\}.\end{eqnarray}$$
Grünbaum [Reference Grünbaum, Kaibel, Klee and Ziegler17, p. 131] showed that the affine hull of
$f({\mathcal{P}}^{d})$
is a hyperplane in
$\mathbb{R}^{d}$
, determined by the Euler equation. Moreover, the
$f$
-vectors of the simplicial polytopes, which we denote by
$f({\mathcal{P}}_{s}^{d})$
, were characterized completely by McMullen’s “
$g$
-conjecture” [Reference McMullen21], as proven by Billera and Lee [Reference Billera and Lee6] and Stanley [Reference Stanley29].
The flag vector of a polytope, introduced by Bayer and Billera [Reference Bayer and Billera5] as the “extended
$f$
-vector”, in general contains considerably more combinatorial information than the
$f$
-vector. For example, the dimension of the affine hull of the set of flag vectors of
$d$
-polytopes, which we denote by
$f\ell ({\mathcal{P}}^{d})$
, is a Fibonacci number minus one [Reference Bayer and Billera5] and thus grows exponentially with
$d$
. On the other hand, within some important classes of polytopes the
$f$
-vector determines the flag vector; for example, this holds for
$3$
-polytopes, as well as for simplicial polytopes (and thus for simple polytopes, by duality). Thus, the results just quoted also characterize the flag vector sets
$f\ell ({\mathcal{P}}^{3})$
and
$f\ell ({\mathcal{P}}_{s}^{d})$
.
While the
$f$
-vectors and the flag vectors of
$3$
-polytopes are thus completely understood, for four-dimensional polytopes our knowledge about the sets of
$f$
-vectors and of flag vectors is rather incomplete. The two-dimensional coordinate projections of the three-dimensional set
$f({\mathcal{P}}^{4})$
have been determined completely; see [Reference Grünbaum, Kaibel, Klee and Ziegler17, §10.4 and p. 198c]. A systematic study of the four-dimensional set
$f\ell ({\mathcal{P}}^{4})$
was started by Bayer [Reference Bayer4]; see also [Reference Höppner, Ziegler, Kalai and Ziegler18] and [Reference Ziegler and Tatsien35, Reference Ziegler, Miller, Reiner and Sturmfels36]. But there are still open questions, e.g. those related to the fatness. While there are
$3$
-spheres of arbitrarily large fatness, this is not known for
$4$
-polytopes [Reference Ziegler, Miller, Reiner and Sturmfels36]. On the other hand, there is a lower bound for the fatness of
$4$
-polytopes, but we do not know whether this also holds for
$3$
-spheres [Reference Ziegler, Miller, Reiner and Sturmfels36].
A
$d$
-sphere is a regular CW
$d$
-sphere with the intersection property (i.e. any two faces intersect in a common face). We call a
$d$
-sphere polyhedral if in addition it is PL and all facets are polytopal. However, all
$3$
-spheres are PL, since all
$3$
-manifolds are [Reference Moise23, §36], and all facets (
$2$
-spheres) are polytopal by Steinitz’ theorem [Reference Steinitz, Meyer and Mohrmann31, Reference Steinitz and Rademacher32], as their graphs are planar and
$2$
-connected for any regular CW complex, and the intersection property then implies that they are
$3$
-connected. Hence, all
$3$
-spheres are polyhedral and we will simply refer to them as
$3$
-spheres.
As polyhedral spheres appear very naturally in any attempt to enumerate combinatorial types of polytopes (see e.g. Grünbaum [Reference Grünbaum, Kaibel, Klee and Ziegler17, §§3.3 and 5.5] or Bokowski and Sturmfels [Reference Bokowski and Sturmfels11]), one must ask whether the characterizations of sets of respectively
$f$
-vectors and flag vectors extend to polyhedral spheres, that is, whether
$$\begin{eqnarray}f({\mathcal{S}}^{d-1})=f({\mathcal{P}}^{d})\qquad \text{and}\qquad f\ell ({\mathcal{S}}^{d-1})=f\ell ({\mathcal{P}}^{d})?\end{eqnarray}$$
Steinitz’s theorem [Reference Steinitz, Meyer and Mohrmann31, Reference Steinitz and Rademacher32] in essence proves that
${\mathcal{S}}^{2}={\mathcal{P}}^{3}$
. The question whether
$f({\mathcal{S}}_{s}^{d-1})=f({\mathcal{P}}_{s}^{d})$
, or equivalently
$f\ell ({\mathcal{S}}_{s}^{d-1})=f\ell ({\mathcal{P}}_{s}^{d})$
, amounts to the “
$g$
-conjecture for spheres”: McMullen’s conjectured answer from [Reference McMullen21] is “yes”; this is known to hold for
$d\leqslant 5$
, as a consequence of the lower bound theorem for spheres, proven by Barnette [Reference Barnette3], and the sufficiency part of the
$g$
-theorem for polytopes, due to Billera and Lee [Reference Billera and Lee6].
Up to now all available evidence with respect to the question (*) was positive. There are many simplicial
$3$
-spheres (but also non-simplicial ones) that are non-polytopal, that is, not combinatorially equivalent to the boundary complex of a
$4$
-polytope, so
${\mathcal{P}}_{s}^{4}\subsetneq {\mathcal{S}}_{s}^{3}$
and consequently
${\mathcal{P}}_{s}^{d}\subsetneq {\mathcal{S}}_{s}^{d-1}$
for all
$d\geqslant 4$
. Indeed, most
$(d-1)$
-spheres are non-polytopal for
$d\geqslant 4$
, as can be seen by comparison of Goodman and Pollack’s upper bounds on the numbers of combinatorial types of polytopes [Reference Goodman and Pollack16] with the lower bounds for spheres by Kalai [Reference Kalai20] and Pfeifle and Ziegler [Reference Pfeifle and Ziegler27]. However, all the non-polytopal
$3$
-spheres studied so far turned out to have an
$f$
-vector (and even flag vector) that is also the
$f$
- (respectively flag) vector of some
$4$
-polytope: this was observed repeatedly, from the first examples (such as the Brückner and Barnette spheres, see e.g. Grünbaum [Reference Grünbaum, Kaibel, Klee and Ziegler17, §11.5] and Ewald [Reference Ewald14, §III.4]) to the systematic enumerations of spheres with few vertices by Altshuler et al (see e.g. [Reference Altshuler and Steinberg2] as well as [Reference Grünbaum, Kaibel, Klee and Ziegler17, p. 96b]).
Here we establish, for the first time, that
$f\ell ({\mathcal{S}}^{d-1})=f\ell ({\mathcal{P}}^{d})$
does not hold in general: indeed, this fails for
$d=4$
. For this we exhibit a specific flag vector in
$f\ell ({\mathcal{S}}^{3})\setminus f\ell ({\mathcal{P}}^{4})$
.
This flag vector belongs to a
$2$
-simple
$2$
-simplicial
$3$
-sphere (
$2s2s$
sphere, for short): a
$4$
-polytope or
$3$
-sphere is 2-simple if every edge lies in exactly three facets, and 2-simplicial if every
$2$
-face has exactly three vertices. The 2s2s property is closed under duality. The 2s2s
$4$
-polytopes were introduced by Grünbaum [Reference Grünbaum, Kaibel, Klee and Ziegler17, §4.5]. This fascinating class of polytopes includes the hypersimplex and the 24-cell. It appears naturally in the study of
$f\ell ({\mathcal{P}}^{4})$
(see Bayer [Reference Bayer4], Ziegler [Reference Ziegler and Tatsien35, Reference Ziegler, Miller, Reiner and Sturmfels36], and Paffenholz and Werner [Reference Paffenholz, Werner and Athanasiadis25]). The flag vectors of 2s2s
$3$
-spheres/
$4$
-polytopes are of the form
$$\begin{eqnarray}(f_{0},f_{1},f_{2},f_{3};f_{02})=(n,m,m,n;3m),\end{eqnarray}$$
and any
$3$
-sphere/
$4$
-polytope with such a flag vector is 2s2s. In particular, within the class 2s2s the
$f$
-vector determines the flag vector. (Here and in the following we only list part of the full flag vector: all other components are determined by the generalized Dehn–Sommerville equations of Bayer and Billera [Reference Bayer and Billera5].) However, there are 2s2s and non-2s2s polytopes which have the same
$f$
-vector: see Paffenholz and Ziegler [Reference Paffenholz and Ziegler26, Corollary 4.3] for examples. Our main result is that there is a specific 2s2s
$3$
-sphere that is non-polytopal and at the same time unique for its flag vector.
Theorem 1.1. There is a unique polyhedral
$3$
-sphere, but no convex
$4$
-polytope, with flag vector given by
$$\begin{eqnarray}(f_{0},f_{1},f_{2},f_{3};f_{02})=(12,40,40,12;120).\end{eqnarray}$$
Thus, the set of flag vectors of
$4$
-polytopes is a proper subset of the set of flag vectors of
$3$
-spheres:
$$\begin{eqnarray}f\ell ({\mathcal{P}}^{4})\subsetneq f\ell ({\mathcal{S}}^{3}).\end{eqnarray}$$
Proof. Any
$3$
-sphere with the given flag vector is necessarily
$2$
-simplicial, as
$f_{02}=3f_{2}$
, and it is
$2$
-simple, as
$f_{13}=f_{02}=3f_{1}$
. A
$3$
-sphere
$W_{12}^{40}$
with this flag vector was discovered in 2009 by Werner [Reference Werner33, Table 7.1, left] in the course of his partial enumeration of shellable 2s2s
$3$
-spheres with
$12$
vertices. In §2, we report about a complete enumeration of 2s2s
$3$
-spheres with at most
$12$
vertices, which yields that Werner’s
$3$
-sphere
$W_{12}^{40}$
is the only sphere with this flag vector. Finally, in §3, we prove that this sphere does not have an oriented matroid, so in particular it is not polytopal.◻
We will present an alternative proof of the non-polytopality of
$W_{12}^{40}$
in §4. In Proposition 4.1, we show that the sphere does not have a diagram based on the facet
$F_{12}$
, which implies that
$W_{12}^{40}$
is non-polytopal. Based on the non-polytopality, we show in §5 that the sphere
$W_{12}^{40}$
cannot be realized as a polytopal complex in any
$\mathbb{R}^{n}$
.
We conjecture that also
$f({\mathcal{P}}^{4})\subsetneq f({\mathcal{S}}^{3})$
, but we have not proved that. In particular, we know of no
$4$
-polytope with the
$f$
-vector
$(f_{0},f_{1},f_{2},f_{3})=(12,40,40,12)$
. As Marge Bayer has pointed out to us, any
$3$
-sphere with this
$f$
-vector would be “close” to being 2s2s, as it must satisfy
$120=3f_{2}\leqslant f_{02}\leqslant 130$
by [Reference Bayer4, Theorem 2(3)].
We would also presume that
$f\ell ({\mathcal{P}}^{d})\subsetneq f\ell ({\mathcal{S}}^{d-1})$
holds for all
$d>4$
, but again this does not seem to follow immediately from our results.
2 2s2s 3-spheres with few vertices
The goal of this section is to report about the proof of the following result, which includes the uniqueness claim in Theorem 1.1.
Theorem 2.1. The following is a complete list of combinatorial types of
$2$
-simple
$2$
-simplicial
$3$
-spheres with at most
$12$
vertices.
All of these, except for the hypersimplex and its dual, are self-dual.
This improves upon results of Werner [Reference Werner33], who classified the 2s2s
$3$
-polytopes with
$f_{0}\leqslant 9$
vertices [Reference Werner33, Theorem 7.2.13]. He also performed a computer enumeration that produced all shellable 2s2s 3-spheres with
$f_{0}\leqslant 11$
. For
$f_{0}=12$
, Werner’s computations remained incomplete due to constraints in computing power; however, his incomplete enumeration produced the two spheres mentioned above. One of these spheres,
$W_{12}^{39}$
, was realized as a
$4$
-polytope by Miyata [Reference Miyata22].
2.1 The enumeration algorithm
For a
$3$
-sphere
$S$
, we define the
$p$
-vector
$p(S)=(p_{4},p_{5},\ldots )$
, where
$p_{i}$
is the number of facets of
$S$
with
$i$
vertices. For any 2s2s
$3$
-sphere with
$f$
-vector
$(n,m,m,n)$
, we have
$p_{i}=0$
for
$2i-4\geqslant n$
, since a facet with
$i$
vertices is a simplicial
$3$
-polytope with
$2i-4$
faces and thus has
$2i-4$
neighbouring facets. In particular, for
$n=12$
, we have
$p_{i}=0$
for
$i>7$
. Moreover, we have
$\sum _{i\geqslant 4}p_{i}=n$
and
$\sum _{i\geqslant 4}(2i-4)p_{i}=2m$
. This yields a finite list of possible
$p$
-vectors for any possible
$f$
-vector. For example, for
$f=(12,40,40,12)$
, there are exactly
$23$
potential
$p$
-vectors that satisfy the three restrictions. To enumerate all 2s2s
$3$
-spheres with a given number
$n$
of vertices, note that
While the lower bound is trivial, the upper bound stems from [Reference Bayer4, Theorem 2(3)].
We have designed and implemented an enumeration algorithm in order to produce, for each
$p$
-vector, one symmetry representative of each set system (of vertex sets of facets) that has the given
$p$
-vector and is proper in the sense that it satisfies:
- (I1)
-
the intersection of two facets contains zero, one, or three vertices;
- (I2)
-
the intersection of three facets contains at most two vertices; and
- (I3)
-
the intersection of four facets contains at most one vertex.
This is where we crucially use the fact that we are looking for 2s2s
$3$
-spheres only. The resulting lists are then checked for being Eulerian lattices of rank
$5$
.
The idea for symmetry breaking in the enumeration, and thus to avoid producing re-labelled versions of the same facet lists too often, is to fix the labelling of the vertex set of a facet of maximal size
$i$
, and then to assign step by step vertex labels to a remaining facet of maximal size. It turns out that in some cases even more facets can be fixed, or at least up to re-labelling have only a few distinct possibilities. In particular, this is the case whenever
$p_{7}>0$
.
Algorithm 2.2.
After roughly two weeks of computation on standard Linux workstations with altogether 45 kernels, the algorithm had enumerated all connected 2s2s rank-
$5$
Eulerian lattices with up to
$12$
vertices. This produced exactly the face lattices of the spheres listed in Theorem 2.1, and thus proves that theorem as well as the second part of Theorem 1.1.
We refer to the works by Paffenholz and Werner [Reference Paffenholz24, Reference Paffenholz, Werner and Athanasiadis25, Reference Werner33] for information and data on 2s2s
$4$
-polytopes with more than
$12$
vertices.
3 Non-polytopality
Our approach to prove non-polytopality is via oriented matroids. This is a standard method for proving the non-realizability of polytopes as well as of polyhedral surfaces (see for example Bokowski and Sturmfels [Reference Bokowski and Sturmfels11], Bokowski [Reference Bokowski, Gruber and Wills8], or Björner et al [Reference Björner, Las Vergnas, Sturmfels, White and Ziegler7, Ch. 8]). However, as far as we know this has always been applied to simplicial polytopes or surfaces, and thus in a setting of uniform oriented matroids, with the notable exception of Bremner’s software package mpc [Reference Bremner12]; see Bokowski et al [Reference Bokowski, Bremner and Gévay9, §7]. (Indeed, David Bremner has confirmed the non-existence result of this section using the nuoms function of his package.) Here we demonstrate that the oriented matroid method is particularly effective in an example with a non-simplicial sphere and hence for a non-uniform oriented matroid.
The basic approach is as follows: any set of points
$v_{0},\ldots ,v_{N}\in \mathbb{R}^{d}$
leads to an orientation function
$\unicode[STIX]{x1D712}:\{v_{0},v_{1},\ldots ,v_{N}\}^{d+1}\rightarrow \{0,+1,-1\}$
by setting
$$\begin{eqnarray}\unicode[STIX]{x1D712}(v_{i_{0}},v_{i_{1}},\ldots ,v_{i_{d}}):=\text{sign}\,\text{det}\left(\begin{array}{@{}cccc@{}}v_{i_{0}} & v_{i_{1}} & \cdots \, & v_{i_{d}}\\ 1 & 1 & \cdots \, & 1\end{array}\right).\end{eqnarray}$$
This map is a chirotope of rank
$d+1$
. In addition to the condition that its support has to be a matroid (which we do not use; cf. [Reference Björner, Las Vergnas, Sturmfels, White and Ziegler7, Theorem 3.6.2]), this means that:
-
(C1) it is alternating; and
-
(C2) it satisfies the three-term Grassmann–Plücker relations: for any
$d-1$
points
$\unicode[STIX]{x1D706}=(v_{i_{0}},\ldots ,v_{i_{d-2}})$
and four points
$v_{a},v_{b},v_{c},v_{d}$
, the set either equals
$$\begin{eqnarray}\displaystyle & & \displaystyle \{\!\unicode[STIX]{x1D712}(\unicode[STIX]{x1D706},v_{a},v_{b})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706},v_{c},v_{d}),-\unicode[STIX]{x1D712}(\unicode[STIX]{x1D706},v_{a},v_{c})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706},v_{b},v_{d}),\nonumber\\ \displaystyle & & \displaystyle \qquad \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706},v_{a},v_{d})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706},v_{b},v_{c})\!\}\nonumber\end{eqnarray}$$
$\{0\}$
or contains
$\{-1,+1\}$
.
If the points
$v_{0},\ldots ,v_{N}$
are supposed to be the vertices of a
$d$
-dimensional polytope with a prescribed facet list
$(F_{1},\ldots ,F_{n})$
, then the map must satisfy the following extra conditions.
-
(P1) If
$v_{i_{0}},\ldots ,v_{i_{d}}$
are contained in a facet
$F_{j}$
, then
$\unicode[STIX]{x1D712}(v_{i_{0}},\ldots ,v_{i_{d}})=0$
. -
(P2) If
$v_{i_{1}},\ldots ,v_{i_{d}}$
are contained in a facet
$F_{j}$
which does not contain
$v_{a}$
or
$v_{b}$
, then
$$\begin{eqnarray}\unicode[STIX]{x1D712}(v_{a},v_{i_{1}},\ldots ,v_{i_{d}})=\unicode[STIX]{x1D712}(v_{b},v_{i_{1}},\ldots ,v_{i_{d}}).\end{eqnarray}$$
Proof of Theorem 1.1.
(The non-polytopality part.) Werner’s sphere
$W_{12}^{40}$
with the flag vector
$(f_{0},f_{1},f_{2},f_{3};f_{02})=(12,40,40,12;120)$
is given by the following list of facets (where we use the vertex labelling of [Reference Werner33, Table 7.1, left]):
$$\begin{eqnarray}\begin{array}{@{}ll@{}}F_{1}:\{v_{0},v_{1},v_{2},v_{3}\},\qquad & F_{7}:\{v_{0},v_{5},v_{7},v_{8},v_{9},v_{10}\},\\ F_{2}:\{v_{0},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\},\qquad & F_{8}:\{v_{1},v_{2},v_{3},v_{4},v_{10},v_{11}\},\\ F_{3}:\{v_{0},v_{1},v_{3},v_{4},v_{8},v_{9}\},\qquad & F_{9}:\{v_{2},v_{5},v_{6},v_{8},v_{10},v_{11}\},\\ F_{4}:\{v_{0},v_{1},v_{2},v_{6},v_{9},v_{10}\},\qquad & F_{10}:\{v_{1},v_{8},v_{9},v_{10},v_{11}\},\\ F_{5}:\{v_{0},v_{4},v_{7},v_{8}\},\qquad & F_{11}:\{v_{1},v_{4},v_{5},v_{7},v_{8},v_{11}\},\\ F_{6}:\{v_{0},v_{5},v_{6},v_{10}\},\qquad & F_{12}:\{v_{2},v_{4},v_{5},v_{11}\}.\end{array}\end{eqnarray}$$
In order to prove non-polytopality of this sphere, we will show that there is no chirotope compatible with its facet list.
In the sphere,
$\{v_{8},v_{9},v_{10}\}=F_{7}\cap F_{10}$
is the vertex set of a triangle
$2$
-face, so the vertices
$\{v_{7},v_{8},v_{9},v_{10}\}\subset F_{7}$
span a tetrahedron, while
$v_{2}\notin F_{7}$
. Thus, in any realization, we have
$\unicode[STIX]{x1D712}(v_{7},v_{8},v_{10},v_{2},v_{9})\neq 0$
. Thus, we may fix an orientation of the realization by setting
$\unicode[STIX]{x1D712}(v_{7},v_{8},v_{10},v_{2},v_{9}):=+1$
. Starting with this, we obtain the implications
Note that this chain of arguments uses all facets except for
$F_{1}$
and
$F_{6}$
; all vertices occur except for
$v_{3}$
and
$v_{6}$
.
Given the values of
$\unicode[STIX]{x1D712}$
that we have obtained, the contradiction appears in the three-term Grassmann–Plücker relations.
Let
$\unicode[STIX]{x1D706}_{1}=(v_{7},v_{8},v_{10})$
,
$a_{1}=v_{4}$
,
$b_{1}=v_{11}$
,
$c_{1}=v_{2}$
,
$d_{1}=v_{9}$
and
$\unicode[STIX]{x1D706}_{2}=(v_{4},v_{8},v_{10})$
,
$a_{2}=v_{7}$
,
$b_{2}=v_{11}$
,
$c_{2}=v_{2}$
,
$d_{2}=v_{1}$
.
Then, using the marked values of
$\unicode[STIX]{x1D712}$
, we get
$$\begin{eqnarray}\displaystyle & & \displaystyle \{\!\unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{1},a_{1},b_{1})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{1},c_{1},d_{1}),\nonumber\\ \displaystyle & & \displaystyle \quad -\unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{1},a_{1},c_{1})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{1},b_{1},d_{1}),\unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{1},a_{1},d_{1})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{1},b_{1},c_{1})\!\}\nonumber\\ \displaystyle & & \displaystyle \qquad =\{(-1)\cdot (+1),-\unicode[STIX]{x1D712}(v_{7},v_{8},v_{10},v_{4},v_{2})\cdot (+1),(+1)\cdot (-1)\};\nonumber\\ \displaystyle & & \displaystyle \{\!\unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{2},a_{2},b_{2})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{2},c_{2},d_{2}),\nonumber\\ \displaystyle & & \displaystyle \quad -\unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{2},a_{2},c_{2})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{2},b_{2},d_{2}),\unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{2},a_{2},d_{2})\cdot \unicode[STIX]{x1D712}(\unicode[STIX]{x1D706}_{2},b_{2},c_{2})\!\}\nonumber\\ \displaystyle & & \displaystyle \qquad =\{(+1)\cdot (-1),-\unicode[STIX]{x1D712}(v_{4},v_{8},v_{10},v_{7},v_{2})\cdot (+1),(+1)\cdot (-1)\}.\nonumber\end{eqnarray}$$
Thus, both sets contain
$-1$
, while by the alternating property of
$\unicode[STIX]{x1D712}$
both of them cannot contain
$+1$
. Therefore, there is no chirotope and hence no oriented matroid for the sphere
$W_{12}^{40}$
, so it is not polytopal.◻
4 Diagrams
A different approach to show non-polytopality of a sphere is to show that for some facet it does not have a diagram with this facet as base (see [Reference Ewald14, §III.4], [Reference Grünbaum, Kaibel, Klee and Ziegler17, §3.3], or [Reference Ziegler34, Lecture 5] for details about diagrams). In [Reference Ewald14], this approach was used to demonstrate non-polytopality of the Barnette sphere.
We have constructed diagrams for the sphere
$W_{12}^{40}$
with facets
$F_{1},\ldots ,F_{11}$
as bases. However, the facet
$F_{12}$
, which is also the only facet without a simple vertex, is special and does not serve as the base of a diagram. As an example, we show here the diagram with
$F_{2}$
as base. Note that due to the general position argument, we can choose all coordinates to be integers. The rendering was done with JavaView [Reference Polthier, Hildebrandt, Preuss and Reitebuch28].
Proposition 4.1. The sphere
$W_{12}^{40}$
has a diagram based on every facet, but not based on
$F_{12}$
.
Proof. Again we use oriented matroids, but this time of rank
$4$
, as the diagrams of
$W_{12}^{40}$
live in
$\mathbb{R}^{3}$
. Since
$W_{12}^{40}$
is
$2$
-simplicial, we may assume general position of the vertices, and then the oriented matroids are uniform. Now, in order to find a diagram or to prove its non-existence, we construct a partial chirotope as follows.
-
∙ Take a ridge (triangle) and some other point on a facet that contains this triangle, and choose a sign (
$+1$
or
$-1$
) for the basis. -
∙ Every ridge defines a plane that separates the two facets containing it. Therefore, the sign of the chirotope does not change when we exchange points on the same side, and flips otherwise. The only exception to this are the triangles on the boundary, which are the facets of the convex hull of the diagram.
-
∙ Use the Grassmann–Plücker relations to determine further entries of the partial chirotope.
The resulting partial chirotopes for the different facets as bases give the signs of 199 to 328 elements out of
$\binom{12}{4}=495$
, which is the size of an oriented matroid for a diagram of
$W_{12}^{40}$
. Using an approach recently introduced by Firsching [Reference Firsching15], we used SCIP [Reference Achterberg1] to find coordinates for the diagrams with bases
$F_{1},\ldots ,F_{11}$
, while in the case of the diagram with base
$F_{12}$
we used backtracking to find for every oriented matroid a partial chirotope of size at least 435 (i.e. of roughly 87.5%). For all of these partial chirotopes we checked the existence of a biquadratic final polynomial (bfp) (see [Reference Bokowski and Sturmfels11, Ch. VII] for an introduction and [Reference Bokowski and Richter10] for the algorithm). To find these bfps we used an implementation of the algorithm by Moritz Firsching and Arnau Padrol. The bfps for the partial chirotopes will also be bfps for all oriented matroids that would complete this partial chirotope, so in finding bfps at this stage we could decrease the size of the search tree by a factor of
$2^{60}$
. There were
$6098$
such partial chirotopes. To prove existence of the bfps for all these partial chirotopes, we needed roughly one week of computing time on a usual Linux workstation.◻
5 Embeddability
At this point we know that the sphere
$W_{12}^{40}$
is non-polytopal, but is it fan-like, embeddable, or even star-shaped? These properties of spheres are treated in detail by Ewald [Reference Ewald14, §III.5]. A polyhedral
$d$
-sphere
$S$
is fan-like if there exists a complete fan
$\unicode[STIX]{x1D6F4}\subset \mathbb{R}^{d+1}$
together with an isomorphism that maps a face
$F\in S$
to a cone
$\operatorname{pos}F\in \unicode[STIX]{x1D6F4}$
. The polyhedral sphere
$S$
is embeddable if there is a continuous injection
$\unicode[STIX]{x1D711}:|S|\rightarrow \mathbb{R}^{n}$
for some
$n$
that has a continuous inverse on
$\unicode[STIX]{x1D711}(|S|)$
, and which maps faces of
$S$
to convex polytopes. A polyhedral
$d$
-sphere is star-shaped if it has an embedding into
$\mathbb{R}^{d+1}$
that defines a fan. Clearly it follows that a star-shaped sphere is both fan-like and embeddable. See [Reference Ewald14, §III.5] for examples that show that there are no other implications between these three properties. However, if
$S$
is a simplicial sphere, then fan-like and star-shaped are equivalent, and Kalai [Reference Kalai19] showed that for
$d\geqslant 2$
every embeddable simple polyhedral
$d$
-sphere is polytopal.
The sphere
$W_{12}^{40}$
is fan-like with the following vertex coordinates (respectively rays through the following points):
$$\begin{eqnarray}\begin{array}{@{}ll@{}}v_{0}=(9,2,4,-1),\qquad & v_{6}=(-5,-9,2,-16),\\ v_{1}=(-3,14,-16,6),\qquad & v_{7}=(-1,2,14,-1),\\ v_{2}=(-8,-2,-4,-16),\qquad & v_{8}=(-1,2,4,9),\\ v_{3}=(1,23,-1,-9),\qquad & v_{9}=(9,-7,-12,21),\\ v_{4}=(-1,12,4,-1),\qquad & v_{10}=(-6,-13,-5,-1),\\ v_{5}=(-14,-11,27,-11),\qquad & v_{11}=(-14,4,1,-3).\end{array}\end{eqnarray}$$
These coordinates were found with similar methods as we used for finding coordinates for the diagrams: from the combinatorics we constructed a partial chirotope of rank
$5$
, and then we used SCIP to find coordinates satisfying this.
However, with the methods from the previous section we were not able to decide whether
$W_{12}^{40}$
is embeddable or star-shaped. For embeddability the oriented matroid approach will not work, since there are infinitely many dimensions to check. In the star-shaped case we did not find coordinates, but on the other hand we found an oriented matroid that does not have a bfp.
Proposition 5.1. The sphere
$W_{12}^{40}$
is not embeddable and hence it is not star-shaped.
Proof. This proof heavily depends on the structure of
$W_{12}^{40}$
, and establishes the following.
-
(i) If
$W_{12}^{40}$
is embeddable into some
$\mathbb{R}^{k}$
,
$k\geqslant 4$
, then it is also embeddable into
$\mathbb{R}^{4}$
. -
(ii) If
$W_{12}^{40}$
is embedded into
$\mathbb{R}^{4}$
, then this is an embedding as a convex polytope.
Let us assume that
$W_{12}^{40}$
is embedded in some
$\mathbb{R}^{k}$
, that is, it is realized by a polytopal complex
$\unicode[STIX]{x1D6E4}$
(where each of the facets is realized as a convex
$3$
-polytope).
For (i) we note that
$v_{3}$
is a simple vertex, that is, a vertex that is contained in only four facets or, equivalently, in only four edges. The four facets are each contained in the affine span of three of these edges, so all four facets are contained in the affine span of the four edges. Moreover, each of the
$12$
vertices of the sphere is contained in at least one of the four facets, which are
$F_{1},F_{2},F_{3}$
, and
$F_{8}$
. So, the complete embedded sphere is contained in this affine four-dimensional subspace of
$\mathbb{R}^{k}$
.
For (ii) note that the argument for (i) implies that in addition each of the facets
$F_{1},F_{2},F_{3}$
, and
$F_{8}$
is also a facet of the convex hull of
$\unicode[STIX]{x1D6E4}$
, that is, all of
$\unicode[STIX]{x1D6E4}$
is contained in a closed halfspace of the hyperplane spanned by the facet, while only the vertices of the facet lie on the boundary hyperplane. Exactly the same arguments are valid for the other three simple vertices of
$W_{12}^{40}$
and the facets they are contained in, that is, for
$v_{6}$
and the facets
$F_{2},F_{4},F_{6}$
, and
$F_{9}$
, for
$v_{7}$
and the facets
$F_{2},F_{5},F_{7}$
, and
$F_{11}$
, as well as for
$v_{9}$
and the facets
$F_{3},F_{4},F_{7}$
, and
$F_{10}$
. Thus, we have established for all facets
$F_{i}$
of
$\unicode[STIX]{x1D6E4}$
, except for the tetrahedron
$F_{12}$
, that they are also a facet of the convex hull of
$\unicode[STIX]{x1D6E4}$
. As mentioned above,
$F_{12}$
is special in the way that it is the only facet that does not contain a simple vertex.
To see that also
$F_{12}$
is a facet of the convex hull of
$\unicode[STIX]{x1D6E4}$
, consider its neighbours
$F_{2}$
,
$F_{8}$
,
$F_{9}$
, and
$F_{11}$
. Since these are all facets of the convex hull of
$\unicode[STIX]{x1D6E4}$
, they cannot lie in the same hyperplane as
$F_{12}$
. The facet
$F_{2}$
gives that the vertices
$v_{0},v_{3},v_{6}$
, and
$v_{7}$
lie on the same side of the hyperplane
$H_{12}$
spanned by
$F_{12}$
. Now, the facet
$F_{8}$
contains
$v_{3}$
, the facet
$F_{9}$
contains
$v_{6}$
, and the facet
$F_{11}$
contains
$v_{7}$
, whence the points from these facets not in
$F_{12}$
are also all on the same side of
$H_{12}$
. Therefore, we have that all points, except possibly
$v_{9}$
, lie in, say,
$H_{12}^{+}$
. Since
$F_{10}$
is a bipyramid over the triangle
$v_{1},v_{8},v_{10}$
with apexes
$v_{9}$
and
$v_{11}$
, and since
$v_{11}$
is in
$F_{12}$
, it follows
$v_{9}\in H_{12}^{+}$
. This completes the proof of (ii).◻
Note added in proof
The authors have recently verified [Reference Brinkmann and Ziegler13] that there are four strongly regular 3-spheres (all of them self-dual, one of them 2s2s), but no
$4$
-polytopes at all, with the
$f$
-vector
$(12,40,40,12)$
. Thus the
$3$
-sphere discussed in this paper also has an
$f$
-vector that is not the
$f$
-vector of a
$4$
-polytope.
Acknowledgements
We are very grateful to Marge Bayer, Lou Billera, David Bremner, Moritz Firsching, Hiroyuki Miyata, Arnau Padrol, and Axel Werner for very valuable comments, discussions, references, and data.
