Uncertainty Principles for the Number Theoretic Transform Giulio Malavolta∗
Alon Rosen †
arXiv:2606.08662v1 [math.NT] 7 Jun 2026
Abstract 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 ≡ 1 Z (mod q) every nonzero f ∈ Fp q and its number-theoretic transform fˆ satisfy |Supp(f )| + |Supp(fˆ)| ≥ 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.
1
Introduction
Polynomial identity testing (PIT) asks whether a given algebraic expression is identically zero. For ordinary low-degree polynomials over a field, this problem is well understood: One can evaluate the polynomial at a random point, and the Schwartz–Zippel lemma [Sch80, Zip79, DL77] shows that every nonzero degree-d polynomial vanishes with probability at most d/|S| over a finite test set S. In a recent work [LW26] Li and Wu introduced the analogous problem for expressions that contain exponentials. A typical object has the form P (x) =
k X
fj (x) exp
j=1
gj (x) hj (x)
,
where the fj , gj , hj ∈ Z[x] are polynomials. The identity-testing problem is to decide whether P is identically zero on its domain. This differs from standard PIT in two basic ways: First, the expression is no longer a polynomial, so the Schwartz–Zippel lemma does not apply directly. Second, there is no canonical notion of evaluating exp(·) over a finite field, so even defining a useful black-box testing model requires care. This problem is motivated by recent advances in machine-learning. In optimization compilers for tensor programs, such as Mirage [WCL+ 25] one often needs to test whether two subprograms are ∗ †
Bocconi University, BIDSA. [email protected]. Bocconi University, BIDSA. [email protected].
1
functionally equivalent. For purely algebraic fragments, randomized finite-field testing is already useful. The next natural step is to handle fragments that involve exponentials, since operations such as normalization and softmax introduce this type of structure. Li and Wu [LW26] formalized a finite-field evaluation model for such expressions by using two primes p and q with p ≡ 1 (mod q): Arithmetic inside the exponent is carried out modulo q, arithmetic outside the exponent is carried out modulo p, and exponentials are interpreted using the unique subgroup of order q in F∗p . This gives a mathematically clean black-box model and matches the algebraic structure used by the verifier in Mirage [WCL+ 25]. The central challenge is in proving soundness. The main result of [LW26] shows that, for a sum of k exponential terms of degree d, the acceptance probability on a nonzero polynomial is at most q −1/(k−1) + O(dk 2 /q). In the setting of interest where q = k O(1) , the soundness error is therefore 1 − Θ(log q/k). It is left as an open problem to prove a constant soundness error for the same test, which is conjectured to hold in light of empirical evidence [WCL+ 25]. Li and Wu [LW26] suggested that this conjecture is related to uncertainty principles over finite fields. More specifically, let G ≤ F∗p be the unique subgroup of order q, they define a linear map from polynomials modulo xq − 1 to their evaluations on G. In cryptography, this is known as (the inverse of) the number-theoretic transform (NTT) which, among other things, is routinely used for fast implementations of lattice-related cryptographic schemes [HPS98, LMPR08, LPR13]. The conjecture can be interpreted as a strong uncertainty principle of the NTT and it can be equivalently stated as follows: For sufficiently large q and p, any univariate non-zero polynomial f (z) =
k X
β j z αj ,
j=1
with k ≤ q O(1) distinct non-zero coefficients, has at most O(q) roots in G. A formal version of this conjecture is stated in Conjecture 4.1.
1.1
Our Results
Motivated by the above algorithmic applications, we prove a series of uncertainty principles for the Z NTT. Let f ∈ Fp q and let fˆ be its NTT, with Supp(f ) denote the non-zero coordinates of f . Our first result is a strong uncertainty principle for the NTT for infinitely many p and q. Theorem 1.1 (Additive Uncertainty, Informal). For every fixed prime q, for all but finitely many Z primes p ≡ 1 (mod q), every non-zero f ∈ Fp q satisfies |Supp(f )| + |Supp(fˆ)| ≥ q + 1. A formal version of is given in Theorem 3.1. This implies, as an immediate corollary, a nonuniform version of Conjecture 4.1, in the settings where p is allowed to grow with q. In fact, we obtain a much stronger and essentially optimal bound in these settings. We stress that the well-known Donoho–Stark [DS89, WW21] multiplicative uncertainty principle over finite fields (i.e., where the bound is on the product of the cardinalities of the supports) does not yield any meaningful bound in our context. To bear any implication on the soundness of the identity tester, one needs additive uncertainty principles, such as Theorem 3.1. 2
A limitation of the above result is that it does not offer a good control on the growth of p with 2 respect to q. A quantitative analysis shows that the theorem holds for any p larger than ≈ q q , which is quite far from what is used in practice [WCL+ 25]. In the more realistic settings where p = q O(1) , Theorem 3.1 does not apply. Motivated by this, we prove a weaker approximate uncertainty relation, which also applies to the settings where p is polynomially bounded in q. Such a relation holds for any fixed input vector, but only on average over the random choice of p from the appropriate interval. The following theorem is an informal version of Theorem 3.6. Theorem 1.2 (Approximate Uncertainty, Informal). There exist infinitely many primes q such that, for any non-zero f ∈ ZZq with |Supp(f )| < q, then 32(q − 1) log q E |Supp(fˆ)| ≥ q − 1 − log2 ∥f ∥1 . 4 q2 p≤q While this bound does not have any direct implication on the tester proposed in [LW26], we show how a comparatively simple modification of their test allows us to prove much stronger soundness bounds. In short, if one is willing to additionally randomize the choice of p (sampled from the appropriate interval), then one obtains a test where every nonzero input is accepted with probability at most ≈ dk 2 /q. In particular, once q is moderately larger than dk 2 , the test has constant soundness. Theorem 1.3 (PIT with Exponentials, Informal). There exists a randomized test such that, for all integer-coefficient k-sparse exponential polynomials P ̸≡ 0 of degree at most d and coefficients bounded by w, the test accepts with probability at most 2 dk 1 log(kw) log q O +O +O . q q q2 We refer the reader to Theorem 4.3 for a precise statement. We highlight that, if q = k C with C > 2 and kw is polynomially bounded, then the soundness error is o(1), directly improving over [LW26], where the bound is dominated by the term q −1/(k−1) = 1 − o(1). Besides testing equivalence of program fragments that contain exponentials, this test may be useful for verifying arithmetic circuits with exponentiation gates and may provide a soundness primitive for proof systems built for such circuits.
1.2
Proof Overview
Recall that the number-theoretic transform (NTT) is the finite-field analogue of the discrete Fourier transform. Fix primes q and p with p ≡ 1 (mod q), and let g ∈ F∗p have order q. Then evaluation on the subgroup G = {1, g, g 2 , . . . , g q−1 } defines an Fp -linear isomorphism E : Fp [x]/(xq − 1) 7→ Fqp E(f ) = f (1), f (g), . . . , f (g q−1 ) P j whose inverse F = E −1 is the NTT. Writing f (x) = q−1 j=0 cj x , the evaluation map is represented by the Vandermonde matrix M = (g tj )t,j∈Zq , 3
so uncertainty statements for the NTT naturally translate to statements about sparse polynomials and their evaluations on G. A good strategy in this context [Tao05], is to show hyperinvertibility of M , i.e., that every square submatrix of M must be invertible. A routine calculation shows that this implies the strong (additive) uncertainty principle of the associated Fourier transform. When the co-domain of the map is C, one can show that M is hyperinvertible [Tao05], so we seek a finite-field analogue of this statement. The main difficulty is that such hyperinvertibility does not automatically translate over finite fields, and the direct analogue is in fact false [Zha19]. Fortunately, a recent result of Caragea et al. [CLMP25] shows that, if p is sufficiently large compared to q, then the hyperinvertibility of M holds. We can directly use this fact to establish our first uncertainty principle. In Section 3.1, we also provide a somewhat more direct proof of this fact, using properties of the resultant of polynomials. Yet the above proof is not useful for algorithmic applications, since a conservative bound on 2 the size of p results into p ≈ q q , which is not realistic. To handle the regime where p = q O(1) , we instead prove a weaker probabilistic property, averaging over primes p over a bounded interval. The idea is as follows, fix a nonzero f (z) =
X
cj z j ∈ Z[z]
j∈Zq
with |Supp(f )| < q, then f cannot vanish at a primitive q-th root of unity: Otherwise the cyclotomic polynomial Φq (z) = 1 + z + · · · + z q−1 would divide f , forcing f to be a scalar multiple of Φq , which has full support q. It follows that their resultant Res(f, Φq ) is a nonzero integer. Poisson’s formula for the resultant gives Y |Res(f, Φq )| = |f (ω b )| ≤ ∥f ∥q−1 1 . b∈Z∗q
If f has an order-q root modulo some prime p ≡ 1 (mod q), then f and Φq have a common root modulo p, and hence p | Res(f, Φq ). Thus there are at most (q − 1) log2 ∥f ∥1 such bad primes. To make this useful in the polynomial-size regime, we sample p from the interval P(q) = {p ≤ q 4 : p prime and p ≡ 1
(mod q)}.
We then appeal to the Bombieri–Vinogradov theorem [Bom74, Vin65] to show that there are infinitely many primes q for which q3 |P(q)| ≥ . 32 log q Combining this estimate with the above bound, we obtain our approximate uncertainty principle. This directly suggests a natural one-query zero-tester for polynomials P with exponentiations. Given a polynomial P we sample: • A random admissible prime p ∈ P(q). • A random point v ∈ Fnq for the exponents. • A random point u ∈ Fnp for the coefficients. • A generator g of the order-q subgroup G ≤ F∗p . 4
• A random r ∈ Zq , and set a = g r . We then evaluate the algebraic extension Pp,q,a (u, v) =
k X
−1
fj (u) agj (v)hj (v) ,
j=1
declaring the value undefined if some denominator vanishes, and accept iff the value is either 0 or undefined. The soundness proof is as follows. First, by Schwartz–Zippel and a union bound, we bound the probability that all denominators are nonzero and the exponents αj = gj (v)hj (v)−1 are pairwise distinct. Conditioned on this event, the test evaluates the ordinary polynomial Ha,v (X) =
k X
fj (X)aαj
j=1
at a random point u ∈ Fnp . If Ha,v ̸≡ 0, Schwartz–Zippel gives error at most d/(q + 1). If Ha,v ≡ 0, then some nonzero monomial coefficient vector η = ([X µ ]f1 , . . . , [X µ ]fk ), with ∥η∥1 ≤ kw, satisfies k X
ηj g rαj = 0.
j=1
This is exactly the event that a random coordinate of the evaluation vector of a sparse integer polynomial with ℓ1 -norm at most kw vanishes. The approximate uncertainty principle is precisely a bound on the probability of this event. The bound on the soundness error of the test is then obtained by combining the above estimates.
2
Preliminaries
We write Zq for Z/qZ. If S is finite, x ∼ Unif(S) means that x is sampled uniformly from S. For a vector v = (va )a∈A , write Supp(v) := {a ∈ A : va ̸= 0}. All logarithms are natural unless the base is displayed explicitly.
2.1
Resultants
We recall the elementary properties of the resultant that will be used throughout. If K is a field and f, g ∈ K[z] are nonzero, then Res(f, g) = 0
⇐⇒
f and g have a common root over K.
Equivalently, gcd(f, g) ̸= 1 in K[z]. If g is monic, Poisson’s product formula gives Y |Res(f, g)| = |f (α)|, α:g(α)=0
where the product is taken in an algebraic closure, with multiplicities. 5
(1)
(2)
Lemma 2.1 (Modular Reduction). Let f, g ∈ Z[z], and let p be prime. If the reductions fp , gp ∈ Fp [z] have a common root over Fp , then p | Res(f, g). Proof. Let m = deg f and n = deg g, and form the Sylvester matrix of f and g using these original degrees. Its determinant is Res(f, g). Reducing this matrix modulo p gives the corresponding Sylvester matrix with the same prescribed sizes for fp and gp , possibly with zero leading coefficients if degrees drop. If fp and gp have a common root over Fp , then they are not coprime in Fp [z]. Hence there exist nonzero polynomials A, B ∈ Fp [z], with deg A < n and deg B < m, such that Afp + Bgp = 0. Equivalently, the reduced Sylvester matrix has a nontrivial kernel. Its determinant is therefore zero in Fp , i.e., Res(f, g) ≡ 0 (mod p).
2.2
Schwartz–Zippel
We recall the Schwartz–Zippel lemma [Sch80, Zip79, DL77]. Lemma 2.2 (Schwartz–Zippel). Let F be a field, let H ∈ F[x1 , . . . , xn ] be a nonzero polynomial of total degree at most d, and let S ⊆ F be finite and nonempty. Then Pr
u∼Unif(S n )
2.3
(H(u) = 0) ≤
d . |S|
The Number-Theoretic Transform
Let q be prime, let p be prime with q | p − 1, and choose an element γ ∈ F∗p of exact order q. The order-q subgroup is Gp,q := {1, γ, γ 2 , . . . , γ q−1 } ≤ F∗p . Since Gp,q is the unique subgroup of order q, it is independent of the choice of γ. Define the evaluation map Z E = Ep,q,γ : Fp [x]/(xq − 1) 7→ Fp q , E(f ) := f (γ t ) t∈Zq . (3) If f (x) =
P
c c∈Zq ac x , with exponents represented by 0, . . . , q − 1, then
X
E(f )(t) =
ac γ tc .
c∈Zq
Thus, relative to the monomial basis on the domain and the standard basis on the codomain, E is represented by the Fourier matrix M = Mp,q,γ := (γ tc )t,c∈Zq . Proposition 2.3. The map E in Equation (3) is a well-defined Fp -linear isomorphism.
6
(4)
Proof. Because γ q = 1, evaluation at γ t depends only on the class of a polynomial modulo xq − 1. Moreover, Y xq − 1 = (x − γ t ) t∈Zq
splits over Fp into distinct linear factors. The Chinese remainder theorem gives Y Z Fp [x]/(xq − 1) ∼ Fp [x]/(x − γ t ) ∼ = = Fp q , t∈Zq
and this is exactly the evaluation map E. Definition 2.4 (NTT). The number-theoretic transform (NTT) associated with (p, q, γ) is F := E −1 : Fp q 7→ Fp [x]/(xq − 1). Z
Z
When convenient, we identify F(v) with its coefficient vector in Fp q . Z
The inverse is explicit. For v ∈ Fp q and c ∈ Zq , 1X vt γ −tc (Fv)c = q
(5)
t∈Zq
where q −1 is taken in Fp . This follows from the orthogonality relation ( X q if c = c′ t(c−c′ ) γ = 0 if c ̸= c′ . t∈Z q
3
Uncertainty Principles
P Z For v ∈ Fp q , Supp(v) denotes the nonzero coordinates of v. For f = c∈Zq ac xc ∈ Fp [x]/(xq − 1), Supp(f ) := {c : ac ̸= 0}. Under our identification of Fv with its coefficient vector, Supp(Fv) is well-defined.
3.1
Additive Uncertainty
We prove the first version of the additive uncertainty principle in the following: We show that there are infinitely many pairs of primes p and q that satisfy the stronger (additive) uncertainty principle. Theorem 3.1 (Additive uncertainty). Fix a prime q. For all but finitely many primes p with p ≡ 1 Z (mod q), the following holds. For every element γ ∈ F∗p of order q and every nonzero v ∈ Fp q , |Supp(v)| + |Supp(Fv)| ≥ q + 1. To prove Theorem 3.1 we adopt the strategy from [Tao05], where it is shown that additive uncertainty is equivalent to invertibility of every square submatrix of the Fourier matrix M (see Section 2.3). This statement was shown in the complex settings, but the same proof works for finite-fields. 7
Lemma 3.2 (Hyperinvertibility and Additive Uncertainty). Let q and p be primes with q | p − 1, let γ ∈ F∗p have order q, and let M = (γ tc )t,c∈Zq . The following are equivalent. (i) Every square submatrix of M is nonsingular over Fp . Z
(ii) Every nonzero v ∈ Fp q satisfies |Supp(v)| + |Supp(Fv)| ≥ q + 1. Proof. Assume first that every square submatrix is nonsingular. Let w := Fv, and set S := Supp(w), k := |S|. Write v = M w. Let Z := Zq \ Supp(v) be the zero set of v. Restricting the identity v = M w to rows in Z and columns in S gives 0 = MZ,S wS . If |Z| ≥ k, choose Z ′ ⊆ Z with |Z ′ | = k. Then MZ ′ ,S is a nonsingular k × k matrix, so wS = 0, contradicting the definition of S unless v = 0. Hence |Z| ≤ k − 1, which is equivalent to q − |Supp(v)| ≤ |Supp(F v)| − 1. Conversely, suppose that some k × k submatrix MR,S is singular. Choose 0 ̸= a ∈ FSp with MR,S a = 0, extend it by zero outside S, and set v := M a. Then Fv = a, so |Supp(F v)| ≤ k, while v vanishes on all rows in R, so |Supp(v)| ≤ q − k. Thus |Supp(v)| + |Supp(Fv)| ≤ q, contradicting additive uncertainty. We shall use the following classical theorem of Chebotarev, in the form used in [Tao05]. Theorem 3.3 (Hyperinvertibility of Fourier Matrices). Let q be prime and let ω = e2πi/q . For every 1 ≤ k ≤ q and every pair of k-element subsets R, C ⊆ Zq , det(ω rc )r∈R,c∈C ̸= 0. One may hope to prove a finite-field analogue of Theorem 3.3, unfortunately such a result cannot be true. It was shown by Zhang [Zha19] that in the finite field settings there exists a Fourier matrix with a singular submatrix. To circumvent this obstacle, we show that the finite-field analogue of Theorem 3.3 holds for all but finitely-many primes p. We shall mention that this fact also follows as a consequence of a theorem proven in a very recent work [CLMP25]. Here we choose to give an explicit proof, since it serves as a good warm-up for subsequent arguments. Lemma 3.4 (Finite Field Hyperinvertibility). Fix a prime q. There is a finite set Bq of primes such that, whenever p ≡ 1 (mod q) and p ∈ / Bq , every square submatrix of Mp,q,γ is nonsingular ∗ over Fp for every element γ ∈ Fp of order q. Proof. Fix 1 ≤ k ≤ q and k-element sets R, C ⊆ Zq . Choose integer representatives in {0, . . . , q −1} and define DR,C (z) := det(z rc )r∈R,c∈C ∈ Z[z], 8
where each exponent rc is represented modulo q by an integer in {0, . . . , q − 1}. Let Φq (z) := 1 + z + · · · + z q−1 be the q-th cyclotomic polynomial. For every b ∈ Z∗q , multiplication by b permutes Zq , so bC is again a k-element subset of Zq . By Theorem 3.3, ′
DR,C (ω b ) = det(ω brc )r∈R,c∈C = det(ω rc )r∈R,c′ ∈bC ̸= 0. Thus DR,C and Φq have no common complex root, and Res(DR,C , Φq ) is a nonzero integer. Let ∆q :=
q Y
Y
Res(DR,C , Φq ) ∈ Z \ {0},
k=1 R,C⊆Zq |R|=|C|=k
and let Bq be the set of prime divisors of ∆q . Suppose p ≡ 1 (mod q), p ∈ / Bq , and γ ∈ F∗p has order q. Then Φq (γ) = 0 in Fp . If some minor MR,C were singular, then DR,C (γ) = 0
in Fp .
Hence the reductions of DR,C and Φq modulo p would have the common root γ. By Lemma 2.1, this implies Res(DR,C , Φq ) ≡ 0 (mod p), so p | ∆q , a contradiction. The proof of our main theorem is now straightforward. Proof of Theorem 3.1. For fixed q, take Bq from Lemma 3.4. If p ≡ 1 (mod q) and p ∈ / Bq , the matrix Mp,q,γ is hyperinvertible for every order-q element γ. Lemma 3.2 gives the claimed uncertainty inequality.
3.2
Approximate Uncertainty
The proof above is qualitative because it multiplies all submatrices. We next keep a single resultant at a time and bound the number of primes that can divide it. Lemma 3.5 (Bad Primes). Let q be prime, let F (z) ∈ Z[z], and ω = e2πi/q . Suppose that, for some real B ≥ 1, F (ω b ) ̸= 0 and |F (ω b )| ≤ B for every b ∈ Z∗q . Then the number of primes p ≡ 1 (mod q) for which there exists an element γ ∈ F∗p of order q with F (γ) = 0
in Fp
is at most (q − 1) log2 B. Proof. The hypotheses imply that F and Φq have no common complex root. Hence Res(F, Φq ) ∈ Z \ {0}. If p ≡ 1 (mod q) and F (γ) = 0 for an element γ ∈ F∗p of order q, then also Φq (γ) = 0. Thus the reductions of F and Φq modulo p have a common root. By Lemma 2.1, p | Res(F, Φq ). 9
By Equation (2) (Poisson’s formula), |Res(F, Φq )| =
Y
|F (ω b )|,
b∈Z∗q
and therefore |Res(F, Φq )| ≤ B q−1 . If a nonzero integer N has m distinct prime divisors, then 2m ≤ |N |. Consequently Res(F, Φq ) has at most log2 (B q−1 ) = (q − 1) log2 B distinct prime divisors. Let P(q) := {p ≤ q 4 : p prime and p ≡ 1
(mod q)}.
(6)
We shall use primes q for which q3 . (7) 32 log q We prove an approximate uncertainty principle for a fixed integer sparse vector, but averaged over the random choice of primes p ∈ P(q). To prove the approximate uncertainty principle, all needs to be done is to show that infinitely many such q exist. Here we simply postulate that such q exists, and we refer to Section 3.3 for a proof of this fact. |P(q)| = π(q 4 ; q, 1) ≥
Theorem 3.6 (Approximate Uncertainty). Let q be prime and suppose Equation (7) holds. Let 0 ̸= c ∈ ZZq satisfy X |Supp(c)| < q and ∥c∥1 := |ca | ≤ W a∈Zq
where W ≥ 2. Then 32(q − 1) log q E |Supp(F −1 (c))| ≥ q − 1 − log2 W. p q2 P Proof. Let C(z) := a∈Zq ca z a ∈ Z[z]. We first show that C does not vanish at any primitive q-th root of unity. If C(ω) = 0 for a primitive root ω, then the minimal polynomial Φq of ω over Q divides C in Q[z]. Since deg C ≤ q − 1 = deg Φq , this forces C = λΦq for some λ ∈ Q. But Φq = 1 + z + · · · + z q−1 has support q, whereas 0 ̸= C has support strictly smaller than q. This is impossible. The same argument applies to every primitive root ω b , for b ∈ Z∗q . Moreover for all b ∈ Z∗q , |C(ω b )| ≤
X
|ca | ≤ W.
a
By Lemma 3.5, the number of primes p ≡ 1 (mod q) for which there exists an order-q element h ∈ F∗p with C(h) = 0 in Fp is at most (q − 1) log2 W . Call these primes bad. If p ∈ P(q) is not bad, then for every t ∈ Z∗q , the element γpt has order q, and hence F −1 (c)(t) = Ep,q,γp (c)(t) = C(γpt ) ̸= 0. Thus, for non-bad p, the evaluation vector can vanish only at t = 0, and the zero fraction is at most 1/q. For bad p we use the trivial bound 1. Therefore 1 1 (q − 1) log2 W E {t : Ep,q,γp (c)(t) = 0} ≤ + . p q q |P(q)| Using Equation (7) gives the claimed bound. The desired statement follows by multiplying the zero-fraction inequality by q and subtracting from q. 10
3.3
Bounds on Admissible Primes
For n ≥ 1, let Λ(n) denote the von Mangoldt function. For (a, q) = 1, define X X ψ(x; q, a) := Λ(n), θ(x; q, a) := log p. n≤x n≡a (q)
p≤x p≡a (q)
We use the following standard form of Bombieri–Vinogradov [Bom74, Vin65, Vau]. Theorem 3.7 (Bombieri–Vinogradov). For every A > 0 there are constants B = B(A) and C = C(A) such that, for all x ≥ 2 and all Q ≤ x1/2 (log x)−B , X q≤Q
max max ψ(y; q, a) −
(a,q)=1 2≤y≤x
x y ≤C . φ(q) (log x)A
The next lemma shows that there are infinitely many q with the desired property. Lemma 3.8 (Admissible Primes). There are infinitely many primes q satisfying Equation (7). Proof. First compare ψ and θ. For y ≥ 3, ⌊log2 y⌋
0 ≤ ψ(y; q, 1) − θ(y; q, 1) ≤
X
X
log p
m=2 p≤y 1/m ⌊log2 y⌋
≤ (log y)
X y 1/m , m
m=2
using the elementary bound
4 p≤t log p ≤ t log t. With y = q , this gives, for q ≥ 3,
P
0 ≤ ψ(q 4 ; q, 1) − θ(q 4 ; q, 1) ≤ 2q 2 log q + 4q 4/3 log q (1 + log(4 log q)).
(8)
Indeed, the term m = 2 contributes at most 2q 2 log q, and the remaining terms are bounded by ⌊log2 (q 4 )⌋
4q
4/3
log q
X m=3
1 ≤ 4q 4/3 log q (1 + log(4 log q)). m
Fix A > 2, and let B, C be as in Theorem 3.7. For a large parameter N , set x := (2N )4 ,
Q := x1/2 (log x)−B .
For all sufficiently large N , the interval [N, 2N ] is contained in [1, Q]. Let EN be the set of integers q ∈ [N, 2N ] for which q4 q4 > ψ(q 4 ; q, 1) − . φ(q) 2φ(q) For q ∈ [N, 2N ], the right-hand side is ≫ N 3 . Bombieri–Vinogradov and Markov’s inequality therefore give N |EN | = O . (log N )A 11
By the prime number theorem, the interval [N, 2N ] contains ≫ N/ log N primes. Since A > 2, for all sufficiently large N there is a prime q ∈ [N, 2N ] \ EN . Taking N → ∞ gives infinitely many such primes. For any such prime q, since φ(q) = q − 1, q4 q3 ≥ 2(q − 1) 4
ψ(q 4 ; q, 1) ≥
for q ≥ 2. Combining this with Equation (8), and taking q sufficiently large along the infinite sequence, gives q3 θ(q 4 ; q, 1) ≥ . 8 Finally, θ(q 4 ; q, 1) ≤ π(q 4 ; q, 1) log(q 4 ) = 4π(q 4 ; q, 1) log q, so Equation (7) follows.
3.4
Multiplicative Uncertainty
We refer to the standard Donoho–Stark [DS89, WW21] uncertainty principle as the multiplicative uncertainty principle. For completeness, we recall here the finite-field analogue of Donoho–Stark uncertainty and we refer the reader to [BS22] for a proof. However, we wish to emphasize that this is not going to be useful for our work and we are instead interested in stronger additive uncertainty. Theorem 3.9 (Multiplicative Uncertainty). Let q be prime, let p be prime with q | p − 1, and let Z F be the NTT above. For every nonzero v ∈ Fp q , |Supp(v)| · |Supp(Fv)| ≥ q.
4
Applications to Exponential Polynomial Identity Testing
We now apply the preceding uncertainty principles to the finite-field identity-testing model of Li and Wu [LW26], which we recall in the following. Let P (x) =
k X j=1
gj (x) fj (x) exp hj (x)
(9)
with fj , gj , hj ∈ Z[x1 , . . . , xn ]. We say that P is condensed if each fj and hj is nonzero and gj ht − gt hj ̸≡ 0
for all j ̸= t.
(10)
Thus the rational functions gj /hj are pairwise distinct. We say that P has degree at most d if each fj , gj , hj has total degree at most d. We say that P has height at most w if all integer coefficients appearing in fj , hj , gj ht − gt hj (j ̸= t) (11) have absolute value at most w. We shall assume w ≥ 2.
12
Let p, q be primes with p ≡ 1 (mod q), and let Gp,q ≤ F∗p be the order-q subgroup. For γ ∈ Gp,q , u ∈ Fnp , and v ∈ Fnq , define the algebraic evaluation Pp,q,γ (u, v) :=
k X
−1
fj (u) γ gj (v)hj (v)
∈ Fp ,
(12)
j=1
where the exponent is computed in Fq ∼ = Zq . If some hj (v) is zero in Fq , the value is declared to be ⊥.
4.1
A Strong Descartes Rule over Finite Fields
Li and Wu [LW26] formulate the following finite-field analogue of Descartes’ rule as a sufficient route to improved soundness. Conjecture 4.1 (Strong finite-field Descartes rule). There exist constants ε, δ < 1 such that the following holds. Let p, q be sufficiently large primes with p ≡ 1 (mod q), let γ ∈ F∗p have order q, and let G ≤ F∗p be the subgroup of order q. If k ≤ q δ , if α1 , . . . , αk ∈ Zq are distinct, and if β1 , . . . , βk ∈ Fp , then k X A(z) := βj z αj j=1
has at most εq roots in G, unless all βj are zero. Our additive uncertainty theorem gives a stronger conclusion for fixed q and all but finitely many admissible p. Theorem 4.2 (Nonuniform Strong Descartes Rule). Fix a prime q. For all but finitely many primes p ≡ 1 (mod q), the following holds. Let γ ∈ F∗p have order q, and let G ≤ F∗p be the subgroup of order q. If k X A(z) = βj z αj , j=1
where α1 , . . . , αk ∈ Zq are distinct and β1 , . . . , βk ∈ F∗p , then A has at most k − 1 roots in G. Proof. Choose p so that Theorem 3.1 holds. Equivalently, by Lemma 3.2, the matrix M = Z (γ ta )t,a∈Zq is hyperinvertible. Let S := {α1 , . . . , αk } and define c ∈ Fp q by cαj = βj and ca = 0 for a∈ / S. Then (M c)t = A(γ t ). If A vanished at k or more elements of G, there would be a k-element set R ⊆ Zq such that (M c)t = 0 for every t ∈ R. Hence MR,S cS = 0. The submatrix MR,S is nonsingular, while cS ̸= 0, a contradiction.
13
4.2
A Modified Polynomial Identity Test
Assume q satisfies Equation (7). We describe a modification to the identity tester described in [LW26], where we additionally randomize the choice of the prime p. The following test makes a single algebraic evaluation (see Equation (12)) of a fixed polynomial P . Sample: • p ∼ Unif(P(q)). • v ∼ Unif(Fnq ). • u ∼ Unif(Fnp ). • An element γ ∈ F∗p of order q. • r ∼ Unif(Zq ) and set a := γ r . Accept iff Pp,q,a (u, v) ∈ {0, ⊥}. Theorem 4.3 (Soundness). Let q be a prime satisfying Equation (7). Let P be a condensed ksparse exponential polynomial of degree at most d and height at most w, with w ≥ 2, and suppose q > 2kw. If P ≡ 0, the one-query randomized-p test accepts with probability 1. If P ̸≡ 0, the test accepts with probability at most k kd 2d 2 d 1 32(q − 1) log q + + + + log2 (kw). (13) q q q+1 q q3 Proof. Completeness is immediate: If P ≡ 0, every defined algebraic evaluation is zero, and undefined evaluations are accepted by convention. Assume P ̸≡ 0. Define the good denominator event Eh := {hj (v) ̸= 0 in Fq for all j ∈ [k]}, and the good separation event Eg := {gj (v)ht (v) − gt (v)hj (v) ̸= 0 in Fq for all j ̸= t}. Because q > 2kw ≥ w, every nonzero integer polynomial in Equation (11) remains nonzero after reduction modulo q. By Lemma 2.2 (Schwartz–Zippel) and the union bound, kd 2d k2 Pr ¬(Eh ∩ Eg ) ≤ + (14) q q since deg(gj ht − gt hj ) ≤ 2d. Condition on Eh ∩ Eg and set αj := gj (v)hj (v)−1 ∈ Zq . The αj are pairwise distinct. For fixed p, γ, r, with a = γ r , the algebraic evaluation is the value at u of k X Ha,v (X) := fj (X)aαj ∈ Fp [X1 , . . . , Xn ]. j=1
14
If Ha,v ̸≡ 0, again Lemma 2.2 (Schwartz–Zippel) gives Pr
u∼Unif(Fn p)
d d Ha,v (u) = 0 ≤ ≤ . p q+1
(15)
It remains to bound the probability (over the random choice of p, γ, r) that Hγ r ,v ≡ 0. Since P ̸≡ 0 and is condensed, not all coefficient polynomials fj are zero. Choose a monomial X µ for which η := (η1 , . . . , ηk ) := ([X µ ]f1 , . . . , [X µ ]fk ) ∈ Zk is nonzero. The height bound gives k X
|ηj | ≤ kw.
j=1
Since every sampled p ∈ P(q) satisfies p ≥ q + 1 > 2kw, the vector η remains nonzero modulo p. If Hγ r ,v ≡ 0, then the coefficient of X µ in this polynomial vanishes in Fp : k X
ηj γ rαj = 0.
(16)
j=1
Define c ∈ ZZq by placing ηj at the coordinate αj . Because the αj are distinct, c ̸= 0,
|Supp(c)| ≤ k < q,
∥c∥1 ≤ kw.
Moreover, Ep,q,γ (c)(r) =
k X
ηj γ rαj .
j=1
Therefore Equation (16) is the event Ep,q,γ (c)(r) = 0. Theorem 3.6, applied with W = kw, gives 1 32(q − 1) log q log2 (kw). Pr Hγ r ,v ≡ 0 ≤ Pr Ep,q,γ (c)(r) = 0 ≤ + p,r p,r q q3
(17)
Combining Equation (15), Equation (17), and Equation (14) proves Equation (13).
Acknowledgments We thank ChatGPT for helping with ideas, finding references, sanity-checking the math, and general discussions at any stage of this project. The proofs are all written by a human and the authors verified the correctness and originality of all content, including references. We also thank Jiatu Li and Mengdi Wu for valuable correspondence. G.M. is supported by the European Research Council through an ERC Starting Grant (Grant agreement No. 101077455, ObfusQation) and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC 2092 CASA-390781972. A.R. is supported by European Research Council (ERC) under the EU’s Horizon 2020 research and innovation programme (Grant agreement No. 101019547) and Cariplo CRYPTONOMEX grant. 15
References [Bom74]
Enrico Bombieri. Le grand crible dans la théorie analytique des nombres. 1974. 4, 11
[BS22]
Martino Borello and Patrick Solé. The uncertainty principle over finite fields. Discrete Mathematics, 345(1):112670, 2022. 12
[CLMP25] Andrei Caragea, Dae Gwan Lee, Romanos Malikiosis, and Goetz E Pfander. Principal minors of fourier matrices of square-free order. arXiv preprint arXiv:2505.24326, 2025. 4, 8 [DL77]
Richard A DeMillo and Richard J Lipton. A probabilistic remark on algebraic program testing. Technical report, 1977. 1, 6
[DS89]
David L Donoho and Philip B Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Mathematics, 49(3):906–931, 1989. 2, 12
[HPS98]
Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. Ntru: A ring-based public key cryptosystem. In Algorithmic Number Theory, volume 1423 of Lecture Notes in Computer Science, pages 267–288. Springer, 1998. 2
[LMPR08] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen. Swifft: A modest proposal for fft hashing. In International workshop on fast software encryption, pages 54–72. Springer, 2008. 2 [LPR13]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. A toolkit for ring-lwe cryptography. In Annual international conference on the theory and applications of cryptographic techniques, pages 35–54. Springer, 2013. 2
[LW26]
Jiatu Li and Mengdi Wu. Identity testing for circuits with exponentiation gates. ITCS, 2026. 1, 2, 3, 12, 13, 14
[Sch80]
Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM), 27(4):701–717, 1980. 1, 6
[Tao05]
Terence Tao. An uncertainty principle for cyclic groups of prime order. Mathematical Research Letters, 12(1):121–127, 2005. 4, 7, 8
[Vau]
RC Vaughan. The bombieri–vinogradov theorem. https: // personal. science. psu. edu/ rcv4/ Bombieri. pdf . 11
[Vin65]
AI Vinogradov. The density hypothesis for dirichet l-series. Izv. Akad. Nauk SSSR Ser. Mat, 29, 1965. 4, 11
[WCL+ 25] Mengdi Wu, Xinhao Cheng, Shengyu Liu, Chunan Shi, Jianan Ji, Man Kit Ao, Praveen Velliengiri, Xupeng Miao, Oded Padon, and Zhihao Jia. Mirage: A {Multi-Level} superoptimizer for tensor programs. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25), pages 21–38, 2025. 1, 2, 3 [WW21]
Avi Wigderson and Yuval Wigderson. The uncertainty principle: variations on a theme. Bulletin of the American Mathematical Society, 58(2):225–261, 2021. 2, 12 16
[Zha19]
Guanghui Zhang. On the chebotarëv theorem over finite fields. Finite Fields and Their Applications, 56:97–108, 2019. 4, 8
[Zip79]
Richard Zippel. Probabilistic algorithms for sparse polynomials. In International symposium on symbolic and algebraic manipulation, pages 216–226. Springer, 1979. 1, 6
A
Approximate Hyperinvertibility
In the following, we prove an approximate version of the hyperinvertibility theorem of Fourier matrices. For q prime and 1 ≤ k ≤ q, let Kq,k := {(R, C) : R, C ⊆ Zq , |R| = |C| = k}. For a prime p ≡ 1 (mod q), choose any element γ ∈ F∗p of order q and define Fq,k (p) := Pr det(γ rc )r∈R,c∈C = 0 in Fp .
(18)
(R,C)∼Unif(Kq,k )
This value is independent of the chosen order-q element γ: Replacing γ by γ s with s ∈ Z∗q replaces R by sR, and R is uniform over all k-subsets. Lemma A.1 (Bad Primes for One Submatrix). Fix a prime q, an integer 1 ≤ k ≤ q, and (R, C) ∈ Kq,k . The number of primes p ≡ 1 (mod q) for which there exists an element γ ∈ F∗p of order q such that det(γ rc )r∈R,c∈C = 0 in Fp is at most (q−1)k log2 k. 2 Proof. Define DR,C (z) := det(z rc )r∈R,c∈C ∈ Z[z], again using representatives of rc ∈ Zq in {0, . . . , q − 1}. For b ∈ Z∗q , DR,C (ω b ) = det(ω brc )r∈R,c∈C ̸= 0 by Theorem 3.3. Also DR,C (ω b ) is the determinant of a k × k complex matrix whose entries all have absolute value 1. Hadamard’s inequality gives |DR,C (ω b )| ≤ k k/2 . Apply Lemma 3.5 with B = k k/2 . Next, we obtain an average bound over all submatrices. Lemma A.2 (Averaging over Submatrices). Let q be prime, let 1 ≤ k ≤ q, and let x ≥ 2. For at least half of the primes p ≤ x with p ≡ 1 (mod q), Fq,k (p) ≤
(q − 1)k log2 k, π(x; q, 1)
where π(x; q, 1) := |{p ≤ x : p prime and p ≡ 1 (mod q)}|. 17
Proof. For each admissible prime p, fix one order-q element γp ∈ F∗p . By linearity of expectation, X
Fq,k (p) =
p≤x p≡1 (q)
X
E
(R,C)∼Unif(Kq,k )
1{det(γprc )r∈R,c∈C = 0}.
p≤x p≡1 (q)
log2 k. Hence For each fixed (R, C), Lemma A.1 bounds the inner sum by (q−1)k 2 X
Fq,k (p) ≤
p≤x p≡1 (q)
(q − 1)k log2 k. 2
Markov’s inequality applied to the nonnegative values Fq,k (p) proves the claim. We are now ready to state and prove the main theorem of this section. Theorem A.3 (Approximate Hyperinvertibility). There exist infinitely many primes q such that, for every 1 ≤ k ≤ q, at least half of the primes p ∈ P(q) satisfy k(log q)2 det(γ rc )r∈R,c∈C ̸= 0 in Fp ≥ 1 − 64 , q2 (R,C)∼Unif(Kq,k ) Pr
where γ ∈ F∗p is any element of order q. Proof. Let q be any prime satisfying Equation (7). By Lemma A.2 with x = q 4 , at least half of the primes p ∈ P(q) satisfy Fq,k (p) ≤
(q − 1)k k(q − 1) log2 k ≤ 32 (log q)(log2 k) 4 π(q ; q, 1) q3
using Equation (7). Since k ≤ q and log2 k ≤ 2 log q for all k ≤ q, this is at most 64k(log q)2 /q 2 .
18