Counting with rational generating functions

Abstract

We examine two different ways of encoding a counting function, as a rational generating function and explicitly as a function (defined piecewise using the greatest integer function). We prove that, if the degree and number of input variables of the (quasi-polynomial) function are fixed, there is a polynomial time algorithm which converts between the two representations. Examples of such counting functions include Ehrhart quasi-polynomials, vector partition functions, integer points in parametric polytopes, and projections of the integer points in parametric polytopes. For this last example, this algorithm provides the first known way to compute the explicit function in polynomial time. We rely heavily on results of Barvinok, and also of Verdoolaege, Seghir, Beyls, et al.

25 pages; revised version has significant changes to exposition, but same results

References in corpus (1)

• A primal Barvinok algorithm based on irrational decompositions

Cited by in corpus (13)

• Presburger arithmetic, rational generating functions, and quasi-polynomials
• Ehrhart polynomials of matroid polytopes and polymatroids
• Intermediate Sums on Polyhedra: Computation and Real Ehrhart Theory
• On lattice point counting in $\Delta$-modular polyhedra
• Complexity of short Presburger arithmetic
• Computing the number of numerical semigroups using generating functions
• Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
• Matroid Polytopes: Algorithms, Theory, and Applications
• On the number of integer points in translated and expanded polyhedra
• Short Presburger arithmetic is hard
• A finite calculus approach to Ehrhart polynomials
• An Invitation to Ehrhart Theory: Polyhedral Geometry and its Applications in Enumerative Combinatorics
• The unreasonable ubiquitousness of quasi-polynomials