Let be a semi-rational parametric polytope, where is a real multi-parameter. We study intermediate sums of polynomial functions on ,
where we integrate over the intersections of with the subspaces parallel to a fixed rational subspace through all lattice points, and sum the integrals. The purely discrete sum is of course a particular case (), so counts the integer points in the parametric polytopes.
The chambers are the open conical subsets of such that the shape of does not change when runs over a chamber. We first prove that on every chamber of , is given by a quasi-polynomial function of . A key point of our paper is an analysis of the interplay between two notions of degree on quasi-polynomials: the usual polynomial degree and a filtration, called the local degree.
Then, for a fixed , we consider a particular linear combination of such intermediate weighted sums, which was introduced by Barvinok in order to compute efficiently the highest coefficients of the Ehrhart quasi-polynomial which gives the number of points of a dilated rational polytope. Thus, for each chamber, we obtain a quasi-polynomial function of , which we call Barvinok’s patched quasi-polynomial (at codimension level ).
Finally, for each chamber, we introduce a new quasi-polynomial function of , the cone-by-cone patched quasi-polynomial (at codimension level ), defined in a refined way by linear combinations of intermediate generating functions for the cones at vertices of .
We prove that both patched quasi-polynomials agree with the discrete weighted sum in the terms corresponding to the highest polynomial degrees.
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.46
Keywords: Ehrhart polynomials, generating functions, Barvinok’s algorithm, parametric polytopes
@article{ALCO_2019__2_3_379_0, author = {Baldoni, Velleda and Berline, Nicole and De Loera, Jes\'us A. and K\"oppe, Matthias and Vergne, Mich\`ele}, title = {Three {Ehrhart} quasi-polynomials}, journal = {Algebraic Combinatorics}, pages = {379--416}, publisher = {MathOA foundation}, volume = {2}, number = {3}, year = {2019}, doi = {10.5802/alco.46}, mrnumber = {3968744}, zbl = {07066881}, language = {en}, url = {http://www.numdam.org/articles/10.5802/alco.46/} }
TY - JOUR AU - Baldoni, Velleda AU - Berline, Nicole AU - De Loera, Jesús A. AU - Köppe, Matthias AU - Vergne, Michèle TI - Three Ehrhart quasi-polynomials JO - Algebraic Combinatorics PY - 2019 SP - 379 EP - 416 VL - 2 IS - 3 PB - MathOA foundation UR - http://www.numdam.org/articles/10.5802/alco.46/ DO - 10.5802/alco.46 LA - en ID - ALCO_2019__2_3_379_0 ER -
%0 Journal Article %A Baldoni, Velleda %A Berline, Nicole %A De Loera, Jesús A. %A Köppe, Matthias %A Vergne, Michèle %T Three Ehrhart quasi-polynomials %J Algebraic Combinatorics %D 2019 %P 379-416 %V 2 %N 3 %I MathOA foundation %U http://www.numdam.org/articles/10.5802/alco.46/ %R 10.5802/alco.46 %G en %F ALCO_2019__2_3_379_0
Baldoni, Velleda; Berline, Nicole; De Loera, Jesús A.; Köppe, Matthias; Vergne, Michèle. Three Ehrhart quasi-polynomials. Algebraic Combinatorics, Volume 2 (2019) no. 3, pp. 379-416. doi : 10.5802/alco.46. http://www.numdam.org/articles/10.5802/alco.46/
[1] A User’s Guide for LattE integrale v1.7.3, 2015 http://www.math.ucdavis.edu/~latte/
[2] How to Integrate a Polynomial over a Simplex, Math. Comput., Volume 80 (2011) no. 273, pp. 297-325 | DOI | MR | Zbl
[3] Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra, Found. Comput. Math., Volume 12 (2012), pp. 435-469 | DOI | MR
[4] Intermediate Sums on Polyhedra II: Bidegree and Poisson formula, Mathematika, Volume 62 (2016), pp. 653-684 | DOI | MR | Zbl
[5] Intermediate Sums on Polyhedra: Computation and Real Ehrhart Theory, Mathematika, Volume 59 (2013) no. 1, pp. 1-22 | DOI | MR
[6] Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res., Volume 19 (1994), pp. 769-779 | DOI | MR | Zbl
[7] Computing the Ehrhart quasi-polynomial of a rational simplex, Math. Comput., Volume 75 (2006) no. 255, pp. 1449-1466 | DOI | MR | Zbl
[8] Integer Points in Polyhedra, Zürich Lectures in Advanced Mathematics, European Mathematical Society, 2008, viii+190 pages | Zbl
[9] Multidimensional Ehrhart Reciprocity, J. Comb. Theory, Ser. A, Volume 97 (2002) no. 1, pp. 187-194 | DOI | MR | Zbl
[10] Analytic continuation of a parametric polytope and wall-crossing, Configuration Spaces: Geometry, Combinatorics and Topology (CRM Series), Edizioni della Normale, 2012 | DOI | Zbl
[11] Linear decision trees, subspace arrangements and Möbius functions, J. Am. Math. Soc., Volume 7 (1994) no. 3, pp. 677-706 | DOI | Zbl
[12] Residue formulae, vector partition functions and lattice points in rational polytopes, J. Am. Math. Soc., Volume 10 (1997) no. 4, pp. 797-833 | DOI | MR | Zbl
[13] Parametric analysis of polyhedral iteration spaces, Journal of VLSI Signal Processing, Volume 19 (1998) no. 2, pp. 179-194 | DOI
[14] Lattice points in vector-dilated polytopes (2012) (https://arxiv.org/abs/1204.6142)
[15] The honeycomb model of tensor products. I. Proof of the saturation conjecture, J. Am. Math. Soc., Volume 12 (1999) no. 4, pp. 1055-1090 | DOI | MR | Zbl
[16] Computing parametric rational generating functions with a primal Barvinok algorithm, Electron. J. Comb., Volume 15 (2008), R16, 19 pages | MR | Zbl
[17] Rational Ehrhart quasi-polynomials, J. Comb. Theory, Ser. A, Volume 118 (2011) no. 7, pp. 1966-1978 | DOI | MR | Zbl
[18] Representations of polytopes and polyhedral sets, Geom. Dedicata, Volume 2 (1973), pp. 83-99 | DOI | MR | Zbl
[19] Analytic Combinatorics in Several Variables, Cambridge University Press, 2013 | Zbl
[20] Incremental Loop Transformations and Enumeration of Parametric Sets, Ph. D. Thesis, Department of Computer Science, K.U. Leuven (Belgium) (2005)
[21] Counting integer points in parametric polytopes using Barvinok’s rational functions, Algorithmica, Volume 48 (2007) no. 1, pp. 37-66 | DOI | MR | Zbl
Cited by Sources: