Consider the two cases:

• Case x = 0. First we show the theorem when $f(0)=0$, then the claim is that $f(X)=(X-x)$ $\cdot g(X)$ $=$ $X\cdot g(X)$. To see this observe that if $f(X)={\sum }_{i=0}^d{c}_i\cdot X^i$ then $f(0)=c_0$, and since $f(0)=0$ we have $c_0=0$. Therefore $f(X)$ is of the form: $$\begin{array}{rl}f(X)& =c_1\cdot X+\dots +c_d\cdot X^d\\ & =X\cdot (c_1+\dots +c_d\cdot X^{d-1})\end{array}$$ If we define $g(X)=c_1+\dots +c_d\cdot X^{d-1}$, we see that: $$f(X)=X\cdot g(X)=(X-0)\cdot g(X)$$ As desired.

• Case x $\ne$ 0. Suppose $f(x)=0$. Define the polynomial $f^{\ast }(X)=f(X+x)$ and observe that $f^{\ast }(0)=0$. Therefore, by the “x = 0” case, we conclude that $f^{\ast }(X)=X\cdot g^{\ast }(X)$ for some $g^{\ast }(X)\in \mathcal{F}[X]$. Next write: $$\begin{array}{rl}f(X)& =f((X-x)+x)\\ & =f^{\ast }(X-x)=(X-x)\cdot g^{\ast }(X-x)\end{array}$$

If we define $g(X)=g^{\ast }(X-x)$, then we see that:

$$\begin{array}{rl}f(X)& =(X-x)\cdot g^{\ast }(X-x)\\ & =(X-x)\cdot g(X)\end{array}$$

We prove this using induction over the degree $d$ of $f(X)$.

• Base d = 0. If $d=0$, then $f(X)=c$ for some non-zero $c\in \mathcal{F}$. Clearly, $f(X)$ has $0$ roots.

• Step d > 0. Let $f(X)$ be a polynomial of degree $d$. If $f(X)$ has $0$ roots in $\mathcal{F}$, then we are done. Otherwise, let $x_0\in \mathcal{F}$ be a root of $f(X)$. Then, using the factor theorem, we can write $f(X)=(X-x_0)\cdot g(X)$ for some polynomial $g(X)$ of degree $d-1$. By the inductive hypothesis, $g(X)$ has at most $d-1$ roots and $X-x_0$ has at most $1$ root. Finally $f(X)$ has at most $d$ roots because $\mathcal{F}$ is an integral domain: since if $x\in \mathcal{F}$ is such that $f(x)=(x-x_0)\cdot g(x)=0$, then either $(x-x_0)=0$ or $g(x)=0$, in other words, $x$ must be a root of either $X-x_0$ or $g(X)$ of which there are at most $1+(d-1)=d$.

Define $f(X)=f_0(X)-f_1(X)$. Note that $f(X)$ is a polynomial in $\mathcal{F}[X]$ of degree at most $d$ and observe that $f(x_i)=0$ for all $i\in \{0,\dots ,d\}$: $f(X)$ has at least $d+1$ roots in $\mathcal{F}$. Therefore, $f(X)$ must be the zero polynomial, i.e. $f_0(X)=f_1(X)$.

Note that the statement is vacuous if $|\mathcal{C}|\le d$. When $|\mathcal{C}|>d$ then the statement implies that there must exist a subset $S\subseteq \mathcal{C}$ with $|S|>d$ such that: $$\forall x\in S,f_0(x)=f_1(x)$$ In which case the previous corollary shows that $f_0(X)=f_1(X)$.

We can multiply and add polynomials, it is also clear that polynomial multiplication is commutative (since $\mathcal{F}$ is), i.e. for $f(X)\in \mathcal{F}[X]$ and $g(X)\in \mathcal{F}[X]$, we have: $$f(X)\cdot g(X)=g(X)\cdot f(X)$$ Finally, let us verify that there are no zero divisors in $\mathcal{F}[X]$, i.e. show: $$f(X)\cdot g(X)=0⟹f(X)=0\text{ or }g(X)=0$$ To see this let $j$ and $i$ be the degrees of $f(X)$ and $g(X)$ respectively, denote by $f_j\in \mathcal{F}$ and $g_i\in \mathcal{F}$ the leading coefficients of $f(X)$ and $g(X)$. Note that $f_j\ne 0$ and $g_i\ne 0$ otherwise $f(X)=0$ or $g(X)=0$ respectively. Then the leading coefficient of $f(X)\cdot g(X)$ is $f_j\cdot g_i$ which is non-zero since $\mathcal{F}$ is an integral domain. Therefore, $f(X)\cdot g(X)=0$ if and only if $f(X)=0$ or $g(X)=0$.

We prove this by induction:

• Base k = 1. When $\vec{X}=(X_1)$ the “multivariate” polynomial is a univariate polynomial $f(X_1)\in \mathbb{F}[X_1]$, by applying the fundamental theorem with $\mathcal{F}=\mathbb{F}$, we observe that the number of roots of $f(X_1)$ is at most $d_1=\mathrm{deg}(f)$, however since $|S_1|>d_1$ the polynomial cannot evaluate to zero on all of $S_1$. So the claim holds.

