ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 10, Pages 122–134 (December 1, 2004) S 1079-6762(04)00137-4

PROJECTED PRODUCTS OF POLYGONS

GÜNTER M. ZIEGLER

(Communicated by Sergey Fomin)

Abstract. It is an open problem to characterize the cone of f-vectors of 4-dimensional convex polytopes. The question whether the “fatness” of the fvector of a 4-polytope can be arbitrarily large is a key problem in this context.

Here we construct a 2-parameter family of 4-dimensional polytopes π(P_{n}^{2r}) with extreme combinatorial structure. In this family, the “fatness” of the fvector gets arbitrarily close to 9; an analogous invariant of the flag vector, the “complexity,” gets arbitrarily close to 16.

The polytopes are obtained from suitable deformed products of even polygons by a projection to ℝ^{4}.

1. Introduction

1.1. f -vectors. The combinatorial structure of a d-dimensional convex polytope is given by the incidences between its k-dimensional faces, for 0 ≤ k ≤ d − 1. In particular one looks at the faces of dimensions 0, 1, d − 2, and d − 1, known as the vertices, edges, ridges, and facets, respectively.

To get an overview over enumerative and extremal properties of the multitude of combinatorial types of d-polytopes, one tries to classify their f-vectors, that is, the d-tuples

f(P) := (f_{0}, f_{1}, …, f_{d−2}, f_{d−1}) ∈ ℤ^{d},

where f_{k} denotes the number of k-dimensional faces of the d-polytope P. The f-vector of any d-polytope is a point in ℝ^{d}, but due to the Euler–Poincaré relation

f_{0} − f_{1} ± ⋯ + (−1)^{d−1}f_{d−1} = 1 − (−1)^{d}

the set of all f-vectors of d-polytopes

F_{d} := {f = (f_{0}, f_{1}, …, f_{d−1}) ∈ ℤ^{d} : f = f(P) for a d-polytope P }

has dimension d − 1 [7, Chapter 8].

The f-vector (and more so the flag vector of a d-polytope, as discussed below) not only provides numerical data: it also encodes various extremal properties. So any attempt to characterize the f-vectors of polytopes is closely linked to the analysis and construction of extremal polytopes.

Received by the editors July 4, 2004 and, in revised form, September 17, 2004. 2000 Mathematics Subject Classification. Primary 52B05; Secondary 52B11, 52B12. Key words and phrases. Discrete geometry, convex polytopes, f-vectors, deformed products of

polygons.

Partially supported by Deutsche Forschungs-Gemeinschaft (DFG), via the Matheon Research Center “Mathematics for Key Technologies” (FZT86), the Research Group “Algorithms, Structure, Randomness” (Project ZI 475/3), and a Leibniz grant (ZI 475/4).

\begin{matrix}c \\ ◯ \end{matrix}2004 American Mathematical Society

Reverts to public domain 28 years from publication

For example, a d-polytope is simplicial if and only if its f-vector satisfies f_{d−2} = \frac{d}{2}f_{d−1}. Indeed, each facet of a d-polytope is bounded by at least d ridges, while every ridge is in exactly 2 facets. Hence 2f_{d−2} ≤ d f_{d−1} is valid for all polytopes, and the constraint is tight exactly if all facets are simplices. Thus simplicial polytopes are extremal in the sense that they maximize a (linear) quantity among all f-vectors: they maximize 2f_{d−2} − d f_{d−1}.

In the study of f-vectors of d-polytopes, one tries to find all such linear inequalities for the f-vectors, and to understand the extremal polytopes for which these inequalities are tight.

My lecture notes [19] contain a more extensive discussion of the interplay between f-vector theory and constructions of extremal polytopes that arises from this.

