Unimodular Covers of Multiples of Polytopes

Winfried Bruns and Joseph Gubeladze^{1}

Received: November 11, 2001 Revised: December 4, 2002

Communicated by Günter M. Ziegler

Abstract. Let P be a d-dimensional lattice polytope. We show that there exists a natural number c_{d}, only depending on d, such that the multiples cP have a unimodular cover for every natural number c ≥ c_{d}. Actually, an explicit upper bound for c_{d} is provided, together with an analogous result for unimodular covers of rational cones.

2000 Mathematics Subject Classification: Primary 52B20, 52C07, Secondary 11H06 Keywords and Phrases: lattice polytope, rational cone, unimodular covering

1. Statement of results

All polytopes and cones considered in this paper are assumed to be convex. A polytope P ⊂ ℝ^{d} is called a lattice polytope, or integral polytope, if its vertices belong to the standard lattice ℤ^{d}. For a (not necessarily integral) polytope P ⊂ ℝ^{d} and a real number c ≥ 0 we let cP denote the image of P under the dilatation with factor c and center at the origin O ∈ ℝ^{d}. A polytope of dimension e is called an e-polytope. A simplex Δ is a polytope whose vertices v_{0}, …, v_{e} are affinely independent (so that e = dim Δ). The multiplicity μ(Δ) of a lattice simplex is the index of the subgroup U generated by the vectors v_{1} − v_{0}, …, v_{e} − v_{0} in the smallest direct summand of ℤ^{d} containing U, or, in other words, the order of the torsion subgroup of ℤ^{d}/U. A simplex of multiplicity 1 is called unimodular. If Δ ⊂ ℝ^{d} has the full dimension d, then μ(Δ) = d! vol(Δ), where vol is the Euclidean volume. The union of all unimodular d-simplices inside a d-polytope P is denoted by UC(P). In this paper we investigate for which multiples cP of a lattice d-polytope one can guarantee that cP = UC(cP). To this end we let 𝔠_{d}^{pol} denote the infimum of the natural numbers c such that c′P = UC(c′P) for all lattice d-polytopes P and all natural numbers c′ ≥ c. A priori, it is not excluded that 𝔠_{d}^{pol} = ∞ and, to the best of our knowledge, it has not been known up till now whether 𝔠_{d}^{pol} is finite except for the cases d = 1, 2, 3: 𝔠_{1}^{pol} = 𝔠_{2}^{pol} = 1 and 𝔠_{3}^{pol} = 2, where the first equation is trivial, the second is a crucial step in the derivation of Pick’s theorem, and a proof of the third can be found in Kantor and Sarkaria [KS]. Previous results in this direction were obtained by Lagarias and Ziegler (Berkeley 1997, unpublished). The main result of this paper is the following upper bound, positively answering Problem 4 in [BGT2]:

1The second author was supported by the Deutsche Forschungsgemeinschaft.

Theorem 1.1. For all natural numbers d > 1 one has

𝔠_{d}^{pol} ≤ O(d^{5})(\frac{3}{2})^{⌈\sqrt{d−1}⌉(d−1)}.

Theorem 1.1 is proved by passage to cones, for which we establish a similar result on covers by unimodular subcones (Theorem 1.3 below). This result, while interesting of its own, implies Theorem 1.1 and has the advantage of being amenable to a proof by induction on d. We now explain some notation and terminology. The convex hull of a set X ⊂ ℝ^{d} is denoted by conv(X), and Aff(X) is its affine hull. Moreover, ℝ_{+} = {x ∈ ℝ : x ≥ 0} and ℤ_{+} = ℤ ∩ ℝ_{+}. A lattice simplex is called empty if its vertices are the only lattice points in it. Every unimodular simplex is empty, but the opposite implication is false in dimensions ≥ 3. (In dimension 2 empty simplices are unimodular.) A cone (without further predicates) is a subset of ℝ^{d} that is closed under linear combinations with coefficients in ℝ_{+}. All cones considered in this paper are assumed to be polyhedral, rational and pointed (i. e. not to contain an affine line); in particular they are generated by finitely many rational vectors. For such a cone C the semigroup C ∩ ℤ^{d} has a unique finite minimal set of generators, called the Hilbert basis and denoted by Hilb(C). The extreme (integral) generators of a rational cone C ⊂ ℝ^{d} are, by definition, the generators of the semigroups l ∩ ℤ^{d} ≈ ℤ_{+} where l runs through the edges of C. The extreme integral generators of C are members of Hilb(C). We define Δ_{C} to be the convex hull of O and the extreme integral generators of C. A cone C is simplicial if it has a linearly independent system of generators. Thus C is simplicial if and only if Δ_{C} is a simplex. We say that C is empty simplicial if Δ_{C} is an empty simplex. The multiplicity of a simplicial cone is μ(Δ_{C}). If Δ is a lattice simplex with vertex O, then the multiplicity of the cone ℝ_{+}Δ divides μ(Δ). This follows easily from the fact that each non-zero vertex of Δ is an integral multiple of an extreme integral generator of ℝ_{+}Δ. A unimodular cone C ⊂ ℝ^{d} is a rational simplicial cone for which Δ_{C} is a unimodular simplex. Equivalently we could require that C is simplicial and its extreme integral generators generate a direct summand of ℤ^{d}. A unimodular cover of an arbitrary rational cone C is a finite system of unimodular cones whose union is C. A unimodular triangulation of a cone is defined in the usual way – it is a unimodular cover whose member cones coincide along faces. In addition to the cones C with apex in the origin O, as just introduced, we will sometimes have to deal with sets of the form v + C where v ∈ ℝ^{d}. We call v + C a cone with apex v. We define 𝔠_{d}^{cone} to be the infimum of all natural numbers c such that every rational d-dimensional cone C ⊂ ℝ^{d} admits a unimodular cover C = ⋃_{j=1}^{k} C_{j} for which

Hilb(C_{j}) ⊂ cΔ_{C} j ∈ [1, k].

