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.
For a finite sequence of positive integers $\boldsymbol{a}=(a_1,\dots,a_n)$, the restricted partition function $q_{\boldsymbol{a}}(k)$ denote the number of nonnegative integer solutions to the equation $a_1x_1+a_2x_2+\cdots +a_nx_n=k$. It is proved to be a quasi-polynomial of degree $n-1$. Write $q_{\boldsymbol{a}}(k)=\sum_{j=0}^{n-1}c_j(k)k^j$ with periodic coefficient functions $c_j$, and set $b_m=\#\{i:m\mid a_i\}$. In 2008, Beck, Sam, and Woods conjectured that the minimum period of $c_j(k)$ is $\mathrm{lcm}\{m:b_m>j\}$. In this paper, we derive an exact root-of-unity formula for every coefficient function $c_j(k)$. The formula proves the conjectured divisibility upper bound, but it also reveals a lower bound for the period of $c_j(k)$. Both divisibility bounds are sharp. This leads us to construct a family of counterexamples to this conjecture.
Feihu Liu, Jinlong Tang, Guoce Xin et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
