多线性扩展 (Multilinear Extension, MLE) 在 点值表示 与 系数表示 下的运算方法，涵盖了在特定点的求值、加法运算与乘法运算等核心内容。通过形式化推导与公式化描述，展示在不同表示法中实现高效计算，特别是在布尔超立方体 ${0,1}^v$ 上的逐点运算方式。该框架为 multivariate sumcheck 协议 及其在零知识证明（zkSNARKs）中的应用提供了坚实的数学基础与算法支持。

1. 多项式点值表示在特定点的求值方法

在点值表示 (evaluation form) 下，一个多线性扩展 $\tilde{f}:\mathbb{F}^n \to \mathbb{F}$ 由其在布尔超立方体 ${0,1}^n$ 上的所有取值所确定。通过多线性性，可以在不显式回到系数表示的情况下，对 $\tilde{f}$ 在任意点 $r \in \mathbb{F}$ 上进行求值。这一方法依赖于递归插值公式，将高维函数的约束逐步降维。

设 $\tilde{f}$ 在点值表示下的向量为

$$ E = \big(\tilde{f}(x_1, \ldots, xn)\big){(x_1, \ldots, x_n) \in {0,1}^n}. $$

若要求 $\tilde{f}(r, x_2, \ldots, x_n)$，则利用多线性性有

$$ \tilde{f}(r, x_2, \ldots, x_n) = (1-r)\,\tilde{f}(0, x_2, \ldots, x_n) + r\,\tilde{f}(1, x_2, \ldots, x_n). $$

对应的算法操作为

$$ E'[i] \;=\; E[i] + r \cdot \big(E[i+2^{v-1}] - E[i]\big), \quad i=0,1,\ldots,2^{v-1}-1. $$

其中，$E'$ 表示在 $x_1=r$ 后得到的 $(n-1)$ 变量点值向量。其计算与空间复杂度均为 $O(2^v)$。

2. 多项式系数表示在特定点的求值方法

在系数表示 (coefficient form) 下，一个多线性扩展 $\tilde{f}$ 可由布尔超立方体上函数 $f:{0,1}^n \to \mathbb{F}$ 与对应的Lagrange基函数展开而得。其优势在于可以直接代入任意点 $r \in \mathbb{F}^n$ 来获得求值结果，而不需要依赖递归插值。

令 $\tilde{f}$ 的系数表示为

$$ \tilde{f}(x_1, \ldots, xn) = \sum{w \in {0,1}^n} f(w)\, \chi_w(x_1, \ldots, x_n), $$

其中

$$ \chi_w(x_1,\ldots,xn) = \prod{i=1}^n \big((1-w_i)(1-x_i) + w_i x_i\big) $$

是 Lagrange 基函数。

在特定点 $r=(r_1,\ldots,r_n) \in \mathbb{F}^n$ 的求值公式为

$$ \tilde{f}(r) = \sum_{w \in {0,1}^n} f(w)\, \chi_w(r). $$

这对应了从系数表示直接代入点 $r$ 的操作。

3. 多元多项式乘法运算

在多变量多项式系统中，MLE × MLE 操作广泛用于基于multivariate sumcheck的 zkSNARK协议中。设 $f, g$ 是从布尔超立方体 ${0,1}^v$ 上定义的两个多线性扩展函数（即多项式仅在每个变量上为线性），它们可以通过在所有 $2^v$ 个点上的取值向量来表示，这种形式称为点值表示（evaluation form）。使用该表示，可以高效地计算 $f(r_1, \ldots, r_v) \cdot g(r_1, \ldots, r_v)$，也就是将 $f, g$ 在某点上的值直接相乘。

当我们需要对两个 MLE 进行乘法操作时，若它们当前的点值表示长度不足（比如 degree 尚未达到预期的 $d$），就必须先对其进行填充扩展到长度 $d$。这是因为在乘法后其 degree 会增加（最多加倍），而保持长度为 $d$ 的向量能确保后续 IFFT 或拉格朗日插值等操作的正确性。整个过程与单变量多项式在 FFT 阶段的处理方式类似：在 FFT 后的点值阶段做按位乘法，然后通过 IFFT 恢复到系数表示。多变量 MLE 的点值乘法同样遵循这一原则，但是在高维布尔超立方体上进行。

