Lattice polytopes: some open problems

Jean-Michel Kantor

Jean-Michel KANTOR (IMJ, Paris 7-Diderot)

I. Empty polytopes I.1. Definition and general results I.2. Width and classification in dimension 3, and extensions. II. Special empty simplices III. Problems related to triangulations III.1. Scaling III.2. Ehrhart polynomial and classification III.3. Rationale polytopes

Introduction

It is a pleasure to thank the organizers of the AMS Snowbird Conference of July 2003 for their kindness and efficiency in bringing together young enthousiasts and (sometimes older) specialists of lattice polytopes.

Our personal interest is in geometrical combinatorics of lattice polytopes.We assume here for simplicity integral polytopes with vertices in the integral lattice ℤ^{d}. Since the birth of toroidal geometry a strong connection has been established between geometric combinatorics of polytopes, algebraic geometry and singularity theory.

This survey aims at pointing interesting links and connections between combinatorics, algebraic geometry and moreover number theory, at the occasion of lattice polytopes... and of Snowbird.

I. Empty polytopes

I.1. Definition and general results

Definition 1. An empty simplex is an integral simplex with no other integral point.

We will call arithmetical volume (or sometimes volume) the volume with respect to the basic simplex (of euclidean volume 1/d!).

Examples :

1. In dimension one (resp. two) empty simplices are exactly those which generate the lattice, or equivalently have area 1 (resp. 1/2).

2. In all dimension an interesting family of examples is given by the class of Delaunay-Voronoï polytopes constructed via the “empty sphere” method and originally introduced in connection with cristallography [B_{1}, De, Du, ER].

Definition 2.

Barycentric coordinates (Reznick)

If

Σ = [0, v_{1}, …, v_{d}]

is a simplex of full dimension d and arithmetical volume D and C the cone with vertex at the origin generated by Σ, any point M of C can be expressed in a unique way as

M = \frac{1}{D} ∑ λ_{i}v_{i}, λ_{i} ≥ 0.

The λ_{i}’s are called barycentric coordinates of the point x The sum s(x) = Σλ_{i} is called the barycentric sum of x.

Lemma 1. σ is empty iff no integral point x has barycentric sum strictly less than d.

I.2. Width and classification in dimension 3;

Empty simplices can have unbounded volume in any fixed dimension superior to 3 (see Proposition 3). However:

Definition 3. Given a dual element u in (ℤ^{d})^{⋆} the width of P in direction u is the quantity

w_{u}(P) = max{u(x) − u(y), x, y ∈ P }

The width of P is

w(P) = min{w_{u}(P); u ∈ (ℤ^{d})^{⋆}\{0}}.

In a given dimension there exists a uniform bound for the width:

Theorem 1. For a fixed dimension d there exists a uniform bound C(d) for all empty polytopes:

w(P) ≤ C(d)

for all empty polytopes P in dimension d.

The first proof of this result is due to Khinchine [Kh], (for convex compact bodies with no integral points), and was used for studying simultaneous diophantine approximations.

Remark. The first proof that C(d) goes to infinity with d was given in [K], then many more examples were found [HZ,Se]. The current best result for C(d) is

C(d) ≤ d^{3/2}

[BL]

Problems:

– Compute C(4)

– Give refined estimates on the width in connection with the arithmetical volume.

Partial results can be found in [HZ], and asymptotic estimates on the number of classes of simplices with given volume can be found in [BK].

Proposition 3. (White’s lemma)[Wh] Any empty simplex of dimension 3 has width 1.

Corollary. Any simplex S of dimension 3 is equivalent to an empty simplex with vertices the origin and the points

( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & p & q \end{matrix} )

where

(p, q) = 1, 0 ≤ p ≤ q

and q is the volume of S. The unimodular case corresponds to

p = 0, 1 and q = 1

otherwise 1 ≤ p ≤ q

Various proofs exist,from the simplest to the more elaborate one using elementary properties of the Bernoulli function B_{1} [MS].

Let

x_{i} = \frac{a_{i}}{D} , a_{i}, D ∈ ℕ^{⋆},

with

0 < x_{i} < 1, (a_{i}, D) = 1.

Let

((x)) = B_{1}(x) = \{ \begin{matrix}x − [x] − \frac{1}{2} if x ∈ ℤ, \\ 0 otherwise. \end{matrix}

Theorem 2

The following assertions are equivalent

a)

Σ((kx_{i})) ≥ 0 for all k ∈ ℤ, or equivalently k = 1, ....D − 1

b)

∑_{i=1}^{m}((kx_{i})) = O for all k = 1, ...D − 1

c) There exists an involution τ : {1, ...m} → {1, ...m}, τ^{2} = Identity such that

a_{i} + a_{τ(i)} ≡ 0 (mod D) .

The difficult part is the proof of the implication from b to c. It relies on a hard technical result proved by Miles Reid (see [Rei], p. 380 and Appendix).

Remark. [ Se_{1}].

