🔢 mathematics

Uncertainty Principles for the Number Theoretic Transform

Motivated by polynomial identity testing, this paper establishes strong sparsity tradeoffs for the number-theoretic transform (NTT) and proves a probabilistic uncertainty principle averaged over primes, leading to a black-box identity test for sparse exponential polynomials with vanishing soundness error.

Original authors: Giulio Malavolta, Alon Rosen

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Giulio Malavolta, Alon Rosen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a secret recipe written in a very specific code. This code involves mixing regular ingredients (polynomials) with a special, magical ingredient: an exponential (like $e^x$ ). In the world of computer science, checking if two such recipes are actually the same (or if one is just "zero" or empty) is a huge challenge.

This paper, written by Giulio Malavolta and Alon Rosen, tackles a specific problem: How can we be sure that a complex mathematical expression involving exponentials isn't secretly zero?

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Ghost" Recipe

Imagine you have a machine that takes a number, does some math, and spits out a result. Sometimes, the machine is supposed to output "Zero" no matter what you put in. But sometimes, it's a trick machine that outputs "Zero" only by accident for a few specific numbers, but actually produces a number for others.

In standard math (polynomials), we have a reliable trick to catch these trick machines: just ask the machine to calculate the result for a random number. If it's not a "zero" machine, it will almost certainly give a non-zero answer. This is a famous rule called the Schwartz-Zippel Lemma.

However, when you add exponentials (the magical ingredient) to the mix, this old trick stops working. The rules change, and we don't have a reliable way to say, "This machine is definitely not a zero machine."

2. The Tool: The "Number-Theoretic Transform" (NTT)

To solve this, the authors look at a mathematical tool called the Number-Theoretic Transform (NTT). Think of the NTT as a special translator or mirror.

Input: You give it a list of numbers (a sparse list, meaning most are zero, like a recipe with only a few ingredients).
Output: The translator gives you a new list of numbers (the "transform").

The authors are interested in a rule called the Uncertainty Principle. In the real world, the Uncertainty Principle says you can't know exactly where a particle is and how fast it's moving at the same time. In math, it means you can't have a list that is "short" (sparse) in the original form and "short" in the translated form.

The Paper's Big Discovery:
They proved that for this specific translator (the NTT), if your original list is short, the translated list must be long. You can't hide the information in both places at once.

Analogy: If you write a secret message using only 3 letters, and then translate it into a different language, the translation must use at least a certain number of letters. It cannot stay short in both languages.

3. The Catch: The "Prime Number" Problem

The authors found a problem with their first discovery. The rule works perfectly, but only if the "language" (the mathematical field) is huge—specifically, if the prime number used to define the math is astronomically large (like $q^{q^2}$ ).

In the real world (like in computer programs), we can't use numbers that big; we need to use numbers that are only a few times larger than the input (polynomial size). In these "small" worlds, the strict rule breaks down. Sometimes, a short message can translate into a short message by accident.

4. The Solution: The "Roll of the Dice"

Since they can't guarantee the rule works for every single small number, they changed the strategy. Instead of picking one specific number and hoping for the best, they decided to roll the dice.

They proposed a new testing method:

Pick a random "prime number" (the size of the math world) from a safe range.
Run the test.

They proved that while the rule might fail for some specific prime numbers, it works almost all the time if you pick the prime number randomly.

Analogy: Imagine trying to find a needle in a haystack. If you look in one specific spot, you might miss it. But if you pick a spot at random from the whole haystack, you are almost guaranteed to find it. The authors proved that if you "pick your math world at random," the "short-to-short" trick almost never happens.

5. The Result: A Better "Zero" Detector

By combining this "random prime" strategy with their uncertainty rule, they built a new Identity Test.

Old Method: Had a high chance of being fooled (it might say a non-zero recipe is zero).
New Method: By randomizing the prime number, they reduced the chance of being fooled to a tiny, constant number.

