%Dec-96 %%%%%%%%% La TeX2e %%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{amsart} \headheight=8pt \textheight=574pt \textwidth=432pt \oddsidemargin=18.88pt \evensidemargin=18.88pt \topmargin=14.21pt \makeatletter \let\atopwithdelims\@@atopwithdelims \let\over\@@over %\usepackage{amstex} \newtheorem{theorem}{Theorem}%[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{observation}[theorem]{Observation} \newtheorem{problem}{Problem} %\newcommand{\qed}{\hfill \mbox{ $\Box$} \\ \vspace{1mm} } %\newenvironment{proof}{\noindent\mbox{\sc Proof} }{\qed} \newenvironment{example}{\mbox{\sc Example} }{} \newenvironment{remark}{\mbox{\sc Remark} }{} \newenvironment{definition}{\mbox{\sc Definition} }{\qed} \newcommand{\DEF}{\buildrel {\rm def} \over =} \newcommand{\sso}{\mathop {\rm ss}} \newcommand{\rank}{\mathop {\rm rank}} %\newcommand{\mod}{{\mbox {mod }}} \newcommand{\fv}{{{\bf f}}} \newcommand{\gv}{{{\bf g}}} \newcommand{\fE}{{E_{\bullet}\!}} \newcommand{\fF}{{F_{\bullet}\!}} \newcommand{\cP}{{\cal P}} \newcommand{\Z }{{Z\!\!\! Z}} \newcommand{\pa }{{\partial}} \newcommand{\la }{{\langle}} \newcommand{\lb }{{\lambda}} \newcommand{\da }{{\delta}} \newcommand{\ra}{{\rangle}} \newcommand{\meet}{\wedge} \newcommand{\join}{\vee} \newcommand{\chX}{\check{X}} \newcommand{\cX}{{\cal X}} \begin{document} \title[The number of $k$-faces of a simple $d$-polytope]{The number of {\large $\lowercase{k}$}-faces of a simple {\large $\lowercase{d}$}-polytope} \author{Anders Bj\"orner} \address{\hskip-\parindent Anders Bj\"orner\\ Department of Mathematics \\ Royal Institute of Technology \\ S-100 44 Stockholm, SWEDEN} \email {bjorner@math.kth.se } \author{Svante Linusson} \address{\hskip-\parindent Svante Linusson\\ Department of Mathematics \\ Stockholm University \\ S-106 91 Stockholm, SWEDEN} \email{linusson@matematik.su.se} \thanks{Both authors were supported by EC grant CHRX-CT93-0400 and by the Mathematical Sciences Research Institute (Berkeley, CA). Research at MSRI is supported in part by NSF grant DMS-9022140.} \begin{abstract} Consider the question: Given integers $k N(d,k)$ the answer is yes if and only if $n\equiv 0\quad \pmod {G(d,k)}$. Furthermore, a formula for $G(d,k)$ is given, showing that e.g. $G(d,k)=1$ if $k\ge \left\lfloor\frac{d+1}{2}\right\rfloor$ or if both $d$ and $k$ are even, and also in some other cases (meaning that all numbers beyond $N(d,k)$ occur as the number of $k$-faces of some simple $d$-polytope). This question has previously been studied only for the case of vertices ($k=0$), where Lee \cite{Le} proved the existence of $N(d,0)$ (with $G(d,0)=1$ or $2$ depending on whether $d$ is even or odd), and Prabhu \cite{P2} showed that $N(d,0) \le cd\sqrt {d}$. We show here that asymptotically the true value of Prabhu's constant is $c=\sqrt2$ if $d$ is even, and $c=1$ if $d$ is odd. \end{abstract} \maketitle \section{Introduction} An integer $n$ will be called $(d,k)$-{\it realizable} if there is a simple $d$-polytope with $n$ faces of dimension $k$. For terminology and basic properties of polytopes we refer to the literature, see e.g. \cite{Z}. We show, see Theorem \ref{gap-thm}, that there exist numbers $G(d,k)$ and $N(d,k)$ such that \begin{itemize} \item{if $n$ is $(d,k)$-realizable then $G(d,k)$ divides $n$;} \item{if $G(d,k)$ divides $n$ and $n>N(d,k)$ then $n$ is $(d,k)$-realizable.} \end{itemize} The $G(d,k)$-divisible numbers that are not $(d,k)$-realizable will be called $(d,k)$-{\it gaps}. Thus there are only finitely many gaps for all $d>k\ge 0$. In this paper we study the numbers $G(d,k)$ and $N(d,k)$. Our proofs rely on the $g$-theorem. To give some feeling for the results, let us discuss a few special cases. The parity restrictions that exist for each dimension $k$ are easiest to understand for the case of vertices ($k=0$). Namely, the graph of a simple $d$-polytope is $d$-regular, so if the polytope has $n$ vertices then it has $\frac{dn}{2}$ edges. Hence, if $d$ is odd $n$ must be even. This is in fact the only constraint, and we have \[ G(d,0)=\left\{ \begin{array}{rl} 1, &\quad \mbox{$d$ even}\\ 2, &\quad\mbox{$d$ odd.} \end{array}\right. \] This result is due to Lee \cite{Le}, who initiated the study of properties of vertex-count numbers of simple polytopes. Via the regular graph property this also implies the result for edge-count numbers: \[ G(d,1)=\left\{ \begin{array}{rl} \frac{d}{2}, &\quad \mbox{$d$ even}\\ d, &\quad\mbox{$d$ odd.} \end{array}\right. \] For $1a_{s-1}>\dots>a_i\ge i\ge 1$. Then define: \[\pa^s(n):={a_s-1\choose s-1}+{a_{s-1}-1\choose s-2}+ \dots+{a_i-1\choose i}. \] Also let $\pa^s(0):=0$. A nonnegative integer sequence $(n_0,n_1,n_2,\dots)$ is called an {\it $M$-sequence} if \[n_0=1 \quad\mbox{ and } \quad \partial^s(n_s)\le n_{s-1}\quad \mbox{for all }s\ge 1. \] Two simple facts we will need about $M$-sequences is that if there is a zero in the sequence then all the following entries are also zeros, and that any sequence satisfying $n_0=1$ and $n_1\ge n_2\ge n_3 \ge\dots$ is an $M$-sequence. An alternative definition of $M$-sequence, due to Macaulay and Stanley \cite{S1}, says that a sequence is a $M$-sequence if and only if it is the $f$-vector of a multicomplex. See \cite {Li} and \cite {Z} for examples of other interpretations of $M$-sequences. Let $\left\lfloor x\right\rfloor$ and $\left\lceil x\right\rceil$ denote the largest integer less than or equal to $x$ and the smallest integer larger than or equal to $x$, respectively. Let $\da:=\left\lfloor {d \over 2}\right\rfloor$ and let $M_d=(m_{ik})$ be the $(\da +1)\times d$-matrix with entries \[ m_{ik}={d+1-i\choose k+1}-{i\choose k+1}, \quad \mbox{for } 0\le i\le \da,\ 0\le k \le d-1. \] For example, \[ M_{10}=\left( \begin{array}{rrrrrrrrrr} 11&55 &165 &330 &462 &462 & 330&165 &55 &11 \\ 9& 45& 120 &210 &252 &210 &120 &45 &10& 1 \\ 7& 35 & 84 &126 &126 & 84 &36 & 9 & 1 & 0 \\ 5 &25 & 55 & 70 & 56 &28 & 8 & 1 &0&0 \\ 3 & 15 & 31 & 34 &21 & 7 & 1 &0 & 0 &0\\ 1 & 5 & 10 &10 & 5 & 1 &0&0 & 0 & 0 \\ \end{array} \right) \] Our proofs will rely on the $g$-theorem, conjectured by McMullen. Sufficiency was proved by Billera and Lee \cite{BL}, and necessity by Stanley \cite{S2} and later by McMullen \cite{M}, see \cite{Z}. We will use the following matrix reformulation of the $g$-theorem, given by Bj\"orner \cite{B1,B2}, see also \cite{Z}. We have here reformulated the statement from simplicial polytopes to simple polytopes, which just correspond to reading the $f$-vector backwards. \medskip \noindent \begin{theorem}\label{g-thm}{\bf [The $g$-theorem]} The matrix equation \[ \fv=\gv\cdot M_d \] gives a one-to-one correspondence between $f$-vectors $\fv$ of simple $d$-polytopes and $M$-sequences $\gv=(g_0,g_1,\dots,g_\da)$.\qed \end{theorem} \section{The modulus $G(d,k)$} The modulus mentioned in the introduction is defined as follows \begin{equation}\label{Gdef} G(d,k):=\gcd(m_{1,k},m_{2,k},\dots,m_{\da, k}), \end{equation} the greatest common divisor for the elements in the $k$-th column and below the top row of the matrix $M_d$. %Here we will prove some %identities and divisibility properties for the numbers $G(d,k)$. In this section we will give simple and explicit formulas for $G(d,k)$. The role of $G(d,k)$ as the period for the possible numbers of $k$-faces of $d$-polytopes will be shown in the next section. \begin{theorem}\label{th:main} \begin{enumerate} \item[(i)]{If $k\ge\left\lfloor\frac{d+1}{2}\right\rfloor$, then $G(d,k)=1.$} \item[(ii)]{If $k<\left\lfloor\frac{d+1}{2}\right\rfloor$ is even, let $e$ be the integer such that $2^{e}\le k+1<2^{e+1}$. Then \[G(d,k)=\left \{ \begin{array}{rl} 2, & \quad \mbox{ if $d-k+1\equiv 0$ (mod $2^{e+1}$)}\\ 1, & \quad \mbox{ otherwise}. \end{array} \right. \] } \item[(iii)]{If $k<\left\lfloor\frac{d+1}{2}\right\rfloor$ is odd, let $p_1,\dots,p_t$ be the primes smaller than or equal to $k+1$, and let $e_i\ge 1$ be the integers such that $p_i^{e_i}\le k+1p^{e}$, say $ap^{e}e$. In that case we have $$ \alpha+v_p((k+1)!)=v_p((i-k)\cdots s\cdots i)-v_p(s)+e = $$ $$ v_p((i-k)\cdots (s-1))+v_p((s+1)\cdots i)+e = v_p((s-(i-k))!)+v_p((i-s)!)+e, $$ where the last equality uses (\ref{a}) twice. Thus, using Lemma \ref{4}, $$ \alpha=-v_p((k-(i-s)+1)(k-(i-s)+2)\cdots (k+1))+v_p((i-s)!)+e = $$ $$ -v_p\left((k+1){k\choose i-s}\right)+e\ge 0. $$ \smallskip To prove $(iii)$ assume that ${d+i\choose k+1}\equiv_{p^r} 0$, for some $d\ge k+1$ and all $i=0,\dots,k$. Then ${d\choose j}\equiv_{p^r} 0$, for $j=1,\dots,k+1$. Especially, ${d\choose p^s}\equiv_{p^r} 0$ for $0\le s\le e$, which gives that $v_p({d\choose p^s})\ge r$. In particular, $v_p(d)\ge r$. We will now show that $v_p(d)\ge r+s$ for all $0\le s\le e$, by induction on $s$. Assume that $v_p(d)\ge r+s-1$. Then $r\le v_p({d\choose p^s})=v_p(d(d-1)\cdots(d-(p^s-1)))- v_p(1\cdot 2\cdots(p^s-1)p^s)=v_p(d)+v_p((p^s-1)!)-v_p((p^s-1)!)-v_p(p^s)= v_p(d)-s$. Hence, a run of $k+1$ consecutive zeros must begin with ${d\choose k+1}$ for some $d$ divisible by $p^{e+r}$. On the other hand, the $1$'s along the left boundary of Pascal's triangle show that there cannot be a run of more than $k+1$ zeros of the form ${i\choose k+1}$. This proves the lemma. \qed \medskip We can now proceed toward the proof of Theorem \ref{th:main}. \begin{lemma}\label{lm:delare} For each $k<\left\lfloor\frac{d+1}{2}\right\rfloor$, $G(d,k)$ is a divisor of $\frac{d-k+1}{\gcd(d-k+1, p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t})}$, where $p_1,\dots,p_t$ are the primes $\le k+1$ and $p_i^{e_i}\le k+1k_ep^e$. From $d-k+1\ge k+1>k_ep^e$ we conclude that $v_p(d-k+1-k_ep^e)\ge e$, which implies $v_p(d-k+1-k_ep^e-i)=v_p(i)$, for all $i=1,\dots,k+1-k_ep^eN$: \[\mbox{$n$ is the number of $k$-faces of a simple $d$-polytope }\] \[\Longleftrightarrow\] \[n\equiv 0\quad \pmod {G(d,k)}\] \end{theorem} \begin{proof} We will prove the theorem with the last statement replaced by $n\equiv m_{0,k}\; \pmod {G(d,k)}$. Lemma \ref{lm:coroll} shows that $m_{0,k}$ is divisible by $G(d,k)$, so this reformulation is equivalent. \smallskip\noindent $\Longrightarrow$ This direction is clear from Theorem \ref{g-thm}. \smallskip\noindent $\Longleftarrow$ Write \[ G(d,k) = \sum_{i=1}^{\da} \lb_i m_{i,k}, \qquad \lb_i \in \Z. \] Suppose $m_{1,k} = C\cdot G(d,k)$. Define \[ g_{\da}:=\left\{ \begin{array}{rl} (C-1) |\lb_{\da}| ,&\quad \mbox{ if $\lb_{\da} <0$}\\ 0 , &\quad\mbox{ otherwise;} \end{array}\right. \] and recursively \[ g_i := g_{i+1} + (C-1)(|\lb_{i}| + |\lb_{i+1}|) ,\qquad 00$, $\pa^s_{-p}(n)$ is the greatest number such that $\pa^s_p(\pa^s_{-p}(n))=n$. We will continue to write just $\pa^s$ for $\pa_1^s$. Now, fix $d$ and $k\ge \left\lfloor\frac{d+1}{2}\right\rfloor$. Define a vector $\gv:=(g_0,g_1,\dots,g_{d-k})$ inductively as follows. \begin {itemize} \item{} Let $g_{d-k}:=0$. \item{} Assume we have defined $g_{d-k},g_{d-k-1},\dots,g_i$, for some $0cd\sqrt{d}$ is $(d,0)$-realizable (with parity restrictions). This gives an upper bound on the size $N(d,0)$ of the largest gap in each dimension --- we are not aware of any published non-trivial lower bound. The exact result is previously known only for small dimensions, see \cite {Le} where Lee lists all $(d,0)$-gaps for $d\le 9$. We will sharpen Prabhu's result in both directions and prove that one can use $c=\sqrt{2}+\epsilon$ as constant in his theorem for any $\epsilon>0$ and sufficiently large even $d$. However, the statement is not true for $c<\sqrt 2$. \begin{theorem}\label{th:lower} If $d\ge 4$ is even, then there does not exist a simple $d$-polytope with $n=(d-1)(\left\lceil \sqrt {2d-4}\right\rceil-2)+4$ vertices.\qed \end{theorem} \begin{theorem}\label{th:upper} For every even $d\ge 2$ and every $n>(d-1)(\sqrt{2d}+2\sqrt{2\sqrt{2d}}+5)$, there exists a simple $d$-polytope with $n$ vertices.\qed \end{theorem} \noindent If we restrict our attention to $d$ odd, the true value for $c$ is bounded by $1\le c\le 1+\epsilon$. \begin{theorem}\label{th:odd} If $d\ge 3$ is odd, then there does not exist a simple $d$-polytope with $n= (d-1)(\left\lceil \sqrt {d-2}\right\rceil-2)+4$ vertices, but for every even integer $n>(d-1)(\sqrt{d}+2\sqrt{2\sqrt{2d}}+5)$, there exists a simple $d$-polytope with $n$ vertices.\qed \end{theorem} \noindent {\sc Proof of Theorem \ref{th:lower} } Let $d=2\da\ge 6$, so the first column of $M_d$ will be $2\da+1,2\da-1,\dots,3,1$. We will look for the lowest possible value for $f_0$ such that $f_0\equiv 4 \pmod {2\da-1}$. The entries of the first column will be the weights by which we seek to create the value of $f_0$. They are $2,0,-2,-4,\dots,-(2\da-2) \pmod {2\da-1}$. By the properties of $M$-sequences we have to take at least $k+2$ weights to obtain $f_0\equiv 4\equiv -2\da+5\pmod{2\da-1}$, where \[2+\sum_{i=0}^k -2i\le -(2\da-1)-(2\da-5), \] corresponding to the $M$-sequence $\gv=(1,1,\dots,1,1)$ with $k+2$ $1$'s. This is equivalent to \[k(k+1)\ge 4\da-4. \] Now, choose $k$ such that $k\le\sqrt{4\da-4} \] \[2\da+1+(2\da-1)\left\lceil \sqrt{4\da-4}\right\rceil- (\left\lfloor \sqrt{4\da-4}\right\rfloor^2+\left\lfloor \sqrt{4\da-4}\right\rfloor)> \] \[ (d-1)(\left\lceil \sqrt{2d-4}\right\rceil-2)+4. \] Hence, $(d-1)(\left\lceil {\sqrt{2d-4}}\right\rceil-2)+4$ is a gap. The result is easily seen to be true also for $d=4$.\qed \medskip \noindent {\sc Proof of Theorem \ref{th:upper} } Let $d=2\da\ge 4$ (the case $d=2$ is easily checked). As above the first column of $M_d$ will be $2\da+1,2\da-1,\dots,3,1$. First we note that if $n+1,n+2,\dots,n+d-1$ are all realizable then every integer larger then $n$ is realizable since we can just add $1$ to $g_1$ in the corresponding $M$-sequences. As in the previous proof we let $k_1$ be such that $k_1\le\sqrt{4\da-4}\sqrt{2(k_1-1)}. \] It is clear that the $M$-sequences $1=g_0,2=g_1=\dots=g_j$, $1=g_{j+1}=g_{j+2}=\dots=g_i$ and $0=g_{i+1}=g_{i+2}=\dots$, for $0\le j