Information Technology Reference
In-Depth Information
given by
D
=
S
1
is a linearly
independent set. So there is no function
g
with degree 2 such that
h
=
fg
{
00000001
,
00100001
}
. It is easy to see that
D
∪
=0
with
deg
(
h
)=1.
This shows that the condition
d
+
e
n
in Assertion A in Section 1 cannot
guarantee that the existence of some function
g
≥
=0with
deg
(
g
)
≤
d
such that
h
=
fg
=0with
deg
(
h
)
≤
e
, since there exists a degenerated case for which
|
.
Note that the boolean form of
f
is given by
f
(
x
0
,x
1
,x
2
)=
x
0
x
1
+
x
0
x
2
+
x
1
x
2
+
x
1
. We may use the boolean form of
f
to show the above result using a
similar technique as above.
From the proof of Theorem 1, it is not necessary to require
r
+
s>
2
n
.Inthe
following, we characterize this condition.
fS
d
|
<
|
S
d
|
Theorem 2.
(
Existence of Low Degree Multipliers
, Function Version)
With the above notation, for a given
f
d, e < n
,let
D
d
be a
maximal linearly independent set of
fS
d
. Then there exists a function
g
∈F
n
and
1
≤
∈F
n
with degree at most
d
such that
h
=
fg
=0
with
deg
(
h
)
≤
e
if and only if
D
d
∪
S
e
is linearly dependent over
F
2
.
Proof.
A proof for the sucient condition is similar as we did for Theorem 1.
We denote
|
D
d
|
=
t
and
|
S
e
|
=
s
.Since
D
d
∪
S
e
is linearly dependent over
F
2
,
there exist
c
i
∈
F
2
,i
=1
,...,t
+
s
such that
r
s
c
i
fg
i
+
c
t
+
i
h
i
=0
i
=1
i
=1
where
fg
i
∈
D
d
and
h
i
∈
S
e
.Sinceboth
D
d
and
S
e
are linear independent
over
F
2
,thereexistsome
i
with 1
≤
i
≤
t
and
j
with 1
≤
j
≤
s
such that
= 0, respectively. Thus
g
=
i
=1
c
i
g
i
c
i
=0and
c
t
+
j
=0with
deg
(
g
)
≤
d
,and
fg
=
h
=
j
=1
c
t
+
j
h
j
e
, which establishes the assertion.
Conversely, assume that there exists some
g
=0with
deg
(
h
)
≤
∈F
n
with
deg
(
g
)
≤
d
such that
fg
e
. Since any function with degree less than or equal to
d
is a linear combination of functions in
S
d
,wemaywrite
g
=
i
=1
d
i
g
i
where
d
i
∈
F
2
and
l
=
=0and
deg
(
fg
)
≤
. For simplicity, we may assume that
g
i
,i
=1
,...,t
are
functions in
S
d
such that
|
S
d
|
{
fg
i
|
i
=1
,...,t
}
is a maximal linearly independent
set of
fS
d
.Thuswehave
l
l
t
fg
=
f
·
d
i
g
i
=
d
i
(
fg
i
)=
e
i
(
fg
i
)
=0
,e
i
∈
F
2
.
i
=1
i
=1
i
=1
Consequently, there exists some
i
with 1
≤
i
≤
t
such that
e
i
= 0. On the other
hand, since
h
=
fg
with degree
deg
(
h
)
≤
e
,then
h
∈
S
e
. Therefore,
h
is a linear
combination of the functions in
S
e
,say
h
=
i
=1
k
i
h
i
=0
,k
i
∈
F
2
. This shows
that there is some
k
i
=0with1
≤
i
≤
s
. Therefore, we have
t
e
h
=
fg
⇐⇒
e
i
fg
i
+
k
i
h
i
=0
i
=1
i
=1
