Part1Schwartz-Zippel 引理

Schwartz-Zippel 引理是关于有限域中的多变量多项式零点个数的紧致上界，具体表述如下：

对于域上的每一个阶最多为的变元非零多项式，对于任意有限集合,

等价地，在中最多有 个根，(是的零点集) ：

Part2归纳证明

1起始步骤

代数基本定理：n = 1时，上述多项式 最多可以有个根。

代数基本定理的归纳证明

子起始步骤

, 则 ，为非零常数。永远非零，自然有0个根。根的个数不超过。

子递推步骤

子归纳假设：对整数，任意阶多项式至多有个根。

令为阶多项式。要说明的是有至多个根。

如果没有根，证毕，因为。

如果 有至少一个根  , 对于阶多项式，可以将写为。

由子归纳假设，至多有个根。

再加上有一个根，则有至多个根。

2递推步骤

重写如下：

为非零多项式，所以一定存在使得。因为 ，于是。

归纳假设：对变元的上述多项式Schwartz-Zippel 引理成立，即：

如果，取最大的，那么  (即不等于0) ，所以由起始步骤（代数基本定理）：

• 事件 :

• 事件：

• 的补事件：

Part3直接证明

将写为，是阶齐次多项式，包含所有阶严格小于的项。

引理：如果非零且阶 ，则存在  使得 . 此外，如果是齐次的，则.

. 假设对于每个。则一定存在 和 使得 , 但对每个 ，.

注意到的阶最多为。而对于每个, , 则 的阶至少为 , 矛盾。

此外，如果是齐次的，则.

由上述引理，令 使得 。

注意到可以被划分为条平行线。每条线的形式为，

对于每个，受限多项式是一个以为变元的单变元多项式，阶最多为。

此外，因为的系数是，则非零！

因此，由代数基本定理，每条线的零点最多个，则在中的总零点至多个。