Information Technology Reference
In-Depth Information
=
Here we are thinking of a bounded
k
. But now even
k
2 seems non-trivial! In fact,
a simpler PIT case than this is an old open question in a related area [
vzG83
].
This
bounded top fanin
depth-4 PIT is an important open question currently.
What is doable are other restricted models of depth-4. Inspired from the last sub-
section we ask: Is there a notion of 'rank' for general polynomials, are there easy
'faithful' maps, and finally is all this useful in PIT?
There are several notions of rank in commutative algebra. The one we [
BMS13
]
found useful is—
transcendence degree
(trdeg). We say that a set
S
of polynomials
{
f
1
,...,
f
m
}∞F[
x
1
,...,
x
n
]
is
algebraically dependent
if there exists a nonzero
annihilating polynomial
A
0. The
largest number of algebraically
in
dependent polynomials in
S
is called trdeg
(
y
1
,...,
y
m
)
, over
F
, such that
A
(
f
1
,...,
f
m
)
=
(
S
)
.
With this notion we call a homomorphism
ϕ
faithful
if trdeg
.The
usefulness of
ϕ
(assuming that one can come up with it efficiently) was first proved
in [
BMS13
]:
(
S
)
=
trdeg
(ϕ(
S
))
Lemma 3.3
(
Faithful is useful)
Let
ϕ
be a homomorphism faithful to
f
=
{
f
1
,...,
f
m
}∞F[
x
]
. Then for any C
ↆ F[
y
]
,C
(
f
)
=
0
≈
C
(ϕ(
f
))
=
0
.
This implies that we can use a faithful map to 'reduce' the number of variables
n
without changing the nonzeroness of
C
. The strategy can be used in cases where
trdeg
is small, say, smaller than a constant
r
.
The only missing piece is the efficiency of
ϕ
.
4
To do this we need three funda-
mental ingredients—an efficient criterion for algebraic independence (Jacobian), its
behaviour under
ϕ
(chain rule), and standard maps (Vandermonde and Kronecker-
based).
(
f
)
Lemma 3.4
(
Jacobian criterion)
Let
f
∞ F[
x
]
be a finite set of polynomials of
d
r
, then
trdeg
degree at most d, and
trdeg
(
f
)
∧
r. If
char
(
F
)
=
0
or
char
(
F
)>
(
f
)
=
)
:=
⊡
∂
f
i
/∂
x
j
⊣
m
×
n
rk
F
(
x
)
J
x
(
f
)
, where
J
x
(
f
is the
Jacobian matrix
.
There are several proofs of this, see [
Jac41
,
For91
,
BMS13
,
MSS12
]. This gives
us an efficient way to capture trdeg, when the characteristic is zero/large. Let us now
see how the Jacobian matrix changes under
ϕ
.
Lemma 3.5
, where
ϕ
applied to a
matrix/set refers to the matrix/set obtained by applying
ϕ
to every entry.
(
Chain rule)
J
y
(ϕ(
f
))
=
ϕ (J
x
(
f
))
·
J
y
(ϕ(
x
))
This is a simple consequence of the chain rule of 'derivatives'. It suggests that
for
ϕ
to preserve the trdeg of the polynomials, we need to control—(1) the image
of the original Jacobian under
ϕ
, and (2) the Jacobian of the image of
x
. In our
applications, the former is achieved by a Kronecker-based map (i.e. sparse PIT
tricks, e.g. [
BHLV09
]) and the latter by Vandermonde map (as seen in the previous
subsection).
This general 'recipe' has been successfully implemented to various circuit models.
The case of the circuit
C
(
x
)
:=
C
(
f
)
, where trdeg
(
f
)
∧
r
and
f
i
's are polynomials
4
It can be shown, from first principles, that a faithful
r
-variate map always
exists
[
BMS13
].
