Polynomial-Time Evaluation of Aardal-Lenstra Denumerants via Constant Term Method

Aardal and Lenstra systematically studied hard knapsack problems of the form $a_1{x}_1+\cdots +a_n{x}_n=b$, where $a_i=p_{i}M+r_{i}N$, $(M,N)$ is a coprime pair of positive integers, and the integers $\mathrm{\mid }{p}_i\mathrm{\mid },\mathrm{\mid }{r}_i\mathrm{\mid }$ are small relative to $M$ and $N$. We investigate the corresponding challenging denumerant problem (i.e., counting the number of nonnegative integer solutions) and present a polynomial-time algorithm. This eliminates the computational bottlenecks caused by large values of $M$, $N$ and $b$. The proposed algorithm achieves a time complexity of $O(n^4{\mathrm{\Delta }}^2\log n\log \mathrm{\Delta })$, which depends solely on the parameters $n$ and $\mathrm{\Delta }={\max }_{i,j}\mathrm{\mid }{r}_i{p}_j-r_j{p}_i\mathrm{\mid }$. Moreover, we consider the problem of expressing a general vector $(a_1,\dots ,a_n)$ in the above form using the LLL algorithm.