Short rational generating functions for lattice point problems

Details Short rational generating functions for lattice point problems Short rational generating functions for lattice point problems

2002-11-08

arxiv.org/abs/math/0211146v1

Mathematics

Combinatorics

26 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Short rational generating functions for lattice point problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Short rational generating functions for lattice point problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Short rational generating functions for lattice point problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-470085