Information Technology Reference
In-Depth Information
Intuition from Algebraic Geometry
Another perspective for the shifted partial
derivatives comes from algebraic geometry. Any zero
a
n
of
Q
is a zero of
multiplicity d
of
Q
d
. This implies t
ha
t the set of common zeroes of all
k
-th order
partial derivatives of
Q
d
∗ F
≈
∀
d
)is
large
. On the other hand if
f
is a random
polynomial, then with high probability there are no roots of large multiplicity.
In algebraic geometry terminology, the common zeroes of a set of polynomials is
called the
variety
of the ideal generated by them. Further, there is also a well-defined
notion of a
dimension of a variety
which measures how large a variety is. Let
(for
k
F[
x
]
≥
r
dim
I
]
≥
r
.
refer to the set of polynomials of degree at most
r
, and let
˕
I
(
r
)
=
ₔ F[
x
Intuitively, if
˕
I
(
is large, then there are
many constraints
and hence the variety
is
small
. In other words the growth of
˕
I
(
r
)
is inversely related to the dimension of
the variety of
I
, and this is precisely captured by what is known as the
Affine Hilbert
function of I
. More about the precise definitions of the Affine Hilbert function, etc.,
can be found in any standard text in algebraic geometry such as [
CLO07
].
In our setting, the ideal we are interested in is
I
r
)
=
˃
=
k
f
.If
f
is a homogeneous
=
˃
=
k
)
polynomial, then
I
ₔ F[
x
]
≥
r
(
f
where
=
r
−
(
deg
(
f
)
−
k
)
. Hence
≥
studying the dimension of shifted partial derivatives is exactly studying
˕
I
(
r
)
which
holds all information about the dimension of the variety.
5.9.3 Lower Bounding Shifted Partials of Explicit Polynomials
For a random polynomial
R
(
x
)
, we would expect that
min
⊣
n
⊤
⊣
n
⊤⊣
n
⊤
+
+
d
−
k
+
k
+
n
[
Kay
]
k
(
R
)
≈
,
.
,
n
n
The terms on the RHS correspond to trivial upper bounds, where the first term is the
total number of monomials of degree
(
+
d
−
k
)
and the second term is the total
number shifted partials.
=
∂
∀
d for a small enough
∂ >
cn
∀
d
log
n
Claim 47
Fo r k
0
, and
=
for a large enough
constant c, we have
min
n
+
+
d
−
k
n
,
n
+
n
n
+
n
2
ˇ(
∀
d
log
n
)
.
=
O
(
∀
d
)
k
n
+
(
∀
d
−
1
)
k
+
n
The proof of this claim is easily obtained by using standard asymptotic estimates
of binomial coefficients. Note that using Corollary 46, the above claim shows that if
we can find an explicit polynomial whose d
i
mension of shifted partials are as large
as above
,
then w
e
would have an exp
(ˇ(
∀
d
log
n
))
lower bound for the top fan-in
[
∀
d
]
[
∀
d
]
circuits computing this polynomial.
of
