Resumen Técnico: Principios de Incertidumbre para la Transformada de Números Teóricos

1. Planteamiento del Proble de y Motivación

El artículo aborda el problema de la Prueba de Identidad Polinómica (PIT) para expresiones que involucran exponenciales, un dominio recientemente formalizado por Li y Wu [LW26]. En este entorno, se debe determinar si una expresión de la forma $P(x) = \sum_{j=1}^k f_j(x) \exp(g_j(x)/h_j(x))$ es identicamente cero.

El desafío central al probar tales expresiones sobre cuerpos finitos reside en definir un modelo de evaluación sólido. Li y Wu propusieron un modelo utilizando dos primos, $p$ y $q$ (donde $p \equiv 1 \pmod q$), interpretando las exponenciales a través del subgrupo único de orden $q$ en $\mathbb{F}_p^*$. Sin embargo, su análisis del error de solidez (la probabilidad de aceptar un polinomio no nulo) arrojó un límite de $q^{-1/(k-1)} + O(dk^2/q)$. En el régimen práctico donde $q = k^{O(1)}$, este error se aproxima a 1, lo que hace que la prueba sea ineficaz.

Li y Wu conjeturaron que esta pobre solidez está relacionada con la falta de principios de incertidumbre para la Transformada de Números Teóricos (NTT) sobre cuerpos finitos. Específicamente, conjeturaron que un polinomio disperso con pocos coeficientes no puede tener demasiados ceros en el subgrupo $G$. Los autores de este artículo pretenden demostrar tales principios de incertidumbre para mejorar la solidez de la prueba de identidad.

2. Metodología y Enfoque Técnico

Los autores investigan la relación entre la dispersión de un vector $f$ y la dispersión de su NTT, $\hat{f}$. Definen el tamaño del soporte $|\text{Supp}(f)|$ como el número de coordenadas no nulas. El objetivo es establecer cotas inferiores en $|\text{Supp}(f)| + |\text{Supp}(\hat{f})|$.

2.1 Incertidumbre Aditiva mediante Hiperinvertibilidad

El primer enfoque adapta la estrategia de Tao [Tao05] para la Transformada Discreta de Fourier (DFT) compleja. En el entorno complejo, la matriz DFT es "hiperinvertible" (cada submatriz cuadrada es invertible), lo que implica un fuerte principio de incertidumbre aditiva: $|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$.

Los autores señalan que esta propiedad falla para los cuerpos finitos en general (como muestra Zhang [Zha19]). Sin embargo, demuestran que para un primo $q$ fijo, la hiperinvertibilidad de la matriz NTT se cumple para todos los primos $p \equiv 1 \pmod q$, excepto para un número finito de ellos.

• Técnica de Demostración: Utilizan el resultante de polinomios. Para cualquier submatriz cuadrada de la matriz de Fourier, construyen un polinomio $D_{R,C}(z)$ cuyo determinante es no nulo en las raíces de la unidad de orden $q$ primitivas (por el resultado complejo). Demuestran que si una submatriz se vuelve singular módulo $p$, entonces $p$ debe dividir el resultante de $D_{R,C}(z)$ y el polinomio ciclotómico $\Phi_q(z)$. Dado que el resultante es un entero no nulo, tiene solo un número finito de divisores primos, lo que limita los primos "malos" $p$.

2.2 Incertidumbre Aproximada para Regímenes Polinómicos

El resultado de incertidumbre aditiva anterior requiere que $p$ sea extremadamente grande (aproximadamente $p \approx q^{q^2}$), lo cual es poco práctico para aplicaciones donde $p = q^{O(1)}$. Para abordar esto, los autores demuestran un principio de incertidumbre probabilístico (aproximado).

• Régimen: Consideran $p$ muestreado uniformemente del intervalo $P(q) = \{p \le q^4 : p \text{ es primo}, p \equiv 1 \pmod q\}$.
• Técnica de Demostración: Fijan un polinomio entero disperso $f$ y analizan la probabilidad de que $f$ se anule en una raíz primitiva de orden $q$ módulo un primo aleatorio $p$.
  • Si $f$ se anula en tal raíz, entonces $p$ debe dividir el resultante $\text{Res}(f, \Phi_q)$.
  • Utilizando la fórmula de producto de Poisson, acotan la magnitud de este resultante por $\|f\|_1^{q-1}$.
  • Esto implica que hay como máximo $(q-1)\log_2 \|f\|_1$ primos "malos" $p$ donde el principio de incertidumbre falla.
  • Al invocar el teorema de Bombieri–Vinogradov, demuestran que para infinitos $q$, el conjunto $P(q)$ es lo suficientemente grande ($|P(q)| \ge q^3 / (32 \log q)$) de modo que la densidad de los primos malos es insignificante.

