Triangulations of integral polytopes, examples and problems(Topology of Holomorphic Dynamical Systems and Related Topics)

Triangulations

of

integral

polytopes,

examples and problems

Jean-Michel KANTOR

We are interested in polytopes in real space of arbitrary dimension, having vertices with integral

co-ordinates: integral polytopes. The recent increase of interest for the study of these $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}$

.

topes and their

triangulations has various motivations;

.

let us mentionthe mainones:

thebeautiful theory oftoric varietieshas built a bridge between algebraic geometryand the

combina-toricsof theseintegralpolytopes[12]. Triangulationsofconesand polytopesoccurnaturally for example

inproblems ofexistence of crepantresolution of singularities $[1,5]$

.

.

The work of the school of$\mathrm{I}.\mathrm{M}$

.

Gelfandon secondary polytopes gives a new insight on triangulations,

with applications to algebraic geometry andgrouptheory [13].

.

In statistical physics, random tilings lead to some interesting problems dealingwith triangulations of

orderpolytopes $[6,29]$

.

With these motivations in mind, we introduce new tools: Generalizations of the Ehrhart polynomial

(counting points “modulo congruence”), discrete length betweenintegral points (and studyingthegeometry

associatedto it), arithmetic Euler-Poincar\’eformulawhichgives, in dimension 3, the Ehrhart polynomialin

terms of the$\mathrm{f}$-vectorofaminimal

triangulation of the polytope (Theorem 7).

.

Finally, let us mention the results in dimension 2 of the late PeterGreenberg, they led us to the study

of “Arithmetical $\mathrm{P}\mathrm{L}$-topology” which, we believe with M. Gromov, D. Sullivan, and P. Vogel, has not yet

revealed allits beauties. We thank these mathematicians for their interest, and Professor Ito for his kind

invitationto the Seminar at R.I.M.S. in October 1995, where part of these results where given.

I Polytopes; counting integral points; triangulations.

I.1.

Definition 1. A polytope $P$ in$\mathbb{R}^{d}$ is theconvexhull ofa

finite numberofpoints $\{A_{1}, \ldots A_{n}\}$

.

The set ofverticesVert$(P)$ is asubset of$\{A_{1}, \ldots A_{n}\}$

.

The polytope $P$ is called integral (resp. rational) ifthe $A_{i^{\mathrm{S}}}$’ canbe chosen in$\mathbb{Z}^{d}$ (resp. in$\mathbb{Q}^{d}$).

Definition 2. The polytope $P$ is said to be elementary if

$\mathrm{v}_{\mathrm{e}}\mathrm{r}\mathrm{t}(P)=P\cap \mathbb{Z}^{d}$

.

These polytopes have also been called “free-lattice polytopes”.

Denote by

$\mathrm{G}_{d}=\mathbb{Z}^{d}\ltimes GL(d, \mathbb{Z})$

thegroupofaffine unimodular maps (affine linear isomorphisms preservingthe lattice $\mathbb{Z}^{d}$).

Lemma 1 and definition 3. Let $\sigma$ be an integral simplexin $\mathbb{R}^{d}$. The following conditions are

equivalent: 1) $\sigma=g(\sigma_{\mathrm{c}\mathrm{a}\mathrm{n}})$,

where $g$is in $\mathrm{G}_{d}$ and $\sigma_{\mathrm{c}\mathrm{a}\mathrm{n}}$isthebasicsimplex with vertices the origin and

$\{A_{i}=(0,..,$$\mathrm{o},$$1,$ $\mathrm{o}-_{1}i-\cdot,$$\ldots,$

$0);?$.$=1,$$\ldots,$$d\}$

2) Theverticesofa generate $\mathbb{Z}^{d}$

.

Elementary simplices.

Elementary simplices arewell knownindimensionupto three (see III.1). Theycoincide with primitive

simplicesin dimension 1 and 2. Some partial results areknown indimension4 [26].

I.2. The Ehrhart polynomial. Let $P$be an integral polytope.

Theorem 1. $[10,3]$ For any integer $k$, let

$i_{P}(k)=\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\{kP\cap \mathbb{Z}^{d}\}$

.

1) $i_{P}$ is a polynomial in $k$ ($k$ in $\mathbb{N}$),

2) The values of this polynomialat negative $k$ are given by

(1) $i_{P}(-k)=(-1)^{m}\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(kP^{0}\cap \mathbb{Z}^{d})$

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 Ehrhartpolynomial 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+\cdots+a_{d}(P)k^{d}$

