On the efficient computation of Fourier coefficients of eta-quotients

Technische Samenvatting: Over de Efficiënte Berekening van Fouriercoëfficiënten van Eta-quotiënten

Probleemstelling
Het artikel behandelt de computationele uitdaging van het bepalen van de Fouriercoëfficiënten $a(n)$ van eta-quotiënten met een negatief gewicht. Hoewel de Hardy–Ramanujan–Rademacher (HRR) expansie een convergerende reeksrepresentatie biedt voor deze coëfficiënten (algemeen vastgesteld door Sussman voor negatieve gewichten), wordt het praktische nut van deze expansie gehinderd door de moeilijkheid van het berekenen van de centrale termen, bekend als HRR-coëfficiënten $A^\delta_k(n)$. Directe berekening via de definitie omvat het sommeren van eenheden van wortels over coprime residuen, een proces dat computationeel kostbaar is. Voor de klassieke partitiefunctie $p(n)$ toonde Lehmer aan dat deze coëfficiënten efficiënt berekend kunnen worden door gebruik te maken van multipliciteit en door ze uit te drukken via getwiste Kloosterman-sommen. Dit artikel streeft ernaar om de efficiënte computationele raamwerk van Lehmer te generaliseren naar willekeurige eta-quotiënten met een negatief gewicht.

Methodologie
De auteurs ontwikkelen een theoretisch kader om de HRR-coëfficiënten $A^\delta_k(n)$ voor algemene eta-quotiënten $\eta^\delta$ uit te drukken in termen van getwiste Kloosterman-sommen. De methodologie verloopt via drie hoofdfasen:

1. Karakterisering van HRR-coëfficiënten: De auteurs analyseren de structuur van de Dedekind-sommen die voorkomen in de definitie van $A^\delta_k(n)$. Door gebruik te maken van bekende congruenties en reciprociteitsrelaties voor Dedekind-sommen, leiden zij expliciete formules af die $A^\delta_k(n)$ relateren aan getwiste Kloosterman-sommen $S_\chi(a-n, b; k)$. Dit wordt bereikt door de exponentiële termen in de definitie van $A^\delta_k(n)$ te deconstrueren in karakters en additieve componenten modulo $k$.
2. Multipliciteitsanalyse: Het artikel onderzoekt of de HRR-coëfficiënten voldoen aan multipliciteitsrelaties van de vorm $A^\delta_{k_1 k_2}(n) = A^\delta_{k_1}(n_1) A^\delta_{k_2}(n_2)$ voor onderling priem $k_1, k_2$. De auteurs stellen voldoende voorwaarden vast waaronder een dergelijke decompositie geldt, welke verband houden met de oplosbaarheid van een specifiek stelsel van congruenties gerelateerd aan de parameters van de eta-quotiënt.
3. Afleiding van Foutgrenzen: Om te waarborgen dat de HRR-reeks gebruikt kan worden voor exacte gehele getalberekening, leiden de auteurs een expliciete bovengrens af voor de afkapfout (de staart van de reeks). Dit omvat het schatten van de groei van de gemodificeerde Bessel-functies en de grootte van de HRR-coëfficiënten.

Belangrijkste Bijdragen en Resultaten

• Gegeneraliseerde Expressie via Getwiste Kloosterman-sommen (Stelling 4.5): Het artikel bewijst dat voor elke positieve integer $k$, de HRR-coëfficiënt $A^\delta_k(n)$ kan worden uitgedrukt als $i^c \psi(1) S_{\chi\rho}(a-n, b; k)$, waarbij $S_{\chi\rho}$ een getwiste Kloosterman-som is. In tegen tegenstelling tot Lehmer's resultaat voor de partitiefunctie, dat beperkt was tot priemmachtmoduli, houdt dit resultaat stand voor elke integer $k$. Dit maakt de toepassing van gesloten vormules voor Kloosterman-sommen mogelijk om $A^\delta_k(n)$ efficiënt te berekenen.
• Multipliciteit van Coëfficiënten (Stelling 5.1): De auteurs bewijzen dat, onder specifieke hypothesen (het bestaan van een integer $\ell$ die een stelsel van congruenties bevredigt betrokken bij de eta-quotiënt), de coëfficiënten een multipliciteitsrelatie bevredigen. Dit reduceert de berekening van $A^\delta_k(n)$ voor samengestelde $k$ tot berekeningen voor priemmachtfactoren, wat de computationele complexiteit aanzienlijk verlaagt. Het artikel merkt op dat hoewel dit geldt voor partities en overpartities, dit niet universeel geldt voor alle eta-quotiënten, waarbij een tegenvoorbeeld wordt gegeven waar de relatie faalt.
• Expliciete Foutgrenzen (Stelling 6.3): Een expliciete bovengrens $M(n, N)$ wordt afgeleid voor de foutterm $R(n, N)$ die voortvloeit uit het afkappen van de HRR-reeks bij $N$. Deze bovengrens hangt af van het gewicht van de eta-quotiënt en de parameters van de reeks. De auteurs demonstreren dat deze bovengrens asymptotisch afneemt als $O(N^{-c_1})$, wat garandeert dat de reeks kan worden afgekapt om $a(n)$ exact te berekenen door de partiële som naar het dichtstbijzijnde gehele getal af te ronden.
• Algoritmische Implementatie: Het artikel synthetiseert deze resultaten in Algoritme 7.1, dat $A^\delta_k(n)$ berekent door $k$ te ontbinden in priemmachten, de multipliciteitsstelling toe te passen waar mogelijk, en de gesloten vormules voor Kloosterman-sommen (uit Sectie 3) te gebruiken voor de priemmachtcomponenten.

Betekenis en Claims
Het artikel claimt de efficiënte berekeningsmethoden, die voorheen alleen bekend waren voor de partitiefunctie en overpartities, uit te breiden naar een brede klasse van eta-quotiënten met een negatief gewicht. De betekenis ligt in:

1. Efficiëntie: Door de berekening van $A^\delta_k(n)$ te reduceren tot getwiste Kloosterman-sommen en gebruik te maken van multipliciteit, bieden de auteurs een methaling die de directe sommatie van eenheden van wortels vermijdt. Zij illustreren dit met een voorbeeld waarbij het berekenen van coëfficiënten voor 5-gekleurde partities van $10^6$ minder dan 9 seconden duurt met hun algoritme, vergeleken met meer dan 1 uur en 15 minuten met de definitie.
2. Generaliteit: De resultaten zijn van toepassing op algemene eta-quotiënten met een negatief gewicht, niet slechts op specifieke gevallen. De afleiding van de foutgrens (Stelling 6.3) is uniform over deze klasse, wat exacte berekening voor elk dergelijk functie mogelijk maakt.
3. Theoretische Uitbreiding: Het werk generaliseert de bevindingen van Lehmer, door aan te tonen dat de onderliggende structuur van HRR-coëfficiënten fundamenteel verbonden is met getwiste Kloosterman-sommen voor alle $k$, en niet enkel voor priemmachten.

De auteurs blijven bescheiden over de reikwijdte van het multipliciteitsresultaat, en merken expliciet op dat de voorwaarden voor Stelling 5.1 niet altijd worden voldaan (zoals getoond in Voorbeeld 7.3), in welk geval de algemene Kloosterman-somformule (Stelling 4.5) direct moet worden gebruikt. De complexiteit van het voorgestelde algoritme wordt verwacht $O(n^{1/2} \log^{4+o(1)} n)$ te zijn, vergelijkbaar met de optimale complexiteit voor de partitiefunctie.