Schwartz–Zippelの補題

$n$ についての帰納法で示す。
$n=1$ の場合。 $P$ は $0$ でない 1 変数多項式で次数を $e\le d$ とすると、多項式環 の定理「根の個数」により $P$ の $K$ の中の根は $e$ 個以下である。よって $\lvert Z(P;S_1)\rvert\le e\le d=\frac d{\lvert S_1\rvert}N$ である。
$n\ge2$ の場合。 変数の個数が $n-1$ のとき主張が成り立つとする。多項式環 の系「多変数の普遍性と変数の順序」により $K[x_1,\dots,x_n]=K[x_2,\dots,x_n][x_1]$ とみなし、
$$ P=\sum_{i=0}^{k}x_1^{\,i}\,P_i(x_2,\dots,x_n),\qquad P_k\neq0 $$
と書く（$P\neq0$ なので、$0$ でない $P_i$ のうち $i$ が最大のものを $P_k$ とする）。$x_1^{\,i}$ と $P_i$ の単項式の積は $P$ の単項式なので、$P_i$ の全次数は $d-i$ 以下であり、とくに $P_k$ の全次数は $d-k$ 以下である。
$a'=(a_2,\dots,a_n)\in S':=S_2\times\cdots\times S_n$ を 2 種類に分ける。

• $P_k(a')=0$ となる $a'$ の集合を $E$ とする。帰納法の仮定を $P_k$ と $S_2,\dots,S_n$ に使うと、$\lvert E\rvert\le\frac{d-k}m\lvert S'\rvert$ である（$\min_{i\ge2}\lvert S_i\rvert\ge m$ なので）。$a'\in E$ については、$P(a_1,a')=0$ となる $a_1\in S_1$ は高々 $\lvert S_1\rvert$ 個である。
• $a'\notin E$ なら、$P(x_1,a')=\sum_{i=0}^k P_i(a')x_1^{\,i}$ は $x_1^{\,k}$ の係数が $P_k(a')\neq0$ の $k$ 次の 1 変数多項式なので、根は $k$ 個以下である。よって $P(a_1,a')=0$ となる $a_1\in S_1$ は $k$ 個以下である。
  $a'$ ごとに数えて足すと、$\lvert S'\rvert\,\lvert S_1\rvert=N$ と $k\le\frac km\lvert S_1\rvert$ から
  $$ \lvert Z(P;S_1,\dots,S_n)\rvert\le\lvert E\rvert\,\lvert S_1\rvert+k\,\lvert S'\rvert\le\frac{d-k}mN+\frac kmN=\frac dmN $$
  である。$\square$

prf-sz-main と同じく $n$ についての帰納法で示す。$n=1$ は根の個数が $d_1$ 以下であることによる。$n\ge2$ では、prf-sz-main と同じく $P=\sum_{i=0}^kx_1^{\,i}P_i$（$P_k\neq0$）と書くと $k\le d_1$ であり、$P_k$ の $x_j$ についての次数は $d_j$ 以下（$j\ge2$）である。帰納法の仮定から $\lvert E\rvert\le\bigl(\sum_{j\ge2}d_j/\lvert S_j\rvert\bigr)\lvert S'\rvert$ で、$a'\notin E$ では零点は $k\le d_1$ 個以下なので、$\lvert Z\rvert\le\lvert E\rvert\lvert S_1\rvert+d_1\lvert S'\rvert\le\bigl(\sum_{j\ge2}d_j/\lvert S_j\rvert+d_1/\lvert S_1\rvert\bigr)N$ である。$\square$

$P\neq0$ なら thm-sz-main により零点は $\frac dmN< N$ 個（$m>d$ なので）であり、すべての点で $0$ になることに反する。$K$ が無限体なら、各 $S_i$ として $d+1$ 個の元をとればよい。$\square$

1：$P=0$ ならどの点でも値は $0$ なので「$P=0$」と答える。「$P\neq0$」と答えるのは $0$ でない値が実際に見つかったときである。
2：$P\neq0$ とする。誤るのは $t$ 個の点がすべて零点のときで、点は独立なので、その確率は 1 点が零点になる確率の $t$ 乗である。thm-sz-main によりこれは $(d/\lvert S\rvert)^t$ 以下で、$\lvert S\rvert\ge2d$ から $2^{-t}$ 以下である。$\square$