Theorem 1 (Euler)

Chebyshev’s theorem

Theorem 3 (Chebyshev). There exist constants a and A, 0 < a < A, such that


x x
a · _{log x} < π(x) < A · _{log x}, for sufficiently large x.

Proof. Let


l = lim inf
x→∞


π(x) x/ log x


, L = lim sup
x→∞


π(x) x/ log x

We shall prove Theorem 3 by showing that L ⩽ 4 log 2, and l ⩾ log 2. By Theorem 2 these two inequalities are equivalent to

L = lim sup
x→∞
^ϑ(x) 4 log 2; (7)

⩽
x

Proof of (7). The binomial coefficient
l = lim inf
x→∞
ψ(x) x
⩾ log 2. (8)

_{N =} 2n ₌ (n + 1)(n + 2) · · · (2n)

has the following properties:

n 1 · 2 · 3 · · · n

1. 
   _2n (b)
   

1. 
   N is an integer, and N < 2 < (2n + 1)N (9)
   

where the first inequality follows as N occurs in the binomial expansion of (1 + 1)²ⁿ, which has (2n + 1) positive terms; while the second from the fact that N is the largest among these (2n + 1) terms.

2. 
   N is divisible by the product of all primes p, such that n < p ⩽ 2n, because every such prime appears in the numerator of N , and not in its denominator.
   

Because of (ii), we have N ⩾ ^Q_n
⩽2n p, hence

⩾
(9)
2n log 2 > log N
n<Σp⩽2n
log p = ϑ(2n) − ϑ(n). (10)

If we set n = 1, 2, 2², · · · , 2^m−1 in (10), and add the resulting inequalities, we get

Σ
m
ϑ(2^m) = ϑ(2^m) − ϑ(1) < 2^r log 2 < 2^m+1 log 2,
r=1
since ϑ(1) = 0.
Now fix x > 1. Choose m ∈ Z such that 2^m−1 ⩽ x < 2^m. Since ϑ is non-decreasing, (11) gives

x
ϑ(x) ⩽ ϑ(2^m) < 2^m+1 log 2 ⩽ 4x log 2, and hence ^ϑ(x) < 4 log 2,

from which we can deduce

⩽
as claimed in (7).


L = lim sup
x→∞
^ϑ(x) 4 log 2, x

Proof of (8). The second part of theorem is proved differently, for which we need the following lemma.
We say that a prime p divides the integer n exactly k times, if p^k | n, and p^k+1 ∤ n.
Lemma. The number of times a prime p exactly divides m! is equal to

p

_p2

_p3
, ^m , + , ^m , + , ^m , + · · · ,


where the sum above is finite since ⌊x⌋ = 0 for 0 < x < 1.
Proof. Among the integers 1, 2, . . . , m, there are exactly ⌊m/p⌋ which are divisible by p, namely

p
p, 2p, . . . , , ^m ,p.

, ,
The integers between 1 and m which are divisible by p² are


p², 2p², . . . , ^m p²,
_p2

which are ⌊m/p²⌋ in number, and so on.

The number of integers between 1 and m which are divisible by p exactly r times, is therefore
⌊m/p^r⌋ − ⌊m/p^r+1⌋. Hence p divides m! exactly

_pr

_pr+1

_pr

_pr

_pr
_Σ r , _m , − , _m

_r⩾1

, = ^Σ r, ^m , − ^Σ(r − 1), ^m , = ^Σ, ^m ,

_r⩾1

_r⩾2

_r⩾1

times, which proves the lemma.

In order to prove (8), we fix n ∈ Z_⩾1, and consider the integer

n

(n!)²
_{N =} 2n ₌ (2n)! _.



Let p be any prime, such that p ⩽ 2n. By virtue of the previous lemma, the numerator of N is divisible by p exactly ⌊2n/p⌋ + ⌊2n/p²⌋ + · · · times, and n! is divisible by p exactly ⌊n/p⌋ + ⌊n/p²⌋ + · · · times, so that the denominator of N is divisible by p exactly 2 ⌊n/p⌋ + ⌊n/p²⌋ + · · · times.
Hence N is divisible by p exactly v_p times, where

p

_pr

_pr
v = _Σ , _2n , − 2, _n ,

_r⩾1

Therefore, since N cannot be divisible by any prime larger than 2n,



Y
N = p^vp .

Since ^{, 2n ,} = ^{, n ,} = 0 when p^r > 2n, i.e., when r > ⌊log 2n/ log p⌋, we have
p⩽2n

, ,
_pr _pr



_Σ , ,
v_p =
^Mp 2n _pi
i=1
— 2, _n ,


, where M_p =
log 2n log p
. (11)

