×

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

Software:

LattE
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Math. Ann. 296 (1993), no. 4, 625 – 635. · Zbl 0786.11035
[2] 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
[3] Alexander I. Barvinok, Computing the volume, counting integral points, and exponential sums, Discrete Comput. Geom. 10 (1993), no. 2, 123 – 141. · Zbl 0774.68054
[4] 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
[5] A. I. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Discrete Comput. Geom. 12 (1994), no. 1, 35 – 48. · Zbl 0804.52009
[6] 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
[7] 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
[8] M. Beck and F. Sottile, Irrational proofs for three theorems of Stanley, preprint arXiv math.CO/0501359, 2005. · Zbl 1109.05017
[9] Richard Bellman, A brief introduction to theta functions, Athena Series: Selected Topics in Mathematics, Holt, Rinehart and Winston, New York, 1961. · Zbl 0098.28301
[10] 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.
[11] 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
[12] J. A. De Loera, R. Hemmecke, M. Köppe, and R. Weismantel, Integer polynomial optimization in fixed dimension, preprint, arXiv: math.OC/0410111, 2004.
[13] R. Diaz and S. Robins, Solid angles, lattice points, and the Fourier decomposition of polytopes, manuscript, 1994.
[14] 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
[15] 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
[16] 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
[17] Peter D. Lax, Functional analysis, Pure and Applied Mathematics (New York), Wiley-Interscience [John Wiley & Sons], New York, 2002. · Zbl 1009.47001
[18] Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. · Zbl 0999.52006
[19] P. McMullen, Lattice invariant valuations on rational polytopes, Arch. Math. (Basel) 31 (1978/79), no. 5, 509 – 516. · Zbl 0387.52007
[20] Peter McMullen, Valuations and dissections, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 933 – 988. · Zbl 0791.52014
[21] Peter McMullen and Rolf Schneider, Valuations on convex bodies, Convexity and its applications, Birkhäuser, Basel, 1983, pp. 170 – 247. · Zbl 0534.52001
[22] Robert Morelli, Pick’s theorem and the Todd class of a toric variety, Adv. Math. 100 (1993), no. 2, 183 – 231. · Zbl 0797.14018
[23] 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
[24] Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. · Zbl 0798.52001
[25] 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
[26] 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.
[27] 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.