Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. 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}