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:
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。