Hostname: page-component-7b7567c8c-tnzcf Total loading time: 0 Render date: 2026-11-12T10:46:41.953Z Has data issue: false hasContentIssue false
  • English
  • Français

INTERMEDIATE SUMS ON POLYHEDRA II: BIDEGREE AND POISSON FORMULA

Part of:CombinatoricsDiscrete geometryDiscrete mathematics in relation to computer sciencePolytopes and polyhedra

Published online by Cambridge University Press:  29 February 2016

Velleda Baldoni,
Nicole Berline,
Jesús A. De Loera,
Matthias Köppe and
Michèle Vergne
Velleda Baldoni
Affiliation:
Dipartimento di Matematica, Università degli studi di Roma “Tor Vergata”, Via della Ricerca Scientifica 1, I-00133 Roma, Italy email baldoni@mat.uniroma2.it
Nicole Berline
Affiliation:
École Polytechnique, Centre de Mathématiques Laurent Schwartz, 91128 Palaiseau Cedex, France email Nicole.Berline@math.cnrs.fr
Jesús A. De Loera
Affiliation:
Department of Mathematics, University of California, Davis, One Shields Avenue, Davis, CA 95616, U.S.A. email deloera@math.ucdavis.edu
Matthias Köppe
Affiliation:
Department of Mathematics, University of California, Davis, One Shields Avenue, Davis, CA 95616, U.S.A. email mkoeppe@math.ucdavis.edu
Michèle Vergne
Affiliation:
Institut de Mathématiques de Jussieu – Paris Rive Gauche, Batiment Sophie Germain, Case 7012, 75205 Paris Cedex 13, France email michele.vergne@imj-prg.fr

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We continue our study of intermediate sums over polyhedra, interpolating between integrals and discrete sums, which were introduced by Barvinok [Computing the Ehrhart quasi-polynomial of a rational simplex. Math. Comp. 75 (2006), 1449–1466]. By well-known decompositions, it is sufficient to consider the case of affine cones $s+\mathfrak{c}$ , where $s$ is an arbitrary real vertex and $\mathfrak{c}$ is a rational polyhedral cone. For a given rational subspace  $L$ , we define the intermediate generating functions $S^{L}(s+\mathfrak{c})(\unicode[STIX]{x1D709})$ by integrating an exponential function over all lattice slices of the affine cone  $s+\mathfrak{c}$ parallel to the subspace  $L$ and summing up the integrals. We expose the bidegree structure in parameters $s$ and $\unicode[STIX]{x1D709}$ , which was implicitly used in the algorithms in our papers [Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Found. Comput. Math.12 (2012), 435–469] and [Intermediate sums on polyhedra: computation and real Ehrhart theory. Mathematika59 (2013), 1–22]. The bidegree structure is key to a new proof for the Baldoni–Berline–Vergne approximation theorem for discrete generating functions [Local Euler–Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes. Contemp. Math.452 (2008), 15–33], using the Fourier analysis with respect to the parameter  $s$ and a continuity argument. Our study also enables a forthcoming paper, in which we study intermediate sums over multi-parameter families of polytopes.

MSC classification

Primary:05A15: Exact enumeration problems, generating functions
Secondary:52C07: Lattices and convex bodies in $n$ dimensions68R05: Combinatorics68U05: Computer graphics; computational geometry52B20: Lattice polytopes (including relations with commutative algebra and algebraic geometry)

Information

Type
Research Article
Information
Mathematika , Volume 62 , Issue 3 , 2016, pp. 653 - 684
Copyright
Copyright © University College London 2016 

References

Baldoni, V., Berline, N., De Loera, J. A., Köppe, M. and Vergne, M., How to integrate a polynomial over a simplex. Math. Comp. 80(273) 2011, 297–325, doi:10.1090/S0025-5718-2010-02378-6.Google Scholar
Baldoni, V., Berline, N., De Loera, J. A., Köppe, M. and Vergne, M., Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Found. Comput. Math. 12 2012, 435–469, doi:10.1007/s10208-011-9106-4.Google Scholar
Baldoni, V., Berline, N., De Loera, J. A., Köppe, M. and Vergne, M., Three Ehrhart quasi-polynomials. Preprint, 2014, arXiv:1410.8632 [math.CO].Google Scholar
Baldoni, V., Berline, N., Köppe, M. and Vergne, M., Intermediate sums on polyhedra: computation and real Ehrhart theory. Mathematika 59(1) 2013, 1–22, doi:10.1112/S0025579312000101.CrossRefGoogle Scholar
Baldoni, V., Berline, N. and Vergne, M., Local Euler–Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes. Contemp. Math. 452 2008, 15–33.Google Scholar
Barvinok, A. I., Computing the volume, counting integral points, and exponential sums. Discrete Comput. Geom. 10(2) 1993, 123–141.Google Scholar
Barvinok, A. I., Computing the Ehrhart quasi-polynomial of a rational simplex. Math. Comp. 75(255) 2006, 1449–1466.Google Scholar
Barvinok, A. I., Integer points in polyhedra. In Zürich Lectures in Advanced Mathematics, European Mathematical Society (EMS) (Zürich, Switzerland, 2008).Google Scholar
Beck, M., Multidimensional Ehrhart reciprocity. J. Combin. Theor. Ser. A 97(1) 2002, 187–194, doi:10.1006/jcta.2001.3220.Google Scholar
Brion, M., Points entiers dans les polyèdres convexes. Ann. Sci. Éc. Norm. Supér. 21(4) 1988, 653–663.CrossRefGoogle Scholar
Brion, M. and Vergne, M., Residue formulae, vector partition functions and lattice points in rational polytopes. J. Amer. Math. Soc. 10(4) 1997, 797–833, doi:10.1090/S0894-0347-97-00242-7 ;MR 1446364 (98e:52008).Google Scholar
Clauss, P. and Loechner, V., Parametric analysis of polyhedral iteration spaces. J. VLSI Signal Process. 19(2) 1998, 179–194.CrossRefGoogle Scholar
Henk, M. and Linke, E., Lattice points in vector-dilated polytopes. Preprint, 2012, arXiv:1204.6142 [math.MG].Google Scholar
Köppe, M. and Verdoolaege, S., Computing parametric rational generating functions with a primal Barvinok algorithm. Electron. J. Combin. 15 2008, 1–19  #R16.Google Scholar
Linke, E., Rational Ehrhart quasi-polynomials. J. Combin. Theory Ser. A 118(7) 2011, 1966–1978, doi:10.1016/j.jcta.2011.03.007.Google Scholar
Verdoolaege, S., Incremental loop transformations and enumeration of parametric sets. PhD Thesis, Department of Computer Science, K.U. Leuven, Belgium, April 2005.Google Scholar
Verdoolaege, S., Seghir, R., Beyls, K., Loechner, V. and Bruynooghe, M., Counting integer points in parametric polytopes using Barvinok’s rational functions. Algorithmica 48(1) 2007, 37–66.CrossRefGoogle Scholar