On the efficient computation of Fourier coefficients of eta-quotients

Resumo Técnico: Sobre a Computação Eficiente de Coeficientes de Fourier de Eta-Quotients

Enunciado do Problema
O artigo aborda o desafio computacional de determinar os coeficientes de Fourier $a(n)$ de eta-quotients de peso negativo. Embora a expansão de Hardy–Ramanujan–Rademacher (HRR) forneça uma representação em série convergente para esses coeficientes (estabelecida genericamente por Sussman para pesos negativos), a utilidade prática dessa expansão é dificultada pela dificuldade de computar os termos centrais, conhecidos como coeficientes HRR $A^\delta_k(n)$. A computação direta via definição envolve a soma de raízes da unidade sobre resíduos coprimos, um processo computacionalmente dispendioso. Para a função de partição clássica $p(n)$, Lehmer demonstrou que esses coeficientes poderiam ser computados eficientemente explorando a multiplicatividade e expressando-os via somas de Kloosterman torcidas. Este artigo busca generalizar o arcabouço computacional eficiente de Lehmer para arbitrários eta-quotients de peso negativo.

Metodologia
Os autores desenvolvem um arcabouço teórico para expressar os coeficientes HRR $A^\delta_k(n)$ para eta-quotients gerais $\eta^\delta$ em termos de somas de Kloosterman torcidas. A metodologia procede através de três estágios principais:

1. Caracterização dos Coeficientes HRR: Os autores analisam a estrutura das somas de Dedekind que aparecem na definição de $A^\delta_k(n)$. Utilizando congruências conhecidas e relações de reciprocidade para somas de Dedekind, eles derivam fórmulas explícitas que relacionam $A^\delta_k(n)$ a somas de Kloosterman torcidas $S_\chi(a-n, b; k)$. Isso é alcançado ao decompor os termos exponenciais na definição de $A^\delta_k(n)$ em caracteres e componentes aditivos módulo $k$.
2. Análise de Multiplicatividade: O artigo investiga se os coeficientes HRR satisfazem relações de multiplicatividade da 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. Os autores estabelecem condições suficientes sob as quais tal decomposição ocorre, envolvendo a solubilidade de um sistema específico de congruências relacionado aos parâmetros do eta-quotient.
3. Derivação de Limites de Erro: Para garantir que a série HRR possa ser usada para computação exata de inteiros, os autores derivam um limite superior explícito para o erro de truncamento (a cauda da série). Isso envolve estimar o crescimento das funções de Bessel modificadas e a magnitude dos coeficientes HRR.

Principais Contribuições e Resultados

• Expressão Generalizada via Somas de Kloosterman Torcidas (Teorema 4.5): O artigo prova que, para qualquer inteiro positivo $k$, o coeficiente HRR $A^\delta_k(n)$ pode ser expresso como $i^c \psi(1) S_{\chi\rho}(a-n, b; k)$, onde $S_{\chi\rho}$ é uma soma de Kloosterman torcida. Diferentemente do resultado de Lehmer para a função de partição, que era restrito a módulos de potência de primos, este resultado é válido para todo inteiro $k$. Isso permite a aplicação de fórmulas de forma fechada para somas de Kloosterman para computar $A^\delta_k(n)$ eficientemente.
• Multiplicatividade dos Coeficientes (Teorema 5.1): Os autores provam que, sob hipóteses específicas (existência de um inteiro $\ell$ satisfazendo um sistema de congruências envolvendo o expoente do eta-quotient), os coeficientes satisfazem uma relação de multiplicatividade. Isso reduz a computação de $A^\delta_k(n)$ para $k$ compostos às computações para fatores de potência de primos, diminuindo significativamente a complexidade computacional. O artigo observa que, embora isso ocorra para partições e overpartitions, não ocorre universalmente para todos os eta-quotients, fornecendo um contraexemplo onde a relação falha.
• Limites de Erro Explícitos (Teorema 6.3): Um limite explícito $M(n, N)$ é derivado para o termo de erro $R(n, N)$ resultante do truncamento da série HRR em $N$. Este limite depende do peso do eta-quotient e dos parâmetros da série. Os autores demonstram que este limite diminui assintoticamente como $O(N^{-c_1})$, garantindo que a série possa ser truncada para computar $a(n)$ exatamente através do arredondamento da soma parcial para o inteiro mais próximo.
• Implementação Algorítmica: O artigo sintetiza esses resultados no Algoritmo 7.1, que computa $A^\delta_k(n)$ fatorando $k$ em potências de primos, aplicando o teorema de multiplicatividade onde possível, e utilizando as fórmulas de soma de Kloosterman de forma fechada (da Seção 3) para os componentes de potência de primos.

Significância e Alegações
O artigo alega estender os métodos de computação eficiente anteriormente conhecidos apenas para a função de partição e overpartitions para uma ampla classe de eta-quotients de peso negativo. A significância reside em:

1. Eficiência: Ao reduzir a computação de $A^\delta_k(n)$ para somas de Kloosterman torcidas e utilizar a multiplicatividade, os autores fornecem um método que evita a soma direta de raízes da unidade. Eles ilustram isso com um exemplo onde a computação de coeficientes para partições de 5 cores de $10^6$ leva menos de 9 segundos usando seu algoritmo, comparado a mais de 1 hora e 15 minutos usando a definição.
2. Generalidade: Os resultados aplicam-se a eta-quotients gerais de peso negativo, não apenas casos específicos. A derivação do limite de erro (Teorema 6.3) é uniforme em toda esta classe, permitindo a computação exata para qualquer tal função.
3. Extensão Teórica: O trabalho generaliza as descobertas de Lehmer, mostrando que a estrutura subjacente dos coeficientes HRR está fundamentalmente ligada às somas de Kloosterman torcidas para todo $k$, não apenas para potências de primos.

Os autores mantêm-se modestos quanto ao escopo do resultado de multiplicatividade, notando explicitamente que as condições para o Teorema 5.1 nem sempre são atendidas (como mostrado no Exemplo 7.3), caso em que a fórmula geral de soma de Kloosterman (Teorema 4.5) deve ser usada diretamente. Espera-se que a complexidade do algoritmo proposto seja $O(n^{1/2} \log^{4+o(1)} n)$, comparável à complexidade ótima para a função de partição.