Three Ehrhart quasi-polynomials
Algebraic Combinatorics, Volume 2 (2019) no. 3, p. 379-416

Let 𝔭(b) d be a semi-rational parametric polytope, where b=(b j ) N is a real multi-parameter. We study intermediate sums of polynomial functions h(x) on 𝔭(b),

SL(𝔭(b),h)=y𝔭(b)(y+L)h(x)dx,

where we integrate over the intersections of 𝔭(b) with the subspaces parallel to a fixed rational subspace L through all lattice points, and sum the integrals. The purely discrete sum is of course a particular case (L=0), so S 0 (𝔭(b),1) counts the integer points in the parametric polytopes.

The chambers are the open conical subsets of N such that the shape of 𝔭(b) does not change when b runs over a chamber. We first prove that on every chamber of N , S L (𝔭(b),h) is given by a quasi-polynomial function of b N . 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 kd, we consider a particular linear combination of such intermediate weighted sums, which was introduced by Barvinok in order to compute efficiently the k+1 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 b, which we call Barvinok’s patched quasi-polynomial (at codimension level k).

Finally, for each chamber, we introduce a new quasi-polynomial function of b, the cone-by-cone patched quasi-polynomial (at codimension level k), defined in a refined way by linear combinations of intermediate generating functions for the cones at vertices of 𝔭(b).

We prove that both patched quasi-polynomials agree with the discrete weighted sum bS {0} (𝔭(b),h) in the terms corresponding to the k+1 highest polynomial degrees.

Received : 2018-03-27
Revised : 2018-10-25
Accepted : 2018-11-01
Published online : 2019-06-06
DOI : https://doi.org/10.5802/alco.46
Classification:  05A15,  52C07,  68R05,  68U05,  52B20
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},
     publisher = {MathOA foundation},
     volume = {2},
     number = {3},
     year = {2019},
     pages = {379-416},
     doi = {10.5802/alco.46},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_3_379_0}
}
Three Ehrhart quasi-polynomials. Algebraic Combinatorics, Volume 2 (2019) no. 3, pp. 379-416. doi : 10.5802/alco.46. https://alco.centre-mersenne.org/item/ALCO_2019__2_3_379_0/

[1] Baldoni, Velleda; Berline, Nicole; De Loera, Jesús A.; Dutra, Brandon; Köppe, Matthias; Moreinis, Stanislav; Pinto, Gregory; Vergne, Michèle; Wu, Jianqiu A User’s Guide for LattE integrale v1.7.3 (2015) http://www.math.ucdavis.edu/~latte/

[2] Baldoni, Velleda; Berline, Nicole; De Loera, Jesús A.; Köppe, Matthias; Vergne, Michèle How to Integrate a Polynomial over a Simplex, Math. Comput., Volume 80 (2011) no. 273, pp. 297-325 | Article | MR 2728981 | Zbl 1216.68120

[3] Baldoni, Velleda; Berline, Nicole; De Loera, Jesús A.; Köppe, Matthias; Vergne, Michèle Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra, Found. Comput. Math., Volume 12 (2012), pp. 435-469 | Article | MR 2946460

[4] Baldoni, Velleda; Berline, Nicole; De Loera, Jesús A.; Köppe, Matthias; Vergne, Michèle Intermediate Sums on Polyhedra II: Bidegree and Poisson formula, Mathematika, Volume 62 (2016), pp. 653-684 | Article | MR 3464986 | Zbl 1347.05005

[5] Baldoni, Velleda; Berline, Nicole; Köppe, Matthias; Vergne, Michèle Intermediate Sums on Polyhedra: Computation and Real Ehrhart Theory, Mathematika, Volume 59 (2013) no. 1, pp. 1-22 | Article | MR 3028168

[6] Barvinok, Alexander I. Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res., Volume 19 (1994), pp. 769-779 | Article | MR 1304623 | Zbl 0821.90085

[7] Barvinok, Alexander I. Computing the Ehrhart quasi-polynomial of a rational simplex, Math. Comput., Volume 75 (2006) no. 255, pp. 1449-1466 | Article | MR 2219037 | Zbl 1093.52009

[8] Barvinok, Alexander I. Integer Points in Polyhedra, European Mathematical Society, Zürich Lectures in Advanced Mathematics (2008), viii+190 pages | Zbl 1154.52009

[9] Beck, Matthias Multidimensional Ehrhart Reciprocity, J. Comb. Theory, Ser. A, Volume 97 (2002) no. 1, pp. 187-194 | Article | MR 1879135 | Zbl 1005.52006

[10] Berline, Nicole; Vergne, Michèle Analytic continuation of a parametric polytope and wall-crossing, Configuration Spaces: Geometry, Combinatorics and Topology, Edizioni della Normale (CRM Series) (2012) | Article | Zbl 1303.52003

[11] Björner, Anders; Lovász, László Linear decision trees, subspace arrangements and Möbius functions, J. Am. Math. Soc., Volume 7 (1994) no. 3, pp. 677-706 | Article | Zbl 0811.05070

[12] Brion, Michel; Vergne, Michèle Residue formulae, vector partition functions and lattice points in rational polytopes, J. Am. Math. Soc., Volume 10 (1997) no. 4, pp. 797-833 | Article | MR 1446364 | Zbl 0926.52016

[13] Clauss, Philippe; Loechner, Vincent Parametric analysis of polyhedral iteration spaces, Journal of VLSI Signal Processing, Volume 19 (1998) no. 2, pp. 179-194 | Article

[14] Henk, Martin; Linke, Eva Lattice points in vector-dilated polytopes (2012) (https://arxiv.org/abs/1204.6142 )

[15] Knutson, Allen; Tao, Terence The honeycomb model of GL n () tensor products. I. Proof of the saturation conjecture, J. Am. Math. Soc., Volume 12 (1999) no. 4, pp. 1055-1090 | Article | MR 1671451 | Zbl 0944.05097

[16] Köppe, Matthias; Verdoolaege, Sven Computing parametric rational generating functions with a primal Barvinok algorithm, Electron. J. Comb., Volume 15 (2008), R16, 19 pages | MR 2383436 | Zbl 1180.52014

[17] Linke, Eva Rational Ehrhart quasi-polynomials, J. Comb. Theory, Ser. A, Volume 118 (2011) no. 7, pp. 1966-1978 | Article | MR 2802181 | Zbl 1234.52010

[18] Mcmullen, Peter Representations of polytopes and polyhedral sets, Geom. Dedicata, Volume 2 (1973), pp. 83-99 | Article | MR 0326574 | Zbl 0273.52006

[19] Pemantle, Robin; Wilson, Mark C. Analytic Combinatorics in Several Variables, Cambridge University Press (2013) | Zbl 1297.05004

[20] Verdoolaege, Sven Incremental Loop Transformations and Enumeration of Parametric Sets, Department of Computer Science, K.U. Leuven (Belgium) (2005) (Ph. D. Thesis)

[21] Verdoolaege, Sven; Seghir, Rachid; Beyls, Kristof; Loechner, Vincent; Bruynooghe, Maurice Counting integer points in parametric polytopes using Barvinok’s rational functions, Algorithmica, Volume 48 (2007) no. 1, pp. 37-66 | Article | MR 2312001 | Zbl 1123.68023