Information Technology Reference
In-Depth Information
Let the sequence
R
n
(
X
) of rational functions over
F
q
be defined by
R
n
(
X
)=
R
n−
1
(
aX
−
1
+
b
)
,
R
0
(
X
)=
X,
n
≥
1
.
Obviously this sequence is purely periodic and denote by
T
a,b
its least period.
From [8, Lemma 6] it follows that there are elements
ε
1
,...,ε
T
a,b
−
1
∈
F
q
,such
that
R
n
(
X
)=
(
b
−
ε
n
)
X
+
a
X
,
1
≤
n
≤
T
a,b
−
1
.
−
ε
n
This implies that for 1
≤
n
≤
T
a,b
−
1wehave
ψ
n
(
γ
)=
(
b
−
ε
n
)
γ
+
a
,
γ
∈
F
q
\{
ε
1
,...,ε
n
}
,
(1)
γ
−
ε
n
where
ψ
n
denotes the
n
th iterate of
ψ
.
For a permutation polynomial
f
(
X
)
∈
F
q
[
X
] we define the sequence
f
n
(
X
)of
polynomials over
F
q
by
f
0
(
X
)=
X,
f
n
(
X
)=
f
(
f
n−
1
(
X
))
,
n≥
1
.
The sequence
f
n
(
X
)mod(
X
q
−
X
) is purely periodic and we denote by
T
f
its
period.
We put
N−
1
χ
(
ψ
n
(
ϑ
))
,
S
χ,a,b
(
N, ϑ
)=
1
≤
N
≤
T
a,b
,
n
=0
and
N−
1
S
χ,f
(
N, ϑ
)=
χ
(
f
n
(
ϑ
))
,
1
≤
N
≤
T
f
,
n
=0
where
χ
is a nontrivial multiplicative character of
F
q
.
For 'individual' sequences it was proved in [10,11] that
=
O
(
N
1
/
2
q
1
/
4
)
,
max
ϑ∈
F
q
|
S
χ,a,b
(
N, ϑ
)
|
1
≤
N
≤
t
ϑ
,
(2)
where the implied constant is absolute, and under some restrictions
=
O
(
N
1
/
2
q
1
/
2
(log
q
)
−
1
/
2
)
,
max
ϑ
|
S
χ,f
(
N, ϑ
)
|
1
≤
N
≤
t
ϑ
,
(3)
where the maximum is taken over all
ϑ
such that (
x
n
) is purely periodic and the
implied constant depends only on the degree of
f
(
X
).
In this paper we prove that for any 0
<ε<
1 and all initial values
ϑ
∈
F
q
,
except at most
O
(
ε
2
q
) of them, we have
S
χ,a,b
(
N, ϑ
)=
O
(
ε
−
1
max
Nq
−
1
/
4
,N
1
/
2
{
}
)
(4)
and under the same restrictions as needed for (3)
S
χ,f
(
N, ϑ
)=
O
(
ε
−
1
N
(log
q
)
−
1
/
2
)
.
(5)
