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

DOI:
https://doi.org/10.1090/S0894-0347-03-00428-4

Published electronically:
April 25, 2003

MathSciNet review:
1992831

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that for any fixed the generating function of the projection of the set of integer points in a rational -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 ) admit polynomial time algorithms. We also discuss a related problem of computing the Hilbert series of a ring generated by monomials.

**[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, http://www.math.ucdavis.edu/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**and**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**

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:
https://doi.org/10.1090/S0894-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