Schwartz-Zippel Lemma¶
Lemma: Let \(F\) be any field, and let g: \(F^m → F\) be a nonzero \(m\)-variate polynomial of total degree (a.k.a the number of possible roots) at most \(d\). Then on any finite set \(S \subseteq F\) :
\[
\begin{aligned}
Pr_{x←S^m} [g(x) = 0] ≤ d/|S|.
\end{aligned}
\]