where

(2) $\{$

$a_{d}(P)=V(P)$, volumeof $P$

$a_{d-1}(P)= \frac{1}{2}\sum V_{d-1}(F)=\frac{1}{2}V_{d-1}(P)$

$\mathrm{s}\mathrm{u}\mathrm{I}\mathrm{I}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}_{0}\mathrm{n}$ overall facets $F$of$P,$ _{$V_{d-1}$} denoting the volume of each facet with respect to the lattice induced

by$\mathbb{Z}^{d}$ on

the affine space generated by this facet.

Properties ofothercoefficients arestill mysterious [3.15,17].

I.3. Weintroduce new countingfunctions.

Let $m$be an integer and:

$\Pi_{m}$ :$\mathbb{R}^{d}arrow \mathbb{R}^{d}/m\mathbb{Z}^{d}$

the quotient map.

Definition 4. For anycouple ofintegers$m$ and$k$, define:

(3) $i_{P}(k,, m)=\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}\Pi_{m}(kP\cap \mathbb{Z}^{d})$

The functions $i_{P}(k, m)$ count integral points in $kP$ “modulo$m$”, and

$i_{P}(k, 0)=i_{P}(k.)$,

Proposition 1.

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

for any$g$ in $GL(d, \mathbb{Z})$

.

Proof.

1) It isenough to considertwo cases:

a) $g(x)=x+a,$ $a\in \mathbb{Z}^{d},$ $Q=P+a$

.

Then

$\Pi_{m}(kP\cap \mathbb{Z}^{d})=\mathrm{I}\mathrm{I}_{m}(kP\cap \mathbb{Z}^{d})+\mathrm{I}\mathrm{I}_{m}$($k$a).

b) $g=A\in \mathrm{G}\mathrm{L}(d, \mathbb{Z})$

.

$A$induces abijection:

$\tilde{A}$

: $\mathbb{R}^{d}/m\mathbb{Z}^{d}arrow \mathbb{R}^{d}/m\mathbb{Z}^{d}$

sending $\Pi_{m}(kP\cap \mathbb{Z}^{d})$ to $\Pi_{m}(kA(P)\cap \mathbb{Z}^{d})$

.

Proposition 2.

Suppose $\Pi$ hasanintegral interior point. Then there exist tworationals $\alpha$ and $\beta$ such that:

$k>m\alpha\Rightarrow i_{P}(k, m)=m^{d}$ $k<m\beta\Rightarrow i_{P}(k, m)=i_{P}(k)$

From this one deduces the existence of two critical lines in the plane $(k, m)$ $L_{1},$ $L_{2}$ with the following

properties:

in region 1, $\dot{i}_{p}$is the Ehrhart polynomial

in region 2, $i_{p}$is $m^{d}$

in region 3, $i_{\mathrm{p}}$is unknown

Proof:

1) Suppose the interior pointis at the origin; let $\alpha$ be such that

$\alpha>0$,

$x=(x_{i}),$ $0\leq x_{i}<\alpha\Rightarrow x\in P$

.

If$(m-1)<k.\alpha$:

$0\leq x_{i}\leq m-1\Rightarrow x\in kP$

$kP\cap \mathbb{Z}^{d}\supseteq[0, m-1]^{d}$

and thissubset contains all equivalence classes modulo $m$.

2) We introduce discrete analogs of euclidean lengths:

Definition 5

1) If$a$and $b$are in $\mathbb{Z}^{d}$,

the discretelength _between$a$ and $b$is

$d(a, b)=\mathrm{c}_{\mathrm{a}\mathrm{r}}\mathrm{d}([a, b)\cap \mathbb{Z}^{d}]-1$

2) The discretediameter ofan integral polytopeis

$D(P)= \sup_{a,b\in P}d(a, b)$

.

The function$d$is not a distance!

Now noticethat iftwo integralpoints $x$ and $x’$ satisfy

$x-x’=mu,$

$u\in \mathbb{Z}^{d},$ _{$u\neq 0$}

then:

$x’+iu\in[X, X^{;}],$ $i=0,$$\ldots,$$m$,

$(*)$ $d(X, X’)>m$

.

In particular, if

$m>D(P)$,

$(*)$ cannot be satisfied for points in $P$

.

Remark now that

$d(ka, kb)\geq kd(a, b)$,

and deduce that

