Schwartz–Zippel引理

切成一元多项式时，先防止整片消失 ​

固定 $x_1,\dots ,x_{n-1}$ 后，P成为关于 $x_n$ 的一元多项式。如果这片非零，一元根数界便能控制最后一个随机坐标。但某些固定值可能使整片变成零多项式，不能无条件直接套一元结论。

例如 $P(x,y)=xy$。当x=0时，无论y是什么都得到零；当x≠0时，只有y=0才命中零点。证明把这两类失败分开，分别向不同变量的次数收费。

一元根数界从除法得到 ​

若非零一元多项式f满足f(a)=0，除以x−a的余数为f(a)，所以 $f=(x-a)g$。对于另一个根b≠a，$0=(b-a)g(b)$；域中b−a非零，可消去，故g(b)=0。每取走一个不同根，次数减少1，非零常数没有根，于是d次非零多项式至多有d个不同根。

这段论证已经指出代数条件的用途：必须能够从 $(b-a)g(b)=0$ 推出g(b)=0，不能在有零因子的环里照搬。

多元归纳的两笔预算 ​

把P按最后一个变量分组，取最高非零系数：

每个来自Q的单项式再乘 $x_n^k$ 后总次数至多D，所以 $\mathrm{deg}Q\le D-k$。由对变量数的归纳，前n−1个坐标使Q消失的概率至多 $(D-k)/|S|$。

若Q没有消失，代入后的多项式恰有次数k，最后一个坐标命中根的概率至多 $k/|S|$。利用条件概率理路条件概率Conditional probability在已知正概率事件发生后，把交集概率重新规范到该事件内部。，对每个已固定的前缀分别应用这一界，再对前缀求平均，得到

即使k=0也不出问题：Q就是不依赖最后一个变量的P，第二项为0。若某个粗界超过1，只把它当上界使用，不把负的“成功下界”继续相乘。最后与平凡上界1取小值。

二维网格上的九个零点 ​

在 ${\mathbb{F}}_5$ 上取 $P(x,y)=xy$、$S={\mathbb{F}}_5$。25个等概率点中，x=0的一行有5点，y=0的一列有5点，原点被重复计数一次，实际零点率为 $9/25$。总次数D=2给出上界 $2/5=10/25$。

按刚才的证明计数：先抽x，坏切片概率1/5；其余4/5的切片各有1/5的零点率，总和为 $1/5+(4/5)(1/5)=9/25$。证明中的最后一次放大把后者粗估为1/5，正好多算一个点。

相同边际分布不等于独立坐标 ​

仍在 ${\mathbb{F}}_5$ 上，$P(x,y)=x-y$ 的总次数是1。若只抽一个均匀r并取(x,y)=(r,r)，两个坐标各自都均匀，但P总为零，概率1大于1/5。重新抽取第二个坐标才符合定理。

即使坐标确实独立，若先抽r，再把输入多项式定义成 $P_r(x)=x-r$，这次代入仍总为零。定理是“每个事先固定的P，在随机点上很少为零”，不能交换为“看到随机点后任意挑P也很少为零”。

小域和零因子的两种障碍 ​

在 ${\mathbb{F}}_5[x]$ 中，$x^5-x$ 是非零形式多项式，却在全部五个域元素上为零。D/|S|=1恰好说明该测试空间没有保证。要测试原来的特征5多项式，可以在足够大的特征5扩域中取点；直接改到特征7，会改变系数解释和问题本身。

在 $\mathbb{Z}/4\mathbb{Z}$ 中，$2x$ 次数为1，却有0和2两个根。这里的失败来自零因子，不是采样点数太少。把“模一个整数”当成“在域中计算”，会同时破坏根数证明与非零除法。

从一次零点界到多轮测试 ​

若固定非零P，每轮重新独立抽整个向量，t轮都为零的概率至多 $min(1,D/|S|{)}^t$。当 $|S|\ge 2D>0$ 时，不超过 $2^{-t}$。反复代入同一个点只是重做同一计算，不能把失败率乘t次。

多项式恒等式测试理路多项式恒等式测试Polynomial identity testing · PIT对形式多项式电路逐门随机求值，以次数预算给出单边漏检界，保留非零见证并处理小域与位成本。把这个概率界接到算术电路上：不展开全部系数，直接计算点值。发现非零值就是确定的反例；连续发现零值只得到单边漏检保证。

手算迁移：换一个零点几何 ​

对 $P(x,y)=(x-y)(x+y)$，在 ${\mathbb{F}}_5^2$ 上两条零点直线只在原点相交，所以仍有9个零点。若改到特征2，则x−y与x+y相同，P成为 $(x-y{)}^2$；在 ${\mathbb{F}}_2^2$ 上只有两个零点，D/|S|=1却给不出非平凡上界。次数是上界工具，不能代替对具体代数结构的检查。

读完本页，应能指出给定证明在哪一步使用域、哪一步使用独立性，并对一个具体网格同时算出真实零点率和定理上界。两者相等并不是正确应用定理的必要条件。