Optimal bound for the polynomial Littlewood-Offord problem

技術的要約：多項式リトルウッド・オフロード問題における最適境界

問題設定
本論文は、多項式リトルウッド・オフロード問題（polynomial Littlewood–Offord problem）を扱っている。これは、独立なラデマッハー変数 $\xi_i$ （$\pm 1$ を確率 $1/2$ でとる）に対し、ランダムな多項式 $F(\xi_1, \dots, \xi_n)$ が消滅する（あるいは小さな球内に収まる）確率を抑え込むことを目的とするものである。古典的な線形多項式（$d=1$）の場合、Erdős によって $O(1/\sqrt{n})$ という境界が確立されているが、固定された次数 $d \ge 2$ の多項式への拡張は困難な課題であり続けてきた。

先行研究では、次数 $d$ のマルチリニア多項式が多くの非ゼロ係数を持つ場合、消滅確率は多項式的に減少することが示されている。具体的には、Meka, O. Nguyen, および Vu [20] は、 $r$ を非ゼロの係数を持つ次数 $d$ の互いに素な単項式の数として、$(\log r)^{O(1)} r^{-1/2}$ という境界を証明した。これにより、H. Nguyen と Vu による、「対数因子を取り除いて最適な $O(r^{-1/2})$ の境界を達成できる」という予想が未解決のまま残されていた。

手法
証明戦略は、多項式閾値関数やGotsman–Linial予想に依存していた従来のアプローチとは異なる。代わりに、著者は非消滅多項式の指示関数を近似するために有理関数を利用している。手法の核となるのは以下の点である：

1. 有理関数の全影響度（Total Influence）： 本論文は、実多項式 $p, q$ （次数はともに高々 $d$）からなる関数 $f = p/q$ の全影響度の鋭い境界を確立している。全影響度は $\text{Inf}[f] = \sum_{i=1}^n \mathbb{E}[(f(\xi) - f(\xi^{(i)})^2]$ と定義される。
2. 線形代数的枠組み： 影響度の証明（定理 1.6）では、$f$ による点ごとの乗算を、関数 $\{-1, 1\}^n \to \mathbb{R}$ の空間上の線形写像として扱う。フーリエ基底におけるこの写像の行列を分析することで、二乗されたフーリエ係数の和を、特定の劣行列のランクおよび演算子ノルムに関連付けている。
3. 組合せ論的計数： 主要な補題（補題 2.1）は、重み付き二乗フーリエ係数の和 $\sum \lambda_{|S|} \hat{f}(S)^2$ を $d \cdot \|f\|_\infty^2$ によって抑えるものである。これは、分子と分母の多項式の次数制約によって定義される劣行列へと問題を分解し、二重計数の議論を用いることで達成される。
4. 反集中性（Anticoncentration）への接続： 本論文は、有理関数 $g(x) = 1/(1+|F(x)|^2)$ の全影響度と、多項式 $F$ のスモールボール確率を結びつけている。これにより、影響度の境界を多項式の反集中性の境界へと翻訳することを可能にしている。

主要な貢献および結果

• 最適な反集中境界 (定理 1.1 & 1.2)： 本論文は、非ゼロの係数を持つ $r$ 個の互いに素な次数 $d$ の単項式を含む次数 $d$ のマルチリニア多項式 $F$ に対し、消滅確率が次を満たすことを証明している：
  $$P[F(\xi_1, \dots, \xi_n) = 0] \le C 2^d \sqrt{d} \cdot r^{-1/2}$$
  より一般的には、スモールボール反集中（$|F| \le \gamma$）において、境界は係数の絶対値が少なくとも $\gamma$ である互いに素な単項式の数 $r_\gamma(F)$ に依存する。この結果は、従来の境界にあった多項式対数因子を取り除き、Nguyen–Vu予想を解決した。

• 有理関数の全影響度 (定理 1.6)： 著者らは、$\deg(p), \deg(q) \le d$ である $f = p/q$ について、以下を証明した：
  $$\text{Inf}[f] \le \left(4\sqrt{2\pi} + O(1/n)\right) d \sqrt{n} \|f\|_\infty^2$$
  これは、Gotsman–Linial予想の文脈から導かれた従来の境界を改善するものである。

• 非ゼロ指示関数に関する予想の解決 (定理 1.7)： 補言として、本論文は Kothariら [16] によって提案された Gotsman–Linial予想の弱いバージョンを証明し、実多項式 $p$ に対して以下を確立している：
  $$\text{Inf}[1_{p \neq 0}] \le \left(\sqrt{2\pi} + O(1/n)\right) \deg(p) \sqrt{n}$$
  この境界は、定数倍を除いてシャープであることが示されている。

• ロバストな依存パラメータ (定理 1.4)： 本論文は、$F$ が「ロバストに依存する」変数の数を示す代替パラメータ $s(F)$ を導入し、$s(F)$ による反集中界を提供している。

意義および主張
本論文は、多項式リトルウッド・オフロード問題に対する最適な境界を提供し、H. Nguyen と Vu による予想を解決したと主張している。その意義は以下の点にある：

1. タイトさ（Tightness）： $(\log r)^{O(1)}$ という因子を取り除いたことは、Meka, O. Nguyen, および Vu による最先端の研究に対し、有意な改善を意味する。
2. 手法の新規性： 多項式閾値関数から有理関数への転換、およびそれらのフーリエ係数の線形代数的な分析は、反集中性に対する新しい視点を提供する。
3. 応用： これらの結果は、以下の分野に直接的な影響を与える：
   • パリティ関数の多項式近似： パリティを近似するために必要な次数に関する既知の境界の拡張。
   • 巨大ハイパーグラフにおけるエッジ統計： $k$ 個の頂点の部分集合が特定の数のエッジを誘導する割合に関する境界における $o(1)$ の損失の除去。

著者に関する注記
アブストラクトおよび「AI使用に関する声明」には、証明の議論が GPT-6 Pro によって自律的に発見されたことが明記されている。著者である Alexandr Grebennikov は、証明のアイデアに対する権利を主張するものではなく、自身は議論を検証、咀嚼し、ゼロから書き直したものであると述べている。本論文は、このAIによって発見された証明の解説として機能するものである。