$\frac{m}{k}$

.

$>D(P)\Rightarrow i_{P}(k, m)=i_{P}(k)$

.

Valuations. Let $A$ be any abelian group.

Definition 6. A map

$\varphi$: $P_{d}arrow A$

is said to be additive, or a valuation on$P_{d}$, ifwhenever$P,$$Q,$ $P\cup Q,$ $P\cap Q$ are integral polytopes,

$\varphi(P\cup Q)+\varphi(P\cap Q)=\varphi(P)+\varphi(Q)$

.

Thefollowingwas proved in [2]:

Theorem 2. If$\varphi$ is any valuationinvariant under $G_{d}$, with values in $A$, then there exist unique elements

$\alpha_{i}$ in $A$ suchthat

$\varphi(P)=\sum_{j=0}^{d}\alpha ji(pj)$

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

The proofconsists in studyingthe group

$\mathrm{I}\mathrm{I}=\mathbb{Z}[Pd]/\sim$

where $P_{d}$ is the set of all integral polytopesin$\mathbb{R}^{d}$

, and $\Pi$ isthe quotient of the free abeliangroup on

$P_{d}$ by

the equivalence relation generated by

(4) $\{$

$[P]=(g(P)],$ $g\in G_{d}$

$[P\cup Q]=[P]+[Q]-[P\cap Q]$ if$P,$$Q,$$P\cup Q\in P_{d}$.

Remark. The functions$i_{P}(m, k)$ are not additive. Takefor 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}\cup I_{2}}(k, 2)=2$

I.4. Triangulations. The only triangulationsweconsiderare triangulationsby rationalor integralsimplices

(the triangulations arethen calledrational or integral).

Definition 7. A triangulation$\mathcal{T}$ of thepolytope $P$ is called

primitive if all simplices are (integral) primitive simplices

minimal if all simplices areelementary.

It is easy to see thatminimal triangulations are minimalwithrespect to the natural partial orderonthe set

of integral triangulations.

Definition 8. If$\mathcal{T}$ is any triangulation, call

$f$-vector of$\mathcal{T}$ the vector $f=(f_{i})$, where $f_{i}$ is the number of

simplicesofdimension $i$

.

Lemma 4. If the integral polytope $P$ has a primitive triangulation $\mathcal{T}$, the Ehrhart polynomial

$i_{P}$ is

determined bythe $f$-vector $f(\mathcal{T})$, and conversely.

Proof:

Consider $P$ asthe disjoint union of the relative interiors of simplices of dimension $i$ (of number $f_{i}$ in

dimension i), and use the formula:

$i_{m}(k.)=’ \frac{(k+1)\ldots(k+m)}{m!}.$ ,

then:

$i_{P}(k)= \sum f_{j()}-1ji_{j}(-k)$

.

Proposition 3. Let $P$ and $Q$ be two integral polytopes. The followingconditions are equivalent:

(i) $P$ and $Q$ have thesame Ehrhart polynomial.

(ii) There exists a $k$, such that _$kP$ and _$kQ$ have the sameEhrhart polynomial.

(iii) For all $k,$ $kP$ and $kQ$ have the same Ehrhart polynomial.

Moreover, if$P$ and $Q$ have primitive triangulations$\mathcal{T}_{P}$ and $\mathcal{T}_{Q}$ the conditions above are also equivalent to

$f(\mathcal{T}_{P})=f(\mathcal{T}Q)$

$\mathcal{T}_{P}$ and $\mathcal{T}_{Q}$ are said to be numerically equivalent.

Proof:

Thefollowingis obvious:

$i_{kP}(n)=i_{P}(kn)$ , for all $k$ and_$n$

.

From this onededuces, usingthe polynomial character of$i_{P}$:

$(i)\Rightarrow(iii)\Rightarrow(ii)\Rightarrow(i)$

I.5. Given a polytope $P$, it is a difficult question to decide whether there exist primitive triangulations of

$P$

.

Let usremarkthatthe proof of theorem 2(see [2])shows that primitive triangulations$\mathrm{e}\mathrm{x}\mathrm{i}_{\mathrm{S}\mathrm{t}}\underline{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{b}1_{\mathrm{Y}}}$, that

is if replacing $P$ by$P\cup Q$,for some $Q$

.

1) Example: Order polytopes [29].

If$O$is afinite poset of$d$elements (partially ordered set):

define $P(\mathrm{O})$ to be the set of all points in$\mathbb{R}^{d}$ such that