Remark 1.2. We will often use that a cone C can be triangulated into empty simplicial cones C′ such that Δ_{C′} ⊂ Δ_{C}. In fact, one first triangulates C into simplicial cones generated by extreme generators of C. After this step one can assume that C is simplicial with extreme generators v_{1}, …, v_{d}. If Δ_{C} is not empty, then we use stellar subdivision along a ray through some v ∈ Δ_{C} ∩ ℤ^{d}, v ≠ 0, v_{1}, …, v_{d}, and for each of the resulting cones C′ the simplex Δ_{C′} has a smaller number of integral vectors than Δ_{C}. In proving a bound on 𝔠_{d}^{cone} it is therefore enough to consider empty simplicial cones. Similarly one triangulates every lattice polytope into empty simplices.

Results on 𝔠_{d}^{cone} seem to be known only in dimensions ≤ 3. Since the empty simplicial cones in dimension 2 are exactly the unimodular 2-cones (by a well known description of Hilbert bases in dimension 2, see Remark 4.2) we have 𝔠_{2}^{cone} = 1. Moreover, it follows from a theorem of Sebő [S1] that 𝔠_{3}^{cone} = 2. In fact Sebő has shown that a 3-dimensional cone C can be triangulated into unimodular cones generated by elements of Hilb(C) and that Hilb(C) ⊂ (d − 1)Δ_{C} in all dimensions d (see Remark 1.4(f)). We can now formulate the main result for unimodular covers of rational cones:

Theorem 1.3. For all d ≥ 2 one has

𝔠_{d}^{cone} ≤ ⌈\sqrt{d − 1} ⌉ (d − 1)\frac{d(d + 1)}{2}(\frac{3}{2})^{⌈\sqrt{d−1}⌉(d−1)−2}.

Remark 1.4. (a) We have proved in [BGT1, Theorem 1.3.1] that there is a natural number c_{P} for a lattice polytope P ⊂ ℝ^{d} such that cP = UC(cP) whenever c ≥ c_{P}, c ∈ ℕ. However, neither did the proof in [BGT1] provide an explicit bound for c_{P}, nor was it clear that the numbers c_{P} can be uniformly bounded with respect to all d-dimensional polytopes. The proof we present below is an essential extension of that of [BGT1, Theorem 1.3.1].

(b) It has been proved in [KKMS, Theorem 4, Ch. III] that for every lattice polytope P there exists a natural number c such that cP admits even a regular triangulation into unimodular simplices. This implies that c′cP also admits such a triangulation for c′ ∈ ℕ. However, the question whether there exists a natural number c_{P}^{triang} such that the multiples c′P admit unimodular triangulations for all c′ ≥ c_{P}^{triang} remains open. In particular, the existence of a uniform bound 𝔠_{d}^{triang} (independent of P) remains open.

(c) The main difficulty in deriving better estimates for 𝔠_{d}^{pol} lies in the fundamental open problem of an effective description of the empty lattice d-simplices; see Haase and Ziegler [HZ] and Sebő [S2] and the references therein.

(d) A chance for improving the upper bound in Theorem 1.1 to, say, a polynomial function in d would be provided by an algorithm for resolving toric singularities which is faster then the standard one used in the proof of Theorem 4.1 below. Only there exponential terms enter our arguments.

(e) A lattice polytope P ⊂ ℝ^{d} which is covered by unimodular simplices is normal, i. e. the additive subsemigroup

S_{P} = ∑_{x∈P ∩ℤ^{d}} ℤ_{+}(x, 1) ⊂ ℤ^{d+1}

is normal and, moreover, gp(S_{P}) = ℤ^{d+1}. (The normality of S_{P} is equivalent to the normality of the K-algebra K[S_{P}] for a field K.) However, there are normal lattice polytopes in dimension ≥ 5 which are not unimodularly covered [BG]. On the other hand, if dim P = d then cP is normal for arbitrary c ≥ d−1 [BGT1, Theorem 1.3.3(a)] (and gp(S_{cP}) = ℤ^{d+1}, as is easily seen). The example found in [BG] is far from being of type cP with c > 1 and, correspondingly, we raise the following question: is 𝔠_{d}^{pol} = d − 1 for all natural numbers d > 1? As mentioned above, the answer is ‘yes’ for d = 2, 3, but we cannot provide further evidence for a positive answer.

(f) Suppose C_{1}, …, C_{k} form a unimodular cover of C. Then Hilb(C_{1}) ∪ ⋯ ∪ Hilb(C_{k}) generates C ∩ ℤ^{d}. Therefore Hilb(C) ⊂ Hilb(C_{1}) ∪ ⋯ ∪ Hilb(C_{k}), and so Hilb(C) sets a lower bound to the size of Hilb(C_{1}) ∪ ⋯ ∪ Hilb(C_{k}) relative to Δ_{C}. For d ≥ 3 there exist cones C such that Hilb(C) is not contained in (d − 2)Δ_{C} (see Ewald and Wessels [EW]), and so one must have 𝔠_{d}^{cone} ≥ d − 1. On the other hand, d − 1 is the best lower bound for 𝔠_{d}^{cone} that can be obtained by this argument since Hilb(C) ⊂ (d − 1)Δ_{C} for all cones C. We may assume that C is empty simplicial by Remark 1.2, and for an empty simplicial cone C we have

Hilb(C) ⊂ □_{C} \ (v_{1} + ⋯ + v_{d} − Δ_{C}) ⊂ (d − 1)Δ_{C}

where (i) v_{1}, …, v_{d} are the extreme integral generators of C, (ii) □_{C} is the semi-open parallelotope spanned by v_{1}, …, v_{d}, that is,

□_{C} = {ξ_{1}v_{1} + ⋯ + ξ_{d}v_{d} : ξ_{1}, …, ξ_{d} ∈ [0, 1)}.

Acknowledgement. We thank the referees for their careful reading of the paper. It led to a number of improvements in the exposition, and helped us to correct an error in the first version of Lemma 4.1.

2. Slope independence

By [0, 1]^{d} = {(z_{1}, …, z_{d}) | 0 ≤ z_{1}, …, z_{d} ≤ 1} we denote the standard unit d-cube. Consider the system of simplices

Δ_{σ} ⊂ [0, 1]^{d}, σ ∈ S_{d},

where S_{d} is the permutation group of {1, …, d}, and Δ_{σ} is defined as follows: (i) Δ_{σ} = conv(x_{0}, x_{1}, …, x_{d}), (ii) x_{0} = O and x_{d} = (1, …, 1), (iii) x_{i+1} differs from x_{i} only in the σ(i+1)st coordinate and x_{i+1,σ(i+1)} = 1

