365体育网站

365体育网站Advertisement

Springer Nature is making SARS-CoV-2 and COVID-19 research free. View research | View latest news | Sign up for updates

Local formulas for Ehrhart coefficients from lattice tiles

Abstract

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.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

References

  1. 365体育网站Beck, M., Robins, S.: Computing the continuous discretely, 2nd edn. Springer, New York (2015)

  2. 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)

  3. Barvinok, A.I.: Integer points in polyhedra. Zurich Lectures in Advanced Mathematics, European Mathematical Society, Zürich (2008)

  4. Berline, N., Vergne, M.: Local Euler McLaurin formula for polytopes. Mosc. Math. J. 7(3), 355–386 (2007)

  5. 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)

  6. Castillo, F., Liu, F.: Berline-Vergne valuation and generalized permutohedra. preprint: (2015)

  7. Cohen, J., Hickey, T.: Two algorithms for determining volumes of convex polyhedra. J. ACM (JACM) 26(3), 401–414 (1979)

  8. Danilov, V.I.: The geometry of toric varieties. Russ. Math. Surv. 33(2), 97–154 (1978)

  9. Dyer, M.E., Frieze, A.M.: The complexity of computing the volume of a polyhedron. SIAM J. Comput. 17365体育网站, 967–974 (1988)

  10. Ehrhart, E.: Sur les polyèdres rationnels homothétiques à n dimensions. C. R. Acad. Sci. Paris 254, 616–618 (1962)

  11. 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)

  12. Lawrence, J.: Polytope volume computation. Math. Comput. 57365体育网站(195), 259–271 (1991)

  13. 365体育网站Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems. Kluwer Academic Publishers, Norwell (2002)

  14. Morelli, R.: Pick’s theorem and the Todd class of a toric variety. Adv. Math. 100, 183–231 (1993)

  15. McMullen, P.: Lattice invariant valuations on rational polytopes. Arch. Math. 31, 509–516 (1978)

  16. McMullen, P.: Weakly continuous valuations on convex polytopes. Arch. Math. 41, 555–564 (1983)

  17. 365体育网站Pick, G.: Geometrisches zur Zahlenlehre, Sitzungsberichte des deutschen naturwissenschaftlich-medicinischen Vereines für Böhmen Lotos in Prag, pp. 311–319 (1899)

  18. Pommersheim, J.E., Thomas, H.: Cycles representing the Todd class of a toric variety. J. Am. Math. Soc. 17365体育网站, 983–994 (2004)

  19. Postnikov, A., Reiner, V., Williams, L.: Faces of generalized permutohedra. Doc. Math. 13365体育网站, 207–273 (2008)

  20. Ring, M.: Ph.D. thesis, University of Rostock (2019) (in preparation)

  21. SageMath: the Sage Mathematics Software (Version 7.4). (2016)

  22. Ziegler, G.M.: Lectures on polytopes, 2nd printing. Springer, New York (1997)

Download references

Acknowledgements

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.

Author information

Correspondence to Achill Schürmann.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

Keywords

  • Ehrhart coefficients
  • Local formula
  • Lattice tiling

Mathematics Subject Classification

  • 52C
  • 52B
  • 11H