The number of k-faces of a simple d-polytope

Anders Björner^{∗}

Department of Mathematics Royal Institute of Technology S-100 44 Stockholm, SWEDEN bjorner@math.kth.se

Svante Linusson^{∗}

Department of Mathematics Stockholm University S-106 91 Stockholm, SWEDEN linusson@matematik.su.se

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 G(d, k) divides n. Furthermore, a formula for G(d, k) is given, showing that e.g. G(d, k) = 1 if k ≥ ⌊ \frac{d+1}{2} ⌋ 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 [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 [P2] showed that N(d, 0) ≤ 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.

1 Introduction

An integer n will be called (d, k)-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. [Z].

We show, see Theorem 7, that there exist numbers G(d, k) and N(d, k) such that

• if n is (d, k)-realizable then G(d, k) divides n;

• if G(d, k) divides n and n > N(d, k) then n is (d, k)-realizable.

∗Supported by EC grant CHRX-CT93-0400 and by the Mathematical Sciences Research Institute (Berkeley, CA).

The G(d, k)-divisible numbers that are not (d, k)-realizable will be called (d, k)- gaps. Thus there are only finitely many gaps for all d > k ≥ 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 dregular, 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) = \{ \begin{matrix}1, & d even \\ 2, & d odd. \end{matrix}

This result is due to Lee [Le], who initiated the study of properties of vertexcount numbers of simple polytopes. Via the regular graph property this also implies the result for edge-count numbers:

G(d, 1) = \{ \begin{matrix}\frac{d}{2}, & d even \\ d, & d odd. \end{matrix}

For 1 < k < ⌊\frac{d+1}{2}⌋ the situation gets more complicated and the answer is different for k even and k odd. For instance,

G(d, 2) = \{ \begin{matrix}2, & d ≡ 1 (mod 4) \\ 1, & otherwise. \end{matrix}

The modulus G(d, k) can get arbitrarily large in this range; for instance, G(d, k) = d − k + 1 whenever k is odd and d − k + 1 is a prime. Then, for k ≥ ⌊\frac{d+1}{2}⌋ the situation simplifies again to G(d, k) = 1. Theorem 2 gives the general formula for G(d, k).

It is also of interest to study the magnitude of the numbers N(d, k) (defined as the smallest possible ones for which the above statement is true). Again, this has been studied for the case of vertices by Prabhu [P2], who showed that N(d, 0) ≤ cd\sqrt{d}. We prove that asymptotically the true value of Prabhu’s constant is c = \sqrt{2} if d is even, and c = 1 if d is odd, see Section 5. We also give an upper bound for N(d, k) in the general case, Theorems 10 and 11, but leave open the determination of its true asymptotic growth.

2 Preliminaries

Given a d-dimensional polytope P, we will call f := (f_{0}, f_{1}, …, f_{d−1}) the fvector of P, where f_{i} is the number of faces of dimension i.

For any integers n, s ≥ 1, there is a unique way of writing

n = \binom{a_{s}}{s} + \binom{a_{s−1}}{s − 1} + ⋯ + \binom{a_{i}}{i},

so that a_{s} > a_{s−1} > ⋯ > a_{i} ≥ i ≥ 1. Then define:

∂^{s}(n) := \binom{a_{s} − 1}{s − 1} + \binom{a_{s−1} − 1}{s − 2} + ⋯ + \binom{a_{i} − 1}{i − 1}.

Also let ∂^{s}(0) := 0.

A nonnegative integer sequence (n_{0}, n_{1}, n_{2}, …) is called an M-sequence if

n_{0} = 1 and ∂^{s}(n_{s}) ≤ n_{s−1} for all s ≥ 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} ≥ n_{2} ≥ n_{3} ≥ … is an M-sequence.

An alternative definition of M-sequence, due to Macaulay and Stanley [S1], says that a sequence is a M-sequence if and only if it is the f-vector of a multicomplex. See [Li] and [Z] for examples of other interpretations of Msequences. Let ⌊x⌋ and ⌈x⌉ denote the largest integer less than or equal to x and the smallest integer larger than or equal to x, respectively.

Let δ := ⌊\frac{d}{2}⌋ and let M_{d} = (m_{ik}) be the (δ + 1) × d-matrix with entries

m_{ik} = \binom{d + 1 − i}{k + 1} − \binom{i}{k + 1}, for 0 ≤ i ≤ δ, 0 ≤ k ≤ d − 1.

For example,

M_{10} = ( \begin{matrix}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{matrix} )

Our proofs will rely on the g-theorem, conjectured by McMullen. Sufficiency was proved by Billera and Lee [BL], and necessity by Stanley [S2] and later by McMullen [M], see [Z]. We will use the following matrix reformulation of the gtheorem, given by Björner [B1, B2], see also [Z]. We have here reformulated the statement from simplicial polytopes to simple polytopes, which just correspond to reading the f-vector backwards.

Theorem 1 [The g-theorem] The matrix equation

f = g · M_{d}

gives a one-to-one correspondence between f-vectors f of simple d-polytopes and M-sequences g = (g_{0}, g_{1}, …, g_{δ}). □

3 The modulus G(d, k)

The modulus mentioned in the introduction is defined as follows

G(d, k) := gcd(m_{1,k}, m_{2,k}, …, m_{δ,k}),  (1)

the greatest common divisor for the elements in the k-th column and below the top row of the matrix M_{d}. 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.

Theorem 2 (i) If k ≥ ⌊\frac{d+1}{2}⌋, then G(d, k) = 1.

(ii) If k < ⌊\frac{d+1}{2}⌋ is even, let e be the integer such that 2^{e} ≤ k + 1 < 2^{e+1}. Then

G(d, k) = \{ \begin{matrix}2, & if d − k + 1 ≡ 0 (mod 2^{e+1}) \\ 1, & otherwise. \end{matrix}

(iii) If k < ⌊\frac{d+1}{2}⌋ is odd, let p_{1}, …, p_{t} be the primes smaller than or equal to k + 1, and let e_{i} ≥ 1 be the integers such that p_{i}^{e_{i}} ≤ k + 1 < p_{i}^{e_{i}+1}. Then

G(d, k) = \frac{d − k + 1}{gcd(d − k + 1, p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{t}^{e_{t}})}.

For the proof we will need some facts about binomial coefficients modulo powers of a prime, that will be developed in a sequence of lemmas. Binomial coefficients modulo prime powers have been much studied, see e.g. [G] and the references therein, and the following lemma (which summarizes the properties that we need) is probably known. We have however not been able to find it in the literature, so we include a proof.

Lemma 3 Let k, e ≥ 0 and let p be a prime such that p^{e} ≤ k + 1 < p^{e+1}. Then for all r ≥ 1 we have

(i) d ≡ d′ (mod p^{e+r}) implies \binom{d}{k+1} ≡ \binom{d′}{k+1} (mod p^{r});

(ii)

\binom{p^{e+r} + k − i}{k + 1} ≡ (−1)^{k+1}\binom{i}{k + 1} (mod p^{r}),

for all i = 0, 1, …, p^{e+r} + k;

(iii) the unique longest run of zeros in the period is \binom{d}{k+1} ≡_{p^{r}} 0 for all p^{e+r} ≤ d ≤ p^{e+r} + k.

Part (ii) shows that if k is odd then the period extended by k is symmetric (mod p^{r}), and if k is even then it is antisymmetric. The lemma is illustrated by the following modular Pascal triangle.

1 1 1 1 2 1 1 3 3 1 1 0 2 0 1 1 1 2 2 1 1 1 2 3 0 3 2 1 1 3 1 3 3 1 3 1 1 0 0 0 2 0 0 0 1 1 1 0 0 2 2 0 0 1 1 1 2 1 0 2 0 2 0 1 2 1 1 3 3 1 2 2 2 2 1 3 3 1 1 0 2 0 3 0 0 0 3 0 2 0 1 1 1 2 2 3 3 0 0 3 3 2 2 1 1 1 2 3 0 1 2 3 0 3 2 1 0 3 2 1 1 3 1 3 1 3 1 3 3 1 3 1 3 1 3 1 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 2 2 0 0 0 0 0 0 1 1 1 2 1 0 0 0 0 0 2 0 2 0 0 0 0 0 1 2 1 1 3 3 1 0 0 0 0 2 2 2 2 0 0 0 0 1 3 3 1 1 0 2 0 1 0 0 0 2 0 0 0 2 0 0 0 1 0 2 0 1 1 1 2 2 1 1 0 0 2 2 0 0 2 2 0 0 1 1 2 2 1 1 1 2 3 0 3 2 1 0 2 0 2 0 2 0 2 0 1 2 3 0 3 2 1 1 3 1 3 3 1 3 1 2 2 2 2 2 2 2 2 1 3 1 3 3 1 3 1 1 0 0 0 2 0 0 0 3 0 0 0 0 0 0 0 3 0 0 0 2 0 0 0 1 1 1 0 0 2 2 0 0 3 3 0 0 0 0 0 0 3 3 0 0 2 2 0 0 1 1 1 2 1 0 2 0 2 0 3 2 3 0 0 0 0 0 3 2 3 0 2 0 2 0 1 2 1 1 3 3 1 2 2 2 2 3 1 1 3 0 0 0 0 3 1 1 3 2 2 2 2 1 3 3 1 1 0 2 0 3 0 0 0 1 0 2 0 3 0 0 0 3 0 2 0 1 0 0 0 3 0 2 0 1

Pascal’s triangle (mod 4).

For each prime p define the valuation v_{p} : ZZ \ {0} → N N by v_{p}(n) = s, where p^{s} is the highest power of p that is a divisor to n. We will frequently use that

v_{p}(n + m) = v_{p}(n) if v_{p}(n) < v_{p}(m);  (2)

in particular, v_{p}(n + p^{x}) = v_{p}(n) if |n| < p^{x}.

Lemma 4 Let k, e and p be as in Lemma 3. Then

v_{p} [(k + 1)\binom{k}{j}] ≤ e, for all 0 ≤ j ≤ k.

Proof The proof hinges on the following fact: Among all products of x ≤ p^{e}(p − 1) consecutive integers in the interval 1, 2, …, p^{e+1} − 1 the maximum valuation is attained by the string that starts with p^{e}. To show this, assume that r, r+1, …, r+x−1 is such a string of integers. If r > p^{e}, say ap^{e} < r ≤ (a+1)p^{e}, then the string beginning with r − ap^{e} has the same valuation. Thus we may assume that r ≤ p^{e}.

If r < p^{e}, let s be the least number such that r < s ≤ p^{e} and v_{p}(r) < v_{p}(s). Then it is easy to see that v_{p}(r(r + 1) ⋯ (r + x − 1)) ≤ v_{p}(s(s + 1) ⋯ (s + x − 1), and the claim follows.

We may assume that j ≤ \frac{k}{2} . Then j+1 ≤ p^{e}(p−1), and what was just shown implies that v_{p}((k − j + 1)(k − j + 2) ⋯ (k + 1)) ≤ v_{p}(p^{e}(p^{e} + 1) ⋯ (p^{e} + j)) = e + v_{p}(j!), which is equivalent to the stated formula. □

Proof of Lemma 3 We know from Pascal’s triangle that \binom{d}{k+1} (mod p^{r}) is completely determined by the values of \binom{j}{0} = 1, j ≥ 0, and \binom{d′+i}{i} (mod p^{r}) for any d′ ≥ 0 and all i = 1, …, k + 1. Therefore it suffices to show that

\binom{p^{e+r} − 1 + i}{i} ≡_{p^{r}} 0,  (3)

for all i = 1, …, p^{e+1} − 1, to establish the first part of the lemma. We have that v_{p}(p^{e+r} + s) = v_{p}(s) for all s = 1, …, p^{e+r} − 1. So the expansion of the binomial coefficient

\binom{p^{e+r} − 1 + i}{i} = \frac{(p^{e+r} + i − 1)(p^{e+r} + i − 2) ⋯ p^{e+r}}{i(i − 1)(i − 2) ⋯ 2 · 1}

gives v_{p}(\binom{p^{e+r}−1+i}{i}) = e + r − v_{p}(i) ≥ r, if i < p^{e+1}, which proves (3).

The second part of the lemma is obvious when 0 ≤ i ≤ k, since both sides are zero (for the left-hand side this follows from (i)). Therefore, assume that k < i < p^{e+r}. For each j ≠ 0 write j = p^{min{v_{p}(j),e}}q_{j}. Then, for 0 < j < p^{e+r}:

q_{p^{e+r}−j} ≡_{p^{r}} q_{−j} = −q_{j}.  (4)

We have the equality

\binom{i}{k + 1}\frac{(k + 1)!}{p^{v_{p}((k+1)!)}} = \frac{i(i − 1) ⋯ (i − k)}{p^{v_{p}((k+1)!)}} =

p^{∑_{j=0}^{k} min{v_{p}(i−j),e}−v_{p}((k+1)!)} ∏_{j=0}^{k} q_{i−j} = p^{α} ∏_{j=0}^{k} q_{i−j},

and similarly

\binom{p^{e+r} + k − i}{k + 1}\frac{(k + 1)!}{p^{v_{p}((k+1)!)}} = \frac{(p^{e+r} − i)(p^{e+r} − i + 1) ⋯ (p^{e+r} − i + k)}{p^{v_{p}((k+1)!)}} =

p^{∑_{j=0}^{k} min{v_{p}(p^{e+r}−(i−j)),e}−v_{p}((k+1)!)} ∏_{j=0}^{k} q_{p^{e+r}−(i−j)} = p^{β} ∏_{j=0}^{k} q_{p^{e+r}−(i−j)}.

We claim that

β = α ≥ 0.

The equality follows from (2), and the inequality will soon be proved. The two identities therefore give, using (4):

\binom{i}{k + 1}\frac{(k + 1)!}{p^{v_{p}((k+1)!)}} ≡_{p^{r}} (−1)^{k+1}\binom{p^{e+r} + k − i}{k + 1}\frac{(k + 1)!}{p^{v_{p}((k+1)!)}} .

Since \frac{(k+1)!}{p^{vp((k+1)!)}} is invertible in ZZ_{p^{r}} this implies (ii).

It remains to show that α ≥ 0. If v_{p}(i − j) ≤ e for all j = 0, …, k, then α = v_{p}(\binom{i}{k+1}) ≥ 0. If not, then since k + 1 < p^{e+1} there is exactly one s, with i − k ≤ s ≤ i, such that v_{p}(s) > e. In that case we have

α + v_{p}((k + 1)!) = v_{p}((i − k) ⋯ s ⋯ i) − v_{p}(s) + e =

v_{p}((i − k) ⋯ (s − 1)) + v_{p}((s + 1) ⋯ i) + e = v_{p}((s − (i − k))!) + v_{p}((i − s)!) + e,

where the last equality uses (2) twice. Thus, using Lemma 4,

α = −v_{p}((k − (i − s) + 1)(k − (i − s) + 2) ⋯ (k + 1)) + v_{p}((i − s)!) + e =

−v_{p} ((k + 1)\binom{k}{i − s}) + e ≥ 0.

To prove (iii) assume that \binom{d+i}{k+1} ≡_{p^{r}} 0, for some d ≥ k + 1 and all i = 0, …, k. Then \binom{d}{j} ≡_{p^{r}} 0, for j = 1, …, k + 1. Especially, \binom{d}{p^{s}} ≡_{p^{r}} 0 for 0 ≤ s ≤ e, which gives that v_{p}(\binom{d}{p^{s}}) ≥ r. In particular, v_{p}(d) ≥ r. We will now show that v_{p}(d) ≥ r + s for all 0 ≤ s ≤ e, by induction on s. Assume that v_{p}(d) ≥ r + s − 1. Then r ≤ v_{p}(\binom{d}{p^{s}}) = v_{p}(d(d − 1) ⋯ (d − (p^{s} − 1))) − v_{p}(1 · 2 ⋯ (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 \binom{d}{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 \binom{i}{k+1}. This proves the lemma. □

We can now proceed toward the proof of Theorem 2.

Lemma 5 For each k < ⌊\frac{d+1}{2}⌋, G(d, k) is a divisor of \frac{d−k+1}{gcd(d−k+1,p_{1}^{e_{1}} p_{2}^{e_{2}} ···p_{t}^{e_{t}})},

where p_{1}, …, p_{t} are the primes ≤ k + 1 and p_{i}^{e_{i}} ≤ k + 1 < p_{i}^{e_{i}+1}.

Proof Take a prime p dividing G(d, k) and let x := v_{p}(G(d, k)) ≥ 1. Write k + 1 in base p, k + 1 = k_{0} + k_{1}p + ⋯ + k_{e}p^{e}, where 0 ≤ k_{i} < p and k_{e} ≠ 0. Notice that

v_{p}(\frac{d − k + 1}{gcd(d − k + 1, p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{t}^{e_{t}})}) = \begin{cases}v_{p}(d − k + 1) − e & if v_{p}(d − k + 1) ≥ e, \\ 0 & otherwise, \end{cases}

so it will suffice to show that v_{p}(d − k + 1) − e ≥ x in the first case and obtain a contradiction in the second.

Since p^{x}|G(d, k) we get that \binom{d+1−i}{k+1} ≡_{p^{x}} \binom{i}{k+1}, for all i = 1, …, δ. Especially we must have \binom{d+1−i}{k+1} ≡_{p^{x}} 0, for i = 1, …, k and \binom{d−k}{k+1} ≡_{p^{x}} 1. From

(d − 2k)\binom{d + 1 − k}{k + 1} = \binom{d − k}{k + 1}(d − k + 1),

we get v_{p}(d − k + 1) − v_{p}(d − 2k) = v_{p}(\binom{d+1−k}{k+1}) ≥ x ≥ 1. Hence by (2), v_{p}(k + 1) = v_{p}(d − k + 1 − (d − 2k)) = v_{p}(d − 2k) < v_{p}(d − k + 1).

There are now two cases: First assume that v_{p}(d − k + 1) ≥ e. If k + 1 = k_{e}p^{e} we are done, since we have shown that v_{p}(d − k + 1) − v_{p}(k + 1) ≥ x. Assume that k + 1 > k_{e}p^{e}. From d − k + 1 ≥ k + 1 > k_{e}p^{e} we conclude that v_{p}(d − k + 1 − k_{e}p^{e}) ≥ e, which implies v_{p}(d − k + 1 − k_{e}p^{e} − i) = v_{p}(i), for all i = 1, …, k + 1 − k_{e}p^{e} < p^{e}. This in turn implies that

v_{p} (\frac{(d − k − k_{e}p^{e})!}{(d − 2k)!}) = v_{p}((k − k_{e}p^{e})!) = v_{p} (\frac{(d + 1 − k_{e}p^{e})!}{(d + 1 − k)!}) .

Using the equality

\frac{(d − k − k_{e}p^{e})!}{(d − 2k)!}\binom{d + 1 − k_{e}p^{e}}{k + 1} = \binom{d + 1 − k}{k + 1}\frac{(d + 1 − k_{e}p^{e})!}{(d + 1 − k)!},

we get that v_{p}(\binom{d+1−k_{e}p^{e}}{k+1}) = v_{p}(\binom{d+1−k}{k+1}). This together with the identity

(d − k + 1 − k_{e}p^{e})\binom{d + 2 − k_{e}p^{e}}{k + 1} = \binom{d + 1 − k_{e}p^{e}}{k + 1}(d + 2 − k_{e}p^{e})

gives

x ≤ v_{p}(m_{k_{e}p^{e}−1,k}) = v_{p} (\binom{d + 2 − k_{e}p^{e}}{k + 1}) ≤

v_{p} (\binom{d + 1 − k_{e}p^{e}}{k + 1}) − e + v_{p}(d + 2 − k_{e}p^{e}) =

v_{p} (\binom{d − k + 1}{k + 1}) − e + v_{p}(k + 1 − k_{e}p^{e}) = v_{p}(d − k + 1) − e.

Here the last equality comes from v_{p}(k + 1 − k_{e}p^{e}) = v_{p}(k + 1) = v_{p}(d − 2k) and v_{p}(\binom{d−k+1}{k+1}) = v_{p}(d − k + 1) − v_{p}(d − 2k), established above.

The second case is if a := v_{p}(d − k + 1) < e. The same argument can be applied again; however, now replacing k_{e}p^{e} everywhere by k_{a}p^{a} + ⋯ + k_{e}p^{e} and replacing e by a. We then get x ≤ v_{p}(d − k + 1) − a = 0, a contradiction. □

Lemma 6 G(d, k) is a divisor to m_{0,k} = \binom{d+1}{k+1}.

Proof If for a prime p we have that p^{r} divides G(d, k) and p^{e} ≤ k + 1 < p^{e+1}, then Lemma 5 implies that p^{r+e} divides d−k+1. Hence v_{p}(\binom{d+1}{k+1}) = v_{p}(\binom{d+1}{k})+ v_{p}(d − k + 1) − v_{p}(k + 1) ≥ r. □

Proof of Theorem 2. The first statement follows from the fact that m_{d−k,k} = 1 for k ≥ ⌊\frac{d+1}{2}⌋ .

Let k < ⌊\frac{d+1}{2}⌋. We have from the definition of m_{i,k} that for every prime p and every r ≥ 1:

p^{r}|G(d, k) ⟺ \binom{d + 1 − i}{k + 1} ≡_{p^{r}} \binom{i}{k + 1}, for i = 0, 1, …, ⌊\frac{d+1}{2}⌋ . (5)

Actually, the definition supports this only for i = 1, …, δ = ⌊\frac{d}{2}⌋ on the right hand side, but i = 0 can be added because of Lemma 6 and i = ⌊\frac{d+1}{2}⌋ (for d odd) gives a trivially true identity.

Case 1: k even. Assume that G(d, k) ≠ 1, and that p^{r}|G(d, k). Since by Lemma 3 there is a unique longest run of k + 1 zeros in the period of \binom{i}{k+1} (mod p^{e+r}) we get from (5) that d − k + 1 ≡_{p^{e+r}} 0. Therefore, Lemma 3 and (5) give

\binom{k + 1}{k + 1} ≡_{p^{r}} \binom{d − k}{k + 1} ≡_{p^{r}} \binom{p^{e+r} − 1}{k + 1} ≡_{p^{r}} −\binom{k + 1}{k + 1},

which implies p = 2 and r = 1. Hence, G(d, k) = 2, and this happens only if d − k + 1 ≡_{2^{e+1}} 0. On the other hand, if d − k + 1 ≡_{2^{e+1}} 0 then 2|G(d, k) can be concluded from Lemma 3 and (5).

Case 2: k odd. Let p^{r} be a divisor of \frac{d−k+1}{gcd(d−k+1,p_{1}^{e_{1}} p_{2}^{e_{2}} ···p_{t}^{e_{t}})}. By Lemma 5 it suffices to show that p^{r}|G(d, k). The assumption implies that p^{r+e} divides d − k + 1, where as usual e is defined by p^{e} ≤ k + 1 < p^{e+1}. Hence by Lemma 3

\binom{d + 1 − i}{k + 1} ≡_{p^{r}} \binom{i}{k + 1}, for all i = 0, …, d + 1,

which via (5) shows that p^{r}|G(d, k).

This finishes the proof of the theorem. □

Example We want to calculate G(116, 9). Since k = 9 is odd we calculate the greatest common divisor of 116 − 9 + 1 = 108 and 2^{3} · 3^{2} · 5 · 7 which is 36. We get G(116, 9) = 118/36 = 3. □

4 Periodicity of (d, k)-realizable numbers

We will now show the general theorem about the ultimately stable periodic distribution of the (d, k)-realizable numbers.

Theorem 7 Fix 0 ≤ k < d, and let G(d, k) be the number defined in equation (1). Then there exists an integer N such that for all n > N:

n is the number of k-faces of a simple d-polytope

⟺

n ≡ 0 (mod G(d, k))

Proof We will prove the theorem with the last statement replaced by n ≡ m_{0,k} (mod G(d, k)). Lemma 6 shows that m_{0,k} is divisible by G(d, k), so this reformulation is equivalent. ⟹ This direction is clear from Theorem 1. ⟸ Write

G(d, k) = ∑_{i=1}^{δ} λ_{i}m_{i,k}, λ_{i} ∈ ZZ.

Suppose m_{1,k} = C · G(d, k). Define

g_{δ} := \{ \begin{matrix}(C − 1)|λ_{δ}|, & if λ_{δ} < 0 \\ 0, & otherwise; \end{matrix}

and recursively

g_{i} := g_{i+1} + (C − 1)(|λ_{i}| + |λ_{i+1}|), 0 < i < δ.

Let N := m_{0,k} + ∑_{i=1}^{δ} g_{i}m_{i,k}, and let g_{i}^{(p)} = g_{i} + pλ_{i}, for p = 0, 1, …

Then g^{(p,q)} = (1, g_{1}^{(p)} + q, g_{2}^{(p)}, …, g_{δ}^{(p)}) is nonnegative and decreasing after the first entry for all q ≥ 0 and all 0 ≤ p < C, and hence is an M-sequence. The f_{k} values corresponding to these g-vectors are

f_{k}^{(p,q)} = N + qCG(d, k) + pG(d, k).

It is clear from the construction that all numbers N + j · G(d, k), j = 0, 1, … are of the form f_{k}^{(p,q)} for suitable q ≥ 0 and 0 ≤ p < C. □

Corollary 8 If the m_{i,k} are relatively prime, then all numbers from some point on are (d, k)-realizable. Furthermore, Theorem 2 shows that this happens precisely in the following cases:

(i) if k ≥ ⌊\frac{d+1}{2}⌋;

(ii) if k < ⌊\frac{d+1}{2}⌋ is even, unless d − k + 1 ≡ 0 (mod 2^{e+1}); (iii) if k < ⌊\frac{d+1}{2}⌋ is odd, unless d − k + 1 fails to divide p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{t}^{e_{t}}. □

Now, define N(d, k) to be the least number N for which Theorem 7 is true. Note that N(d, d − 1) = d, so in what follows we may assume that k < d − 1.

What can be said about the magnitude of N(d, k)? We will here give a general upper bound, and then we will determine the exact asymptotic growth for the special case N(d, 0) in the following section.

Define

L(d, k) := min max_{i=1}^{δ} |λ_{i}|,

with the minimum taken over all ways to represent G(d, k) on the form

G(d, k) = ∑_{i=1}^{δ} λ_{i}m_{i,k}, λ_{i} ∈ ZZ.

Lemma 9 For all 0 ≤ k ≤ d − 2, we have L(d, k) < m_{1,k}.

Proof Assume G(d, k) = ∑_{i=1}^{δ} λ_{i}m_{i,k}, with |λ_{s}| ≥ m_{1,k} and m_{s,k} ≠ 0. By symmetry we may assume that λ_{s} is positive, that is λ_{s} ≥ m_{1,k}. Since G(d, k) < m_{1,k}m_{s,k}, there has to be a t such that λ_{t} < 0 and m_{t,k} ≠ 0. Let

λ′_{i} = \begin{cases}λ_{s} − m_{t,k} & if i = s, \\ λ_{t} + m_{s,k} & if i = t, \\ λ_{i} & otherwise. \end{cases}

We get G(d, k) = ∑_{i=1}^{δ} λ′_{i}m_{i,k}. Since |λ′_{s}| < |λ_{s}|, |λ′_{t}| < |λ_{t}| or else |λ′_{t}| < m_{s,k}, and all other |λ′_{i}| are unchanged, we can continue this process until |λ_{i}| < m_{1,k}, for all i. □

Theorem 10 N(d, k) < \frac{1}{2}d^{2}\binom{d}{k+1}^{3}

Proof Referring to the proof of Theorem 7, with an optimal choice of the λ_{i}-s, we have

N(d, k) ≤ ∑_{i=0}^{δ} g_{i}m_{i,k} ≤ \binom{d + 1}{k + 1} + L(d, k)(C − 1) ∑_{i=1}^{δ}(2δ + 1 − 2i)\binom{d + 1 − i}{k + 1}

≤ \binom{d + 1}{k + 1} + L(d, k)(C − 1)δ(2δ − 1)\binom{d}{k + 1} < 2L(d, k)δ^{2}\binom{d}{k + 1}^{2}.

□

For example, let k = 0. The general bound specializes to N(d, 0) ≤ \frac{1}{2}d^{5}. This should be compared to the true asymptotic value N(d, 0) ∼ cd^{3/2}, which will be proved in the next section.

For k ≥ ⌊\frac{d+1}{2}⌋ we can improve on the general bound significantly.

Theorem 11 Suppose k ≥ ⌊\frac{d+1}{2}⌋. Then N(d, k) < \binom{d+1}{d−k}(d−k)(k+1)(d+1)/2.

Since G(d, k) = 1 for such k this implies that for every n ≥ \binom{d+1}{d−k}(d − k)(k + 1)(d + 1)/2 there is a simple d-polytope with n faces of dimension k.

To prove this we need a more technical construction than before. First we extend the definition of ∂^{s}. Define for p ≤ s:

∂_{p}^{s}(n) := \binom{a_{s} − p}{s − p} + \binom{a_{s−1} − p}{s − 1 − p} + ⋯ + \binom{a_{i} − p}{i − p},

where n is written in the unique expansion

n = \binom{a_{s}}{s} + \binom{a_{s−1}}{s − 1} + ⋯ + \binom{a_{i}}{i},

as in Section 2. Also let ∂_{p}^{s}(0) := 0. We will allow p to be negative, which corresponds to the natural “inverse” of ∂_{p}^{s} for positive p. Thus, for p > 0, ∂_{−p}^{s}(n) is the greatest number such that ∂_{p}^{s}(∂_{−p}^{s}(n)) = n. We will continue to write just ∂^{s} for ∂_{1}^{s}.

Now, fix d and k ≥ ⌊\frac{d+1}{2}⌋. Define a vector g := (g_{0}, g_{1}, …, g_{d−k}) inductively as follows.

• Let g_{d−k} := 0.

• Assume we have defined g_{d−k}, g_{d−k−1}, …, g_{i}, for some 0 < i ≤ d − k. Let

g_{i−1} := ∂^{i}(x_{i}), where x_{i} is the smallest integer such that x_{i} ≥ g_{i} and

∑_{s=i}^{d−k} (∂_{i−s}^{i}(x_{i}) − g_{s}) m_{s,k} ≥ m_{i−1,k} − 1.  (6)

This is an M-sequence by construction.

Lemma 12 Given the g-vector above, define N := ∑_{i=0}^{d−k} g_{i}m_{i,k}. Then there are no (d, k)-gaps larger than or equal to N.

Proof Adding any positive integer to g_{1} in an M-sequence gives another Msequence. Thus we only have to prove that it is possible to form all the m_{1,k} − 1 integers following N with legal g-vectors. This will imply the lemma.

We will think of the elements in column k of M_{d} as weights which we combine to get the correct total weight.

Consider first the choice of g_{d−k−1} := ∂^{d−k}(x_{d−k}), where x_{d−k} = m_{d−k−1,k}− 1. All the vectors (g_{0}, g_{1}, …, g_{d−k−1}, i), i = 0, … m_{d−k−1,k}−1 are M-sequences, producing N, N + 1, …, N + m_{d−k−1,k} − 1 k-faces respectively. We here use the fact that m_{d−k,k} = 1. Similarly (g_{0}, g_{1}, …, g_{d−k−1} + j, i), for fixed j and i = 0, … m_{d−k−1,k} − 1 gives N + jm_{d−k−1,k}, N + jm_{d−k−1,k} + 1, …, N + (j + 1)m_{d−k−1,k} − 1 k-faces. The definition of g_{d−k−2} allows us to have j sufficiently large to get all the numbers at least up to and including N + m_{d−k−2,k} − 1.

Assuming inductively that we can form the sequence N, N +1, …, N +m_{i,k}− 1 by increasing only coordinates i + 1, …, d − k, the definition of g gives that we can form all the numbers N, N + 1, …, N + m_{i−1,k} − 1 by increasing only coordinates i, …, d − k of g. This proves the lemma □

Example Take d = 10 and k = 6. We see from the matrix M_{10}, displayed in Section 2, that the weights are 330, 120, 36, 8 and 1. We get g = (1, 4, 6, 6, 0) which gives N(10, 6) < 1074, showing that every n ≥ 1074 is (10, 6)-realizable.

Proof of Theorem 11 First we show that g_{i} ≤ (d − k − i)(k + 1) by reverse induction. It is trivially true for g_{d−k}. Assume it is true for g_{i}. Since g_{i−1} = ∂^{i}(x_{i}) ≤ x_{i}, it suffices to bound x_{i}. The inequality (6) is true if (x_{i} − g_{i})m_{i,k} ≥ m_{i−1,k} − 1. Since x_{i} is chosen to be minimal we get that

x_{i} ≤ g_{i} + ⌈\frac{m_{i−1,k} − 1}{m_{i,k}}⌉ = g_{i} + ⌈\frac{\binom{d+2−i}{k+1} − 1}{\binom{d+1−i}{k+1}}⌉ ≤

≤ g_{i} + ⌈\frac{d + 2 − i}{d + 1 − i − k} − \frac{1}{\binom{d+1−i}{k+1}}⌉ ≤ g_{i} + k + 1 ≤ (k + 1)(d − k − i + 1).

Now,

N ≤ \binom{d + 1}{k + 1} + (k + 1) ∑_{i=1}^{d−k}(d − k − i)\binom{d + 1 − i}{k + 1} ≤

\binom{d + 1}{k + 1} + (k + 1)\binom{d}{k + 1}\binom{d − k}{2} ≤ \binom{d + 1}{k + 1} (1 + \frac{(k + 1)(d − k − 1)(d + 1)}{2}) .

This proves the theorem. □

Note that m_{0,k} + 1 = \binom{d+1}{d−k} + 1 is never (d, k)- realizable for k < d − 1. This gives a trivial lower bound for N(d, k) to be compared with the upper bounds in Theorems 10 and 11.

5 The case of vertices

The only case of (d, k)-realizability that seems to have been previously studied is for k = 0, i.e., the number of vertices. We will make a more exact analysis of that case.

Lee showed in [Le, Corollary 4.4.15] that for each dimension d all sufficiently large numbers are (d, 0)-realizable (with parity restrictions, see the Introduction). Prabhu [P1, P2] strengthened the result and proved that there exists a constant c such that every n > cd\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 [Le] where Lee lists all (d, 0)-gaps for d ≤ 9.

We will sharpen Prabhu’s result in both directions and prove that one can use c = \sqrt{2} + ϵ as constant in his theorem for any ϵ > 0 and sufficiently large even d (depending on ϵ). However, the statement is not true for c < \sqrt{2}.

Theorem 13 If d ≥ 4 is even, then there does not exist a simple d-polytope with n = (d − 1)(⌈\sqrt{2d − 4}⌉ − 2) + 4 vertices. □

Theorem 14 For every even d ≥ 2 and every n > (d−1)(\sqrt{2d}+2\sqrt{2\sqrt{2d}}+5), there exists a simple d-polytope with n vertices. □

Similarly, if we restrict our attention to d odd the true value for c is asymptotically equal to 1.

Theorem 15 If d ≥ 3 is odd, then there does not exist a simple d-polytope with n = (d − 1)(⌈\sqrt{d − 2}⌉ − 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. □

Proof of Theorem 13 Let d = 2δ ≥ 6, so the first column of M_{d} will be 2δ + 1, 2δ − 1, …, 3, 1. We will look for the lowest possible value for f_{0} such that f_{0} ≡ 4 (mod 2δ − 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, …, −(2δ − 2) (mod 2δ − 1). By the properties of M-sequences we have to take at least k + 2 weights to obtain f_{0} ≡ 4 ≡ −2δ + 5 (mod 2δ − 1), where

2 + ∑_{i=0}^{k} −2i ≤ −(2δ − 1) − (2δ − 5),

corresponding to the M-sequence g = (1, 1, …, 1, 1) with k + 2 1’s. This is equivalent to

k(k + 1) ≥ 4δ − 4.

Now, choose k such that k ≤ \sqrt{4δ − 4} < k + 1. We then get that

f_{0} ≥ 2δ + 1 + ∑_{i=0}^{k} 2δ − 1 − 2i = 2δ + 1 + (2δ − k − 1)(k + 1) >

2δ + 1 + (2δ − 1) ⌈\sqrt{4δ − 4}⌉ − (⌊\sqrt{4δ − 4}⌋^{2} + ⌊\sqrt{4δ − 4}⌋) >

(d − 1)(⌈\sqrt{2d − 4}⌉ − 2) + 4.

Hence, (d − 1)(⌈\sqrt{2d − 4}⌉ − 2) + 4 is a gap.

The result is easily seen to be true also for d = 4. □

Proof of Theorem 14 Let d = 2δ ≥ 4 (the case d = 2 is easily checked). As above the first column of M_{d} will be 2δ + 1, 2δ − 1, …, 3, 1. First we note that if n + 1, n + 2, …, 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} ≤ \sqrt{4δ − 4} < k_{1} + 1. We consider the M-sequences 1 = g_{0} = g_{1} = ⋯ = g_{i} and 0 = g_{i+1} = g_{i+2} = …, for 0 ≤ i ≤ k_{1} + 1. The corresponding values for f_{0} constitute one sequence of odd residues and one sequence of even residues modulo d − 1, with no distance being larger than 2(k_{1} − 1). Now we choose k_{2} such that

∑_{i=0}^{k_{2}} −2i ≤ −(2k_{1} − 1) ⟺ k_{2} + 1 > \sqrt{2(k_{1} − 1)}.

It is clear that the M-sequences 1 = g_{0}, 2 = g_{1} = ⋯ = g_{j}, 1 = g_{j+1} = g_{j+2} = ⋯ = g_{i} and 0 = g_{i+1} = g_{i+2} = …, for 0 ≤ j < i ≤ k_{1} + 1 and j ≤ k_{2}, give values for f_{0} (mod d − 1) where no residue is more than 2(k_{2} − 1) away from another residue of the same parity. Continuing this process, we choose integers k_{1}, k_{2}, …, k_{s}, as small as possible such that \sqrt{2(k_{i−1} − 1)} < k_{i} + 1, for 2 ≤ i ≤ s. We stop when we have reached k_{s} = 1. Hence, every possible value for f_{0} (mod d − 1) can be obtained with an M-sequence that has coordinates satisfying g_{i} ≤ j, whenever k_{j+1} + 1 < i.

So if f_{0} is a gap then we must have

f_{0} < 2δ + 1 + ∑_{i=0}^{k_{1}}(2δ − 1 − 2i) + ∑_{i=0}^{k_{2}}(2δ − 1 − 2i) + ⋯ + ∑_{i=0}^{k_{s}}(2δ − 1 − 2i) <

2δ + 1 + (k_{1} + 1 + k_{2} + 1 + ⋯ + k_{s} + 1)(2δ − 1) < [by induction]

2δ + 1 + (k_{1} + 1 + 2(k_{2} + 1))(2δ − 1) < (d − 1)(\sqrt{2d − 4} + 2\sqrt{2\sqrt{2d − 4} − 2} + 5).

This estimate suffices to show the theorem. □

Proof of Theorem 15 The proof can be carried out in the same manner as the two previous proofs. □

References

[BL] L.J. Billera and C.W. Lee, A proof of the sufficiency of McMullen’s conditions for f-vectors of simplicial convex polytopes, J. Combinatorial Theory Ser. A 31 (1981), 237–255.

[B1] A. Björner, Face numbers of complexes and polytopes, in “Proceedings of the International Congress of Mathematicians, Berkeley, 1986”, Amer. Math. Soc., 1987, pp. 1408-1418.

[B2] A. Björner, Partial unimodality for f-vectors of simplicial polytopes and spheres, in “Jerusalem Combinatorics ’93” (eds. H. Barcelo and G. Kalai), Contemporary Math. Series, Vol. 178, Amer. Math. Soc., 1994, pp. 45–54.

[G] A. Granville, Binomial coefficients modulo prime powers, preprint, http://www.math.uga.edu/˜ andrew/Binomial/index.html.

[Le] C. W. Lee, Counting the faces of simplicial convex polytopes, Ph.D. thesis, Cornell University, 1981.

[Li] S. Linusson, The number of M-sequences and f-vectors, in Ph.D. thesis “Studies in algebraic and topological combinatorics”, KTH, Sweden, 1995, pp. 117–141.

[M] P. McMullen, On simple polytopes, Inventiones Math. 113 (1993), 419– 444.

[P1] N. Prabhu, Hamiltonian Simple Polytopes, Discrete&Computational Geometry 14 (1995), 301–304 .

[P2] N. Prabhu, Facet-numbers of simplicial polytopes, Chapter 7 in Ph.D. thesis “Properties of Convex Polytopes”, New York University, 1991.

[S1] R. P. Stanley, Hilbert functions for graded algebras, Advances in Math. 28 (1978), 57–83.

[S2] R.P. Stanley, The number of faces of simplicial convex polytopes, Advances in Math. 35 (1980), 236–238.

[Z] G. M. Ziegler, Lectures on Polytopes, GTM-series, Springer-Verlag, 1995.