# Polynomial in several variables over $GF(2)$

Can anyone please explain how this Lemma has been proved?

Lemma: Let $f$ be a nonzero polynomial in variables $x_1,\ldots,x_n$ over $GF(2)$, and let $d$ be the maximum degree of $f$ with respect to any variable. Then there exist values for $x_1,\ldots,x_n$ in $GF(2^m)^n$ such that $f(x_1,\ldots,x_n)$ is not equal to $0$, for any $m$ such that $d<2^m$.

Proof: Consider $f$ as a polynomial in $x_2, \ldots , x_n$ with coefficients from $GF(2)[x_1]$. Since the coefficients of $f$ are polynomials of degree at most $d$ they are not divisible by $x_1^{2^m} − x_1$ (the roots of which are the elements of $GF(2^m)$. Thus, there exists an element $\alpha \in GF(2^m)$ such that $f$ is nonzero when $x_1 = \alpha$. The proof is completed by induction on the variables.

Lemma. Let $f\in\mathbb F_2[x_1,\ldots,x_n]$, and let $d$ be the maximum degree of $f$ with respect to any variable. Then for any $m$ such that $2^m>d$ there exists $(a_1,\ldots,a_n)\in\mathbb F_{2^m}^n$ such that $f(a_1,\ldots,a_n)\ne0$.
Proof. Induction on $n\ge1$.
For $n=1$ the Lemma claims that there is $a\in\mathbb F_{2^m}$ such that $f(a)\ne0$ provided $2^m>d$. The reason is simple: the finite field $\mathbb F_{2^m}$ has $2^m$ elements, and $\deg f=d$. If $f(a)=0$ for all $a\in\mathbb F_{2^m}$ it follows $f=0$. (Over a field a non-zero polynomial can't have more roots than its degree.)
Now suppose $n>1$ and consider $f$ as a polynomial in $x_n$ with coefficients in $\mathbb F_2[x_1,\ldots,x_{n-1}]$. Write $$f(x_1,\ldots,x_{n})=f_0(x_1,\ldots,x_{n-1})+f_1(x_1,\ldots,x_{n-1})x_n+\cdots+f_r(x_1,\ldots,x_{n-1})x_n^r$$ with $r\le d$ and $f_r(x_1,\ldots,x_{n-1})\ne0$. By the induction hypothesis there is $(a_1,\ldots,a_{n-1})\in\mathbb F_{2^m}^{n-1}$ such that $f_r(a_1,\ldots,a_{n-1})\ne0$. Now look at $f(a_1,\dots,a_{n-1},x_n)$ which is a non-zero polynomial from $\mathbb F_2[x_n]$ of degree at most $d$, and apply the singe variable case (that is, the base case in our inductive proof) to find $a_n\in\mathbb F_{2^m}$ such that $f(a_1,\dots,a_{n-1},a_n)\ne0$.