Counting with rational generating functions (Q2474247)

The authors study two ways of encoding a counting function \(c : {\mathbb Z}^d \to {\mathbb Q}\). The first is in the form of a rational generating function \[ \sum_{ m \in {\mathbb Z}^d } c(m) \, x^m = \sum_{ i \in I } \alpha_i {{ x^{ p_i } } \over { \left( 1 - x^{ a_{ i1 } } \right) \cdots \left( 1 - x^{ a_{ is } } \right) }} , \] where \(I\) is finite, \(\alpha_i \in {\mathbb Q}\) and \(p_i, a_{ ij } \in {\mathbb Z^d}\). Here we use the multinomial notation \(a^b = a_1^{ b_1 } \cdots a_k^{ b_k }\) for vectors \(a = (a_1,\dots,a_k)\) and \(b = (b_1,\dots,b_k)\). The second form of encoding \(c\) is in form of a step-polynomial \[ c(m) = \sum_{ j=1 }^n \alpha_j \prod_{ k=1 }^{ d_j } \left\lfloor \langle a_{ jk } , m \rangle + b_{ jk } \right\rfloor , \] where \(\alpha_j, b_{ jk } \in {\mathbb Q}\) and \(a_{ ij } \in {\mathbb Q}^d\). Examples of such counting functions include Ehrhart quasipolynomials (integer-point enumeration in rational polyhedra) and their variants, such as vector partition functions. The main result of the paper is that, if the degree and number of input variables of the (quasi-polynomial) function \(c\) are fixed, there is a polynomial-time algorithm that converts between the two representations. The main tool in the proof of this result is Barvinok's algorithm [\textit{A. I. Barvinok}, Discrete Comput. Geom. 12, No. 1, 35--48 (1994; Zbl 0804.52009)].