A compensated coupling bound for the average sensitivity of polynomial threshold functions

技术摘要：关于多项式阈值函数平均敏感性的补偿耦合界限

问题陈述
本文研究了为多项式阈值函数（PTF）设定平均敏感性（$AS(f)$）上界的问题。PTF 是一个定义在 $\{-1, 1\}^n$ 上的布尔函数 $f: \{-1, 1\}^n \to \{-1, 1\}$，其形式为次数至多为 $d$ 的实多项式 $p$ 的符号。平均敏感性的定义为：
$$AS(f) = \sum_{i=1}^n P\{f(X) \neq f(X^{\oplus i})\}$$
其中 $X$ 在布尔立方体 $\Omega_n$ 上服从均匀分布。虽然 Gotsman–Linial 猜想（即识别精确的对称极大值函数）已被证明是错误的，但寻找紧致的统一上界仍然是布尔函数分析和计算复杂度领域的一个核心课题。OpenAI [1] 此前建立了一个 $8d\sqrt{n}$ 的界限，而作者随后的一篇笔记将该界限精炼为 3.83 的统一系数。

方法论
作者通过改进 OpenAI [1] 最初开发的“加权分级”（weighted-grading）论证来完善该研究。这种方法将平均敏感性的估计简化为一个涉及二项分布随机变量的耦合问题。本文的核心方法论贡献包括：

1. 补偿耦合估计（Compensated Coupling Estimate）： 作者引入了一个经过精炼的概率引理（引理 2），涉及一种“补偿耦合”。该引理通过界定两个具有相同分布且位移有界（$V - U \le a$）的随机变量（$U, V$）之间的二阶矩。通过在耦合势能中引入线性修正，作者消除了早期界限中存在的平方项次数损失。
2. 有限范围估计（Finite-Range Estimation）： 本文推导出了一个考虑特定维度 $n$ 和次数 $d$ 的有限参数估计，而非仅仅依赖于渐近近似。
3. 二项耦合构造（Binomial Coupling Construction）： 作者构造了特定的二项耦合，以展示其松弛化的紧致性。他们表明，在仅利用两个边缘分布、单侧位移约束以及现有的两倍分级比较的情况下，所推导出的系数在渐近意义上是尖锐的。

主要结果
本文为 $n$ 维布尔立方体上的实多项式阈值函数 $f$（次数为 $d$）建立了两个主要的界限：

1. 统一渐近界限（Uniform Asymptotic Bound）：
   $$AS(f) \le \frac{8}{\sqrt{2\pi}} d\sqrt{n} \approx 3.19 d\sqrt{n}$$
   该界限对于所有维度 $n$ 和次数 $d$ 均一致成立。

2. 更强的有限参数界限（Stronger Finite-Parameter Bound）：
   $$AS(f) \le \min\left\{n, \frac{8 d b_n (n + d)}{n + 2d}\right\}$$
   其中 $b_n = E|B_n - n/2|$ 且 $B_n \sim \text{Bin}(n, 1/2)$。该公式明确捕捉了对 $n$ 和 $d$ 的依赖关系，表明当 $d$ 相对于 $n$ 增大时，系数会随之减小。

作者还证明了，如果仅通过对具有二项边缘分布和位移约束的所有耦合进行二阶矩估计，则无法改进系数 $8/\sqrt{2\pi}$，从而为这种特定的松弛方法设定了一个障碍。

主张与意义
本文将自身的贡献定位为对现有加权分级框架中概率步骤的精炼。

• 精炼： 本工作将统一系数从之前的 3.83 改进为 $8/\sqrt{2\pi}$。
• 统一性： 新的界限在所有维度和次数下均有效，包括次数随维度增长的情况。
• 局限性与谦逊态度： 作者明确指出，他们并非断言对于多项式阈值函数本身是达到最优的。他们澄清，用于证明该系数紧致性的构造耦合可能并不源自实际的多项式阈值函数。此外，本文并不声称建立了详尽的历史优先权、独立的同行评审或正式的 Lean 证明。
• 验证： 结果由解析不等式和广泛的计算验证支持（使用精确算术和标准库检查了超过 12,000 个逐点不等式和 8,000 个维度-次数对），而非使用浮点近似。

总而言之，本文通过精炼加权分级论证中的耦合步骤，为 PTF 的平均敏感性提供了一个更紧致且在全域有效的上界，同时仔细界定了其关于所用松弛方法的最优性主张的范围。