傅里叶界把一致数卡在 2^{n/2}
论文研究向量布尔函数 F: F_2^n → F_2^m，在对称密钥密码学中也被称为 S 盒。关注的量是 maxagree(F, deg 1)：在所有仿射映射 L(x) = Mx + b 中取最小，F(x) 与 L(x) 相等的输入 x 的最大个数。等价地，非线性度 nl(F) = 2^n − maxagree(F, deg 1) 衡量 F 与每个仿射映射的距离。
经典路线用 bent 函数和傅里叶分析构造 F：若每个非零投影 F_y(x) = ⟨F(x), y⟩ 都几乎 bent，则 maxagree(F, deg 1) ≤ 2^n/2^m + O(2^{n/2})。该方法能证明的最好界是 A(m,n) = Θ(2^{n−m} + 2^{n/2})，永远不会低于 2^{n/2}。论文表明这不是构造的缺陷，而是方法的天花板：存在 F 具有很大的 maxagree(F, deg 1)，但其傅里叶系数都基本尽可能小，因此任何基于傅里叶系数的论证都无法压到 2^{n/2} 以下。
随机函数很难，但显式构造一直缺失
概率方法表明，当 m ≥ n 时存在 F: F_2^n → F_2^m 满足 maxagree(F, deg 1) ≤ poly(n)；更一般地，maxagree(F, deg d) ≥ M(q,n,d)，即次数至多 d、各变量次数至多 q−1 的 n 元单项式个数。当 m = O_ε(n) 时，随机 F 达到 maxagree(F, deg d) ≤ (1+ε)M(q,n,d)，接近插值下界。
论文填补的空白是构造性的：此前没有已知的显式 F 能达到这一区间。当 m ≥ n 时，傅里叶方法明显次优，通过它能证明的最好上界是 2^{n/2}。论文的贡献是显式构造，而不是新的存在性证明。
一致数等于独立集个数
构造从一个 r-一致超图 H = (V, E) 出发，其中 V = [n]，|E| = m。每条边 e = (i_1, …, i_r) 定义一个单项式，对应的函数 F_H: F_2^n → F_2^m 由 F_H(x)_e = ∏_{j∈[r]} x_{i_j} 给出。论文证明，对任意 1 ≤ d < r，maxagree(F_H, deg d) = |Ind(H)|，即 H 中独立集的个数。
这一等式把多项式逼近问题转化为组合问题：要让 F_H 难逼近，就选一个 n 个顶点、m = O(n) 条边的 r-一致超图，使其独立集尽可能少。该界通过 Macaulay 定理（也称足迹界）得到，它用多项式函数空间的维数来界定多项式方程组的解集大小。
不相交团并已经越过这道屏障
把框架实例化为 H 是 n/k 个完全 r-一致超图 K_k^{(r)} 的不相交并，就得到显式函数。对 d = 1，取 r = 2，则对每个整数 k，m = ((k−1)/2)·n，且 maxagree(F, deg 1) ≤ (k+1)n/k。当 k = O_γ(1) 足够大时，这至多为 (1+γ)n，并且对每个 k ≥ 6 都突破傅里叶界。
对一般次数 d，超团的不相交并给出 m/n = (1/k)·C(k, d+1)（k 任意）以及 maxagree(F, deg d) = O(k n^{d/k})。此前对 m = O(n) 和 d ≥ 2 的最好界是 maxagree(F, deg d) ≤ 2^{−n/2^{d+1}}·2^n，由 Ben-Sasson 和 Kopparty 基于 Gowers 范数类论证给出。新的界对常数 d 甚至绕过了 d = 1 的傅里叶界。
次数 d 的难度由直积引理推出
同一框架可扩展到与 m 元组次数 d 多项式 Q: F_2^n → F_2^m 的一致数，其中 maxagree(F, deg d) 是在所有这样的元组中，满足 F(x) = Q(x) 的 x 的最大个数。对 r-一致超图的不相交并 H = H_1 ⊔ ⋯ ⊔ H_t，论文证明 maxagree(F_H, deg d) ≤ ∏_i |N_{H_i}(q)|，并在 d = r−1 时取等号。
这种直积行为在框架内是精确的，与 Viola 和 Wigderson 有损的一般直积定理形成对比。正是它让构造可扩展：一致数界在各分量间相乘，而输出维数 m 相加，因此 m = O_{γ,d}(n) 就足以对每个固定 γ > 0 和 d ∈ N 达到 maxagree(F, deg d) ≤ (1+γ)n。
构造可推广到所有有限域
所有结果都从 F_2 推广到 F_q。在 F_q 上会出现非多重线性单项式，组合问题变成多重集版本：不再比较边与独立集，而是计数边的多重集与独立集的多重集版本。不相交团并的实例化仍然给出突破傅里叶界的显式函数，其中 |M_{H_clique(k,r),q}| 和 maxagree(F_{H_clique(k,r),q}, deg d) 由关于 k 和 r 的容斥求和给出。
当 q > r 时公式简化：|M_{H_clique(k,r),q}| = C(k+r−1, r)·(n/k)，且对 d < r，maxagree(F_{H_clique(k,r),q}, deg d) ≤ C(k+r−1, r−1)^{n/k}，在 d = r−1 时取等号。
团在 d = 1 最优，在 d ≥ 2 不再最优
对 d = 1，框架归结为找 m 条边、独立集最少的图，Sah、Sawhney、Stoner 和 Zhao 的定理表明常数大小团的不相交并是最优的。对更大的 d，常数大小完全超图的不相交并并非最优。对足够大的固定 d，Turán 超图胜过团构造：|M_{H_Turán(k,r),q}| = λ·(n/k)·C(k+r−1, r)，|N_{H_Turán(k,r)}(q)| ≤ C(k, r)^{n/k}，其中 λ ≤ 2/(1+⌊(r+1)/2⌋) + o(1)。
Turán 超图也不总是最优。对 d = 2 和 m = n，一个临时的 8 顶点 3-一致超图 H* 通过不相交并给出 maxagree = 1^{115n/8}，在该区间胜过作者所知的其他所有构造。论文指出，尚不清楚底层问题的最优极值 r-一致超图族是什么，并在附录中讨论了超图框架的局限。
次数 1 的实际门槛是 k ≥ 6
对判断该构造是否相关的读者来说，关键比较是傅里叶界 2^{n/2} 的下限与新的显式界 (1+γ)n（输出比 m = O_γ(n)）之间的差距。次数 1 的实例化在 k ≥ 6 时就跨过这道下限，此时不相交团并给出 maxagree(F, deg 1) ≤ (k+1)n/k。次数 d 的类比更强：对常数 d，它完全绕过 d = 1 的傅里叶界，而 d = r−1 时的精确直积等号使一致数界可由分量超图预测，而不仅仅是被上界约束。
未决之处是定量的，而非定性的。对 d = 1，由于团最优，框架的极限已被理解；对 d ≥ 2，超图中的最佳选择尚未确定，大固定 d 时 Turán 超图胜出，而 d = 2、m = n 时临时构造 H* 胜出。因此比较不同构造的读者应关注所用的是哪类超图族，因为同一框架会因这一选择给出不同的一致数界。
本文引用的文献
Explicit Nonlinear Functions beyond the Fourier bound
论文首次给出显式构造的向量映射 F: F_2^n → F_2^m，取 m = O_γ(n)，对每个 γ>0 达到 maxagree(F, deg 1) ≤ (1+γ)n，突破经典傅里叶界 Θ(2^{n−m} + 2^{n/2})，并把同样的定量行为扩展到与 m 元组次数 d 多项式的一致数。