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 suﬃciently 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 suﬃciently 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)

− · · · .