Remote Access Journal of the American Mathematical Society
Green Open Access

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

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?)

  • [B94] A. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), 769-779. MR 96c:52026
  • [B02] A. Barvinok, A Course in Convexity, Graduate Studies in Mathematics, vol. 54, Amer. Math. Soc., Providence, RI, 2002.
  • [BP99] A. Barvinok and J.E. Pommersheim, An algorithmic theory of lattice points in polyhedra, New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996-97), Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 91-147. MR 2000k:52014
  • [BS98] D. Bayer and B. Sturmfels, Cellular resolutions of monomial modules, J. Reine Angew. Math. 502 (1998), 123-140. MR 99g:13018
  • [BL:99] W. Banaszczyk, A.E. Litvak, A. Pajor and S.J. Szarek, The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces, Math. Oper. Res. 24 (1999), 728-750. MR 2002k:52019
  • [C97] J.W.S Cassels, An Introduction to the Geometry of Numbers. Corrected reprint of the 1971 edition, Classics in Mathematics, Springer-Verlag, Berlin, 1997. MR 97i:11074
  • [D96] G. Denham, The Hilbert series of a certain module, manuscript, 1996.
  • [DH:03] J.A. De Loera, R. Hemmecke, J. Tauzer and R. Yoshida, Effective lattice point counting in rational convex polytopes, preprint,$\sim $latte/ (2003).
  • [E95] D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. MR 97a:13001
  • [EG72] P. Erdös and R.L. Graham, On a linear diophantine problem of Frobenius, Acta Arith. 21 (1972), 399-408. MR 47:127
  • [GLS93] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Second edition, Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR 95e:90001
  • [H70] J. Herzog, Generators and relations of abelian semigroups and semigroup rings, Manuscripta Math. 3 (1970), 175-193. MR 42:4657
  • [K92] R. Kannan, Lattice translates of a polytope and the Frobenius problem, Combinatorica 12 (1992), 161-177. MR 93k:52015
  • [Kh95] A.G. Khovanskii, Sums of finite sets, orbits of commutative semigroups and Hilbert functions, Funktsional. Anal. i Prilozhen. 29 (1995), 36-50; English transl. Funct. Anal. Appl. 29 (1995), 102-112. MR 96e:20091
  • [KLS90] R. Kannan, L. Lovász, and H. Scarf, The shapes of polyhedra, Math. Oper. Res. 15 (1990), 364-380. MR 91d:52004
  • [P94] C.H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994. MR 95f:68082
  • [S97] H. Scarf, Test sets for integer programs, Math. Programming, Ser. B 79 (1997), 355-368. MR 98e:90098
  • [Sc86] A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience, Chichester, 1986. MR 88m:90090
  • [St96] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8, Amer. Math. Soc., Providence, RI, 1996. MR 97b:13034
  • [SW86] L.A. Székely and N.C. Wormald, Generating functions for the Frobenius problem with $2$ and $3$ generators, Math. Chronicle 15 (1986), 49-57. MR 88i:05013
  • [T95] R. Thomas, A geometric Buchberger algorithm for integer programming, Math. Oper. Res. 20 (1995), 864-884. MR 97a:90027

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

Kevin Woods
Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109

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