6 1. Arithmetic Functions

1.2. Bertrand’s Postulate

The method of Chebyshev does not prove the Prime Number Theorem,

but it does show that ψ(x) has the expected order of growth. By a more

elaborate version of his method Chebyshev obtained bounds such as .921·x ≤

ψ(x) ≤ 1.106·x for all x suﬃciently large. He used these bounds to give the

first proof of Bertrand’s Postulate. Today Bertrand’s Postulate is taken as

the statement that for all x ≥ 2 there is at least one prime in the interval

(x/2,x]. The weaker bounds in Proposition 1.1 do not suﬃce to prove this

with Chebyshev’s approach. But we shall obtain the result anyway using an

idea of S. A. Ramanujan.

Proposition 1.2 (Bertrand’s Postulate). For every x ≥ 2 there exists at

least one prime p with x/2 p ≤ x.

Proof. For 2 ≤ x ≤ 797 the interval (x/2,x] contains a prime by a trick of

E. G. H. Landau: The chain 2, 3, 5, 7, 11, 17, 31, 59, 107, 211, 401, 797 consists

of primes and each is smaller than twice its predecessor. To detect primes in

the intervals (x/2,x] for x ≥ 797 we show that the difference ϑ(x) − ϑ(x/2)

is positive.

Fetch the inequality

ψ(x) − ψ

x

2

+ ψ

x

3

≥ T(x) − 2 T

x

2

from the proof of Proposition 1.1. Retention of the term ψ(x/3) is an idea

due to Ramanujan. Now

ϑ(x) − ϑ

x

2

≥ ψ(x) −

2ψ(x1/2)

− ψ

x

2

≥ T(x) − 2 T

x

2

− ψ

x

3

−

2ψ(x1/2)

≥ log(2)x − log(4x) − 2 log(2)

x

3

−

log2(x/3)

log(2)

− 4

log(2)x1/2

− 2

log2(x1/2)

log(2)

= f(x)

with

f(x) =

log(2)

3

x − log(4x) −

3

log2(x)

2 log(2)

− 4

log(2)x1/2,

by Proposition 1.1 and its proof. The derivative

f (x) =

log(2)

3

−

1

x

−

3 log(x)

x log(2)

−

2 log(2)

x1/2

is an increasing function on x ≥ 797 since log(x)/x is decreasing on x ≥ e.

Then f (x) 0 on x ≥ 797 because f (797) = 0.14. Thus f(x) is increasing

on this interval and hence positive there because f(797) = 1.2.