Information Technology Reference
In-Depth Information
Corollary 3.
For any
0
<ε<
1
and all initial values
ϑ
,exceptatmost
O
(
εq
)
of them, we have
=
O
ε
−
1
max
,
N
s
Nq
−
1
/
4
,N
1
/
2
R
s,a,b
(
N, ϑ
)
−
{
}
1
≤
N
≤
T
a,b
,
and under the conditions of Theorem 2
=
O
ε
−
1
N
min
log
q
log
d
,N,t
0
−
1
/
2
N
s
R
s,f
(
N, ϑ
)
−
for
1
≤
N
≤
T
f
.
∈
F
q
is a
primitive element
of
We recall that
w
F
q
if it is not an
s
th power for
any divisor
s>
1of
q
1wedenoteby
ν
(
m
)thenumber
of distinct prime divisors of
m
and by
ϕ
(
m
) Euler's totient function.
Let
Q
a,b
(
N, ϑ
)and
Q
f
(
N, ϑ
) be the number of primitive elements of
−
1. For an integer
m
≥
F
q
among
u
0
,u
1
,...,u
N−
1
and
x
0
,x
1
,...,x
N−
1
, respectively, with initial value
ϑ
.
Theorem 5.
For
1
≤
N
≤
t
we have
N
=
O
2
ν
(
q−
1)
max
.
ϕ
(
q
−
1)
Nq
3
/
4
,N
1
/
2
q
Q
a,b
(
N, ϑ
)
−
{
}
q
−
1
ϑ
∈
F
q
Proof.
From Vinogradov's formula (see [5, Lemma 7.5.3], [6, Exercise 5.14]) we
obtain
⎛
⎞
Q
a,b
(
N, ϑ
)=
ϕ
(
q
−
1)
μ
(
s
)
ϕ
(
s
)
⎝
⎠
,
S
χ,a,b
(
N, ϑ
)
q
−
1
s|
(
q−
1)
χ∈Y
s
where
μ
denotes the Mobius function and
Y
s
the set of multiplicative characters
of
F
q
of order
s
. The rest follows using the Cauchy-Schwarz inequality from
Theorem 1.
With the notation in Theorem 2, we have the following result.
Theorem 6.
For
1
≤
N
≤
T
f
we have
=
O
2
ν
(
q−
1)
Nq
min
log
q
log
d
,N,t
0
−
1
/
2
.
N
ϕ
(
q
−
1)
Q
f
(
N, ϑ
)
−
q
−
1
ϑ∈
F
q
Proof.
We get the result from Theorem 2 in the same way.
Corollary 4.
For any
0
<ε<
1
and all initial values
ϑ
,exceptatmost
O
(
εq
)
of them, we have
N
=
O
ε
−
1
2
ν
(
q−
1)
max
ϕ
(
q
−
1)
Nq
−
1
/
4
,N
1
/
2
Q
s,a,b
(
N, ϑ
)
−
{
}
q
−
1
for
1
≤
N
≤
T
a,b
, and under the conditions of Theorem 2
=
O
ε
−
1
2
ν
(
q−
1)
N
min
log
q
log
d
,N,t
0
−
1
/
2
N
ϕ
(
q
−
1)
Q
s,f
(
N, ϑ
)
−
q
−
1
for
1
≤
N
≤
T
f
.