for i ∈ [0, d − 1]. Then {Δ_{σ}}_{σ∈S_{d}} is a unimodular triangulation of [0, 1]^{d} with additional good properties [BGT1, Section 2.3]. The simplices Δ_{σ} and their integral parallel translates triangulate the entire space ℝ^{d} into affine Weyl chambers of type A_{d}. The induced triangulations of the integral multiples of the simplex

conv(O, e_{1}, e_{1} + e_{2}, …, e_{1} + ⋯ + e_{d}} ⊂ ℝ^{d}

are studied in great detail in [KKMS, Ch. III]. All we need here is the very existence of these triangulations. In particular, the integral parallel translates of the simplices Δ_{σ} cover (actually, triangulate) the cone

ℝ_{+}e_{1} + ℝ_{+}(e_{1} + e_{2}) + ⋯ + ℝ_{+}(e_{1} + ⋯ + e_{d}) ≈ ℝ_{+}^{d}

into unimodular simplices. Suppose we are given a real linear form

α(X_{1}, …, X_{d}) = a_{1}X_{1} + ⋯ + a_{d}X_{d} ≠ 0.

The width of a polytope P ⊂ ℝ^{d} in direction (a_{1}, …, a_{d}), denoted by width_{α}(P), is defined to be the Euclidean distance between the two extreme hyperplanes that are parallel to the hyperplane a_{1}X_{1} + ⋯ + a_{d}X_{d} = 0 and intersect P. Since [0, 1]^{d} is inscribed in a sphere of radius \sqrt{d}/2, we have width_{α}(Δ_{σ}) ≤ \sqrt{d} whatever the linear form α and the permutation σ are. We arrive at

Proposition 2.1. All integral parallel translates of Δ_{σ}, σ ∈ S_{d}, that intersect a hyperplane H are contained in the \sqrt{d}-neighborhood of H.

In the following we will have to consider simplices that are unimodular with respect to an affine sublattice of ℝ^{d} different from ℤ^{d}. Such lattices are sets

L = v_{0} + ∑_{i=1}^{e} ℤ(v_{i} − v_{0})

where v_{0}, …, v_{e}, e ≤ d, are affinely independent vectors. (Note that L is independent of the enumeration of the vectors v_{0}, …, v_{d}.) An e-simplex Δ = conv(w_{0}, …, w_{e}) defines the lattice

L_{Δ} = w_{0} + ∑_{i=0}^{e} ℤ(w_{i} − w_{0}).

Let L be an affine lattice. A simplex Δ is called L-unimodular if L = L_{Δ}, and the union of all L-unimodular simplices inside a polytope P ⊂ ℝ^{d} is denoted by UC_{L}(P). For simplicity we set UC_{Δ}(P) = UC_{L_{Δ}}(P). Let Δ ⊂ Δ′ be (not necessarily integral) d-simplices in ℝ^{d} such that the origin O ∈ ℝ^{d} is a common vertex and the two simplicial cones spanned by Δ and Δ′ at O are the same. The following lemma says that the L_{Δ}-unimodularly covered area in a multiple cΔ′, c ∈ ℕ, approximates cΔ′ with a precision independent of Δ′. The precision is therefore independent of the “slope” of the facets of Δ and Δ′ opposite to O. The lemma will be critical both in the passage to cones (Section 3) and in the treatment of the cones themselves (Section 6).

Lemma 2.2. For all d-simplices Δ ⊂ Δ′ having O as a common vertex at which they span the same cone, all real numbers ε, 0 < ε < 1, and c ≥ \sqrt{d}/ε one has

(c − εc)Δ′ ⊂ UC_{Δ}(cΔ′).

Proof. Let v_{1}, …, v_{d} be the vertices of Δ different from O, and let w_{i}, i ∈ [1, d] be the vertex of Δ′ on the ray ℝ_{+}v_{i}. By a rearrangement of the indices we can achieve that

\frac{|w_{1}|}{|v_{1}|} ≥ \frac{|w_{2}|}{|v_{2}|} ≥ ⋯ ≥ \frac{|w_{d}|}{|v_{d}|} ≥ 1.

where | | denotes Euclidean norm. Moreover, the assertion of the lemma is invariant under linear transformations of ℝ^{d}. Therefore we can assume that

Δ = conv(O, e_{1}, e_{1} + e_{2}, …, e_{1} + ⋯ + e_{d}).

Then L_{Δ} = ℤ^{d}. The ratios above are also invariant under linear transformations. Thus

\frac{|w_{1}|}{|e_{1}|} ≥ \frac{|w_{2}|}{|e_{1} + e_{2}|} ≥ ⋯ ≥ \frac{|w_{d}|}{|e_{1} + ⋯ + e_{d}|} ≥ 1.

Now Lemma 2.4 below shows that the distance h from O to the affine hyperplane H through w_{1}, …, w_{d} is at least 1. By Proposition 2.1, the subset

(cΔ′) \ U\sqrt{d}(cH) ⊂ cΔ′

is covered by integral parallel translates of the simplices Δ_{σ}, σ ∈ S_{d} that are contained in cΔ. (U_{δ}(M) is the δ-neighborhood of M.) In particular,

(1)  (cΔ′) \ U\sqrt{d}(cH) ⊂ UC_{Δ}(cΔ′).

Therefore we have

(1−ε)cΔ′ ⊂ (1− \frac{\sqrt{d}}{c})cΔ′ ⊂ (1− \frac{\sqrt{d}}{ch})cΔ′ = \frac{ch − \sqrt{d}}{ch}cΔ′ = (cΔ′)\U\sqrt{d}(cH),

and the lemma follows from (1). □

Remark 2.3. One can derive an analogous result using the trivial tiling of ℝ_{+}^{d} by the integral parallel translates of [0, 1]^{d} and the fact that [0, 1]^{d} itself is unimodularly covered. The argument would then get simplified, but the estimate obtained is c ≥ d/ε, and thus worse than c ≥ \sqrt{d}/ε.

