Applications Schwartz–Zippel lemma
1 applications
1.1 comparison of 2 polynomials
1.2 primality testing
1.3 perfect matching
applications
the importance of schwartz–zippel theorem , testing polynomial identities follows algorithms obtained problems can reduced problem of polynomial identity testing.
comparison of 2 polynomials
given pair of polynomials
p
1
(
x
)
{\displaystyle p_{1}(x)}
,
p
2
(
x
)
{\displaystyle p_{2}(x)}
, is
p
1
(
x
)
≡
p
2
(
x
)
{\displaystyle p_{1}(x)\equiv p_{2}(x)}
?
this problem can solved reducing problem of polynomial identity testing. equivalent checking if
[
p
1
(
x
)
−
p
2
(
x
)
]
≡
0.
{\displaystyle [p_{1}(x)-p_{2}(x)]\equiv 0.}
hence if can determine that
p
(
x
)
≡
0
,
{\displaystyle p(x)\equiv 0,}
where
p
(
x
)
=
p
1
(
x
)
−
p
2
(
x
)
,
{\displaystyle p(x)=p_{1}(x)\;-\;p_{2}(x),}
then can determine whether 2 polynomials equivalent.
comparison of polynomials has applications branching programs (also called binary decision diagrams). read-once branching program can represented multilinear polynomial computes (over field) on {0,1}-inputs same boolean function branching program, , 2 branching programs compute same function if , if corresponding polynomials equal. thus, identity of boolean functions computed read-once branching programs can reduced polynomial identity testing.
comparison of 2 polynomials (and therefore testing polynomial identities) has applications in 2d-compression, problem of finding equality of 2 2d-texts , b reduced problem of comparing equality of 2 polynomials
p
a
(
x
,
y
)
{\displaystyle p_{a}(x,y)}
,
p
b
(
x
,
y
)
{\displaystyle p_{b}(x,y)}
.
primality testing
given
n
∈
z
+
{\displaystyle n\in \mathbb {z^{+}} }
,
n
{\displaystyle n}
prime number?
a simple randomized algorithm developed manindra agrawal , somenath biswas can determine probabilistically whether
n
{\displaystyle n}
prime , uses polynomial identity testing so.
they propose prime numbers n (and prime numbers) satisfy following polynomial identity:
(
1
+
z
)
n
=
1
+
z
n
(
mod
n
)
.
{\displaystyle (1+z)^{n}=1+z^{n}({\mbox{mod}}\;n).}
this consequence of frobenius endomorphism.
let
p
n
(
z
)
=
(
1
+
z
)
n
−
1
−
z
n
.
{\displaystyle {\mathcal {p}}_{n}(z)=(1+z)^{n}-1-z^{n}.}
then
p
n
(
z
)
=
0
(
mod
n
)
{\displaystyle {\mathcal {p}}_{n}(z)=0\;({\mbox{mod}}\;n)}
iff n prime. proof can found in [4]. however, since polynomial has degree
n
{\displaystyle n}
, , since
n
{\displaystyle n}
may or may not prime, schwartz–zippel method not work. agrawal , biswas use more sophisticated technique, divides
p
n
{\displaystyle {\mathcal {p}}_{n}}
random monic polynomial of small degree.
prime numbers used in number of applications such hash table sizing, pseudorandom number generators , in key generation cryptography. therefore, finding large prime numbers (on order of (at least)
10
350
≈
2
1024
{\displaystyle 10^{350}\approx 2^{1024}}
) becomes important , efficient primality testing algorithms required.
perfect matching
let
g
=
(
v
,
e
)
{\displaystyle g=(v,e)}
graph of n vertices n even. g contain perfect matching?
theorem 2 (tutte 1947): tutte matrix determinant not 0-polynomial if , if there exists perfect matching.
a subset d of e called matching if each vertex in v incident @ 1 edge in d. matching perfect if each vertex in v has 1 edge incident in d. create tutte matrix in following way:
a
=
[
a
11
a
12
⋯
a
1
n
a
21
a
22
⋯
a
2
n
⋮
⋮
⋱
⋮
a
n
1
a
n
2
…
a
n
n
]
{\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
a
i
j
=
{
x
i
j
if
(
i
,
j
)
∈
e
and
i
<
j
−
x
j
i
if
(
i
,
j
)
∈
e
and
i
>
j
0
otherwise
.
{\displaystyle a_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in e{\mbox{ , }}i<j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in e{\mbox{ , }}i>j\\0\;\;\;\;{\mbox{otherwise}}.\end{cases}}}
the tutte matrix determinant (in variables xij,
i
<
j
{\displaystyle i<j}
) defined determinant of skew-symmetric matrix coincides square of pfaffian of matrix , non-zero (as polynomial) if , if perfect matching exists. 1 can use polynomial identity testing find whether g contains perfect matching. there exists deterministic black-box algorithm graphs polynomially bounded permanents (grigoriev & karpinski 1987).
in special case of balanced bipartite graph on
n
=
m
+
m
{\displaystyle n=m+m}
vertices matrix takes form of block matrix
a
=
(
0
x
−
x
t
0
)
{\displaystyle a={\begin{pmatrix}0&x\\-x^{t}&0\end{pmatrix}}}
if first m rows (resp. columns) indexed first subset of bipartition , last m rows complementary subset. in case pfaffian coincides usual determinant of m × m matrix x (up sign). here x edmonds matrix.
Comments
Post a Comment