1.2. Flag vectors. Additional combinatorial information is contained in the flag vector of a d-polytope, which in addition to the components f_{k} of the f-vector also records the numbers f_{k,ℓ} of incidences of k-faces with ℓ-faces (that is, the numbers of pairs (F, G) consisting of a k-face F contained in an ℓ-face G, for k < ℓ), the numbers f_{k,ℓ,m} of chains of three faces F ⊂ G ⊂ H of dimensions k < ℓ < m, etc. The flag vector is an integral vector with 2^{d} − 1 components; nevertheless, due to a multitude of linear relations, the generalized Dehn-Sommerville relations [4], the set of all flag-vectors has dimension only F_{d} − 1, where F_{d} denotes the d-th Fibonacci number. In particular, for d ≤ 3 there is no additional information contained in the flag vector, while for 4-polytopes the set of f-vectors is 3-dimensional, but the set of flag vectors is 4-dimensional. So, there is indeed extra information contained in, say, f_{03}, while all the other components of the flag vector can be recovered from f̃ = (f_{0}, f_{1}, f_{2}, f_{3}; f_{03}).

It makes sense to treat the f-vector problem for each dimension separately. This starts at d = 2, where the trivial answer is F_{2} = {(n, n) : n ≥ 3}.

1.3. f -vectors of 3-polytopes. According to Steinitz’ paper [16] of 1906, the f-vectors of 3-polytopes are all the integral vectors that satisfy

f_{2} ≤ 2f_{0} − 4  and  f_{0} ≤ 2f_{2} − 4

in conjunction with Euler’s formula, f_{1} = f_{0} + f_{2} − 2; see also [7, Section 10.3]. Since both inequalities are tight for the 3-simplex, with f(Δ_{3}) = (4, 6, 4), this implies that F_{3} is the set of all integral points in a 2-dimensional polyhedral cone with apex f(Δ_{3}), which is pictured in Figure 1.

Here the extreme cases, polytopes whose f- or flag vectors lie on the boundary of the cone, are given by the simplicial polytopes (for which Steinitz’ first inequality is tight) and the simple polytopes (second inequality tight). One can thus say that “all (f-vectors of) 3-polytopes lie between the extremes of simple and of simplicial polytopes.”

1.4. f -vector cones. For 4-dimensional polytopes, such a complete and simple answer is not to be expected. Indeed, F_{d} is not just the set of all integral points in a convex set, since some of the constraints, such as f_{1} ≤ \binom{f_{0}}{2}, are concave rather than convex. Also, some of the 2-dimensional coordinate projections of F_{4} show “holes” that cannot be explained by such systematic inequalities; compare Grünbaum [7, Section 10.4], Bayer [3], and Höppner and Ziegler [8].

Figure 1. The f-vectors of 3-polytopes, graphed in the (f_{0}, f_{2})-plane.

Thus, one heads for a more modest goal, the complete description of the closed convex cone, with apex f(Δ_{d}), that is spanned by the f-vectors of d-polytopes:

cone(F_{d}) := topological closure of

{f(Δ_{d}) + ∑_{i=1}^{N} λ_{i}(f(P_{i}) − f(Δ_{d})) : N ≥ 0, λ_{1}, …, λ_{N} ≥ 0,

P_{1}, …, P_{N} d-polytopes}.

Equivalently, this is the solution set for the system of all linear inequalities that are valid for the f-vectors of d-polytopes and are tight for the f-vector of the d-simplex.

1.5. The f -vector cone for 4-polytopes. The f-vector cone for 4-polytopes, cone(F_{4}), is a 3-dimensional convex cone. One can visualize it in terms of an intersection with an affine hyperplane, which yields a 2-dimensional convex set; equivalently, one can introduce projective coordinates for the cone, that is, suitable ratios of linear quantities which vanish at the apex of the cone.

Here we use the projective coordinates introduced in [18],

φ_{0} := \frac{f_{0} − 5}{f_{1} + f_{2} − 20}  and  φ_{3} := \frac{f_{3} − 5}{f_{1} + f_{2} − 20}.

In terms of these quantities, we describe (and picture) our knowledge about the f-vector cone of 4-polytopes. The known necessary conditions can be written as

(1) φ_{0} ≥ 0, φ_{3} ≥ 0, φ_{0} + 3φ_{3} ≤ 1, 3φ_{0} + φ_{3} ≤ 1, and φ_{0} + φ_{3} ≤ \frac{2}{5}.

The first two conditions are trivial, the second two have simplicial, resp. simple, polytopes as extreme cases, and the last condition is a non-trivial bound that Bayer [3] derived from a flag vector inequality, which in terms of the “toric g-vector” of Stanley [15] reads “g_{2}^{tor} ≥ 0”; a rigidity-theoretic proof was obtained by Kalai [10].

