Information Technology Reference
In-Depth Information
5Fin lRem rks
The bounds (2) and (3) for all
ϑ
are only nontrivial if
N
is at least of the order
of magnitude
Ω
(
q
1
/
2
)and
Ω
(
q/
log
q
), respectively. However, the bounds (4) and
(5) for almost all
ϑ
are nontrivial for all
N
larger than a constant which doesn't
depend on
q
.
Corollary 3 provides the existence of an
s
th power in the sequence
u
0
,
u
1
,...,
u
N−
1
or
x
0
,x
1
,...,x
N−
1
for almost all initial values if
s
=
O
ε
min
q
1
/
4
,N
1
/
2
{
}
or
s
=
O
ε
min
log
q
log
d
,N,t
0
1
/
2
,
respectively. It also provides the existence of an
s
th non-power in these sequences
for almost all
ϑ
if
N
is larger than a constant depending only on
ε
provided that
t
0
is large enough in the second case.
Corollary 4 implies the existence of a primitive element in
u
0
,u
1
,...,u
N−
1
or
x
0
,x
1
,...,x
N−
1
for almost
ϑ
if
2
ν
(
q−
1)
=
O
ε
ϕ
(
q
1)
q −
1
−
q
1
/
4
,N
1
/
2
{
}
min
or
2
ν
(
q−
1)
=
O
ε
ϕ
(
q −
1)
q
log
d
,N,t
0
1
/
2
,
min
log
q
−
1
respectively.
It is clear that the maximal value
t
ϑ
=
q
of the least period of (
x
n
)withinitial
value
x
0
=
ϑ
is obtained if and only if
f
(
X
) is a permutation polynomial of
F
q
representing a permutation which is a cycle of length
q
.Inthiscasewehave
t
ϑ
=
t
0
.
Let
f
(
X
)=
X
d
with
d ≥
2,
x
0
=0,and
s
be a divisor of
d −
1. Then it is
clear that for a character
χ
of order
s
we have
χ
(
x
n
)=
χ
(
x
0
) for all
n ≥
0.
This example provides some evidence that the dependence of the character sum
bound on
t
0
is natural.
Let
f
(
X
)=(
X
+
a
)
d
∈
F
q
,
x
0
= 0. The sequence (
x
n
)
generated by this polynomial can be obtained by subtracting
a
from a sequence
as in the previous remark. Hence, both sequences have the same least period.
For example, if
q
is even,
q
−
a
with
d
≥
2,
a
−
1 a Mersenne prime,
d
the least primitive root
1, i. e.,
d
=
O
(log
6
(
q
modulo
q
−
−
1)) under ERH (see [12, Theorem 1.3]), and
a
is a primitive element of
2.
This shows that examples for which Theorem 2 gives a nontrivial bound can
be easily constructed.
F
q
,thenwehave
t
0
=
q
−
