布尔超压缩不等式

高阶范数对罕见的大峰值更敏感。噪声平均削弱这些尖峰，使平滑后的高阶范数可由原函数较温和的低阶范数控制。普通同阶收缩只说平均不会增加范数，这里则跨越了两个不同阶数。

为什么一位足以控制很多位 ​

一位上的函数写为 $a+bx$，噪声后变成 $a+\rho bx$。定理先证明这个二点空间上的范数不等式，再利用坐标独立性与混合范数不等式逐坐标张量化。每加入一位都保持同一对 $p,q$ 和同一 $\rho$，所以不会累积一个依赖 $n$ 的常数。

必要阈值也能从一位看出。取 $a=1,b=t$ 且 $t$ 很小，展开得 $\Vert 1+tX{\Vert }_r=1+(r-1)t^2/2+O(t^4)$。若收缩对任意小 $t$ 成立，就必须有 $(q-1){\rho }^2\le p-1$。

一次可以完整算完的 2 到 4 检验 ​

取 $f(x)=1+x$，$p=2,q=4$，临界 $\rho =1/\sqrt{3}$。输入范数平方为 $\mathbb{E}(1+X{)}^2=2$。输出四次矩为

于是 $\Vert T_{\rho }f{\Vert }_4=(28/9{)}^{1/4}\approx 1.328$，确实小于 $\Vert f{\Vert }_2=\sqrt{2}\approx 1.414$。若不加噪声，$\Vert f{\Vert }_4=8^{1/4}\approx 1.682$，收缩不等式就失败。

低次数多项式的四阶矩 ​

若 $f$ 的 Fourier 次数至多 $d$，写 $f=T_{1/\sqrt{3}}g$，即令 $\hat{g}(S)=3^{|S|/2}\hat{f}(S)$。超压缩与 Parseval 给

这说明低次多项式的尾部不能在固定二阶质量下无限尖锐；代价依赖次数，而不是输入变量总数。对高次数函数，$9^d$ 很大，结论可能数值上较松。

混合 bit 与 Gaussian 时的矩界 ​

低次数的四阶矩界还适用于独立坐标 $Z_i$，只要每个坐标满足 $\mathbb{E}{Z}_i=\mathbb{E}{Z}_i^3=0$、$\mathbb{E}{Z}_i^2=1$、$\mathbb{E}{Z}_i^4\le 3$。均匀 bit 和标准 Gaussian 都满足这些条件，因此可在同一个多线性多项式中混用。

这个推广可直接归纳验证。写 $Q=A+Z_{i}B$，先对 $Z_i$ 平均：

再用 $L^2$ 三角不等式，得到 $\Vert Q{\Vert }_4^2\le \Vert A{\Vert }_4^2+3\Vert B{\Vert }_4^2$。逐坐标归纳后，若 $Q=\sum _S{a}_S\prod _{i\in S}{Z}_i$ 的次数至多 $d$，则

最后一步只用独立、中心化与单位二阶矩。平方后即得 $\mathbb{E}{Q}^4\le 9^d(\mathbb{E}{Q}^2{)}^2$，补齐逐坐标替换时所需的混合输入版本。

KKL 定理公理库KKL 影响定理KKL theorem在均匀立方体上，以方差和维数约束最大坐标影响，并用 tribes 展示对数因子的必要尺度。与Friedgut junta 定理公理库Friedgut junta 定理Friedgut junta theorem把均匀分布下总影响小的布尔函数近似为只依赖少数固定坐标的函数，并明确坐标数对误差的指数依赖。把超压缩用于离散导数，限制许多微弱坐标在低阶频谱中共同积累的质量。导数的低阶范数由其非零概率决定，超压缩因而把坐标影响转成可加的频谱质量界。

本页的常数适用于均匀、独立的 bit。偏置乘积分布有相应版本，但常数会随偏置变化；相关输入则更不能直接照搬二点张量化证明。