技术摘要：数论变换的测不准原理

1. 问题陈述与动机

本文研究了涉及指数函数的多项式恒等性测试（Polynomial Identity Testing, PIT）问题，该领域最近由 Li 和 Wu [LW26] 正式化。在此设定中，必须确定形如 $P(x) = \sum_{j=1}^k f_j(x) \exp(g_j(x)/h_j(x))$ 的表达式是否恒等于零。

在有限域上测试此类表达式的核心挑战在于定义一个可靠的评估模型。Li 和 Wu 提出了一个使用两个素数 $p$ 和 $q$（其中 $p \equiv 1 \pmod q$）的模型，通过 $\mathbb{F}_p^*$ 中唯一的 $q$ 阶子群来解释指数函数。然而，他们对健全性误差（即接受非零多项式的概率）的分析得出的界限为 $q^{-1/(k-1)} + O(dk^2/q)$。在 $q = k^{O(1)}$ 的实际情形下，该误差趋于 1，使得测试失效。

Li 和 Wu 推测，这种较差的健全性源于数论变换（NTT）在有限域上缺乏测不准原理。具体而言，他们推测一个具有少量非零系数的稀疏多项式在子群 $G$ 中不能拥有过多的根。本文作者旨在证明此类测不准原理，以提高恒等性测试的健全性。

2. 方法论与技术路径

作者研究了向量 $f$ 的稀疏度与其 NTT $\hat{f}$ 的稀疏度之间的关系。他们将支持集大小 $|\text{Supp}(f)|$ 定义为非零坐标的数量。目标是建立 $|\text{Supp}(f)| + |\text{Supp}(\hat{f})|$ 的下界。

2.1 通过超可逆性实现的加法测不准性

第一种方法借鉴了 Tao [Tao05] 对复数离散傅里叶变换（DFT）的研究策略。在复数设定下，DFT 矩阵是“超可逆的”（每一个方子矩阵都是可逆的），这意味着一个强的加法测不准原理：$|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$。

作者指出，这一性质在一般情况下对于有限域并不成立（如 Zhang [Zha19] 所证）。然而，他们证明了对于固定的素数 $q$，NTT 矩阵的超可逆性对于所有除有限个之外的满足 $p \equiv 1 \pmod q$ 的素数 $p$ 均成立。

• 证明技术： 他们利用了多项式的结式（resultant）。对于傅里叶矩阵的任何方子矩阵，他们构造了一个多项式 $D_{R,C}(z)$，其行列式在原根处非零（基于复数结论）。他们表明，如果一个子矩阵在模 $p$ 下变为奇异，那么 $p$ 必须整除 $D_{R,C}(z)$ 与分圆多项式 $\Phi_q(z)$ 的结式。由于该结式是一个非零整数，它只有有限个素因数，从而限制了“坏”素数 $p$ 的数量。

2.2 多项式情形下的近似测不准性

上述加法测不准性结果要求 $p$ 非常大（大约 $p \approx q^{q^2}$），这在应用中是不切实际的，因为通常 $p = q^{O(1)}$。为了解决这个问题，作者证明了一个概率性的（近似）测不准原理。

• 情形： 他们考虑从区间 $P(q) = \{p \le q^4 : p \text{ 是素数}, p \equiv 1 \pmod q\}$ 中均匀采样 $p$。
• 证明技术： 他们固定一个稀疏整数多项式 $f$，并分析 $f$ 在随机素数 $p$ 下于一个原根处消失的概率。
  • 如果 $f$ 在此类根处消失，则 $p$ 必须整除 $\text{Res}(f, \Phi_q)$。
  • 利用 Poisson 乘积公式，他们将该结式的量级限制在 $\|f\|_1^{q-1}$ 以内。
  • 这意味着只有至多 $(q-1)\log_2 \|f\|_1$ 个“坏”素数 $p$ 会导致测不准原理失效。
  • 通过调用 Bombieri–Vinogradov 定理，他们证明了对于无穷多个 $q$，集合 $P(q)$ 足够大（$|P(q)| \ge q^3 / (32 \log q)$），使得坏素数的密度可以忽略不计。

3. 核心贡献与结果

3.1 强加法测不准性 (Theorem 1.1 / Theorem 3.1)

对于每个固定的素数 $q$，以及对于所有除有限个之外的满足 $p \equiv 1 \pmod q$ 的素数 $p$，每个非零 $f \in \mathbb{F}_p^{\mathbb{Z}_q}$ 满足：
$$|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$$
这表明一个 $k$-稀疏函数其变换支持集至少为 $q - k + 1$。该结果提供了一个非均匀版本的 Li-Wu 猜想，在允许 $p$ 随 $q$ 足够快增长时有效。

3.2 近似测不准性 (Theorem 1.2 / Theorem 3.6)

对于无穷多个素数 $q$，以及对于任何满足 $|\text{Supp}(c)| < q$ 且 $\ell_1$ 范数为 $W$ 的非零整数向量 $c$，在随机素数 $p \in P(q)$ 下，逆 NTT 的期望支持集大小满足：
$$\mathbb{E}_p [|\text{Supp}(\hat{c})|] \ge q - 1 - \frac{32(q-1)\log q}{q^2} \log_2 W$$
该结果在 $p$ 关于 $q$ 多项式有界的现实情形下成立。

3.3 改进的恒等性测试 (Theorem 1.3 / Theorem 4.3)

作者利用这些原理构建了一个改进的黑盒恒等性测试，用于测试度数为 $d$、系数高度为 $w$ 的 $k$-稀疏指数多项式。

• 修改： 该测试除了标准的随机评估点外，还会从区间 $P(q)$ 中随机采样素数 $p$。
• 健全性界限： 若 $P \not\equiv 0$，则接受概率被以下项控制：
  $$O\left(\frac{dk^2}{q}\right) + O\left(\frac{1}{q}\right) + O\left(\frac{\log(kw)\log q}{q^2}\right)$$
• 意义： 如果 $q = k^C$ 且 $C > 2$ 且 $kw$是多项式有界的，则健全性误差变为$o(1)$（具体而言，当$q$ 增大时趋于 0）。这直接改进了 Li-Wu 的界限 $q^{-1/(k-1)}$，后者在相同的参数设置下趋于 1。

4. 意义与主张

本文声称其主要贡献在于建立了 NTT 的加法测不准原理，这是证明恒等性测试健全性所必需的。作者明确指出，标准的乘法测不准原理（Donoho–Stark）不足以实现此目的。

这项工作的意义在于：

1. 解决猜想： 为 NTT 的强测不准原理提供了形式化证明，验证了 Li 和 Wu 猜想背后的直觉。
2. 算法改进： 证明了通过随机化选择素数模数 $p$，可以实现指数多项式的恒等性测试具有常数级健全误差，而此前认为在实际参数设置下该任务具有高误差率。
3. 理论桥梁： 将结式和分圆多项式的代数性质与有限域上变换的稀疏性质联系起来。

作者对其最强结果（Theorem 3.1）的“非均匀性”保持谦逊，指出其适用于“除有限个之外的所有”素数，并依赖于概率性结果（Theorem 3.6）来处理 $p$ 较小时的实际应用。他们并未声称解决了所有指数表达式的通用 PIT 问题，而是专门针对其应用部分定义的稀疏、紧凑情形。