Existing polynomial identity bounds

The existing A nonzero polynomial of degree $n$ over an integral domain has at most $n$ distinct roots says that a nonzero univariate polynomial of degree $m$ over an integral domain has at most $m$ distinct roots. A field is an integral domain: if $ab=0$ and $a\mathrm{\ne }0$, multiplication by $a^{-1}$ gives $b=0$.

A nonzero formal polynomial of total degree at most $d$ over a field vanishes at a uniform point of $S^n$ with probability at most $d\mathrm{/}\mathrm{\mid }S\mathrm{\mid }$, for nonempty finite $S\subseteq F$. Here total degree and coefficient expansions are as in Monomials, coefficients, degree in each variable and total degree in $F[x_1,\dots ,x_n]$. To see the bound directly, induct on $n$. For $n=0$ a nonzero constant never vanishes. For $n>0$, write $f={\sum }_{j=0}^m{f}_j(x_1,\dots ,x_{n-1})x_n^j$ with $f_m\mathrm{\ne }0$. The total degree of $f_m$ is at most $d-m$, so the induction hypothesis bounds the fraction of points of $S^{n-1}$ where it vanishes by $(d-m)\mathrm{/}\mathrm{\mid }S\mathrm{\mid }$. At each remaining point the specialization in $x_n$ has degree $m$ and at most $m$ roots by the root bound. Splitting the finite set $S^n$ into these two cases gives a vanishing fraction at most $(d-m)\mathrm{/}\mathrm{\mid }S\mathrm{\mid }+m\mathrm{/}\mathrm{\mid }S\mathrm{\mid }=d\mathrm{/}\mathrm{\mid }S\mathrm{\mid }$. This argument is finite counting and uses no Axiom of Choice.

Apply such bounds to a nonzero difference of formal polynomials. Individual degree bounds concern one variable at a time; total degree bounds concern sums of exponents within a monomial. Sum-check's round comparison is univariate and needs only the root bound. When a degree bound is at least the field size, the resulting probability bound may be vacuous. Distinct formal polynomials over a finite field need not define distinct functions on the whole field.