• Step k > 1. Define $\mathcal{F}$ $=$ $\mathbb{F}[X_1,\dots ,X_{k-1}]$ and now rewrite $f(\vec{X})$ as a polynomial with coefficients in $\mathcal{F}$: $$f(X_1,\dots ,X_k)=\sum _i{X}_k^i\cdot f_i(X_1,\dots ,X_{k-1})\in \mathcal{F}[X_k]$$ Since $\mathcal{F}$ is an integral domain, we can apply the fundamental theorem, this time to $\mathcal{F}$ $=$ $\mathbb{F}[X_1,\dots ,X_{k-1}]$, rather than $\mathcal{F}=\mathbb{F}$. We conclude that at most $d_k$ values $x_k\in \mathcal{F}$ satisfy: $$f(x_k)=\sum _i{x}_k^i\cdot f_i(X_1,\dots ,X_{k-1})=0$$ And, in particular, there exist at most $d_k$ elements $x_k\in S_k\subseteq \mathbb{F}\subseteq \mathcal{F}$ (constant polynomials) satisfying this. On the other hand, since $|S_k|>d_k$ there must exist at least one $x_k\in S_k$ which is not a root, in other words: $$f(x_k)=g(X_1,\dots ,X_{k-1})\ne 0\in \mathcal{F}$$ We then apply the induction hypothesis on $g(X_1,\dots ,X_{k-1})$ to conclude that it does not vanish over ${\mathbb{H}}_{k-1}$. In other words, we conclude that there is at least one $(x_1,$ $\dots ,$ $x_{k-1})$ $\in$ ${\mathbb{H}}_{k-1}$ such that $g(x_1,\dots ,x_{k-1})\ne 0$, which also allows us to conclude: $$f(x_1,\dots ,x_k)=g(x_1,\dots ,x_{k-1})\ne 0\in \mathbb{F}$$ So $f(X_1,\dots ,X_k)$ also cannot vanish over ${\mathbb{H}}_k$ and the claim holds for $k$ as well.

We can form: $$h(X_1,\dots ,X_k)=f(X_1,\dots ,X_k)-g(X_1,\dots ,X_k)$$ By assumption $\forall \vec{x}\in {\mathbb{H}}_k.h(\vec{x})=f(\vec{x})-g(\vec{x})=0$, therefore we conclude that $h(X_1,X_2,\dots ,X_k)=0$ by the theorem. Hence $f(X_1,\dots ,X_k)=g(X_1,\dots ,X_k)$.

We show this by induction:

• Base k = 1. When $k=1$ the “multivariate” polynomial is a univariate polynomial $f(X_1)\in \mathbb{F}[X_1]$, by applying the fundamental theorem with $\mathcal{F}=\mathbb{F}$ we observe that the number of roots of $f(X_1)$ is at most $d_1$. Hence for uniform $x_1\stackrel{\$}{\leftarrow }{S}_1$, the probability that $f(x_1)=0$, i.e. that $x_1$ is one of the at most $d_1$ roots, is at most $d_1/|S_1|$.

• Step k > 1. Basically, there are two ways that $f(x_1,\dots ,x_k)$ could be zero:

  • When we partially evaluate we get the zero polynomial $f(X_1,\dots ,X_{k-1},x_k)=0$
  • Or, $g(X_1,\dots ,X_{k-1})=f(X_1,\dots ,X_{k-1},x_k)\ne 0$, but $g(x_1,\dots ,x_{k-1})=0$.

  Define $\mathcal{F}$ $=$ $\mathbb{F}[X_1,\dots ,X_{k-1}]$ and view $f(\vec{X})$ as a polynomial in $\mathcal{F}$: $$f(X_1,\dots ,X_k)=\sum _i{X}_k^i\cdot f_i(X_1,\dots ,X_{k-1})\in \mathcal{F}[X_k]$$ Since $\mathcal{F}$ is an integral domain, we conclude that at most $d_k$ values $x_k\in \mathcal{F}$ satisfy: $$f(x_k)=\sum _i{x}_k^i\cdot f_i(X_1,\dots ,X_{k-1})=0$$ And, in particular, there exist at most $d_k$ elements $x_k\in S_k\subseteq \mathbb{F}\subseteq \mathcal{F}$ which make $f(x_k)=0$, hence the probability that $x_k\stackrel{\$}{\leftarrow }{S}_k$ makes $f(x_k)=0$ is at most $d_k/|S_k|$.

  On the other hand, if $x_k\stackrel{\$}{\leftarrow }{S}_k$ is not a root: $$f(x_k)=g(X_1,\dots ,X_{k-1})\ne 0\in \mathcal{F}$$ We can apply the induction hypothesis on $g(X_1,\dots ,X_{k-1})$ to conclude that: $${\mathbb{P}}_{\vec{x}\stackrel{\$}{\leftarrow }{\mathbb{H}}_{k-1}}\left[g(\vec{x})=0\right]\le \sum _{i=1}^{k-1}\frac{d_i}{|S_i|}$$ By applying a union bound on both these events we conclude that: $${\mathbb{P}}_{\vec{x}\stackrel{\$}{\leftarrow }{\mathbb{H}}_k}\left[f(\vec{x})=0\right]\le \frac{d_k}{|S_k|}+\left(\sum _{i=1}^{k-1}\frac{d_i}{|S_i|}\right)=\sum _{i=1}^k\frac{d_i}{|S_i|}$$