Information Technology Reference
In-Depth Information
5.8.2.2 Log-Products Are Far from Full-Rank on a Random Partition
The main technical part of the proof is to show that log-product multivariate polyno-
mials are far from full-rank under a random partition of variables. This would let us
show that a sum of log-product multivariate polynomials cannot be full rank unless
it is a very large sum.
{
Main idea
Suppose
f
=
g
1
...g
t
where each
g
i
∗ F[
X
i
]
.Let
X
=
Y
∈
Z
be a
random partition with
|
Y
|=|
Z
|=|
X
|
/
2, and
Y
i
=
Y
ₔ
X
i
and
Z
i
=
Z
ₔ
X
i
.Let
⊩
|
Y
i
|−|
Z
i
|
2
⊩
d
i
measure the imbalance between the sizes of
Y
i
and
Z
i
, and we shall
say
X
i
is
k
-imbalanced if
d
i
=
=
|
Y
i
|+|
Z
i
|
2
=
|
X
i
|
2
ↆ
k
.Let
b
i
.
By Observation 26, we know that
[
Raz
]
Y
)
=
[
Raz
]
Y
i
,
Z
i
(g
1
)...
[
Raz
]
(
f
Z
i
(g
t
)
,
Z
Y
i
,
2
min
(
|
Y
1
|
,
|
Z
1
|
)
····
2
min
(
|
Y
t
|
,
|
Z
t
|
)
≥
2
|
X
|
/
2
2
d
1
+···+
d
t
.
2
b
1
−
d
1
2
b
t
−
d
t
=
···
=
Hence, even if one of the
X
i
's is a little imbalanced, the product is far from
full-rank.
Lemma 30 shows that the size of
X
i
decreases slowly with
i
, and it is not hard to
show that
X
i
| ↆ
∀
|
def
=
log
|
X
|
t
|
X
|
for
i
≥
. We wish to show that the probability
100
1
/
20
is very small. Let
t
)is
k
-unbalanced for
k
that none of
g
i
(for
i
E
i
be
the event that
X
i
is not
k
-unbalanced. The goal is to upper bound the probability that
all the events
≥
= |
X
|
E
i
hold. These probability calculations would follow from this lemma
about the
hypergeometric distribution
.
Hypergeometric Distribution
Fix parameters
n
, g,
r
ↆ
0, and let
G
∧[
n
]
with
|
|=
g
. Informally, the hypergeometric distribution is the distribution obtained on
the intersection sizes of a random set of size
r
with a fixed set of size
g
G
from a
universe of size
n
. Formally, the random variable
H(
n
, g,
r
)
is defined as:
k
n
−
g
k
r
−
|
|
=
r
Pr [
H(
n
, g,
r
)
=
k
]
=
Pr
[
R
ₔ
G
k
]
=
.
R
∧[
n
]
,
|
R
|=
r
The following lemma shows that for a fairly large range of parameters, the hyperge-
ometric distribution does not put too much mass on any value.
Lemma 31
n
4
3
n
4
2
n
Let n
, g,
r be parameters such that
≥
r
≥
and
0
≥
g
≥
3
. Then
for any t
≥
g
,
O
⊣
1
⊤
Pr [
H(
n
, g,
r
)
=
t
]
≥
∀
g
.
The proof of this lemma follows from standard binomial coefficient estimates on the
probability.
