Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 

 

Generalized Ehrhart polynomials


Authors: Sheng Chen, Nan Li and Steven V Sam
Journal: Trans. Amer. Math. Soc. 364 (2012), 551-569
MSC (2010): Primary 11D45; Secondary 11D04, 52C07, 05A16
Published electronically: June 29, 2011
MathSciNet review: 2833591
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ P$ be a polytope with rational vertices. A classical theorem of Ehrhart states that the number of lattice points in the dilations $ P(n) = nP$ is a quasi-polynomial in $ n$. We generalize this theorem by allowing the vertices of $ P(n)$ to be arbitrary rational functions in $ n$. In this case we prove that the number of lattice points in $ P(n)$ is a quasi-polynomial for $ n$ sufficiently large. Our work was motivated by a conjecture of Ehrhart on the number of solutions to parametrized linear Diophantine equations whose coefficients are polynomials in $ n$, and we explain how these two problems are related.


References [Enhancements On Off] (What's this?)

  • [Bar] Alexander Barvinok, Integer points in polyhedra, Zurich Lectures in Advanced Mathematics, European Mathematical Society (EMS), Zürich, 2008. MR 2455889
  • [BR] Matthias Beck and Sinai Robins, Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, New York, 2007. Integer-point enumeration in polyhedra. MR 2271992
  • [Ehr] E. Ehrhart, Polynômes arithmétiques et méthode des polyèdres en combinatoire, Birkhäuser Verlag, Basel-Stuttgart, 1977. International Series of Numerical Mathematics, Vol. 35. MR 0432556
  • [New] Morris Newman, Integral matrices, Academic Press, New York-London, 1972. Pure and Applied Mathematics, Vol. 45. MR 0340283
  • [Sta] 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
  • [Xu] Zhiqiang Xu, An explicit formulation for two dimensional vector partition functions, Integer points in polyhedra—geometry, number theory, representation theory, algebra, optimization, statistics, Contemp. Math., vol. 452, Amer. Math. Soc., Providence, RI, 2008, pp. 163–178. MR 2405771, 10.1090/conm/452/08781

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 11D45, 11D04, 52C07, 05A16

Retrieve articles in all journals with MSC (2010): 11D45, 11D04, 52C07, 05A16


Additional Information

Sheng Chen
Affiliation: Department of Mathematics, Harbin Institute of Technology, Harbin, People’s Republic of China 150001
Email: schen@hit.edu.cn

Nan Li
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: nan@math.mit.edu

Steven V Sam
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: ssam@math.mit.edu

DOI: https://doi.org/10.1090/S0002-9947-2011-05494-2
Keywords: Ehrhart polynomials, Diophantine equations, lattice points, polytopes, quasi-polynomials
Received by editor(s): May 14, 2010
Received by editor(s) in revised form: September 6, 2010, October 8, 2010, and October 26, 2010
Published electronically: June 29, 2011
Additional Notes: The first author was sponsored by Project 11001064 supported by the National Natural Science Foundation of China, and Project HITC200701 supported by the Science Research Foundation in Harbin Institute of Technology.
The third author was supported by an NSF graduate fellowship and an NDSEG fellowship.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.