Ehrhart Polynomial - Definition

Definition

Informally, if P is any polyhedron or polytope, and tP is the polytope formed by expanding P by a factor of t in each dimension, then L(int P, t) is the number of integer lattice points in tP.

More formally, consider a lattice L in Euclidean space Rn and a d-dimensional polytope P in Rn, and assume that all the 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 (the polytope formed by multiplying each vertex coordinate, in a basis for the lattice, by a factor of t), and let

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

L(P, t) = a_dtd + a_d−1td−1 + … + a₀ for all positive integers t.

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