$P(\mathrm{O})=\{x=(x_{1}, \ldots, x_{d});x\in \mathbb{R}^{d}\}$

$P(\mathrm{O})$ is an integral convex polytope of dimension $d$, whosevertices correspond to the set $\mathcal{L}(P, 1)$ ofmaps

$\sigma$ : $\mathrm{O}arrow\{0,1\}$such that

$y_{1}<y_{2}$ in $O\Rightarrow\sigma(y_{1})\geq\sigma(y_{2})$.

Theorem 3. $P(\mathrm{O})$ has acanonical primitive triangulation.

The primitivesimplices of top dimension are givenby the maximal chains:

$x_{i_{1}}\geq x_{i_{d}}\geq\ldots\geq x_{i_{d}}$

associated with the poset.

See [6] for another construction of triangulations of$\mathrm{O}(P)$ giving explicitly the number of simplices in

all dimensions.

2) The following result is provedin [16]:

Theorem 6. For any integral polytope $P$, there exists an integer $k$ such that $kP$ posesses a primitive

triangulation.

Let $t(P)$ bethe minimal integerwith this property.

$\mathrm{L}\mathrm{e}\mathrm{t}\mathcal{L}$

.

us recall [12] that to

$P$ is associated a fan$\sum$and atoric variety$X_{\Sigma}$ equippedwithan ample linebundle

Let $k_{\min}$ be the minimal integer$k$ suchthat $\mathcal{L}^{k}$

’

isvery ample.

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

.

It wasnoticed by B. Sturmfels (unpublished) that an example from [11] shows that

$t(P)\geq\dim P-1$

in general.

I.6. Ehrhart polynomialand triangulations: the main conjecture. Let $P$ beanintegral polytope in

$\mathbb{R}^{d}$.

The Ehrhart polynomial $i_{P}$ is clearly invariant by thegroup $G_{d}$

.

Let $\mathcal{G}_{d}$be the pseudogroup associated to $G_{d}$ and $P$ and $Q$ twointegral polytopes.

Definition

.

7.

Amap $\varphi$ :$Parrow Q$ belongsto $\mathcal{G}_{d}$ (or “is locally in $G_{d}$”) if

$\varphi$ is ahomeomorphism

.

thereexists a rational triangulation $\mathcal{T}$of$P$ (resp. $T’$ of$Q$) such that on the interior of each simplex a

of top dimension of$\mathcal{T},$

$\varphi$ coincides with an elementof$G_{d}$, and

$\varphi(\sigma)\in \mathcal{T}’$

.

Proposition 4. The Ehrhart polynomial isinvariant with respect to the pseudogroup $\mathcal{G}_{d}$

.

Proof:

Let $\varphi$ be as above. The homeomorphism $\varphi$ preserves

$\mathbb{Z}^{d}$: this is

clear for an integral point $a$which is

interior to asimplex of top dimension, because $\varphi$ coincides there with an elenlent of$\mathrm{G}_{d}$

.

If$a$ belongs to a

face of such asimplex, $\varphi(a)$ can be expressed by continuity via an element of$\mathrm{G}_{d}$ and so is stillin $\mathbb{Z}^{d}$.

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

to extend $\varphi$ as

in acompatible manner with $\varphi$ and with

$\varphi_{k}(kP\cap \mathbb{Z}^{d})\subseteq kQ\cap \mathbb{Z}^{d}$

.

Applyingthe same argument tothe inverseof$\varphi$shows that

Card$(kP\cap \mathbb{Z}^{d})=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(kQ\cap \mathbb{Z}^{d})$

.

In dimension two, Peter Greenbergproved the following [14]:

Proposition 8. Let $P$ and $Q$ be two integral polytopes in $\mathbb{R}^{2}$

.

They have

the same Ehrhart polynomial if

and only ifthey areequivalent withrespect to $\mathcal{G}_{2}$

.

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

fol-lowing

