Short rational generating functions for lattice point problems
By Alexander I. Barvinok, Kevin M. Woods. 2002
194 citations recorded by the source corpus.
Abstract. We prove that for any fixed d the generating function of the projectionof the set of integer points in a rational d-dimensional polytope can be computed inpolynomial time. As a corollary, we deduce that various interesting sets of latticepoints, notably integer semigroups and (minimal) Hilbert bases of rational cones,have short rational generating functions provided certain parameters (the dimensionand the number of generators) are fixed. It follows then that many computationalproblems for such sets (for example, finding the number of positive integers notrepresentable as a non-negative integer combination of given coprime positive integersa 1 ,... ,a d ) admit polynomial time algorithms. We also discuss a related problem ofcomputing the Hilbert series of a ring generated by monomials. 1. Introduction and Main ResultsOur main motivation is the following question which goes back to Frobenius andSylvester.(1.1) The Frobenius Problem. Let a 1 ,... ,a d be positive coprime integers andletS =nµ
Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/cad0bbe46eb07b6ef6b510829017029184ae3ee7
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Algebra and Number Theory
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- Effective lattice point counting in rational convex polytopes (2004, methodology): “This can be done by the Laurent series calculations described before (Barvinok and Woods, 2003, Theorem 2.6).”
- The many aspects of counting lattice points in polytopes (2005, background): “Similarly the maximum of a linear functional over the lattice points equals the highest degree of the univariate polynomial one gets after doing a monomial substitution xi → t ci (See [10]).”