That proves the theorem for even n. Now consider odd n ≥ 3, so n =

2m ’ 1 for m ≥ 2. Since the function x/ log x is increasing for x ≥ 3 (verify),

and since π(2m ’ 1) = π(2m) for m ≥ 2, we have

π(2m ’ 1) = π(2m)

≥ 1 (log 2)(2m)/ log(2m)

2

≥ 1 (log 2)(2m ’ 1)/ log(2m ’ 1).

2

That proves the theorem for odd n. 2

As a consequence of the above theorem, we have π(x) = „¦(x/ log x) for

real x ’ ∞. Indeed, for real x ≥ 2, setting c := 1 (log 2), we have

2

π(x) = π( x ) ≥ c x / log x ≥ c(x ’ 1)/ log x = „¦(x/ log x).

To obtain a corresponding upper bound for π(x), we introduce an auxiliary

function, called Chebyshev™s theta function:

‘(x) := log p,

p¤x

where the sum is over all primes p up to x.

Chebyshev™s theta function is an example of a summation over primes,

and in this chapter, we will be considering a number of functions that are

de¬ned in terms of sums or products over primes. To avoid excessive tedium,

we adopt the usual convention used by number theorists: if not explicitly

stated, summations and products over the variable p are always understood

to be over primes. For example, we may write π(x) = p¤x 1.

The next theorem relates π(x) and ‘(x). Recall the “∼” notation from

§3.1: for two functions f and g such that f (x) and g(x) are positive for all

su¬ciently large x, we write f ∼ g to mean that limx’∞ f (x)/g(x) = 1, or

5.1 Chebyshev™s theorem on the density of primes 77

equivalently, for all > 0 there exists x0 such that (1 ’ )g(x) < f (x) <

(1 + )g(x) for all x > x0 .

Theorem 5.4. We have

‘(x)

π(x) ∼ .

log x

Proof. On the one hand, we have

log p ¤ log x

‘(x) = 1 = π(x) log x.

p¤x p¤x

So we have

‘(x)

π(x) ≥ .

log x

On the other hand, for every x > 1 and δ with 0 < δ < 1, we have

‘(x) ≥ log p

xδ <p¤x

≥ δ log x 1

xδ <p¤x

= δ log x (π(x) ’ π(xδ ))

≥ δ log x (π(x) ’ xδ ).

Hence,

‘(x)

π(x) ¤ xδ + .

δ log x

Since by the previous theorem, the term xδ is o(π(x)), we have for all su¬-

ciently large x (depending on δ), xδ ¤ (1 ’ δ)π(x), and so

‘(x)

π(x) ¤ .

δ 2 log x

Now, for any > 0, we can choose δ su¬ciently close to 1 so that 1/δ 2 <

1 + , and for this δ, and for all su¬ciently large x, we have π(x) < (1 +

)‘(x)/ log x, and the theorem follows. 2

Theorem 5.5. ‘(x) < 2x log 2 for all real numbers x ≥ 1.

Proof. It su¬ces to prove that ‘(n) < 2n log 2 for integers n ≥ 1, since then

‘(x) = ‘( x ) < 2 x log 2 ¤ 2x log 2.

For positive integer m, consider the binomial coe¬cient

2m + 1 (2m + 1)!

M := = .

m m!(m + 1)!

78 The distribution of primes

One sees that M is divisible by all primes p with m + 1 < p ¤ 2m + 1.

As M occurs twice in the binomial expansion of (1 + 1)2m+1 , one sees that

M < 22m+1 /2 = 22m . It follows that

‘(2m + 1) ’ ‘(m + 1) = log p ¤ log M < 2m log 2.

m+1<p¤2m+1

We now prove the theorem by induction. For n = 1 and n = 2, the

theorem is trivial. Now let n > 2. If n is even, then we have

‘(n) = ‘(n ’ 1) < 2(n ’ 1) log 2 < 2n log 2.

If n = 2m + 1 is odd, then we have

‘(n) = ‘(2m + 1) ’ ‘(m + 1) + ‘(m + 1)

< 2m log 2 + 2(m + 1) log 2 = 2n log 2. 2

Another way of stating the above theorem is:

p < 4x .

p¤x

Theorem 5.1 follows immediately from Theorems 5.3, 5.4 and 5.5. Note

that we have also proved:

Theorem 5.6. We have

‘(x) = ˜(x).

Exercise 5.1. If pn denotes the nth prime, show that pn = ˜(n log n).

Exercise 5.2. For integer n > 1, let ω(n) denote the number of distinct

primes dividing n. Show that ω(n) = O(log n/ log log n).

Exercise 5.3. Show that for positive integers a and b,

a+b

≥ 2min(a,b) .

b

5.2 Bertrand™s postulate

Suppose we want to know how many primes there are of a given bit length,

or more generally, how many primes there are between m and 2m for a given

integer m. Neither the statement, nor the proof, of Chebyshev™s theorem

imply that there are any primes between m and 2m, let alone a useful density

estimate of such primes.

Bertrand™s postulate is the assertion that for all positive integers m,

5.2 Bertrand™s postulate 79

there exists a prime between m and 2m. We shall in fact prove a stronger

result, namely, that not only is there one prime, but the number of primes

between m and 2m is „¦(m/ log m).

Theorem 5.7 (Bertrand™s postulate). For any positive integer m, we

have

m

π(2m) ’ π(m) > .

3 log(2m)

The proof uses Theorem 5.5, along with a more careful re-working of the

proof of Theorem 5.3. The theorem is clearly true for m ¤ 2, so we may

assume that m ≥ 3. As in the proof of the Theorem 5.3, de¬ne N := 2m , m

and recall that N is divisible only by primes strictly less than 2m, and that

we have the identity

( 2m/pk ’ 2 m/pk ),

νp (N ) = (5.1)

k≥1

where each term in the sum is either 0 or 1. We can characterize the values

νp (N ) a bit more precisely, as follows:

2m

Lemma 5.8. Let m ≥ 3 and N = as above. For all primes p, we have

m

pνp (N ) ¤ 2m; (5.2)

√

if p > 2m, then νp (N ) ¤ 1; (5.3)

if 2m/3 < p ¤ m, then νp (N ) = 0; (5.4)

if m < p < 2m, then νp (N ) = 1. (5.5)