On the efficient computation of Fourier coefficients of eta-quotients

Sintesi Tecnica: Sull'efficace computazione dei coefficienti di Fourier di prodotti di eta

Enunciato del Problema
Il saggio affronta la sfida computazionale di determinare i coefficienti di Fourier $a(n)$ di prodotti di eta a peso negativo. Sebbene l'espansione di Hardy–Ramanujan–Rademacher (HRR) fornisca una rappresentazione in serie convergente per questi coefficienti (stabilita generalmente da Sussman per pesi negativi), l'utilità pratica di questa espansione è ostacolata dalla difficoltà di calcolare i termini centrali, noti come coefficienti HRR $A^\delta_k(n)$. Il calcolo diretto tramite la definizione comporta la sommatoria di radici dell'unità su residui coprimi, un processo computazionalmente oneroso. Per la classica funzione partizione $p(n)$, Lehmer ha dimostrato che questi coefficienti potevano essere calcolati efficientemente sfruttando la molteplicatività e descrivendoli tramite somme di Kloosterman ritorti. Questo saggio mira a generalizzare il framework computazionale efficiente di Lehmer a arbitrari prodotti di eta a peso negativo.

Metodologia
Gli autori sviluppano un framework teorico per esprimere i coefficienti HRR $A^\delta_k(n)$ per generi di prodotti di eta $\eta^\delta$ in termini di somme di Kloosterman ritorti. La metodologia procede attraverso tre fasi principali:

1. Caratterizzazione dei Coefficienti HRR: Gli autori analizzano la struttura delle somme di Dedekind che compaiono nella definizione di $A^\delta_k(n)$. Utilizzando congruenze note e relazioni di reciprocità per le somme di Dedekind, derivano formule esplicite che mettono in relazione $A^\delta_k(n)$ con le somme di Kloosterman ritorti $S_\chi(a-n, b; k)$. Ciò viene ottenuto decomponendo i termini esponenziali nella definizione di $A^\delta_k(n)$ in caratteri e componenti additive modulo $k$.
2. Analisi della Molteplicatività: Il saggio investiga se i coefficienti HRR soddisfino relazioni di molteplicatività del tipo $A^\delta_{k_1 k_2}(n) = A^\delta_{k_1}(n_1) A^\delta_{k_2}(n_2)$ per $k_1, k_2$ coprimi. Gli autori stabiliscono condizioni sufficienti sotto le quali tale decomposizione è valida, coinvolgendo la risolvibilità di un sistema specifico di congruenze relativo ai parametri del prodotto di eta.
3. Derivazione del Limite di Errore: Per garantire che la serie HRR possa essere utilizzata per il calcolo esatto di interi, gli autori derivano un limite superiore esplicito per l'errore di troncamento (la coda della serie). Ciò comporta la stima della crescita delle funzioni di Bessel modificate e dell'ampiezza dei coefficienti HRR.

Contributi Chiave e Risultati

• Espressione Generalizzata tramite Somme di Kloosterman Ritorti (Teorema 4.5): Il saggio dimostra che per ogni intero positivo $k$, il coefficiente HRR $A^\delta_k(n)$ può essere espresso come $i^c \psi(1) S_{\chi\rho}(a-n, b; k)$, dove $S_{\chi\rho}$ è una somma di Kloosterman ritorta. A differenza del risultato di Lehmer per la funzione partizione, che era limitato a moduli di potenza di numeri primi, questo risultato è valido per ogni intero $k$. Ciò consente l'applicazione di formule in forma chiusa per le somme di Kloosterman per calcolare $A^\delta_k(n)$ efficientemente.
• Molteplicatività dei Coefficienti (Teorema 5.1): Gli autori dimostrano che, sotto specifiche ipotesi (esistenza di un intero $\ell$ che soddisfi un sistema di congruenze coinvolgenti gli esponenti del prodotto di eta), i coefficienti soddisfano una relazione di molteplicatività. Ciò riduce il calcolo di $A^\delta_k(n)$ per $k$ composti al calcolo per i fattori di potenza di primi, abbassando significativamente la complessità computazionale. Il saggio nota che, sebbene ciò sia valido per le partizioni e le overpartizioni, non vale universalmente per tutti i prodotti di eta, fornendo un controesempio in cui la relazione fallisce.
• Limiti di Errore Espliciti (Teorema 6.3): Un limite esplicito $M(n, N)$ è derivato per il termine di errore $R(n, N)$ risultante dal troncamento della serie HRR a $N$. Questo limite dipende dal peso del prodotto di eta e dai parametri della serie. Gli autori dimostrano che questo limite decresce asintoticamente come $O(N^{-c_1})$, garantendo che la serie possa essere troncata per calcolare $a(n)$ esattamente tramite l'arrotondamento della somma parziale all'intero più vicino.
• Implementazione Algoritmica: Il saggio sintetizza questi risultati nell'Algoritmo 7.1, che calcola $A^\delta_k(n)$ fattorizzando $k$ in potenze di primi, applicando il teorema di molteplicatività ove possibile, e utilizzando le formule in forma chiusa per le somme di Kloosterman (dal Sezione 3) per le componenti di potenza di primi.

Significatività e Rivendicazioni
Il saggio rivendica di estendere i metodi di calcolo efficiente precedentemente noti solo per la funzione partizione e le overpartizioni a una vasta classe di prodotti di eta a peso negativo. La significatività risiede in:

1. Efficienza: Riducendo il calcolo di $A^\delta_k(n)$ alle somme di Kloosterman ritorti e utilizzando la molteplicatività, gli autori forniscono un metodo che evita la sommatoria diretta delle radici dell'unità. Lo illustrano con un esempio in cui il calcolo dei coefficienti per le partizioni a 5 colori di $10^6$ richiede meno di 9 secondi utilizzando il loro algoritmo, rispetto a oltre 1 ora e 15 minuti utilizzando la definizione.
2. Generalità: I risultati si applicano a generi di prodotti di eta a peso negativo, non solo a casi specifici. La derivazione del limite di errore (Teorema 6.3) è uniforme per questa classe, consentendo il calcolo esatto per qualsiasi tale funzione.
3. Estensione Teorica: Il lavoro generalizza le scoperte di Lehmer, mostrando che la struttura sottostante dei coefficienti HRR è fondamentalmente legata alle somme di Kloosterman ritorti per tutti i valori di $k$, non solo per le potenze di numeri primi.

Gli autori rimangono modesti riguardo all'ambito del risultato di molteplicatività, notando esplicitamente che le condizioni per il Teorema 5.1 non sono sempre soddisfatte (come mostrato nell'Esempio 7.3), nel qual caso deve essere utilizzata direttamente la formula generale della somma di Kloosterman (Teorema 4.5). La complessità dell'algoritmo proposto è attesa essere $O(n^{1/2} \log^{4+o(1)} n)$, comparabile alla complessità ottimale per la funzione partizione.