Résumé technique : Principes d'incertitude pour la transformée de numérologie entière (NTT)

1. Énoncé du problème et motivation

L'article traite du problème du test d'identité polynomiale (PIT) pour les expressions impliquant des exponentielles, un domaine récemment formalisé par Li et Wu [LW26]. Dans ce cadre, il s'agit de déterminer si une expression de la forme $P(x) = \sum_{j=1}^k f_j(x) \exp(g_j(x)/h_j(x))$ est identiquement nulle.

Le défi central pour tester de telles expressions sur des corps finis réside dans la définition d'un modèle d'évaluation robuste. Li et Wu ont proposé un modèle utilisant deux nombres premiers, $p$ et $q$ (où $p \equiv 1 \pmod q$), interprétant les exponentielles via le sous-groupe unique d'ordre $q$ de $\mathbb{F}_p^*$. Cependant, leur analyse de l'erreur de robustesse (la probabilité d'accepter un polynôme non nul) a produit une borne de $q^{-1/(k-1)} + O(dk^2/q)$. Dans le régime pratique où $q = k^{O(1)}$, cette erreur approche 1, rendant le test inefficace.

Li et Wu ont conjecturé que cette faible robustesse est liée à un manque de principes d'incertitude pour la transformée de numérologie entière (NTT) sur les corps finis. Plus précisément, ils ont conjecturé qu'un polynôme creux avec peu de coefficients non nuls ne peut pas posséder trop de racines dans le sous-groupe $G$. Les auteurs de cet article visent à prouver de tels principes d'incertitude afin d'améliorer la robustesse de l'identification.

2. Méthodologie et approche technique

Les auteurs étudient la relation entre la parcimonie d'un vecteur $f$ et la parcimonie de sa NTT, $\hat{f}$. Ils définissent la taille du support $|\text{Supp}(f)|$ comme le nombre de coordonnées non nulles. L'objectif est d'établir des bornes inférieures sur $|\text{Supp}(f)| + |\text{Supp}(\hat{f})|$.

2.1 Incertitude additive via l'hyperinvertibilité

La première approche adapte la stratégie de Tao [Tao05] pour la transformée de Fourier discrète (DFT) complexe. Dans le cadre complexe, la matrice DFT est « hyperinvertible » (chaque sous-matrice carrée est inversible), ce qui implique un principe d'incertitude additive fort : $|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$.

Les auteurs notent que cette propriété échoue pour les corps finis en général (comme le montre Zhang [Zha19]). Cependant, ils prouvent que pour un nombre premier $q$ fixé, l'hyperinvertibilité de la matrice de la NTT est vérifiée pour tous les nombres premiers $p \equiv 1 \pmod q$, sauf un nombre fini.

• Technique de preuve : Ils utilisent le résultant de polynômes. Pour toute sous-matrice carrée de la matrice de Fourier, ils construisent un polynôme $D_{R,C}(z)$ dont le déterminant est non nul aux racines primitives $q$-ièmes de l'unité (par le résultat complexe). Ils montrent que si une sous-matrice devient singulière modulo $p$, alors $p$ doit diviser le résultant de $D_{R,C}(z)$ et du polynôme cyclotomique $\Phi_q(z)$. Comme le résultant est un entier non nul, il possède seulement un nombre fini de diviseurs premiers, ce qui limite les nombres premiers $p$ « mauvais ».

2.2 Incertitude approximative pour les régimes polynomiaux

Le résultat d'incertitude additive ci-dessus nécessite que $p$ soit extrêmement grand (approximativement $p \approx q^{q^2}$), ce qui est peu pratique pour les applications où $p = q^{O(1)}$. Pour y remédier, les auteurs prouvent un principe d'incertitude probabiliste (approximatif).

• Régime : Ils considèrent $p$ échantillonné uniformément dans l'intervalle $P(q) = \{p \le q^4 : p \text{ est premier}, p \equiv 1 \pmod q\}$.
• Technique de preuve : Ils fixent un polynôme entier creux $f$ et analysent la probabilité que $f$ s'annule en une racine primitive $q$-ième modulo un nombre premier $p$ choisi au hasard.
  • Si $f$ s'annule en une telle racine, alors $p$ doit diviser le résultant $\text{Res}(f, \Phi_q)$.
  • En utilisant la formule produit de Poisson, ils bornent la magnitude de ce résultant par $\|f\|_1^{q-1}$.
  • Cela implique qu'il existe au plus $(q-1)\log_2 \|f\|_1$ nombres premiers $p$ « mauvais » où le principe d'incertitude échoue.
  • En invoquant le théorème de Bombieri–Vinogradov, ils montrent que pour une infinité de $q$, l'ensemble $P(q)$ est suffisamment grand ($|P(q)| \ge q^3 / (32 \log q)$) pour que la densité des nombres premiers mauvais soit négligeable.

3. Contributions clés et résultats

3.1 Incertitude additive forte (Théorème 1.1 / Théorème 3.1)

Pour tout nombre premier $q$ fixé, et pour tous les nombres premiers $p \equiv 1 \pmod q$ sauf un nombre fini, toute fonction non nulle $f \in \mathbb{F}_p^{\mathbb{Z}_q}$ satisfait :
$$|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$$
Cela implique qu'une fonction $k$-creuse possède un support de transformée d'au moins $q - k + 1$. Ce résultat fournit une version non uniforme de la conjecture de Li-Wu, valable lorsque $p$ peut croître suffisamment vite par rapport à $q$.

3.2 Incertitude approximative (Théorème 1.2 / Théorème 3.6)

Pour une infinité de nombres premiers $q$, et pour tout vecteur entier non nul $c$ tel que $|\text{Supp}(c)| < q$ et la norme $\ell_1$ est $W$, la taille attendue du support de la NTT inverse sur un nombre premier $p$ aléatoire de $P(q)$ satisfait :
$$\mathbb{E}_p [|\text{Supp}(\hat{c})|] \ge q - 1 - \frac{32(q-1)\log q}{q^2} \log_2 W$$
Ce résultat est valable dans le régime réaliste où $p$ est polynomialement borné par rapport à $q$.

3.3 Amélioration du test d'identité (Théorème 1.3 / Théorème 4.3)

Les auteurs appliquent ces principes pour construire un test d'identité à boîte noire modifié pour les exponentielles polynomiales $k$-creuses de degré $d$ et de hauteur de coefficient $w$.

• Modification : Le test échantillonne le nombre premier $p$ aléatoirement dans l'intervalle $P(q)$ en plus des points d'évaluation aléatoires standards.
• Borne de robustesse : Si $P \not\equiv 0$, la probabilité d'acceptation est bornée par :
  $$O\left(\frac{dk^2}{q}\right) + O\left(\frac{1}{q}\right) + O\left(\frac{\log(kw)\log q}{q^2}\right)$$
• Signification : Si $q = k^C$ avec $C > 2$ et que $kw$ est polynomialement borné, l'erreur de robustesse devient $o(1)$ (plus précisément, elle tend vers 0 quand $q$ croît). C'est une amélioration directe de la borne de Li-Wu de $q^{-1/(k-1)}$, qui approche 1 dans le même régime.

4. Signification et affirmations

L'article affirme que la contribution principale est l'établissement de principes d'incertitude additive pour la NTT, qui sont nécessaires pour prouver la robustesse dans le test d'identité. Les auteurs précisent explicitement que le principe d'incertitude multiplicatif standard (Donoho–Stark) est insuffisant à cette fin.

La portée de ce travail réside dans :

1. Résolution d'une conjecture : Fournir une preuve formelle d'un principe d'incertitude fort pour la NTT dans des régimes spécifiques, validant l'intuition derrière la conjecture de Li et Wu.
2. Amélioration algorithmique : Démontrer qu'en randomisant le choix du modulo premier $p$, on peut obtenir une erreur de robustesse constante pour le test d'identité des exponentielles polynomiales, une tâche auparavant considérée comme ayant des taux d'erreur élevés dans des configurations de paramètres pratiques.
3. Pont théorique : Connecter les propriétés algébriques des résultants et des polynômes cyclotomiques aux propriétés de parcimonie des transformées sur les corps finis.

Les auteurs restent modestes quant à la nature « non uniforme » de leur résultat le plus fort (Théorème 3.1), notant qu'il s'applique à « tous les nombres premiers sauf un nombre fini », et s'appuient sur le résultat probabiliste (Théorème 3.6) pour l'application pratique où $p$ est petit. Ils ne prétendent pas résoudre le problème général du PIT pour toutes les expressions exponentielles, mais spécifiquement pour le cas creux et condensé défini dans leur section d'application.