Conjecture 2. Let $P$ and $Q$ be integral polytopes in $\mathbb{R}^{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$.

(Main) Conjecture 3. Indimensionthree

and

above,it is not truein general that if$P$and $Q$ areintegral

polytopes with the same Ehrhart polynomial, they are equivalent by the pseudogroup $\mathcal{G}_{d}$

.

Remark. In view ofProposition 3, this can be considered as a kind of “Arithmetical Hauptvermutung”:

the problem is to find $P$ and $Q$ with numerically equivalent primitive triangulations $\mathcal{T}$and $\mathcal{T}’$, such that $\mathcal{T}$

and$\mathcal{T}’$ cannot be refined to rational triangulations

$\mathcal{T}_{1},$ $\mathcal{T}_{1}’$, combinatoriallyequivalent and with all simplices

of topdimensions having samevolumes (for both).

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

II. Hilbert’s third problem for rational polytopes.

Problem. Let $P$ and $Q$ be two integral (resp. rational) polytopes. Under which condition are _they

equidecomposable? equicomplementable?

As in usual scissorxcongruence framework [24], $P$ and $Q$ are equidecomposableifthere existsubdivisions:

$P=\cup P_{i}i\in I$ $Q= \bigcup_{i\in I}Qi$

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

$P_{i}=gi(Q_{i})$

,

$g_{i}\in G_{d}$ $i\in I$

.

Equicomplementability is defined in a similar way, allowing addition of other polytopes (loc.cit.). This is

completely analogous to the usual framework ofscissor congruence in the classical sense, but the groupof

motions considered is here thegroupof unimodular mappings.

Proposition 9. $P$ and $Q$ rational polytopesare equicomplementableover$\mathbb{Q}$ if and only if they are

equide-composable.

The proof of Zylev [28] adaptswithout anydifficulty to this situation.

Remark: Scissorcongruence as definedabovedoes not preserve cotlntingpoints. A continuitycondition is

III. The case ofdimension 3: Arithmetical Euler-Poincar\’e formula.

III.1. Wewill usetheclassificationof elementary simplices modulo $G_{3}$ $[21,27]$.

Proposition 10. Let $T_{p,q}$ be the simplex with vertices the origin and the points $A(1,0,0),$ $B(\mathrm{O}, 1,0)$,

$C(1,p, q)$ in $\mathbb{R}^{3}$, with

$1\leq p<q,$ $(p, q)=1$

.

1) $T_{p,q}$ is an elementary simplexof volume $\mathrm{q}/6$

.

2) Any elementary simplex of$\mathbb{R}^{3}$ isequivalent to some$T(p, q)$;

$T(p, q)$ and $T(\mathrm{P}’, q)’$ are equivalent if and only if

$q=q’$ ; $p=\pm p’$ _(mod$q$).

Themain pointin the proofconsistsin provingthat any elementary simplex$\sigma$ indimension3 haswidth

equal one, where the width is defined by

$w(\sigma)=\mathrm{i}\mathrm{n}\mathrm{f}u\in \mathrm{Z}^{3}$

.

$D[u(\sigma)]$

.

Proposition 11. If$\sigma=T(p, q)$ is as above, its Ehrhart polynomial is

$i_{\sigma}(k)=1+(2-q/6)k+k^{2}+ \frac{q}{6}k^{3}$

.

Proof:

Thetwocoefficients of top degree are easyto compute from the properties of$i_{\sigma}(k)$; the coefficient $a_{1}$ is

determinedby writing

$i_{\sigma}(1)=4$

.

Geometric interpretation. Considerthe basic triangle $\mathrm{O}AB$ in $\mathbb{R}^{2}$, and add the point $D(1,p, 0)$:

$T(p, q)$ is the pyramid

over

$\mathrm{O}AB$

with vertex$C(1, p, q)$.

Considerthecone$T’(p, q)$ ofvertex$C$with basis _$BDA$

.

By subdividing the trapezeOBDA using$\mathrm{O}D$ instead

of $AB$, one gets two different simplices $T_{1}$ and $T_{2}$

.

It is easy to show that all $T_{1},$ $T_{2}$ and $T’(p, q)$ are

$G_{3}$-equivalent to the simplex

$T(q)=[0, A, B, E(\mathrm{o}, 0, q)]$

.

Denoting by the same symbol$\tau_{1},$$\tau_{2},$$T’(p, q)$ by$T(q)$ one gets

($\mathrm{U}$: union with no common interiorpoints) whichimplies by additivity(the intersection

of the simplicesare

primitivetriangles) that the Ehrhart polynomialof$T(p, q)$ is equalto theEhrhart polynomial _of$T(q)$

.

$.$.

Other remarkable relations between the $T(p, q)’ \mathrm{S}$ can be obtained. For example consider the famous

decomposition of Euclid of a prism as a union of three simplices [4]. Begin with a simplex $T(p, q)$ and