Figure 2 represents the pentagon described by the five linear inequalities (1). As indicated in the figure, four of its vertices are spanned by the (φ_{0}, φ_{3})-pairs of known classes of polytopes.

Figure 2. The f-vector cone of 4-polytopes, graphed in projective coordinates, (φ_{0}, φ_{3}).

There is some hope that the five linear inequalities of (1) represent a complete description of cone(F_{4}). This is true if and only if there exist polytopes whose (φ_{0}, φ_{3})-pairs approach the fifth vertex of the pentagon, that is, for which the sum φ_{0} + φ_{3} is arbitrarily small. Equivalently, we want the fatness parameter

F (P) := \frac{1}{φ_{0} + φ_{3}} = \frac{f_{1} + f_{2} − 20}{f_{0} + f_{3} − 10}

arbitrarily large [18]. This observation has sparked a certain race for “fat” 4dimensional polytopes. The following table summarizes the main steps. Most of the examples that appear there are 2-simple and 2-simplicial, with a symmetric f-vector; the first infinite family of such polytopes was constructed by Eppstein, Kuperberg and Ziegler [5]; a simple construction appears in Paffenholz and Ziegler [12]. We call a polytope “even” if its 1-skeleton is a bipartite graph.

4-polytopes  fatness property  reference  date
simple or simplicial < 3
24-cell  4.526 2-simple, 2-simplicial Schläfli [13]  1852
dipyramidal 720-cell 5.020 2-simple, 2-simplicial Geváy [6]  1991
neighborly cubical 5 − ε even  Joswig and Ziegler [9] 2000
[E-construction]  5.048 2-simple, 2-simplicial Eppstein et al. [5]  2003
E(C_{m} × C_{n})  6 − ε 2-simple, 2-simplicial Paffenholz [11]  2004
Projected products 9 − ε even  here

For example, the neighborly cubical 4-polytopes C_{4}^{n} for n → ∞ yield the point (0, \frac{1}{5}) in the (φ_{0}, φ_{3})-plane, and thus fatness arbitrarily close to 5.

The concept of “strictly preserving a face” used in the following theorem will be explained in Section 3. (Compare the concept of faces in the “shadow boundary” of a projection, e.g. in [2].)

Theorem 1.1 (Projected Products of Polygons). Let n ≥ 4 be even and r ≥ 2. Then there is a 2r-polytope P_{n}^{2r} ⊂ ℝ^{2r}, combinatorially equivalent to a product of r n-gons, P_{n}^{2r} ≅ (C_{n})^{r}, such that the projection π : ℝ^{2r} → ℝ^{4} to the last four coordinates strictly preserves the 1-skeleton as well as all the “polygon 2-faces” of P_{n}^{2r}.

Theorem 1.2. The polytopes π(P_{n}^{2r}) have the f-vectors

(\frac{4}{r}, 4, 5 − \frac{6}{r} + \frac{4}{n}, 1 − \frac{2}{r} + \frac{4}{n}) · \frac{1}{4}r n^{r}.

For n, r → ∞ they yield the point (0, \frac{1}{9}), in the (φ_{0}, φ_{3})-plane, while their duals yield (\frac{1}{9}, 0). In particular, for each ε > 0 there are polytopes of fatness larger than 9 − ε.

Thus the known polytopes now span a hexagon, which is shaded in Figure 2. A flag vector parameter that is similar to fatness, called complexity [18], is defined

by

C(P) := \frac{f_{03} − 20}{f_{0} + f_{3} − 10}.

All 4-polytopes satisfy C(P) ≥ 3. Fatness and complexity are roughly within a factor of 2: C(P) ≤ 2F (P) − 2 and F (P) ≤ 2C(P) − 2. In particular, it is not known whether C(P) can be arbitrarily large. Previously, the polytopes with the largest known complexity were the “neighborly cubical polytopes” of Joswig and Ziegler [9], of complexity 8−ε. Our present construction yields “neighborly cubical polytopes” for n = 4, but for n, r → ∞ it yields complexity as large as 16 − ε.

