4 1. Arithmetic Functions
into T(x) 2 T(x/2) yields
ψ(x) ψ
x
2
+ ψ
x
3
· · · = T(x) 2 T
x
2
.
Then
ψ(x) log(2)x log(4x)
since ψ is an increasing and nonnegative function, and
ψ(x) ψ
x
2
log(2)x + log(x)
for the same reason. Adding up the inequalities
ψ
x
2j
ψ
x
2j+1

log(2)2−jx
+ log(x)
for j = 0, 1, 2,..., [log(x)/ log(2)] 1 yields
ψ(x) 2 log(2)x +
log(x)
log(2)
log(x) 2 log(2)x +
log2(x)
log(2)
since
ψ(x/2j+1)
= 0 when
x/2j+1
2.
The inequalities in Proposition 1.1 and the limits
log2(x)/(x
log(2)) 0
and log(4x)/x 0 as x +∞ imply that for every ε 0 there exists some
x0(ε) so that log(2) ε ψ(x)/x 2 log(2) + ε for x x0(ε). Such ε-
x0(ε) inequalities are often expressed in a somewhat different but equivalent
way, using concepts from analysis. The limit superior lim supx→+∞ f(x) of a
bounded real function f(x) on an interval [a, ∞) is the unique real number σ
such that f(x) σ+ε holds for all x sufficiently large, while f(x) σ−ε fails
for some x arbitrarily large, no matter how small ε 0 is taken. Similarly
the limit inferior lim infx→+∞ f(x) is the unique real number ι such that
f(x) ι ε holds for all x sufficiently large, while f(x) ι + ε fails for
some x arbitrarily large, no matter how small ε 0 is taken. That σ and ι
must necessarily exist is a consequence of the completeness property of the
real number system. Define
a
def
= lim inf
x→+∞
ψ(x)
x
and A
def
= lim sup
x→+∞
ψ(x)
x
.
Then the ε-x0(ε) bounds for ψ(x)/x can be reformulated as the statement
that log(2) a A 2 log(2).
The definitions of ψ and ϑ yield
ψ(x) =
pk≤x
log(p) =

k=1
p≤x1/k
log(p) = ϑ(x) +
ϑ(x1/2)
+
ϑ(x1/3)
+ · · · ,
and so
ψ(x)
2ψ(x1/2)
= ϑ(x)
ϑ(x1/2)
+
ϑ(x1/3)
· · · .
Previous Page Next Page