布尔函数的多项式次数

形式陈述

每个布尔函数 $f:\{0,1\}^n\to\mathbb R$ 都存在唯一实 multilinear 多项式

p_f(x)=\sum_{S\subseteq[n]}a_S\prod_{i\in S}x_i

满足对每个 $x\in\{0,1\}^n$ 都有 $p_f(x)=f(x)$ 。Multilinear 表示中每个变量次数至多 $1$ ；这是因为在 Boolean cube 上 $x_i^k=x_i$ 对所有 $k\ge1$ ，高次幂可约去而不改变函数值。

$f$ 的精确多项式次数定义为

\deg(f)=\max\{|S|:a_S\ne0\}.

常值函数次数为 $0$ 。次数计算的是最高项涉及多少个不同变量，不是总单项式数、系数大小或求值时间。

本页系数位于实数多项式环。换到有限域会改变加法、系数消去和次数；必须把域写进结论，不能只因输入仍为 $0/1$ 就认为表示相同。

对 $T\subseteq[n]$ ，记 $1_T$ 为恰在 $T$ 上取 $1$ 的输入。系数可由 Boolean lattice 上的 Möbius 反演显式给出：

a_S=\sum_{T\subseteq S} (-1)^{|S|-|T|}f(1_T).

代回输入 $1_U$ 时，只有 $S\subseteq U$ 的单项式为 $1$ ，于是

p_f(1_U)=\sum_{S\subseteq U}a_S=f(1_U).

每个 Boolean 输入都唯一写成某个 $1_U$ ，所以构造在整个 cube 上与 $f$ 一致。这不是从有限样本拟合的近似，而是 $2^n$ 个点上的精确插值。

设 multilinear 多项式 $q$ 在所有 Boolean 输入上取 $0$ 。写成

q(x_1,\ldots,x_n) =q_0(x_1,\ldots,x_{n-1}) +x_nq_1(x_1,\ldots,x_{n-1}).

令 $x_n=0$ ，得 $q_0$ 在 $(n-1)$ 维 cube 上恒零；令 $x_n=1$ ，得 $q_0+q_1$ 恒零，所以 $q_1$ 也恒零。由维数归纳， $q_0,q_1$ 的全部系数为零。故两个表示之差只能是零多项式，multilinear 表示唯一。

若不要求 multilinear，唯一性会失败： $x_i^2-x_i$ 在 cube 上恒为零，可以任意加到表示中并提高形式次数。Exact degree 必须先在这些恒零关系下约化，不能从随手写出的公式直接读最高幂。

直觉

Boolean cube 上的 multilinear 多项式像一张代数坐标表：每个集合 $S$ 对应“这些变量同时出现”的交互项，Möbius 反演从函数在所有子集点上的取值逐层剥出该交互的净贡献。最高非零集合大小，便记录精确表达函数时无法消掉的最高阶联合依赖。

Multilinear 限制也把无意义的形式次数清理掉。因为 $0/1$ 输入满足 $x_i^2=x_i$ ，同一变量反复相乘并没有增加新的行为；真正增加次数的是必须让更多不同变量共同参与一个单项式。

例子与边界

多数函数 $\operatorname{Maj}_3$ 在至少两个输入 bit 为 $1$ 时输出 $1$ 。其唯一 multilinear 表示为

p(x)=x_1x_2+x_1x_3+x_2x_3-2x_1x_2x_3.

重量为 $0$ 或 $1$ 时所有二次乘积为 $0$ ，输出 $0$ ；重量为 $2$ 时恰一个二次项为 $1$ 、三次项为 $0$ ，输出 $1$ ；重量为 $3$ 时三个二次项总和为 $3$ ，减去 $2$ 后仍为 $1$ 。

三次项系数非零，因此 $\deg(\operatorname{Maj}_3)=3$ 。公式中虽然主要由“两两同时为 1”表达多数语义，仍需要三次修正项消除全 1 输入的重复计数；直觉上的“看两个就够”不能替代唯一表示的系数检查。

多项式次数不是电路深度。一个高次单项式可由平衡 AND 树以对数深度计算；一个低次多项式也可能含大量单项式，显式求值并不便宜。两种度量分别记录代数相互作用阶数与门级并行层数。

在 $\mathbb F_2$ 上，parity 是一次线性多项式 $x_1+\cdots+x_n$ ；在实 $0/1$ 表示中，其唯一 multilinear 多项式包含次数 $n$ 的项。引用 parity 次数时若不标域，会得到相反的复杂度图像。

偏函数只要求在 promise 集 $S$ 上匹配，表示通常不再唯一：不同多项式可以在 $S$ 上相同、在 cube 其余点不同。对 partial function 定义 exact degree 时应在所有匹配多项式中取最低次数，而不能直接沿用 total function 的唯一性句子。

推论与应用

Exact degree 为确定性查询复杂度提供直接下界：深度 $T$ 的决策树只能生成次数至多 $T$ 的接受多项式，因此任何精确表示中不可消去的高次项都会迫使相应数量的查询。允许错误后，角色由精确次数转交给近似次数，证明对象从“唯一表示是什么”变为“所有低次近似为何失败”。

这项度量也常与 sensitivity、certificate complexity 等布尔查询参数比较。它揭示代数交互阶数，却不计算单项式数量、系数尺度或电路求值成本；跨模型应用时，应先说明所需的是次数障碍，而不是把它当作完整表示复杂度。

参考资料

Noam Nisan and Mario Szegedy, “On the Degree of Boolean Functions as Real Polynomials,” Computational Complexity 4, 1994, pp. 301–313.
Ryan O'Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014, Chapter 1.
Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012, Chapter 14.