In the following two sections, we review the main ingredients for the construction of π(P_{n}^{2r}). The construction that yields Theorem 1.1 is described in Section 4, with a sketch of the proof for its correctness. The flag vectors of the polytopes π(P_{n}^{2r}) are computed in Section 5, which yields Theorem 1.2. Detailed proofs, the combinatorial characterization of the resulting polytopes, possible extensions, further remarkable aspects (such as the polyhedral surfaces of high genus embedded in the 2-skeleta of the resulting 4-polytopes; cf. [14]) as well as necessity of the restrictions (e.g., that n must be even) are topics of current research and will be presented later.

Acknowledgements. The intuition for the construction given here grew from previous joint work and current discussions with Nina Amenta, Michael Joswig, Raman Sanyal, and Thilo Schröder.

2. Products and deformed products

The combinatorial structure of the products of polygons (C_{n})^{r} is easy to describe. These are simple 2r-polytopes, with f_{0} = n^{r} vertices, f_{1} = rn^{r} edges, and f_{2r−1} = rn facets. In general, its non-empty faces are products of non-empty faces of the polygons, so ∑_{i=0}^{2r} f_{i}t^{i} = (n + nt + t^{2})^{r}.

The 2-dimensional faces of (C_{n})^{r}, and thus of any polytope combinatorially equivalent to (C_{n})^{r}, may be split into two classes. There are rn^{r−1} faces that are n-gons, to which we refer as polygons; they arise as products of one of the n-gons with a vertex from each of the other factors. There are also \binom{r}{2}n^{r} quadrilaterals that (in (C_{n})^{r}) arise as products of edges from two of the factors with vertices from the others. Thus, in total (C_{n})^{r} has f_{2} = rn^{r−1} + \binom{r}{2}n^{r} 2-faces.

In the case n = 4, the polygon 2-faces of (C_{n})^{r} are 4-gons, but we nevertheless treat the r4^{r−1} polygons and the \binom{r}{2}4^{r} quadrilaterals separately also in this case.

An inequality description for such a product polytope may be obtained as

(  ) x ≤ ( ) ,

assuming that V x ≤ b is a correct description for an n-gon. For this it is necessary and sufficient that the row vectors v_{i} of V are non-zero and distinct and that they positively span ℝ^{2}, that the components b_{i} of b are positive, and that the rescaled vectors \frac{1}{b_{i}} v_{i} are in convex position (the vertices of the polar of the polygon).

For this we say that a finite set of vectors v_{1}, …, v_{k} ∈ ℝ^{d} positively spans if it satisfies the following equivalent conditions:

(i) every vector x ∈ ℝ^{d} is a linear combination of the vectors v_{i}, with nonnegative coefficients; (ii) every vector x ∈ ℝ^{d} is a linear combination of the vectors v_{i}, with positive

coefficients; (iii) the vectors v_{i} span ℝ^{d}, and 0 ∈ ℝ^{d} is a linear combination of the vectors v_{i},

with positive coefficients (that is, the vectors v_{i} are positively dependent).

In the following, we will need “deformed products.” (The deformations are more general than the “rank 1” deformations as described in Amenta and Ziegler [1].) For this, we look at systems of the form

(  ) x ≤ ( ) .

Given any such left-hand side matrix for such a system, we can adapt the righthand side so that the resulting polytope is combinatorially equivalent to (C_{n})^{r}. For this all components of b_{k} have to be sufficiently large compared to b_{1}, …, b_{k−1}, for k = 2, 3, …, r. (Compare [1] and [9].)

3. Projections

We will work with a rather restrictive concept of faces “being preserved under projection.”

Definition 3.1 (Strictly preserving faces under projection). Let π : P → Q = π(P) be a projection of polytopes. Then a face G ⊆ P is strictly preserved if

(i) its image π(G) is a face of Q, (ii) the map G → π(G) is a bijection, and (iii) the preimage of the image is G, that is, π^{−1}(π(G)) = G.

In the definition, conditions (ii) and (iii) are both needed. Indeed, in the projection “to the second coordinate” displayed in our figure, the vertex v is strictly preserved, but the vertex w and the edge e are not: for w condition (iii) fails, while for e condition (ii) is violated.

For simplicity, the following characterization result is given only in a coordinatized version, for the projection “to the last d coordinates.”