We have formulated the Lemma 2.2 only for full dimensional simplices, but it holds for simplices of smaller dimension as well: one simply chooses all data relative to the affine subspace generated by Δ′. Above we have used the following Lemma 2.4. Let e_{1}, …, e_{d} be the canonical basis of ℝ^{d} and set w_{i} = λ_{i}(e_{1} + ⋯ + e_{i}) where λ_{1} ≥ ⋯ ≥ λ_{d} > 0. Then the affine hyperplane H through w_{1}, …, w_{d} intersects the set Q = λ_{d}(e_{1} + ⋯ + e_{d}) − ℝ_{+}^{d} only in the boundary ∂Q. In particular the Euclidean distance from O to H is ≥ λ_{d}.

Proof. The hyperplane H is given by the equation

\frac{1}{λ_{1}} X_{1} + (\frac{1}{λ_{2}} − \frac{1}{λ_{1}} ) X_{2} + ⋯ + (\frac{1}{λ_{d}} − \frac{1}{λ_{d−1}} ) X_{d} = 1.

The linear form α on the left hand side has non-negative coefficients and w_{d} ∈ H. Thus a point whose coordinates are strictly smaller than λ_{d} cannot be contained in H. □

3. Passage to cones

In this section we want to relate the bounds for 𝔠_{d}^{pol} and 𝔠_{d}^{cone}. This allows us to derive Theorem 1.1 from Theorem 1.3.

Proposition 3.1. Let d be a natural number. Then 𝔠_{d}^{pol} is finite if and only if 𝔠_{d}^{cone} is finite, and, moreover,

(2)  𝔠_{d}^{cone} ≤ 𝔠_{d}^{pol} ≤ \sqrt{d}(d + 1)𝔠_{d}^{cone}.

Proof. Suppose that 𝔠_{d}^{pol} is finite. Then the left inequality is easily obtained by considering the multiples of the polytope Δ_{C} for a cone C: the cones spanned by those unimodular simplices in a multiple of Δ_{C} that contain O as a vertex constitute a unimodular cover of C. Now suppose that 𝔠_{d}^{cone} is finite. For the right inequality we first triangulate a polytope P into lattice simplices. Then it is enough to consider a lattice d-simplex Δ ⊂ ℝ^{d} with vertices v_{0}, …, v_{d}. Set c′ = 𝔠_{d}^{cone}. For each i there exists a unimodular cover (D_{ij}) of the corner cone C_{i} of Δ with respect to the vertex v_{i} such that c′Δ − c′v_{i} contains Δ_{D_{ij}} for all j. Thus the simplices Δ_{D_{ij}} + c′v_{i} cover the corner of c′Δ at c′v_{i}, that is, their union contains a neighborhood of c′v_{i} in c′Δ. We replace Δ by c′Δ and can assume that each corner of Δ has a cover by unimodular simplices. It remains to show that the multiples c′′Δ are unimodularly covered for every number c′′ ≥ \sqrt{d}(d + 1) for which c′′P is an integral polytope. Let

ω = \frac{1}{d + 1}(v_{0} + ⋯ + v_{d})

be the barycenter of Δ. We define the subsimplex Δ_{i} ⊂ Δ as follows: Δ_{i} is the homothetic image of Δ with respect to the center v_{i} so that ω lies on the facet of Δ_{i} opposite to v_{i}. In dimension 2 this is illustrated by Figure 1. The factor of the homothety that transforms Δ into Δ_{i} is d/(d + 1). In particular, the simplices Δ_{i} are pairwise congruent. It is also clear that

(3)  ⋃_{i=0}^{d} Δ_{i} = Δ.

v_{0}  v_{2}  v_{1} Δ_{0}  Δ C_{0} ω

Figure 1.

The construction of ω and the subsimplices Δ_{i} commutes with taking multiples of Δ. It is therefore enough to show that c′′Δ_{i} ⊂ UC(c′′Δ) for all i. In order to simplify the use of dilatations we move v_{i} to O by a parallel translation. In the case in which v_{i} = O the simplices c′′Δ and c′′Δ_{i} are the unions of their intersections with the cones D_{ij}. This observation reduces the critical inclusion c′′Δ_{i} ⊂ c′′Δ to

c′′(Δ_{i} ∩ D_{ij}) ⊂ c′′(Δ ∩ D_{ij})

for all j. But now we are in the situation of Lemma 2.2, with the unimodular simplex Δ_{D_{ij}} in the role of the Δ of 2.2 and Δ ∩ D_{ij} in that of Δ′. For ε = 1/(d + 1) we have c′′ ≥ \sqrt{d}/ε and so

c′′(Δ_{i} ∩ D_{ij}) = c′′ \frac{d}{d + 1}(Δ ∩ D_{ij}) = c′′(1 − ε)(Δ ∩ D_{ij}) ⊂ UC(Δ ∩ D_{ij}),

as desired. □

At this point we can deduce Theorem 1.1 from Theorem 1.3. In fact, using the bound for 𝔠_{d}^{cone} given in Theorem 1.3 we obtain

𝔠_{d}^{pol} ≤ \sqrt{d}(d + 1)𝔠_{d}^{cone}

≤ \sqrt{d}(d + 1) ⌈\sqrt{d − 1}⌉ (d − 1)\frac{d(d + 1)}{2}(\frac{3}{2})^{⌈\sqrt{d−1}⌉(d−1)−2}

≤ O(d^{5})(\frac{3}{2})^{⌈\sqrt{d−1}⌉(d−1)},

as desired. (The left inequality in (2) has only been stated for completeness; it will not be used later on.)

4. Bounding toric resolutions

Let C be a simplicial rational d-cone. The following lemma gives an upper bound for the number of steps in the standard procedure to equivariantly resolve the toric singularity Spec(k[ℤ^{d} ∩ C]) (see [F, Section 2.6] and [O, Section 1.5] for the background). It depends on d and the multiplicity of Δ_{C}. Exponential factors enter our estimates only at this place. Therefore any improvement of the toric resolution bound would critically affect the order of magnitude of the estimates of 𝔠_{d}^{pol} and 𝔠_{d}^{cone}.

Theorem 4.1. Every rational simplicial d-cone C ⊂ ℝ^{d}, d ≥ 3, admits a unimodular triangulation C = D_{1} ∪ ⋯ ∪ D_{T} such that

