Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 39 (1998), No. 1, 205–218.

Triangulations of Integral Polytopes and Ehrhart Polynomials

Jean-Michel Kantor

Institut de Mathématiques Case 247, 4, Place Jussieu, F-75525 Paris Cedex 05 e-mail: kantor@math.jussieu.fr

Abstract. We are interested in polytopes in real space of arbitrary dimension, having vertices with integral coordinates: integral polytopes. The recent increase of interest for the study of these polytopes and their triangulations has various motivations; let us mention the main ones:

• the beautiful theory of toric varieties has built a bridge between algebraic geometry and the combinatorics of these integral polytopes [14]. Triangulations of cones and polytopes occur naturally for example in problems of existence of crepant resolution of singularities [1], [6].

• The work of the school of I. M. Gelfand on secondary polytopes gives a new insight on triangulations, with applications to algebraic geometry and group theory [15].

• In statistical physics, random tilings lead to some interesting problems deal-

ing with triangulations of order polytopes [7]. With these motivations in mind, we introduce new tools which might bring some informations: Generalizations of the Ehrhart polynomial (counting points modulo congruence), discrete length between integral points and studying the geometry associated to it, arithmetic Euler-Poincaré formula which gives, in dimension 3, the Ehrhart polynomial in terms of the f-vector of a minimal triangulation of the polytope (Theorem 6). Finally, let us mention the results in dimension 2 of the late Peter Greenberg which led us to the study of “Arithmetical PL-topology” which, we believe with M. Gromov, D. Sullivan, and P. Vogel, has not yet revealed all its beauties. We thank these mathematicians for their interest, and Professor Ito for his kind invitation to The Seminar at R.I.M.S. in October 1995 where part of these results were given.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1998 Heldermann Verlag 1. Polytopes; counting integral points “modulo m”

1.1.

Definition 1. A polytope P in ℝ^{d} is the convex hull of a finite number of points {A_{1}, …, A_{n}}. The set of vertices Vert(P) is a subset of {A_{1}, …, A_{n}}. The polytope P is called integral (resp. rational) if the A_{i} can be chosen in ℤ^{d} (resp. in ℚ^{d}).

Definition 2. The polytope P is said to be elementary if Vert(P) = P ∩ Z^{d}. These polytopes have been called also free-lattice polytopes.

Denote by

G_{d} = Z^{d}×GL(d, Z)

the group of affine unimodular maps (affine linear isomorphisms preserving the lattice ℤ^{d}).

Lemma 1 and Definition 3. Let σ be an integral simplex in ℝ^{d}. The following conditions are equivalent:

1) σ = g(σ_{can}), where g is in G_{d} and σ_{can} is the basic simplex with vertices at the origin and {e_{i} = (0, …, 0, 1, 0, …, 0), i = 1, …, d}

2) The vertices of σ generate Z^{d}. If these conditions are satisfied, σ is said to be a primitive simplex, and the volume of σ is \frac{1}{d!}.

3) vol σ = \frac{1}{d!}

Elementary simplices. Elementary simplices are well known in dimension up to three (see 3.1). They coincide with primitive simplices in dimension 1 and 2. Some partial results are known in dimension 4 [33].

1.2. The Ehrhart polynomial

Let P be an integral polytope.

Theorem 1. [12], [4] For any integer k, let i_{P} (k) = card{k P ∩ Z^{d}} .

1) i_{P} is a polynomial in k (k in N).

2) The values of this polynomial at negative values are given by

i_{P} (−k) = (−1)^{m} card(k P^{0} ∩ Z^{d}), k ∈ N  (1)

where m is the dimension of P (dimension of the affine space generated by P), and P^{0} denotes the relative interior of P.

The polynomial i_{P} is called the Ehrhart polynomial of P.

Properties of i_{P}. The degree of i_{P} is the dimension of P. For example, for a polytope of dimension d

