Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates uncertainty principles related to the number-theoretic transform (NTT) in the context of polynomial identity testing, revealing that the NTT exhibits strong sparsity tradeoffs. Specifically, it establishes that for a fixed prime \( q \), any nonzero function \( f \) and its transform \( \hat{f} \) must satisfy a lower bound on their supports, indicating that a \( k \)-sparse function has a transform support of at least \( q-k+1 \). The authors further extend this result by proving a probabilistic version of the uncertainty principle, which leads to a novel black-box identity test for \( k \)-sparse exponential polynomials with vanishing soundness error.
The NTT reveals a surprising tradeoff: a \( k \)-sparse function guarantees a transform support that grows linearly with the prime modulus, fundamentally enhancing polynomial identity testing.
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 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$.