Information Technology Reference
In-Depth Information
If we have a set of polynomials with distinct leading monomials, then they are
clearly linearly independent. Hence, one way of lower bounding the dimension of
a space of polynomials is to find a sufficiently large set of polynomials with dis-
tinct monomials in the space. The vector space of polynomials we are interested is
˃
=
k
≥
, and if we choose a structured polynomial
f
we can hope to be able to
estimate the number of distinct leading monomials in this vector space.
(
f
)
5.9.3.1 Shifted Partials of the Determinant and Permanent
[
∀
d
]
[
∀
d
]
circuits was by Gupta, Kamath, Kayal,
and Saptharishi [
GKKS13
] for the determinant and the permanent polynomials. We
shall describe the lower bound for
Det
n
, although it would carry over immediately
to
Perm
n
as well. As mentioned earlier, we wish to estimate the number of distinct
The first lower bound for
leading monomials in
˃
=
k
span
⊞
x
≥
˃
=
k
Det
n
⊠
.[
GKKS13
] made a
relaxation to merely count the number of distinct leading monomials among the
Det
n
)
(
≥
=
generators
⊞
x
≥
˃
=
k
Det
n
⊠
instead of their span.
The first observation is that any
k
-th order partial derivative of
Det
n
is just an
(
minor. Let us fix a monomial ordering induced by the lexicographic
ordering on the variables:
n
−
k
)
×
(
n
−
k
)
x
11
≡
x
12
··· ≡
x
1
n
≡
x
21
≡ ··· ≡
x
nn
.
Under this ordering, the leading monomial of any minor is just the product of vari-
ables on the main diagonal of the submatrix corresponding to the minor, and hence is
a term of the form
x
i
1
j
1
...
x
i
(
n
−
k
)
,
j
(
n
−
k
)
where
i
1
<
···
<
i
n
−
k
and
j
1
<
···
<
j
n
−
k
;
let us call such a sequence of indices as an
(
n
−
k
)
-increasing sequence in
[
n
]×[
n
]
.
Further, for any
-increasing sequence, there is a unique minor
M
whose
leading monomial is precisely the product of the variables indexed by the increas-
ing sequence. Therefore, the task of lower bounding distinct leading monomials in
(
n
−
k
)
⊞
x
≥
˃
=
k
Det
n
⊠
reduces to the following combinatorial problem:
Claim 48
For any k
, >
0
, we have
#
monomials of degree
(
+
n
−
k
)
that
[
Kay
]
k
,
(
Det
n
)
ↆ
.
contain an
(
n
−
k
)
-increasing sequence
We could start with an
(
n
−
k
)
-increasing sequence, and multiply by a monomial
of degree
to obtain a monomial containing an increasing sequence. Of course, the
issue is that this process is not invertible and hence we might overcount. To fix this
issue, [
GKKS13
] assign a
canonical increasing sequence
to every monomial that
contains an increasing sequence and multiply by monomials of degree
that do not
change the canonical increasing sequence.
Definition 49
Let
D
2
=
⊞
x
1
,
1
,...,
x
n
−
1
,
n
⊠
, the main diagonal
and the diagonal just above it. For any monomial
m
define the canonical increasing
x
n
,
n
,
x
1
,
2
,
x
2
,
3
,...,
