布尔函数的多项式次数

Multilinear 表示 ​

每个布尔函数 $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\ge 1$，高次幂可约去而不改变函数值。

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

$$\mathrm{deg}(f)=max\{|S|:a_S\ne 0\}.$$

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

本页系数位于实数多项式环公理库多项式环Polynomial ring系数来自给定环、以形式不定元构造的多项式集合。。换到有限域会改变加法、系数消去和次数；必须把域写进结论，不能只因输入仍为 $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,\dots ,x_n)=q_0(x_1,\dots ,x_{n-1})+x_n{q}_1(x_1,\dots ,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 必须先在这些恒零关系下约化，不能从随手写出的公式直接读最高幂。

三变量多数函数 ​

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

$$p(x)=x_1{x}_2+x_1{x}_3+x_2{x}_3-2x_1{x}_2{x}_3.$$

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

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

与表示复杂度的边界 ​

多项式次数不是电路公理库布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。深度。一个高次单项式可由平衡 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 的唯一性句子。

参考资料

• 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.