Ehrhart polynomial
In mathematics, the Ehrhart polynomial of a convex lattice polytope P \subset \mathbb{R}^d is the unique polynomial L_P(t) \in \mathbb{Q} of degree d such that for every positive integer k, L_P(k) equals the number of points in kP \cap \mathbb{Z}^d, where kP denotes the k-fold dilation of P with respect to the origin.[1] The leading coefficient of L_P(t) is the normalized volume of P, the second-highest coefficient is half the normalized surface area, and the constant term is always 1, reflecting the single lattice point at the origin when k = 0.[1] These coefficients admit explicit formulas in terms of the intrinsic volumes of the faces of P, providing a bridge between discrete and continuous geometry.[1] Named after the French mathematician Eugène Ehrhart, who established the polynomial nature of this counting function in his seminal 1962 paper "Sur les polyèdres rationnels homothétiques à n dimensions," the theory generalizes Pick's theorem on lattice polygons to arbitrary dimensions.[2] For rational polytopes (with rational vertices), the counting function becomes a quasi-polynomial, periodic in the coefficients with a period dividing the least common multiple of the denominators of the vertices.[3] A cornerstone result is Ehrhart reciprocity, which asserts that L_P(-k) = (-1)^d times the number of interior lattice points in kP for positive integers k, linking values at positive and negative integers.[3] The associated Ehrhart series \sum_{k=0}^\infty L_P(k) x^k = h^*(x) / (1 - x)^{d+1}, where h^*(x) is the h^*-polynomial with non-negative integer coefficients by Stanley's theorem, further encodes combinatorial invariants like the h^*-vector.[3] Ehrhart polynomials find applications in enumerative combinatorics for counting integer solutions to linear inequalities, in the study of toric varieties via their connections to h^*-polynomials[4], and in computational fields such as program analysis for optimizing loop transformations through exact lattice point counts.[5] They also appear in voting theory to compute probabilities of election outcomes by enumerating lattice points in transportation polytopes.[6]Fundamentals
Definition
A lattice polytope P is a convex polytope in \mathbb{R}^d whose vertices all belong to the integer lattice \mathbb{Z}^d.[7] The Ehrhart polynomial associated to such a P is defined for positive integers t by L_P(t) = |tP \cap \mathbb{Z}^d|, where tP = \{ t x \mid x \in P \} denotes the t-dilate of P.[7] This function counts the lattice points lying inside or on the boundary of the dilated polytope. Eugène Ehrhart established that L_P(t) agrees with a polynomial in t of degree d = \dim(P). One proof of the polynomial nature of L_P(t) proceeds via generating functions: the Ehrhart series \sum_{t=0}^\infty L_P(t) z^t admits a rational generating function of the form h(z)/(1-z)^{d+1}, where h(z) is a polynomial with h(0) = 1, implying that the coefficients L_P(t) are polynomial in t for t \geq 0.[7] The leading coefficient of this polynomial is the d-dimensional volume \vol(P) of P.[7] For simple cases, consider the one-dimensional interval P = [0, a] with a \in \mathbb{Z}_{\geq 0}. Here, L_P(t) = at + 1, which is linear with leading coefficient a = \vol(P).[7] In higher dimensions, the standard d-simplex \Delta^d = \conv\{ \mathbf{0}, e_1, \dots, e_d \}, where e_i are the standard basis vectors, has Ehrhart polynomial L_{\Delta^d}(t) = \binom{t + d}{d}, a degree-d polynomial whose leading coefficient is $1/d! = \vol(\Delta^d).[7]Reciprocity theorem
The Ehrhart reciprocity theorem provides a fundamental relation between the Ehrhart polynomial L_P(t) of a d-dimensional lattice polytope P and the counting function for lattice points in its interior. Specifically, for any positive integer t, L_P(-t) = (-1)^d L_{P^\circ}(t), where P^\circ denotes the relative interior of P, and L_{P^\circ}(t) counts the lattice points in the t-dilate of the interior.[8] This signed evaluation at negative arguments reveals that the Ehrhart polynomial encodes both boundary and interior lattice point enumerations through analytic continuation.[8] The theorem was proved by Eugène Ehrhart in 1962 as part of his foundational work on lattice point enumeration in rational polytopes.[8] Its roots trace to Pick's theorem (1899), which equates the area of a lattice polygon to the number of interior plus half the boundary lattice points, serving as the d=2 case of reciprocity.[8] Ehrhart's discovery extended this relation to higher dimensions, highlighting the polynomial's duality between the polytope and its interior. An important interpretation arises from expressing the Ehrhart polynomial via an alternating sum over intrinsic volumes: L_P(t) = \sum_{k=0}^d (-1)^{d-k} \vol_k(P) \binom{t + d - k}{d}, where \vol_k(P) denotes the k-dimensional intrinsic volume of P.[4] This form connects directly to the h^*-polynomial of P, obtained by a change of basis from the standard monomial form, where the coefficients h_i^* are nonnegative integers reflecting the topology of the normal fan.[1] Reciprocity implies that evaluating this sum at negative t yields the signed interior count, underscoring the theorem's role in decomposing lattice point data geometrically. A bijective proof of the theorem proceeds via inclusion-exclusion on simplices, then extends to general polytopes using triangulation. For a d-simplex \Delta, consider the (t + d + 1)-dilate and apply inclusion-exclusion over its boundary facets to relate boundary and interior points; a geometric bijection maps excess boundary points to interior adjustments, yielding the signed relation.[8] For general P, triangulate into simplices and invoke Möbius inversion on the poset of faces to preserve the reciprocity.[8] Generating function approaches alternatively use the toric ideal of the polytope's normal fan, where the denominator reflects boundary contributions and numerator adjustments enforce the alternating sign via Serre duality.[4] In low dimensions, the theorem simplifies computations. Consider the triangle P with vertices (0,0), (2,0), and (2,1) in \mathbb{R}^2, a lattice polytope of dimension d=2. The Ehrhart polynomial is L_P(t) = t^2 + 2t + 1, counting 4, 9, and 16 lattice points in P, $2P, and $3P, respectively. By reciprocity, L_P(-1) = (-1)^2 L_{P^\circ}(1) = 0, so zero interior points in P; similarly, L_P(-2) = 1 gives one interior point in $2P (e.g., at (3,1)). This matches direct enumeration and illustrates the theorem's utility for verifying interior counts without exhaustive listing.Basic Examples
Integer polytopes
Integer lattice polytopes, which have vertices at integer coordinates, provide straightforward examples where the Ehrhart polynomial exactly counts the lattice points in their dilates. Consider the unit square P = [0,1]^2 in \mathbb{R}^2, a 2-dimensional integer polytope with volume 1. The Ehrhart polynomial of this polytope is L_P(t) = (t+1)^2, which enumerates the lattice points in the dilate tP = [0,t]^2.[9] To verify this, enumerate the lattice points for small t. For t=1, the dilate is [0,1]^2, containing the four points (0,0), (0,1), (1,0), and (1,1). For t=2, [0,2]^2 includes all integer pairs (i,j) with $0 \leq i,j \leq 2, totaling nine points: the previous four plus (0,2), (1,2), (2,0), (2,1), and (2,2). For t=3, [0,3]^2 adds points with coordinates up to 3, yielding 16 points. These counts—4, 9, 16—match (t+1)^2 for t=1,2,3.| t | Lattice points in tP | L_P(t) |
|---|---|---|
| 1 | 4 | 4 |
| 2 | 9 | 9 |
| 3 | 16 | 16 |
| t | Lattice points in t\Delta_2 | L_{\Delta_2}(t) |
|---|---|---|
| 1 | 3 | 3 |
| 2 | 6 | 6 |
| 3 | 10 | 10 |
Rational polytopes
A rational polytope is a convex polytope in \mathbb{R}^d whose vertices have rational coordinates. The denominator q of such a polytope P is the smallest positive integer such that qP has integer vertices, making qP an integral polytope.[10] Unlike integral polytopes, where the Ehrhart function L_P(t) is a polynomial, for rational polytopes it is generally a quasi-polynomial whose period divides the denominator q.[11] Consider the rational triangle P with vertices (0,0), (1/2,0), and (0,1/2). This polytope has denominator q=2, as $2P is the integral unit triangle with vertices (0,0), (1,0), and (0,1). The Ehrhart function L_P(t) counts the lattice points in tP = \{(x,y) \in \mathbb{R}^2 \mid x \geq 0, y \geq 0, x + y \leq t/2\}, which consists of nonnegative integer pairs (x,y) satisfying x + y \leq t/2. This yields a quasi-polynomial of period 2: L_P(t) = \begin{cases} \dfrac{t^2 + 6t + 8}{8} & \text{if } t \text{ is even}, \\ \dfrac{t^2 + 4t + 3}{8} & \text{if } t \text{ is odd}. \end{cases} The following table lists the number of lattice points for small values of t, illustrating the periodic behavior and deviation from a single polynomial (e.g., the count remains constant from t=2 to t=3, unlike the steady growth expected from a quadratic).| t | Lattice points in tP | L_P(t) |
|---|---|---|
| 1 | (0,0) | 1 |
| 2 | (0,0), (1,0), (0,1) | 3 |
| 3 | (0,0), (1,0), (0,1) | 3 |
| 4 | (0,0), (1,0), (0,1), (2,0), (1,1), (0,2) | 6 |
Ehrhart Quasi-Polynomials
Definition and properties
The Ehrhart quasi-polynomial of a rational polytope P \subseteq \mathbb{R}^d is defined in relation to its denominator q, the smallest positive integer such that all vertices of P lie in \frac{1}{q} \mathbb{Z}^d. For positive integers t, the Ehrhart function L_P(t) counts the number of lattice points in the dilation tP, i.e., L_P(t) = \#(tP \cap \mathbb{Z}^d). This function is a quasi-polynomial of degree d: L_P(t) = \sum_{r=0}^d c_r(t) \, t^r, where each coefficient function c_r: \mathbb{Z} \to \mathbb{Q} is periodic with period dividing q.[7][12] The existence of L_P(t) as a quasi-polynomial follows from its behavior on arithmetic progressions tied to the integer dilates of the scaled polytope qP, which is an integral polytope with Ehrhart polynomial L_{qP}(s). Specifically, L_P(t) = L_{qP}(t/q), where the right-hand side extends the polynomial L_{qP} to rational arguments via the quasi-polynomial structure induced by the periodicity of period q. This transformation establishes that L_P(t) agrees with a polynomial on multiples of q and interpolates quasi-periodically elsewhere.[7][13] A key property is the generalized reciprocity theorem, which extends the integer case to rational polytopes: L_P(-t) = (-1)^d L_{\mathrm{int}\, P}(t), where \mathrm{int}\, P denotes the relative interior of P. This equates the quasi-polynomial evaluated at negative arguments (with a sign) to the count of lattice points in the interior of the dilation tP, providing a signed interpretation of interior points. The theorem holds by analytic continuation of the Ehrhart series or via inclusion-exclusion on boundary contributions.[12][7] The periodicity theorem asserts that the minimal period of each c_r(t) divides q, the denominator of P, which is the least common multiple of the denominators of the coordinates of P's vertices (expressed in lowest terms). While the period always divides this LCM, the minimal period may be strictly smaller in some cases, but it achieves the full LCM for certain simplices and coefficients, such as the second-highest term.[14][7]Examples
A prominent example of an Ehrhart quasi-polynomial with period 3 is provided by the rational triangle P in \mathbb{R}^2 with vertices at (0,0), (2/3,0), and (0,1/3). This polytope has denominator 3, as the least common multiple of the denominators in its vertex coordinates is 3, and the period of its Ehrhart quasi-polynomial is exactly 3. The volume of P is $1/9, so the leading coefficient of the quasi-polynomial is the constant $1/9. The full quasi-polynomial is L(P, t) = \frac{1}{9} t^2 + b(t) t + c(t), where the periodic functions with period 3 are b(t) = \begin{cases} 4/9 & \text{if } t \equiv 1 \pmod{3}, \\ 5/9 & \text{if } t \equiv 2 \pmod{3}, \\ 2/3 & \text{if } t \equiv 0 \pmod{3}, \end{cases} and c(t) = \begin{cases} 4/9 & \text{if } t \equiv 1 \pmod{3} \text{ or } t \equiv 2 \pmod{3}, \\ 1 & \text{if } t \equiv 0 \pmod{3}. \end{cases} To illustrate the periodicity, the number of lattice points in tP for t = 1,2,3 is 1, 2, and 4, respectively. These values repeat the pattern in coefficients when extended to higher t: for t=4 \equiv 1 \pmod{3}, there are 4 lattice points; for t=5 \equiv 2 \pmod{3}, 6 lattice points; and for t=6 \equiv 0 \pmod{3}, 9 lattice points. Substituting into the quasi-polynomial confirms the counts, such as for t=3: (1/9)(9) + (2/3)(3) + 1 = 1 + 2 + 1 = 4. Another example is the 3D rational pyramid Q with base the unit square in the xy-plane with vertices (0,0,0), (1,0,0), (0,1,0), (1,1,0), and apex at (1/2, 1/2, 1/2). This polytope has denominator 2, and its Ehrhart function has degree 3. The volume of Q is $1/6, so the leading coefficient is the constant $1/6. Computations show that, despite the denominator of 2, the Ehrhart function is actually a polynomial (period 1): L(Q, t) = \frac{1}{6} t^3 + t^2 + \frac{11}{6} t + 1. The following table lists the number of lattice points in tQ for t=1 to $6, demonstrating the polynomial behavior:| t | Lattice points in tQ |
|---|---|
| 1 | 4 |
| 2 | 10 |
| 3 | 20 |
| 4 | 35 |
| 5 | 56 |
| 6 | 84 |