Short rational generating functions for lattice point problems |
| |
Authors: | Alexander Barvinok Kevin Woods |
| |
Affiliation: | Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109 ; Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109 |
| |
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. |
| |
Keywords: | Frobenius problem semigroup Hilbert series Hilbert basis generating functions computational complexity |
|
| 点击此处可从《Journal of the American Mathematical Society》浏览原始摘要信息 |
|
点击此处可从《Journal of the American Mathematical Society》下载全文 |