Information Technology Reference
In-Depth Information
Z
2
l
→{±
1
}
be the mapping
μ
(
t
)=(
−
1)
c
,where
c
is the most significant
bit of
t
Let
μ
:
∈
Z
2
l
;inotherwordsitmaps0
,
1
, ...,
2
l−
1
1to+1and2
l−
1
,
2
l−
1
+
−
1
, ...,
2
l
1. Our goal is to express this map as a linear combination of
characters. Recall the Fourier transformation formula on
−
1to
−
Z
2
l
:
2
l
2
l
−
1
−
1
1
2
l
μ
=
μ
j
ψ
j
,
where
μ
j
=
μ
(
x
)
ψ
j
(
−
x
)
.
(1)
j
=0
x
=0
Combining Lemma 4.1 and Corollary 7.4 of [5], we obtain
Lemma 3.1.
Let
l
=3
. For the constants
μ
j
=(1+
ω
−j
+
ω
−
2
j
+
ω
−
3
j
)
/
4
j
=1
,
3
,
5
,
7
we have
μ
=
μ
1
ψ
1
+
μ
3
ψ
3
+
μ
5
ψ
5
+
μ
7
ψ
7
,
and
μ
j
=0
, for even
j
.Furthermore
)
2
=2+
√
2
.
(
|
μ
1
|
+
|
μ
3
|
+
|
μ
5
|
+
|
μ
7
|
Let
q
=2
l
where
l
≥
4
.Then
q−
1
j
=0
|
2
π
ln(
q
)+1
.
μ
j
|
<
For all
β
= 0 in the ring
R
=
GR
(2
l
,m
), we denote by
Ψ
β
the additive character
∗
,x
→
C
ω
Tr(
βx
)
.
Ψ
β
:
R
→
Note that for the defined above
ψ
k
and
Ψ
β
,wehave:
ψ
k
(Tr(
βx
)) =
Ψ
βk
(
x
)
.
Let
f
(
X
) denote a polynomial in
R
[
X
]andlet
f
(
X
)=
F
0
(
X
)+2
F
1
(
X
)+
...
+2
l−
1
F
l−
1
(
X
)
denote its 2-adic expansion. Let
d
i
be the degree in
x
of
F
i
.
Let
Ψ
be an arbitrary
additive character of
R
,andset
D
f
to be the
weighted degree
of
f
, defined as
d
0
2
l−
1
,d
1
2
l−
2
,...,d
l−
1
}
D
f
=max
{
.
With the above notation, and for any integers
k, H
such that 0
≤ k<k
+
H−
1
≤
2
m
−
2, we have, under mild technical conditions, the bound
2
+1
D
f
√
2
m
.
Ψ
(
f
(
ξ
j
))
≤
k
+
H−
1
π
ln
4(2
m
−
1)
(2)
π
j
=
k
See [10] for details.
