The motivation for the lemma is the following problem:
Given a polynomial with coefficients in a field is the zero polynomial?
Depending on how is defined, it is sometimes easier to explicitly plug in values for the variables than it is to expand the polynomial completely and check that at least one of the coefficients is nonzero. For example, if is a sum of products of a large number of terms (e.g. the determinant of a matrix), expanding the product and evaluating the coefficients has exponential complexity in the degree of
If evaluating at a certain set of values gives a nonzero answer, the polynomial is not the zero polynomial; but if the evaluation at a randomly chosen set of values gives the polynomial may or may not be zero. The Schwartz-Zippel lemma gives an upper bound on the probability that the polynomial is zero in the latter case, which makes it quite useful for applications where a probabilistic test is sufficient.
Let be a field. Let be a polynomial of total degree , and suppose that is not the zero polynomial. Let be a finite subset of Let be chosen at random uniformly and independently from Then the probability that is
(1) If then the result follows from the fact that a polynomial of degree over a field has at most roots in the field. This follows from the division algorithm for and the existence of unique factorization into irreducibles in note that this fact is not true if is replaced by, say, the integers mod Equality holds in the inequality of the lemma if and only if has roots and contains all of them. The proof of the lemma, given in the last section, is an induction on so this argument for establishes the base case.
(2) Repeating the process of choosing elements of , say times, the probability that evaluates to every time is If and is large enough, this probability becomes vanishingly small. That is the point: if the process is repeated enough times--say, so that the probability that a nonzero polynomial will evaluate to zero every time becomes less than --and the given polynomial evaluates to zero every time, then we are quite confident that the polynomial is identically zero. This is not a deterministic algorithm--it is of course possible that is not identically zero and the process happened to make a one-in-a-million set of choices--but it is fast and practical.
(3) There are other, similar versions of the lemma. For instance, if each is chosen from a subset of and the degree of as a polynomial in is then another form of the lemma states that the probability that is at most
(4) If is a finite field, there is the added wrinkle that some polynomials which are not the zero polynomial nevertheless evaluate to everywhere. For instance, Fermat's little theorem implies that is one such polynomial in For polynomials like this, Schwartz-Zippel cannot be expected to give any meaningful information, and indeed this is because the degree is for any subset of That is, Schwartz-Zippel is only useful when the degree d of the polynomial is smaller than the size of the field
Let the integers mod Let Let Then Schwartz-Zippel says that the probability that is a zero of is Of the nine ordered pairs to consider, it turns out that five of them are zeroes: Indeed, So Schwartz-Zippel gives a nontrivial upper bound on the number of zeroes of a nonzero polynomial; for a degree-2 polynomial over there are at most
Let be a graph with an even number of vertices, say A perfect matching on is a choice of edges such that every vertex of is an endpoint of exactly one of the edges.
The natural computational problems about perfect matchings are as follows:
Given a graph how efficiently can we
(1) determine whether there is a perfect matching on
(2) find a perfect matching if one exists?
This section will describe a probabilistic algorithm that solves problem (1) using the Schwartz-Zippel lemma. The polynomial that governs the existence of a perfect matching turns out to be the determinant of a certain matrix defined below.
Let be a graph with vertices Let be the matrix with polynomial entries defined as follows: the entry is Then is called the Tutte matrix of
Note that the determinant of the Tutte matrix is a polynomial in the variables
Let be a square, with vertices labeled going around the square. Then the Tutte matrix of is
(Tutte, 1947) There is a perfect matching on if and only if the determinant of the Tutte matrix is not the zero polynomial.
Here is an outline of the proof. The details are left to the interested reader.
First, if there is a perfect matching on plug in if and are matched, and otherwise. It is not hard to show that the determinant evaluates to for those values of the variables, so it cannot be the zero polynomial. On the other hand, the proof that a perfect matching exists if the determinant is nonzero proceeds by writing the determinant as a signed sum of products of the entries and pairing off terms that cancel, until the only terms left correspond to groupings of the vertices into paths of even length that start and end at the same point. Any such path admits a perfect matching.
The determinant of the Tutte matrix of the square above is
So this polynomial can be checked probabilistically to be nonzero by Schwartz-Zippel over one can check that if it is nonzero over the rationals, it is nonzero over any finite field, because it contains a monomial with coefficient This solves problem (1).
For problem (2), the procedure in (1) can be converted into an inefficient algorithm: start with an edge, check whether the graph with that edge removed has a perfect matching (using Tutte matrices); if not, then that edge is part of any matching, so write it down and then delete those two vertices and all the associated edges and keep going; if so, then delete that edge and keep going.
This is obviously going to be very slow if the graph has a lot of edges. There is a version of this idea that is efficiently parallelized, but the details are beyond the scope of this wiki.
As discussed above, the proof is by induction on with the base case having been established.
Now suppose the result is true for variables. Write as a polynomial in the first variable: with not the zero polynomial.
By the inductive hypothesis, the probability that for a randomly uniformly independently chosen set of is If it is not zero, the polynomial will be nonzero, since the coefficient of is nonzero. By the base case, the probability that plugging in will give for a random uniform choice of is
To summarize, if then either or the nonzero degree- single-variable polynomial evaluates to at The probability of the first case is and the probability of the second case is where is the probability that is nonzero. So the probability that is as desired.