HOME

TheInfoList



OR:

In mathematics, the Schwartz–Zippel lemma (also called the DeMillo–Lipton–Schwartz–Zippel lemma) is a tool commonly used in probabilistic
polynomial identity testing In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and ...
. Identity testing is the problem of determining whether a given multivariate
polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
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 Øystein Ore (7 October 1899 – 13 August 1968) was a Norwegian mathematician known for his work in ring theory, Galois connections, graph theory, and the history of mathematics. Life Ore graduated from the University of Oslo in 1922, with a ...
in 1922.Ö. Ore, Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I (1922), no. 7, 15 pages.


Statement and proof of the lemma

Theorem 1 (Schwartz, Zippel). ''Let'' : P\in R _1,x_2,\ldots,x_n/math> ''be a non-zero polynomial of total degree'' ''over an
integral domain In mathematics, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibilit ...
 R. Let S be a finite subset of R and let'' ''be selected at random independently and uniformly from S. Then'' : \Pr (r_1,r_2,\ldots,r_n)=0leq\frac. ''Equivalently, the Lemma states that for any finite subset S of R, if Z(P) is the zero set of P, then'' : , Z(P) \cap S^n , \leq d \cdot , S, ^. ''Proof.'' The proof is by
mathematical induction Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots  all hold. This is done by first proving a ...
on ''n''. For , ''P'' can have at most ''d'' roots by the
fundamental theorem of algebra The fundamental theorem of algebra, also called d'Alembert's theorem or the d'Alembert–Gauss theorem, states that every non-constant polynomial, constant single-variable polynomial with Complex number, complex coefficients has at least one comp ...
. 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 ''x''1 by writing it as : P(x_1,\dots,x_n)=\sum_^d x_1^i P_i(x_2,\dots,x_n). Since is not identically 0, there is some such that P_i is not identically 0. Take the largest such . Then \deg P_i\leq d-i, since the degree of x_1^iP_i is at most d. Now we randomly pick r_2,\dots,r_n from . By the induction hypothesis, \Pr _i(r_2,\ldots,r_n)=0leq\frac. If P_i(r_2,\ldots,r_n)\neq 0, then P(x_1,r_2,\ldots,r_n) is of degree (and thus not identically zero) so ::: \Pr P_i(r_2,\ldots,r_n)\neq 0leq\frac. If we denote the event P(r_1,r_2,\ldots,r_n)=0 by , the event P_i(r_2,\ldots,r_n)=0 by , and the complement of by B^c, we have :\begin \Pr & =\Pr \cap B\Pr \cap B^c\\ &=\Pr Pr B\Pr ^cPr B^c\\ &\leq \Pr \Pr B^c\\ &\leq \frac+\frac=\frac \end


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 In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and ...
.


Zero testing

One of the most common applications of the Schwartz-Zippel lemma in
theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...
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 + 3x_2 - x_3)(3x_1 + x_4 - 1) \cdots (x_ - x_) \equiv 0\ ? To solve deterministically, we can multiply all the terms and check whether the coefficient of every possible product of variables is  0. However, this can take
exponential time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
in the number of variables $n$ since there may be at most $2^n$ product terms. Instead, we can evaluate the polynomial at a random tuple of points over a sufficiently large field (which can be done in linearly-many arithmetic operations in the length of the formula) and if the result is indeed 0, we can use the SZ lemma to conclude the formula is identically 0 with high probability.


Comparison of two polynomials

''Given a pair of polynomials p_1(x) and p_2(x), is'' ::: p_1(x) \equiv p_2(x)? This problem can be solved by reducing it to the problem of polynomial identity testing. It is equivalent to checking if ::: _1(x) - p_2(x)\equiv 0. Hence if we can determine that ::: p(x) \equiv 0, where ::: 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 diagram In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Un ...
s). A read-once branching program can be represented by a multilinear polynomial which computes (over any field) on -inputs the same
Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...
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) and p_B(x,y).


Primality testing

''Given n \in \mathbb, is n a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
?'' A simple randomized algorithm developed by
Manindra Agrawal Manindra Agrawal (born 20 May 1966) is an Indian computer scientist and director of Indian Institute of Technology, Kanpur. He is also a professor at the Department of Computer Science and Engineering at the Indian Institute of Technology, Ka ...
and Somenath Biswas can determine probabilistically whether 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 (\mbox\;n). This is a consequence of the
Frobenius endomorphism In commutative algebra and field theory (mathematics), field theory, the Frobenius endomorphism (after Ferdinand Georg Frobenius) is a special endomorphism of commutative Ring (mathematics), rings with prime number, prime characteristic (algebra), ...
. Let ::: \mathcal_n(z) = (1+z)^n - 1 -z^n. Then \mathcal_n(z) = 0\;(\mbox\;n) ''
iff In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either both ...
n is prime''. The proof can be found in However, since this polynomial has degree n, where 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 \mathcal_n by a random monic polynomial of small degree. Prime numbers are used in a number of applications such as hash table sizing,
pseudorandom A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Pseudorandom number generators are often used in computer programming, as tradi ...
number generators and in key generation for
cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
. Therefore, finding very large prime numbers (on the order of (at least) 10^ \approx 2^) becomes very important and efficient primality testing algorithms are required.


Perfect matching

''Let G = (V, E) be a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
of vertices where is even. Does contain a
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
?'' Theorem 2 : ''A Tutte matrix determinant is not a -polynomial
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
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: ::: A = \begin a_ & a_ & \cdots & a_ \\ a_ & a_ & \cdots & a_ \\ \vdots & \vdots & \ddots & \vdots \\ a_ & a_ & \ldots & a_ \end where ::: a_ = \begin x_\;\;\mbox\;(i,j) \in E \mbox ij\\ 0\;\;\;\;\mbox. \end The Tutte matrix determinant (in the variables ''xij'', ) is then defined as the
determinant In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
of this
skew-symmetric matrix In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition In terms of the entries of the matrix, if a ...
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 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 In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
on n =m + m vertices this matrix takes the form of a
block matrix In mathematics, a block matrix or a partitioned matrix is a matrix that is interpreted as having been broken into sections called blocks or submatrices. Intuitively, a matrix interpreted as a block matrix can be visualized as the original matrix w ...
::: A = \begin 0 & X \\ -X^t & 0 \end 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.


Determinant of a matrix with polynomial entries

Let : p(x_1,x_2, \ldots, x_n) be the
determinant In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...
of the polynomial matrix. Currently, there is no known sub-exponential time
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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.


Notes


References

* * * * Moshkovitz, Dana (2010). An Alternative Proof of The Schwartz-Zippel Lemma. * * * * * * *


External links


The Curious History of the Schwartz–Zippel Lemma
by Richard J. Lipton {{DEFAULTSORT:Schwartz-Zippel lemma Theorems about polynomials Computer algebra Lemmas in algebra Mathematical theorems in theoretical computer science