i_{P} (k) = 1 + a_{1}(P) k + ⋯ + a_{d}(P) k^{d}
\{ \begin{matrix}a_{d}(P) = V (P), volume of P \\ a_{d−1}(P) = \frac{1}{2} ∑ V_{d−1}(F) = \frac{1}{2}V_{d−1}(P) \end{matrix}  (2)

summation over all facets F of P, V_{d−1} denoting the volume of each facet with respect to the lattice induced by Z^{d} on the affine space generated by this facet.

For the next coefficient there is also a formula, see [18] Theorem 3. The other coefficients are still mysterious [18], [23].

1.3.

We introduce new counting functions. Let m be an integer and

π_{m} : R^{d} → \frac{R^{d}}{mZ^{d}}

be the quotient map.

Definition 4. For any couple of integers m and k:

i_{P} (k, m) = card π_{m} (k P ∩ Z^{d}) ,  (3)

the functions i_{P} (k, m) count integral points in k P “modulo m”, and i_{P} (k, 0) = i_{P} (k) is the Ehrhart polynomial.

Proposition 1.

i_{P} (k, m) = i_{g(P)} (k, m)

for any g in Z^{d}×GL(d, Z) : g(x) = u + Ax, u ∈ Z^{d}, A ∈ GL(d, Z).

Proof. It is enough to consider two cases:

a) g(x) = x + a, a ∈ Z^{d}, Q = P + a. Then π_{m}(k P ∩ Z^{d}) = π_{m}(k Q ∩ Z^{d}) + π_{m}(k a).

b) g = A ∈ GL(d, Z). A induces a bijection:

Ã : \frac{R^{d}}{mZ^{d}} → \frac{R^{d}}{mZ^{d}}

sending π_{m}(k P ∩ Z^{d}) to π_{m}(k A(P) ∩ Z^{d}).

Proposition 2. Suppose P has non-empty interior. Then there exist two rationals α and β such that

k > mα ⟹ i_{P} (k, m) = m^{d},
k < mβ ⟹ i_{P} (k, m) = i_{P} (k.)

Proof. 1) Suppose P contains a cube of side ε. Then kP contains a cube of side m if kε > m and it implies i_{p}(k, m) = m^{d}.

208 J.-M. Kantor: Triangulations of integral polytopes and Ehrhart polynomials

2) We introduce discrete analogs of euclidean lengths. Definition 5. If a and b are distinct in Z^{d}, the discrete length between a and b is

d(a, b) = Card([a, b] ∩ Z^{d}) − 1

where [a, b] is the segment joining a and b. Lemma 2.

a) d(ka, kb) = k d(a, b), k ∈ ℕ

b) d is not a distance. Proof. a) One reduces the proof of the first assertion to the case (easy) d(u, 0) = 1 ⟹ d(ku, 0) = k.

b) Take in ℝ^{2} the triangle with vertices the origin and points (3, 0) and (2, 1). It does not satisfy the triangular inequality. Definition 6. The discrete diameter of an integral polytope is

D(P) = sup_{a,b∈P} d(a, b) .

Now notice that if two integral points x and x′ satisfy

x − x′ = mu, u ∈ ℤ^{d}, u ≠ 0

then  x′ + iu ∈ [x, x′], i = 0, …, m ,
d(x, x′) > m .  (∗)

In particular, if m > D(P) , (∗) cannot be satisfied for points in P. Hence

\frac{m}{k} > D(P) ⟹ i_{P} (k, m) = i_{P} (k) .

Let us introduce the following Definition 7. A function φ(k_{1}, ..., k_{m}) of several positive integral variables is a quasipolynomial (with respect to a cofinite lattice L) on the subset A of ℕ^{d} if for any a in A the restriction φ_{a} = φ_{|(a+L)∩A} is a polynomial. The following was proved in [21, 22]. Theorem 2. Let Δ_{1}, ..., Δ_{k} be rational polytopes in R^{d}. Then the number of integral points in Δ(λ) = λ_{1}Δ_{1} + ... + λ_{k}Δ_{k} is a quasipolynomial in (λ_{1}, ..., λ_{k}). We state the following extension to modular Ehrhart functions: Theorem 3. Let P be an integral polytope. There exist L_{1}, ...L_{n} rational lines in the quadrant ℝ_{+}^{2} such that on each open cone (L_{i}, L_{i+1}) i_{p}(k, m) is a quasipolynomial.

