3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

This is known as the Schwartz–Zippel lemma, and has several proofs. Perhaps you'll find the account in Wikipedia helpful (it contains the same proof as yours).

$\endgroup$
  • $\begingroup$ yes I have read it but I am not able to understand it quite well. :( $\endgroup$ – MA Jadoon Jun 2 '15 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.