We say that a vector c defines the face G ⊆ P given by all the points of P that have maximal scalar product with c. This describes exactly all the vectors in the relative interior of the normal cone of G. If P is full-dimensional, this interior of the normal cone consists of all the positive combinations of outer facet normals n_{F} to the facets F ⊂ P that contain G. (Compare [17, Sections 2.1, 3.2, 7.1].)

Proposition 3.2. Let π : ℝ^{e+d} → ℝ^{d}, (x′, x′′) ↦ x′′ be the projection to the last d coordinates, and let P ⊂ ℝ^{e+d} be an (e + d)-dimensional polytope, and let G be a face of P. Then the following three conditions are equivalent:

(1) G is strictly preserved by the projection π : P → π(P) = Q.

(2) Any c′ ∈ ℝ^{e} arises as the first e components of a vector (c′, c′′) that defines G.

(3) The vectors n′_{F}, given by the first e components of the normal vectors (n′_{F} , n′′_{F}) = n_{F} to facets F of P that contain G, positively span ℝ^{e}.

Proof. Here we only establish “(3) ⇒ (1),” which is used in the following.

If the vectors n′_{F} are positively dependent, then some positive combination of the vectors (n′_{F} , n′′_{F}) = n_{F} yields (0, c′′) =: c. A point x ∈ P lies in the face G ⊆ P if and only if its scalar product with each facet normal n_{F} is maximal. This happens if and only if c^{t}x is maximal, that is, iff (c′′)^{t}x′′ is maximal under the restriction x′′ ∈ π(P). Thus we have established that under the assumption (3), π(G) =: Ḡ is a face of π(P), and π^{−1}(π(G)) = π^{−1}(Ḡ) = G; that is, conditions (i) and (iii) of Definition 3.1 are satisfied.

For part (ii) of Definition 3.1, we have to show that G → π(G) is injective. Assume that x = (x′, x′′) and y = (y′, y′′) are points in G with π(x) = π(y), that is, x′′ = y′′. For each normal vector n_{F} = (n′_{F} , n′′_{F}) we have n_{F}^{t}x = n_{F}^{t}y and (n′′_{F})^{t}x′′ = (n′′_{F})^{t}y′′, which implies (n′_{F})^{t}x′′ = (n′_{F})^{t}y′′. But the vectors n′_{F} that correspond to the various facets F that contain G are positively spanning in ℝ^{e}, which implies x′ = y′. □

4. Construction

Proposition 4.1 (Construction for the proof of Theorem 1.1). For n ≥ 4 even and r ≥ 2, let P_{n}^{2r} be defined by the linear inequality system

(  ) x ≤ ( ) .

Here the left-hand side coefficient matrix A_{n,r}^{ε} ∈ ℝ^{rn×2r} contains blocks of size n × 2, where

V =  ⟶ V^{ε} =  ,  W =  ,  U =  ∈ ℝ^{n×2},

with

v_{0} = (1, 0), v_{1} = (0, 0) = 0, w_{0} = (0, 1), w_{1} = (−3, −\frac{2}{3}),
u_{0} = (−\frac{31}{4}, \frac{1}{2}), u_{1} = (9, −\frac{2}{3}).

The block V^{ε} arises from V by an ε-perturbation:

v_{i}^{ε} = \begin{cases}(1 − ε(n − 2 − 2i)^{2}, ε(n − 2 − 2i)) & for i = 0, 2, 4, …, n − 2, \\ ε(1 − ε(n − 2 − 2i)^{2}, ε(n − 2 − 2i)) & for i = 1, 3, 5, …, n − 3, \\ ε(−1, 0) = (−ε, 0) & for i = n − 1 \end{cases}

for a sufficiently small ε > 0. All entries of A_{n,r}^{ε} outside the r + (r − 1) + (r − 2) = 3r − 3 blocks of types V^{ε}, W and U are zero.

Let the right-hand side vector be such that b_{1} is given by b_{1,i} = 1 for even i, and b_{1,i} = ε for odd i, and by b_{k} = M^{k−1}b_{1} for sufficiently large M.

Then P_{n}^{2r} has the properties claimed by Theorem 1.1. In particular, it is a deformed product of r n-gons, and all its polygon 2-faces survive the projection to the last 4 coordinates.

Proof. The rows v_{i}^{ε} of V^{ε} are indeed in cyclic order:

