Schwartz–Zippel lemma

{{short description|Tool used in probabilistic polynomial identity testing}}

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,{{sfn|Schwartz|1980}} Richard Zippel,{{sfn|Zippel|1979}} and Richard DeMillo and Richard J. Lipton, although DeMillo and Lipton's version was shown a year prior to Schwartz and Zippel's result.{{sfn|DeMillo|Lipton|1978}} The finite field version of this bound was proved by Øystein Ore 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[x_1,x_2,\ldots,x_n]$

be a non-zero polynomial of total degree {{math|1=d ≥ 0}} over an integral domain R. Let S be a finite subset of R and let {{math|r₁, r₂, ..., r_n}} be selected at random independently and uniformly from S. Then

: $\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}$

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|^{n-1}.$

Proof. The proof is by mathematical induction on n. For {{math|1=n = 1}}, P can have at most d roots by the fundamental theorem of algebra. This gives us the base case.

Now, assume that the theorem holds for all polynomials in {{math|n − 1}} variables. We can then consider P to be a polynomial in x₁ by writing it as

: $P(x_1,\dots,x_n)=\sum_{i=0}^d x_1^i P_i(x_2,\dots,x_n).$

Since {{mvar|P}} is not identically 0, there is some {{mvar|i}} such that $P_i$ is not identically 0. Take the largest such {{mvar|i}}. 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 {{mvar|S}}. By the induction hypothesis, $\Pr[P_i(r_2,\ldots,r_n)=0]\leq\frac{d-i}$

If $P_i(r_2,\ldots,r_n)\neq 0$ , then $P(x_1,r_2,\ldots,r_n)$ is of degree {{mvar|i}} (and thus not identically zero) so

::: $\Pr[P(r_1,r_2,\ldots,r_n)=0|P_i(r_2,\ldots,r_n)\neq 0]\leq\frac{i}$

If we denote the event $P(r_1,r_2,\ldots,r_n)=0$ by {{mvar|A}}, the event $P_i(r_2,\ldots,r_n)=0$ by {{mvar|B}}, and the complement of {{mvar|B}} by $B^c$ , we have

: $\begin{align}
\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}$

+\frac{i}

=\frac{d}

\end{align}

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

: $(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 $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 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)$ and $p_B(x,y)$ .

= Primality testing =

Given $n \in \mathbb{N}$ , is $n$ a prime number?

A simple randomized algorithm developed by Manindra Agrawal 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{mod}\;n).$

This is a consequence of the Frobenius endomorphism.

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$ , 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{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) $10^{350} \approx 2^{1024}$ ) becomes very important and efficient primality testing algorithms

are required.

= Perfect matching =

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

Theorem 2 {{harv|Tutte|1947}}: A Tutte matrix determinant is not a {{math|0}}-polynomial if and only if there exists a perfect matching.

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

::: $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_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i j\\
0\;\;\;\;\mbox{otherwise}. \end{cases}$

The Tutte matrix determinant (in the variables x_ij, {{tmath|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 {{math|G}} contains a perfect matching. There exists a deterministic black-box algorithm for graphs with polynomially bounded permanents (Grigoriev & Karpinski 1987).{{sfn|Grigoriev|Karpinski|1987}}

In the special case of a balanced bipartite graph on $n =m + m$ vertices this matrix takes the form of a block matrix

::: $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.

= Determinant of a matrix with polynomial entries =

Let

: $p(x_1,x_2, \ldots, x_n)$

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 whose analysis requires a bound on the probability that a non-zero polynomial will have roots at randomly selected test points.

Notes

References

{{cite journal

|url= https://ieeexplore.ieee.org/document/814592

|title= Primality and Identity Testing via Chinese Remaindering

|access-date= 2008-06-15

|last1=Agrawal|first1=Manindra

|last2=Biswas | first2=Somenath

|date= 2003-02-21

|journal= Journal of the ACM

|volume= 50

|issue= 4

|pages=429–443

|doi=10.1145/792538.792540

|s2cid= 13145079

}}

{{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

|access-date= 2008-06-15

|last1=Berman | first1=Piotr

|last2=Karpinski | first2=Marek | authorlink2=Marek Karpinski

|last3=Larmore | first3=Lawrence L.

|last4=Plandowski | first4=Wojciech

|last5=Rytter | first5=Wojciech | author5-link = Wojciech Rytter

|format= ps

|journal= Journal of Computer and System Sciences

|volume=65

|issue= 2

|pages=332–350

|doi= 10.1006/jcss.2002.1852

|year= 2002

|doi-access=free

}}

{{cite conference

| last1 = Grigoriev | first1 = Dima

| last2 = Karpinski | first2 = Marek

| contribution = The matching problem for bipartite graphs with polynomially bounded permanents is in NC

| doi = 10.1109/SFCS.1987.56

| isbn = 978-0-8186-0807-0

| pages = 166–172

| publisher = IEEE Computer Society

| s2cid = 14476361

| title = Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS 1987), Los Angeles, California, USA, 27-29 October 1987

| year = 1987}}

Moshkovitz, Dana (2010). An Alternative Proof of The Schwartz-Zippel Lemma. {{ECCC|2010|10|096}}
{{cite journal

|title= A probabilistic remark on algebraic program testing

|last1= DeMillo | first1=Richard A. | authorlink1=Richard DeMillo

|last2= Lipton | first2=Richard J. | authorlink2 = Richard Lipton

|journal = Information Processing Letters

|volume = 7

|number = 4

|year = 1978

|pages = 193–195

|doi = 10.1016/0020-0190(78)90067-4

}}

{{cite book

|last=Rudich

|first=Steven

|editor=AMS

|title=Computational Complexity Theory

|series= IAS/Park City Mathematics Series

|volume=10

|isbn= 978-0-8218-2872-4

|year=2004}}

{{cite journal

|url= http://delivery.acm.org/10.1145/330000/322225/p701-schwartz.pdf

|title= Fast probabilistic algorithms for verification of polynomial identities

|access-date= 2008-06-15

|last=Schwartz |first=Jacob T.

|authorlink=Jacob T. Schwartz

|date=October 1980

|journal= Journal of the ACM

|pages=701–717

|doi= 10.1145/322217.322225

|volume= 27

|issue= 4

|citeseerx= 10.1.1.391.1254

|s2cid= 8314102

}}

{{cite journal

|title= The factorization of linear graphs

|last=Tutte |first=W.T.

|authorlink=W. T. Tutte

|date=April 1947

|volume=22

|issue= 2

|journal=J. London Math. Soc.

|pages=107–111

|doi=10.1112/jlms/s1-22.2.107

|hdl= 10338.dmlcz/128215

}}

{{cite conference

| last = Zippel | first = Richard

| editor-last = Ng | editor-first = Edward W.

| contribution = Probabilistic algorithms for sparse polynomials

| doi = 10.1007/3-540-09519-5_73

| isbn = 978-3-540-09519-4

| pages = 216–226

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings

| volume = 72

| year = 1979}}

{{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

|access-date= 2008-06-15

|first= Richard

|last=Zippel

|date=February 1989

|format= ps

}}

{{cite book

|last=Zippel

|first=Richard

|editor=Springer

|title=Effective Polynomial Computation

|url=https://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

|year=1993}}

External links

[http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma The Curious History of the Schwartz–Zippel Lemma], by Richard J. Lipton

Category:Theorems about polynomials

Category:Computer algebra

Category:Lemmas in algebra

Category:Mathematical theorems in theoretical computer science