= Schwartz-Zippel lemma
{c}
{title2=$\#\{x\in S^n:P(x)=0\}\le d|S|^{n-1}$}
For a nonzero <multivariate polynomial> of <total degree> $d$ over a <field>, and a finite subset $S$ of that field, at most $d|S|^{n-1}$ points of $S^n$ are zeros. For one variable this is the <root bound for a polynomial>. If $d\ge|S|$, the bound is already trivial. Otherwise, in the inductive proof write the <polynomial> as degree $k$ in its last variable, with a nonzero leading coefficient of degree at most $d-k$ in the other variables. The leading coefficient vanishes on at most $(d-k)|S|^{n-2}$ fibers; outside those fibers there are at most $k$ <roots of a polynomial> per fiber. Counting the bad fibers with the trivial $|S|$ bound gives the asserted inequality.
Back to article page
