\magnification=1200

\newfam\msbmfam
\font\tenmsbm=msbm10\textfont\msbmfam=\tenmsbm
\font\sevenmsbm=msbm7 \scriptfont\msbmfam=\sevenmsbm
\font\fivemsbm=msbm5 \scriptscriptfont\msbmfam=\fivemsbm 
\mathchardef\R="7852 
\mathchardef\N="784E
\mathchardef\M="784D
\mathchardef\L="784C
\mathchardef\C="7843
\mathchardef\Q="7851
\mathchardef\Z="785A
\mathchardef\P="7850
\mathchardef\T="7854 
\mathchardef\I="7849 
\mathchardef\H="7848
 


\centerline{\bf Lattice polytopes: some open problems}

\medskip

\centerline{\bf Jean-Michel Kantor}

\vskip 1cm
									





\noindent Jean-Michel KANTOR  (IMJ, Paris 7-Diderot)
 
\vskip 1cm


\noindent I.  Empty polytopes

\noindent I.1. Definition and general results 

\noindent I.2. Width and classification in dimension 3, and extensions.


\noindent  II. Special empty simplices

\noindent   III. Problems related to triangulations

\noindent III.1. Scaling

\noindent   III.2. Ehrhart polynomial and
classification

\noindent   III.3. Rationale polytopes


\vskip 1cm

{\bf Introduction}

\smallskip

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. 
\medskip
Our personal  interest is in geometrical  combinatorics of lattice polytopes.We assume here  for simplicity integral  polytopes with vertices in  the integral
lattice $\Z^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.

\vskip 1cm

{\bf I. Empty polytopes}

\medskip

{\bf I.1. Definition and general results} 

\medskip

\noindent {\bf Definition 1.} 
{\sl An empty simplex is an integral  simplex with no other integral point.}
\noindent

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


\medskip

\noindent  Examples :

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

\medskip

  2. In all dimension an interesting family of examples is given by the class of Delaunay-Vorono\"\i \ 
polytopes constructed via the  ``empty sphere'' method and originally introduced in connection
with cristallography [B$_1$, De, Du, ER].

\bigskip

\noindent {\bf Definition 2.} 

 Barycentric coordinates (Reznick)

If 
$${\Sigma = [ 0,v_1,\ldots ,v_d]} $$  
is a simplex of full dimension $d$  and  arithmetical volume $D$ and 
${\cal C}$ the cone with vertex at the origin generated by ${\Sigma}$, any  point $M$
of ${\cal C}$  can be expressed in a unique way as  
$$  M ={{1 \over D}\sum \lambda _i }  v_i, \qquad  \lambda_i \geq 0.  $$  
The $\lambda _i $'s are called barycentric coordinates of the point $x$

The sum 
$s(x) = \Sigma \lambda_i$ is called the barycentric sum of $x$.


\medskip

\noindent {\bf Lemma 1.} 
 {\sl ${\sigma}$ is empty iff no integral point $x$  has barycentric sum strictly less than $d$.}  

\medskip
 
