Friedgut–Kalai–Naor 定理

一般实值一次多项式可以是很多坐标的加权和，但它往往取许多不同实数值。布尔函数只能取 $\pm 1$，这个离散输出限制迫使“几乎一次”的函数接近一个常量或一个坐标。

结论不仅说函数靠近某个实值线性表达式，还把这个表达式进一步约束成极简单的布尔规则。关键结构来自值域，若取消布尔值条件，结论就不成立。

精确情形先看清机制 ​

若所有高阶系数为零，写 $f=a_0+\sum _i{a}_i{x}_i$。由 $f^2\equiv 1$，其二次项系数 $2a_i{a}_j$ 对 $i\ne j$ 必须为零，一次项系数 $2a_0{a}_i$ 也必须为零。因此至多一个 $a_i$ 非零；结合常数项 $a_0^2+\sum _i{a}_i^2=1$，只剩常量或 $\pm x_i$。

近似情形不能直接把平方误差逐项当成零。证明先令 $\ell =a_0+\sum _i{a}_i{x}_i$，高阶质量正是 $\Vert f-\ell {\Vert }_2^2$，再用超压缩给出的低次高阶矩控制公理库布尔超压缩不等式Boolean hypercontractivity · Bonami-Beckner inequality给出布尔噪声算子从 Lp 到 Lq 收缩所需的精确噪声强度，并说明张量化如何消去维数依赖。把“$\ell$ 大多数时候接近 $\pm 1$”转成“多个显著线性系数不能同时存在”。最后在常数项和各坐标项中选出主导项并作符号判断，得到线性于 $\epsilon$ 的错误界。

与独裁者只差一小块输入 ​

从 $g=x_1$ 出发，只在集合 $A$ 上翻转输出，设均匀测度 $\text{Pr}(A)=\eta$。则

由于 $g$ 完全在一次层，$f$ 的高阶正交投影范数平方至多 $4\eta$。这说明少量局部修改确实产生近一次频谱；FKN 则给反方向的结构保证，虽然不声称最优常数恰为 $4$。

三位多数的高阶质量为 $1/4$，且它与任一个相应独裁者的分歧概率恰为 $1/4$：只有另外两票同时反对该位时改变决定。这是可直接核对的中等误差例子；定理最有力的区间是高阶质量非常小。

实值反例说明值域不可删除 ​

$\ell =(x_1+x_2)/\sqrt{2}$ 的频谱全部在一次层，$\Vert \ell {\Vert }_2=1$，但它取 $-\sqrt{2},0,\sqrt{2}$，不等于任何常量或独裁者。它不满足 $\pm 1$ 值域条件，因此不是 FKN 的反例，反而说明条件的作用。

FKN 为近独裁结构提供定量证书，常用于性质测试与社会选择中的稳定性论证。它与Friedgut junta 定理公理库Friedgut junta 定理Friedgut junta theorem把均匀分布下总影响小的布尔函数近似为只依赖少数固定坐标的函数，并明确坐标数对误差的指数依赖。的假设不同：后者控制总影响并允许依赖多个重要坐标；本页直接控制二阶以上质量，结论收缩到一个坐标。