On the efficient computation of Fourier coefficients of eta-quotients

技術要約：エータ商体のフーリエ係数の効率的な計算について

問題提起
本論文は、負の重みを持つエータ商体のフーリエ係数 $a(n)$ を決定するという計算上の課題に取り組んでいる。Hardy–Ramanujan–Rademacher (HRR) 展開は、これらの係数の収束級数表現（負の重みの場合はSussmanによって一般的に確立されている）を提供するが、その実用性は、中心項であるHRR係数 $A^\delta_k(n)$ の計算の困難さによって阻害されている。定義に従って直接計算する場合、互いに素な剰余類にわたって1のべき根を総和させる必要があり、これは計算コストが高い。古典的な分割関数 $p(n)$ については、Lehmerが、性質の多重性を利用し、ねじれクロネッカー和（twisted Kloosterman sums）を用いて表現することで、これらの係数を効率的に計算できることを示した。本論文は、Lehmerによる効率的な計算フレームワークを、任意の負の重みを持つエータ商体へと一般化することを目的としている。

手法
著者らは、HRR係数 $A^\delta_k(n)$ をねじれクロネッカー和を用いて表現するための理論的枠組みを構築している。その手法は、以下の3つの主要な段階を経て進行する：

1. HRR係数の特徴付け： 著者らは、$A^\delta_k(n)$ の定義に現れるデデキント和の構造を分析する。デデキンド和に関する既知の合同式や相互法則を利用することで、彼らは $A^\delta_k(n)$ をねじれクロネッカー和 $S_\chi(a-n, b; k)$ に関連付ける明示的な公式を導出する。これは、$A^\delta_k(n)$ の定義における指数項を、文字（character）成分と加法的成分に分解することによって達成される。
2. 多重性の分析： 論文では、HRR係数が、互いに素な $k_1, k_2$ に対して $A^\delta_{k_1 k_2}(n) = A^\delta_{k_1}(n_1) A^\delta_{k_2}(n_2)$ という形の多重性関係を満たすかどうかを調査している。著者らは、エータ商体のパラメータに関連する特定の合同系の解が存在するという条件の下で、このような分解が成立するための十分条件を確立している。
3. 誤差界の導出： HRR級数を正確な整数計算に使用できるようにするため、著者らは（級数の末尾である）切断誤差の明示的な上界を導出している。これには、修正ベッセル関数の増大度およびHRR係数の大きさの推定が含まれる。

主な貢献と結果

• ねじれクロネッカー和による一般化された表現 (定理 4.5)： 本論文は、任意の正の整数 $k$ に対して、HRR係数 $A^\delta_k(n)$ が $i^c \psi(1) S_{\chi\rho}(a-n, b; k)$ （ここで $S_{\chi\rho}$ はねじれクロネッカー和）として表現できることを証明している。分割関数に対するLehmerの結果が素数冪の法に限定されていたのに対し、この結果はすべての整数 $k$ に対して成立する。これにより、クロネッカー和の閉形式の公式を適用して $A^\delta_k(n)$ を効率的に計算することが可能となる。
• 係数の多重性 (定理 5.1)： 著者らは、特定の仮定（エータ商体の指数を含む合同系を満たす整数 $\ell$ の存在）の下で、係数が多重性関係を満たすことを証明している。これにより、合成数 $k$ に対する $A^\delta_k(n)$ の計算を、素数冪因子に対する計算へと還元でき、計算の複雑性を大幅に低減できる。論文では、これは分割関数やオーバーパーティション（overpartitions）については成立するものの、すべてのエータ商体に対して普遍的に成立するわけではないことを指摘しており、その関係が失敗する反例も提示している。
• 明示的な誤差界 (定理 6.3)： HRR級数を $N$ で切断した際に生じる誤差項 $R(n, N)$ に対する明示的な上界 $M(n, N)$ が導出されている。この上界は、エータ商体の重みと級数のパラメータに依存する。著者らは、この上界が $O(N^{-c_1})$ として漸近的に減少することを実証しており、部分和を最も近い整数に丸めることで $a(n)$ を正確に計算できることを保証している。
• アルゴリズムの実装： 著者らはこれらの結果を統合し、$k$ を素数冪へと因数分解し、可能な場合には多重性定理を適用し、素数冪成分に対しては（セクション3の）閉形式のクロネッカー和の公式を用いることで $A^\delta_k(n)$ を計算するアルゴリズム 7.1を構築している。

意義と主張

本論文は、分割関数やオーバーパーティションにのみ知られていた効率的な計算手法を、広範な負の重みを持つエータ商体へと拡張することを主張している。その意義は以下の通りである：

1. 効率性： $A^\delta_k(n)$ の計算をねじれクロネッカー和へと還元し、多重性を利用することで、著者らは1のべき根の直接的な総和を回避する方法を提供している。これを示す例として、10⁶における5色分割（5-colored partitions）の係数を計算する場合、定義を用いた場合には1時間15分以上かかるのに対し、提案するアルゴリズムを用いれば9秒未満で完了することを挙げている。
2. 汎用性： 結果は、特定のケースだけでなく、負の重みを持つ一般的なエータ商体に適用される。誤差界の導出（定理 6.3）は、このクラス全体で一様であり、当該関数の正確な計算を可能にしている。
3. 理論的拡張： 本研究はLehmerの知見を一般化し、HRR係数の根底にある構造が、素数冪に限らずすべての $k$ においてねじれクロネッカー和と根本的に結びついていることを示している。

著者らは、多重性の結果の範囲について謙虚な姿勢を保っており、定理5.1の条件が常に満たされるわけではないこと（例7.3により示される）を明記している。その場合、一般的なクロネッカー和の公式（定理 4.5）を直接使用する必要がある。提案されたアルゴリズムの計算量は $O(n^{1/2} \log^{4+o(1)} n)$ と予想され、これは分割関数に対する最適に近い複雑さと同等である。