A polynomial time algorithm for Sylvester waves when entries are bounded

The Sylvester’s denumerant $d(t;\mathit{a})$ is a quantity that counts the number of nonnegative integer solutions to the equation ${\sum }_{i=1}^N{a}_i{x}_i=t$, where $\mathit{a}=(a_1,\dots ,a_N)$ is a sequence of distinct positive integers with $\gcd (\mathit{a})=1$. We present a polynomial time algorithm in $N$ for computing $d(t;\mathit{a})$ when $\mathit{a}$ is bounded and $t$ is a parameter. The proposed algorithm is rooted in the use of cyclotomic polynomials and builds upon recent results by Xin-Zhang-Zhang on the efficient computation of generalized Todd polynomials. The algorithm has been implemented in $\mathtt{\text{Maple}}$ under the name $\mathtt{\text{Cyc-Denum}}$ and demonstrates superior performance when $a_i\le 500$ compared to Sills-Zeilberger’s $\mathtt{\text{Maple}}$ package $\mathtt{\text{PARTITIONS}}$.