A polynomial time algorithm for almost bounded denumerant

Abstract

Sylvester's denumerant $d(t;\mathbf{A})$ counts the number of nonnegative integer solutions to ${\sum }_{i=1}^N{a}_i{x}_i=t$, where $\mathbf{A}=(a_1,\dots ,a_N)$ is a sequence of positive integers with $\gcd (\mathbf{A})=1$. In 2025, Xin and Zhang gave a polynomial time algorithm in $N$ for computing $d(t;\mathbf{A})$ when the entries of $\mathbf{A}$ are bounded by a constant. In this paper, we extend this algorithm by incorporating Barvinok's algorithm, enabling it to handle the case where a fixed number of entries of $\mathbf{A}$ are allowed to be unbounded.

12 pages