Why does this matter?
The paper mentions this is useful for optimizing computer programs (specifically those involving "tensor programs" and machine learning). These programs often use exponential functions (like "softmax" in AI). If a compiler wants to know if two parts of a program do the same thing, it needs to check if their difference is zero. This new test gives a much more reliable way to do that check without getting tricked by complex math.

Summary

The authors proved a new mathematical law: You can't be short in two different languages at the same time. While this law is strict only in huge worlds, they showed that by randomly choosing the size of the world, you can make the law work almost perfectly for practical, smaller worlds. This allows computers to check complex math formulas much more reliably.

Technical Summary: Uncertainty Principles for the Number Theoretic Transform

1. Problem Statement and Motivation

The paper addresses the problem of Polynomial Identity Testing (PIT) for expressions involving exponentials, a domain recently formalized by Li and Wu [LW26]. In this setting, one must determine if an expression of the form $P(x) = \sum_{j=1}^k f_j(x) \exp(g_j(x)/h_j(x))$ is identically zero.

The core challenge in testing such expressions over finite fields lies in defining a sound evaluation model. Li and Wu proposed a model using two primes, $p$ and $q$ (where $p \equiv 1 \pmod q$ ), interpreting exponentials via the unique subgroup of order $q$ in $\mathbb{F}_p^*$ . However, their analysis of the soundness error (the probability of accepting a non-zero polynomial) yielded a bound of $q^{-1/(k-1)} + O(dk^2/q)$ . In the practical regime where $q = k^{O(1)}$ , this error approaches 1, rendering the test ineffective.

Li and Wu conjectured that this poor soundness is related to a lack of uncertainty principles for the Number-Theoretic Transform (NTT) over finite fields. Specifically, they conjectured that a sparse polynomial with few non-zero coefficients cannot have too many roots in the subgroup $G$ . The authors of this paper aim to prove such uncertainty principles to improve the soundness of identity testing.

2. Methodology and Technical Approach

The authors investigate the relationship between the sparsity of a vector $f$ and the sparsity of its NTT, $\hat{f}$ . They define the support size $|\text{Supp}(f)|$ as the number of non-zero coordinates. The goal is to establish lower bounds on $|\text{Supp}(f)| + |\text{Supp}(\hat{f})|$ .

2.1 Additive Uncertainty via Hyperinvertibility

The first approach adapts the strategy of Tao [Tao05] for the complex Discrete Fourier Transform (DFT). In the complex setting, the DFT matrix is "hyperinvertible" (every square submatrix is invertible), which implies a strong additive uncertainty principle: $|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$ .

The authors note that this property fails for finite fields in general (as shown by Zhang [Zha19]). However, they prove that for a fixed prime $q$ , the hyperinvertibility of the NTT matrix holds for all but finitely many primes $p \equiv 1 \pmod q$ .

Proof Technique: They utilize the resultant of polynomials. For any square submatrix of the Fourier matrix, they construct a polynomial $D_{R,C}(z)$ whose determinant is non-zero at primitive $q$ -th roots of unity (by the complex result). They show that if a submatrix becomes singular modulo $p$ , then $p$ must divide the resultant of $D_{R,C}(z)$ and the cyclotomic polynomial $\Phi_q(z)$ . Since the resultant is a non-zero integer, it has only finitely many prime divisors, limiting the "bad" primes $p$ .

2.2 Approximate Uncertainty for Polynomial Regimes

The additive uncertainty result above requires $p$ to be extremely large (roughly $p \approx q^{q^2}$ ), which is impractical for applications where $p = q^{O(1)}$ . To address this, the authors prove a probabilistic (approximate) uncertainty principle.

