Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Short rational generating functions for lattice point problems
HTML articles powered by AMS MathViewer

by Alexander Barvinok and Kevin Woods PDF
J. Amer. Math. Soc. 16 (2003), 957-979 Request permission

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
Similar Articles
Additional Information
  • Alexander Barvinok
  • Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109
  • MR Author ID: 237145
  • Email: barvinok@umich.edu
  • Kevin Woods
  • Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109
  • Email: kmwoods@umich.edu
  • 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.
  • © Copyright 2003 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 16 (2003), 957-979
  • MSC (2000): Primary 05A15, 11P21, 13P10, 68W30
  • DOI: https://doi.org/10.1090/S0894-0347-03-00428-4
  • MathSciNet review: 1992831