The fact that a univariate polynomial over a field of degree has at most zeroes is well known. It follows from the so called Factor theorem, if and only if . But what about a polynomial in -variables, , where ?

When is an infinite field, say or , then the number of zeroes would almost always be infinite. For example, has infinitely many zeroes in . But things are a bit more interesting when is a finite field. We have the following important result bounding the number of zeroes of a polynomial:

(Schwartz-Zippel lemma.) Let be a finite field of size , let , and let be a non-zero polynomial of degree at most . Let us denote the set of zeroes of in by . Then

.

For the first proof, which is chronologically the latest proof, we need an important lemma,

Lemma 1.If is a non-zero polynomial for all then there exists an such that .

This can be easily proved by induction on . Now, since the degree of is at most , the degree of each variable is also at most . We can safely assume that since otherwise the bound is trivial. So, let in be such that .

A line in is a collection of points of the form where and are fixed points of and runs over (think of as the direction vector of the line). From this it should be clear that a line has precisely points on it and that intersects the set either in all points (when is zero) or at most points. Now consider the set of lines through , . Every point of belongs to some line of , and in fact partitions the set . Since each line has points on it we have

Because each line in has a point on it that doesn’t lie in , the point , it intersects in at most points. Therefore we have . This is asymptotically close to the bound given in Schwartz-Zippel lemma but not the bound we need. A similar idea, which is in fact more similar than it looks right away, leads to the correct bound (cf. [1]).

The points of can be partitioned by the set of parallel lines in the direction of a given vector . Since each line has points on it, we have . Now, if we can choose a direction so that no line of is completely contained in then we are essentially done as each of these lines would intersect in at most points. Let be of degree and write as where is the degree part of . The coefficient of in the univariate polynomial is .

Therefore, if we pick to be a vector for which is not equal to zero then we can ensure that none of the lines in are contained in . But why can we choose such a (non-zero) ?

This again follows from the important lemma we discussed before. Since is a homogenous non-zero polynomial of degree , by Lemma 1 there must be a non-zero with (non-zero because ).

**Remark: **In Moshkovitz’s proof we are also fixing a point that doesn’t lie in , a point at infinity. But the crucial difference is that instead of looking at all lines through we are only looking at those that do not lie in the hyperplane at infinity, i.e., the set of parallel lines that determine this point . The accepted answer here mistakenly assumes that the hyperplane at infinity has size and hence doesn’t really give an alternate proof.

Now, we discuss the original proof which follows by induction on . This has an additional advantage that it doesn’t require Lemma 1.

For the lemma reduces to the factor theorem, so let . For induction to work, we would like to pick a value for variable to get a polynomial of lower degree, but the only problem is that this polynomial might become . So, let be the (possibly empty) set of elements in for which divides , which are precisely the values of for which becomes zero.

Then we can write Since we have . Let belong to , so that does not divide . Then the polynomial must be non-zero. Since is a non-zero polynomial of degree at most in variables, we can apply the induction hypothesis to conclude that the number of zeroes of is at most .

Now we can partition the set (zeroes of ) in two parts: those zeroes for which the value of belongs to and those for which it doesn’t. We get zeroes in the first case because for every we can assign to be and every other to be any element of . In the second case we have zeroes.

Therefore,

Are there any other proofs?

See this for a nice discussion on Moshkovit’s proof and this for an historical account of the Schwartz-Zippel lemma by Robert Lipton.

[1] Dana Moshkovitz. An alternative proof of the schwartz-zippel lemma. *Electronic Colloquium on Computational Complexity*, 2010. Available at http://eccc.hpi-web.de/report/2010/096/.

* this is a part of notes on the polynomial method that I am working on with Abhishek Khetan and Aditya Potukuchi

**Edit (19 April 2015): ** This Lemma dates back to 1922, originally proved by Ore. See the chapter notes at pg 320, on Theorem 6.13, in “Finite Fields” by Lidl and Niederreiter. It also appears as a special case of a more general result in the PhD thesis of Daniel Edwin Erickson from 1974, “Counting Zeros of Polynomials over Finite Fields” :http://thesis.library.caltech.edu/4061/1/Erickson_de_1974.pdf. Put in Theorem 5.1.

**Edit (20 September 2015): **In our new paper we have shown connections between a result of Alon-Furedi and Schwartz-Zippel lemma(s), which in particular, gives us several new proofs of this result: arXiv:1508.06020. So yes, there are many other proofs of the Schwartz-Zippel lemma.

Pingback: The Kakeya problem | Anurag's Math Blog

Can we prove it as follows or do I miss something or it is the same as some of above arguments?

Induction in $n$ and $d

There seems to be a typo, or perhaps I don’t understand you properly. Could you say something more about the induction you have in mind? How different would it be from the inductive proof above?

Sorry, it probably contained some typo which deleted a post almost completely. I mean the following. If density of zeros exceeds $d/q$, it exceeds $d/q$ on some section $x_n=a$. It follows (induction in $n$) that $f$ restricted to this section is identical zero, i.e. $f=(x_n-a)g$. Next, density of zeros of $g$ does not exceed $(d-1)/q$. It looks similar to above, but looks shorter and needs only one multiple $x_n-a$.

So, you are doing induction on the degree d. Nice! I don’t think it’s any shorter, but it certainly looks like a better proof. Perhaps something like this can also be done by taking any other set of parallel hyperplanes that cover the whole space.

Yes, I induct both on $n$ and on $d$ for fixed $n$. It works for the products $\prod_{i=1}^n A_i$ with the same sizes $|A_i|=q$ in any field, (I guess that other proofs work too), but probably for some more general situations aswell. For example, the same argument allows to prove that polynomial $f(x,y,z)\in K[x,y,z]$ of degree $n$, which vanishes on all points $(x_i,y_j,z_k)$, $0\leq i,j,k; i+j+k \leq n$, vanishes on $K^3$ (here $\{x_0,\dots,x_n\}$, $\{y_0,y_1,\dots,y_n\}, \{z_0,\dots,z_n\}$ are sets of cardinality $n+1$ in a field $K$). The same for higher number of variables, 3 is chosen for simplicity of notations.

To be rigorous: “vanishes on $K^3$” must be replaced to “vanishes identically” (as polynomial).

By the way, how do you type latex code?

Replace ” in “latex e^{i \pi}” by $. So, . https://en.support.wordpress.com/latex/