Schwartz zippel over finite fields

A field is an integral domain: distributivity gives $a0=a(0+0)=a0+a0$, so additive cancellation gives $a0=0$. If $ab=0$ and $a\mathrm{\ne }0$, multiply by $a^{-1}$ to obtain $b=0$. Thus F2 applies over F. For m=1 it gives at most d roots in A, and hence probability at most $d\mathrm{/}\mathrm{\mid }A\mathrm{\mid }$ and also at most one. If d=0 in any number of variables, F1 makes f a nonzero constant, with no zero evaluations.

To pass from m-1 to m for $m>1$, suppose the asserted root-count bound holds in m-1 variables for every nonzero polynomial. Put $q=\mathrm{\mid }A\mathrm{\mid }>0$. If $d\ge q$ the target minimum is one and the bound is immediate from counting at most all $q^m$ tuples. It remains to consider $0<d<q$. Collect monomials by the last exponent as $f={\sum }_{j=0}^r{g}_j{x}_m^j$ with $g_r\mathrm{\ne }0$. F1 gives $\mathrm{deg}{g}_r\le d-r$, and $0\le r\le d<q$.

By the m-1 assertion the number B of base tuples in $A^{m-1}$ on which $g_r$ vanishes is at most $(d-r)q^{m-2}$. For the other $q^{m-1}-B$ tuples, specialization yields a nonzero univariate polynomial of degree exactly r, so F2 bounds its roots by r. A bad base tuple has at most q possible last coordinates, regardless of whether its specialized polynomial is zero. The total zero count is therefore $Bq+(q^{m-1}-B)r\le Bq+q^{m-1}r\le (d-r)q^{m-1}+r{q}^{m-1}=d{q}^{m-1}\mathrm{.}$ For r=0 the good specializations are nonzero constants and have zero roots, exactly as this count says. Division by $q^m>0$ gives $d\mathrm{/}q$.

Step 1.1 supplies the one-variable base; steps 2.1–3.1 pass the root-count bound to each next number of variables, and F4 gives it for every positive m. The case $\mathrm{\mid }A\mathrm{\mid }=1$ is covered by the constant case or $d\ge q$, so no hidden division by q-1 occurs. To see why formal nonzero is the right hypothesis, for any finite F the formal product ${\prod }_{a\in F}(X-a)$ has leading coefficient one and degree $\mathrm{\mid }F\mathrm{\mid }$, yet vanishes at every element of F. This finite product needs no ordering choice: commuting factors give the same polynomial in any listing. Thus a vanishing polynomial function is compatible with the bound when degree is large.