Editing Ehrhart polynomial

{{short description|Relation of an integral polytope's volume to how many integer points it encloses}}

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 point]]s the polytope contains. The theory of Ehrhart [[polynomial]]s 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 introduced them in the 1960s.

==Definition==
Informally, if {{math|''P''}} is a [[polytope]], and {{math|''tP''}} is the polytope formed by expanding {{math|''P''}} by a factor of {{math|''t''}} in each dimension, then {{math|''L''(''P'', ''t'')}} is the number of [[integer lattice]] points in {{math|''tP''}}.

More formally, consider a [[lattice (group)|lattice]] <math>\mathcal{L}</math> in [[Euclidean space]] <math>\R^n</math> and a {{math|''d''}}-[[dimension]]al polytope {{math|''P''}} in <math>\R^n</math> with the property that all vertices of the polytope are points of the lattice. (A common example is <math>\mathcal{L} = \Z^n</math> and a polytope for which all vertices have [[integer]] coordinates.) For any positive integer {{math|''t''}}, let {{math|''tP''}} be the {{math|''t''}}-fold dilation of {{math|''P''}} (the polytope formed by multiplying each vertex coordinate, in a basis for the lattice, by a factor of {{math|''t''}}), and let

:<math>L(P,t) = \#\left(tP \cap \mathcal{L}\right)</math>

be the number of lattice points contained in the polytope {{math|''tP''}}. Ehrhart showed in 1962 that {{math|''L''}} is a rational [[polynomial]] of degree {{math|''d''}} in {{math|''t''}}, i.e. there exist [[rational number]]s <math>L_0(P),\dots,L_d(P)</math> such that:

:<math>L(P, t) = L_d(P) t^d + L_{d-1}(P) t^{d-1} + \cdots + L_0(P)</math>

