Information Technology Reference
In-Depth Information
re k
Denoting
F
=
{
|
k
∈L}
we deduct
2 ν
L 2 ν
2 ν
T 2 ν− 1
|
S χ |
χ ( R f ( u ))
u
IF p
f∈F
R f j ( u ) R f ν + j ( u ) p− 2
ν
.
T 2 ν− 1
χ
f 1 ,...,f 2 ν ∈F
u∈ IF p
j =1
For the case that no integer in the set ( f 1 ,...,f ν +1 ,...,f 2 ν )appearsonly
once we use the trivial bound p for the inner sum. Since in this case there are
at most ν different values in ( f 1 ,...,f ν +1 ,...,f 2 ν )thereareatmost L ν
such
cases, which gives the total contribution
O ( L ν p ) .
Otherwise, to apply Lemma 2 we have to show that the polynomial
ν
g f j ( X ) h ν + j ( X )( h j ( X ) g f ν + j ( X )) p− 2
Ψ f 1 ,...,f 2 ν ( X )=
(6)
j =1
is not, up to a multiplicative constant, an s th-power of a polynomial, where
s> 1 denotes the order of χ . We cancel all elements which appear in both
sets
{
f 1 ,...,f ν }
and
{
f ν +1 ,...,f 2 ν }
.Let f> 1 be the largest number in
{
which is not eliminated. We may assume f<p . We show that
g f ( X ) has a zero which is neither a zero of any h f ( X )with f
f 1 ,...,f 2 ν }
f nor a zero
of any g f ( X )with f <f .
With (2) we obtain
( X + ξ ) k
( X + ζ ) k =( ξ
ζ ) h k ( X ) .
Hence, h k ( x 0 ) = 0 if and only if
x 0 + ξ
x 0 + ζ
k
=1 ,
(7)
i.e., ( x 0 + ξ ) / ( x 0 + ζ )isa k -th root of unity. Similarly using
ζ ( X + ξ ) k
ξ ( X + ζ ) k =( ζ
ξ ) g k ( X )
we get g k ( x 0 ) = 0 if and only if
x 0 + ξ
x 0 + ζ
k
ξ
ζ
= ζ p− 1 .
=
Let α> 1 be the order of ζ p− 1 , i.e., α
p + 1, put l = αf and let ρ be a suitable
primitive l th root of unity in an appropriate extension field of IF p ,whichexists
since f<p and thus gcd( l, p ) = 1, such that
|
ξ
ρζ
z 0 =
ρ
1
Search WWH ::




Custom Search