Schwartz-Zippel lemma and testing polynomial identities

Schwartz-Zippel lemma and testing polynomial identities

Polynomial identity testing is the problem of determining whether a given multivariate polynomial is the0-polynomial or identically equal to 0. The input to the problem is an "n"-variable polynomial over a fieldF. It can occur in the following forms:

; Algebraic form : e.g. Is (x_1 + 3x_2 - x_3)(3x_1 + x_4 - 1) cdots (x_7 - x_2) equiv 0. To solve this, we can multiply it out and check that all the co-efficients are 0. However, this takes exponential time.; Determinant of a matrix with polynomial entries: Let p(x_1,x_2, ldots, x_n) be the determinant of the polynomial matrix.; Read-once branching program : also called binary decision diagrams.

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 Schwartz and Zippel. [cite web
url=http://historical.ncstrl.org/tr/ps/cornellcs/TR89-965.ps
title= An Explicit Separation of Relativised Random Polynomial Time and Relativised Deterministic Polynomial Time
accessdate= 2008-06-15
author= Richard Zippel
year= 1989
month= February
format= ps
]

Schwartz-Zippel theorem

The Schwartz-Zippel theorem is a tool commonly used in probabilistic polynomial identity testing. 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 Pin F [x_1,x_2,ldots,x_n] be a non-zero polynomial of degree dgeq0 over a field, F. Let mathrm{S} be a finite subset of F and let r_1,r_2,ldots,r_n be selected randomly from S. Then"

::: Pr [P(r_1,r_2,ldots,r_n)=0] leqfrac{d}

If we denote the event P(r_1,r_2,ldots,r_n)=0 by A and the event P_i(r_2,ldots,r_n)=0 by B, we have

=frac{d}

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 problemof polynomial identity testing.

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

::: [p_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 two polynomials (and therefore testing polynomial identities) also hasapplications in 2D-compression, where the problem of finding the equality of two2D-texts "A" and "B" is reduced to the problemof comparing equality of two polynomials Poly_A(x,y) and Poly_B(x,y)

Primality testing

"Given n in mathbb{Z^+}, is n a prime number?"

A simple randomized algorithm developed by Manindra Agrawal and Somenath Biswas can determine probabilisticallywhether n is prime and uses polynomial identity testing to do so.

They propose that all prime numbers "n" (and only prime numbers) satisfy the followingpolynomial identity:

::: (1+z)^n = 1+z^n (mbox{mod};n).

This is a consequence of the Frobenius Homomorphism.

Let

::: mathcal{P}_n(z) = (1+z)^n - 1 -z^n.,

Then 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, and since 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{P}_n by a random monic polynomial of small degree.

Prime numbers are used in a number of applications such as hash table sizing, pseudorandom numbergenerators and in key generation for cryptography. Therefore finding very large prime numbers(on the order of 10^{10,000}) becomes very important and efficient primality testing algorithmsare required.

Perfect matching

"Let G = (V, E) be a graph of mathrm{n} vertices where mathrm{n} is even. Does mathrm{G} contain a perfect matching?"

Theorem 2 (Tutte): "A Tutte matrix determinant is not a mathrm{0}-polynomial if and only if there exists a perfect matching."

A subset mathrm{D} of mathrm{E} is called a matching if each vertex in mathrm{V} is incident with at most one edge in mathrm{D}. A matching is perfect if each vertex in mathrm{V} has exactly one edge that is incident to it in mathrm{D}. Create a "Tutte matrix" mathrm{A} in the following way:

::: A = egin{bmatrix} a_{11} & a_{12} & cdots & a_{1mathit{n \ a_{21} & a_{22} & cdots & a_{2mathit{n \ vdots & vdots & ddots & vdots \ a_{mathit{n}1} & a_{mathit{n}2} & ldots & a_{mathit{nn end{bmatrix}

where

::: a_{ij} = egin{cases} x_{ij};;mbox{if};(i,j) in E mbox{ and } ij\0;;;;mbox{otherwise} end{cases}

The Tutte matrix determinant (in the variables "xij", "ideterminant 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 mathrm{G} contains a perfect matching.

In the special case of a balanced bipartite graph on n =m + m vertices this matrix takes the form of a block matrix ::: A = egin{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.

References

* cite book
last=Rudich
first=Steven
editor=AMS
title=Computational Complexity Theory
origyear=2004
origmonth=September
series= IAS/Park City Mathematics Series
volume=10
isbn= 0-8218-2872-X

* cite book
last=Zippel
first=Richard
editor=Springer
title=Effective Polynomial Computation
origyear=1993
url=http://www.springer.com/computer/mathematics/book/978-0-7923-9375-7
edition=
series=The Springer International Series in Engineering and Computer Science
volume=241
isbn= 978-0-7923-9375-7

* cite journal
url= http://www.egr.unlv.edu/~larmore/Research/pattern.ps.gz
title= On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts
accessdate= 2008-06-15
author= Piotr Berman
coauthors= Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski and Wojciech Rytter
format= ps
journal= Journal of Computer and System Sciences
volume=65
pages=332–350
doi= 10.1006/jcss.2002.1852
year= 2002

* cite journal
url= http://ieeexplore.ieee.org/iel5/6604/17631/00814592.pdf
title= Primality and Identity Testing via Chinese Remaindering
accessdate= 2008-06-15
author= Manindra Agrawa
coauthors= Somenath Biswas
date= 2003-02-21
format= pdf
journal= Journal of the ACM (JACM)
pages=429–443

* cite journal
url= http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf
title= The factorization of linear graphs
accessdate= 2008-06-15
author= W.T. Tutte
authorlink=W. T. Tutte
year= 1947
month= April
volume=22
journal=J. London Math. Soc.
pages=107–111
doi=10.1112/jlms/s1-22.2.107

* cite journal
url= http://delivery.acm.org/10.1145/330000/322225/p701-schwartz.pdf
title= Fast probabilistic algorithms for verification of polynomial identities
accessdate= 2008-06-15
author= J. Schwartz
year= 1980
month= October
format= pdf
journal= Journal of the ACM
pages=701–717
doi= 10.1145/330000/322225/p701-schwartz.pdf
doi_brokendate= 2008-07-06


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Computer algebra system — A computer algebra system (CAS) is a software program that facilitates symbolic mathematics. The core functionality of a CAS is manipulation of mathematical expressions in symbolic form. Contents 1 Symbolic manipulations 2 Additional capabilities …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”