Ehrhart polynomial

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 R^"n" and an "n"-dimensional polytope "P" in R^"n", and assume that all vertices of the polytope are points of the lattice. (A common example is "L" = Z^"n" 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 "a"₀,...,"a"_"n" such that:

:"L"("P", "t") = "a"_"n""t"^"n" + "a"_"n"−1"t"^"n"−1 + … + "a"₀ 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, "a"_"n", 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, "a"_"n"−1, can be computed as follows: the lattice "L" induces a lattice "L_F" on any face "F" of "P"; take the ("n"−1)-dimensional volume of "F", divide by 2"d"("L_F"), and add those numbers for all faces of "P";
* the constant coefficient "a"₀ 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.

See also

* Quasi-polynomial

References

*citation
last1 = Beck | first1 = Matthias
last2 = Robins | first2 = Sinai
id = MR|2271992
isbn = 978-0-387-29139-0
location = New York
publisher = Springer-Verlag
series = Undergraduate Texts in Mathematics
title = Computing the Continuous Discretely, Integer-point enumeration in polyhedra
year = 2007.

*citation
last1 = Diaz | first1 = Ricardo
last2 = Robins | first2 = Sinai
journal = Electronic Research Announcements of the American Mathematical Society
pages = 1–6
title = The Ehrhart polynomial of a lattice "n"-simplex
url = http://www.ams.org/era/1996-02-01/S1079-6762-96-00001-7/home.html
volume = 2
year = 1996. Introduces the Fourier analysis approach and gives references to other related articles.

*citation
last = Ehrhart | first = Eugène
journal = C. R. Acad. Sci. Paris
pages = 616–618
title = Sur les polyèdres rationnels homothétiques à "n" dimensions
volume = 254
year = 1962. Definition and first properties.

*citation
last = Mustaţă | first = Mircea
contribution = Chapter 13: Ehrhart polynomials
date = February 2005
title = Lecture notes on toric varieties
url = http://www.math.lsa.umich.edu/~mmustata/toric_var.html.