Information Technology Reference
In-Depth Information
Proof.
The lemma is certainly true for
s
= 0. We proceed by induction on
s
,
where we use the lemma as a hypothesis. Observe that for
s>
0wehave
E
s
(
z
s
+1
)=
z
s
∈V
n
1)
(
z
s
+1
+
u
s
)
·z
s
i
wt(
z
s
)
E
s−
1
(
z
s
)
.
(
−
Now assume that the lemma is true for
s
≡
0 (mod 3). Using Lemma 1, we have
for
s
≡
1(mod3)
E
s
(
z
s
+1
)=2
(
s−
1)
n/
2
ω
c
1)
(
z
s
+1
+
u
s
+
a
)
·z
s
i
wt(
z
s
)
(
−
z
s
∈V
n
=2
sn/
2
ω
c
+
n
i
−
wt(
z
s
+1
+
u
s
+
a
)
=2
sn/
2
ω
c
(
1)
a
·z
s
+1
i
−
wt(
z
s
+1
)
,
−
where
c
=
c
+
n
2wt(
u
s
+
a
)and
a
=
a
+
u
s
. This proves the lemma for
s
−
≡
1
(mod 3) provided that it holds for
s
≡
0 (mod 3). Now assume that the lemma
is true for
s
≡
1(mod3).Thenfor
s
≡
2(mod3)weobtain
E
s
(
z
s
+1
)=2
(
s−
1)
n/
2
ω
c
1)
(
z
s
+1
+
u
s
+
a
)
·z
s
(
−
z
s
∈V
n
=2
(
s
+1)
n/
2
ω
c
δ
z
s
+1
+
a
.
where
c
=
c
and
a
=
a
+
u
s
. Assuming that the lemma is true for
s
≡
2
(mod 3), we have for
s
0(mod3)
E
s
(
z
s
+1
)=2
sn/
2
ω
c
≡
1)
(
z
s
+1
+
u
s
)
·z
s
i
wt(
z
s
)
δ
z
s
+
a
(
−
z
s
∈V
n
=2
sn/
2
ω
c
(
1)
a
·z
s
+1
,
−
where
c
=
c
+2wt(
a
)+4
a
u
s
and
a
=
a
. This completes the induction.
Proof (of Theorem 4).
We define the relabeling
z
2
j
:=
x
j
and
z
2
j−
1
:=
y
j
for
j
=1
,
2
,...,m
,sothatwehave
·
f
(
x
1
,...,x
m
,y
1
,...,y
m
)=
2
k
−
2
2
m
h
(
z
2
k
)+
z
j
·
z
j
+1
+
z
2
k−
1
·
ψ
(
z
2
k
)+
z
j−
1
·
z
j
+
z
2
k
+1
·
φ
(
z
2
k
)
.
j
=1
j
=2
k
+2
Write
(
f
)(
u
1
,...,u
2
m
)=2
−mn
1)
h
(
z
2
k
)+
z
2
k
·u
2
k
i
wt(
z
2
k
)
P
(
z
2
k
)
Q
(
z
2
k
)
,
N
(
−
(2)
z
2
k
∈
V
n
where
2
k−
2
1)
(
z
j
+1
+
u
j
)
·z
j
i
wt(
z
j
)
1)
(
ψ
(
z
2
k
)+
u
2
k−
1
)
·z
2
k−
1
i
wt(
z
2
k−
1
)
P
(
z
2
k
)=
(
−
(
−
j
=1
z
j
∈V
n
z
2
k−
1
∈V
n
2
m
1)
(
z
j−
1
+
u
j
)
·z
j
i
wt(
z
j
)
z
2
k
+1
∈V
n
1)
(
φ
(
z
2
k
)+
u
2
k
+1
)
·z
2
k
+1
i
wt(
z
2
k
+1
)
.
Q
(
z
2
k
)=
(
−
(
−
j
=2
k
+2
z
j
∈V
n