Hilb(D_{t}) ⊂ (\frac{d}{2}(\frac{3}{2})^{μ(Δ_{C})−2})Δ_{C}, t ∈ [1, T].

Proof. We use the sequence h_{k}, k ≥ −(d−2), of real numbers defined recursively as follows:

h_{k} = 1, k ≤ 1,  h_{2} = \frac{d}{2},  h_{k} = \frac{1}{2}(h_{k−1} + ⋯ + h_{k−d}), k ≥ 3.

One sees easily that this sequence is increasing, and that

h_{k} = \frac{1}{2}h_{k−1} + \frac{1}{2}(h_{k−2} + ⋯ + h_{k−d−1}) − \frac{1}{2}h_{k−d−1} = \frac{3}{2}h_{k−1} − \frac{1}{2}h_{k−d−1}

≤ \frac{d}{2}(\frac{3}{2})^{k−2}

for all k ≥ 2. Let v_{1}, …, v_{d} be the extreme integral generators of C and denote by □_{C} the semi-open parallelotope

{z | z = ξ_{1}v_{1} + ⋯ + ξ_{d}v_{d}, 0 ≤ ξ_{1}, …, ξ_{d} < 1} ⊂ ℝ^{d}.

The cone C is unimodular if and only if

□_{C} ∩ ℤ^{d} = {O}.

If C is unimodular then the bound given in the theorem is satisfied (note that d ≥ 3). Otherwise we choose a non-zero lattice point, say w, from □_{C},

w = ξ_{i_{1}}v_{i_{1}} + ⋯ + ξ_{i_{k}}v_{i_{k}}, 0 < ξ_{i_{j}} < 1.

We can assume that w is in (d/2)Δ_{C}. If not, then we replace w by

(4)  v_{i_{1}} + ⋯ + v_{i_{k}} − w.

The cone C is triangulated into the simplicial d-cones

C_{j} = ℝ_{+}v_{1} + ⋯ + ℝ_{+}v_{i_{j}−1} + ℝ_{+}w + ℝ_{+}v_{i_{j}+1} + ⋯ + ℝ_{+}v_{d}, j = 1, …, k.

Call these cones the second generation cones, C itself being of first generation. (The construction of the cones C_{j} is called stellar subdivision with respect to w.) For the second generation cones we have μ(Δ_{C_{i}}) < μ(Δ_{C}) because the volumes of the corresponding parallelotopes are in the same relation. Therefore we are done if μ(Δ_{C}) = 2. If μ(Δ_{C}) ≥ 3, we generate the (k + 1)st generation cones by successively subdividing the kth generation non-unimodular cones. It is clear that we obtain a triangulation of C if we use each vector produced to subdivide all kth generation cones to which it belongs. Figure 2 shows a typical situation after 2 generations of subdivision in the cross-section of a 3-cone.

Figure 2.

If C′′ is a next generation cone produced from a cone C′, then μ(Δ_{C′′}) < μ(Δ_{C′}), and it is clear that there exists g ≤ μ(Δ_{C}) for which all cones of generation g are unimodular. We claim that each vector w^{(k)} subdividing a (k − 1)st generation cone C^{(k−1)} is in

h_{k} Δ_{C}.

For k = 2 this has been shown already. So assume that k ≥ 3. Note that all the extreme generators u_{1}, …, u_{d} of C^{(k−1)} either belong to the original vectors v_{1}, …, v_{d} or were created in different generations. By induction we therefore have

u_{i} ∈ h_{t_{i}} Δ_{C}, t_{1}, …, t_{d} pairwise different.

Using the trick (4) if necessary, one can achieve that

w^{(k)} ∈ cΔ_{C}, c ≤ \frac{1}{2}(h_{t_{1}} + ⋯ + h_{t_{d}}).

Since the sequence (h_{i}) is increasing,

c ≤ \frac{1}{2}(h_{k−1} + ⋯ + h_{k−d}) = h_{k}.  □

Remark 4.2. (a) In dimension d = 2 the algorithm constructs a triangulation into unimodular cones D_{t} with Hilb(D_{t}) ⊂ Δ_{C}.

(b) For d = 3 one has Sebő’s [S1] result Hilb(D_{t}) ⊂ 2Δ_{C}. It needs a rather tricky argument for the choice of w.

5. Corner covers

Let C be a rational cone and v one of its extreme generators. We say that a system {C_{j}}_{j=1}^{k} of subcones C_{j} ⊂ C covers the corner of C at v if v ∈ Hilb(C_{j}) for all j and the union ⋃_{j=1}^{k} C_{j} contains a neighborhood of v in C.

Lemma 5.1. Suppose that 𝔠_{d−1}^{cone} < ∞, and let C be a simplicial rational d-cone with extreme generators v_{1}, …, v_{d}.

(a) Then there is a system of unimodular subcones C_{1}, …, C_{k} ⊂ C covering the corner of C at v_{1} such that Hilb(C_{1}), …, Hilb(C_{k}) ⊂ (𝔠_{d−1}^{cone} +1)Δ_{C}.

(b) Moreover, each element w ≠ v_{1} of a Hilbert basis of C_{j}, j ∈ [1, k], has a representation w = ξ_{1}v_{1} + ⋯ + ξ_{d}v_{d} with ξ_{1} < 1.

Proof. For simplicity of notation we set 𝔠 = 𝔠_{d−1}^{cone}. Let C′ be the cone generated by w_{i} = v_{i} − v_{1}, i ∈ [2, d], and let V be the vector subspace of ℝ^{d} generated by the w_{i}. We consider the linear map π : ℝ^{d} → V given by π(v_{1}) = 0, π(v_{i}) = w_{i} for i > 0, and endow V with a lattice structure by setting L = π(ℤ^{d}). (One has L = ℤ^{d} ∩ V if and only if ℤ^{d} = ℤv_{1} + (ℤ^{d} ∩ V).) Note that v_{1}, z_{2}, …, z_{d} with z_{j} ∈ ℤ^{d} form a ℤ-basis of ℤ^{d} if and only if π(z_{2}), …, π(z_{d}) are a ℤ-basis of L. This holds since ℤv_{1} = ℤ^{d} ∩ ℝv_{1}, and explains the unimodularity of the cones C_{j} constructed below. Note that w_{i} ∈ L for all i. Therefore Δ_{C′} ⊂ conv(O, w_{2}, …, w_{d}). The cone C′ has a unimodular covering (with respect to L) by cones C′_{j}, j ∈ [1, k], with Hilb(C′_{j}) ⊂ 𝔠Δ_{C′}. We “lift” the vectors x ∈ Hilb(C′_{j}) to elements x̃ ∈ C as follows. Let x = α_{2}w_{2} +⋯+α_{d}w_{d} (with α_{i} ∈ ℚ_{+}). Then there exists a unique integer n ≥ 0 such that

