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 Free Access

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]**Alexander I. Barvinok,*A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed*, Math. Oper. Res.**19**(1994), no. 4, 769–779. MR**1304623**, https://doi.org/10.1287/moor.19.4.769**[B02]**A. Barvinok,*A Course in Convexity*, Graduate Studies in Mathematics, vol. 54, Amer. Math. Soc., Providence, RI, 2002.**[BP99]**Alexander Barvinok and James 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**1731815****[BS98]**Dave Bayer and Bernd Sturmfels,*Cellular resolutions of monomial modules*, J. Reine Angew. Math.**502**(1998), 123–140. MR**1647559**, https://doi.org/10.1515/crll.1998.083**[BL:99]**Wojciech Banaszczyk, Alexander E. Litvak, Alain Pajor, and Stanislaw J. Szarek,*The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces*, Math. Oper. Res.**24**(1999), no. 3, 728–750. MR**1854250**, https://doi.org/10.1287/moor.24.3.728**[C97]**J. W. S. Cassels,*An introduction to the geometry of numbers*, Classics in Mathematics, Springer-Verlag, Berlin, 1997. Corrected reprint of the 1971 edition. MR**1434478****[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]**David Eisenbud,*Commutative algebra*, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR**1322960****[EG72]**P. Erdős and R. L. Graham,*On a linear diophantine problem of Frobenius*, Acta Arith.**21**(1972), 399–408. MR**311565**, https://doi.org/10.4064/aa-21-1-399-408**[GLS93]**Martin Grötschel, László Lovász, and Alexander Schrijver,*Geometric algorithms and combinatorial optimization*, 2nd ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR**1261419****[H70]**Jürgen Herzog,*Generators and relations of abelian semigroups and semigroup rings*, Manuscripta Math.**3**(1970), 175–193. MR**269762**, https://doi.org/10.1007/BF01273309**[K92]**Ravi Kannan,*Lattice translates of a polytope and the Frobenius problem*, Combinatorica**12**(1992), no. 2, 161–177. MR**1179254**, https://doi.org/10.1007/BF01204720**[Kh95]**A. G. Khovanskiĭ,*Sums of finite sets, orbits of commutative semigroups and Hilbert functions*, Funktsional. Anal. i Prilozhen.**29**(1995), no. 2, 36–50, 95 (Russian, with Russian summary); English transl., Funct. Anal. Appl.**29**(1995), no. 2, 102–112. MR**1340302**, https://doi.org/10.1007/BF01080008**[KLS90]**Ravi Kannan, László Lovász, and Herbert E. Scarf,*The shapes of polyhedra*, Math. Oper. Res.**15**(1990), no. 2, 364–380. MR**1051577**, https://doi.org/10.1287/moor.15.2.364**[P94]**Christos H. Papadimitriou,*Computational complexity*, Addison-Wesley Publishing Company, Reading, MA, 1994. MR**1251285****[S97]**Herbert E. Scarf,*Test sets for integer programs*, Math. Programming**79**(1997), no. 1-3, Ser. B, 355–368. Lectures on mathematical programming (ismp97) (Lausanne, 1997). MR**1464774**, https://doi.org/10.1016/S0025-5610(97)00058-0**[Sc86]**Alexander Schrijver,*Theory of linear and integer programming*, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR**874114****[St96]**Bernd Sturmfels,*Gröbner bases and convex polytopes*, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996. MR**1363949****[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**900339****[T95]**Rekha R. Thomas,*A geometric Buchberger algorithm for integer programming*, Math. Oper. Res.**20**(1995), no. 4, 864–884. MR**1378110**, https://doi.org/10.1287/moor.20.4.864

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