# Schwartz-Zippel 引理#

Schwartz-Zippel 引理是关于有限域中的多变量多项式零点个数的紧致上界，具体表述如下：

Schwartz-Zippel 引理

$\operatorname{Pr}_{r_{1}, \ldots, r_{n} \leftarrow S}\left[f\left(r_{1}, \ldots, r_{n}\right)=0\right] \leq \frac{d}{|S|}$

$\left|Z(f) \cap S^{n}\right| \leq d \cdot|S|^{n-1}$

Note

Let $$\mathbb{F}$$ be a finite field and let $$f \in \mathbb{F}\left[X_{1}, \ldots, X_{n}\right]$$ be a non-zero $$n$$ variate polynomial with maximum degree $$d$$. Let $$S$$ be a subset of $$\mathbb{F}$$. Then $$\operatorname{Pr}\left[f\left(x_{1}, \ldots, x_{n}\right)=0\right] \leq d /|S|$$, where the probability is taken over the choice of $$x_{1}, \ldots, x_{n}$$ according to $$x_{i} \stackrel{\}{\leftarrow} d /(p-1)$$.

For a univariate polynomial $$f \in \mathbb{Z}_{p}[X]$$ of degree $$d$$, where $$p$$ is prime, let $$x \leftarrow \mathbb{Z}_{p}^{*}$$, then $$\operatorname{Pr}[f(x)=0] \leq$$ $$d /(p-1)$$.

## 归纳证明#

### 起始步骤#

#### 代数基本定理的归纳证明#

##### 子起始步骤#

$$d=0$$, 则 $$f(x)=c_{0}$$$$c_{0}$$为非零常数。 $$f(x)$$永远非零，自然有0个根。根的个数不超过$$d$$

##### 子递推步骤#

$$f(x)$$$$k+1$$阶多项式。要说明的是$$f(x)$$有至多$$k+1$$个根。

$$\square$$

### 递推步骤#

Proof. 重写$$f$$如下：

$f\left(x_{1}, \ldots, x_{n}\right)=\sum_{i=0}^{d} x_{1}^{i} P_{i}\left(x_{2}, \ldots, x_{n}\right)$

$$f$$为非零多项式，所以一定存在$$i$$使得$$P_{i}\ne 0$$。 因为 $$\mathrm{deg}(x_{1}^{i} P_{i}) \le d$$，于是$$\mathrm{deg} (P_i) \le d-i$$

$\operatorname{Pr}\left[P_{i}\left(r_{2}, \ldots, r_{n}\right)=0\right] \leq \frac{d-i}{|S|}$

$\operatorname{Pr}\left[f\left(r_{1}, r_{2}, \ldots, r_{n}\right)=0 \mid P_{i}\left(r_{2}, \ldots, r_{n}\right) \neq 0\right] \leq \frac{i}{|S|}$
• 事件$$A$$ : $$f\left(r_{1}, r_{2}, \ldots, r_{n}\right)=0$$

• 事件$$B$$$$P_{i}\left(r_{2}, \ldots, r_{n}\right)=0$$

• $$B$$的补事件：$$B^c$$

\begin{split} \begin{aligned} \operatorname{Pr}[A] &=\operatorname{Pr}[A \cap B]+\operatorname{Pr}\left[A \cap B^{c}\right] \\ &=\operatorname{Pr}[B] \operatorname{Pr}[A \mid B]+\operatorname{Pr}\left[B^{c}\right] \operatorname{Pr}\left[A \mid B^{c}\right] \\ & \leq \operatorname{Pr}[B]+\operatorname{Pr}\left[A \mid B^{c}\right] \\ & \leq \frac{d-i}{|S|}+\frac{i}{|S|}=\frac{d}{|S|} \end{aligned} \end{split}

$$\square$$

## 直接证明#

Proof. 将$$f$$写为$$f=g+h$$$$g \not \equiv 0$$$$d$$阶齐次多项式，$$h$$包含所有阶严格小于$$d$$的项。

$$\mathcal{Proof}$$. 假设对于每个$$y \in S^n, g(y)=0$$。则一定存在$$1 \leq i \leq n$$$$a_{1}, \ldots, a_{i-1} \in S$$ 使得 $$g\left(y_{i}, \ldots, y_{n}\right) \doteq f\left(a_{1}, \ldots, a_{i-1}, y_{i}, \ldots, y_{n}\right) \not \equiv 0$$, 但对每个 $$a \in S$$$$g\left(a, y_{i+1}, \ldots, y_{m}\right) \equiv 0$$.

$$\square$$