Uncertainty Principles for the Number Theoretic Transform

Motivated by polynomial identity testing with exponentials (Li and Wu, ITCS’26), we study uncertainty principles for the number-theoretic transform (NTT). We show that the NTT satisfies strong sparsity tradeoffs: For every fixed prime $q$ and for all but finitely many primes $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}q)$ every nonzero $f\in {\mathbb{F}}_p^{{\mathbb{Z}}_q}$ and its number-theoretic transform $\widehat{f}$ satisfy $$\mathrm{\mid }\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}(f)\mathrm{\mid }+\mathrm{\mid }\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}(\widehat{f})\mathrm{\mid }\ge q+1.$$ Thus, a $k$-sparse function has transform support at least $q-k+1$. As our main technical contribution, we prove a probabilistic version of the above uncertainty principle, averaged over primes $p$, in the regime $p=q^{O(1)}$. As an application, we obtain a black-box identity test for $k$-sparse exponential polynomials of degree at most $d$ with vanishing soundness error, for $q$ moderately larger than $k$.