Information Technology Reference
In-Depth Information
The second claim follows from the fact that
Δ
n
(1) = 4 (see the proof of
Lemma 2).
Lemma 7.
We have
N
(
π
n
|
−
1)
|
lim
n→∞
=1
.
2
n
N
(
π
n
Thus for every
>
0
,if
n
is suciently large
log
2
|
−
1)
−
n
|≤
.
Proof:
Fix
y
∈{
0
,
1
,
···
,d
−
1
}
and consider just the
n
of the form
n
=
xd
+
y
,
x
≥
0. Then
=
|
d−
1
d−
1
N
(
π
n
i
=0
(
p
x
ζ
yi
π
y
|
−
1)
|
−
1)
|
p
−x
ζ
−yi
π
−y
)
=
(1
−
.
2
n
2
n
i
=0
This has limit 1 as
x
tends to infinity since
p
−x
tends to zero. The last statement
is immediate.
Suppose
π
n
1 is irreducible, so in the sum in equation (6),
q
equals
π
n
1or
1. The term with
q
= 1 is zero, so by Lemma 7, for any
>
0, if
n
is suciently
large, the sum is at least
n
−
−
.Thus
E
n
≥
−
n
−
O
(1).
In general we have
E
n
∈
Theorem 2.
n
−
O
(log(
n
))
.
Proof:
We have
N
k
k
1
2
n
E
n
=
z
m
i
i
Δ
n
z
m
i
i
log
2
−
c
−
1
.
(7)
i
=1
i
=1
(
m
1
,··· ,m
k
)
∈I
m
i
not all 0
Let
Δ
0
,n
(
x
)=
1 if
x
is a unit
Δ
n
(
x
)otherwise.
Thus
t
Δ
0
,n
(
z
i
)=
t
.
|
N
(
z
)
|
i
=0
Then note that the right hand side of equation (7) is unchanged if we replace
Δ
n
by
Δ
0
,n
. Thus (after a long calculation that we omit due to lack of space)
k
k
1
2
n
E
n
≥
Δ
0
,n
(
z
m
i
m
i
log
2
(
|
N
(
z
i
)
|
)
)
−
O
(1)
i
(
m
1
,··· ,m
k
)
∈I
i
=1
i
=1
k
N
(
π
n
N
(
π
n
log
p
(
|
N
(
z
)
|
)
≥
|
−
1)
|
−
|
−
1)
|
N
(
π
n
log
p
(
|
−
1)
|
)
1
−
O
(1)
.
2
n
2
n
|
N
(
z
)
|−
=1