Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Short rational generating functions for lattice point problems


Authors: Alexander Barvinok and Kevin Woods
Journal: J. Amer. Math. Soc. 16 (2003), 957-979
MSC (2000): Primary 05A15, 11P21, 13P10, 68W30
Published electronically: April 25, 2003
MathSciNet review: 1992831
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that for any fixed $d$ the generating function of the projection of the set of integer points in a rational $d$-dimensional polytope can be computed in polynomial time. As a corollary, we deduce that various interesting sets of lattice points, notably integer semigroups and (minimal) Hilbert bases of rational cones, have short rational generating functions provided certain parameters (the dimension and the number of generators) are fixed. It follows then that many computational problems for such sets (for example, finding the number of positive integers not representable as a non-negative integer combination of given coprime positive integers $a_{1}, \ldots , a_{d}$) admit polynomial time algorithms. We also discuss a related problem of computing the Hilbert series of a ring generated by monomials.


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


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 05A15, 11P21, 13P10, 68W30

Retrieve articles in all journals with MSC (2000): 05A15, 11P21, 13P10, 68W30


Additional Information

Alexander Barvinok
Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109
Email: barvinok@umich.edu

Kevin Woods
Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109
Email: kmwoods@umich.edu

DOI: http://dx.doi.org/10.1090/S0894-0347-03-00428-4
PII: S 0894-0347(03)00428-4
Keywords: Frobenius problem, semigroup, Hilbert series, Hilbert basis, generating functions, computational complexity
Received by editor(s): November 20, 2002
Published electronically: April 25, 2003
Additional Notes: This research was partially supported by NSF Grant DMS 9734138. The second author was partially supported by an NSF VIGRE Fellowship and an NSF Graduate Research Fellowship.
Article copyright: © Copyright 2003 American Mathematical Society