Ehrhart polynomial
|
|
In mathematics, integral polytopes have associated Ehrhart polynomials which encode some geometrical information about them.
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) be the number of lattice points contained in tP. Ehrhart showed in 1967 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 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 polytope P can be computed as:
- L(int P, t) = (-1)n L(P, −t).
References
- E. Ehrhart: Sur un problème géométrie diophantienne linéaire II, Journal Reine Angewandte Mathematik 227 (1967), pp. 25-49. Definition and first properties.
- 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 (http://www.ams.org/era/1996-02-01/S1079-6762-96-00001-7/home.html). Introduces the Fourier analysis approach and gives references to other related articles.