Chapter 1
Arithmetic Functions
1.1. The method of Chebyshev
Around 1792 J. K. F. Gauss counted primes in successive blocks of a thou-
sand integers, and noticed that the sequence of primes seems to thin out
according to a definite law. One formulation of his law is that the intervals
(x h, x] contain about h/ log(x) primes when x is large and h is not too
small. Another way to express the same empirical observation is that the
chance of a randomly chosen large integer n being prime is approximately
1/ log(n). Gauss went on to integrate this density to obtain the approxima-
tion
π(x)
def
=
p≤x
1 li(x)
def
=
x
2
du
log(u)
for the counting function π(x) of the primes. Here li(x) is the integral loga-
rithm. By his counts of primes, Gauss guessed that limx→+∞ π(x)/li(x) = 1.
This is simply the statement that the relative error |π(x) li(x)|/π(x) in
the approximation goes to zero as x +∞. Using the notation
f(x) g(x)
def
⇐⇒ lim
x→+∞
f(x)
g(x)
= 1
of asymptotic equality familiar from analysis, the conjecture can be ex-
pressed as π(x) li(x). This is the Prime Number Theorem (abbreviated
PNT) first proved by J. S. Hadamard and C. G. J. N. de la Vall´ ee Poussin
in 1896. Since li(x) x/ log(x) by l’Hˆ opital’s rule, the PNT also has the
formulation π(x) x/ log(x), showing that about 1/ log(x) of the positive
integers up to x are prime.
Because the density of the primes near n is approximately 1/ log(n), it
may be more natural to count each prime p with weight log(p) rather than
1
Previous Page Next Page