for all positive integers {{math|''t''}}.<ref name=ehrhart>{{citation
 | last = Ehrhart | first = Eugène | authorlink=Eugène Ehrhart
 | journal = [[Comptes rendus de l'Académie des Sciences]]
 | pages = 616–618
 | title = Sur les polyèdres rationnels homothétiques à ''n'' dimensions
 | volume = 254
 | year = 1962
 | mr=0130860}}</ref>

===Reciprocity property===

The Ehrhart polynomial of the [[interior (topology)|interior]] of a closed convex polytope {{math|''P''}} can be computed as:

:<math> L(\operatorname{int}(P), t) = (-1)^d L(P, -t),</math>

where {{math|''d''}} is the dimension of {{math|''P''}}. This result is known as Ehrhart–Macdonald reciprocity.<ref>Ehrhart, Eugène (1967), "Démonstration de la loi de réciprocité du polyèdre rationnel", ''Comptes Rendus de l'Academie des Sciences de Paris, Sér. A-B'' 265, A91–A94.</ref><ref>{{citation| last=Macdonald |first =Ian G.|authorlink=Ian G. Macdonald| title=Polynomials associated with finite cell-complexes|journal=[[Journal of the London Mathematical Society]]|year=1971|volume=2|issue=1|pages=181–192|doi=10.1112/jlms/s2-4.1.181 }}</ref>

==Examples==
[[File:Second dilate of a unit square.png|thumbnail|This is the second dilate, <math>t = 2</math>, of a unit square. It has nine integer points.]]

Let {{math|''P''}} be a {{math|''d''}}-dimensional [[unit cube|unit]] [[hypercube]] whose vertices are the integer lattice points all of whose coordinates are 0 or 1. In terms of inequalities,

:<math> P = \left\{x\in\R^d : 0 \le x_i \le 1; 1 \le i \le d\right\}.</math>

Then the {{math|''t''}}-fold dilation of {{math|''P''}} is a cube with side length {{math|''t''}}, containing {{math|(''t'' + 1)<sup>''d''</sup>}} integer points. That is, the Ehrhart polynomial of the hypercube is {{math|''L''(''P'',''t'') {{=}} (''t'' + 1)<sup>''d''</sup>}}.<ref>{{citation|title=Triangulations: Structures for Algorithms and Applications|volume=25|series=Algorithms and Computation in Mathematics|first1=Jesús A.|last1=De Loera|author1-link=Jesús A. De Loera|first2=Jörg|last2=Rambau|first3=Francisco|last3=Santos|author3-link= Francisco Santos Leal 
|publisher=Springer|year=2010|isbn=978-3-642-12970-4
|contribution=Ehrhart polynomials and unimodular triangulations
|page=475
|url=https://books.google.com/books?id=SxY1Xrr12DwC&pg=PA475}}</ref><ref>{{citation|first1=Richard J.|last1=Mathar|arxiv=1002.3844
|title=Point counts of <math>D_k</math> and some <math>A_k</math> and <math>E_k</math> integer lattices inside hypercubes
|year=2010
|bibcode=2010arXiv1002.3844M
}}</ref> Additionally, if we evaluate {{math|''L''(''P'', ''t'')}} at negative integers, then

: <math>L(P, -t) = (-1)^d (t - 1)^d = (-1)^d L(\operatorname{int}(P), t),</math>

as we would expect from Ehrhart–Macdonald reciprocity.

Many other [[figurate number]]s can be expressed as Ehrhart polynomials. For instance, the [[square pyramidal number]]s 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 {{math|{{sfrac|1|6}}(''t'' + 1)(''t'' + 2)(2''t'' + 3)}}.<ref>{{citation
 | last1 = Beck | first1 = Matthias
 | last2 = De Loera | first2 = Jesús A. | author2-link = Jesús A. De Loera
 | last3 = Develin | first3 = Mike | author3-link = Mike Develin
 | last4 = Pfeifle | first4 = Julian
 | last5 = Stanley | first5 = Richard P. | author5-link = Richard P. Stanley
 | contribution = Coefficients and roots of Ehrhart polynomials
 | location = Providence, RI
 | mr = 2134759
 | pages = 15–36
 | publisher = [[American Mathematical Society]]
 | series = Contemporary Mathematics
 | title = Integer Points in Polyhedra—Geometry, Number Theory, Algebra, Optimization
 | volume = 374
 | year = 2005}}</ref>

==Ehrhart quasi-polynomials==
Let {{math|''P''}} be a rational polytope. In other words, suppose

:<math>P = \left\{ x\in\R^d : Ax \le b\right\},</math>

where <math>A \in \Q^{k \times d}</math> and <math>b \in \Q^k.</math> (Equivalently, {{math|''P''}} is the [[convex hull]] of finitely many points in <math>\Q^d.</math>) Then define

:<math>L(P, t) = \#\left(\left\{x\in\Z^d : Ax \le tb \right\} \right). </math>

In this case, {{math|''L''(''P'', ''t'')}} is a [[quasi-polynomial]] in {{math|''t''}}. Just as with integral polytopes, Ehrhart–Macdonald reciprocity holds, that is,

: <math> L(\operatorname{int}(P), t) = (-1)^d L(P, -t). </math>

===Examples of Ehrhart quasi-polynomials===
Let {{math|''P''}} be a polygon with vertices (0,0), (0,2), (1,1) and ({{sfrac|3|2}}, 0). The number of integer points in {{math|''tP''}} will be counted by the quasi-polynomial <ref name=MR2271992>{{citation
 | last1 = Beck | first1 = Matthias
 | last2 = Robins | first2 = Sinai
 | mr = 2271992
 | isbn = 978-0-387-29139-0
 | location = New York
 | pages = [https://archive.org/details/computingcontinu00beck_082/page/n61 46]–47
 | publisher = Springer-Verlag
 | series = [[Undergraduate Texts in Mathematics]]
 | title = Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra
 | title-link = Computing the Continuous Discretely
 | year = 2007}}</ref>

: <math> L(P, t) = \frac{7t^2}{4} + \frac{5t}{2} + \frac{7 + (-1)^t}{8}. </math>

==Interpretation of coefficients==
If {{math|''P''}} is [[closed set|closed]] (i.e. the boundary faces belong to {{math|''P''}}), some of the coefficients of {{math|''L''(''P'', ''t'')}} have an easy interpretation:

* the leading coefficient, <math>L_d(P)</math>, is equal to the {{math|''d''}}-dimensional [[volume]] of {{math|''P''}}, divided by {{math|''d''(''L'')}} (see [[lattice (group)|lattice]] for an explanation of the content or covolume {{math|''d''(''L'')}} of a lattice);

* the second coefficient, <math>L_{d-1}(P)</math>, can be computed as follows: the lattice {{math|''L''}} induces a lattice {{math|''L<sub>F</sub>''}} on any face {{math|''F''}} of {{math|''P''}}; take the {{math|(''d'' − 1)}}-dimensional volume of {{math|''F''}}, divide by {{math|2''d''(''L<sub>F</sub>'')}}, and add those numbers for all faces of {{math|''P''}};

* the constant coefficient, <math>L_0(P)</math>, is the [[Euler characteristic]] of {{math|''P''}}. When {{math|''P''}} is a closed [[convex polytope]], <math>L_0(P)=1.</math>

==The Betke–Kneser theorem==
Ulrich Betke and [[Martin Kneser]]<ref>{{citation|last1=Betke|first1= Ulrich|last2= Kneser|first2=Martin|authorlink2=Martin Kneser| year=1985 | title=Zerlegungen und Bewertungen von Gitterpolytopen|journal= [[Crelle's Journal|Journal für die reine und angewandte Mathematik]] |volume=358|pages= 202–208|mr=0797683}}</ref> established the following characterization of the Ehrhart coefficients. A functional <math>Z</math> defined on integral polytopes is an <math>\operatorname{SL}(n,\Z)</math> and translation invariant [[Valuation (measure theory)|valuation]] if and only if there are real numbers <math>c_0,\ldots, c_n</math> such that

:<math> Z= c_0 L_0+\cdots +c_n L_n.</math>

==Ehrhart series==
We can define a [[generating function]] for the Ehrhart polynomial of an integral {{math|''d''}}-dimensional polytope {{math|''P''}} as

: <math> \operatorname{Ehr}_P(z) = \sum_{t\ge 0} L(P, t)z^t. </math>

This series can be expressed as a [[rational function]]. Specifically, Ehrhart proved (1962) that there exist complex numbers <math>h_j^*</math>, <math>0 \le j \le d</math>, such that the Ehrhart series of {{math|''P''}} is<ref name=ehrhart/>

:<math>\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.</math>

[[Richard P. Stanley]]'s non-negativity theorem states that under the given hypotheses, <math>h_j^*</math> will be non-negative integers, for <math>0 \le j \le d</math>.

Another result by Stanley shows that if {{math|''P''}} is a lattice polytope contained in {{math|''Q''}}, then <math>h_j^*(P) \le h_j^*(Q)</math> for all {{math|''j''}}.<ref>{{citation|last1=Stanley|first1=Richard|title=A monotonicity property of <math>h</math>-vectors and <math>h^*</math>-vectors|journal=[[European Journal of Combinatorics]]|year=1993|volume=14|issue=3 |pages=251–258 |doi=10.1006/eujc.1993.1028|doi-access=free}}</ref>  The <math>h^*</math>-vector is in general not unimodal, but it is whenever it is symmetric and the polytope has a regular unimodular triangulation.<ref>{{citation|last1=Athanasiadis|first1=Christos A.|title=''h''*-Vectors, Eulerian Polynomials and Stable Polytopes of Graphs| journal= [[Electronic Journal of Combinatorics]]| year=2004| volume=11| issue=2|doi=10.37236/1863| url= http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i2r6| doi-access=free}}</ref>

===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 {{math|''P''}}, where {{math|''D''}} is the smallest integer such that {{math|''DP''}} is an integer polytope ({{math|''D''}} is called the denominator of {{math|''P''}}), then one has

:<math>\operatorname{Ehr}_P(z) = \sum_{t\ge 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}},</math>

where the <math>h_j^*</math> are still non-negative integers.<ref>{{citation|last=Stanley|first=Richard P.|authorlink=Richard P. Stanley|title=Decompositions of rational convex polytopes|journal=Annals of Discrete Mathematics|date=1980|volume=6|pages=333–342| doi=10.1016/s0167-5060(08)70717-9|isbn=9780444860484}}</ref><ref>{{citation| last1=Beck| first1=Matthias| last2=Sottile| first2= Frank|title=Irrational proofs for three theorems of Stanley|journal=[[European Journal of Combinatorics]]|date=January 2007| volume =28|issue=1|pages=403–409|doi=10.1016/j.ejc.2005.06.003|arxiv=math/0501359| s2cid=7801569}}</ref>

== Non-leading coefficient bounds ==
The polynomial's non-leading coefficients <math>c_0,\dots,c_{d-1}</math> in the representation 

:<math>L(P,t) = \sum_{r=0}^d c_r t^r</math> 

can be upper bounded:<ref>{{citation|last1=Betke|first1=Ulrich |last2=McMullen|first2=Peter|author2-link=Peter McMullen|date=1985-12-01|title=Lattice points in lattice polytopes| journal=[[Monatshefte für Mathematik]]| language=en|volume=99|issue=4|pages=253–265|doi=10.1007/BF01312545|s2cid=119545615 |issn=1436-5081}}</ref>

:<math>c_r \leq |s(d,r)| c_d + \frac{1}{(d-1)!} |s(d,r+1)|</math>

where <math>s(n,k)</math> is the [[Stirling numbers of the first kind|Stirling number of the first kind]]. Lower bounds also exist.<ref>{{citation|last1=Henk|first1=Martin|last2=Tagami|first2=Makoto|date=2009-01-01|title=Lower bounds on the coefficients of Ehrhart polynomials|journal=[[European Journal of Combinatorics]]|volume=30|issue=1|pages=70–83|doi=10.1016/j.ejc.2008.02.009|issn=0195-6698| arxiv=0710.2665|s2cid=3026293}}</ref>

==Toric variety==
The case <math>n=d=2</math> and <math>t = 1</math> of these statements yields [[Pick's theorem]]. Formulas for the other coefficients are much harder to get; [[Todd class]]es of [[toric variety|toric varieties]], the [[Riemann–Roch theorem]] as well as [[Fourier analysis]] have been used for this purpose.

If {{math|''X''}} is the [[toric variety]] corresponding to the normal fan of {{math|''P''}}, then {{math|''P''}} defines an [[ample line bundle]] on {{math|''X''}}, and the Ehrhart polynomial of {{math|''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.<ref>{{citation|last1=Braun|first1=Benjamin|last2=Develin|first2=Mike|authorlink2=Mike Develin| title=Ehrhart Polynomial Roots and Stanley's Non-Negativity Theorem|publisher=[[American Mathematical Society]] |year=2008|volume=452|series=Contemporary Mathematics|pages=67–78| doi= 10.1090/conm/452/08773 |arxiv=math/0610399|isbn=9780821841730|s2cid=118496291}}</ref> Furthermore, some authors have pursued the question of how these polynomials could be classified.<ref>{{citation| last=Higashitani |first=Akihiro| title= Classification of Ehrhart Polynomials of Integral Simplices|journal=DMTCS Proceedings| year=2012| pages=587–594| url= http://www.math.nagoya-u.ac.jp/fpsac12/download/contributed/dmAR0152.pdf}}</ref>

==Generalizations==
It is possible to study the number of integer points in a polytope {{math|''P''}} if we dilate some facets of {{math|''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.<ref>{{citation| last=Beck |first= Matthias|title=Multidimensional Ehrhart reciprocity|journal=[[Journal of Combinatorial Theory]]|date=January 2002|volume=97|series=Series A| issue=1| pages=187–194| doi= 10.1006/jcta.2001.3220| arxiv= math/0111331|s2cid= 195227}}</ref>

Counting the number of integer points in semi-dilations of polytopes has applications<ref>{{citation| last=Lisonek| first=Petr| title= Combinatorial Families Enumerated by Quasi-polynomials|journal=[[Journal of Combinatorial Theory]]| year=2007| volume=114| series=Series A|issue=4|pages=619–630| doi=10.1016/j.jcta.2006.06.013| doi-access=free}}</ref> 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]]

==References==
{{reflist}}

==Further reading==
*{{citation
 | last1 = Diaz | first1 = Ricardo
 | last2 = Robins | first2 = Sinai
 | journal = Electronic Research Announcements of the American Mathematical Society
 | pages = 1–6
 | title = The Ehrhart polynomial of a lattice ''n''-simplex
 | volume = 2
 | year = 1996
 | mr = 1405963
 | doi = 10.1090/S1079-6762-96-00001-7| doi-access = free
 }}. Introduces the Fourier analysis approach and gives references to other related articles.
*{{citation
 | last = Mustață | first = Mircea | authorlink=Mircea Mustaţă 
 | contribution = Ehrhart polynomials
 | date = February 2005
 | title = Lecture notes on toric varieties
 | url = http://www.math.lsa.umich.edu/~mmustata/toric_var.html}}.

[[Category:Figurate numbers]]
[[Category:Polynomials]]
[[Category:Lattice points]]
[[Category:Polytopes]]