In mathematics, the Schwartz–Zippel lemma is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomial is the 0-polynomial. It was discovered independently by Jack Schwartz, Richard Zippel, and Richard DeMillo and Richard J. Lipton, although DeMillo and Lipton's version was shown a year prior to Schwartz and Zippel's result. The finite field version of this bound was proved by Øystein Ore in 1922.
Statement of the lemma
The input to the problem is an n-variable polynomial over a fieldF. It can occur in the following forms:
Algebraic form
For example, is To solve this, we can multiply it out and check that all the coefficients are 0. However, this takes exponential time. In general, a polynomial can be algebraically represented by an arithmetic formula or circuit.
Let be the determinant of the polynomial matrix. Currently, there is no known sub-exponential timealgorithm that can solve this problem deterministically. However, there are randomized polynomial algorithms for testing polynomial identities. Their analysis usually requires a bound on the probability that a non-zero polynomial will have roots at randomly selected test points. The Schwartz–Zippel lemma provides this as follows: Theorem 1. Let be a non-zero polynomial of total degreeover a field F. Let S be a finite subset of F and letbe selected at random independently and uniformly from S. Then In the single variable case, this follows directly from the fact that a polynomial of degree d can have no more than d roots. It seems logical, then, to think that a similar statement would hold for multivariable polynomials. This is, in fact, the case. Proof. The proof is by mathematical induction on n. For, as was mentioned before, P can have at most d roots. This gives us the base case. Now, assume that the theorem holds for all polynomials in variables. We can then consider P to be a polynomial in x1 by writing it as Since is not identically 0, there is some such that is not identically 0. Take the largest such. Then, since the degree of is at most d. Now we randomly pick from. By the induction hypothesis, If, then is of degree so If we denote the event by, the event by, and the complement of by, we have
Applications
The importance of the Schwartz–Zippel Theorem and Testing Polynomial Identities follows from algorithms which are obtained to problems that can be reduced to the problem of polynomial identity testing.
Comparison of two polynomials
Given a pair of polynomials and, is
This problem can be solved by reducing it to the problem of polynomial identity testing. It is equivalent to checking if Hence if we can determine that
where
then we can determine whether the two polynomials are equivalent. Comparison of polynomials has applications for branching programs. A read-once branching program can be represented by a multilinear polynomial which computes on -inputs the same Boolean function as the branching program, and two branching programs compute the same function if and only if the corresponding polynomials are equal. Thus, identity of Boolean functions computed by read-once branching programs can be reduced to polynomial identity testing. Comparison of two polynomials also has applications in 2D-compression, where the problem of finding the equality of two 2D-texts A and B is reduced to the problem of comparing equality of two polynomials and.
Primality testing
Given, is a prime number? A simple randomized algorithm developed by Manindra Agrawal and Somenath Biswas can determine probabilistically whether is prime and uses polynomial identity testing to do so. They propose that all prime numbersn satisfy the following polynomial identity: This is a consequence of the Frobenius endomorphism. Let Then iff n is prime. The proof can be found in . However, since this polynomial has degree, and since may or may not be a prime, the Schwartz–Zippel method would not work. Agrawal and Biswas use a more sophisticated technique, which divides by a random monic polynomial of small degree. Prime numbers are used in a number of applications such as hash table sizing, pseudorandom number generators and in key generation for cryptography. Therefore, finding very large prime numbers becomes very important and efficient primality testing algorithms are required.
Perfect matching
Let be a graph of vertices where is even. Does contain a perfect matching? Theorem 2 : A Tutte matrix determinant is not a -polynomial if and only if there exists a perfect matching. A subset of is called a matching if each vertex in is incident with at most one edge in. A matching is perfect if each vertex in has exactly one edge that is incident to it in. Create a Tutte matrix in the following way: where The Tutte matrix determinant is then defined as the determinant of this skew-symmetric matrix which coincides with the square of the pfaffian of the matrixA and is non-zero if and only if a perfect matching exists. One can then use polynomial identity testing to find whether contains a perfect matching. There exists a deterministic black-box algorithm for graphs with polynomially bounded permanents. In the special case of a balanced bipartite graph on vertices this matrix takes the form of a block matrix if the first m rows are indexed with the first subset of the bipartition and the last m rows with the complementary subset. In this case the pfaffian coincides with the usual determinant of the m × m matrix X. Here X is the Edmonds matrix.
