Information Technology Reference
In-Depth Information
If we divide the inner sum of
S
χ,a,b
(
N
)intoatmost
N/K
+ 1 subsums of
length
K
, except possibly the last sum, and use the triangle inequality we have
2
S
χ,a,b
(
N
)=
ϑ
N−
1
χ
(
ψ
n
(
ϑ
))
∈
F
q
n
=0
2
K−
1
K−
1
χ
(
ψ
n
(
ϑ
))
χ
(
ψ
n
(
ψ
K
(
ϑ
)))
≤
+
...
+
ϑ∈
F
q
n
=0
n
=0
χ
(
ψ
n
(
ϑ
))
2
K
−
1
N
2
K
2
n
=0
ϑ∈
F
q
N
where
=
K
. Therefore
S
χ,a,b
(
N
)=
O
N
2
K
2
(
Kq
+
K
3
)
.
By choosing
K
=min
N,
we get the result.
q
1
/
2
Corollary 1.
For any
0
<ε<
1
and all initial values
ϑ
,exceptatmost
O
(
ε
2
q
)
of them, we have
S
χ,a,b
(
N, ϑ
)=
O
ε
−
1
max
.
Nq
−
1
/
4
,N
1
/
2
{
}
Proof.
Let
A
be the number of exceptional
ϑ
.Thenwehave
S
χ,a,b
(
N
)=
Ω
(
Aε
−
2
max
N
2
q
−
1
/
2
,N
{
}
)
and Theorem 1 implies the result.
3 Bounds on Character Sums of Nonlinear Sequences
In this section we estimate the sums
S
χ,f
(
N
)=
ϑ
2
,
∈
F
q
|
S
χ,f
(
N, ϑ
)
|
≤
N
≤
T
f
.
1
Let
t
0
be the least period of the sequence (
x
n
) with initial value
x
0
=0.
Theorem 2.
Let
χ
be a nontrivial multiplicative character of
F
q
of order
s>
1
and
f
(
X
)
∈
F
q
[
X
]
a permutation polynomial with
d
=deg(
f
)
≥
2
. Then for
1
≤
N
≤
T
f
we have
S
χ,f
(
N
)=
O
,
N
2
q
{
log
q/
log
d, N, t
0
}
min
where the implied constant is absolute.