设 $f, g : {0,1}^v \to \mathbb{F}$ 为两个多线性扩展函数）。它们在点值表示下分别由向量

$$ \mathbf{f} = (f(w)){w \in {0,1}^v}, \quad \mathbf{g} = (g(w)){w \in {0,1}^v} $$

表示。则在某个点 $r = (r_1, \ldots, r_v) \in \mathbb{F}^v$ 上的乘法运算为：

$$ (f \cdot g)(r) \;=\; f(r) \cdot g(r). $$

若采用系数表示，则有：

$$ f(x_1, \ldots, xv) = \sum{w \in {0,1}^v} f(w) \cdot \chi_w(x_1, \ldots, x_v), \quad g(x_1, \ldots, xv) = \sum{u \in {0,1}^v} g(u) \cdot \chi_u(x_1, \ldots, x_v), $$

其中，基函数为

$$ \chi_w(x_1,\ldots,xv) = \prod{i=1}^v \big( (1-w_i)(1-x_i) + w_i x_i \big). $$

因此，乘法结果为

$$ (f \cdot g)(x_1,\ldots,xv) = \sum{w \in {0,1}^v} \sum_{u \in {0,1}^v} f(w) g(u) \cdot \chi_w(x_1,\ldots,x_v) \chi_u(x_1,\ldots,x_v). $$

在点值表示下，则等价于 Hadamard 积：

$$ \mathbf{h} = \mathbf{f} \odot \mathbf{g}, \quad \text{其中 } h(w) = f(w) \cdot g(w), \;\; \forall w \in {0,1}^v. $$

4. 多元多项式加法运算

在多变量情形下，多项式的加法运算本质上是逐点相加：给定两个多项式 $f,g : {0,1}^v \to \mathbb{F}$，它们在布尔超立方体的任意点 $w \in {0,1}^v$ 上的和定义为 $(f+g)(w) = f(w)+g(w)$。在不同表示法下，这一运算表现为：

• 系数表示中，对应基函数的系数逐一相加；
• 点值表示中，对应点的函数值逐一相加。

这种结构确保了加法运算在两种表示下都能以线性时间完成，计算与存储开销均为 $O(2^v)$。

设 $f, g : {0,1}^v \to \mathbb{F}$，则多项式加法定义为：

$$ (f+g)(x_1,\ldots,x_v) = f(x_1,\ldots,x_v) + g(x_1,\ldots,x_v). $$

• 系数表示法：若

$$ f(x) = \sum_{w \in {0,1}^v} a_w \chiw(x), \quad g(x) = \sum{w \in {0,1}^v} b_w \chi_w(x), $$

则

$$ (f+g)(x) = \sum_{w \in {0,1}^v} (a_w + b_w)\chi_w(x). $$

• 点值表示法：若

$$ \mathbf{f} = (f(w)){w \in {0,1}^v}, \quad \mathbf{g} = (g(w)){w \in {0,1}^v}, $$

则

$$ \mathbf{h} = \mathbf{f} + \mathbf{g}, \quad \text{其中 } h(w) = f(w) + g(w), \;\; \forall w \in {0,1}^v. $$

总结

通过对比 点值表示 与 系数表示，展示了多线性扩展在高维布尔超立方体上的基本计算机制。在 点值表示 下，利用多线性性可递归降维，从而高效实现特定点求值，乘法与加法分别对应 Hadamard 积与向量加法。在 系数表示 下，MLE 可借助 Lagrange 基函数直接展开，求值与代数运算均归结为系数的逐项操作。两种表示形式在表达能力上等价，但在不同应用场景中各有优势：点值表示更适合数值计算与并行化，而系数表示更利于代数推导与协议设计。整体而言，为理解和实现 multivariate sumcheck 协议中的多项式计算提供了统一的理论框架和运算工具。