Ehrhart polynomial

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.

Definition

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

More formally, consider a lattice ${\displaystyle {\mathcal {L}}}$ in Euclidean space ${\displaystyle \mathbb {R} ^{n}}$ and a d-dimensional polytope P in ${\displaystyle \mathbb {R} ^{n}}$ with the property that all vertices of the polytope are points of the lattice. (A common example is ${\displaystyle {\mathcal {L}}=\mathbb {Z} ^{n}}$ 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

${\displaystyle L(P,t)=\#\left(tP\cap {\mathcal {L}}\right)}$

be the number of lattice points contained in the polytope tP. Ehrhart showed in 1962 that L is a rational polynomial of degree d in t, i.e. there exist rational numbers ${\displaystyle L_{0}(P),\dots ,L_{d}(P)}$ such that:

${\displaystyle L(P,t)=L_{d}(P)t^{d}+L_{d-1}(P)t^{d-1}+\cdots +L_{0}(P)}$

for all positive integers t.

The Ehrhart polynomial of the interior of a closed convex polytope P can be computed as:

${\displaystyle L(\operatorname {int} (P),t)=(-1)^{d}L(P,-t),}$

where d is the dimension of P. This result is known as Ehrhart–Macdonald reciprocity.[1]

Examples

This is the second dilate, ${\displaystyle t=2}$, of a unit square. It has nine integer points.

Let P be a d-dimensional unit hypercube whose vertices are the integer lattice points all of whose coordinates are 0 or 1. In terms of inequalities,

${\displaystyle P=\left\{x\in \mathbb {R} ^{d}:0\leq x_{i}\leq 1;1\leq i\leq d\right\}.}$

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.[2][3] Additionally, if we evaluate L(P, t) at negative integers, then

${\displaystyle L(P,-t)=(-1)^{d}(t-1)^{d}=(-1)^{d}L(\operatorname {int} (P),t),}$

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).[4]

Ehrhart quasi-polynomials

Let P be a rational polytope. In other words, suppose

${\displaystyle P=\left\{x\in \mathbb {R} ^{d}:Ax\leq b\right\},}$

where ${\displaystyle A\in \mathbb {Q} ^{k\times d}}$ and ${\displaystyle b\in \mathbb {Q} ^{k}.}$ (Equivalently, P is the convex hull of finitely many points in ${\displaystyle \mathbb {Q} ^{d}.}$) Then define

${\displaystyle L(P,t)=\#\left(\left\{x\in \mathbb {Z} ^{n}:Ax\leq tb\right\}\right).}$

In this case, L(P, t) is a quasi-polynomial in t. Just as with integral polytopes, Ehrhart–Macdonald reciprocity holds, that is,

${\displaystyle L(\operatorname {int} (P),t)=(-1)^{n}L(P,-t).}$

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 [5]

${\displaystyle L(P,t)={\frac {7t^{2}}{4}}+{\frac {5t}{2}}+{\frac {7+(-1)^{t}}{8}}.}$

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, ${\displaystyle L_{d}(P)}$, 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, ${\displaystyle L_{d-1}(P)}$, can be computed as follows: the lattice L induces a lattice L_F on any face F of P; take the (d − 1)-dimensional volume of F, divide by 2d(L_F), and add those numbers for all faces of P;

• the constant coefficient a₀ is the Euler characteristic of P. When P is a closed convex polytope, ${\displaystyle L_{0}(P)=1}$.

The Betke–Kneser theorem

Ulrich Betke and Martin Kneser[6] established the following characterization of the Ehrhart coefficients. A functional ${\displaystyle Z}$ defined on integral polytopes is an ${\displaystyle \operatorname {SL} (n,\mathbb {Z} )}$ and translation invariant valuation if and only if there are real numbers ${\displaystyle c_{0},\ldots ,c_{n}}$ such that

${\displaystyle Z=c_{0}L_{0}+\cdots +c_{n}L_{n}.}$

Ehrhart series

We can define a generating function for the Ehrhart polynomial of an integral d-dimensional polytope P as

${\displaystyle \operatorname {Ehr} _{P}(z)=\sum _{t\geq 0}L(P,t)z^{t}.}$

This series can be expressed as a rational function. Specifically, Ehrhart proved (1962) that there exist complex numbers ${\displaystyle h_{j}^{*}}$, ${\displaystyle 0\leq j\leq d}$, such that the Ehrhart series of P is

${\displaystyle \operatorname {Ehr} _{P}(z)={\frac {\sum _{j=0}^{d}h_{j}^{\ast }(P)z^{j}}{(1-z)^{d+1}}},\qquad \sum _{j=0}^{d}h_{j}^{\ast }(P)\neq 0.}$

Additionally, Richard P. Stanley's non-negativity theorem states that under the given hypotheses, ${\displaystyle h_{j}^{*}}$ will be non-negative integers, for ${\displaystyle 0\leq j\leq d}$.

Another result by Stanley shows that if P is a lattice polytope contained in Q, then ${\displaystyle h_{j}^{*}(P)\leq h_{j}^{*}(Q)}$ for all j. The ${\displaystyle h^{*}}$-vector is in general not unimodal, but it is whenever it is symmetric, and the polytope has a regular unimodal triangulation.[7]

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

${\displaystyle \operatorname {Ehr} _{P}(z)=\sum _{t\geq 0}L(P,t)z^{t}={\frac {\sum _{j=0}^{D(d+1)}h_{j}^{\ast }(P)z^{j}}{\left(1-z^{D}\right)^{d+1}}},}$

where the ${\displaystyle h_{j}^{*}}$ are still non-negative integers.[8][9]

Non-leading coefficient bounds

The polynomial's non-leading coefficients ${\displaystyle c_{0},\dots ,c_{d-1}}$ in the representation

${\displaystyle L(P,t)=\sum _{r=0}^{d}c_{r}t^{r}}$

can be upper bounded:[10]

${\displaystyle c_{r}\leq (-1)^{d-r}{\begin{bmatrix}d\\r\end{bmatrix}}c_{d}+{\frac {(-1)^{d-r-1}}{(d-1)!}}{\begin{bmatrix}d\\r+1\end{bmatrix}}}$

where ${\displaystyle \left[{\begin{smallmatrix}n\\k\end{smallmatrix}}\right]}$ is a Stirling number of the first kind. Lower bounds also exist.[11]

Toric variety

The case ${\displaystyle n=d=2}$ and ${\displaystyle 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.

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.

Ehrhart polynomials can be studied for their own sake. For instance, one could ask questions related to the roots of an Ehrhart polynomial.[12] Furthermore, some authors have pursued the question of how these polynomials could be classified.[13]

Generalizations

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.[14]

Counting the number of integer points in semi-dilations of polytopes has applications[15] 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.

See also

• Quasi-polynomial
• Stanley's reciprocity theorem

Notes

1. Macdonald, Ian G. (1971). "Polynomials associated with finite cell-complexes" (PDF). Journal of the London Mathematical Society. 2 (1): 181–192. doi:10.1112/jlms/s2-4.1.181.
2. De Loera, Rambau & Santos (2010)
3. Mathar (2010)
4. Beck et al. (2005).
5. Beck, Matthias; Robins, Sinai (2007). Computing the Continuous Discretely. New York: Springer. pp. 46–47. MR 2271992.
6. Betke, Ulrich; Kneser, Martin (1985), "Zerlegungen und Bewertungen von Gitterpolytopen", Journal für die reine und angewandte Mathematik, 358: 202–208, MR 0797683
7. Athanasiadis, Christos A. (2004). "h*-Vectors, Eulerian Polynomials and Stable Polytopes of Graphs". Electronic Journal of Combinatorics. 11 (2).
8. Stanley, Richard P. (1980). "Decompositions of rational convex polytopes". Annals of Discrete Mathematics. 6: 333–342. doi:10.1016/s0167-5060(08)70717-9. ISBN 9780444860484.
9. Beck, Matthias; Sottile, Frank (January 2007). "Irrational proofs for three theorems of Stanley". European Journal of Combinatorics. 28 (1): 403–409. arXiv:math/0501359. doi:10.1016/j.ejc.2005.06.003.
10. Betke, Ulrich; McMullen, Peter (1985-12-01). "Lattice points in lattice polytopes". Monatshefte für Mathematik. 99 (4): 253–265. doi:10.1007/BF01312545. ISSN 1436-5081.
11. Henk, Martin; Tagami, Makoto (2009-01-01). "Lower bounds on the coefficients of Ehrhart polynomials". European Journal of Combinatorics. 30 (1): 70–83. arXiv:0710.2665. doi:10.1016/j.ejc.2008.02.009. ISSN 0195-6698.
12. Braun, Benjamin; Develin, Mike (2008). Ehrhart Polynomial Roots and Stanley's Non-Negativity Theorem. Contemporary Mathematics. 452. American Mathematical Society. pp. 67–78. arXiv:math/0610399. doi:10.1090/conm/452/08773. ISBN 9780821841730.
13. Higashitani, Akihiro (2012). "Classification of Ehrhart Polynomials of Integral Simplices" (PDF). DMTCS Proceedings: 587–594.
14. Beck, Matthias (January 2002). "Multidimensional Ehrhart reciprocity". Journal of Combinatorial Theory. Series A. 97 (1): 187–194. arXiv:math/0111331. doi:10.1006/jcta.2001.3220.
15. Lisonek, Petr (2007). "Combinatorial Families Enumerated by Quasi-polynomials". Journal of Combinatorial Theory. Series A. 114 (4): 619–630. doi:10.1016/j.jcta.2006.06.013.

References

• Beck, Matthias; De Loera, Jesús A.; Develin, Mike; Pfeifle, Julian; Stanley, Richard P. (2005), "Coefficients and roots of Ehrhart polynomials", Integer Points in Polyhedra—Geometry, Number Theory, Algebra, Optimization, Contemporary Mathematics, 374, Providence, RI: American Mathematical Society, pp. 15–36, MR 2134759.
• Beck, Matthias; Robins, Sinai (2007), Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, Undergraduate Texts in Mathematics, New York: Springer-Verlag, ISBN 978-0-387-29139-0, MR 2271992.
• De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), "Ehrhart polynomials and unimodular triangulations", Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, 25, Springer, p. 475, ISBN 978-3-642-12970-4.
• Diaz, Ricardo; Robins, Sinai (1996), "The Ehrhart polynomial of a lattice n-simplex", Electronic Research Announcements of the American Mathematical Society, 2: 1–6, doi:10.1090/S1079-6762-96-00001-7, MR 1405963. Introduces the Fourier analysis approach and gives references to other related articles.
• Ehrhart, Eugène (1962), "Sur les polyèdres rationnels homothétiques à n dimensions", Comptes rendus de l'Académie des Sciences, 254: 616–618, MR 0130860. Definition and first properties.
• Mathar, Richard J. (2010), Point counts of ${\displaystyle D_{k}}$ and some ${\displaystyle A_{k}}$ and ${\displaystyle E_{k}}$ integer lattices inside hypercubes, arXiv:1002.3844, Bibcode:2010arXiv1002.3844M
• Mustață, Mircea (February 2005), "Ehrhart polynomials", Lecture notes on toric varieties.