Ehrhart polynomial

Last updated February 28, 2024

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.

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

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 $L_{0}(P),\dots ,L_{d}(P)$ such that:

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

for all positive integers $t$ .^[1]

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

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.^[2]

Examples

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,

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

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 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/6(t + 1)(t + 2)(2t + 3)$ .^[5]

Ehrhart quasi-polynomials

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

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

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

L(P,t)=\#\left(\left\{x\in \mathbb {Z} ^{d}: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,

L(\operatorname {int} (P),t)=(-1)^{d}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 ^[6]

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, $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, $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 $2 d (L F)$ , and add those numbers for all faces of $P$ ;

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

The Betke–Kneser theorem

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

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

\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 $h_{j}^{*}$ , $0\leq j\leq d$ , such that the Ehrhart series of $P$ is^[1]

\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, $h_{j}^{*}$ will be non-negative integers, for $0\leq j\leq d$ .

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

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

\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 $h_{j}^{*}$ are still non-negative integers.^[10]^[11]

Non-leading coefficient bounds

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

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

can be upper bounded:^[12]

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 $\left[{\begin{smallmatrix}n\\k\end{smallmatrix}}\right]$ is a Stirling number of the first kind. Lower bounds also exist.^[13]

Toric variety

The case $n=d=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.

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.^[14] Furthermore, some authors have pursued the question of how these polynomials could be classified.^[15]

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.^[16]

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

Related Research Articles

<span class="mw-page-title-main">Minkowski's theorem</span> Every symmetric convex set in R^n with volume > 2^n contains a non-zero integer point

In mathematics, Minkowski's theorem is the statement that every convex set in $which is symmetric with respect to the origin and which has volume greater than contains a non-zero integer point. The theorem was proved by Hermann Minkowski in 1889 and became the foundation of the branch of number theory called the geometry of numbers. It can be extended from the integers to any lattice and to any symmetric convex set with volume greater than, where denotes the covolume of the lattice.$

In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the original polynomial. The discriminant is widely used in polynomial factoring, number theory, and algebraic geometry.

Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in $and the study of these lattices provides fundamental information on algebraic numbers. The geometry of numbers was initiated by Hermann Minkowski.$

In mathematics, a modular form is a (complex) analytic function on the upper half-plane, $, that satisfies:$

In mathematics, in particular in algebraic topology, differential geometry and algebraic geometry, the Chern classes are characteristic classes associated with complex vector bundles. They have since become fundamental concepts in many branches of mathematics and physics, such as string theory, Chern–Simons theory, knot theory, Gromov–Witten invariants. Chern classes were introduced by Shiing-Shen Chern.

In algebraic geometry, a projective variety over an algebraically closed field k is a subset of some projective n-space $over k that is the zero-locus of some finite family of homogeneous polynomials of n + 1 variables with coefficients in k, that generate a prime ideal, the defining ideal of the variety. Equivalently, an algebraic variety is projective if it can be embedded as a Zariski closed subvariety of .$

In transcendental number theory, the Lindemann–Weierstrass theorem is a result that is very useful in establishing the transcendence of numbers. It states the following:

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In geometry and group theory, a lattice in the real coordinate space $is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension which spans the vector space . For any basis of, the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a regular tiling of a space by a primitive cell.$

In mathematics, the Mahler measure $of a polynomial with complex coefficients is defined as$

In commutative algebra, an element b of a commutative ring B is said to be integral over a subring A of B if b is a root of some monic polynomial over A.

In mathematics, a quasi-polynomial (pseudo-polynomial) is a generalization of polynomials. While the coefficients of a polynomial come from a ring, the coefficients of quasi-polynomials are instead periodic functions with integral period. Quasi-polynomials appear throughout much of combinatorics as the enumerators for various objects.

In mathematics, specifically in combinatorial commutative algebra, a convex lattice polytope P is called normal if it has the following property: given any positive integer n, every lattice point of the dilation nP, obtained from P by scaling its vertices by the factor n and taking the convex hull of the resulting points, can be written as the sum of exactly n lattice points in P. This property plays an important role in the theory of toric varieties, where it corresponds to projective normality of the toric variety determined by P. Normal polytopes have popularity in algebraic combinatorics. These polytopes also represent the homogeneous case of the Hilbert bases of finite positive rational cones and the connection to algebraic geometry is that they define projectively normal embeddings of toric varieties.

