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, 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 and proof of the lemma Theorem 1 (Schwartz, Zippel). Let
P ∈ R [ x 1 , x 2 , … , x n ] {\displaystyle P\in R[x_{1},x_{2},\ldots ,x_{n}]}
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
Pr [ P ( r 1 , r 2 , … , r n ) = 0 ] ≤ d | S | . {\displaystyle \Pr[P(r_{1},r_{2},\ldots ,r_{n})=0]\leq {\frac {d}{|S|}}.}
Equivalently, the Lemma states that for any finite subset S of R, if Z(P) is the zero set of P, then
| Z ( P ) ∩ S n | ≤ d ⋅ | S | n − 1 . {\displaystyle |Z(P)\cap S^{n}|\leq d\cdot |S|^{n-1}.}
Proof. The proof is by mathematical induction on n. For n = 1, P can have at most d roots. This gives us the base case. Now, assume that the statement holds for all polynomials in n − 1 variables. We can then consider P to be a polynomial in x1 by writing it as
P ( x 1 , … , x n ) = ∑ i = 0 d x 1 i P i ( x 2 , … , x n ) . {\displaystyle P(x_{1},\dots ,x_{n})=\sum _{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\dots ,x_{n}).}
Since P is not identically 0, there is some i such that P i {\displaystyle P_{i}} is not identically 0. Take the largest such i. Then deg P i ≤ d − i {\displaystyle \deg P_{i}\leq d-i} , since the degree of x 1 i P i {\displaystyle x_{1}^{i}P_{i}} is at most d. Now we randomly pick r 2 , … , r n {\displaystyle r_{2},\dots ,r_{n}} from S. By the induction hypothesis, Pr [ P i ( r 2 , … , r n ) = 0 ] ≤ d − i | S | . {\displaystyle \Pr[P_{i}(r_{2},\ldots ,r_{n})=0]\leq {\frac {d-i}{|S|}}.}
If P i ( r 2 , … , r n ) ≠ 0 {\displaystyle P_{i}(r_{2},\ldots ,r_{n})\neq 0} , then P ( x 1 , r 2 , … , r n ) {\displaystyle P(x_{1},r_{2},\ldots ,r_{n})} is of degree i (and thus not identically zero) so
Pr [ P ( r 1 , r 2 , … , r n ) = 0 | P i ( r 2 , … , r n ) ≠ 0 ] ≤ i | S | . {\displaystyle \Pr[P(r_{1},r_{2},\ldots ,r_{n})=0|P_{i}(r_{2},\ldots ,r_{n})\neq 0]\leq {\frac {i}{|S|}}.}
If we denote the event P ( r 1 , r 2 , … , r n ) = 0 {\displaystyle P(r_{1},r_{2},\ldots ,r_{n})=0} by A, the event P i ( r 2 , … , r n ) = 0 {\displaystyle P_{i}(r_{2},\ldots ,r_{n})=0} by B, and the complement of B by B c {\displaystyle B^{c}} , we have
Pr [ A ] = Pr [ A ∩ B ] + Pr [ A ∩ B c ] = Pr [ B ] Pr [ A | B ] + Pr [ B c ] Pr [ A | B c ] ≤ Pr [ B ] + Pr [ A | B c ] ≤ d − i | S | + i | S | = d | S | {\displaystyle {\begin{aligned}\Pr[A]&=\Pr[A\cap B]+\Pr[A\cap B^{c}]\\&=\Pr[B]\Pr[A|B]+\Pr[B^{c}]\Pr[A|B^{c}]\\&\leq \Pr[B]+\Pr[A|B^{c}]\\&\leq {\frac {d-i}{|S|}}+{\frac {i}{|S|}}={\frac {d}{|S|}}\end{aligned}}}
Remark. The Schwartz-Zippel lemma is tight in the following sense. Let S ⊆ R {\displaystyle S\subseteq R} be a finite subset and let d ≤ | S | {\displaystyle d\leq |S|} . Choose any d {\displaystyle d} distinct elements s 1 , … , s d {\displaystyle s_{1},\ldots ,s_{d}} from S {\displaystyle S} . Then define P ∈ R [ x 1 , … , x n ] {\displaystyle P\in R[x_{1},\ldots ,x_{n}]} by P ( x 1 , … , x n ) = ∏ i = 1 d ( x 1 − s i ) {\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{i=1}^{d}(x_{1}-s_{i})} . Let r 1 , … , r n {\displaystyle r_{1},\ldots ,r_{n}} be selected uniformly at random from S {\displaystyle S} . Then Pr [ P ( r 1 , … , r n ) = 0 ] = Pr [ r 1 ∈ { s 1 , … , s d } ] = d | S | {\displaystyle \Pr[P(r_{1},\ldots ,r_{n})=0]=\Pr[r_{1}\in \{s_{1},\ldots ,s_{d}\}]={\frac {d}{|S|}}} so that the bound stated in the Schwartz-Zippel lemma is exactly matched.
Applications The Schwartz–Zippel lemma is used to obtain algorithms for problems which are reducible to polynomial identity testing.
Zero testing One of the most common applications of the Schwartz-Zippel lemma in theoretical computer science is to testing whether a polynomial (given in terms of an arithmetic circuit or formula) is identically 0. For example, consider asking whether the arithmetic formula below is identically 0
( x 1 + 3 x 2 − x 3 ) ( 3 x 1 + x 4 − 1 ) ⋯ ( x 7 − x 100 ) ≡ 0 ? {\displaystyle (x_{1}+3x_{2}-x_{3})(3x_{1}+x_{4}-1)\cdots (x_{7}-x_{100})\equiv 0\ ?}
To solve this problem deterministically, we can multiply all the terms and check whether the coefficient of every monomial is nonzero. However, this can take exponential time in the number of variables n {\displaystyle n} since a degree d {\displaystyle d} polynomial in n {\displaystyle n} variables has up to ( n + d d ) {\displaystyle {\binom {n+d}{d}}} monomials. Instead, we can evaluate the polynomial at a random tuple of points over a sufficiently large field and if the result is indeed 0, we can use the Schwartz-Zippel lemma to conclude the formula is identically 0 with high probability.
Comparison of two polynomials Given a pair of polynomials p 1 ( x ) {\displaystyle p_{1}(x)} and p 2 ( x ) {\displaystyle p_{2}(x)} , is
p 1 ( x ) ≡ p 2 ( x ) {\displaystyle p_{1}(x)\equiv p_{2}(x)} ? This problem, also known as polynomial identity testing, can be solved by reducing it to the above problem of testing whether a polynomial is identically 0. Specifically, p 1 ( x ) ≡ p 2 ( x ) {\displaystyle p_{1}(x)\equiv p_{2}(x)} is equivalent to
[ p 1 ( x ) − p 2 ( x ) ] ≡ 0. {\displaystyle [p_{1}(x)-p_{2}(x)]\equiv 0.}
Hence if we can determine that
p ( x ) ≡ 0 , {\displaystyle p(x)\equiv 0,}
where
p ( x ) = p 1 ( x ) − p 2 ( x ) , {\displaystyle p(x)=p_{1}(x)\;-\;p_{2}(x),}
then we can determine whether the two polynomials are equivalent. 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. Comparison of two polynomials (and therefore testing polynomial identities) 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 p A ( x , y ) {\displaystyle p_{A}(x,y)} and p B ( x , y ) {\displaystyle p_{B}(x,y)} .
Primality testing Given n ∈ N {\displaystyle n\in \mathbb {N} } , is n {\displaystyle n} a prime number? A simple randomized algorithm developed by Manindra Agrawal and Somenath Biswas can determine probabilistically whether n {\displaystyle n} 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:
( 1 + z ) n = 1 + z n ( mod n ) . {\displaystyle (1+z)^{n}=1+z^{n}({\mbox{mod}}\;n).}
This is a consequence of the Frobenius endomorphism. Let
P n ( z ) = ( 1 + z ) n − 1 − z n . {\displaystyle {\mathcal {P}}_{n}(z)=(1+z)^{n}-1-z^{n}.}
Then P n ( z ) = 0 ( mod n ) {\displaystyle {\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)} iff n is prime. The proof can be found in [4]. However, since this polynomial has degree n {\displaystyle n} , where n {\displaystyle n} may or may not be a prime, the Schwartz–Zippel method would not work. Agrawal and Biswas use a more sophisticated technique, which divides
P n {\displaystyle {\mathcal {P}}_{n}} by a random monic polynomial of small degree. The AKS algorithm uses a similar technique but runs in deterministic polynomial time. 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 (on the order of (at least) 10 350 ≈ 2 1024 {\displaystyle 10^{350}\approx 2^{1024}} ) becomes very important and efficient primality testing algorithms are required.
Perfect matching Let G = ( V , E ) {\displaystyle G=(V,E)} be a graph of n vertices where n is even. Does G contain a perfect matching? Theorem 2 (Tutte 1947): A Tutte matrix determinant is not a 0-polynomial if and only if there exists a perfect matching. 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:
A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n ] {\displaystyle A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1{\mathit {n}}}\\a_{21}&a_{22}&\cdots &a_{2{\mathit {n}}}\\\vdots &\vdots &\ddots &\vdots \\a_{{\mathit {n}}1}&a_{{\mathit {n}}2}&\ldots &a_{\mathit {nn}}\end{bmatrix}}}
where
a i j = { x i j if ( i , j ) ∈ E and i < j − x j i if ( i , j ) ∈ E and i > j 0 otherwise . {\displaystyle a_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i<j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i>j\\0\;\;\;\;{\mbox{otherwise}}.\end{cases}}}
The Tutte matrix determinant (in the variables xij, i < j {\displaystyle i<j} ) 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). In the special case of a balanced bipartite graph on n = m + m {\displaystyle n=m+m} vertices this matrix takes the form of a block matrix
A = ( 0 X − X t 0 ) {\displaystyle A={\begin{pmatrix}0&X\\-X^{t}&0\end{pmatrix}}}
if the first m rows (resp. columns) 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 (up to sign). Here X is the Edmonds matrix.
Notes
References
External links The Curious History of the Schwartz–Zippel Lemma, by Richard J. Lipton