Moreover, rescaled as \frac{1}{b_{k,i}} v_{i}^{ε} = \frac{1}{M^{k−1}ε}v_{i}^{ε} for odd i and as \frac{1}{b_{k,i}} v_{i}^{ε} = \frac{1}{M^{k−1}} v_{i}^{ε} for even i they are in convex position, if ε is small; so V^{ε}x ≤ b_{i} defines a convex n-gon. Thus for sufficiently small ε and sufficiently large M, the polytope P_{2r} is indeed a deformed product of polygons, as discussed in Section 2.

Now we show that for sufficiently small ε, all the polygon 2-faces of P_{n}^{2r} survive the projection to the last 4 coordinates. For this, we verify that the left-hand side matrix with V -blocks instead of V^{ε}-blocks, which we denote by A_{n,r}^{0} = A_{n,r}, satisfies the linear algebra condition dictated by Proposition 3.2(3). This is sufficient, since the “positively spanning” condition is stable under perturbation by a small ε.

Any polygon 2-face G of the simple 2r-polytope P_{n}^{2r} is defined by the facet normals to the 2r − 2 facets that contain G. The facet normals correspond to the rows of the inequality system, and thus for the facet normals of a polygon 2face one has to choose two cyclically adjacent rows from each block (corresponding to a vertex from each factor polygon), except from one of the blocks no row is taken. Moreover, due to the structure of the matrices U, V, and W, in which rows alternate, any choice of two cyclically-adjacent rows from a block yields the same pair of rows (only the order is not clear, but it also does not matter).

Thus, to apply Proposition 3.2(3) we have to show:

If one of the r pairs of rows is deleted from the reduced matrix

A′_{n,r} = (  ) ∈ ℝ^{2r×(2r−4)},

then the remaining 2r − 2 rows

(a) span ℝ^{2r−4}, and

(b) have a linear dependence with strictly positive coefficients. Let us establish (b) first. For this, let

α_{k} := 2^{k} + 2^{−k} − 2  and  β_{k} := 2^{k} + \frac{5}{4}2^{−k} − \frac{9}{4}.

These sequences are designed to be non-negative, α_{k}, β_{k} ≥ 0 for all k ∈ ℤ, with equality only for k = 0. Thus for (b) it suffices to verify that

For any 1 ≤ t ≤ r, the rows of A′_{n,r} are positively dependent with coefficients α_{k−t} for the even-index row from the k-th block, and β_{k−t} for the odd-index row from the k-th block,

since the (two) vectors in the t-th block thus get zero coefficients, so they may be deleted from any linear dependence (with otherwise positive coefficients). Thus we are led to the condition

α_{k−1}v_{0} + α_{k}w_{0} + β_{k}w_{1} + α_{k+1}u_{0} + β_{k+1}u_{1} = 0,

which is needed to hold for k ≤ |r − 2|, but which we impose for all k ∈ ℤ. The choice of vectors v_{0}, w_{0}, w_{1}, u_{0}, u_{1} is designed to satisfy this condition. Indeed, except for the choice of a basis, which we took to be v_{0} = (1, 0) and w_{0} = (0, 1), the configuration of five vectors v_{0}, w_{0}, w_{1}, u_{0}, u_{1} is uniquely determined by the condition.

For property (a), we have to show that if one of the r pairs of rows is deleted from the matrix A′_{n,r}, then the resulting matrix still has full rank. If the first or the second pair of rows is deleted, then we still have the last 2r − 4 rows, and they form a block upper triangular matrix, which has full rank since its diagonal block

(  )

is non-singular. If a later pair of rows is deleted, then we are faced with the task to show that the 2k × 2k matrices M_{k} of the form

M_{k} := (  ) ∈ ℝ^{2k×2k}

are non-singular. To verify this (without proving explicitly that det M_{k} = \frac{(2^{k}−1)^{2}}{3^{k}}, which might need combinatorial ingenuity) we use our knowledge about row combinations of M_{k}. Indeed, if we sum the rows of M_{k} with coefficients (α_{0}, β_{0}, α_{1}, …, α_{k−1}, β_{k−1}), then this will result in the linear combination of the three rows of the matrix

H_{3} = ( ) ∈ ℝ^{3×2r}

