Information Technology Reference
In-Depth Information
Moreover, we have
nl
r
(
F
)
≥
max
r
≤n
(min (
λ
r
,μ
r
))
,where:
⎛
⎞
⎠
n
i
,
n
r
−
AI
(
F
)
−
r
−
1
1
−
r
λ
r
=2
m
max
⎝
if
r
≤
AI
(
F
)
−
r
−
1
,
i
i
=0
i
=0
n
i
if
r
>AI
(
F
)
AI
(
F
)
−
r
−
1
=2
m
−
r
−
1
,
i
=0
n
+2
m−
1
n
.
AI
(
F
)
−r
AI
(
F
)
−r−
1
r
+1
i
−
r
−
μ
r
=2
m−
1
i
i
=0
i
=0
Proof.
Let
h
be any
n
-variable function of degree at most
r
and let
be any
m
-variable nonzero linear function. We have
d
H
(
F, h
)=
z∈supp
(
)
|
F
−
1
(
z
)
◦
∩
+
z∈supp
(
+1)
|
F
−
1
(
z
)
supp
(
h
+1)
|
∩
supp
(
h
)
|
.
F
)=
z∈supp
(
)
|
F
−
1
(
z
)
If
h
is constant, then
d
H
(
◦
F, h
)equals
w
H
(
◦
|
or
F
+1) =
z∈supp
(
+1)
|
F
−
1
(
z
)
w
H
(
which, according to the property recalled
before Proposition 2, are lower bounded by 2
m−
1
AI
(
F
)
−
1
◦
|
i
=0
i
.Itisasimple
matter to check that the bound of Theorem 1 is then satisfied.
If
h
is not constant, then Proposition 2 (last line of) implies
d
H
(
◦
F, h
)
≥
i
=0
n−
i
.
The inequality
2
m
AI
(
F
)
−r−
1
2
m−
1
⎛
⎞
⎠
n
i
+
n
AI
(
F
)
−r−
1
AI
(
F
)
−r−
1
−
r
⎝
nl
r
(
F
)
≥
i
i
=0
i
=
AI
(
F
)
−
2
r
is a direct consequence of Proposition 2 and of the inequality
dim
Mul
AI
(
F
)
−r−
1
(
h
)
+
dim
Mul
AI
(
F
)
−r−
1
(
h
+1)
≥
n
i
+
n
AI
(
F
)
−r−
1
AI
(
F
)
−r−
1
−
r
i
i
=0
i
=
AI
(
F
)
−
2
r
which is a direct consequence of Lemma 2 and Corollary 6 in [46].
Let
r
be any nonnegative integer. If
AI
(
h
)
r
, then Proposition 2 shows
≥
F
2
,
F
−
1
(
z
)
F
−
1
(
z
)
that, for every
z
∈
|
∩
supp
(
h
)
|
and
|
∩
supp
(
h
+1)
|
are lower
bounded by
⎛
⎞
⎠
n
i
,
n − r
i
r
−
AI
(
F
)
−r−
1
1
⎝
if
r
≤
max
AI
(
F
)
−
r
−
1
,
i
=0
i
=0
n
i
if
r
>AI
(
F
)
AI
(
F
)
−r−
1
−
r
−
1
.
i
=0
