Information Technology Reference
In-Depth Information
4 Distribution of Powers and Primitive Elements
∈
F
q
is called an
s
th power
if the
For a positive divisor
s
of
q
−
1, an element
w
equation
w
=
z
s
has a solution in
F
q
.
Let
R
s,a,b
(
N, ϑ
)and
R
s,f
(
N, ϑ
)bethenumberof
s
th powers among
u
0
,
u
1
,...,u
N−
1
and
x
0
,x
1
,...,x
N−
1
, respectively, with initial value
ϑ
.
Theorem 3.
Let
q
be a prime power and
s>
1
be a divisor of
q
−
1
. We have
=
O
max
N
s
Nq
3
/
4
,N
1
/
2
q
R
s,a,b
(
N, ϑ
)
−
{
}
for
1
≤
N
≤
T
a,b
.
ϑ∈
F
q
Proof.
Let
X
s
denote the set of multiplicative characters
χ
for which
χ
(
w
)=1
for any
s
th power
w
∈
F
q
. By [6, Theorem 5.4] we obtain
χ
(
w
)=
1
,
if
w
1
s
∈
F
q
is an
s
th power,
0
,
otherwise
,
χ∈X
s
where we used the convention
χ
0
(0) = 0 for the trivial character
χ
0
of
F
q
.
Therefore
R
s,a,b
(
N, ϑ
)=
1
s
S
χ,a,b
(
N, ϑ
)
.
χ∈X
s
The contribution to
R
s,a,b
(
N
) of the sum corresponding to the trivial character
is either (
N
−
1)
/s
or
N/s
. Therefore
≤
N
s
1
s
+
1
R
s,a,b
(
N, ϑ
)
−
|
S
χ,a,b
(
N, ϑ
)
|
.
s
χ∈X
s
\{χ
0
}
Summing over
ϑ
and applying the Cauchy-Schwarz inequality to
q
1
/
2
S
χ,a,b
(
N
)
1
/
2
,
∈
F
q
|
S
χ,a,b
(
N, ϑ
)
|≤
ϑ
we get the result by Theorem 1.
With the notation of Theorem 2, we have the following result.
Theorem 4.
Let
q
be a prime power and
s>
1
be a divisor of
q
−
1
.Then
=
O
Nq
min
log
q
log
d
,N,t
0
−
1
/
2
N
s
R
s,f
(
N, ϑ
)
−
ϑ∈
F
q
for
1
≤
N
≤
T
f
.
Proof.
The result is proved analogously to the previous theorem using
Theorem 2.