A Fast Algorithm for Denumerants with Three Variables

1. Problem Statement

The paper addresses the computation of the denumerant function, denoted as $d(n; a, b, c)$. This function counts the number of non-negative integer solutions $(x_1, x_2, x_3)$ to the linear Diophantine equation:
$$ax_1 + bx_2 + cx_3 = n$$
where $a, b, c$ are distinct positive integers with $a < b < c$ and $\gcd(a, b, c) = 1$.

While explicit formulas exist for the case $k=2$ (Sylvester's formula), the problem becomes significantly harder for $k \geq 3$. Previous algorithms for $k=3$ had time complexities ranging from $O(a_3 \log a_3)$ (Popoviciu, 1953) to $O(a_2 + \log a_3)$ (Aguiló-Gost and Llena, 2018) and $O(\log a_3)$ (Binner, 2020). The authors aim to improve this by developing an algorithm with a time complexity of $O(\log b)$ (where $b$ is the middle variable), which is a significant improvement when $b$ is small relative to $c$.

2. Methodology

The authors combine two primary mathematical tools: the Constant Term (CT) Method and a Key Transformation Technique.

A. The Constant Term Method

The denumerant is expressed as the constant term of a Laurent series:
$$d(n; a, b, c) = \text{CT}_\lambda \left( \frac{\lambda^{-n}}{(1-\lambda^a)(1-\lambda^b)(1-\lambda^c)} \right)$$
To handle the variables, the authors introduce slack variables $z_1, z_2, z_3$ and take the limit as $z_i \to 1$. The core of the method involves decomposing the rational function using partial fractions. According to Proposition 2.1, the constant term can be extracted by summing the values of specific polynomial components $A_i(0)$ derived from the decomposition.

B. Key Transformation (Theorem 2.3)

A crucial tool is the transformation theorem:
$$\text{CT}_\lambda \left( \frac{1}{1-z\lambda^a} F(\lambda) \right) = \text{CT}_\lambda \left( \frac{1}{1-z^{1/u}\lambda^a} F(\lambda^u) \right)$$
where $\gcd(u, a) = 1$. This allows the authors to change the "multiplier" of the variable, effectively reducing the problem size in a manner analogous to the Euclidean algorithm.

C. Reduction Strategy

The algorithm proceeds through several reduction steps:

1. GCD Reduction: The problem is reduced to the case where $\gcd(a, b) = 1$ using Lemma 3.1, which handles common factors via modular arithmetic.
2. Two-Term Decomposition: The original constant term is split into two parts, $T(a)$ and $T(b)$, based on the contribution of the term $(1-\lambda^c)$.
3. Variable Elimination:
   • For $T(a)$, the variable $b$ is reduced to $1$ using the Key Transformation (since $\gcd(a, v)=1$ where $au+bv=1$).
   • For $T(b)$, the variable $a$ is reduced to $1$.
4. Euclidean-Style Recursion (Lemma 3.2): Once a variable is reduced to 1, the authors apply a recursive operation similar to the Euclidean algorithm. This step halves the index of the remaining variable in each iteration.
   • Specifically, a constant term of type $(1^\circ; a, 1, c)$ is transformed into a sum of a rational function and a new constant term with index $a' \leq a/2$.
   • This recursion continues until the index becomes 0 or 1, at which point the term is either 0 or a simple rational function.

3. Key Contributions

• Algorithm Design: The paper presents Algorithm 1, which computes $d(n; a, b, c)$ by iteratively applying the Key Transformation and the Euclidean-style recursion.
• Complexity Improvement: The authors prove that the algorithm runs in $O(\log b)$ time. This is achieved because the recursion depth is logarithmic with respect to the variable being reduced (specifically $b$ in the dominant term), and each step involves a constant number of ring operations.
• Slack Variable Dispelling: The paper details a method to eliminate the introduced slack variables ($z_i$) by substituting them with a vector $\mu$ and taking a limit, ultimately reducing the problem to evaluating a specific constant term formula (Equation 16) involving dot products.
• Theoretical Insight: The authors connect their recursive strategy to the concept of "simplicial cones" in computational geometry (Barvinok's algorithm), suggesting that their specific strategy $h$ (always choosing 1 as the multiplier) bounds the number of terms by $O(\log a)$ for the three-variable case.

4. Results

• Correctness: Theorem 4.1 formally proves that Algorithm 1 correctly computes the denumerant.
• Efficiency: The complexity analysis confirms the $O(\log b)$ bound. The steps involve:
  • Extended GCD computation: $O(\log a)$.
  • Recursive reduction: $O(\log a)$ for the first term and $O(\log b)$ for the second.
  • Final summation: $O(\log a + \log b)$ operations.
• Example: The paper provides a concrete example calculating $d(25; 3, 7, 11)$. The algorithm successfully reduces the complex constant term expression through several transformations and limit evaluations to yield the integer result 3.

5. Significance

• Speed: The proposed algorithm is significantly faster than previous methods for cases where the middle variable $b$ is small, offering a logarithmic time complexity relative to $b$.
• Methodological Synthesis: It successfully integrates the constant term method from algebraic combinatorics with transformation techniques from number theory to solve a classic partition problem.
• Open Problems: The paper concludes by posing an open problem: whether an algorithm with $O(\log a)$ complexity exists (where $a$ is the smallest variable), suggesting that the current $O(\log b)$ bound might not be the theoretical lower limit for all configurations.

In summary, Liu and Xin provide a highly efficient, theoretically grounded algorithm for computing 3-variable denumerants, leveraging recursive reductions and constant term extraction to achieve logarithmic time complexity.