Information Technology Reference
In-Depth Information
5.8.2.3
Det
n
and
Perm
n
have Large Rank
The last step of the proof would be to find an explicit polynomial whose partial
derivative matrix under a random partition has large rank. As earlier, our candidate
polynomial would be
Det
n
or
Perm
n
. Unfortunately, both these polynomials are
over
n
2
variables and degree
n
. It is not hard to verify that the rank of the partial
derivative matrix of
Det
n
or
Perm
n
can never be greater than 2
2
n
. Hence directly
using Lemma 32, we would have 2
O
(
n
)
competing with 2
n
2
−
n
O
(
1
)
which is simply
futile. A simple fix is to first randomly restrict ourselves to fewer variables and then
apply Lemma 32.
Let
m
/
2
n
1
/
3
.Let
˄
be a random restriction that assigns random values to all
but 2
m
randomly chosen variables. We shall call this set of 2
m
variables as
X
, and
randomly partition this into two sets
Y
and
Z
of size
m
each. Hence,
˄(
=
reduces
to amultilinear polynomial over 2
m
variables. It is alsoworth noting that amultilinear
formula remains a multilinear formula under this restriction. The following claim is
easy to verify.
Det
n
)
Claim 33
With probability at least
1
/
2
, the variables in X belong to distinct rows
and columns.
We shall restrict ourselves to only these random restrictions, and without loss of
generality let the sets be
Y
=
⊞
x
1
,
1
,
x
2
m
−
1
,
2
m
−
1
⊠
and
Z
=
⊞
x
2
,
2
,
x
3
,
3
,...,
x
4
,
4
,...,
x
2
m
,
2
m
⊠
. For ease of notation, we shall refer to
x
2
i
−
1
,
2
i
−
1
as
y
i
and
x
2
i
,
2
i
as
z
i
for
i
=
m
.
Consider the following restriction:
1
,...,
y
1
1
1
z
1
⊢
⊥
.
.
.
y
m
1
1
z
m
f
=
Det
1
.
.
.
1
=
(
y
1
z
1
−
1
)...(
y
m
z
m
−
1
).
[
Raz
]
Y
2
m
. Although this is a single restriction with large
rank, the Schwartz-Zippel-DeMillo-Lipton lemma immediately gives that random
restriction would also have rank 2
m
with high probability.
7
We shall record this as a
lemma.
It is easy to check that
(
f
)
=
,
Z
7
provided the underlying field is large, but this isn't really a concern as we can work with a large
enough extension if necessary.
