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