On the efficient computation of Fourier coefficients of eta-quotients

Resumen Técnico: Sobre la Computación Eficiente de los Coeficientes de Fourier de Cocientes de Eta

Planteamiento del Problema
El artículo aborda el desafío computacional de determinar los coeficientes de Fourier $a(n)$ de los cocientes de eta de peso negativo. Si bien la expansión de Hardy–Ramanujan–Rademacher (HRR) proporciona una representación en serie convergente para estos coeficientes (establecida generalmente por Sussman para pesos negativos), la utilidad práctica de esta expansión se ve dificultada por la dificultad de computar los términos centrales, conocidos como coeficientes HRR $A^\delta_k(n)$. La computación directa mediante la definición implica sumar raíces de la unidad sobre residuos coprimos, un proceso que es computacionalmente costoso. Para la función de partición clásica $p(n)$, Lehmer demostró que estos coeficientes podían computarse eficientemente explotando la multiplicatividad y expresándolos mediante sumas de Kloosterman retorcidas (twisted Kloosterman sums). Este artículo busca generalizar el marco de computación eficiente de Lehmer a cocientes de eta de peso negativo arbitrario.

Metodología
Los autores desarrollan un marco teórico para expresar los coeficientes HRR $A^\delta_k(n)$ para cocientes de eta generales en términos de sumas de Kloosterman retorcidas. La metodología progresa a través de tres etapas principales:

1. Caracterización de los Coeficientes HRR: Los autores analizan la estructura de las sumas de Dedekind que aparecen en la definición de $A^\delta_k(n)$. Utilizando congruencias y relaciones de reciprocidad conocidas para las sumas de Dedekind, derivan fórmulas explícitas que relacionan $A^\delta_k(n)$ con sumas de Kloosterman retorcidas $S_\chi(a-n, b; k)$. Esto se logra descomponiendo los términos exponenciales en la definición de $A^\delta_k(n)$ en caracteres y componentes aditivos módulo $k$.
2. Análisis de Multiplicatividad: El artículo investiga si los coeficientes HRR satisfacen relaciones de multiplicatividad de la forma $A^\delta_{k_1 k_2}(n) = A^\delta_{k_1}(n_1) A^\delta_{k_2}(n_2)$ para $k_1, k_2$ coprimos. Los autores establecen condiciones suficientes bajo las cuales tal descomposición se cumple, involucrando la solvencia de un sistema específico de congruencias relacionado con los parámetros del cociente de eta.
3. Derivación de la Cota de Error: Para asegurar que la serie HRR pueda utilizarse para la computación exacta de enteros, los autores derivan una cota explícita para el error de truncamiento (la cola de la serie). Esto implica estimar el crecimiento de las funciones de Bessel modificadas y la magnitud de los coeficientes HRR.

Contribuciones Clave y Resultados

• Expresión Generalizada mediante Sumas de Kloosterman Retorcidas (Teorema 4.5): El artículo demuestra que para cualquier entero positivo $k$, el coeficiente HRR $A^\delta_k(n)$ puede expresarse como $i^c \psi(1) S_{\chi\rho}(a-n, b; k)$, donde $S_{\chi\rho}$ es una suma de Kloosterman retorcida. A diferencia del resultado de Lehmer para la función de partición, que estaba restringido a módulos de potencia de primos, este resultado se sostiene para cada entero $k$. Esto permite la aplicación de fórmulas de forma cerrada para sumas de Kloosterman para computar $A^\delta_k(n)$ eficientemente.
• Multiplicatividad de los Coeficientes (Teorema 5.1): Los autores demuestran que, bajo hipótesis específicas (la existencia de un entero $\ell$ que satisface un sistema de congruencias involucrando el cociente de eta), los coeficientes satisfacen una relación de multiplicatividad. Esto reduce la computación de $A^\delta_k(n)$ para $k$ compuestos a las computaciones para sus factores de potencia de primos, reduciendo significativamente la complejidad computacional. El artículo señala que, si bien esto se cumple para particiones y sobreparticiones, no se cumple universalmente para todos los cocientes de eta, proporcionando un contraejemplo donde la relación falla.
• Cotas de Error Explícitas (Teorema 6.3): Se deriva una cota explícita $M(n, N)$ para el término de error $R(n, N)$ resultante de truncar la serie HRR en $N$. Esta cota depende del peso del cociente de eta y de los parámetros de la serie. Los autores demuestran que esta cota disminuye asintóticamente como $O(N^{-c_1})$, asegurando que la serie pueda truncarse para computar $a(n)$ exactamente mediante el redondeo de la suma parcial al entero más cercano.
• Implementación Algorítmica: El artículo sintetiza estos resultados en el Algoritmo 7.1, el cual computa $A^\delta_k(n)$ factorizando $k$ en potencias de primos, aplicando el teorema de multiplicatividad donde sea posible, y utilizando las fórmulas de forma cerrada para sumas de Kloosterman (de la Sección 3) para los componentes de potencia de primos.

Significancia y Reivindicaciones
El artículo afirma extender los métodos de computación eficiente previamente conocidos solo para la función de partición y las sobreparticiones a una amplia clase de cocientes de eta de peso negativo. La significancia radica en:

1. Eficiencia: Al reducir la computación de $A^\delta_k(n)$ a sumas de Kloosterman retorcidas y utilizar la multiplicatividad, los autores proporcionan un método que evita la suma directa de raíces de la unidad. Ilustran esto con un ejemplo donde la computación de los coeficientes para particiones de 5 colores de $10^6$ toma menos de 9 segundos usando su algoritmo, comparado con más de 1 hora y 15 minutos usando la definición.
2. Generalidad: Los resultados se aplican a cocientes de eta de peso negativo generales, no solo a casos específicos. La derivación de la cota de error (Teorema 6.3) es uniforme en toda esta clase, permitiendo la computación exacta para cualquier función de este tipo.
3. Extensión Teórica: El trabajo generaliza los hallazgos de Lehmer, mostrando que la estructura subyacente de los coeficientes HRR está fundamentalmente ligada a las sumas de Kloosterman retorcidas para todo $k$, no solo para potencias de primos.

Los autores mantienen la modestia respecto al alcance del resultado de multiplicatividad, señalando explícitamente que las condiciones para el Teorema 5.1 no siempre se cumplen (como se muestra en el Ejemplo 7.3), en cuyo caso se debe usar directamente la fórmula general de la suma de Kloosterman (Teorema 4.5). Se espera que la complejidad del algoritmo propuesto sea $O(n^{1/2} \log^{4+o(1)} n)$, comparable a la complejidad óptima para la función de partición.