Ehrhart polynomial

From Wikipedia, the free encyclopedia

In mathematics, a integral polytope has an associated Ehrhart polynomial which encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a higher dimensional generalization of Pick's theorem in the Euclidean plane.

Specifically, consider a lattice L in Euclidean space Rn and an n-dimensional polytope P in Rn, and assume that all vertices of the polytope are points of the lattice. (A common example is L = Zn and a polytope with all its vertex coordinates being integers.) For any positive integer t, let tP be the t-fold dilation of P, and let

L(P,t) = \#(tP \cap L)\,

be the number of lattice points contained in tP. Ehrhart showed in 1962 that L is a rational polynomial of degree n in t, i.e. there exist rational numbers a0,...,an such that:

L(P, t) = antn + an−1tn−1 + … + a0     for all positive integers t.

Furthermore, if P is closed (i.e. the boundary faces belong to P), some of the coefficients of L(P, t) have an easy interpretation:

  • the leading coefficient, an, is equal to the n-dimensional volume of P, divided by d(L) (see lattice for an explanation of the content or covolume d(L) of a lattice);
  • the second coefficient, an−1, can be computed as follows: the lattice L induces a lattice LF on any face F of P; take the (n−1)-dimensional volume of F, divide by 2d(LF), and add those numbers for all faces of P;
  • the constant coefficient a0 is the Euler characteristic of P.

The case n=2 and t=1 of these statements yields Pick's theorem. Formulas for the other coefficients are much harder to get; Todd classes of toric varieties, the Riemann–Roch theorem as well as Fourier analysis have been used for this purpose.

The Ehrhart polynomial of the interior of a closed convex polytope P can be computed as:

L(int P, t) = (−1)n L(P, −t).

If X is the toric variety corresponding to the normal fan of P, then P defines an ample line bundle on X, and the Ehrhart polynomial of P coincides with the Hilbert polynomial of this line bundle.

[edit] References

  • Matthias Beck, Sinai Robins: "Computing the Continuous Discretely, Integer-point enumeration in polyhedra", Undergraduate Texts in Mathematics, Springer, New York, 2007. ISBN 978-0-387-29139-0. MR2271992
  • Ricardo Diaz, Sinai Robins: "The Ehrhart polynomial of a lattice n-simplex", Electronic Research Announcements of the American Mathematical Society 2 (1996), pages 1–6, online version. Introduces the Fourier analysis approach and gives references to other related articles.
  • Eugène Ehrhart: "Sur les polyèdres rationnels homothétiques à n dimensions", C. R. Acad. Sci. Paris 254 (1962), pp. 616–618. Definition and first properties.
  • Mircea Mustaţă, "Lecture notes on toric varieties", Chapter 13: Ehrhart polynomials (version of February 1, 2005)

[edit] See also