The number of faces of a simple polytope

Abstract

Consider the question: Given integers $k<d<n$, does there exist a simple $d$-polytope with $n$ faces of dimension $k$? We show that there exist numbers $G(d,k)$ and $N(d,k)$ such that for $n>N(d,k)$ the answer is yes if and only if $n\equiv 0(\mathrm{mod}G(d,k))$. Furthermore, a formula for $G(d,k)$ is given, showing that e.g. $G(d,k)=1$ if $k\ge \lfloor \frac{d+1}{2}\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=\sqrt{2}$ if $d$ is even, and $c=1$ if $d$ is odd.