The image is from Wikipedia Commons
In mathematics, an integral polytope has an associated Ehrhart polynomial that 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.
These polynomials are named after Eugène Ehrhart who studied them in the 1960s.
More formally, consider a lattice in Euclidean space and a d-dimensional polytope P in with the property that all vertices of the polytope are points of the lattice. (A common example is and a polytope for which all vertices have integer coordinates.) For any positive integer t, let tP be the t-fold dilation of P (the polytope formed by multiplying each vertex coordinate, in a basis for the lattice, by a factor of t), and let
for all positive integers t.
The Ehrhart polynomial of the interior of a closed convex polytope P can be computed as:
where d is the dimension of P. This result is known as Ehrhart–Macdonald reciprocity.
Then the t-fold dilation of P is a cube with side length t, containing (t + 1)d integer points. That is, the Ehrhart polynomial of the hypercube is L(P,t) = (t + 1)d. Additionally, if we evaluate L(P, t) at negative integers, then
as we would expect from Ehrhart–Macdonald reciprocity.
Many other figurate numbers can be expressed as Ehrhart polynomials. For instance, the square pyramidal numbers are given by the Ehrhart polynomials of a square pyramid with an integer unit square as its base and with height one; the Ehrhart polynomial in this case is 1/6(t + 1)(t + 2)(2t + 3).
Let P be a rational polytope. In other words, suppose
where and (Equivalently, P is the convex hull of finitely many points in ) Then define
In this case, L(P, t) is a quasi-polynomial in t. Just as with integral polytopes, Ehrhart–Macdonald reciprocity holds, that is,
Examples of Ehrhart quasi-polynomials
Let P be a polygon with vertices (0,0), (0,2), (1,1) and ( 3/2, 0). The number of integer points in tP will be counted by the quasi-polynomial 
Interpretation of coefficients
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, , is equal to the d-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, , can be computed as follows: the lattice L induces a lattice LF on any face F of P; take the (d − 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. When P is a closed convex polytope, .
The Betke–Kneser theorem
Ulrich Betke and Martin Kneser established the following characterization of the Ehrhart coefficients. A functional defined on integral polytopes is an and translation invariant valuation if and only if there are real numbers such that
We can define a generating function for the Ehrhart polynomial of an integral d-dimensional polytope P as
Additionally, Richard P. Stanley's non-negativity theorem states that under the given hypotheses, will be non-negative integers, for .
Another result by Stanley shows that if P is a lattice polytope contained in Q, then for all j. The -vector is in general not unimodal, but it is whenever it is symmetric, and the polytope has a regular unimodal triangulation.
Ehrhart series for rational polytopes
As in the case of polytopes with integer vertices, one defines the Ehrhart series for a rational polytope. For a d-dimensional rational polytope P, where D is the smallest integer such that DP is an integer polytope (D is called the denominator of P), then one has
Non-leading coefficient bounds
The polynomial's non-leading coefficients in the representation
can be upper bounded:
The case and 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.
Ehrhart polynomials can be studied for their own sake. For instance, one could ask questions related to the roots of an Ehrhart polynomial. Furthermore, some authors have pursued the question of how these polynomials could be classified.
It is possible to study the number of integer points in a polytope P if we dilate some facets of P but not others. In other words, one would like to know the number of integer points in semi-dilated polytopes. It turns out that such a counting function will be what is called a multivariate quasi-polynomial. An Ehrhart-type reciprocity theorem will also hold for such a counting function.
Counting the number of integer points in semi-dilations of polytopes has applications in enumerating the number of different dissections of regular polygons and the number of non-isomorphic unrestricted codes, a particular kind of code in the field of coding theory.
- This page is based on the Wikipedia article Ehrhart polynomial; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA.