BLR 线性测试

被测试的性质 ​

令定义域为向量空间 $G={\mathbb{F}}_2^n$，对象是 oracle function $f:G\to {\mathbb{F}}_2$。目标性质由全部线性函数组成：存在 $a\in {\mathbb{F}}_2^n$，使

$$f(x)=⟨a,x⟩(\mathrm{mod}2)$$

对所有 $x$ 成立。每个对象的显式表示是长度 $2^n$ 的真值表，距离取不同函数值所占比例

$$\mathrm{dist}(f,g)={\text{Pr}}_{x\sim U(G)}[f(x)\ne g(x)].$$

这些线性真值表构成Hadamard 码公理库线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。。测试器通过查询函数 oracle 的位置，而不是输入向量 $a$；本地加法和随机采样在有限域公理库有限域Finite field · Galois field底层集合有限的域。上完成。

三查询算法 ​

一次 BLR 试验独立均匀抽取 $x,y\in G$，查询

$$f(x),f(y),f(x+y),$$

并在且仅在

$$f(x)+f(y)=f(x+y)pmod2$$

时接受。三个查询地址在看到答案前已经确定，所以试验非自适应；若等式失败，当前三元组就是一个不可由线性函数产生的拒绝 witness。

重复 $k$ 次并在任一次失败时拒绝，仍保持 perfect completeness。若单次拒绝概率至少 $\delta$，全部漏检概率为 $(1-\delta {)}^k\le e^{-k\delta }$，达到失败率 $\eta$ 需要 $k=O({\delta }^{-1}\log \left(1/\eta \right))$，总查询为 $3k$。

完备性 ​

若 $f(x)=⟨a,x⟩$，则对每个 $x,y$ 都有

$$f(x+y)=⟨a,x+y⟩=⟨a,x⟩+⟨a,y⟩=f(x)+f(y)pmod2.$$

因此线性函数在每条随机轨迹上都接受，完备性为 $1$。测试不接受一般 affine function $f(x)=⟨a,x⟩+b$；若 $b=1$，取 $x=y=0$ 就会违反加法式。要测试 affine 性需改变方程或先消去 $f(0)$。

一个具体拒绝轨迹 ​

在 ${\mathbb{F}}_2^2$ 上，线性函数 $f(x_1,x_2)=x_1+x_2$ 的表为

$$f(00)=0,f(01)=1,f(10)=1,f(11)=0.$$

取 $x=01,y=10$，有 $x+y=11$，等式检查为 $1+1=0$，通过。现在只把表中 $f(11)$ 腐化为 $1$；同一三元组变成 $1+1\ne 1$，测试拒绝。

另一些随机三元组可能避开腐化点而通过，所以“一次发现”不是 soundness 的全部。需要证明如果表远离每个线性函数，失败三元组在所有随机对中占有可观比例。

Fourier soundness 恒等式 ​

把函数编码为 $F(x)=(-1{)}^{f(x)}\in \{-1,+1\}$。BLR 等式通过当且仅当

$$F(x)F(y)F(x+y)=1.$$

若单次拒绝概率为 $\delta$，则

$${\mathbb{E}}_{x,y}[F(x)F(y)F(x+y)]=1-2\delta .$$

对字符 ${\chi }_a(x)=(-1{)}^{⟨a,x⟩}$ 定义 Fourier 系数 $\hat{F}(a)={\mathbb{E}}_x[F(x){\chi }_a(x)]$。利用字符正交性展开三重相关，得到

$${\mathbb{E}}_{x,y}[F(x)F(y)F(x+y)]=\sum _{a\in G}\hat{F}(a{)}^3.$$

Parseval 恒等式给 $\sum _a\hat{F}(a{)}^2=1$。令 $M=\underset{a}{max}\hat{F}(a)$，则每项 $\hat{F}(a{)}^3\le M\hat{F}(a{)}^2$，所以

$$1-2\delta \le M\sum _a\hat{F}(a{)}^2=M.$$

因此存在 $a$ 使 $\hat{F}(a)\ge 1-2\delta$。而

$$\hat{F}(a)=1-2{\text{Pr}}_x[f(x)\ne ⟨a,x⟩],$$

故 $f$ 到某个线性函数的距离至多 $\delta$。取逆否得到 soundness：若 $f$ 与每个线性函数的距离至少 $\epsilon$，单次 BLR 拒绝概率至少 $\epsilon$。

证明链不能缩成口号 ​

“大多数局部方程成立”只给出三重相关接近 $1$；真正的全局结论来自 Fourier 恒等式、Parseval 和大系数对应某个一致线性字符。跳过这段，会遗漏为何不同局部三元组必须围绕 同一个 $a$ 对齐。

测试依赖 $x,y$ 独立均匀。偏置采样会改变字符正交与拒绝率；复用相关随机对也不能直接使用独立放大。对一般有限域、非阿贝尔群或高次多项式，测试方程和 soundness 常数都需重新证明。

距离按完整真值表的均匀 Hamming 比例计算。若 oracle 只允许从未知分布抽 $x$，或只在某个 promise 子集上查询，BLR 的随机加法点可能不可访问，原 tester 不再合法。

参考资料

• Manuel Blum, Michael Luby, and Ronitt Rubinfeld, “Self-Testing/Correcting with Applications to Numerical Problems,” Journal of Computer and System Sciences 47(3), 1993, pp. 549–595.
• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapter 2.
• Madhu Sudan, “Invariance in Property Testing,” Property Testing, Springer, 2010, pp. 211–229.