\noindent {\bf 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:


\medskip

\noindent {\bf Definition 3.} 
{\sl  Given a dual element  $u$ in $(\Z^{d})^{\star}$
the width of $P$ in direction u is the quantity }
 $$ w_u(P ) = \max \{ u(x) - u(y ),x,y \in P\} $$

The width of $P$ is 
$$ w (P ) = \min \{ w_u(P) ; u \in (\Z^{d})^{\star} \backslash \{0\}\}.$$


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

\noindent {\bf  Theorem 1.}
{\sl For a fixed  dimension d there exists a uniform bound $C(d)$ for all empty polytopes:
$$w(P) \leq 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.

\medskip

\noindent {\bf 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) \leq d^{3/2} $$
[BL]

\medskip

\noindent {\bf Problems:}

\item{--} Compute C(4)
\item{--} Give refined estimates on the width in connection 
with the arithmetical volume. 

\medskip
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].


\noindent
{\bf Proposition 3.} (White's lemma)[Wh]
\noindent
{\sl Any empty simplex of dimension 3 has width $1 $.}

\medskip

\noindent
{\bf Corollary.}
Any simplex $S$ of dimension $3$ is equivalent to an empty simplex with vertices the origin
and the points
$$\pmatrix{ 
1 &0 &0\cr
0&1&0\cr
1&p&q\cr}$$
where 
 $$ (p,q) = 1, 0 \leq p \leq q $$
and $q$ is the volume of $S$.
The unimodular case corresponds  to  
$$ p = 0 , 1 \; \hbox{and} \;  \ q =1$$
\noindent 
$$\hbox{otherwise} \quad 1 \leq p \leq q $$



Various proofs exist,from the simplest to the more elaborate one using elementary properties of
the Bernoulli function $B_1$  [MS]. 
\noindent

Let
$$ x_i = {a_i \over D},  \quad a_i, D \in \N^\star,$$
with
$$ 0 < x_i < 1, \quad (a_i, D) = 1.$$

Let 
$$\eqalign{((x)) = B_1 (x) = \left\{\eqalign{ 
&x - [x] - {1 \over 2} \quad \hbox{if}\  x \in \Z,\cr 
&0\; \hbox{otherwise}.\cr
}\right.
}$$

Theorem 2 

The following assertions are equivalent

a)
$$\Sigma  ((k x_i)) \geq 0 \quad \hbox{for all}\ k \in
\Z,  \quad \hbox{or equivalently} \; k = 1,....D-1
$$

b)
$$\sum^m_{i=1} ((k x_i))  = O \quad \hbox{for all}\ k
=1,...D-1 $$

c) There exists an involution $\tau : \{1,...m\} \rightarrow \{1,...m\}$,
$\tau^2 =$ Identity such that 


$$a_i + a_{\tau(i)}\equiv {0} \pmod {D}\hbox{ }. $$


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).
\medskip

\noindent {\bf 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.

\vskip 1cm

\noindent  {\bf II. Special empty simplices}

\medskip

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) : 


\medskip


\noindent {\bf Definition 4.}

{\sl A simplex is  a special empty simplex if 

\item{--} it is an  empty simplex

\item{--} 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

$$ \Sigma (u ) = [{u;e_i,i=1...d-1}] $$
where $u$ is some lattice vector.

\medskip
 
\noindent {\bf Problem.}
Give a  complete classification of special empty simplices using the results above.


\vskip 1cm

\noindent {\bf III.    Problems related to triangulations}

\medskip
 
\noindent {\bf III.1. Scaling}
\smallskip
 
Any lattice polytope  posesses a triangulation made of  empty simplices (this is easy to
proof), but not necessarily with unimodular simplices. However 

\medskip

\noindent {\bf Theorem 3.} [KMS]
 
{\sl For any lattice polytope P there exists an integer $ N =  N(P) $  such that 
  $$ (* )   N.P \quad \hbox{posesses a unimodular triangulation.}$$
Equivalently, by increasing the lattice from $\Z^d$ to ${1\over N} \Z^d$ permits to 
find a unimodular triangulation.}

\medskip

          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$;

\medskip

{\bf Conjecture :}
             $$    N(P) \leq M(P) \leq K(d)$$
where $K(d)$ is a constant depending on $d$ only, and the inequalities can be strict.


\medskip

\noindent
{\bf Example 3} (due to B.Sturmfels).
Consider the parallelotope $\Pi$ generated by $d$  integral primitive  independent 
vectors. 


\medskip
\noindent {\bf Proposition} [EW]
{\sl Any lattice point in $\Pi$ is a non-negative linear combination of  integral
points in $\Pi$ with barycentric sum less or equal to   
 $$k = (d-1),$$
but this is not true,in general, for any smaller $k$.}

\medskip

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), \quad r \geq 0.$$

\medskip

In dimension 3 however

\medskip

\noindent {\bf 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

\vskip 1cm   



\noindent {\bf III.2. Ehrhart Polynomial and classification}

\smallskip

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

\medskip 


\noindent {\bf Definition 4}[G]

{\sl 1) A map $\phi $ is a  $\Z$  piecewise -linear unimorphism  iff

 \item{--} It is a homeomorphism with compact support ($\phi$ is the identity at infinity)

 \item{--}  There exists a  unimodular triangulation such that $\phi$ is locally a
unimodular isomorphism with respect to these triangulations.

\medskip

2) $\phi$ is a $\Q$ piecewise-linear unimorphism over $\Q$ iff there exists an integer $N$ such
that $\tilde\varphi$ defined by 
$$\varphi(Nx) = N \, \tilde\varphi(x)$$
is a $\Z$ piecewise-linear unimorphism.}

