Chapter 16. Distribution of Primes

Next Chapter

The problem of understanding the distribution of the prime numbers has been an important one since ancient times. Euclid showed that there are infinitely many primes. While numerous tables of primes were constructed, nothing else was proved about the primes until the middle of the nineteenth century, pointing to the great difficulty of the subject. Knowledge of the distribution of primes is of fundamental importance in number theory. The majority of results in the theory are accessible only by the use of complex function theory. There are some results that do not require complex analysis, and we study a few such theorems in this chapter. We will obtain some estimates on the prime number function and prove Bertrand's postulate that there is a prime number between a natural number n and 2n.

We denote by the number of primes less than or equal to x. There are large gaps in the sequence of primes, and it is also expected that there are infinitely many twin primes. This illustrates that is not a simple function to analyze. There are two problems associated with . One is to compute for a given value of x (say or ) without listing all the primes. The second is to describe the laws governing . The first problem is easier to solve, though the actual computation can be time consuming. The second problem is more difficult, and we discuss some results giving bounds on for large x.

We start with a discussion of Legendre's formula for the computation of (this is an application of the Principle of Inclusion-Exclusion). An elementary proof of Chebyshev's estimates on are given in the next two sections. The results of Chebyshev were the first results about the number of primes since Euclid's proof of the infinitude of primes. Chebyshev's estimates lead to a proof of Bertrand's postulate, which states that there is a prime between n and 2n for every n>1.

The last section is a discussion of the Riemann -function and its connection with prime numbers. The text includes a description of the relation between the distribution of primes and zeros of the -function. In addition, we prove the celebrated formula