x̃ := nv_{1} + x = nv_{1} + α_{2}(v_{2} − v_{1}) + ⋯ + α_{d}(v_{d} − v_{1})
= α_{1}v_{1} + α_{2}v_{2} + ⋯ + α_{d}v_{d}

with 0 ≤ α_{1} < 1. (See Figure 3.) If x ∈ 𝔠Δ_{C′} ⊂ 𝔠 · conv(O, w_{2}, …, w_{d}), then x̃ ∈ (𝔠 + 1)Δ_{C}.

\begin{aligned}v_{1} & v_{2} & w_{2} & x & x̃ \\ & Figure 3. \end{aligned}

We now define C_{j} as the cone generated by v_{1} and the vectors x̃ where x ∈ Hilb(C′_{j}). It only remains to show that the C_{j} cover a neighborhood of v_{1} in C. To this end we intersect C with the affine hyperplane H through v_{1}, …, v_{d}. It is enough that a neighborhood of v_{1} in C ∩ H is contained in C_{1} ∪ ⋯ ∪ C_{k}. For each j ∈ [1, k] the coordinate transformation from the basis w_{2}, …, w_{d} of V to the basis x_{2}, …, x_{d} with {x_{2}, …, x_{d}} = Hilb(C′_{j}) defines a linear operator on ℝ^{d−1}. Let M_{j} be its ∥ ∥_{∞} norm. Moreover, let N_{j} be the maximum of the numbers n_{i}, i ∈ [2, d] defined by the equation x̃_{i} = n_{i}v_{1} + x_{i} as above. Choose ε with

0 < ε ≤ \frac{1}{(d − 1)M_{j}N_{j}} , j ∈ [1, k].

and consider

y = v_{1} + β_{2}w_{2} + ⋯ + β_{d}w_{d}, 0 ≤ β_{i} < ε.

Since the C′_{j} cover C′, one has β_{2}w_{2} +⋯+β_{d}w_{d} ∈ C′_{j} for some j, and therefore

y = v_{1} + γ_{2}x_{2} + ⋯ + γ_{d}x_{d},

where {x_{2}, …, x_{d}} = Hilb(C′_{j}) and 0 ≤ γ_{i} ≤ M_{j}ε for i ∈ [2, d]. Then

y = (1 − ∑_{i=2}^{d} n_{i}γ_{i})v_{1} + γ_{2}x̃_{2} + ⋯ + γ_{d}x̃_{d}

and

∑_{i=2}^{d} n_{i}γ_{i} ≤ (d − 1)N_{j}M_{j}ε ≤ 1,

whence (1 − ∑_{i=2}^{d} n_{i}γ_{i}) ≥ 0 and y ∈ C_{j}, as desired. □

6. The bound for cones

Before we embark on the proof of Theorem 1.3, we single out a technical step. Let {v_{1}, …, v_{d}} ⊂ ℝ^{d} be a linearly independent subset. Consider the hyperplane

H = Aff(O, v_{1} + (d − 1)v_{2}, v_{1} + (d − 1)v_{3}, …, v_{1} + (d − 1)v_{d}) ⊂ ℝ^{d}

It cuts a simplex δ off the simplex conv(v_{1}, …, v_{d}) so that v_{1} ∈ δ. Let Φ denote the closure of

ℝ_{+}δ \ (((1 + ℝ_{+})v_{1} + ℝ_{+}e_{2} + ⋯ + ℝ_{+}v_{d}) ∪ Δ) ⊂ ℝ^{d}.

where Δ = conv(O, v_{1}, …, v_{d}). See Figure 4 for the case d = 2. The polytope

3v_{2} 3v_{1}  v_{2} v_{1}  H Φ δ 3Δ

Figure 4.

Φ′ = −\frac{1}{d − 1}v_{1} + \frac{d}{d − 1}Φ

is the homothetic image of the polytope Φ under the dilatation with factor d/(d − 1) and center v_{1}. We will need that

(5)  Φ′ ⊂ (d + 1)Δ.

The easy proof is left to the reader.

Proof of Theorem 1.3. We want to prove the inequality

(6)  𝔠_{d}^{cone} ≤ ⌈\sqrt{d − 1}⌉ (d − 1)\frac{d(d + 1)}{2}(\frac{3}{2})^{⌈\sqrt{d−1}⌉(d−1)−2}

for all d ≥ 2 by induction on d. The inequality holds for d = 2 since 𝔠_{2}^{cone} = 1 (see the remarks preceding Theorem 1.3 in Section 1), and the right hand side above is 2 for d = 2. By induction we can assume that (6) has been shown for all dimensions < d. We set

γ = ⌈\sqrt{d − 1} ⌉(d − 1) and κ = γ \frac{d(d + 1)}{2}(\frac{3}{2})^{γ−2}.

As pointed out in Remark 1.2, we can right away assume that C is empty simplicial with extreme generators v_{1}, …, v_{d}.

Outline. The following arguments are subdivided into four major steps. The first three of them are very similar to their analogues in the proof of Proposition 3.1. In Step 1 we cover the d-cone C by d + 1 smaller cones each of which is bounded by the hyperplane that passes through the barycenter of conv(v_{1}, …, v_{d}) and is parallel to the facet of conv(v_{1}, …, v_{d}) opposite of v_{i}, i = 1, …, d. We summarize this step in Claim A below. In Step 2 Lemma 5.1 is applied for the construction of unimodular corner covers. Claim B states that it is enough to cover the subcones of C ‘in direction’ of the cones forming the corner cover. In Step 3 we extend the corner cover far enough into C. Lemma 2.2 allows us to do this within a suitable multiple of Δ_{C}. The most difficult part of the proof is to control the size of all vectors involved. However, Lemma 2.2 is applied to simplices Γ = conv(w_{1}, …, w_{e}) where w_{1}, …, w_{e} span a unimodular cone of dimension e ≤ d. The cones over the unimodular simplices covering cΓ have multiplicity dividing c, and possibly equal to c. Nevertheless we obtain a cover of C by cones with bounded multiplicities. So we can apply Theorem 4.1 in Step 4 to obtain a unimodular cover.

