Sylvester's denumerant $d(t; \boldsymbol{A})$ counts the number of nonnegative integer solutions to $\sum_{i=1}^{N} a_i x_i = t$, where $\boldsymbol{A} = (a_1, \dots, a_N)$ is a sequence of positive integers with $\gcd(\boldsymbol{A}) = 1$. In 2025, Xin and Zhang gave a polynomial time algorithm in $N$ for computing $d(t; \boldsymbol{A})$ when the entries of $\boldsymbol{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 $\boldsymbol{A}$ are allowed to be unbounded.
Let $\mathrm{IMS}_n(m)$ count the $n\times n$ nonnegative integer matrices whose row sums, column sums, main-diagonal sum, and antidiagonal sum are all $m$. We determine the Ehrhart series $F_n(q)=\sum_{m\geq0}\mathrm{IMS}_n(m)q^m$ as reduced rational functions for $n=7$ and $n=8$. Their numerator--denominator degrees are respectively $(366,373)$ and $(540,548)$. Both numerators have positive integer coefficients, are palindromic and strictly unimodal. The proofs share one finite architecture: a signed SimpCone decomposition is evaluated by quotient characters over finite fields, a certified common denominator and Ehrhart reciprocity reduce the rational identity to finitely many coefficients, an explicit counting bound lifts modular congruences to integer equalities, and exact gcd computations prove reducedness. For order eight, a face-index pole certificate gives a degree-$598$ common denominator without enumerating the full face lattice, leaving $296$ independent coefficients in degrees $0$ through $295$. Once the candidate rational function is known, the first six production primes certify this finite prefix by the same bounded-coefficient argument used for order seven.
By using constant term manipulations, we present the first polynomial-time algorithm for lattice-point counting in fixed dimension that does not rely on Barvinok's unimodular decomposition. The algorithm instead operates directly on a rational generating function in the form of a nested root average, as produced by the \texttt{SimpCone[S]} framework. By means of a residue-lattice argument based on Minkowski's theorem, we construct a short multiplier that induces an exact non-coprime split of the outermost average. The resulting child terms are encoded as joint root averages, and Smith normal form is used to restore the recursive structure. Two structural invariants---the generation condition and full-column independence---ensure that the recursion is well defined and that all required pole exchanges are valid. For a fixed-dimensional simplicial cone, the algorithm achieves recursion depth \(O_d(1+\log\log(2+\ind(\mathcal K^*)))\) and produces a signed sum of at most \((1+\log \ind(\mathcal K^*))^{O_d(1)}\) unimodular cone generating functions. The framework uniformly handles numerators that are Laurent polynomials, not merely monomials, thereby giving a polynomial-time algorithm for MacMahon's partition analysis when the dimension is fixed.
Aardal and Lenstra systematically studied hard knapsack problems of the form $a_1x_1+\cdots+a_nx_n=b$, where $a_i=p_iM+r_iN$, $(M,N)$ is a coprime pair of positive integers, and the integers $|p_i|, |r_i|$ 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\Delta^2\log n\log\Delta)$, which depends solely on the parameters $n$ and $\Delta=\max_{i,j}|r_i p_j - r_j p_i|$. Moreover, we consider the problem of expressing a general vector $(a_1,\dots,a_n)$ in the above form using the LLL algorithm.
Jinlong Tang, Guoce Xin, Zihao Zhang· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
