Information Technology Reference
In-Depth Information
If dim(
An
k
(
A
supp
(
h
)))
>
dim(
An
k
(
supp
(
h
))), then there exists an annihilator
g
of degree at most
k
of
A
∩
supp
(
h
) which is not an annihilator of
h
. Then,
gh
is a nonzero annihilator of
A
and has degree at most
k
+
r
.Thus,if
k
=
AI
(
A
)
∩
−
r
−
≥
0, we arrive to a contradiction. We deduce that dim(
An
AI
(
A
)
−r−
1
(
A
∩
1
supp
(
h
)))
≤
dim(
An
AI
(
A
)
−r−
1
(
supp
(
h
))). This implies:
n
i
AI
(
A
)
−
r
−
1
−|
A
∩
supp
(
h
)
|≤
i
=0
⎛
⎞
⎠
,
n
i
,
n
i
n
AI
(
A
)
−r−
1
AI
(
A
)
−r−
1
AI
(
A
)
−r−
1
−
r
⎝
min
−
i
i
=
r
i
=0
i
=0
that is:
⎛
⎞
⎠
n
i
,
n
r
−
1
AI
(
A
)
−r−
1
−
r
⎝
if
r
≤
|
A
∩
supp
(
h
)
|≥
max
AI
(
A
)
−
r
−
1
,
i
i
=0
i
=0
and
n
i
if
r
>AI
(
A
)
AI
(
A
)
−
r
−
1
|
A
∩
supp
(
h
)
|≥
−
r
−
1
.
i
=0
dim
An
AI
(
A
)
−
1
(
supp
(
h
+1))
comes from the
facts that the system of equations expressing that a given function of degree at
most
AI
(
A
)
The inequality
|
A
∩
supp
(
h
)
|≥
1(givenbyitsANF)isanannihilatorof
A
(we shall denote this
system by
S
A
) has full rank by definition of the algebraic immunity, and that the
system
S
supp
(
h
+1)
has
−
equationsincommonwith
S
A
,which
implies that the rank of
S
supp
(
h
+1)
is at least equal to the rank of
S
A
minus
|
|
A
∩
supp
(
h
+1)
|
A
∩
supp
(
h
)
|
(see a more detailed proof in Lemma 9 of [46]). The inequality
dim
An
AI
(
A
)
−
1
(
supp
(
h
+1))
≥
dim
Mul
AI
(
A
)
−r−
1
(
h
)
is straightforward.
This implies:
Theorem 1.
Let
F
be any
(
n, m
)
-function and let
r
be any positive integer such
that
AI
(
F
)
−
r
−
1
≥
0
.Then
nl
r
(
F
)
≥
⎛
,
2
m−
1
⎛
⎞
⎠
⎞
n
n
i
+
n
AI
(
F
)
−r−
1
AI
(
F
)
−r−
1
AI
(
F
)
−r−
1
−
r
−
r
⎝
2
m
⎝
⎠
.
max
i
i
i
=0
i
=0
i
=
AI
(
F
)
−
2
r
