# Schwartz–Zippel lemma

Now we randomly pick {displaystyle r_{2},dots ,r_{n}} from S. By the induction hypothesis, {displaystyle Pr[P_{i}(r_{2},ldots ,r_{n})=0]leq {frac {d-i}{|S|}}.} If {displaystyle P_{i}(r_{2},ldots ,r_{n})neq 0} , then {displaystyle P(x_{1},r_{2},ldots ,r_{n})} is of degree i (and thus not identically zero) so {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 {displaystyle P(r_{1},r_{2},ldots ,r_{n})=0} by A, the event {displaystyle P_{i}(r_{2},ldots ,r_{n})=0} by B, and the complement of B by {displaystyle B^{c}} , we have {displaystyle {begin{aligned}Pr[A]&=Pr[Acap B]+Pr[Acap 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}}} 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.

Zero testing For example, is {displaystyle (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 coefficients are 0. However, this takes exponential time. In general, a polynomial can be algebraically represented by an arithmetic formula or circuit.

Comparison of two polynomials Given a pair of polynomials {displaystyle p_{1}(x)} and {displaystyle p_{2}(x)} , is {displaystyle 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 {displaystyle [p_{1}(x)-p_{2}(x)]equiv 0.} Hence if we can determine that {displaystyle p(x)equiv 0,} where {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 {displaystyle p_{A}(x,y)} and {displaystyle p_{B}(x,y)} .

Primality testing Given {displaystyle nin mathbb {N} } , is {displaystyle n} a prime number?

A simple randomized algorithm developed by Manindra Agrawal and Somenath Biswas can determine probabilistically whether {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: {displaystyle (1+z)^{n}=1+z^{n}({mbox{mod}};n).} This is a consequence of the Frobenius endomorphism.

Let {displaystyle {mathcal {P}}_{n}(z)=(1+z)^{n}-1-z^{n}.} Then {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 {displaystyle n} , where {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 {displaystyle {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 number generators and in key generation for cryptography. Therefore, finding very large prime numbers (on the order of (at least) {displaystyle 10^{350}approx 2^{1024}} ) becomes very important and efficient primality testing algorithms are required.

Perfect matching Let {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: {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 {displaystyle a_{ij}={begin{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, {displaystyle i

Si quieres conocer otros artículos parecidos a Schwartz–Zippel lemma puedes visitar la categoría Computer algebra.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información