Step 1. The facet conv(v_{1}, …, v_{d}) of Δ_{C} is denoted by Γ_{0}. (We use the letter Γ for (d−1)-dimensional simplices, and Δ for d-dimensional ones.) For i ∈ [1, d] we put

H_{i} = Aff(O, v_{i}+(d−1)v_{1}, …, v_{i}+(d−1)v_{i−1}, v_{i}+(d−1)v_{i+1}, …, v_{i}+(d−1)v_{d})

and

Γ_{i} = conv (v_{i}, Γ_{0} ∩ H_{i}).

Observe that v_{1} + ⋯ + v_{d} ∈ H_{i}. In particular, the hyperplanes H_{i}, i ∈ [1, d] contain the barycenter of Γ_{0}, i. e. (1/d)(v_{1} + ⋯ + v_{d}). In fact, H_{i} is the vector subspace of dimension d−1 through the barycenter of Γ_{0} that is parallel to the facet of Γ_{0} opposite to v_{i}. Clearly, we have the representation ⋃_{i=1}^{d} Γ_{i} = Γ_{0}, similar to (3) in Section 3. In particular, each of the Γ_{i} is homothetic to Γ_{0} with factor (d − 1)/d. To prove (6) it is enough to show the following

Claim A. For each index i ∈ [1, d] there exists a system of unimodular cones

C_{i1}, …, C_{ik_{i}} ⊂ C

such that Hilb(C_{ij}) ⊂ κΔ_{C}, j ∈ [1, k_{i}], and Γ_{i} ⊂ ⋃_{j=1}^{k_{i}} C_{ij}.

The step from the original claim to the reduction expressed by Claim A seems rather small – we have only covered the cross-section Γ_{0} by the Γ_{i}, and state that it is enough to cover each Γ_{i} by unimodular subcones. The essential point is that these subcones need not be contained in the cone spanned by Γ_{i}, but just in C. This gives us the freedom to start with a corner cover at v_{i} and to extend it far enough into C, namely beyond H_{i}. This is made more precise in the next step.

Step 2. To prove Claim A it is enough to treat the case i = 1. The induction hypothesis implies 𝔠_{d−1}^{cone} ≤ κ − 1 because the right hand side of the inequality (6) is a strictly increasing function of d. Thus Lemma 5.1 provides a system of unimodular cones C_{1}, …, C_{k} ⊂ C covering the corner of C at v_{1} such that

(7)  Hilb(C_{j}) \ {v_{1}, …, v_{d}} ⊂ (κΔ_{C}) \ Δ_{C}, j ∈ [1, k].

Here we use the emptiness of Δ_{C} – it guarantees that Hilb(C_{j}) ∩ (Δ_{C} \ Γ_{0}) = ∅ which is crucial for the inclusion (9) in Step 3. With a suitable enumeration {v_{j1}, …, v_{jd}} = Hilb(C_{j}), j ∈ [1, k] we have v_{11} = v_{21} = ⋯ = v_{k1} = v_{1} and

(8)  0 ≤ (v_{jl})_{v_{1}} < 1, j ∈ [1, k], l ∈ [2, d],

where (−)_{v_{1}} is the first coordinate of an element of ℝ^{d} with respect to the basis v_{1}, …, v_{d} of ℝ^{d} (see Lemma 5.1(b)). Now we formulate precisely what it means to extend the corner cover beyond the hyperplane H_{1}. Fix an index j ∈ [1, k] and let D ⊂ ℝ^{d} denote the simplicial d-cone determined by the following conditions:

(i) C_{j} ⊂ D, (ii) the facets of D contain those facets of C_{j} that pass through O and v_{1}, (iii) the remaining facet of D is in H_{1}.

Figure 5 describes the situation in the cross-section Γ_{0} of C. By considering all possible values j = 1, …, k, it becomes clear that to prove Claim A it is enough to prove

\begin{aligned}D & H_{1} & v_{1} & Γ_{0} & C_{2} & C_{1} \\ & & & Figure 5. \end{aligned}

Claim B. There exists a system of unimodular cones D_{1}, …, D_{T} ⊂ C such that

Hilb(D_{t}) ⊂ κΔ_{C}, t ∈ [1, T]  and  D ⊂ ⋃_{t=1}^{T} D_{t}.

Step 3. For simplicity of notation we put Δ = Δ_{C_{j}}, H = H_{1}. (Recall that Δ is of dimension d, spanned by O and the extreme integral generators of C_{j}.) The vertices of Δ, different from O and v_{1} are denoted by w_{2}, …, w_{d} in such a way that there exists i_{0}, 1 ≤ i_{0} ≤ d, for which

(i) w_{2}, …, w_{i_{0}} ∈ D \ H (‘bad’ vertices, on the same side of H as v_{1}),
(ii) w_{i_{0}+1}, … w_{d} ∈ \overline{C_{j} \ D} (‘good’ vertices, beyond or on H),

neither i_{0} = 1 nor i_{0} = d being excluded. (\overline{X} is the closure of X ⊂ ℝ^{d} with respect to the Euclidean topology.) In the situation of Figure 5 the cone C_{2} has two bad vertices, whereas C_{1} has one good and one bad vertex. (Of course, we see only the intersection points of the cross-section Γ_{0} with the rays from O through the vertices.) If all vertices are good, there is nothing to prove since D ⊂ C_{j} in this case. So assume that there are bad vertices, i. e. i_{0} ≥ 2. We now show that the bad vertices are caught in a compact set whose size with respect to Δ_{C} depends only on d, and this fact makes the whole proof work. Consider the (d − 1)-dimensional cone

E = v_{1} + ℝ_{+}(w_{2} − v_{1}) + ⋯ + ℝ_{+}(w_{d} − v_{1}).

