Three Ehrhart quasi-polynomials
Algebraic Combinatorics, Volume 2 (2019) no. 3, pp. 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),

S L (𝔭(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:
Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/alco.46
Classification: 05A15,  52C07,  68R05,  68U05,  52B20
Keywords: Ehrhart polynomials, generating functions, Barvinok’s algorithm, parametric polytopes
Baldoni, Velleda 1; Berline, Nicole 2; De Loera, Jesús A. 3; Köppe, Matthias 3; Vergne, Michèle 4

1. Dipartimento di Matematica Università degli studi di Roma “Tor Vergata” Via della ricerca scientifica 1 I-00133 Italy
2. École Polytechnique Centre de Mathématiques Laurent Schwartz 91128 Palaiseau Cedex France
3. Department of Mathematics University of California Davis One Shields Avenue Davis, CA, 95616 USA
4. Université Paris 7 Diderot Institut Mathématique de Jussieu Sophie Germain, case 75205 Paris Cedex 13 France
@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 = {https://alco.centre-mersenne.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
DA  - 2019///
SP  - 379
EP  - 416
VL  - 2
IS  - 3
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.46/
UR  - https://www.ams.org/mathscinet-getitem?mr=3968744
UR  - https://zbmath.org/?q=an%3A07066881
UR  - https://doi.org/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 https://doi.org/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. https://alco.centre-mersenne.org/articles/10.5802/alco.46/

[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, Zürich Lectures in Advanced Mathematics, European Mathematical Society, 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 (CRM Series), Edizioni della Normale, 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), Paper no. 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 (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

Cited by Sources: