4 Various Papers 4.2 Discrete Gaussian Leftover Hash Lemma 4.4 Ligero Interleaved Linear Code Testing

4.3 Schwartz-Zippel by Dana Moshkovitz

The geometric viewpoint in [Mos10] is to foliate $\mathbb{F}_{q}^{n}$ by parallel lines, and count their intersections with the zero set of a polynomial. The key is to choose a direction for which no whole line lies in the zero set.

The existence of the direction uses only the following elementary fact.

Lemma 4.3.1 (Nonzero evaluation [Mos10]).

Let $\mathbb{F}_{q}$ be a finite field with $q$ elements, and $f\in\mathbb{F}_{q}[X_{1},\ldots,X_{n}]$ be nonzero with individual degrees less than $q$ . Then $f$ has a nonzero evaluation in $\mathbb{F}_{q}^{n}$ .

Proof.

Fixing coordinates successively while keeping the remaining polynomial nonzero is always possible: if every substitution $X_{i}=a$ for $a\in\mathbb{F}_{q}$ over a nonzero remaining polynomial $P$ , made $P$ identically zero, then

\prod_{a\in\mathbb{F}_{q}}(X_{i}-a)=X_{i}^{q}-X_{i}\mid P,

contradicting $\deg_{X_{i}}P<q$ . After all coordinates are fixed, the resulting value is nonzero. ∎

We now restate Schwartz-Zippel [Sch80, Zip79] in Moshkovitz’s viewpoint [Mos10].

Lemma 4.3.2 (Schwartz-Zippel [Sch80, Zip79]).

Let $\mathbb{F}_{q}$ be a finite field with $q$ elements, and $f\in\mathbb{F}_{q}[X_{1},\ldots,X_{n}]$ be nonzero of total degree $d$ , with $n\geq 1$ . From uniformly random $\mathbf{x}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{F}_{q}^{n}$ ,

\Pr\left[f(\mathbf{x})=0\right]\leq\frac{d}{q}.

Equivalently, as for the zero set of $f$ over $\mathbb{F}_{q}^{n}$ ,

\left|\{\mathbf{x}\in\mathbb{F}_{q}^{n}:f(\mathbf{x})=0\}\right|\leq dq^{n-1}.

Proof.

The cases $d=0$ and $d\geq q$ are immediate, so assume $1\leq d<q$ .

Write $f=g+h$ , where nonzero $g$ consists of all the degree- $d$ monomials, and thus $\deg h<d$ . By lemma 4.3.1, $g$ has a nonzero evaluation over $\mathbb{F}_{q}^{n}$ , and by $g$ being all degree- $d$ monomials, $g(\boldsymbol{0})=0$ . Hence, there exists $\mathbf{y}\in\mathbb{F}_{q}^{n}\setminus\{\boldsymbol{0}\}$ such that $g(\mathbf{y})\neq 0$ .

For any basepoint $\mathbf{x}$ , substitution gives $p(t)=f(\mathbf{x}+t\mathbf{y})$ that $\deg_{t}p=d$ , whose degree- $d$ term has coefficient $g(\mathbf{y})$ , and has at most $d$ roots.

There are $q^{n-1}$ distinct parallel lines $\mathbf{x}+t\mathbf{y}$ , as $\left|\mathbb{F}_{q}^{n}/\mathrm{Span}\left(\mathbf{y}\right)\right|=q^{n-1}$ , and thus at most $dq^{n-1}$ zero evaluations, as each line contributes at most $d$ roots. ∎

The same counting pattern appears in the Ligero argument below: choose a direction along which every parallel line contains few exceptional points, then count across the partition. There the points are received words close to a code; here they are zeros of $f$ .