Figure 1

The proof consists in lifting up the study to the usual space R^{d}, using locally finite arrangements of hyperplanes and the general strategy of moving hyperplanes parallel to themselves, due to A. Khovanskii, which makes a connection between continuous and discrete invariants (see [18], [19]). The details will be published elsewhere.

1.4. Valuations

Let A be any abelian group, and P_{d} the set of all integral polytopes in ℝ^{d}.

Definition 8. A map φ : P_{d} → A is said to be additive, or a valuation on P_{d}, if whenever P, Q, P ∪ Q, P ∩ Q are integral polytopes, φ(P ∪ Q) + φ(P ∩ Q) = φ(P) + φ(Q).

Theorem 4. If φ is any G_{d}-invariant valuation with values in A, then there exist unique elements α_{i} in A such that

φ(P) = ∑_{j=0}^{d} i_{p}(j) α_{j}

where i_{p}(j) are the values of the Ehrhart polynomial of P at integers j.

The proof [2] consists in studying in a geometrical way the group

Π = Z[P_{d}]/ ∼

where Π is the quotient of the free abelian group on P_{d} by the equivalence relation generated by

\{ \begin{matrix}[P] = [g(P)], g ∈ G_{d} \\ [P ∪ Q] = [P] + [Q] − [P ∩ Q]  if P, Q, P ∪ Q ∈ P_{d} . \end{matrix}  (4)

Remark. The functions i_{P} (m, k) are not additive. Take for example d = 1, m = 2. For adjacent intervals I, and I_{2} with at least two points

i_{I_{1}}(k, 2) = i_{I_{2}}(k, 2) = i_{I_{1}∪I_{2}}(k, 2) = 2
i_{I_{1}∩I_{2}}(k, 2) = 1 .

2. Triangulations

2.1.

We consider only rational (resp. integral) triangulations by rational (resp. integral) simplices.

Definition 9. A triangulation T of the polytope P is called primitive if all simplices are (integral) primitive simplices, maximal if all simplices are elementary.

Maximal triangulations are maximal with respect to the natural partial order on the set of integral triangulations.

Definition 10. If T is any triangulation, the f-vector of T is the integral vector f = (f_{i}), where f_{i} is the number of simplices of dimension i.

Lemma 3. If T is a primitive triangulation of the integral polytope P, the Ehrhart polynomial i_{P} is determined by the f-vector f(T ), and conversely.

Proof. Results from formula (1); this implies:

i_{P} (k) = ∑ f_{j}(−1)^{j} i_{j}(−k)

where i_{j}(k) is the number of integral points in k · e_{j}, e_{j} is the basic integral simplex of dimension j:

i_{j}(k) = \frac{(k + 1) … (k + j)}{j!} .

Proposition 3. Let P and Q be two integral polytopes. The following conditions are equivalent:

(i) P and Q have the same Ehrhart polynomial. (ii) There exists a k such that kP and kQ have the same Ehrhart polynomial. (iii) For all k, kP and kQ have the same Ehrhart polynomial. Moreover, if P and Q have primitive triangulations T_{P} and T_{Q} the conditions above are also equivalent to

f(T_{P}) = f(T_{Q}).

T_{P} and T_{Q} are said to be numerically equivalent.

Proof. The following is obvious:

i_{k P} (n) = i_{P} (k n) for all k and n

From this one deduces, using the polynomial character of i_{P}:

(i) ⟹ (iii) ⟹ (ii) ⟹ (i)

Unfortunately, most polytopes do \underline{not} have primitive triangulations. Given a polytope P, it is a difficult question to decide whether there exist primitive triangulations of P.

Example: Order polytopes. If O is a finite poset of d elements (partially ordered set): O = {y_{1}, …, y_{d}} define P (O) to be the set of all points in ℝ^{d} such that

P (O) = \{x = (x_{1}, …, x_{d}); x ∈ ℝ^{d} \left\{{0 ≤ x_{i} ≤ 1, if i = 1, …, d, \atop x_{i} ≤ x_{j} if y_{i} > y_{j} in O.}\right\}\}

P (O) is an integral convex polytope of dimension d, whose vertices correspond to the set L(P, 1) of maps σ : O → {0, 1} such that

y_{1} < y_{2} in O ⟹ σ(y_{1}) ≥ σ(y_{2}) .

Proposition 4. (Stanley) P (O) has a primitive triangulation. The primitive simplices of top dimension are given by the maximal chains: x_{i_{1}} ≥ x_{i_{d}} ≥ … ≥ x_{i_{d}} associated with the poset.

See [32], [17] and also [7] for another construction of triangulations of O(P) taking explicitly into account the simplices in all dimensions.

Theorem 5. For any integral polytope P, there exists an integer k such that kP possesses a primitive triangulation. (Due to Mumford et al., see [20]).

This theorem has a difficult proof, and important applications (to semi-stable reduction, not to toric varieties!). Let t(P) be the minimal integer with the property of the Theorem. Heuristically, the applications show that there is no uniform bound in a given dimension, but they do not go against the following: To P can be associated a fan ∑ and a toric variety X_{Σ} equipped with an ample line bundle L. Let k_{min} be the minimal integer k such that L^{k} is very ample.

Conjecture 1. t(P) = k_{min}.

2.2. Ehrhart polynomial and triangulations. The main conjecture

Let P be an integral polytope in ℝ^{d}. The Ehrhart polynomial i_{P} is clearly invariant by the group G_{d}. Let G_{d} be the pseudogroup associated to G_{d}:

Definition 11. If P and Q are two integral polytopes a map φ : P → Q belongs to G_{d} (or “is locally in G_{d}”) if

(i) φ is a homeomorphism (ii) there exists a rational triangulation T of P (resp. T′ of Q) such that on the interior of each simplex σ of top dimension of T , φ coincides with an element of G_{d}, and φ(σ) ∈ T′.

Proposition 5. The Ehrhart polynomial is invariant with respect to the pseudogroup G_{d}.

Proof. Let φ be as above. The homeomorphism φ preserves Z^{d}: this is clear for integral points which are interior to a simplex of top dimension, because φ coincides there with an element of G_{d}. If the integral point we consider belongs to a face of such a simplex, the image by φ can be expressed by continuity via an element of G_{d} and so is still in Z^{d}.

The same argument applies to the lattices \frac{1}{k} Z^{d}, and shows that they are preserved by φ. This allows to extend φ as

φ_{k} : k P ↦ k Q

in a compatible manner with φ and such that

φ_{k}(k P ∩ Z^{d}) ⊆ k Q ∩ Z^{d} .

Applying the same argument to the inverse of φ shows that

Card(k P ∩ Z^{d}) = Card(k Q ∩ Z^{d}) .

If φ : P → Q is as above, it induces a homeomorphism of the same type φ : k P → k Q. But φ preserves also Z^{d}: this is clear for integral points interior to a simplex on which φ restricts to an element of G_{d}, and one shows by an argument of continuity that it is also true for points on boundary of such simplices.

In dimension two, Peter Greenberg proved the following [16]:

Proposition 6. Let P and Q be two integral polytopes in ℝ^{2}. They have the same Ehrhart polynomial if and only if they are equivalent with respect to G_{2}.

The considerations above, and some computations with the counting functions i_{P} (k, m), led us to the following

Conjecture 2. Let P and Q be integral polytopes in ℝ^{d} such that i_{P} (k, m) = i_{Q}(k, m) for all k and m. Then there is a linear unimodular map sending P to Q.

The situation seems very different in higher dimensions:

Main Conjecture. In dimension three and above, if P and Q are integral polytopes with the same Ehrhart polynomial, in general they are not equivalent under the pseudogroup G_{d}.

In view of Proposition 3, this can be considered as a kind of “Arithmetical Hauptvermutung”: the problem is to find P and Q with numerically equivalent primitive triangulations T and T′, such that T and T′ cannot be refined to rational triangulations T_{1}, T′_{1}, combinatorially equivalent and with all simplices of top dimensions having same volumes (for both).

We will study in detail the arithmetical specificity in dimension 3 in the next paragraph.

3. Hilbert’s third problem for rational polytopes

3.1. Problem

Let P and Q be two integral (resp. rational) polytopes. Under which condition are they equidecomposable? equicomplementable? By this we mean, as in usual scissor congruence framework [30] that we ask whether P and Q can be written:

P = ⋃_{i∈I} P_{i}

Q = ⋃_{i∈I} Q_{i}

with P_{i} and Q_{i} integral, (resp. rational) polytopes with disjoint interior, in finite number, such that

P_{i} = g_{i}(Q_{i}) , g_{i} ∈ G_{d} i ∈ I.

Equicomplementability is defined in a similar way by allowing addition of other polytopes (loc.cit.). This framework is completely analogous to the usual framework of scissor congruence in the classical sense, where the group of motions considered is the group of euclidean motions.

Proposition 7. P and Q rational polytopes are equicomplementable over ℚ if and only if they are equidecomposable.

The proof follows the case of [35], and is valid in a more general framework [30].

3.2. The case of dimension 3: Arithmetical Euler-Poincaré formula

We will use the classification of elementary simplices modulo G_{3} [27], [34].

Proposition 8. Let T_{p,q} be the simplex with vertices the origin and the points A(1, 0, 0), B(0, 1, 0), C(1, p, q) in ℝ^{3}, with 1 ≤ p < q , (p, q) = 1.

1) T_{p,q} is an elementary simplex of volume q/6.