3. Contribuciones Clave y Resultados

3.1 Incertidumbre Aditiva Fuerte (Teorema 1.1 / Teorema 3.1)

Para cada primo fijo $q$, y para todos los primos $p \equiv 1 \pmod q$, excepto para un número finito de ellos, todo $f \in \mathbb{F}_p^{\mathbb{Z}_q}$ no nulo satisface:
$$|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$$
Esto implica que una función $k$-dispersa tiene un soporte de transformada de al menos $q - k + 1$. Este resultado proporciona una versión no uniforme de la conjetura de Li-Wu, válida cuando se permite que $p$ crezca lo suficiente respecto a $q$.

3.2 Incertidumbre Aproximada (Teorema 1.2 / Teorema 3.6)

Para infinitos primos $q$, y para cualquier vector entero $c$ con $|\text{Supp}(c)| < q$ y norma $\ell_1$ denotada por $W$, el tamaño de soporte esperado de la NTT inversa sobre un primo aleatorio $p \in P(q)$ satisface:
$$\mathbb{E}_p [|\text{Supp}(\hat{c})|] \ge q - 1 - \frac{32(q-1)\log q}{q^2} \log_2 W$$
Este resultado se sostiene en el régimen realista donde $p$ está acotado polinomialmente en $q$.

3.3 Mejora de la Prueba de Identidad (Teorema 1.3 / Teorema 4.3)

Los autores aplican estos principios para construir una prueba de identidad de caja negra modificada para polinomios exponenciales de $k$-dispersión, grado $d$ y altura de coeficiente $w$.

• Modificación: La prueba muestrea el primo $p$ aleatoriamente del intervalo $P(q)$, además de los puntos de evaluación aleatorios estándar.
• Límite de Solidez: Si $P \not\equiv 0$, la probabilidad de aceptación está acotada por:
  $$O\left(\frac{dk^2}{q}\right) + O\left(\frac{1}{q}\right) + O\left(\frac{\log(kw)\log q}{q^2}\right)$$
• Significancia: Si $q = k^C$ con $C > 2$ y $kw$ es polinomialmente acotado, el error de solidez se convierte en $o(1)$ (específicamente, tiende a 0 a medida que $q$ crece). Esto es una mejora directa sobre el límite de Li-Wu de $q^{-1/(k-1)}$, que tiende a 1 en el mismo régimen.

4. Significancia y Reivindicaciones

El artículo afirma que la contribución principal es el establecimiento de principios de incertidumbre aditiva para la NTT, los cuales son necesarios para demostrar la solidez en la prueba de identidad. Los autores declaran explícitamente que el principio de incertidumbre multiplicativo estándar (Donoho–Stark) es insuficiente para este propósito.

La significancia del trabajo radica en:

1. Resolución de una Conjetura: Proporcionar una demostración formal de un fuerte principio de incertidumbre para la NTT en regímenes específicos, validando la intuición detrás de la conjetura de Li y Wu.
2. Mejora Algorítmica: Demostrar que, al aleatorizar la elección del módulo primo $p$, se puede lograr un error de solidez constante para la prueba de identidad de polinomios exponenciales, una tarea que anteriormente se consideraba con altas tasas de error en configuraciones de parámetros prácticas.
3. Puente Teórico: Conectar las propiedades algebraicas de los resultantes y los polinomios ciclotómicos con las propiedades de dispersión de las transformadas sobre cuerpos finitos.

Los autores mantienen la modestia respecto a la naturaleza "no uniforme" de su resultado más fuerte (Teorema 3.1), señalando que se aplica a "todos excepto un número finito de" primos, y dependen del resultado probabilístico (Teorema 3.6) para la aplicación práctica donde $p$ es pequeño. No pretenden resolver el problema general de PIT para todas las expresiones exponenciales, sino específicamente para el caso disperso y condensado definido en su sección de aplicación.