On the efficient computation of Fourier coefficients of eta-quotients

技术摘要：关于 Eta-商傅里埃系数的高效计算

问题陈述
本文探讨了确定负权 Eta-商（eta-quotients）的傅里埃系数 $a(n)$ 的计算挑战。虽然 Hardy–Ramanujan–Rademacher (HRR) 展开式为这些系数提供了一个收敛级数表示（Sussman 已针对负权重建立了这一通用的表示法），但由于计算中心项（即 HRR 系数 $A^\delta_k(n)$）存在困难，该展开式的实际应用受到了限制。通过定义进行直接计算涉及对互质剩余类进行单位根求和，这是一个计算成本极高的过程。对于经典的划分函数 $p(n)$，Lehmer 证明了可以通过利用乘性性质并将其表示为扭曲 Kloosterman 和（twisted Kloosterman sums）来高效地计算这些系数。本文旨在将 Lehmer 的高效计算框架推广到任意负权 Eta-商。

方法论
作者开发了一个理论框架，将一般 Eta-商 $\eta^\delta$ 的 HRR 系数 $A^\delta_k(n)$ 表示为扭曲 Kloosterman 和。该方法论通过三个主要阶段进行：

1. HRR 系数的特征化： 作者分析了出现在 $A^\delta_k(n)$ 定义中的 Dedekind 和的结构。通过利用已知的 Dedekind 和的同余关系和互易关系，他们推导出了显式公式，将 $A^\delta_k(n)$ 与扭曲 Kloosterman 和 $S_\chi(a-n, b; k)$ 联系起来。这是通过将 $A^\delta_k(n)$ 定义中的指数项分解为模 $k$ 的特征分量和加法分量来实现的。
2. 乘性分析： 本文研究了 HRR 系数是否满足形式为 $A^\delta_{k_1 k_2}(n) = A^\delta_{k_1}(n_1) A^\delta_{k_2}(n_2)$（其中 $k_1, k_2$ 互质）的乘性关系。作者确立了使此类分解成立的充分条件，这些条件涉及与 Eta-商参数相关的特定同余方程组的可解性。
3. 误差界限推导： 为了确保 HRR 级数可以用于精确的整数计算，作者推导了截断误差（级数尾项）的显式上界。这涉及对修正 Bessel 函数增长情况以及 HRR 系数量级的估计。

主要贡献与结果

• 通过扭曲 Kloosterman 和实现的广义表达式（定理 4.5）： 本文证明了对于任何正整数 $k$，HRR 系数 $A^\delta_k(n)$ 可以表示为 $i^c \psi(1) S_{\chi\rho}(a-n, b; k)$，其中 $S_{\chi\rho}$ 是一个扭曲 Kloosterman 和。与 Lehmer 针对划分函数的限制在素幂模情形下的结果不同，此结果对每一个整数 $k$ 都成立。这使得应用 Kloosterman 和的闭式公式来高效计算 $A^\delta_k(n)$ 成为可能。
• 系数的乘性（定理 5.1）： 作者证明，在特定假设下（即存在一个整数 $\ell$ 满足涉及 Eta-商指数的同余方程组），这些系数满足乘性关系。这使得将 $A^\delta_k(n)$ 的计算简化为对素幂因子的计算，从而显著降低了计算复杂度。论文指出，虽然这适用于划分函数和过划分函数（overpartitions），但并不普遍适用于所有 Eta-商，并提供了一个关系失效的反例。
• 显式误差界限（定理 6.3）： 文中推导了由在 $N$ 处截断 HRR 级数产生的误差项 $R(n, N)$ 的显式界限 $M(n, N)$。该界限取决于 Eta-商的权重和级数的参数。作者展示了该界限在渐近意义下以 $O(N^{-c_1})$ 的速度下降，从而确保可以通过将部分和舍入到最近整数来精确计算 $a(n)$。
• 算法实现： 本文将这些结果综合为 算法 7.1，该算法通过将 $k$ 分解为素幂，在可能的情况下应用乘性定理，并对素幂分量使用（第 3 节中的）闭式 Kloosterman 和公式来计算 $A^\delta_k(n)$。

意义与主张
本文声称将此前仅已知于划分函数和过划分函数的有效计算方法，推广到了广泛的负权 Eta-商类。其意义在于：

1. 效率： 通过将 $A^\delta_k(n)$ 的计算简化为扭曲 Kloosterman 和并利用乘性，作者提供了一种避免直接对单位根求和的方法。他们通过一个例子说明了这一点：计算 $10^6$ 的 5 色划分（5-colored partitions）的系数时，使用其算法耗时不到 9 秒，而使用定义计算则需要超过 1 小时 15 分钟。
2. 普适性： 结果适用于一般的负权 Eta-商，而非仅限于特定情形。误差界限（定理 6.3）的推导在这一类中是统一的，从而实现了对任何此类函数的精确计算。
3. 理论扩展： 该工作推广了 Lehmer 的发现，表明 HRR 系数的底层结构从根本上与扭曲 Kloosterman 和相关联，且该关系对所有 $k$（不仅是素幂）均成立。

作者对乘性结果的适用范围保持谨慎，明确指出定理 5.1 的条件并不总是满足（如示例 7.3 所示），在这种情况下必须直接使用通用的 Kloosterman 和公式（定理 4.5）。所提算法的复杂度预计为 $O(n^{1/2} \log^{4+o(1)} n)$，与划分函数的最优复杂度相当。