2) Any elementary simplex of ℝ^{3} is equivalent to some T (p, q); T (p, q) and T (p′, q′) are

equivalent if and only if

q = q′ ; p = ±p′ (mod q).

Proposition 9. If σ = T (p, q) is as above, its Ehrhart polynomial is

i_{σ}(k) = 1 + (2 − q/6)k + k^{2} + \frac{q}{6} k^{3}.

Proof. The two coefficients of top degree are easy to compute from the properties of i_{σ}(k); the coefficient a_{1} is determined by writing i_{σ}(1) = 4.

Geometric interpretation: Consider the basic triangle 0AB in ℝ^{2}, and add the point D(1, p, 0):

Figure 2

Consider the cone T′(p, q) of vertex C with basis BDA. By subdividing the trapeze OBDA using OD instead of AB, one gets two different simplices T_{1} = [O, A, D, C] and T_{2} = [O, B, D, C]. It is easy to show that

\begin{aligned}T_{1} & ≡ T′(p, q) \\ T_{2} & ≡ T_{3} = [O, A, B, F] \end{aligned} (G_{3}-equivalence)

where F = (1, 0, q) and T_{3} is independent of p. One gets

T_{1} ∪· T_{2} = T (p, q) ∪· T′(p, q)

(∪· : union with no common interior points) which implies by additivity (the intersection of the simplices are primitive triangles) that the Ehrhart polynomial of T (p, q) is equal to the Ehrhart polynomial of T_{3}.

