Optimal bound for the polynomial Littlewood-Offord problem

技术摘要：多项式 Littlewood–Offord 问题的最优界限

问题陈述
本文研究了多项式 Littlewood–Offord 问题，即寻求寻找一个随机多项式 $F(\xi_1, \dots, \xi_n)$ 消失（或落在一个小球内）的概率的上界，其中 $\xi_i$ 是独立的 Rademacher 随机变量（以 $1/2$ 的概率取 $\pm 1$）。虽然对于线性多项式（$d=1$）的经典情况，Erdős 已给出了 $O(1/\sqrt{n})$ 的界限，但对于固定次数 $d \ge 2$ 的多项式的扩展一直是一个具有挑战性的问题。

此前的研究表明，如果一个 $d$ 次多项式具有许多非零系数，其消失概率呈多项式衰减。具体而言，Meka, O. Nguyen, 和 Vu [20] 证明了一个 $(\log r)^{O(1)} r^{-1/2}$ 的界限，其中 $r$ 代表具有非零系数的离散 $d$ 次单项式的数量。这使得 H. Nguyen 和 Vu 的一个猜想悬而未决，即通过移除对数因子，可以实现最优的 $O(r^{-1/2})$ 界限。

方法论
其证明策略不同于以往依赖于多项式阈值函数和 Gotsman–Linial 猜想的方法。相反，作者利用有理函数来逼近非零多项式的指示函数。该方法的核心包括：

1. 有理函数的总影响（Total Influence）： 本文建立了一个关于形式为 $f = p/q$ 的函数（其中 $p$ 和 $q$ 是次数至多为 $d$ 的实多项式）的总影响的尖锐界限。总影响定义为 $\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）通过 $d \cdot \|f\|_\infty^2$ 限制了平方傅里叶系数的加权和 $\sum \lambda_{|S|} \hat{f}(S)^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$），该界限取决于 $r_\gamma(F)$，即系数绝对值至少为 $\gamma$ 的离散单项式数量。这一结果移除了此前界限中存在的对数多项式因子，解决了 Nguyen–Vu 猜想。

• 有理函数的总影响 (定理 1.6)： 作者证明了对于 $f = p/q$（其中 $\deg(p), \deg(q) \le d$）：
  $$\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)： 本文引入了一个替代参数 $s(F)$，代表 $F$ “鲁棒依赖”的变量数量，并提供了基于 $s(F)$ 的反集中界限。

意义与主张
本文声称提供了多项式 Littlewood–Offord 问题的最优界限，解决了由 H. Nguyen 和 Vu 提出的猜想。其重要性在于：

1. 紧致性： 移除 $(\log r)^{O(1)}$ 因子代表了相对于 Meka, O. Nguyen, 和 Vu 研究成果的显著改进。
2. 方法论的新颖性： 从多项式阈值函数转向有理函数以及对它们傅里叶系数的特定线性代数分析，为反集中性研究提供了新的视角。
3. 应用： 其结果对以下领域有直接影响：
   • 奇偶函数的多项式逼近： 扩展了关于逼近奇偶函数所需次数的已知界限。
   • 大型超图中的边缘统计： 消除了关于诱导特定数量边的 $k$-顶点子集比例界限中的 $o(1)$ 损失。

关于作者身份的说明
摘要和“AI 使用声明”明确指出，证明论证是由 GPT-6 Pro 自主发现的。作者 Alexandr Grebennikov 表示，他并不声称对证明思路拥有所有权，但他对该论证进行了验证、消化，并从头开始进行了重写。本文旨在对这一由 AI 发现的证明进行阐述。