技术摘要：Banach-Butterfly 不变量

1. 问题陈述

本文旨在刻画将布尔函数 $f: \{-1, +1\}^n \to \{-1, +1\}$ 表示为**三值多项式阈值函数（PTF）**的几何难度。具体而言，它试图确定一个函数何时可以写成 $f(x) = \text{sign}(\sum_{S} w_S \chi_S(x))$ 的形式，其中权重 $w_S \in \{-1, 0, +1\}$。

虽然基于 Walsh-Hadamard 变换（WHT）的标准谱分析在通用的 $\ell_2$ 几何（其中蝴蝶分解具有恒定的特征值 $\sqrt{2}$，与函数无关）下运行，但这种普适性无法区分具有不同结构复杂度的函数。本文提出，寻找稀疏三值表示的“难度”并非仅由总影响（total influence）所捕获，而是由 WHT 蝴蝶分解各层中坐标影响的分布所决定。

2. 方法论：Banach-Butterfly 变换（BBT）

核心方法论贡献是Banach-Butterfly 变换（BBT），这是一种谱框架，它为 WHT 蝴蝶分解的每一层配备了影响自适应的 $\ell_p$ 几何。

2.1 自适应指数

对于具有坐标影响 $\text{Inf}_\ell(f)$ 的布尔函数 $f$，BBT 分配一个特定层的指数：
$$p_\ell = 1 + \text{Inf}_\ell(f) \in [1, 2]$$

• 不敏感坐标（$\text{Inf}_\ell \approx 0$）产生 $p_\ell \approx 1$（类 $\ell_1$ 几何）。
• 最大敏感坐标（$\text{Inf}_\ell \approx 1$）产生 $p_\ell \approx 2$（希尔伯特空间几何）。

2.2 算子范数与收缩

利用 Riesz–Thorin 插值和对偶性，本文推导了 $\ell_p$ 中 $2 \times 2$ 蝴蝶矩阵 $A = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ 的精确算子范数：
$$\|A^{-1}\|_{p_\ell \to p_\ell} = 2^{-\text{Inf}_\ell(f) / (1 + \text{Inf}_\ell(f))}$$
由此导出了BBT 收缩不变量 $\mu(f)$ 的定义，即这些逐层收缩的乘积：
$$\mu(f) = \prod_{\ell=1}^n 2^{-\text{Inf}_\ell(f) / (1 + \text{Inf}_\ell(f))}$$
因此，$\log_2 \mu(f) = -\sum_{\ell=1}^n \frac{\text{Inf}_\ell(f)}{1 + \text{Inf}_\ell(f)}$。

2.3 理论性质

• 舒尔凸性（Schur-Convexity）： 本文证明了 $\mu(f)$ 关于影响向量是严格舒尔凸的。这意味着对于固定的总影响 $I(f)$，更“集中”的影响分布（优超）会导致严格更大的 $\mu(f)$。
• 代数性质： 与总影响（傅里叶系数的多项式）不同，$\log_2 \mu(f)$ 是傅里叶系数的有理函数，而 $\mu(f)$ 本身是一个代数数（具有有理指数的 2 的幂）。
• 区分能力： $\mu(f)$ 可以区分具有相同总影响但不同影响分布的函数（例如，在 $n=3$ 时，有 122 对函数共享 $I(f)$ 但具有不同的 $\mu(f)$）。

3. 实验设置与测试平台

作者利用在配套手稿 [1] 中建立的认证有限测试平台，该平台证明了所有 $n \le 4$ 的布尔函数都承认三值 PTF 表示。

• $n=4$ 全集： 分析了所有 65,536 个布尔函数。作者使用混合整数线性规划（MILP）计算精确最小支撑证书，以找到每个函数的最稀疏三值掩码 $w$。
• $n=5$ 采样： 由于空间规模（$2^{32}$）庞大，作者分析了 10,000 个均匀抽取的函数样本，以及 10,000 个从 NPN 规范代表（共 616,126 个类）中抽取的样本。
• 指标： 该研究将 $\mu(f)$、影响熵和逐层抵消指数与表示所需的最小支撑（非零权重的数量）进行相关性分析。

4. 关键结果

4.1 缩放类别

$\mu(f)$ 的理论预测针对规范函数族进行了验证：

• 奇偶校验（Parity）： $\mu \sim 2^{-n/2}$（最小的 $\mu$，最大的收缩）。
• 多数（Majority）： $\mu \sim 2^{-\Theta(\sqrt{n})}$。
• 独裁者（Dictator）： $\mu = 2^{-1/2}$（关于 $n$ 为常数）。
• 部落（Tribes）： $\mu \sim n^{-\Theta(1)}$。
• AND/OR： 当 $n \to \infty$ 时，$\mu \to 1$。

4.2 与最小支撑的相关性

几何不变量 $\mu(f)$ 与合成难度（最小支撑）之间的关系是条件性的，而非普适的：

• 在 $n=4$ 时： 在最大的固定影响层（$I(f) \approx 1.75$）内，$\mu(f)$ 与最小支撑之间存在强烈的正条件相关性（$\rho = +0.571$）。这证实了舒尔凸性的直觉：集中的影响导致更高的 $\mu$ 和更难的表示。
• 在 $n=5$ 时： 这种关系发生逆转。在均匀采样和 NPN 规范采样下，条件相关性变为负值（$\rho \approx -0.38$）。
• 解释： $\mu(f)$ 是一个有效的舒尔凸集中不变量，但不是跨所有 $n$ 的最小支撑的普适单调预测因子。在 $n=5$ 时，影响熵仍然是支撑的定性预测因子，而 $\mu$ 则不是。

4.3 抵消诊断

逐层抵消指数 $\rho$（衡量蝴蝶级联中的破坏性干涉）在 $n=3$ 时显示出与支撑大小的中等相关性（$r=0.42$）。观察到修复算法会增加该指数，表明它们找到了具有较少破坏性干涉的掩码。

5. 意义与主张

本文对其贡献提出了适度且具体的主张：

1. 新不变量： 它引入了 $\mu(f)$ 作为一个比总影响更精细的不变量，能够区分具有相同总影响但几何结构不同的函数。
2. 几何洞察： 它确立了三值表示的难度与 Walsh 基的Banach 几何之间的联系，具体而言是影响自适应范数如何通过蝴蝶分解收缩向量。
3. 实证局限： 本文明确指出 $\mu(f)$ 不是最小支撑的普适预测因子。$n=4$ 和 $n=5$ 之间相关性的逆转表明，谱收缩与合成复杂度之间的联系是微妙的，并且可能取决于给定 $n$ 下支撑大小的具体分布。
4. 实值应用（定性）： 本文引用了配套工作 [2]，其中受该理论启发的实值谱能量代理改进了 LLM 量化。然而，作者澄清，该应用使用的是定性联系（每坐标谱质量），而非布尔舒尔凸性定理的形式化迁移。

6. 未解决问题

作者指出了几个未解决的问题：

• 三值 PTF 的普适性是否扩展到 $n \ge 5$？
• $\mu(f)$ 能否提供支撑大小的可证明上界？
• 对于 $I(f) = O(\log n)$ 的函数，是否存在多项式时间的合成算法？
• $n=4$ 和 $n=5$ 之间 $\mu$-支撑相关性逆转的理论解释是什么？

总之，本文提供了一个严格的几何框架，通过影响自适应范数来分析布尔函数，证明了强大的理论性质（舒尔凸性、代数性质），同时在实证上表明，这些性质并不能转化为跨所有问题规模的简单、普适的表示复杂度预测因子。