Schwartz–Zippel 引理
November 19, 2024 •
Comment
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$ 进行归纳。