Information Technology Reference
In-Depth Information
Theorem 1.
With the above notation, for a given
f
∈F
n
and two positive
integers
d
and
e
with
1
≤
d, e < n
,if
fS
d
contains at least
2
n
+1
−|
S
e
|
linear independent functions over
F
2
, then there exists a function
g
∈F
n
with
degree at most
d
such that
h
=
fg
=0
with
deg
(
h
)
≤
e
.
=2
n
,thus2
n
+1
Proof.
Note that
e<n
implies that
|
S
e
|
<
|
S
n
|
−|
S
e
|
>
1. Let
,then
r>
1. Since
r
+
s>
2
n
and the dimension of
r
=
|
fS
d
|
and
s
=
|
S
e
|
F
n
is
2
n
, the vectors in
fS
d
∪
F
2
. We list the elements
in
fS
d
as
fg
1
,...,fg
r
,andtheelementsin
S
e
as
h
1
,...,h
s
. Then there exist
c
i
∈
F
2
,i
=1
,...,r
+
s
, which are not all zeros, such that
S
e
are linearly dependent over
r
s
c
i
fg
i
+
c
r
+
i
h
i
=0
.
(24)
i
=1
i
=1
Note that
S
e
is linearly independent over
F
2
. Thus, there are some
j
where
=0.Wewrite
g
=
i
=1
c
i
g
i
and
1
≤
j
≤
r
and
i>r
such that
c
j
=0and
c
i
h
=
i
=1
c
r
+
i
h
i
= 0. Hence
fg
=
h
where
deg
(
g
)
≤
d
and
deg
(
h
)
≤
e
.
Remark 2.
The condition in Theorem 1 implies that
d
+
e
≥
n
.Otherwise
|
S
d
|
+
2
n
, therefore
2
n
, which is a contradiction. However, the
|
S
e
|≤
|
fS
d
|
+
|
S
e
|≤
converse is not true.
Note that it is possible that
|
fS
d
|
<
|
S
d
|
and the elements in
fS
d
are linearly
dependent over
F
2
. In this case, possibly, there is no function
g
with
deg
(
g
)
≤
d
such that
fg
=0and
deg
(
fg
)
≤
e
.
Example 1.
Let
f
(
x
)=
Tr
1
(
α
5
x
+
α
6
x
3
) be a function from
F
2
3
to
F
2
where
α
F
2
3
with
α
3
+
α
+1=0. Let
d
=2and
e
=1,then
d
+
e
=
n
.Theset
S
2
contains the following seven functions
is a primitive element in
Tr
1
(
x
) = 01001011
constant function c = 11111111
Tr
1
(
αx
) = 00010111
Tr
1
(
α
2
x
) = 00101110
Tr
1
(
x
3
) = 01110100
Tr
1
((
αx
)
3
) = 01101001
Tr
1
((
α
2
x
)
3
) = 01010011
On the other hand, we have
f
(
x
) = 00100001
.
Thus the elements of
fS
2
are
fTr
1
(
x
)=
fTr
1
(
αx
)=
fTr
1
((
α
2
x
)
3
) = 00000001
fTr
1
(
α
2
x
)=
fTr
1
(
x
3
) = 00100000
fc
=
fTr
1
((
αx
)
3
) = 00100001
Thus
= 3. However, 00100001 = 00000001 + 00100000. Thus the elements
of
fS
2
are linearly dependent. The maximal linear independent set in
fS
2
is
|
fS
2
|