construct a prism by adding two simplices likeinEuclid. One gets

$P=I\cross\sigma$ _{$I=[0, C(1,p, q)]$}

$\sigma=\{0, A(1, \mathrm{o}, \mathrm{o}), B(\mathrm{o}, 1, \mathrm{o})\}$

$P=T_{p,q}\cup T’\cup T’’$

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(\beta, q-p)$ modulo $G_{3}$

with

$\alpha q=1$ (mod$p$)

$\beta=q$ (mod_$q-p$)

and $\sigma$ and $\sigma’$ areprimitive simplices.

Other decompositions. Another relationcanbe obtained byaddingapoint exterior to$T(p, q)$ (asin [2]).

Onegets

$T(p, q)\mathrm{U}\sigma=\sigma\cup T_{1}’\cup\tau 2$

where$T_{1}$ and$T_{2}$ can be explicitly described.

All these relations suggestthat there should besome arithmetical invariants ofan elementary triangulation

(apart from the sumofvolumes of thevarious simplices).

III.2. Minimal triangulations in dimension 3. Let $T$be aminimal triangulation of the polytope $P$ in

$\mathbb{R}^{3}$,

and $f$ the $f$-vectorof$\mathcal{T}$

.

Theorem 7. (Arithmetic Euler-Poincar\’eformula).

The Ehrhart polynomial of$P$is

$i_{P}(k)=1+a_{1}(P)k+( \frac{f_{2}}{2}-f_{3})k^{2}+Vk^{3}$

.

where $V$is the volume of$P$ and

$a_{1}(P)=f1- \frac{3}{2}f_{2}+2f_{3}-V$

.

Proof:

Results from the proof of lemma 4 and proposition 11 in dimension 3.

Remarks. a) The Ehrhart polynomial$\mathrm{d}_{\mathrm{o}\mathrm{e}\mathrm{S}\underline{\mathrm{n}}}\mathrm{o}\mathrm{t}$dependonthevariousvolumes of the simplices ofdimension

3 whichoccurin theminimaltriangulation.

b) Considerthe tetrahedron $\mathrm{T}$ in $\mathbb{R}^{3}$

withvertices the origin and

$(a, 0, \mathrm{o});(0, b, 0);(0,0, c)$;

The only known formula for the number of integral points in $\mathrm{T}$ involves Dedekind sums; [17.24] here, for

IV. Dimension four and above: Convex triangulations.

IV.1 The following is proved in [26]:

Theorem If$\sigma$ isan elementary simplex of dimension4, a has a primitivefacet (faceofcodimension 1).

Thismeans thereexists abasis of$\mathbb{Z}^{4}$such that

$\sigma$ canbewritten as theconvexenvelope of thefollowing

vectors

with $\mathrm{g}.\mathrm{c}.\mathrm{d}.(a_{1}, a2, a3, a4)=1$

$0\leq a_{i}<a_{4}$ _{$i=1,$$\ldots,$}$3$

.

The classificationof such simplices isstill unknown. In particular:

Conjecture 4.

Elementary simplices in dimension4 have width less orequal to two.

Definition 8. A triangulation $\mathcal{T}$ of the integral polytope $P$ is said to be convex (projective in [16]) if the

maximal simplices of$\mathcal{T}$ correspond to the domains of linearity ofa convex functionon $P$

.

The set ofconvex integral triangulations of $P$ can be identified with a finite set of pointsin $\mathbb{R}^{N}$, and

the secondary polytope $Q(P)$ is defined as theconvexhull ofthis set. From [13], we know that the edges of

$Q(P)$ correspond exactly to elementarytransformations (called flips or modifications). Wehave

Proposition 13. 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 simplicescanbe elementary or not.

We hope tocome back to this.

REFERENCES

[1] BATYREV V.; Dual polyhedra and mirrorsymmetry forCalabi-Yauhypersurfacesin toricvarieties, J.

Alg. Geom., 3 (1994), 493-535.

[2] BETKE V., KNESERM.; Zerlegungen und Bewertungen von Gitterpolytopen, J. Crelle, 358 (1985),

202-208.

[3] BRIONM.; Poly\‘edres et r\’eseaux, L’Enseignement Math\’ematique, 38 (1992), 71-88.

[3] BRION M.; Points entiers dans les poly\‘edres convexes d’apre‘s Pommershein, Morelli,

Kantor-Khovan-ski,

. .

., S\’eminaire Bourbaki, Mars 1994.

