Schwartz-Zippel lemma and testing polynomial identities
Encyclopedia
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 (or identically equal to 0). The input to the problem is an n-variable polynomial over a field
F. 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.
Determinant of a matrix with polynomial entries: Let
be the determinant
of the polynomial matrix
.
Currently, there is no known sub-exponential time algorithm
that can solve this problem deterministically. However, there are randomized polynomial algorithms for testing polynomial identities. The first of these algorithms was discovered independently by Jack Schwartz
and Richard Zippel.
Theorem 1 (Schwartz, Zippel). Let
be a non-zero polynomial of degree
d ≥ 0 over a field
, F. Let S be a finite subset of F and let r1, r2, ..., rn be selected randomly 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 n = 1, 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 n − 1 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 
. Now we randomly pick 
from 
. By the induction hypothesis, 
If 
,then 
is of degree 
so
If we denote the event
by 
and the event 
by 
, we have
from algorithms which are obtained to problems that can be reduced to the problem
of polynomial identity testing.
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 (also called binary decision diagram
s). 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
and 
.
, 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 numbers n (and only prime numbers) 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 [4]. 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
(on the order of (at least)
) becomes very important and efficient primality testing algorithms
are required.
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
Multivariate statistics
Multivariate statistics is a form of statistics encompassing the simultaneous observation and analysis of more than one statistical variable. The application of multivariate statistics is multivariate analysis...
polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
is the
0-polynomial (or identically equal to 0). The input to the problem is an n-variable polynomial over a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
F. 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.
Determinant of a matrix with polynomial entries: Let
be the determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
of the polynomial matrix
Polynomial matrix
A polynomial matrix or sometimes matrix polynomial is a matrix whose elements are univariate or multivariate polynomials. A λ-matrix is a matrix whose elements are polynomials in λ....
.
Currently, there is no known sub-exponential time algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that can solve this problem deterministically. However, there are randomized polynomial algorithms for testing polynomial identities. The first of these algorithms was discovered independently by Jack Schwartz
Jack Schwartz
Jacob Theodore "Jack" Schwartz was an American mathematician, computer scientist, and professor of computer science at the New York University Courant Institute of Mathematical Sciences. He was the designer of the SETL programming language and the NYU Ultracomputer...
and Richard Zippel.
Schwartz–Zippel lemma
It bounds the probability that a non-zero polynomial will have roots at randomly selected test points. The formal statement is as follows:Theorem 1 (Schwartz, Zippel). Let
be a non-zero polynomial of degree
Degree of a polynomial
The degree of a polynomial represents the highest degree of a polynominal's terms , should the polynomial be expressed in canonical form . The degree of an individual term is the sum of the exponents acting on the term's variables...
d ≥ 0 over a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
, F. Let S be a finite subset of F and let r1, r2, ..., rn be selected randomly from S. Then
In the single variable case, this follows directly from the fact that a polynomial of degree
Degree of a polynomial
The degree of a polynomial represents the highest degree of a polynominal's terms , should the polynomial be expressed in canonical form . The degree of an individual term is the sum of the exponents acting on the term's variables...
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
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
on n. For n = 1, 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 n − 1 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 . Now we randomly pick from . By the induction hypothesis, If ,then is of degree so
If we denote the event
by and the event by , we have |
 |
Applications
The importance of the Schwartz–Zippel Theorem and Testing Polynomial Identities followsfrom 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 (also called binary decision diagram
Binary decision diagram
In the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...
s). A read-once branching program can be represented by a multilinear polynomial
Multilinear polynomial
In algebra, a multilinear polynomial is a polynomial that is linear in each of its variables. In other words, no variable occurs to a power of 2 or higher; or alternatively, each monomial is a constant times a product of distinct variables...
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
and .Primality testing
Given, is a prime numberPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
?
A simple randomized algorithm developed by Manindra Agrawal
Manindra Agrawal
Manindra Agrawal is a professor at the department of computer science and engineering and the Dean of Resource, Planning and Generation at the Indian Institute of Technology, Kanpur. He is also the recipient of the first Infosys Prize for Mathematics.-Early life:Manindra Agrawal obtained a...
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
Frobenius endomorphism
In commutative algebra and field theory, the Frobenius endomorphism is a special endomorphism of commutative rings with prime characteristic p, an important class which includes finite fields. The endomorphism maps every element to its pth power...
.
Let
Then
iffIFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
n is prime. The proof can be found in [4]. 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
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. Therefore finding very large prime numbers
(on the order of (at least)
) becomes very important and efficient primality testing algorithmsare required.
Perfect matching
Let be a graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
of
vertices where is even. Does contain a perfect matching?Theorem 2 : A Tutte matrix
Tutte matrix
In graph theory, the Tutte matrix A of a graph G = is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once....
determinant is not a
-polynomial if and only ifIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
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 (in the variables xij, iDeterminantIn linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
of this skew-symmetric matrix which coincides with the square of the pfaffianPfaffianIn mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries. This polynomial is called the Pfaffian of the matrix, The term Pfaffian was introduced by who named them after Johann Friedrich Pfaff...
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.
In the special case of a balanced bipartite graphBipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
on
vertices this matrix takes the form of a block matrixBlock matrixIn the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a matrix broken into sections called blocks. Looking at it another way, the matrix is written in terms of smaller matrices. We group the rows and columns into adjacent 'bunches'. A partition is the rectangle...
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.
External links
- The Curious History of the Schwartz–Zippel Lemma, by Richard J. LiptonRichard J. LiptonRichard Jay "Dick" Lipton is an American computer scientist who has worked in computer science theory, cryptography, and DNA computing. Lipton is presently Associate Dean of Research, Professor, and the Frederick G...
-
-
-