Other remarkable relations between the T (p, q)’s can be obtained. For example consider the famous decomposition of Euclid of a prism as a union of three simplices [5]. Begin with a simplex T (p, q) and construct a prism by adding two simplices like in Euclid. One gets

\begin{aligned}P & = I × σ \begin{aligned}I & = [O, C(1, p, q)] \\ σ & = \{O, A(1, 0, 0), B(0, 1, 0)\} \end{aligned} \\ P & = T_{p,q} ∪· T′ ∪· T′′, \end{aligned}

where T′ is G_{3}-equivalent to T_{p,q} and T′′ is G_{3}-equivalent to T_{q+1−p,q},

T_{2} = T (β, q − p) modulo G_{3}

with

\begin{aligned}αq & = 1 (mod p) \\ β & = q (mod q − p) \end{aligned}

and σ and σ′ are primitive simplices.

Other decompositions. Another relation can be obtained by adding a point exterior to T (p, q) (as in [2]). One gets T (p, q) ∪· σ = σ′ ∪· T_{1} ∪· T_{2} where T_{1} and T_{2} can be explicitly described. All these relations suggest that there should be some arithmetical invariants of an elementary triangulation (apart from the sum of volumes of the various simplices).

3.3. Maximal triangulations in dimension 3

Let T be a maximal triangulation of the polytope P in ℝ^{3}, and f the f-vector of T .

