{"id":"arxiv/2606.08662","url":"https://arxiv.org/abs/2606.08662","tags":["math.NT","cs.CR","cs.DS"],"score":0,"title":"Uncertainty Principles for the Number Theoretic Transform","domain":"math.NT","source":"arxiv","authors":["Giulio Malavolta","Alon Rosen"],"reviews":0,"subject":"math.NT","summary":"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 \\pmod q$ every nonzero $f\\in \\mathbb F_p^{\\mathbb Z_q}$ and its number-theoretic transform $\\hat f$ satisfy \\[ |\\mathrm{Supp}(f)| + |\\mathrm{Supp}(\\hat f)| \\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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-07","reactions":{}}