In dimension three, White’s lemma gives the classification of empty simplices. In higher dimensions however the result above only implies the description of empty parallelotopes.

II. Special empty simplices

The classification of empty simplices seems intractable in higher dimensions. Two type of arguments can be called, one from algebraic geometry and one from complexity theory. First,via Mori’s work, the role of terminal singularities (singularities with special type of resolution) has become crucial [MS,Rei]. Miles Reid described terminal singularities in dimension 3 and 4 that are terminal, generalizing the combinatorial description which in dimension 3 amounts to the classification of empty simplices. In higher dimension the structure of terminal singularities turns out to be extremely complicated [S]. It is natural to restrict to some particular classes, still more general than the Delone- type which are too restricted (for example they have small width) :

Definition 4.

A simplex is a special empty simplex if

– it is an empty simplex

– it has a unimodular facet.

This facet is not unique (for example in dimension 4 any empty simplex has two such facets ([HZ]) In particular after a choice (not unique) of basis e_{i} the simplex can be written

Σ(u) = [u; e_{i}, i = 1...d − 1]

where u is some lattice vector.

Problem. Give a complete classification of special empty simplices using the results above.

III. Problems related to triangulations

III.1. Scaling

Any lattice polytope posesses a triangulation made of empty simplices (this is easy to proof), but not necessarily with unimodular simplices. However

Theorem 3. [KMS] For any lattice polytope P there exists an integer N = N(P) such that

(∗)N.P posesses a unimodular triangulation.

Equivalently, by increasing the lattice from ℤ^{d} to \frac{1}{N} ℤ^{d} permits to find a unimodular triangulation.

The proof is technical and relies on the notion of Waterman point which is connected with the dual description to barycentric coordinates (see [KMS]) but it gives no information on the dependance of N(P) on P in a given dimension.

In particular, let M(P) be the minimum integer M -if it exists- such that (*) is true for all integers at least equal to M;

Conjecture :

N(P) ≤ M(P) ≤ K(d)

where K(d) is a constant depending on d only, and the inequalities can be strict.

Example 3 (due to B.Sturmfels). Consider the parallelotope Π generated by d integral primitive independent vectors.

Proposition [EW] Any lattice point in Π is a non-negative linear combination of integral points in Π with barycentric sum less or equal to

k = (d − 1),

but this is not true,in general, for any smaller k.

Using this, take the special simplex S(r) associated with u = (1, ...; r). One can deduce from the Proposition that kS(r) cannot have any unimodular triangulation for

k < (d − 1), r ≥ 0.

In dimension 3 however

Theorem. [K.S.] N(P) = 2, 3 or 4. More precisely

1) N(T (p, q)) = 2 iff p = 1 or q − 1

2) N(P) = 3 or 4 for any lattice polytope of dimension 3

III.2. Ehrhart Polynomial and classification

We will use freely well-known results concerning the Ehrhart polynomial (resp. quasipolynomial) -of an integral (resp.. rational) polytope (see [E,St]).

Definition 4[G]

1) A map ϕ is a ℤ piecewise -linear unimorphism iff

– It is a homeomorphism with compact support (ϕ is the identity at infinity)

– There exists a unimodular triangulation such that ϕ is locally a unimodular isomorphism with respect to these triangulations.

2) ϕ is a ℚ piecewise-linear unimorphism over ℚ iff there exists an integer N such that φ̃ defined by

φ(Nx) = N φ̃(x)

is a ℤ piecewise-linear unimorphism.

Case of dimension 2: Theorem 5 [ G] Two lattice polygons P and Q are P L-equivalent over ℤ under the above (obvious) equivalence relation iff they have the same Ehrhart polynomial.

The proof is by induction on the area of P. In higher dimension,this is an open area:

Conjecture and example. P and Q have the same Ehrhart polynomial iff they are P L-equivalent over ℚ.

The example to test is the T (p, q) which has a Ehrhart polynomial independant of p !

III.3. Rationale polytopes

Another type of problems on the Ehrhart quasi- polynomial consists in studying the dependance on its coefficients with respects to the geometry of the given rationale polytope.

For example

Proposition [M, St] If P is a rational polytope and each affine subspace generated by any face of codimension up to p is reticular then the coefficients a_{i}’s are constant for i = d, ...d − p.

For example the coefficient a_{d−1} is constant iff the facets are reticular. Further precise description for polygons can be found in [MW].

In the case of simplices explicit description of Ehrhart polynomials of lattice simplices can help. We hope to come back to this.

Finally we close this survey by a simple question : is there any interesting example to be constructed by studying triangulations (or even random triangulations ) of random polytopes ?

References

[BL] Banaszczyk W. ; Litvak A. ; Pajor A.; Szarek S. The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces. Math. Oper. Res. 24, No.3, 728-750 (1999).

[B_{1}] Baranovskii P. Partition of Euclidean spaces into L-polytopes of certain perfect lat-

tices. Proc. Steklov Inst.. Math. 196, 1992, no. 4, 29-51.