Theorem 6. (Arithmetic Euler-Poincaré formula) The Ehrhart polynomial of P is

i_{P} (k) = 1 + a_{1}(P)k + (\frac{f_{2}}{2} − f_{3}) k^{2} + V k^{3}

where V is the volume of P and

a_{1}(P) = f_{1} − \frac{3}{2} f_{2} + 2f_{3} − V.

Proof. Consider P as the disjoint union of the relative interiors of simplices of dimension i (of number f_{i} in dimension i), and use the formula:

i_{σ}(k) = \frac{(k + 1) … (k + m)}{m!}.

for a primitive simplex σ of dimension m (for m equals 1 and 2), and proposition 9 for elementary simplices in dimension 3.

Remarks. a) The Ehrhart polynomial does \underline{not} depend on the various volumes of the simplices of dimension 3 which occur in the minimal triangulation.

b) Consider the tetrahedron T in ℝ^{3} with vertices the origin and (a, 0, 0); (0, b, 0); (0, 0, c); the only known formula for the number of integral points in T involves Dedekind sums; here, for small values of the integers a, b, c, Theorem 6 allows to compute this number through triangulations.

4. Dimension four and above. Convex triangulations

The following is proved in [33]:

Theorem. If σ is an elementary simplex of dimension 4, σ has a primitive facet (face of codimension 1).

This means there exists a basis of Z^{4} such that σ can be written as the convex envelope of the following vectors

( \begin{matrix}0 & 1 & 0 & 0 & a_{1} \\ 0 & 0 & 1 & 0 & a_{2} \\ 0 & 0 & 0 & 1 & a_{3} \\ 0 & 0 & 0 & 0 & a_{4} \end{matrix} )

with g.c.d. (a_{1}, a_{2}, a_{3}, a_{4}) = 1

0 ≤ a_{i} < a_{4} i = 1, …, 3 .

The classification of such simplices is still unknown.

Definition 12. A triangulation T of the integral polytope P is said to be convex if the maximal simplices of T correspond to the domains of linearity of a convex function on P.

The set of convex integral triangulations of P can be identified [15] with a finite set of points in ℝ^{N}, and the secondary polytope Q(P) is defined as the convex hull of this set. From [15], we know that the edges of Q(P) correspond exactly to convex integral triangulations of P, and vertices to elementary transformations (called flips or modifications). We have

Proposition 10. Two minimal regular triangulations can be connected by elementary transformations.

This result allows to study problems mentioned above using secondary polytopes. In general elementary transforms of elementary simplices can be elementary or not.

References

[1] Batyrev, V.: Dual polyhedra and mirror symmetry for Calabi-Yau hypersurfaces in toric varieties. J. Alg. Geom., 3 (1994), 493–535.

[2] Betke, V.; Kneser, M.: Zerlegungen und Bewertungen von Gitterpolytopen. J. Reine Angew. Math., 358 (1985), 202–208.

[3] Brion, M.: Polyèdres et réseaux, L’Enseignement Mathématique, 38 (1992), 71–88.

[4] Brion, M.: Points entiers dans les polyèdres convexes d’après Pommershein, Morelli, Kantor-Khovanski, . . .. Séminaire Bourbaki, Mars 1994.

[5] Cartier, P.: Décomposition des polyèdres: le point sur le troisième problème de Hilbert. Séminaire Bourbaki, 646 (1984–1986).

[6] Dais, D.: Enumerative combinatorics of invariants of certain complex threefolds with trivial canonical bundle. Bonner Math. Schriften, 279 (1995).

[7] Destainville, N.; Mosseri, R.; Bailly, F.: Entropy in random tilings: a geometrical analysis in configuration space. ICQ5, World Scientific, 1995, Proceedings of Avignon Conference.

[8] Diaz R. - Robins S.: The Ehrhart polynomial of a lattice n-simplex. Electron. Res. Announc. Amer. Math. Soc., 1996.

