Technische Samenvatting: Onzekerheidsprincipes voor de Getaltheoretische Transformatie (NTT)

1. Probleemstelling en Motivatie

Het artikel behandelt het probleem van Polynomial Identity Testing (PIT) voor expressies met exponenten, een domein dat recentelijk is geformaliseerd door Li en Wu [LW26]. In deze setting moet men bepalen of een expressie van de vorm $P(x) = \sum_{j=1}^k f_j(x) \exp(g_j(x)/h_j(x))$ identiek nul is.

De kernuitdaging bij het testen van dergelijke expressies over eindige lichamen ligt in het definiëren van een betrouwbaar evaluatiemodel. Li en Wu stelden een model voor met twee priemgetallen, $p$ en $q$ (waarbij $p \equiv 1 \pmod q$), waarbij exponenten worden geïnterpreteerd via de unieke subgroep van orde $q$ in $\mathbb{F}_p^*$. Hun analyse van de foutmarge (de kans op acceptatie van een niet-nul polynoom) leverde echter een bovengrens op van $q^{-1/(k-1)} + O(dk^2/q)$. In het praktische regime waar $q = k^{O(1)}$, nadert deze fout 1, waardoor de test ineffectief wordt.

Li en Wu vermoedden dat deze slechte betrouwbaarheid gerelateerd is aan een gebrek aan onzekerheidsprincipes voor de Getaltheoretische Transformatie (NTT) over eindige lichamen. Specifiek vermoedden zij dat een ijle (sparse) polynoom met weinig niet-nul coëfficiënten niet te veel nulpunten kan hebben in de subgroep $G$. De auteurs van dit artikel beogen dergelijke onzekerheidsprincipes te bewijzen om de betrouwbaarheid van identity testing te verbeteren.

2. Methodologie en Technische Aanpak

De auteurs onderzoeken de relatie tussen de ijleheid van een vector $f$ en de ijleheid van zijn NTT, $\hat{f}$. Ze definiëren de support-grootte $|\text{Supp}(f)|$ als het aantal niet-nul coördinaten. Het doel is om ondergrenzen vast te stellen op $|\text{Supp}(f)| + |\text{Supp}(\hat{f})|$.

2.1 Additieve Onzekerheid via Hyperinvertibiliteit

De eerste aanpak past de strategie van Tao [Tao05] voor de complexe Discrete Fourier Transformatie (DFT) aan. In de complexe setting is de DFT-matrix "hyperinvertibel" (elke vierkante submatrix is invertibel), wat een sterke additieve onzekerheid impliceert: $|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$.

De auteurs merken op dat deze eigenschap in het algemeen niet geldt voor eindige lichamen (zoals aangetoond door Zhang [Zha19]). Echter, zij bewijzen dat voor een vast priemgetal $q$, de hyperinvertibiliteit van de NTT-matrix standhoudt voor alle behalve een eindig aantal priemgetallen $p \equiv 1 \pmod q$.

• Bewijstechniek: Zij maken gebruik van het resultant van polynomen. Voor elke vierkante submatrix van de Fourier-matrix construeren zij een polynoom $D_{R,C}(z)$ waarvan de determinant niet nul is bij primitieve $q$-de eenheden (door de complexe resultaten). Zij tonen aan dat als een submatrix singulier wordt modulo $p$, dan $p$ het resultant moet delen van $D_{R,C}(z)$ en het cyclotomische polynoom $\Phi_q(z)$. Aangezien het resultant een niet-nul geheel getal is, heeft het slechts een eindig aantal priemdelers, wat de "slechte" priemgetallen $p$ beperkt.

2.2 Benaderde Onzekerheid voor Polynoomregimes

Het bovenstaande resultaat voor additieve onzekerheid vereist dat $p$ extreem groot is (ongeveer $p \approx q^{q^2}$), wat onpraktisch is voor toepassingen waar $p = q^{O(1)}$. Om dit aan te pakken, bewijzen de auteurs een probabilistisch (benaderd) onzekerheidsprincipe.

• Regime: Zij beschouwen $p$ gesampled uit een uniform interval $P(q) = \{p \le q^4 : p \text{ is priem}, p \equiv 1 \pmod q\}$.
• Bewijstechniek: Zij fixeren een ijle gehele polynoom $f$ en analyseren de kans dat $f$ verdwijnt bij een primitieve $q$-de eenheid modulo een willekeurig priemgetal $p$.
  • Als $f$ verdwijnt bij een dergelijke eenheid, dan moet $p$ het resultant $\text{Res}(f, \Phi_q)$ delen.
  • Door de Poisson-productformule te gebruiken, begrenzen zij de grootte van dit resultant door $\|f\|_1^{q-1}$.
  • Dit impliceert dat er maximaal $(q-1)\log_2 \|f\|_1$ "slechte" priemgetallen $p$ zijn waar het onzekerheidsprincipe faalt.
  • Door de Bombieri–Vinogradov stelling aan te roepen, tonen zij aan dat voor oneindig veel $q$, de verzameling $P(q)$ groot genoeg is ($|P(q)| \ge q^3 / (32 \log q)$) zodat de dichtheid van de slechte priemgetallen verwaarloosbaar is.