[4] CARTIER P.; D\’ecomposition des poly\‘edres: le point sur le troisi\‘eme probl\‘eme de Hilbert, S\’eminaire

Bourbaki, 1984-85, $\mathrm{n}^{0}646$

.

[5] DAIS D.; Enumerative combinatorics

_of

invariants

_of

certain complex

_threefolds

with trivial canonical

bundle, Bonner Math. Schriften,$\mathrm{N}^{0}279$, Bonn 1995.

[6] DESTAINVILLE-MOSSERI,BAILLYF.; Entropy in random tilings: a geometrical analysis in

config-uration space, ICQ5, World Scientific, 1995, Proceedings ofAvignon Conference.

[7] DI FRANCESCO, GAUDIN M., ITZYKSON C., LESAGE F.; Laughlin’s wave functions, Coulomb

gases and expansionsof the discriminant, InternationalJournal

_of

Modern Physics A, vo1.9, 24 (1994),

[8] DUPONT J.L., SAH C.H.; Homology of Euclidean groups of motions made discrete and Euclidean

scissors congruences, Acta Mathematica, 164 (1990), 1-27.

[9] DUPONT J., KANTORJ.-M.; Scissor Congruence over$\mathbb{Q}$, inpreparation.

[10] EHRHARTE.;Polyn\^omes arithm\’etiques etm\’ethodedes poly\‘edresencombinatoire,InternationalSeries

of

Numerical Mathematics, 35, Birkha\"user

_1977.

[11] EWALD, WESSELS; On the ampleness of invertible sheaves in complete projective toric varieties,

Resultate-Math., 19 (1991), no. 3-4,

275-278.

[12] FULTONW.; Introductionto toric varieties, Princeton Univ. Press.

[13] GELFAND I.M., KAPRANOV, A. ZELEVINSKY; Discriminants, resultants and multidimensional

de-terminants, Birkha\"user.

[14] GREENBERG P.; Piecewise $SL_{2}\mathbb{Z}$-geometry, Transactions Amer. Math. Soc. 335, 2 (Feb. 1993),

705-720.

[15] KANTORJ.-M., KHOVANSKII A.; Une application du Th\’eor\‘eme de Riemann-Rochcombinatoire au

polyn\^ome d’Ehrhart des polytopes entiers de1R

d,

C.R. Acad. Sci. Paris, t.317, I (1993), 501-507.

[16] G.KEMPF; MUMFORD, SAINT DONAT, ToroidalImbeddings, Springer, LNS 339.

[17] MORDELL; Lattice points in a tetrahedron and generalized Dedekind sums, J. Indian Math. (New

Series), 15, (1951), 41-46

[18] MORELLIR.; Translationscissors

congruence,

Adv. in Mathematics, 100, 1 (July 1993), 1-27.

[19] MORI S., MORRISON D.R., MORRISON I.; On four-dimensional terminal quotient singularities.

Mathematics

_of

Computation 51 (1988), no. 184, 769-786.

[20] MORRISON D.R., STEVENS G.; Terminal quotient singularities in dimensions three and four.

Pro-ceedings

_of

the Amer. Math. Soc. 90 (1984), no. 1, 15-20.

[21] ODA T.; Convex bodies and algebraic geometry, Ergebnisse, Springer-Verlag, 1988.

[22] POMMERSHEIM J.; Toric varieties, lattice points and Dedekind sums. Mathematische-Annalen 295

(1993), no. 1, 1-24.

[23] RICHTER G., ZIEGLERG.; Universality of polytopes, B.A.M.S., Oct. 1995.

[24] SAH C.H.; Hilbert’s third problem: scissors congruence,Research Notes inMathematics, 33, PitmanP.,

London, 1979.

[25] SIEBENMANN L.; Topological manifolds, Actes du Congr\‘es International des Math\’ematiciens, Nice

1960.

[26] WESSELS U.; Diplomarbeit, B\"ochum _1989.

[27] WHITE G.K.; Lattice polyhedra, Canad. J. Math., 16 (1964), 389-396.

[28] ZYLEV V.B.; Equidecomposability of equicomplementable polyhedra, Sov. Math. Dokl., 161 (1965),

453-455.

J.-M. Kantor

$\mathrm{e}$-mail: [email protected]

INSTITUT DE MATHEMATIQUES

UNIVERSIT\’E

PIERRE ET MARIE CURIE

Case

247

4, Place $J$ussieu