The study of integer points in convex polyhedra is motivated by questions such as "how many nonnegative integer-valued solutions does a system of linear equations with nonnegative coefficients have" or "how many solutions does an integer linear program have". Counting integer points in polyhedra or other questions about them arise in representation theory, commutative algebra, algebraic geometry, statistics, and computer science.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

The Bernstein–Kushnirenko theorem, proven by David Bernstein and Anatoliy Kushnirenko in 1975, is a theorem in algebra. It states that the number of non-zero complex solutions of a system of Laurent polynomial equations $is equal to the mixed volume of the Newton polytopes of the polynomials, assuming that all non-zero coefficients of are generic. A more precise statement is as follows:$

The order polynomial is a polynomial studied in mathematics, in particular in algebraic graph theory and algebraic combinatorics. The order polynomial counts the number of order-preserving maps from a poset to a chain of length $. These order-preserving maps were first introduced by Richard P. Stanley while studying ordered structures and partitions as a Ph.D. student at Harvard University in 1971 under the guidance of Gian-Carlo Rota.$

Short integer solution (SIS) and ring-SIS problems are two average-case problems that are used in lattice-based cryptography constructions. Lattice-based cryptography began in 1996 from a seminal work by Miklós Ajtai who presented a family of one-way functions based on SIS problem. He showed that it is secure in an average case if the shortest vector problem $(where for some constant) is hard in a worst-case scenario.$

In mathematics, the order polytope of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the unit interval, its vertices correspond to the upper sets of the partial order, and its dimension is the number of elements in the partial order. The order polytope is a distributive polytope, meaning that coordinatewise minima and maxima of pairs of its points remain within the polytope.

In mathematics, and especially differential and algebraic geometry, K-stability is an algebro-geometric stability condition, for complex manifolds and complex algebraic varieties. The notion of K-stability was first introduced by Gang Tian and reformulated more algebraically later by Simon Donaldson. The definition was inspired by a comparison to geometric invariant theory (GIT) stability. In the special case of Fano varieties, K-stability precisely characterises the existence of Kähler–Einstein metrics. More generally, on any compact complex manifold, K-stability is conjectured to be equivalent to the existence of constant scalar curvature Kähler metrics.

References

1 2 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
↑ Macdonald, Ian G. (1971), "Polynomials associated with finite cell-complexes", Journal of the London Mathematical Society , 2 (1): 181–192, doi:10.1112/jlms/s2-4.1.181
↑ 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, vol. 25, Springer, p. 475, ISBN 978-3-642-12970-4
↑ Mathar, Richard J. (2010), Point counts of $D_{k}$ and some $A_{k}$ and $E_{k}$ integer lattices inside hypercubes, arXiv: 1002.3844 , Bibcode:2010arXiv1002.3844M
↑ 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, vol. 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, pp. 46–47, ISBN 978-0-387-29139-0, MR 2271992
↑ Betke, Ulrich; Kneser, Martin (1985), "Zerlegungen und Bewertungen von Gitterpolytopen", Journal für die reine und angewandte Mathematik , 358: 202–208, MR 0797683
↑ Stanley, Richard (1993), "A monotonicity property of $h$ -vectors and $h^{*}$ -vectors", European Journal of Combinatorics , 14 (3): 251–258, doi: 10.1006/eujc.1993.1028
↑ Athanasiadis, Christos A. (2004), "h*-Vectors, Eulerian Polynomials and Stable Polytopes of Graphs", Electronic Journal of Combinatorics , 11 (2), doi: 10.37236/1863
↑ 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
↑ 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, S2CID 7801569
↑ 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, S2CID 119545615
↑ 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, S2CID 3026293
↑ Braun, Benjamin; Develin, Mike (2008), Ehrhart Polynomial Roots and Stanley's Non-Negativity Theorem, Contemporary Mathematics, vol. 452, American Mathematical Society, pp. 67–78, arXiv: math/0610399 , doi:10.1090/conm/452/08773, ISBN 9780821841730, S2CID 118496291
↑ Higashitani, Akihiro (2012), "Classification of Ehrhart Polynomials of Integral Simplices" (PDF), DMTCS Proceedings: 587–594
↑ 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, S2CID 195227
↑ 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