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. ).
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.
Are there any other proofs?
 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/.
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.