[9] Di Francesco, P.; Gaudin, M.; Itzykson, C.; Lesage, F.: Laughlin’s wave functions, Coulomb gases and expansions of the discriminant. International Journal of Modern Physics A, vol.9, 24 (1994), 4257–4351.

[10] Dupont, J.; Sah, C. H.: Homology of Euclidean groups of motions made discrete and Euclidean scissors congruences. Acta Mathematica, 164 (1990), 1–27.

[11] Dupont, J.; Kantor, J.-M.: Scissor Congruence over ℚ. (in preparation).

[12] Ehrhart, E.: Polynômes arithmétiques et méthode des polyèdres en combinatoire. International Series of Numerical Mathematics, 35, Birkhäuser 1977.

[13] Ewald, G.; Wessels, U: On the ampleness of invertible sheaves in complete projective toric varieties. Results Math., 19 (1991), 275–278.

[14] Fulton, W.: Introduction to toric varieties, Princeton Univ. Press.

[15] Gelfand, I. M.; Kapranov; Zelevinsky: Discriminants, resultants and multidimensional determinants, Birkhäuser.

[16] Greenberg, P.: Piecewise SL_{2}ℤ-geometry. Transactions Amer. Math. Soc. 335 2 (1993), 705–720.

[17] Hibi, T.: Algebraic Combinatorics on Convex Polytopes. Carslaw Publications (1992).

[18] Kantor, J.-M.; Khovanskii, A.: Une application du Théorème de Riemann-Roch combinatoire au polynôme d’Ehrhart des polytopes entiers de ℝ^{d}. C.R. Acad. Sci. Paris, 317 I (1993), 501–507.

[19] Kantor, J.-M.; Khovanskii, A.: Integral points in convex polyhedra, combinatorial Riemann-Roch Theorem and generalized Euler Mac-Laurin formula. Preprint IHES, M/92/37.

[20] Kempf, G.; Mumford; Saint Donat: Toroidal Imbeddings. Springer, LNS 339.

[21] Khovanskii, A.; Pukhlikov, A.: The Riemann-Roch Theorem for integrals and sums of quasipolynomials on virtual polytopes. Algebra i Analyz, 4 4 (1992), 186–216.

[22] Khovanskii, A.; Pukhlikov, A.: Finitely additive measures of virtual polyhedra. Algebra i Analyz, 4 2 (1992), 161–185.

[23] Mordell, L.: Lattice points in a tetrahedron and generalized Dedekind sums. J. Indian Math. (New Series), 15 (1951), 41–46.

[24] Morelli, R.: Translation scissors congruence. Adv. Math., 100 1 (1993), 1–27.

[25] Mori, S.; Morrison, D. R.; Morrison, I.: On four-dimensional terminal quotient singularities. Mathematics of Computation 51 184 (1988), 769–786.

[26] Morrison, D.; Stevens, G.: Terminal quotient singularities in dimensions three and four. Proc. Amer. Math. Soc. 90 (1984), 15–20.

[27] Oda, T.: Convex bodies and algebraic geometry. Ergeb. Math. Grenzgeb. Springer-Verlag, 1988.

[28] Pommersheim, J.: Toric varieties, lattice points and Dedekind sums. Math. Ann. 295 (1993), 1–24.

[29] Richter, G.; Ziegler, G.: Universality of polytopes. Bull. Amer. Math. Soc. 1995.

[30] Sah, C. H.: Hilbert’s third problem: scissors congruence. Research Notes in Mathematics 33, Pitman, London 1979.

[31] Siebenmann, L.: Topological manifolds. Actes du Congrès International des Mathématiciens, Nice 1960.

[32] Stanley, R.: Enumerative Combinatorics, Volume I. Wadsworth & Brooks/Cole, Monterey, Calif., 1986.

218 J.-M. Kantor: Triangulations of integral polytopes and Ehrhart polynomials

[33] Wessels, U.: Diplomarbeit, Bochum 1989.

[34] White, G. K.: Lattice polyhedra. Canad. J. Math., 16 (1964), 389–396.

[35] Zylev, V. B.: Equidecomposability of equicomplementable polyhedra. Sov. Math. Dokl. 161 (1965), 453–455.

Received February 6, 1997