技術要約：数論的変換（NTT）における不確定性原理

1. 問題設定と動機

本論文は、指数関数を含む式の**多項式恒等式判定（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$）という2つの素数を用い、$\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 ハイパー逆転可能性による加法的不確定性

第一のアプローチは、複素数における離散フーリエ変換（DFT）に対するTao [Tao05] の戦略を適応させたものである。複素数の設定では、DFT行列は「ハイパー逆転可能（すべての正方部分行列が可逆）」であり、これは強い加法的不確定性 $|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$ を意味する。

著者らは、この性質が一般の有限体では成立しないこと（Zhang [Zha19] によって示されている）を指摘している。しかし、彼らは固定された素数 $q$ に対して、NTT行列のハイパー逆転可能性が、ほとんどすべての（all but finitely many） $p \equiv 1 \pmod q$ に対して成立することを証明した。

• 証明手法: 彼らは多項式の**終結式（resultant）**を利用している。フーリエ行列の任意の正方部分行列に対して、その行列式が原始 $q$ 乗根において非ゼロとなる多項式 $D_{R,C}(z)$ を構成する（複素数の結果より）。もしある部分行列が $\text{mod } p$ で特異になるならば、$p$ は $D_{R,C}(z)$ と円分多項式 $\Phi_q(z)$ の終結式を割り切ることを示す。終結式は非ゼロの整数であるため、有限個の素数しか除数を持たず、これにより「悪い」素数 $p$ が制限される。

2.2 多項式レジームにおける近似的不確定性

上記の加法的不確定性の結果は、$p$ が極めて大きい（およそ $p \approx q^{q^2}$）ことを要求するため、実用的なアプリケーション（$p = q^{O(1)}$ の場合）には不向きである。これに対処するため、著者らは確率的（近似的）不確定性原理を証明している。

• レジーム: 彼らは、$p$ が集合 $P(q) = \{p \le q^4 : p \text{ は素数}, p \equiv 1 \pmod q\}$ から一様にサンプリングされる場合を考える。
• 証明手法: 疎な整数多項式 $f$ を固定し、$f$ がランダムな素数 $p$ に関する原始 $q$ 乗根において消滅する確率を分析する。
  • もし $f$ がそのような根において消滅する場合、$p$ は終結式 $\text{Res}(f, \Phi_q)$ を割り切らなければならない。
  • ポアソンの積公式を用いることで、この終結式の大きさの絶対値を $\|f\|_1^{q-1}$ で抑える。
  • これにより、不確定性原理が成立しなくなる「悪い」素数 $p$ は、高々 $(q-1)\log_2 \|f\|_1$ 個しかないことが示される。
  • ボンビエリ・ヴィノグラードフの定理を援用することで、無限に多くの $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$ について、すべての非ゼロな $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$ に対し、サポートサイズが $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)

著者らは、これらの原理を適用して、$k$-疎な指数多項式（次数 $d$、係数の高さ $w$）のための修正されたブラックボックス恒等式判定を構築する。

• 修正点: 標準的なランダム評価点に加えて、素数 $p$ を区間 $P(q)$ からランダムにサンプリングする。
• 健全性境界: $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）に依拠している。彼らは、すべての指数式に対する一般的なPIT問題を解決したと主張しているのではなく、適用セクションで定義された、疎で凝縮されたケースに特化して取り組んでいる。