with the coefficients (−α_{−1}, −α_{k}, −β_{k}), since v_{1} = 0. Similarly, if we sum the rows of M_{k} with coefficients (α_{1}, β_{1}, α_{2}, …, α_{k}, β_{k}), then we get a linear combination of the same three rows, with coefficients (−α_{0}, −α_{k+1}, −β_{k+1}). And if we use coefficients (α_{2}, β_{2}, α_{3}, …, α_{k+1}, β_{k+1}) to sum the rows of M_{k}, then the result will be a sum with coefficients (−α_{1}, −α_{k+2}, −β_{k+2}). The coefficient matrix

(\begin{matrix}−α_{−1} & −α_{k} & −β_{k} \\ −α_{0} & −α_{k+1} & −β_{k+1} \\ −α_{1} & −α_{k+2} & −β_{k+2} \end{matrix})

is non-singular for k ≥ 0: its determinant is \frac{3}{8}(2^{k} − 1 + 2^{−k−2}). Thus the full row space of H_{3} is contained in the row space of M_{k}. In particular, we find the unit vectors e_{2k−1}, e_{2k} ∈ ℝ^{2k} in the row space of H_{3}, and thus of M_{k}, and this allows us to complete the argument by induction. □

5. Flag vectors

The following result includes Theorem 1.2. Note that its proof relies only on the properties of π(P_{n}^{2r}) that are guaranteed by the statement of Theorem 1.1; it does not refer to the specific combinatorial type of the polytopes constructed in Section 4, in our proof of Theorem 1.1.

Theorem 5.1. The 4-polytope π(P_{n}^{2r}) has the flag vector

(f_{0}, f_{1}, f_{2}, f_{3}; f_{03}) = (n^{r}, rn^{r}, \frac{5}{4}rn^{r}− \frac{3}{2}n^{r}+ rn^{r−1}, \frac{1}{4}rn^{r}− \frac{1}{2}n^{r}+ rn^{r−1}; 4rn^{r}− 4n^{r})

= (4n, 4rn, 5rn − 6n + 4r, rn − 2n + 4r; 16rn − 16n) · \frac{1}{4}n^{r−1}.

Proof. We obtain f_{0} = n^{r} and f_{1} = rn^{r} from the products (C_{n})^{r}, which are simple 2r-polytopes with n^{r} vertices. With the abbreviation N := \frac{1}{4}n^{r−1} this yields f_{0} = 4nN vertices and f_{1} = 4rnN edges for π(P_{n}^{2r}).

The products (C_{n})^{r} have P := rn^{r−1} = 4rN polygon 2-faces. In the projection, all these are preserved, in addition to some of the quadrilateral 2-faces.

The projected polytope has two types of facets. There are “prism” facets, which involve two of the polygons, as well as “cube” facets, which in (C_{n})^{r} arise as products of three edges and r − 3 vertices, but contain no polygon 2-faces. Thus each prism facet is bounded by two polygons, and each polygon lies in two prism facets. Hence there are P = 4rN prism facets, as well as some number C ≥ 0 of cube facets.

Now double counting of ridges yields 6C + (n + 2)P = 2f_{2}. Thus with the Euler equation we get C = \frac{1}{4}(r − 2)n^{r} = (rn − 2n)N. Finally, counting the vertex-facet incidences according to facets yields f_{03} = 8C + 2nP = (8rn − 16n + 8rn)N. □

References

[1] N. Amenta and G. M. Ziegler, Deformed products and maximal shadows, Advances in Discrete and Computational Geometry (South Hadley, MA, 1996), B. Chazelle, J. E. Goodman, and R. Pollack, eds., vol. 223 of Contemporary Mathematics, Amer. Math. Soc., Providence, RI, 1998, pp. 57–90. MR1661377 (2000a:52019)

[2] D. W. Barnette, Projections of 3-polytopes, Israel J. Math. 8 (1970), pp. 304–308. MR0262923 (41:7528)

[3] M. M. Bayer, The extended f-vectors of 4-polytopes, J. Combinatorial Theory, Ser. A, 44 (1987), pp. 141–151. MR0871395 (88b:52009)

[4] M. M. Bayer and L. J. Billera, Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Inventiones Math. 79 (1985), pp. 143–157. MR0774533 (86f:52010b)