In other words, E is the (d − 1)-dimensional cone with apex v_{1} spanned by the facet conv(v_{1}, w_{2}, …, w_{d}) of Δ opposite to O. It is crucial in the following that the simplex conv(v_{1}, w_{2}, …, w_{d}) is unimodular (with respect to ℤ^{d} ∩ Aff(v_{1}, w_{2}, …, w_{d})), as follows from the unimodularity of C_{j}. Due to the inequality (8) the hyperplane H cuts a (d−1)-dimensional (possibly non-lattice) simplex off the cone E. We denote this simplex by Γ. Figure 6 illustrates the situation by a vertical cross-section of the cone C.

C_{j}  H D \ C_{j} E  C \ D Δ_{C} w_{i} Γ v_{1} ℝ_{+}v_{1}  ℝ_{+}v_{2} + ⋯ + ℝ_{+}v_{d}

Figure 6.

By (7) and (8) we have

Γ ⊂ Φ = \overline{ℝ_{+}Γ_{1} \ ((v_{1} + C) ∪ Δ_{C})}.

Let ϑ be the dilatation with center v_{1} and factor d/(d − 1). Then by (5) we have the inclusion

(9)  ϑ(Γ) ⊂ (d + 1)Δ_{C}.

One should note that this inclusion has two aspects: first it shows that Γ is not too big with respect to Δ_{C}. Second, it guarantees that there is some ζ > 0 only depending on d, namely ζ = 1/(d−1), such that the dilatation with factor 1 + ζ and center v_{1} keeps Γ inside C. If ζ depended on C, there would be no control on the factor c introduced below. Let Σ_{1} = conv(v_{1}, w_{2}, …, w_{i_{0}}) and Σ_{2} be the smallest face of Γ that contains Σ_{1}. These are d′-dimensional simplices, d′ = i_{0} − 1. Note that Σ_{2} ⊂ ϑ(Σ_{2}). We want to apply Lemma 2.2 to the pair

γv_{1} + (Σ_{1} − v_{1}) ⊂ γv_{1} + (Σ_{2} − v_{1}).

of simplices with the common vertex γv_{1}. The lattice of reference for the unimodular covering is

L = L_{γv_{1}+(Σ_{1}−v_{1})} = γv_{1} + ∑_{j=2}^{i_{0}} ℤ(w_{j} − v_{1}).

Set

ε = \frac{1}{d} and c = \frac{d}{d − 1}γ = ⌈\sqrt{d − 1} ⌉ d.

Since d′ ≤ d − 1, Lemma 2.2 (after the parallel translation of the common vertex to O and then back to γv_{1}) and (9) imply

(10)  γΣ_{2} ⊂ UC_{L}(γϑ(Σ_{2})) ⊂ γ(d + 1)Δ_{C}.

Step 4. Consider the i_{0}-dimensional simplices spanned by O and the unimodular (i_{0}−1)-simplices appearing in (10). Their multiplicities with respect to the i_{0}-rank lattice ℤL_{Σ_{1}} are all equal to γ, since Σ_{1}, a face of conv(v_{1}, w_{2}, …, w_{d}) is unimodular and, thus, we have unimodular simplices σ on height γ. The cones ℝ_{+}σ have multiplicity dividing γ. Therefore, by Lemma 4.1 we conclude that the i_{0}-cone ℝ_{+}Σ_{2} is in the union δ_{1} ∪ ⋯ ∪ δ_{T} of unimodular (with respect to the lattice ℤL_{Σ_{1}}) cones such that

Hilb(δ_{1}), …, Hilb(δ_{T}) ⊂ (\frac{d}{2}(\frac{3}{2})^{γ−2})Δ_{ℝ_{+}Σ_{2}}

⊂ (\frac{d}{2}(\frac{3}{2})^{γ−2})γ(d + 1)Δ_{C} = κΔ_{C}.

In view of the unimodularity of conv(v_{1}, w_{2}, …, w_{d}), the subgroup ℤL_{Σ_{1}} is a direct summand of ℤ^{d}. It follows that

D_{t} = δ_{t} + ℝ_{+}w_{i_{0}+1} + ⋯ + ℝ_{+}w_{d}, t ∈ [1, T],

is the desired system of unimodular cones. □

References

[BG] W. Bruns and J. Gubeladze, Normality and covering properties of affine semigroups, J. Reine Angew. Math. 510, 151–178, 1999.

[BGT1] W. Bruns, J. Gubeladze, and N. V. Trung, Normal polytopes, triangulations, and Koszul algebras, J. Reine Angew. Math. 485 (1997), 123–160.

[BGT2] W. Bruns, J. Gubeladze, and N. V. Trung, Problems and algorithms for affine semigroups, Semigroup Forum 64 (2002), 180–212.

[EW] G. Ewald and U. Wessels, On the ampleness of invertible sheaves in complete projective toric varieties, Result. Math. 19 (1991), 275-278.

[F] W. Fulton, Introduction to toric varieties, Princeton University Press, 1993.

[HZ] C. Haase and G. M. Ziegler, On the maximal width of empty lattice simplices, Eur. J. Comb. 21 (2000), 111-119.

[KS] J.-M. Kantor and K. S. Sarkaria, On primitive subdivisions of an elementary tetrahedron, preprint.

[KKMS] G. Kempf, F. Knudsen, D. Mumford, and B. Saint-Donat, Toroidal embeddings I, Lecture Notes in Math. 339, Springer, 1973.

[O] T. Oda, Convex bodies and algebraic geometry (An introduction to the theory of toric varieties), Springer, 1988.

[S1] A. Sebő, Hilbert bases, Carathéodory’s theorem, and combinatorial optimization, in ‘Integer Programming and Combinatorial Optimization’ (R. Kannan, W. Pulleyblank, eds.), University of Waterloo Press, Waterloo 1990, 431–456.

[S2] A. Sebő, An introduction to empty lattice simplices, Lect. Notes Comput. Sci. 1610 (1999), 400–414.

Winfried Bruns Universität Osnabrück FB Mathematik/Informatik 49069 Osnabrück Germany winfried@mathematik. uni-osnabrueck.de Joseph Gubeladze A. Razmadze Mathematical Institute Alexidze St. 1 380093 Tbilisi Georgia gubel@rmi.acnet.ge