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.
Search WWH ::




Custom Search