[5] D. Eppstein, G. Kuperberg, and G. M. Ziegler, Fat 4-polytopes and fatter 3-spheres, Discrete Geometry: In honor of W. Kuperberg’s 60th birthday, A. Bezdek, ed., vol. 253 of Pure and Applied Mathematics, Marcel Dekker Inc., New York, 2003, pp. 239–265. arXiv:math.CO/0204007. MR2034720 (2004j:52009)

[6] G. Gévay, Kepler hypersolids, Intuitive Geometry (Szeged, 1991), vol. 63 of Colloq. Math. Soc. János Bolyai, Amsterdam, 1994, North-Holland, pp. 119–129. MR1383617 (97a:52013)

[7] B. Grünbaum, Convex Polytopes, vol. 221 of Graduate Texts in Math., Springer-Verlag, New York, 2003. Second edition edited by V. Kaibel, V. Klee and G. M. Ziegler (original edition: Interscience, London 1967). MR1976856 (2004b:52001)

[8] A. Höppner and G. M. Ziegler, A census of flag-vectors of 4-polytopes, in Polytopes — Combinatorics and Computation, G. Kalai and G. M. Ziegler, eds., vol. 29 of DMV Seminars, Birkhäuser-Verlag, Basel, 2000, pp. 105–110. MR1785294 (2001e:52026)

[9] M. Joswig and G. M. Ziegler, Neighborly cubical polytopes, Discrete Comput. Geometry (Grünbaum Festschrift (G. Kalai, V. Klee, eds.)) 24 (2000), pp. 325–344. arXiv:math.CO/9812033. MR1758054 (2001f:52019)

[10] G. Kalai, Rigidity and the lower bound theorem, I, Inventiones Math. 88 (1987), pp. 125–151. MR0877009 (88b:52014)

[11] A. Paffenholz, New polytopes from products. Preprint, TU Berlin, November 2004, 22 pages.

arXiv:math.MG/0411092.

[12] A. Paffenholz and G. M. Ziegler, The E_{t}-construction for lattices, spheres and polytopes. Discrete Comput. Geometry (Billera Festschrift (M. Bayer, C. Lee, B. Sturmfels, eds.)), in print; published online August 23, 2004; arXiv:math.MG/0304492.

[13] L. Schläfli, Theorie der vielfachen Kontinuität, Denkschriften der Schweizerischen naturforschenden Gesellschaft, Vol. 38, pp. 1–237, Zürcher und Furrer, Zürich, 1901. Written in 1850–1852. Reprinted in: Ludwig Schläfli, 1814–1895, Gesammelte Mathematische Abhandlungen, Vol. I, Birkhäuser, Basel, 1950, pp. 167–387. MR0034587 (11:611b)

[14] T. Schröder, On neighborly cubical spheres and polytopes. Work in progress, TU Berlin, 2004.

[15] R. P. Stanley, Generalized h-vectors, intersection cohomology of toric varieties, and related results, Commutative Algebra and Combinatorics, M. Nagata and H. Matsumura, eds., vol. 11 of Advanced Studies in Pure Mathematics, Kinokuniya, Tokyo, 1987, pp. 187–213. MR0951205 (89f:52016)

[16] E. Steinitz, Über die Eulerschen Polyederrelationen, Archiv für Mathematik und Physik 11 (1906), pp. 86–88.

[17] G. M. Ziegler, Lectures on Polytopes, vol. 152 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995. Revised edition, 1998; “Updates, corrections, and more” at

www.math.tu-berlin.de/ ziegler. MR1311028 (96a:52011)

[18] , Face numbers of 4-polytopes and 3-spheres, Proceedings of the International Congress of Mathematicians (ICM 2002, Beijing), L. Tatsien, ed., vol. III, Higher Education Press, Beijing, 2002, pp. 625–634. arXiv:math.MG/0208073. MR1957513 (2003i:00010b)

[19] , Convex polytopes: Extremal constructions and f-vector shapes. Park City Mathematical Institute (PCMI 2004) Lecture Notes. With an Appendix by Th. Schröder and N. Witte, 2004. Preprint, TU Berlin, November 2004, 73 pages.

Inst. Mathematics, MA 6-2, TU Berlin, D-10623 Berlin, Germany

E-mail address: ziegler@math.tu-berlin.de