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

Let $𝔭\left(b\right)\subset {ℝ}^{d}$ be a semi-rational parametric polytope, where $b=\left({b}_{j}\right)\in {ℝ}^{N}$ is a real multi-parameter. We study intermediate sums of polynomial functions $h\left(x\right)$ on $𝔭\left(b\right)$,

 ${S}^{L}\left(𝔭\left(b\right),h\right)=\sum _{y}{\int }_{𝔭\left(b\right)\cap \left(y+L\right)}h\left(x\right)\phantom{\rule{0.166667em}{0ex}}\mathrm{d}x,$

where we integrate over the intersections of $𝔭\left(b\right)$ 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}\left(𝔭\left(b\right),1\right)$ counts the integer points in the parametric polytopes.

The chambers are the open conical subsets of ${ℝ}^{N}$ such that the shape of $𝔭\left(b\right)$ does not change when $b$ runs over a chamber. We first prove that on every chamber of ${ℝ}^{N}$, ${S}^{L}\left(𝔭\left(b\right),h\right)$ is given by a quasi-polynomial function of $b\in {ℝ}^{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 $k\le d$, 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 $𝔭\left(b\right)$.

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

Revised:
Accepted:
Published online:
DOI: 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},
zbl = {07066881},
mrnumber = {3968744},
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
SP  - 379
EP  - 416
VL  - 2
IS  - 3
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.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 https://alco.centre-mersenne.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. 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 | DOI | MR | Zbl

[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 | DOI | MR

[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 | DOI | MR | Zbl

[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 | DOI | MR

[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 | DOI | MR | Zbl

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

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

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

[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 | DOI | Zbl

[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 | DOI | Zbl

[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 | DOI | MR | Zbl

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

[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 ${\mathrm{GL}}_{n}\left(ℂ\right)$ tensor products. I. Proof of the saturation conjecture, J. Am. Math. Soc., Volume 12 (1999) no. 4, pp. 1055-1090 | DOI | MR | Zbl

[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 | Zbl

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

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

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

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

[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 | DOI | MR | Zbl

Cited by Sources: