These pages are not updated anymore. They reflect the state of . For the current production of this journal, please refer to http://www.math.psu.edu/era/.
%_ ************************************************************************** %_ * The TeX source for AMS journal articles is the publishers TeX code * %_ * which may contain special commands defined for the AMS production * %_ * environment. Therefore, it may not be possible to process these files * %_ * through TeX without errors. To display a typeset version of a journal * %_ * article easily, we suggest that you retrieve the article in DVI, * %_ * PostScript, or PDF format. * %_ ************************************************************************** % Author Package file for use with AMS-LaTeX 1.2 \controldates{17-NOV-2004,17-NOV-2004,17-NOV-2004,17-NOV-2004} \RequirePackage[warning,log]{snapshot} \documentclass{era-l} \issueinfo{10}{14}{}{2004} \dateposted{December 1, 2004} \pagespan{122}{134} \PII{S 1079-6762(04)00137-4} \copyrightinfo{2004}{} \revertcopyright \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} \usepackage{graphicx} \theoremstyle{plain} \newtheorem{lemma}{Lemma}[section] \newtheorem{theorem}[lemma]{Theorem} \newtheorem*{maintheorem}{Theorem} \newtheorem{corollary}[lemma]{Corollary} \newtheorem{proposition}[lemma]{Proposition} \theoremstyle{definition} \newtheorem{definition}[lemma]{Definition} \newtheorem{example}[lemma]{Example} \newtheorem{convention}[lemma]{Convention} \newtheorem{observation}[lemma]{Observation} \theoremstyle{remark} \newtheorem*{remark}{Remark} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\eps}{\varepsilon} \DeclareMathOperator{\aff}{aff} \DeclareMathOperator{\conv}{conv} \DeclareMathOperator{\cone}{cone} \DeclareMathOperator{\lin}{lin} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\relint}{relint} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\vol}{vol} \newcommand{\myvec}[1]{{\boldsymbol {#1}}} \newcommand{\vv}{\myvec{v}} \newcommand{\uu}{\myvec{u}} \newcommand{\ww}{\myvec{w}} \newcommand{\xx}{\myvec{x}} \newcommand{\yy}{\myvec{y}} \newcommand{\bb}{\myvec{b}} \newcommand{\cc}{\myvec{c}} \newcommand{\ee}{\myvec{e}} \newcommand{\nn}{\myvec{n}} \newcommand{\zero}{\myvec{0}} \newcommand{\F}{\mathcal{F}} \graphicspath{{pictures/}} \begin{document} \title{Projected products of polygons} \author{G\"unter M. Ziegler} \address{Inst. Mathematics, MA 6-2, TU Berlin, D-10623 Berlin, Germany} \email{ziegler@math.tu-berlin.de} \thanks{Partially supported by Deutsche Forschungs-Gemeinschaft (DFG), via the \emph{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)} \date{July 4, 2004} \revdate{September 17, 2004} \commby{Sergey Fomin} \subjclass[2000]{Primary 52B05; Secondary 52B11, 52B12} \keywords{Discrete geometry, convex polytopes, $f$-vectors, deformed products of polygons} \begin{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 $f$-vector 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 $\pi(P^{2r}_n)$ with extreme combinatorial structure. In this family, the ``fatness'' of the $f$-vector gets arbitrarily close to~$9$; an analogous invariant of the flag vector, the ``complexity,'' gets arbitrarily close to~$16$. \par The polytopes are obtained from suitable deformed products of even polygons by a projection to~$\mathbb{R}^4$. \end{abstract} \maketitle \section{Introduction} \subsection{{\itshape f}\/-vectors} The combinatorial structure of a $d$-dimensional convex polytope is given by the incidences between its $k$-dimensional faces, for $0\le k\le d-1$. In particular one looks at the faces of dimensions $0$, $1$, $d-2$, and $d-1$, known as the \emph{vertices}, \emph{edges}, \emph{ridges}, and \emph{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 \emph{$f$-vectors}, that is, the $d$-tuples \[ f(P)\ :=\ (f_0,f_1,\dots,f_{d-2},f_{d-1})\ \in\Z^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 $\R^d$, but due to the Euler--Poincar\'e relation \[ f_0-f_1\pm\dots+(-1)^{d-1}f_{d-1}\ =\ 1-(-1)^d \] the set of all $f$-vectors of $d$-polytopes \[ \F_d\ :=\ \big\{f=(f_0,f_1,\dots,f_{d-1})\in\Z^d : f=f(P)\textrm{ for a $d$-polytope }P\big\} \] has dimension $d-1$ \cite[Chapter 8]{Gr1-2}. 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. For example, a $d$-polytope is simplicial if and only if its $f$-vector satisfies $f_{d-2}=\frac d2 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}\le d\, f_{d-1}$ is valid for all polytopes, and the constraint is tight exactly if all facets are simplices. Thus simplicial polytopes are \emph{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 \cite{Z99} contain a more extensive discussion of the interplay between $f$-vector theory and constructions of extremal polytopes that arises from this. \subsection{Flag vectors} Additional combinatorial information is contained in the \emph{flag vector} of a $d$-polytope, which in addition to the components $f_k$ of the $f$-vector also records the numbers $f_{k,\ell}$ of incidences of $k$-faces with $\ell$-faces (that is, the numbers of pairs $(F,G)$ consisting of a $k$-face $F$ contained in an $\ell$-face $G$, for $k<\ell$), the numbers $f_{k,\ell,m}$ of chains of three faces $F\subset G\subset H$ of dimensions $k<\ell0$ there are polytopes of fatness larger than $9-\eps$. \end{theorem} Thus the known polytopes now span a hexagon, which is shaded in Figure~\ref{fig:phiplane}. A flag vector parameter that is similar to fatness, called \emph{complexity}~\cite{Z82}, is defined by \[ C(P)\ :=\ \frac{f_{03}-20}{f_0+f_3-10}. \] All $4$-polytopes satisfy $C(P)\ge3$. Fatness and complexity are roughly within a factor of~$2$: $C(P)\le 2F(P)-2$ and $F(P)\le 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 \cite{Z62}, of complexity $8-\eps$. Our present construction yields ``neighborly cubical polytopes'' for $n=4$, but for $n,r\rightarrow\infty$ it yields complexity as large as $16-\eps$. In the following two sections, we review the main ingredients for the construction of $\pi(P_n^{2r})$. The construction that yields Theorem~\ref{thm:ppp} is described in Section~\ref{sec:construction}, with a sketch of the proof for its correctness. The flag vectors of the polytopes~$\pi(P_n^{2r})$ are computed in Section~\ref{sec:flag}, which yields Theorem~\ref{thm:f-vectors}. 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.\ \cite{schroeder04}) as well as necessity of the restrictions (e.g., that $n$ must be even) are topics of current research and will be presented later. \subsection*{Acknowledgements} The intuition for the construction given here grew from previous joint work and current discussions with Nina Amenta, Michael Joswig, Raman Sanyal, \pagebreak and Thilo Schr\"oder. \section{Products and deformed products}\label{sec: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 $\sum_{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 \emph{polygons}; they arise as products of one of the $n$-gons with a vertex from each of the other factors. There are also $\binom r2 n^r$ \emph{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=r n^{r-1} + \binom r2 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 \begin{equation*} \left(\raisebox{-39mm}{\includegraphics{era137el-pict-1}}\!\right)\xx \ \ \le\ \ \left(\raisebox{-39mm}{\includegraphics{era137el-pict-2}}\!\right), \end{equation*} assuming that $V\xx\le\bb$ is a correct description for an $n$-gon. For this it is necessary and sufficient that the row vectors $\vv_i$ of $V$ are non-zero and distinct and that they positively span~$\R^2$, that the components $b_i$ of~$\bb$ are positive, and that the rescaled vectors $\tfrac1{b_i}\vv_i$ are in convex position (the vertices of the polar of the polygon). For this we say that a finite set of vectors $\vv_1,\dots,\vv_k\in\R^d$ \emph{positively spans} if it satisfies the following equivalent conditions: \begin{enumerate} \item[(i)] every vector $\xx\in\R^d$ is a linear combination of the vectors $\vv_i$, with non-negative \pagebreak coefficients; \item[(ii)] every vector $\xx\in\R^d$ is a linear combination of the vectors $\vv_i$, with positive coefficients; \item[(iii)] the vectors $\vv_i$ span $\R^d$, and $\zero\in\R^d$ is a linear combination of the vectors $\vv_i$, with positive coefficients (that is, the vectors $\vv_i$ are \emph{positively dependent}). \end{enumerate} In the following, we will need ``deformed products.'' (The deformations are more general than the ``rank~$1$'' deformations as described in Amenta and Ziegler \cite{Z51a}.) For this, we look at systems of the form \begin{equation*} \left(\raisebox{-39mm}{\includegraphics{era137el-pict-3}}\!\right)\xx \ \ \le\ \ \left(\raisebox{-39mm}{\includegraphics{era137el-pict-4}} \!\right). \end{equation*} Given any such left-hand side matrix for such a system, we can adapt the right-hand side so that the resulting polytope is \emph{combinatorially equivalent} to~$(C_n)^r$. For this all components of $\bb_k$ have to be sufficiently large compared to $\bb_1,\dots,\bb_{k-1}$, for $k=2,3,\dots,r$. (Compare \cite{Z51a} and \cite{Z62}.) \section{Projections}\label{sec:projections} We will work with a rather restrictive concept of faces ``being preserved under projection.'' \begin{definition}[Strictly preserving faces under projection]% \label{def:strictly}% Let $\pi:P\rightarrow Q=\pi(P)$ be a projection of polytopes. Then a face $G\subseteq P$ is \emph{strictly preserved} if \begin{enumerate} \item[(i)]\label{ci} its image $\pi(G)$ is a face of~$Q$, \item[(ii)]\label{cii} the map $G\rightarrow\pi(G)$ is a bijection, and \item[(iii)]\label{ciii} the preimage of the image is $G$, that is, $\pi^{-1}(\pi(G))=G$. \end{enumerate} \end{definition} In the definition, conditions (ii) and (iii) are both needed. Indeed, in the projection ``to the second coordinate'' displayed in our figure, the vertex \pagebreak $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. \begin{equation*} \includegraphics{era137el-pict-5} \end{equation*} 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 $\cc$ \emph{defines} the face $G\subseteq P$ given by all the points of $P$ that have maximal scalar product with $\cc$. This describes exactly all the vectors in the relative interior of the \emph{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 $\nn_F^{}$ to the facets $F\subset P$ that contain~$G$. (Compare \cite[Sections 2.1, 3.2, 7.1]{Z35}.) \begin{proposition}\label{prop:preserve}% Let $\pi:\R^{e+d}\rightarrow\R^d$, $(\xx',\xx'')\mapsto\xx''$ be the projection to the last~$d$ coordinates, and let $P\subset\R^{e+d}$ be an $(e+d)$-dimensional polytope, and let $G$ be a face of~$P$. Then the following three conditions are equivalent: \begin{enumerate} \item[(1)] $G$ is strictly preserved by the projection $\pi:P\rightarrow\pi(P)=Q$. \item[(2)] Any $\cc'\in\R^e$ arises as the first $e$ components of a vector $(\cc',\cc'')$ that defines~$G$. \item[(3)] The vectors $\nn_F'$, given by the first $e$ components of the normal vectors $(\nn_F',\nn_F'')=\nn^{}_F$ to facets $F$ of~$P$ that contain $G$, positively span $\R^e$. \end{enumerate} \end{proposition} \begin{proof} Here we only establish ``$(3)\Rightarrow(1)$,'' which is used in the following. If the vectors $\nn_F'$ are positively dependent, then some positive combination of the vectors $(\nn_F',\nn_F'')=\nn^{}_F$ yields $(\zero,\cc'')=:\cc$. A point $\xx\in P$ lies in the face $G\subseteq P$ if and only if its scalar product with each facet normal $\nn^{}_F$ is maximal. This happens if and only if $\cc^t\xx$ is maximal, that is, iff $(\cc'')^t\xx''$ is maximal under the restriction $\xx''\in\pi(P)$. Thus we have established that under the assumption (3), $\pi(G)=:\bar G$ is a face of~$\pi(P)$, and $\pi^{-1}(\pi(G))=\pi^{-1}(\bar G)=G$; that is, conditions (i) and (iii) of Definition~\ref{def:strictly} are satisfied. For part~(ii) of Definition~\ref{def:strictly}, we have to show that $G\rightarrow\pi(G)$ is injective. Assume that $\xx=(\xx',\xx'')$ and $\yy=(\yy',\yy'')$ are points in~$G$ with $\pi(\xx)=\pi(\yy)$, that is, $\xx''=\yy''$. For each normal vector $\nn^{}_F=(\nn_F',\nn_F'')$ we have $\nn^{}_F{}^t\xx=\nn^{}_F{}^t\yy$ and $(\nn_F'')^t\xx''=(\nn_F'')^t\yy''$, which implies $(\nn_F')^t\xx''=(\nn_F')^t\yy''$. But the vectors $\nn_F'$ that correspond to the various facets $F$ that contain~$G$ are positively spanning in~$\R^e$, which implies $\xx'=\yy'$. \end{proof} \section{Construction}\label{sec:construction} \begin{proposition}[Construction for the proof of Theorem~\ref{thm:ppp}] For $n\ge4$ even and $r\ge2$, let $P_n^{2r}$ be defined by the linear inequality system \begin{equation*} \left(\raisebox{-55mm}{\includegraphics{era137el-pict-6}} \right)\xx \ \ \le\ \ \left(\raisebox{-55mm}{\includegraphics{era137el-pict-7}} \right). \end{equation*} Here the left-hand side coefficient matrix $A_{n,r}^\eps\in\R^{rn\times 2r}$ contains blocks of size $n\times 2$, where \begin{equation*} V=\raisebox{-8mm}{\includegraphics{era137el-pict-8}} \longrightarrow V^\eps=\raisebox{-8mm}{\includegraphics{era137el-pict-9}}, \qquad W=\raisebox{-8mm}{\includegraphics{era137el-pict-10}}, \qquad U=\raisebox{-8mm}{\includegraphics{era137el-pict-11}} \ \in\ \R^{n\times2}, \end{equation*} with \begin{gather*} \vv_0=(1,0),\ \vv_1=(0,0)=\zero,\ \ww_0=(0,1),\ \ww_1=(-3,-\tfrac23),\\ \uu_0=(-\tfrac{31}4,\tfrac12),\ \uu_1=(9,-\tfrac23). \end{gather*} The block $V^\eps$ arises from $V$ by an $\eps$-perturbation: \[ \vv_i^\eps\ =\ \begin{cases} \hphantom{\eps}\big(1-\eps (n-2-2i)^2,\eps (n-2-2i)\big) &\textrm{for }i=0,2,4,\ldots,n-2,\\ {\eps}\big(1-\eps (n-2-2i)^2,\eps (n-2-2i)\big) &\textrm{for }i=1,3,5,\ldots,n-3,\\ \eps(-1,0)\ =\ (-\eps,0) &\textrm{for }i=n-1 \end{cases} \] for a sufficiently small $\eps>0$. All entries of $A^\eps_{n,r}$ outside the $r+(r-1)+(r-2)=3r-3$ blocks of types $V^\eps$, $W$ and $U$ are zero. Let the right-hand side vector be such that $\bb_1$ is given by $b_{1,i}=1$ for even $i$, and $b_{1,i}=\eps$ for odd~$i$, and by $\bb_k=M^{k-1}\bb_1$ for sufficiently large $M$. Then $P_n^{2r}$ has the properties claimed by Theorem~\ref{thm:ppp}. 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. \end{proposition} \begin{proof} The rows $\vv_i^\eps$ of $V^\eps$ are indeed in cyclic order: \begin{equation*} \includegraphics[scale=.95]{era137el-pict-12} \end{equation*} Moreover, rescaled as $\frac1{b_{k,i}}\vv_i^\eps=\frac1{M^{k-1}\eps}\vv_i^\eps$ for odd~$i$ and as $\frac1{b_{k,i}}\vv_i^\eps=\frac1{M^{k-1} }\vv_i^\eps$ for even $i$ they are in convex position, if $\eps$ is small; so $V^\eps\xx\le\bb_i$ defines a convex $n$-gon. Thus for sufficiently small $\eps$ and sufficiently large~$M$, the polytope $P_{2r}$ is indeed a deformed product of polygons, as discussed in Section~\ref{sec:products}. Now we show that for sufficiently small $\eps$, 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^\eps$-blocks, which we denote by $A_{n,r}^0=A_{n,r}$, satisfies the linear algebra condition dictated by Proposition~\ref{prop:preserve}(3). This is sufficient, since the ``positively spanning'' condition is stable under perturbation by a small~$\eps$. Any polygon $2$-face $G$ of the simple $2r$-polytope $P^{2r}_n$ 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 $2$-face 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~\ref{prop:preserve}(3) we have to show: \begin{quote}\emph{% If one of the $r$ pairs of rows is deleted from the reduced matrix \begin{equation*} A'_{n,r}\ \ =\ \ \left( \raisebox{-25mm}{\includegraphics{era137el-pict-13}} \right) \ \ \in\ \R^{2r\times (2r-4)}, \end{equation*} then the remaining $2r-2$ rows\\ {\rm(a)} \ span $\R^{2r-4}$, and\\ {\rm(b)} \ have a linear dependence with strictly positive coefficients.} \end{quote} Let us establish (b) first. For this, let \[ \alpha_k\ :=\ 2^k+2^{-k}-2\qquad\textrm{and}\qquad \beta_k \ :=\ 2^k+\tfrac54 2^{-k}-\tfrac94. \] These sequences are designed to be non-negative, $\alpha_k,\beta_k\ge0$ for all $k\in\Z$, with equality only for $k=0$. Thus for (b) it suffices to verify that \begin{quote}\emph{% For any $1\le t\le r$, the rows of $A'_{n,r}$ are positively dependent with coefficients $\alpha_{k-t}$ for the even-index row from the $k$-th block, and $ \beta_{k-t}$ for the odd-index row from the $k$-th block,} \end{quote} 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 \[ \alpha_{k-1}\vv_0 + \alpha_k \ww_0 + \beta_k \ww_1 + \alpha_{k+1}\uu_0 + \beta_{k+1}\uu_1 \ =\ \zero, \] which is needed to hold for $k\le |r-2|$, but which we impose for all $k\in\Z$. The choice of vectors $\vv_0,\ww_0,\ww_1,\uu_0,\uu_1$ is designed to satisfy this condition. Indeed, except for the choice of a basis, which we took to be $\vv_0=(1,0)$ and $\ww_0=(0,1)$, the configuration of five vectors $\vv_0,\ww_0,\ww_1,\uu_0,\uu_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 \begin{equation*} \Big( \raisebox{-2.5mm}{\includegraphics{era137el-pict-14}} \Big) \end{equation*} is non-singular. If a later pair of rows is deleted, then we are faced with the task to show that the $2k\times 2k$ matrices $M_k$ of the form \begin{equation*} M_k\ \ :=\ \ \left( \raisebox{-15.5mm}{\includegraphics{era137el-pict-15}} \right) \ \ \in\ \R^{2k\times 2k} \end{equation*} 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 $(\alpha_0,\beta_0,\alpha_1,\ldots,\break\alpha_{k-1},\beta_{k-1})$, then this will result in the linear combination of the three rows of the matrix \begin{equation*} H_3\ \ =\ \ \left( \raisebox{-4mm}{\includegraphics{era137el-pict-16}} \right)\ \in\ \R^{3\times2r} \end{equation*} with the coefficients $(-\alpha_{-1},-\alpha_k,-\beta_k)$, since $\vv_1=\zero$. Similarly, if we sum the rows of $M_k$ with coefficients $(\alpha_1,\beta_1,\alpha_2,\ldots,\alpha_k,\beta_k)$, then we get a linear combination of the same three rows, with coefficients $(-\alpha_0,-\alpha_{k+1},-\beta_{k+1})$. And if we use coefficients $(\alpha_2,\beta_2,\alpha_3,\ldots,\alpha_{k+1},\beta_{k+1})$ to sum the rows of $M_k$, then the result will be a sum with coefficients $(-\alpha_1,-\alpha_{k+2},-\beta_{k+2})$. The coefficient matrix \[ \begin{pmatrix} -\alpha_{-1} & -\alpha_k & -\beta_k\\ -\alpha_0 & -\alpha_{k+1} & -\beta_{k+1}\\ -\alpha_1 & -\alpha_{k+2} & -\beta_{k+2} \end{pmatrix} \] is non-singular for $k\ge0$: its determinant is $\tfrac38(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 $\ee_{2k-1},\ee_{2k}\in\R^{2k}$ in the row space of $H_3$, and thus of $M_k$, and this allows us to complete the argument by induction. \end{proof} \section{Flag vectors}\label{sec:flag} The following result includes Theorem~\ref{thm:f-vectors}. Note that its proof relies only on the properties of~$\pi(P_n^{2r})$ that are guaranteed by the statement of Theorem~\ref{thm:ppp}; it does not refer to the specific combinatorial type of the polytopes constructed in Section~\ref{sec:construction}, in our proof of Theorem~\ref{thm:ppp}. \begin{theorem}\label{cor:flag} The $4$-polytope $\pi(P_n^{2r})$ has the flag vector \begin{align*} (f_0,f_1,f_2,f_3;f_{03}) & = (n^r,rn^r, \tfrac54rn^r\!-\tfrac32n^r\!+rn^{r-1}, \tfrac14rn^r\!-\tfrac12n^r\!+rn^{r-1}; 4rn^r\!-4n^r)\\ &= (4n, 4rn, 5rn-6n+4r, rn-2n+4r; 16rn-16n)\cdot \tfrac14 n^{r-1}. \end{align*} \end{theorem} \begin{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:=\frac14n^{r-1}$ this yields $f_0=4nN$ vertices and $f_1=4rnN$ edges for $\pi(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\ge0$ of cube facets. Now double counting of ridges yields $6C+(n+2)P=2f_2$. Thus with the Euler equation we get $C=\frac14(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$. \end{proof} \begin{thebibliography}{10} \bibitem{Z51a} {\sc N.~Amenta and G.~M. Ziegler}, {\em 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. \MR{1661377 (2000a:52019)} \bibitem{Bar4} {\sc D.~W. Barnette}, {\em Projections of $3$-polytopes}, Israel J. Math. 8 (1970), pp.~304--308. \MR{0262923 (41:7528)} \bibitem{Bay} {\sc M.~M. Bayer}, {\em The extended $f$-vectors of $4$-polytopes}, J. Combinatorial Theory, Ser. A, 44 (1987), pp.~141--151. \MR{0871395 (88b:52009)} \bibitem{BaBi} {\sc M.~M. Bayer and L.~J. Billera}, {\em Generalized {D}ehn-{S}ommerville relations for polytopes, spheres and {E}ulerian partially ordered sets}, Inventiones Math. 79 (1985), pp.~143--157. \MR{0774533 (86f:52010b)} \bibitem{Z80} {\sc D.~Eppstein, G.~Kuperberg, and G.~M. Ziegler}, {\em Fat $4$-polytopes and fatter $3$-spheres}, Discrete Geometry: {I}n 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. \newblock \texttt{arXiv:math.CO/0204007}. \MR{2034720 (2004j:52009)} \bibitem{Gevay} {\sc G.~G\'evay}, {\em Kepler hypersolids}, Intuitive Geometry (Szeged, 1991), vol.~63 of Colloq. Math. Soc. J\'anos Bolyai, Amsterdam, 1994, North-Holland, pp.~119--129. \MR{1383617 (97a:52013)} \bibitem{Gr1-2} {\sc B.~Gr{\"u}nbaum}, {\em Convex {P}olytopes}, 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). \MR{1976856 (2004b:52001)} \bibitem{Z59} {\sc A.~H\"oppner and G.~M. Ziegler}, {\em 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\"auser-Verlag, Basel, 2000, pp.~105--110. \MR{1785294 (2001e:52026)} \bibitem{Z62} {\sc M.~Joswig and G.~M. Ziegler}, {\em Neighborly cubical polytopes}, Discrete Comput. Geometry (Gr\"unbaum Festschrift (G. Kalai, V. Klee, eds.)) 24 (2000), pp.~325--344. \newblock \texttt{arXiv:math.CO/9812033}. \MR{1758054 (2001f:52019)} \bibitem{kalai87:_rigid_i} {\sc G.~Kalai}, {\em Rigidity and the lower bound theorem, {I}}, Inventiones Math. 88 (1987), pp.~125--151. \MR{0877009 (88b:52014)} \bibitem{paffenholz-pc} {\sc A.~Paffenholz}, {\em New polytopes from products}. Preprint, TU Berlin, November 2004, 22~pages. \texttt{arXiv:math.MG/0411092}. \bibitem{Z89} {\sc A.~Paffenholz and G.~M. Ziegler}, {\em 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; \texttt{arXiv:math.MG/0304492}. \bibitem{Schla} {\sc L.~Schl\"afli}, {\em Theorie der vielfachen Kontinuit\"at}, Denkschriften der Schwei\-ze\-ri\-schen naturforschenden Gesellschaft, Vol.~38, pp.~1--237, Z\"urcher und Furrer, Z\"urich, 1901. Written in 1850--1852. Reprinted in: Ludwig Schl\"afli, 1814--1895, Gesammelte Mathemati\-sche Abhandlungen, Vol. I, Birkh\"auser, Basel, 1950, pp. 167--387. \MR{0034587 (11:611b)} \bibitem{schroeder04} {\sc T.~Schr\"oder}, {\em On neighborly cubical spheres and polytopes}. Work in progress, TU Berlin, 2004. \bibitem{Sta7} {\sc R.~P. Stanley}, {\em 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. \MR{0951205 (89f:52016)} \bibitem{Stei3} {\sc E.~Steinitz}, {\em {\"U}ber die {E}ulerschen {P}olyederrelationen}, Archiv f\"ur Mathematik und Physik 11 (1906), pp.~86--88. \bibitem{Z35} {\sc G.~M. Ziegler}, {\em Lectures on {P}olytopes}, vol.~152 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1995. Revised edition, 1998; ``Updates, corrections, and more'' at \texttt{www.math.tu-berlin.de/~ziegler}. \MR{1311028 (96a:52011)} \bibitem{Z82} \bysame, {\em 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. \newblock \texttt{arXiv:math.MG/0208073}. \MR{1957513 (2003i:00010b)} \bibitem{Z99} \bysame, {\em Convex polytopes: {E}xtremal constructions and $f$-vector shapes}. Park City Mathematical Institute (PCMI 2004) Lecture Notes. With an Appendix by Th. Schr\"oder and N. Witte, 2004. Preprint, TU Berlin, November 2004, 73 pages. \end{thebibliography} \end{document}