Regime: They consider $p$ sampled uniformly from the interval $P(q) = \{p \le q^4 : p \text{ is prime}, p \equiv 1 \pmod q\}$ .
Proof Technique: They fix a sparse integer polynomial $f$ $f$ and analyze the probability that $f$ $f$ vanishes at a primitive $q$ $q$ -th root of unity modulo a random prime $p$ $p$ .
- If $f$ vanishes at such a root, then $p$ must divide the resultant $\text{Res}(f, \Phi_q)$ .
- Using Poisson's product formula, they bound the magnitude of this resultant by $\|f\|_1^{q-1}$ .
- This implies there are at most $(q-1)\log_2 \|f\|_1$ "bad" primes $p$ where the uncertainty principle fails.
- By invoking the Bombieri–Vinogradov theorem, they show that for infinitely many $q$ , the set $P(q)$ is large enough ( $|P(q)| \ge q^3 / (32 \log q)$ ) such that the density of bad primes is negligible.

3. Key Contributions and Results

3.1 Strong Additive Uncertainty (Theorem 1.1 / Theorem 3.1)

For every fixed prime $q$ , and for all but finitely many primes $p \equiv 1 \pmod q$ , every non-zero $f \in \mathbb{F}_p^{\mathbb{Z}_q}$ satisfies:
$|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$
This implies that a $k$ -sparse function has a transform support of at least $q - k + 1$ . This result provides a non-uniform version of the Li-Wu conjecture, valid when $p$ is allowed to grow sufficiently fast with $q$ .

3.2 Approximate Uncertainty (Theorem 1.2 / Theorem 3.6)

For infinitely many primes $q$ , and for any non-zero integer vector $c$ with $|\text{Supp}(c)| < q$ and $\ell_1$ -norm $W$ , the expected support size of the inverse NTT over a random prime $p \in P(q)$ satisfies:
$\mathbb{E}_p [|\text{Supp}(\hat{c})|] \ge q - 1 - \frac{32(q-1)\log q}{q^2} \log_2 W$
This result holds in the realistic regime where $p$ is polynomially bounded in $q$ .

3.3 Improved Identity Testing (Theorem 1.3 / Theorem 4.3)

The authors apply these principles to construct a modified black-box identity test for $k$ -sparse exponential polynomials of degree $d$ and coefficient height $w$ .

Modification: The test samples the prime $p$ randomly from the interval $P(q)$ in addition to the standard random evaluation points.
Soundness Bound: If $P \not\equiv 0$ , the probability of acceptance is bounded by:
$O\left(\frac{dk^2}{q}\right) + O\left(\frac{1}{q}\right) + O\left(\frac{\log(kw)\log q}{q^2}\right)$
Significance: If $q = k^C$ with $C > 2$ and $kw$ is polynomially bounded, the soundness error becomes $o(1)$ (specifically, it approaches 0 as $q$ grows). This is a direct improvement over the Li-Wu bound of $q^{-1/(k-1)}$ , which approaches 1 in the same regime.

4. Significance and Claims

The paper claims that the primary contribution is establishing additive uncertainty principles for the NTT, which are necessary for proving soundness in identity testing. The authors explicitly state that the standard multiplicative uncertainty principle (Donoho–Stark) is insufficient for this purpose.

The significance of the work lies in:

Resolving a Conjecture: Providing a formal proof of a strong uncertainty principle for the NTT in specific regimes, validating the intuition behind Li and Wu's conjecture.
Algorithmic Improvement: Demonstrating that by randomizing the choice of the prime modulus $p$ , one can achieve constant soundness error for identity testing of exponential polynomials, a task previously thought to have high error rates in practical parameter settings.
Theoretical Bridge: Connecting the algebraic properties of resultants and cyclotomic polynomials to the sparsity properties of transforms over finite fields.

The authors remain modest regarding the "non-uniform" nature of their strongest result (Theorem 3.1), noting it applies to "all but finitely many" primes, and rely on the probabilistic result (Theorem 3.6) for the practical application where $p$ is small. They do not claim to solve the general PIT problem for all exponential expressions but specifically for the sparse, condensed case defined in their application section.