[BK] Bárány I.. ; Kantor J.-M. On the number of lattice free polytopes. Eur. J. Comb.. 21, no.1, 103-110 (2000).

[BK_{1}] Bárány I.. ; Kantor J.-M. Universal counting of lattice points in polytopes. Publ.

Inst. Math., Nouv. Ser. 66(80),

[DHZ] Dais D. ; Haase C. ; Ziegler G. All toric local complete intersection singularities admit

projective crepant resolutions, Tohoku Math. J.(2), vol. 53, no. 1, pp. 95–107, 2001.

[De] Delone [Delaunay]B.N. The geometry of positive quadratic forms. UspekhiMath. Naouk, 3 (1937), 16-62;4 (1938), 102-164.

[Du] Dutour www.liga.ens.fr/ dutour/

[E] Ehrhart E. Polynômes arithmétiques et méthode des polyèdres en combinatoire ISNM Vol.35, Birkhaüser Verlag, Basel-Stuggart, 1977.

[ER] Ehrdal R. ; Rybnnikov R. New Infinite Series of Perfect Quadratic Forms and Big Delaunay Simplexes in Z^{n} Proceedings of Steklov Mathematical Institute. volume 239, (2002).

[G] Greenberg P. Piecewise SL_{2}Z geometry. Trans. Amer. Math. Soc. 335 (1993), no. 2, 705–720

[HZ] Haase C. ; Ziegler G. On the maximal width of empty lattice simplices, European J. Combin., vol. 21, no. 1, pp. 111–119, 2000.

[H] Haase C. Lattice Polytopes and Unimodular Triangulations, Ph.D. Thesis TU-Berlin (2000).

[EW] Ewald G. ; Wessels . On the ampleness of invertible sheaves in complete projective varieties Results in mathematics, Vol. 19 (1991V) 278.

[KL] Kannan R.. ; Lovasz L. Covering minima and lattice-point free convex bodies, Ann. Math. 128, 1998, 769-786.

[Ka] Kantor J.-M. On the width of lattice-free simplices, Comp. Math. 118 (1999), no 3, 235-241.

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

Pacific Journal of mathematics, 211, no 1, 2003, 123-155.

[KMS] Kempf G.; Knudsen F.; Mumford D.; Saint-Donat, B. Toroidal embeddings. I. Lecture

Notes in Mathematics, Vol. 339. Springer-Verlag, Berlin-New York, 1973. Kh Khintchine, A qualitative formulation of Kronecker’s theory of approximation, Izv.

kad. Naouk SSSR Ser. Mat. 12 (1948), 113-122.

[L] Lovasz L. Geometry of numbers and integer programming. Mathematical programming (Tokyo, 1988), 177–201, Math. Appl. (Japanese Ser.), 6, SCIPRESS, Tokyo, 1989.

[MM] Mcmullen, P. Lattice invariant valuations on rational polytopes. Arch. Math. (Basel) 31 (1978/79), no. 5, 509–516.

[MW] McAllister B. Woods K. The Minimum Period of the Ehrhart Quasi-polynomial of a

Rational Polytope 1. math.CO/0310255

[MMM] Mori S. ; Morrison D. ; Morrison I. On four dimensional terminal quotient singularities,

Math.Comp.51 (1988), no. 184,769-786.

[MS] Morrison D. ; Stevens G. Terminal quotient singularities in dimension three and four Proc. Amer. Math. Soc. 90 (1984 ), no 1, 15-20.

[Rei] Reid M. Young Person’s guide to canonical singularities Proceedings of Symposia in Pure mathematics, Vol. 48 (1987), 345-

[Rez] Reznick B. Lattice point simplices. Discrete Math. 60 (1986), 219–242

[RB] Ryshkov, S. S. ; Baranovskii , E. P. Classification of arithmetical types of Delaunay simplexes in n-dimensional lattices for n ≤ 6. Proceedings of Voronoi Conference, Kiev, (1998).

[S] Sankaran G.K. Stable quintuples and terminal quotient singularities Math. Proc. Cambridge Philo. Soc. 107 (1990), no 1, 91-101.

[Se] Sebo A. Hilbert bases, Caratheodory’s theorem and Combinatorial Optimization, in “Integer Programming and Combinatorial Optimization (IPCO) 1”, University of Waterloo Press, R. Kannan and W. Pulleyblank eds, (1990).

[S_{1}] Sebo A. An introduction to empty lattice simplices Proccedings IPCO, Lect. Notes

in Comput. Sci.. 1610, 400-414, 1999.

[St] Stanley R. Introduction to combinatorics [St_{1}] Stanley R. Decompositions of rational convex polytopes. Combinatorial mathematics,

optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978). Ann. Discrete Math. 6 (1980), 333–342.

[We] Wessels U. Die Sätze von White und Mordell über kritische G ïtter von Polytope sin den Dimension 4 und 5, Diplomaterbeit, R hr Universitat Bochum, 1989.

[Wh] White G.K. L Lattice tetrahedra, Canadian J. of Math. ; 16, 1964, 389-396.