## Computing the Ehrhart quasi-polynomial of a rational simplex.(English)Zbl 1093.52009

To a rational polytope $$P \subset {\mathbb R}^d$$ (i.e., the convex hull of finitely many points in $${\mathbb Q}^d$$), we associate the integer-point counting function $$L_P(t) := \# (tP \cap {\mathbb Z}^d)$$, defined for positive integers $$t$$. E. Ehrhart’s central theorem [C. R. Acad. Sci., Paris 254, 616–618 (1962; Zbl 0100.27601)] asserts that $$L_P$$ is a quasi-polynomial in $$t$$, i.e., $$L_P$$ is of the form $L_P(t) = c_n(t) t^d + c_{ n-1 }(t) t^{ n-1 } + \cdots + c_1(t) \, t + c_0(t),$ where $$c_0, c_1, \dots, c_n$$ are periodic functions of $$t$$. If $$P$$ is an integral polytope, i.e., the vertices of $$P$$ are in $${\mathbb Z}^d$$, then the period of $$c_0, c_1, \dots, c_n$$ is one, i.e., $$L_P$$ is a polynomial.
Regarding the computational complexity of $$L_P$$, a fundamental theorem of A. I. Barvinok [Math. Oper. Res. 19, No. 4, 769–779 (1994; Zbl 0821.90085)] states that in fixed dimension, the rational generating function $$\sum_{ t \geq 0 } L_P(t) x^t$$ can be computed in time polynomial in the input data of $$P$$. (If the dimension is not fixed, it is already an NP-hard problem to check whether there is an integer point in $$P$$, even if $$P$$ is a rational simplex.) Barvinok’s theorem implies that for an integral $$d$$-simplex $$\Delta$$, we can compute the first $$k$$ coefficients of the Ehrhart polynomial $$L_\Delta$$ in polynomial time if we fix $$k$$ and let $$d$$ vary.
In the paper under review, Barvinok extends this result to the rational case. More precisely, the main theorem is as follows: For a fixed integer $$k \geq 0$$, there exists a polynomial-time algorithm that, given any integer $$d \geq k$$, a rational simplex $$\Delta \subset {\mathbb R}^d$$, and an integer $$j \geq 0$$, computes the value of $$c_{ d-k } (j)$$. The underlying algorithm is based on a structural result that relates $$c_{ d-k } (j)$$ to volumes of sections of $$\Delta$$ by affine lattice subspaces parallel to faces of $$\Delta$$ of dimension $$\geq d-k$$.

### MSC:

 52C07 Lattices and convex bodies in $$n$$ dimensions (aspects of discrete geometry) 05A15 Exact enumeration problems, generating functions 68R05 Combinatorics in computer science

### Citations:

Zbl 0100.27601; Zbl 0821.90085

LattE
Full Text:

### References:

  W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Math. Ann. 296 (1993), no. 4, 625 – 635. · Zbl 0786.11035  A. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, preprint TRITA-MAT-1992-0036 (1992), Royal Institute of Technology, Stockholm. · Zbl 0804.52009  Alexander I. Barvinok, Computing the volume, counting integral points, and exponential sums, Discrete Comput. Geom. 10 (1993), no. 2, 123 – 141. · Zbl 0774.68054  Alexander I. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), no. 4, 769 – 779. · Zbl 0821.90085  A. I. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Discrete Comput. Geom. 12 (1994), no. 1, 35 – 48. · Zbl 0804.52009  Alexander Barvinok and James E. Pommersheim, An algorithmic theory of lattice points in polyhedra, New perspectives in algebraic combinatorics (Berkeley, CA, 1996 – 97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 91 – 147. · Zbl 0940.05004  Alexander Barvinok and Kevin Woods, Short rational generating functions for lattice point problems, J. Amer. Math. Soc. 16 (2003), no. 4, 957 – 979. · Zbl 1017.05008  M. Beck and F. Sottile, Irrational proofs for three theorems of Stanley, preprint arXiv math.CO/0501359, 2005. · Zbl 1109.05017  Richard Bellman, A brief introduction to theta functions, Athena Series: Selected Topics in Mathematics, Holt, Rinehart and Winston, New York, 1961. · Zbl 0098.28301  K. Beyls, M. Bruynooghe, V. Loechner, R. Seghir, and S. Verdoolaege Analytical computation of Ehrhart polynomials: Enabling more compiler analyses and optimizations, Proceedings of the 2004 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, ACM Press, New York, 2004 pp. 248-258; see also http:// www.kotnet.org/$$^\sim$$skimo/barvinok.  Jesús A. De Loera, Raymond Hemmecke, Jeremiah Tauzer, and Ruriko Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38 (2004), no. 4, 1273 – 1302. · Zbl 1137.52303  J. A. De Loera, R. Hemmecke, M. Köppe, and R. Weismantel, Integer polynomial optimization in fixed dimension, preprint, arXiv: math.OC/0410111, 2004.  R. Diaz and S. Robins, Solid angles, lattice points, and the Fourier decomposition of polytopes, manuscript, 1994.  Ricardo Diaz and Sinai Robins, The Ehrhart polynomial of a lattice polytope, Ann. of Math. (2) 145 (1997), no. 3, 503 – 518. , https://doi.org/10.2307/2951842 Ricardo Diaz and Sinai Robins, Erratum: ”The Ehrhart polynomial of a lattice polytope”, Ann. of Math. (2) 146 (1997), no. 1, 237. , https://doi.org/10.2307/2951835 Ricardo Diaz and Sinai Robins, The Ehrhart polynomial of a lattice polytope, Ann. of Math. (2) 145 (1997), no. 3, 503 – 518. , https://doi.org/10.2307/2951842 Ricardo Diaz and Sinai Robins, Erratum: ”The Ehrhart polynomial of a lattice polytope”, Ann. of Math. (2) 146 (1997), no. 1, 237. · Zbl 0874.52009  Peter Gritzmann and Victor Klee, On the complexity of some basic problems in computational convexity. II. Volume and mixed volumes, Polytopes: abstract, convex and computational (Scarborough, ON, 1993) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 440, Kluwer Acad. Publ., Dordrecht, 1994, pp. 373 – 466. · Zbl 0819.52008  Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, 2nd ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. · Zbl 0837.05001  Peter D. Lax, Functional analysis, Pure and Applied Mathematics (New York), Wiley-Interscience [John Wiley & Sons], New York, 2002. · Zbl 1009.47001  Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. · Zbl 0999.52006  P. McMullen, Lattice invariant valuations on rational polytopes, Arch. Math. (Basel) 31 (1978/79), no. 5, 509 – 516. · Zbl 0387.52007  Peter McMullen, Valuations and dissections, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 933 – 988. · Zbl 0791.52014  Peter McMullen and Rolf Schneider, Valuations on convex bodies, Convexity and its applications, Birkhäuser, Basel, 1983, pp. 170 – 247. · Zbl 0534.52001  Robert Morelli, Pick’s theorem and the Todd class of a toric variety, Adv. Math. 100 (1993), no. 2, 183 – 231. · Zbl 0797.14018  James Pommersheim and Hugh Thomas, Cycles representing the Todd class of a toric variety, J. Amer. Math. Soc. 17 (2004), no. 4, 983 – 994. · Zbl 1049.14038  Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. · Zbl 0798.52001  Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. · Zbl 0665.90063  V. N. Shevchenko, Qualitative topics in integer linear programming, Translations of Mathematical Monographs, vol. 156, American Mathematical Society, Providence, RI, 1997. Translated from the Russian by H. H. McFaden.  Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. · Zbl 0889.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.