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