3. Belangrijkste Bijdragen en Resultaten

3.1 Sterke Additieve Onzekerheid (Theorem 1.1 / Theorem 3.1)

Voor elk vast priemgetal $q$, en voor alle behalve een eindig aantal priemgetallen $p \equiv 1 \pmod q$, voldoet elke niet-nul $f \in \mathbb{F}_p^{\mathbb{Z}_q}$ aan:
$$|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$$
Dit impliceert dat een $k$-ijle functie een transform-support heeft van ten minste $q - k + 1$. Dit resultaat biedt een niet-uniforme versie van de Li-Wu conjectuur, die geldig is wanneer $p$ voldoende snel groeit met $q$.

3.2 Benaderde Onzekerheid (Theorem 1.2 / Theorem 3.6)

Voor oneindig veel priemgetallen $q$, en voor elke niet-nul gehele vector $c$ met $|\text{Supp}(c)| < q$ en $\ell_1$-norm $W$, voldoet de verwachte support-grootte van de inverse NTT over een willekeurig priemgetal $p \in P(q)$ aan:
$$\mathbb{E}_p [|\text{Supp}(\hat{c})|] \ge q - 1 - \frac{32(q-1)\log q}{q^2} \log_2 W$$
Dit resultaat is geldig in het realistische regime waar $p$ polynomiaal begrensd is in $q$.

3.3 Verbeterde Identity Testing (Theorem 1.3 / Theorem 4.3)

De auteurs passen deze principes toe om een gemodificeerde black-box identity test te construeren voor $k$-ijle exponentiële polynomen van graad $d$ en coëfficiënt-hoogte $w$.

• Modificatie: De test samplet het priemgetal $p$ willekeurig uit het interval $P(q)$, naast de standaard willekeurige evaluatiepunten.
• Betrouwbaarheidsgrens: Indien $P \not\equiv 0$, wordt de kans op acceptatie begrensd door:
  $$O\left(\frac{dk^2}{q}\right) + O\left(\frac{1}{q}\right) + O\left(\frac{\log(kw)\log q}{q^2}\right)$$
• Significantie: Indien $q = k^C$ met $C > 2$ en $kw$ polynomiaal begrensd is, wordt de foutmarge $o(1)$ (specifiek, deze nadert 0 naarmate $q$ groeit). Dit is een directe verbetering ten opzien van de Li-Wu grens van $q^{-1/(k-1)}$, die in hetzelfde regime naar 1 nadert.

4. Significantie en Claims

Het artikel stelt dat de primaire bijdrage het vaststellen van additieve onzekerheidsprincipes voor de NTT is, die noodzakelijk zijn voor het bewijzen van de betrouwbaarheid in identity testing. De auteurs stellen expliciet dat het standaard multiplicatieve onzekerheidsprincipe (Donoho–Stark) onvoldoende is voor dit doel.

De significantie van het werk ligt in:

1. Het oplossen van een conjectuur: Het leveren van een formeel bewijs voor een sterk onzekerheidsprincipe voor de NTT in specifieke regimes, wat de intuïtie achter de conjectuur van Li en Wu valideert.
2. Algoritmische verbetering: Het aantonen dat door de keuze van het priemgetal $p$ te randomiseren, men een constante betrouwbaarheidsfout kan bereiken voor de identity testing van exponentiële polynomen, een taak die voorheen werd geacht hoge foutpercentages te hebben in praktische parameterinstellingen.
3. Theoretische brug: Het verbinden van de algebraïsche eigenschappen van resultanten en cyclotomische polynomen aan de support-eigenschappen van transformaties over eindige lichamen.

De auteurs blijven bescheiden over het "niet-uniforme" karakter van hun sterkste resultaat (Theorem 3.1), waarbij zij opmerken dat dit geldt voor "alle behalve een eindig aantal" priemgetallen, en vertrouwen op het probabilistische resultaat (Theorem 3.6) voor de praktische toepassing waar $p$ klein is. Zij beweren niet het algemene PIT-probleem voor alle exponentiële expressies te hebben opgelost, maar specifien voor de ijle, gecondenseerde casus zoals gedefinieerd in hun applicatiesectie.