\medskip
 


Case of dimension 2:

\noindent {\bf Theorem 5} [ G]   
{\sl Two lattice polygons $P$ and $Q$ are $PL$-equivalent  over $\Z$  under the above (obvious)
equivalence relation iff they have the same Ehrhart polynomial.}

\medskip

The proof is  by induction on the  area of $P$.

In higher dimension,this is an open area:

\medskip
 
\noindent {\bf Conjecture and example.} 
 $P$ and $Q$ have the same Ehrhart polynomial iff they are $PL$-equivalent over $\Q$.


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

%\bigskip

\vfill\eject

\noindent {\bf III.3. Rationale polytopes}
\smallskip

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

\medskip

\noindent {\bf Proposition} [M, St]
{\sl 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
$.}

\medskip
For example the coefficient ${a_{d-1}}$ is constant iff the facets are reticular.

Further precise  description for polygons can be found in [MW].
\medskip

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

\medskip
 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   ?

\vskip 1cm

\noindent {\bf References}

\medskip





\item{[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). 

\item{[B$_1$]} Baranovskii P.  Partition of Euclidean spaces into $L$%
-polytopes of certain perfect lattices.  Proc. Steklov Inst.. Math.
196, 1992, no. 4, 29-51.
 
 \item{[BK]} B\'ar\'any I.. ; Kantor J.-M.
On the number of lattice free polytopes. 
Eur. J. Comb.. 21, no.1, 103-110 (2000). 

\item{[BK$_1$]} B\'ar\'any I.. ; Kantor J.-M.
Universal counting of lattice points in polytopes. 
Publ. Inst. Math., Nouv. Ser. 66(80),



\item{[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.


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

 \item{[Du]} Dutour www.liga.ens.fr/~dutour/

\item{[E]} Ehrhart  E. 
Polyn\^omes arithm\'etiques et m\'ethode des poly\`edres en combinatoire
ISNM Vol.35, Birkha\"user Verlag, Basel-Stuggart, 1977. 

\item {[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).

  
\item{[G]} Greenberg P.  Piecewise ${\rm SL}\sb 2 Z$ geometry. Trans. Amer. Math. Soc. 335
    (1993), no. 2, 705--720

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

\item{[H]} Haase C.
 Lattice Polytopes and Unimodular Triangulations, Ph.D. Thesis TU-Berlin (2000). 
 
\item{[EW]} Ewald G. ; Wessels .
On the ampleness of invertible sheaves in complete projective varieties
Results in mathematics, Vol. 19 (1991V)  278. 


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


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

\item{[KS]} Kantor J.-M.. ; Sarkaria K.S.
On primitive subdivisions of an elementary tetrahedron, Pacific Journal of mathematics, 211, no 1, 2003, 123-155.
           
\item {[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.

\item {Kh} Khintchine,
A qualitative formulation of Kronecker's theory of approximation, Izv. kad. Naouk
SSSR Ser. Mat. 12 (1948), 113-122.

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

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

\item{[MW]} McAllister B. Woods K.
The Minimum Period of the Ehrhart Quasi-polynomial of a Rational Polytope
     1. math.CO/0310255   

\item{[MMM]}  Mori S. ; Morrison D. ; Morrison I. 
On four dimensional terminal quotient singularities,
Math.Comp.51 (1988), no. 184,769-786.

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


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

\item{[Rez]} Reznick B. 
Lattice point simplices. 
Discrete Math. 60 (1986),
219--242                                                                                                                                                         

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



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

\item{[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).
   
\item{[S$_1$]} Sebo A. An introduction to empty lattice simplices
Proccedings IPCO,
Lect. Notes in Comput. Sci.. 1610, 400-414, 1999.


\item{[St]} Stanley R. 
Introduction to combinatorics

\item {[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.



                                                   
 \item{[We]} Wessels U. Die S{\"a}tze von White und Mordell  {\"u}ber kritische G {\"i}tter von
Polytope sin den Dimension 4 und 5, Diplomaterbeit, R hr Universitat Bochum, 1989.

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


\end
