Schwartz–Zippel 引理

Schwartz–Zippel 引理指出，如果我们有非零 $n$ 元 $d$ 次多项式 $p(x_1,\dots,x_n)$，对每个 $x_i$ 在有限集合 $S\subset \mathbb R$ 内独立均匀随机赋值，则
$$
\mathbb P[p(x_1,\dots,x_n)=0]\le \frac d{|S|}.
$$
证明考虑对 $n$ 进行归纳。

$n=1$ 的情况是简单的，$p(x_1)=0$ 也即 $x_1$ 是 $p(x)=0$ 的一根。我们知道一元 $d$ 次方程至多有 $d$ 个实根，所以 $x_1$ 取到根的概率显然为 $d/|S|$。

接下来假设引理对 $1,\dots,n-1$ 成立，我们需要证明引理对 $n$ 成立。

考虑将 $x_n$ 提取出来。令 $k$ 是 $x_n$ 的最大度数，提取出包含 $x_n^k$ 的项，我们有
$$
p(x_1,\dots,x_n)=x_n^kq(x_1,\dots,x_{n-1})+r(x_1,\dots,x_n),
$$
其中 $q$ 的度数不超过 $d-k$，$r$ 中 $x_n$ 的度数不超过 $k-1$。

为 $x_1,\dots,x_n$ 随机赋值，由归纳假设我们知道
$$
\mathbb P[q(x_1,\dots,x_{n-1})=0]\le \frac{d-k}{|S|}.
$$
另一方面，若 $q\ne 0$，则 $p$ 成为了关于 $x_n$ 的一元 $k$ 次多项式，由归纳假设我们知道
$$
\mathbb P[p=0|q\ne 0]=\frac k{|S|}.
$$
于是，
$$
\begin{aligned}
\mathbb P[p=0]&=\mathbb P[p=0|q=0]\mathbb P[q=0]+\mathbb P[p=0|q\ne 0]\mathbb P[q\ne 0]\\
&\le\mathbb P[q=0]+\mathbb P[p=0|q\ne 0]\\
&\le\frac{d-k}{|S|}+\frac k{|S|}=\frac d{|S|}.
\end{aligned}
$$
$\blacksquare$

SZ 引理可用于快速检验两个多项式是否相等。

Reference：