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
Search WWH ::




Custom Search