On the efficient computation of Fourier coefficients of eta-quotients

Technical Summary: On the Efficient Computation of Fourier Coefficients of Eta-Quotients

Problem Statement
The paper addresses the computational challenge of determining the Fourier coefficients $a(n)$ of negative weight eta-quotients. While the Hardy–Ramanujan–Rademacher (HRR) expansion provides a convergent series representation for these coefficients (established generally by Sussman for negative weights), the practical utility of this expansion is hindered by the difficulty of computing the central terms, known as HRR coefficients $A^\delta_k(n)$. Direct computation via the definition involves summing roots of unity over coprime residues, a process that is computationally expensive. For the classical partition function $p(n)$, Lehmer demonstrated that these coefficients could be computed efficiently by exploiting multiplicativity and expressing them via twisted Kloosterman sums. This paper seeks to generalize Lehmer's efficient computational framework to arbitrary negative weight eta-quotients.

Methodology
The authors develop a theoretical framework to express the HRR coefficients $A^\delta_k(n)$ for general eta-quotients $\eta^\delta$ in terms of twisted Kloosterman sums. The methodology proceeds through three main stages:

1. Characterization of HRR Coefficients: The authors analyze the structure of the Dedekind sums appearing in the definition of $A^\delta_k(n)$. By utilizing known congruences and reciprocity relations for Dedekind sums, they derive explicit formulas that relate $A^\delta_k(n)$ to twisted Kloosterman sums $S_\chi(a-n, b; k)$. This is achieved by decomposing the exponential terms in the definition of $A^\delta_k(n)$ into characters and additive components modulo $k$.
2. Multiplicativity Analysis: The paper investigates whether the HRR coefficients satisfy multiplicativity relations of the form $A^\delta_{k_1 k_2}(n) = A^\delta_{k_1}(n_1) A^\delta_{k_2}(n_2)$ for coprime $k_1, k_2$. The authors establish sufficient conditions under which such a decomposition holds, involving the solvability of a specific system of congruences related to the eta-quotient's parameters.
3. Error Bound Derivation: To ensure the HRR series can be used for exact integer computation, the authors derive an explicit upper bound for the truncation error (the tail of the series). This involves estimating the growth of the modified Bessel functions and the magnitude of the HRR coefficients.

Key Contributions and Results

• Generalized Expression via Twisted Kloosterman Sums (Theorem 4.5): The paper proves that for any positive integer $k$, the HRR coefficient $A^\delta_k(n)$ can be expressed as $i^c \psi(1) S_{\chi\rho}(a-n, b; k)$, where $S_{\chi\rho}$ is a twisted Kloosterman sum. Unlike Lehmer's result for the partition function, which was restricted to prime power moduli, this result holds for every integer $k$. This allows for the application of closed-form formulas for Kloosterman sums to compute $A^\delta_k(n)$ efficiently.
• Multiplicativity of Coefficients (Theorem 5.1): The authors prove that under specific hypotheses (existence of an integer $\ell$ satisfying a system of congruences involving the eta-quotient's exponents), the coefficients satisfy a multiplicativity relation. This reduces the computation of $A^\delta_k(n)$ for composite $k$ to computations for prime power factors, significantly lowering the computational complexity. The paper notes that while this holds for partitions and overpartitions, it does not hold universally for all eta-quotients, providing a counterexample where the relation fails.
• Explicit Error Bounds (Theorem 6.3): An explicit bound $M(n, N)$ is derived for the error term $R(n, N)$ resulting from truncating the HRR series at $N$. This bound depends on the weight of the eta-quotient and the parameters of the series. The authors demonstrate that this bound decreases asymptotically as $O(N^{-c_1})$, ensuring that the series can be truncated to compute $a(n)$ exactly by rounding the partial sum to the nearest integer.
• Algorithmic Implementation: The paper synthesizes these results into Algorithm 7.1, which computes $A^\delta_k(n)$ by factoring $k$ into prime powers, applying the multiplicativity theorem where possible, and using the closed-form Kloosterman sum formulas (from Section 3) for the prime power components.

Significance and Claims
The paper claims to extend the efficient computation methods previously known only for the partition function and overpartitions to a broad class of negative weight eta-quotients. The significance lies in:

1. Efficiency: By reducing the computation of $A^\delta_k(n)$ to twisted Kloosterman sums and utilizing multiplicativity, the authors provide a method that avoids the direct summation of roots of unity. They illustrate this with an example where computing coefficients for 5-colored partitions of $10^6$ takes less than 9 seconds using their algorithm, compared to over 1 hour and 15 minutes using the definition.
2. Generality: The results apply to general eta-quotients of negative weight, not just specific cases. The derivation of the error bound (Theorem 6.3) is uniform across this class, enabling exact computation for any such function.
3. Theoretical Extension: The work generalizes Lehmer's findings, showing that the underlying structure of HRR coefficients is fundamentally tied to twisted Kloosterman sums for all $k$, not just prime powers.

The authors remain modest regarding the scope of the multiplicativity result, explicitly noting that the conditions for Theorem 5.1 are not always met (as shown in Example 7.3), in which case the general Kloosterman sum formula (Theorem 4.5) must be used directly. The complexity of the proposed algorithm is expected to be $O(n^{1/2} \log^{4+o(1)} n)$, comparable to the optimal complexity for the partition function.