Schwartz-Zippelの補題

自分のお気に入りの補題のなかにSchwartz-Zippelの補題というものがある.代数,確率,それに組合せ的な話が出てきてとても楽しい補題である.日本語の文献が少ないようなので,ここで紹介しておきたい.補題のStatementは以下の通りである.

Schwartz-Zippelの補題
$p(x_1,\dots,x_n) \neq 0$ を体 $\mathbf{F}$ 上の $n$ 変数非ゼロ多項式とする.$S$ を $\mathbf{F}$ の有限部分集合とし, $r_1, \dots, r_n$ を $S$ から独立かつ一様ランダムに選ぶとする.すると $\mathrm{Pr}(p(r_1, \dots, r_n) = 0) \leq \frac{\mathrm{deg}(p)}{|S|} $ である.

(証明)$d := \mathrm{deg}(p)$とする. $n$ に関する帰納法で証明する.$n=1$ の場合は,$d$ 次多項式は高々 $d$ 個の根しか持たないことから明らかである.$n - 1$ まで正しいとして, $n$ の場合を示そう.$p$ を $x_1$ に関して整理して次のように分解する:
\[
p(x_1, \dots, x_n) = \sum_{i=0}^k x_1^i p_i(x_2, \dots, x_n)
\]
ただし,$p_k \neq 0$ とする.ここで, $A$ を $p(r_1, \dots, r_n) = 0$ となる事象, $B$ を $p_k(r_2, \dots, r_n) = 0$ となる事象とする.$p_k$ の次数が高々 $d-k$ であることに注意すると,帰納法の仮定から $\mathrm{Pr}(B) \leq (d-k) / |S| $. 一方, $p_k(r_2, \dots, r_n) \neq 0$ であるとすると, $A$ が起こるためには $r_1$ は 1変数 $k$ 次多項式 $\tilde{p}(x_1) = p(x_1, r_2, \dots, r_n)$ の根でなければならない.そのような確率は $n=1$ の場合から $\mathrm{Pr}(A \mid \bar{B}) \leq k / |S| $ である.これより
\begin{align*}
\mathrm{Pr}(A) &= \mathrm{Pr}(A \mid B) \mathrm{Pr}(B) + \mathrm{Pr}(A \mid \bar{B}) \mathrm{Pr}(\bar{B}) \\
&\leq \mathrm{Pr}(B) + \mathrm{Pr}(A \mid \bar{B}) \\
&\leq \frac{d-k}{|S|} + \frac{k}{|S|} = \frac{d}{|S|}
\end{align*}

応用

この補題の面白い使い方として,次のようなものがある. $A$ を各成分が $x_1,\dots, x_n$の $\mathbf{F}$ 係数多項式であるような行列としよう.このとき $\det A$ は多項式となるが,これが非ゼロであるか判定するにはどうしたら良いだろうか?掃き出しをやろうとすると,成分が $x_1,\dots, x_n$ の複雑な有理関数となってしまい,多項式時間ではできない.しかし,Schwartz-Zippelの補題によると,$\mathbf{F}$ が十分に大きければ(たとえば $|S| > 2 \mathrm{deg}\det A $ となる $S \subseteq \mathbf{F}$ が取れるならば), $x_1,\dots, x_n$ に一様ランダムに値を代入して得られる定数行列 $\tilde{A}$ の行列式を計算して,ゼロか非ゼロか判定するだけで,片側誤り確率 $1/2$ 未満で正しく判定できる!

実は,$A$ を工夫して作ると $\det A = 0$ の判定によって無向グラフの完全マッチングの存在判定ができることが知られている(そのときに使う行列は Tutte行列 と呼ばれている).完全マッチングの多項式時間アルゴリズムは実装がとても大変だが,判定だけであればこんな方法で簡単にできる.


参考文献
乱択アルゴリズムといえばこれ

  • Motowani, Raghavan, “Randomize Algorithms”

Schwartz-Zippelの補題の歴史が載っている