## 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

- 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**, DOI 10.1287/moor.19.4.769
[B02]B02 A. Barvinok, - 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** - Dave Bayer and Bernd Sturmfels,
*Cellular resolutions of monomial modules*, J. Reine Angew. Math.**502**(1998), 123–140. MR**1647559**, DOI 10.1515/crll.1998.083 - 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**, DOI 10.1287/moor.24.3.728 - 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]D96 G. Denham, - David Eisenbud,
*Commutative algebra*, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR**1322960**, DOI 10.1007/978-1-4612-5350-1 - P. Erdős and R. L. Graham,
*On a linear diophantine problem of Frobenius*, Acta Arith.**21**(1972), 399–408. MR**311565**, DOI 10.4064/aa-21-1-399-408 - 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**, DOI 10.1007/978-3-642-78240-4 - Jürgen Herzog,
*Generators and relations of abelian semigroups and semigroup rings*, Manuscripta Math.**3**(1970), 175–193. MR**269762**, DOI 10.1007/BF01273309 - Ravi Kannan,
*Lattice translates of a polytope and the Frobenius problem*, Combinatorica**12**(1992), no. 2, 161–177. MR**1179254**, DOI 10.1007/BF01204720 - 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**, DOI 10.1007/BF01080008 - 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**, DOI 10.1287/moor.15.2.364 - Christos H. Papadimitriou,
*Computational complexity*, Addison-Wesley Publishing Company, Reading, MA, 1994. MR**1251285** - 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**, DOI 10.1016/S0025-5610(97)00058-0 - 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** - Bernd Sturmfels,
*Gröbner bases and convex polytopes*, University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996. MR**1363949**, DOI 10.1090/ulect/008 - 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** - Rekha R. Thomas,
*A geometric Buchberger algorithm for integer programming*, Math. Oper. Res.**20**(1995), no. 4, 864–884. MR**1378110**, DOI 10.1287/moor.20.4.864

*A Course in Convexity*, Graduate Studies in Mathematics, vol. 54, Amer. Math. Soc., Providence, RI, 2002.

*The Hilbert series of a certain module*, manuscript, 1996. [DH:03]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/$\sim$latte/ (2003).

## 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