On the efficient computation of Fourier coefficients of eta-quotients

기술 요약: 에타-몫(Eta-Quotients)의 푸리에 계수 효율적 계산에 관하여

문제 정의
본 논문은 음수 가중치를 갖는 에타-몫의 푸리에 계수 $a(n)$을 결정하는 계산적 과제를 다룬다. 하디-라마누잔-라데마허(Hardy–Ramanujan–Rademacher, HRR) 전개는 이 계수들에 대한 수렴하는 급수 표현을 제공하지만(Sussman에 의해 음수 가중치에 대해 일반적으로 확립됨), 이 전개의 실용적 유용성은 중심 항인 HRR 계수 $A^\delta_k(n)$을 계산하는 어려움에 의해 저해된다. 정의를 통한 직접적인 계산은 서로소인 잔여(residues)에 대한 단위근(roots of unity)의 합을 포함하며, 이는 계산 비용이 매우 높다. 고전적인 분할 함수 $p(n)$의 경우, 레머(Lehmer)는 이 계수들이 곱셈성을 활용하고 뒤틀린 클로이스터만 합(twisted Kloosterman sums)을 통해 표현될 수 있음을 입증하여 효율적으로 계산할 수 있음을 보여주었다. 본 논문은 레머의 효율적인 계산 프레임워크를 임의의 음수 가중치 에타-몫으로 일반화하는 것을 목표로 한다.

방법론
저자들은 임의의 에타-몫 $\eta^\delta$에 대한 HRR 계수 $A^\delta_k(n)$을 뒤틀린 클로이스터만 합으로 표현하기 위한 이론적 프레임워크를 개발한다. 방법론은 다음과 같은 세 가지 주요 단계로 진행된다:

1. HRR 계수의 특징 규명: 저자들은 $A^\delta_k(n)$의 정의에 등장하는 데데킨트 합(Dedekind sums)의 구조를 분석한다. 데데킨트 합에 관한 알려진 합동식과 상호 관계(reciprocity relations)를 활용함으로써, 저자들은 $A^\delta_k(n)$을 뒤틀린 클로이스터만 합 $S_\chi(a-n, b; k)$와 연결하는 명시적인 공식을 유도한다. 이는 $A^\delta_k(n)$의 정의에 포함된 지수 항들을 모듈로 $k$에 대한 캐릭터(character)와 가법 성분(additive components)으로 분해함으로써 달성된다.
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 급수를 정수 계산에 사용할 수 있도록 하기 위해, 저자들은 절단 오차(급수의 꼬리 부분)에 대한 명시적인 상한을 도출한다. 이는 수정된 베셀 함수(modified Bessel functions)의 성장과 HRR 계수의 크기를 추정하는 과정을 포함한다.

주요 기여 및 결과

• 뒤틀린 클로이스터만 합을 통한 일반화된 표현 (정리 4.5): 본 논문은 임의의 양의 정수 $k$에 대하여, HRR 계수 $A^\delta_k(n)$이 $i^c \psi(1) S_{\chi\rho}(a-n, b; k)$로 표현될 수 있음을 증명한다. 여기서 $S_{\chi\rho}$는 뒤틀린 클로이스터만 합이다. 분할 함수에 국한되었던 레머의 결과와 달리, 이 결과는 모든 정수 $k$에 대해 성립한다. 이를 통해 $A^\delta_k(n)$을 효율적으로 계산하기 위해 클로이스터만 합의 폐쇄형 공식(closed-form formulas)을 적용할 수 있다.
• 계수의 곱셈성 (정리 5.1): 저자들은 에타-몫의 지수들과 관련된 합동식 체계를 만족하는 정수 $\ell$의 존재성이라는 특정 가설 하에서, 계수들이 곱셈성 관계를 만족함을 증명한다. 이는 $A^\delta_k(n)$의 계산을 합성수 $k$에 대한 계산에서 소수의 거듭제곱 인자들에 대한 계산으로 축소시켜 계산 복잡도를 크게 낮춘다. 저자들은 이 관계가 분할(partitions)과 오버분할(overpartitions)에는 적용되지만, 모든 에타-몫에 대해 보편적으로 성립하지는 않는다는 점을 반례를 통해 명시한다.
• 명시적 오차 한한계 (정리 6.3): $N$에서 HRR 급수를 절단했을 때 발생하는 오차 항 $R(n, N)$에 대한 명시적인 상한 $M(n, N)$이 도출된다. 이 상한은 에타-몫의 가중치와 급수의 파라미터에 의존한다. 저자들은 이 상한이 $O(N^{-c_1})$으로 점근적으로 감소함을 보여줌으로써, 부분합을 가장 가까운 정수로 반올림하여 $a(n)$을 정확하게 계산할 수 있음을 입증한다.
• 알고리즘 구현: 저자들은 이러한 결과들을 종합하여 알고리즘 7.1을 구축한다. 이 알고리즘은 $k$를 소수의 거듭제곱으로 분해하고, 가능한 경우 곱셈성 정리를 적용하며, 소수의 거듭제곱 성분에 대해서는 (섹션 3의) 폐쇄형 클로이스터만 합 공식을 사용하여 $A^\delta_k(n)$을 계산한다.

의의 및 주장
본 논문은 분할 함수와 오버분할에만 알려져 있던 효율적 계산 방법을 광범위한 음수 가중치 에타-몫 클래스로 확장한다고 주장한다. 그 의의는 다음과 같다:

1. 효율성: $A^\delta_k(n)$을 뒤틀린 클로이스터만 합으로 환원하고 곱셈성을 활용함으로써, 저자들은 단위근의 직접적인 합산을 피하는 방법을 제공한다. 저자들은 5-색 분할(5-colored partitions)의 $10^6$ 계수를 계산할 때, 제안된 알고리즘은 9초 미만이 소요된 반면, 정의를 사용했을 때는 1시간 15분 이상이 걸렸음을 예시를 통해 보여준다.
2. 일반성: 결과들은 특정 사례에 국한되지 않고 음수 가중치를 갖는 일반적인 에타-몫에 적용된다. 오차 한계(정리 6.3)의 도출은 이 클래스 전체에 대해 균등하게 이루어지므로, 해당 함수에 대한 정확한 계산을 가능하게 한다.
3. 이론적 확장: 본 연구는 레머의 발견을 일반화하여, HRR 계수의 근본적인 구조가 소수의 거듭제곱뿐만 아니라 모든 $k$에 대해 뒤틀린 클로이스터만 합과 밀접하게 연관되어 있음을 보여준다.

저자들은 곱셈성 결과의 범위에 대해 겸허한 태도를 유지하며, 정리 5.1의 조건이 항상 충족되는 것은 아니라는 점(예제 7.3 참조)을 명시하였다. 이 경우 일반적인 클로이스터만 합 공식(정리 4.5)을 직접 사용해야 한다. 제안된 알고리즘의 복잡도는 $O(n^{1/2} \log^{4+o(1)} n)$으로 예상되며, 이는 분할 함수의 최적 복잡도와 유사하다.