_pi
Note that, for any y ∈ R, we have 2⌊y⌋ ⩽ 2y < 2⌊y⌋+2 and ⌊2y⌋ ⩽ 2y < ⌊2y⌋+1, hence −1 < ⌊2y⌋−2⌊y⌋ < 2. Since ⌊2y⌋ − 2⌊y⌋ ∈ Z, we can deduce that
⌊2y⌋ − 2⌊y⌋ ∈ {0, 1}. (12)

Combining (11) and (12), we get v_p ⩽ M_p, and hence
N = ^Y p^vp ⩽ ^Y p^Mp , i.e., log N ⩽ ^Σ M_p log p. (13)

Recall from (9) that

p⩽2n
p⩽2n
p⩽2n

2²ⁿ < (2n + 1)N, i.e., 2n log 2 < log(2n + 1) + log N.

Combining this result with (3), (11) and (13) yields

(3)
ψ(2n) =

log 2n log p

_Σ , ,

⩽
p 2n


log p

(11)
=

pΣ⩽2n


M_p log p

(13)
⩾ log N > 2n log 2 − log(2n + 1). (14)

Now fix x > 2, and set n = ⌊x/2⌋ ∈ Z_⩾1. Then n > (x/2) − 1 and x ⩾ 2⌊x/2⌋ = 2n. Since ψ is non-decreasing, (14) gives

ψ(x) ⩾ ψ(2n)
(14)
> 2n log 2 − log(2n + 1) > (x − 2) log 2 − log(x + 1).

Dividing by x on both sides, we get

x

x

x
ψ(x) _> x − 2 _{· log 2 −} log(x + 1) _.

Since (x − 2)/x → 1 and x⁻¹ log(x + 1) → 0, as x → ∞, we obtain the desired inequality:

ψ(x)

l = lim inf
^x→∞ x
⩾ log 2.

Corollary. Let p_n be the n-th prime. There exist constants c and C, 0 < c < C, such that:



^Σ 1_{· ·}
x
c log log x < < C log log x, for sufficiently large x.
n=1 ^pn


Proof. Theorem 3 tells us that there exist constants a and A, 0 < a < A, such that


x x
a · _{log x} < π(x) < A · _{log x}, for sufficiently large x.
Let n₀ ∈ Z_⩾3 be large enough, such that ∀n ⩾ n₀ : (i) a · p_n/ log p_n < π(p_n) < A · p_n/ log p_n,
(ii) log p_n < a^√p_n.
Fix n ⩾ n₀. Note that n < p_n and π(p_n) = n, hence

(i)
n log n < π(p_n) log p_n < A · p_n, (15)

_√ (ii) _pn (i)

n
p_n < a · _{log p}
< π(p_n) = n. (16)

Thus log p_n < 2 log n, and hence


ap_n
(16)
< n log p_n < 2n log n, (17)

a


2n log n
(17) ₁
<
p_n

(15)
<

A


n log n


. (18)

From (18) we can deduce the corollary, because of the following calculation:

x

ⁿ0

Σ

Σ
∀x ⩾ eⁿ⁰ :
^Σ 1 ₌
⌊x⌋




0


1 ₊ ^Σ 1

Σ

n=1 ^pn
(18)
< A ·

(16)
< A ·

⌊x⌋


ⁿ⁼ⁿ0 ⁺¹

Σ
⌊x⌋



∫
ⁿ⁼ⁿ0 ⁺¹
1
+
n log n


1
+
n log n
^pn

n=1 ^pn

n=n +1 ^pn
1
n
n=1

Σ
ⁿ0²
1
n
n=1

⩽ A ·
⌊x⌋ _dy
+ 1 +
_n0 y log y
ⁿ⁰2 dy

∫
₁ y

= A · log log⌊x⌋ − A · log log n₀ + 1 + log n₀²

⩽ A · log log x + 1 + 2 log n₀

2. 
   

⩽ A · log log x + log log x + 2 log log x

= (A + 3) · log log x,

where (b) follows from x ⩾ eⁿ⁰ , i.e., log log x ⩾ log log eⁿ⁰ = log n₀;

∀x ⩾ n₀^{log n0} :

x



^Σ 1
n=1 ^pn


1

x

Σ

n

⩾
p
ⁿ⁼ⁿ0

₂ ·
x

>
(18) _a
^Σ 1

ⁿ⁼ⁿ0

ⁿ log n

2

∫
⩾ ^a ·
a
⌊x⌋+1 _dy
n0 y log y
a

= ₂ · log log(⌊x⌋ + 1) − ₂ · log log n₀

(c) _{a a}

⩾ ₂ · log log x − ₄ · log log x


a
= ₄ · log log x,



where (c) follows from x ⩾ n₀^{log n0} , i.e., log log x > log log n₀^{log n0} = log(log n₀ · log n₀) = 2 log log n₀.

3.