12 1. Elementary Prime Number Theory, I

It follows that

π(N) ≥

log N

log(1 + log N/ log 2)

.

Taking some care to estimate the denominator, we obtain the lower bound

π(N) ≥ (1 + o(1))

log N

log log N

,

which tends to infinity. Similar proofs of Theorem 1.1 have been given

by Thue (1897), Auric (1915), Schnirelmann [Sch40, pp. 44–45], Chernoff

[Che65], and Rubinstein [Rub93]. See also Exercise 17.

6. Sledgehammers!

In the spirit of the saying, “nothing is too simple to be made complicated,”

we finish off the first half of this chapter with two proofs of Theorem 1.1

that dip into the tool chest of higher mathematics.

The following “topological proof” is due to Furstenberg ([Fur55]):

Proof. We put a topology on Z by taking as a basis for the open sets

all arithmetic progressions, infinite in both directions. (This is permissible

since the intersection of two such progressions is either empty or is itself an

arithmetic progression.) Then each arithmetic progression is both open and

closed: it is open by choice of the basis, and it is closed since its complement

is the union of the other arithmetic progressions with the same common

difference. For each prime p, let Ap = pZ, and define A :=

p

Ap. The

set {−1, 1} = Z \ A is not open. (Indeed, each open set is either empty or

contains an arithmetic progression, so must be infinite.) It follows that A is

not closed. On the other hand, if there are only finitely many primes, then

A is a finite union of closed sets, and so it is closed.

Our next proof, due to L. Washington (and taken from [Rib96]) uses

the machinery of commutative algebra. Recall that a Dedekind domain is

an integral domain R with the following three properties:

(i) R is Noetherian: if I1 ⊂ I2 ⊂ I3 ⊂ · · · is an ascending chain of

ideals of R, then there is an n for which

In = In+1 = In+2 = · · · .

(ii) R is integrally closed: if K denotes the fraction field of R and

α ∈ K is the root of a monic polynomial with coeﬃcients in R,

then in fact α ∈ R.

(iii) Every nonzero prime ideal of R is a maximal ideal.