Short rational generating functions for lattice point problems

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 ... a_d admit polynomial time algorithms. We also discuss a related problem of computing the Hilbert series of a ring generated by monomials.
26 pages

Keywords

Combinatorics, Commutative Algebra, Optimization and Control, 05A15, 11P21, 13P10, 68W30

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/65600

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0211146
 http://arxiv.org/abs/math/0211146

Collections

arXiv