In mathematics, the Schwartz–Zippel lemma (also called the DeMillo–Lipton–Schwartz–Zippel lemma) is a tool commonly used in probabilistic polynomial identity testing.
Identity testing is the problem of determining whether a given multivariate polynomial is the 0-polynomial, the polynomial that ignores all its variables and always returns zero.
The lemma states that evaluating a nonzero polynomial on inputs chosen randomly from a large-enough set is likely to find an input that produces a nonzero output.
it was discovered independently by Jack Schwartz,[1] Richard Zippel,[2] and Richard DeMillo and Richard J. Lipton, although DeMillo and Lipton's version was shown a year prior to Schwartz and Zippel's result.
[3] The finite field version of this bound was proved by Øystein Ore in 1922.
Let be a non-zero polynomial of total degree d ≥ 0 over an integral domain R. Let S be a finite subset of R and let r1, r2, ..., rn be selected at random independently and uniformly from S. Then Equivalently, the Lemma states that for any finite subset S of R, if Z(P) is the zero set of P, then Proof.
The proof is by mathematical induction on n. For n = 1, P can have at most d roots by the fundamental theorem of algebra.
Now, assume that the theorem holds for all polynomials in n − 1 variables.
is of degree i (and thus not identically zero) so If we denote the event
, we have 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.
For example, is To solve this, we can multiply it out and check that all the coefficients are 0.
In general, a polynomial can be algebraically represented by an arithmetic formula or circuit.
Comparison of polynomials has applications for branching programs (also called binary decision diagrams).
A read-once branching program can be represented by a multilinear polynomial which computes (over any field) on {0,1}-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.
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 numbers n (and only prime numbers) satisfy the following polynomial identity: This is a consequence of the Frobenius endomorphism.
Agrawal and Biswas use a more sophisticated technique, which divides
by a random monic polynomial of small degree.
Therefore, finding very large prime numbers (on the order of (at least)
) becomes very important and efficient primality testing algorithms are required.
A subset D of E is called a matching if each vertex in V is incident with at most one edge in D. A matching is perfect if each vertex in V has exactly one edge that is incident to it in D. Create a Tutte matrix A in the following way: where The Tutte matrix determinant (in the variables xij,
) is then defined as the determinant of this skew-symmetric matrix which coincides with the square of the pfaffian of the matrix A and is non-zero (as polynomial) if and only if a perfect matching exists.
One can then use polynomial identity testing to find whether G contains a perfect matching.
There exists a deterministic black-box algorithm for graphs with polynomially bounded permanents (Grigoriev & Karpinski 1987).
[5] In the special case of a balanced bipartite graph on
In this case the pfaffian coincides with the usual determinant of the m × m matrix X (up to sign).
Currently, there is no known sub-exponential time algorithm that can solve this problem deterministically.
However, there are randomized polynomial algorithms whose analysis requires a bound on the probability that a non-zero polynomial will have roots at randomly selected test points.