Computing the Ehrhart quasi-polynomial of a rational simplex

Barvinok, Alexander

doi:10.1090/S0025-5718-06-01836-9

Computing the Ehrhart quasi-polynomial of a rational simplex
HTML articles powered by AMS MathViewer

by Alexander Barvinok;

Math. Comp. 75 (2006), 1449-1466

DOI: https://doi.org/10.1090/S0025-5718-06-01836-9

Published electronically: March 10, 2006

PDF | Request permission

Abstract:

We present a polynomial time algorithm to compute any fixed number of the highest coefficients of the Ehrhart quasi-polynomial of a rational simplex. Previously such algorithms were known for integer simplices and for rational polytopes of a fixed dimension. The algorithm is based on the formula relating the $k$th coefficient of the Ehrhart quasi-polynomial of a rational polytope to volumes of sections of the polytope by affine lattice subspaces parallel to $k$-dimensional faces of the polytope. We discuss possible extensions and open questions.

References

W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers, Math. Ann. 296 (1993), no. 4, 625–635. MR 1233487, DOI 10.1007/BF01445125
A. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, preprint TRITA-MAT-1992-0036 (1992), Royal Institute of Technology, Stockholm.
Alexander I. Barvinok, Computing the volume, counting integral points, and exponential sums, Discrete Comput. Geom. 10 (1993), no. 2, 123–141. MR 1220543, DOI 10.1007/BF02573970
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. MR 1304623, DOI 10.1287/moor.19.4.769
A. I. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Discrete Comput. Geom. 12 (1994), no. 1, 35–48. MR 1280575, DOI 10.1007/BF02574364
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. MR 1731815
Alexander Barvinok and Kevin Woods, Short rational generating functions for lattice point problems, J. Amer. Math. Soc. 16 (2003), no. 4, 957–979. MR 1992831, DOI 10.1090/S0894-0347-03-00428-4
M. Beck and F. Sottile, Irrational proofs for three theorems of Stanley, preprint arXiv math.CO/0501359, 2005.
Richard Bellman, A brief introduction to theta functions, Athena Series: Selected Topics in Mathematics, Holt, Rinehart and Winston, New York, 1961. MR 125252, DOI 10.1017/s0025557200044491
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. MR 2094541, DOI 10.1016/j.jsc.2003.04.003
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. MR 1454701, DOI 10.2307/2951842
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. MR 1322071
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. MR 1261419, DOI 10.1007/978-3-642-78240-4
Peter D. Lax, Functional analysis, Pure and Applied Mathematics (New York), Wiley-Interscience [John Wiley & Sons], New York, 2002. MR 1892228
Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
P. McMullen, Lattice invariant valuations on rational polytopes, Arch. Math. (Basel) 31 (1978/79), no. 5, 509–516. MR 526617, DOI 10.1007/BF01226481
Peter McMullen, Valuations and dissections, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 933–988. MR 1243000
Peter McMullen and Rolf Schneider, Valuations on convex bodies, Convexity and its applications, Birkhäuser, Basel, 1983, pp. 170–247. MR 731112
Robert Morelli, Pick’s theorem and the Todd class of a toric variety, Adv. Math. 100 (1993), no. 2, 183–231. MR 1234309, DOI 10.1006/aima.1993.1033
James Pommersheim and Hugh Thomas, Cycles representing the Todd class of a toric variety, J. Amer. Math. Soc. 17 (2004), no. 4, 983–994. MR 2083474, DOI 10.1090/S0894-0347-04-00460-6
Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521, DOI 10.1017/CBO9780511526282
Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
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. MR 1414900, DOI 10.1090/mmono/156
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. MR 1442260, DOI 10.1017/CBO9780511805967