As shown by McMullen in 1983, the coefficients of the Ehrhart polynomial of a lattice polytope can be written as a weighted sum of facial volumes. The weights in such a local formula depend only on the outer normal cones of faces, but are far from being unique. In this paper, we develop an infinite class of such local formulas. These are based on choices of fundamental domains in sublattices and obtained by polyhedral volume computations. We hereby also give a kind of geometric interpretation for the Ehrhart coefficients. Since our construction gives us a great variety of possible local formulas, these can, for instance, be chosen to fit well with a given polyhedral symmetry group. In contrast to other constructions of local formulas, ours does not rely on triangulations of rational cones into simplicial or even unimodular ones.
This is a preview of subscription content, log in365体育网站 to check access.
Buy single article
Instant access to the full article PDF.
Price includes VAT for USA
Subscribe to journal
365体育网站Immediate online access to all issues from 2019. Subscription will auto renew annually.
This is the net price365体育网站. Taxes to be calculated in checkout.
365体育网站Beck, M., Robins, S.: Computing the continuous discretely, 2nd edn. Springer, New York (2015)
Barvinok, A.I.: A polynomial-time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19365体育网站, 769–779 (1994)
Barvinok, A.I.: Integer points in polyhedra. Zurich Lectures in Advanced Mathematics, European Mathematical Society, Zürich (2008)
Berline, N., Vergne, M.: Local Euler McLaurin formula for polytopes. Mosc. Math. J. 7(3), 355–386 (2007)
365体育网站Büeler, B., Enge, A., Fukuda, K.: Exact volume computation for convex polytopes: a practical study, In: Kalai, G., Ziegler G. (Eds.), Polytopes, Combinatorics and Computation, in: DMV-Seminar, vol. 29, Birkhauser Verlag (2000)
Castillo, F., Liu, F.: Berline-Vergne valuation and generalized permutohedra. preprint: (2015)
Cohen, J., Hickey, T.: Two algorithms for determining volumes of convex polyhedra. J. ACM (JACM) 26(3), 401–414 (1979)
Danilov, V.I.: The geometry of toric varieties. Russ. Math. Surv. 33(2), 97–154 (1978)
Dyer, M.E., Frieze, A.M.: The complexity of computing the volume of a polyhedron. SIAM J. Comput. 17365体育网站, 967–974 (1988)
Ehrhart, E.: Sur les polyèdres rationnels homothétiques à n dimensions. C. R. Acad. Sci. Paris 254, 616–618 (1962)
Lasserre, J.-B.: An analytical expression and an algorithm for the volume of a convex polyhedron in Rn. J. Optim. Theor. Appl. 39365体育网站, 363–377 (1983)
Lawrence, J.: Polytope volume computation. Math. Comput. 57365体育网站(195), 259–271 (1991)
365体育网站Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems. Kluwer Academic Publishers, Norwell (2002)
Morelli, R.: Pick’s theorem and the Todd class of a toric variety. Adv. Math. 100, 183–231 (1993)
McMullen, P.: Lattice invariant valuations on rational polytopes. Arch. Math. 31, 509–516 (1978)
McMullen, P.: Weakly continuous valuations on convex polytopes. Arch. Math. 41, 555–564 (1983)
365体育网站Pick, G.: Geometrisches zur Zahlenlehre, Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen Lotos in Prag, pp. 311–319 (1899)
Pommersheim, J.E., Thomas, H.: Cycles representing the Todd class of a toric variety. J. Am. Math. Soc. 17365体育网站, 983–994 (2004)
Postnikov, A., Reiner, V., Williams, L.: Faces of generalized permutohedra. Doc. Math. 13365体育网站, 207–273 (2008)
Ring, M.: Ph.D. thesis, University of Rostock (2019) (in preparation)
SageMath: the Sage Mathematics Software (Version 7.4). (2016)
Ziegler, G.M.: Lectures on polytopes, 2nd printing. Springer, New York (1997)
365体育网站We like to thank the two anonymous referees, as well as Frieder Ladisch and Erik Friese for valuable comments. Moreover, Maren H. Ring is grateful for support by a Ph.D. scholarship of Studienstiftung des Deutschen Volkes (German Academic Foundation). Both authors gratefully acknowledge support by DFG Grant SCHU 1503/6-1.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
About this article
Cite this article
Ring, M.H., Schürmann, A. Local formulas for Ehrhart coefficients from lattice tiles. Beitr Algebra Geom 61, 365体育网站157–185 (2020). http://doi.org/10.1007/s13366-019-00457-8
- Ehrhart coefficients
- Local formula
- Lattice tiling
Mathematics Subject Classification