next up previous
Next: Fine distribution of primes Up: Multiplicative Number Theory and Previous: Primality testing and factorization

Distribution of primes

If we continue to enumerate the prime positive integers, we find that although they occur less and less frequently there still seems to be an unending supply of them. Later, we shall prove that there are in fact infinitely many prime numbers. This theorem first appeared in Euclid's Elements. After establishing that fact, there still remains the general question of how the primes are distributed among the integers. There can be long stretches without primes, and also sudden bunches of primes. This gives their distribution an appearance of randomness. After much calculation, Gauss (at age fifteen) conjectured the approximate size of the function $\pi(X)$ defined to be the number of primes less than or equal to X. First established almost a century later in the 1890's, Gauss' conjecture can be stated as the following limit:

\begin{displaymath}\lim_{X\to \infty} {\pi(X)\over \left(X/\log X\right)} =1.
\end{displaymath}

This says that for very large values of X the number $\pi(X)$ is very close to $X/\log X$. Here, $\log X$ is the natural logarithm (i.e. to the base e). This limit is known today as the ``prime number theorem.''

Actually, Gauss discovered a function much closer to the value of the prime number counting function $\pi(X)$. This is the logarithmic integral

\begin{displaymath}\li(X) = \int_2^X \frac{dt}{\log t}
\end{displaymath}

where $\log t$ means the natural logarithm. Riemann conjectured that the difference is just a shade above $\sqrt
X$. This is an equivalent form of Riemann's Hypothesis:

\begin{displaymath}\lim_{X\to \infty} \dfrac{\pi(X)- \li(X)}{ X^{\frac12 +\epsilon}} =0.
\end{displaymath}

for any $\epsilon > 0$. This is largely agreed to be the most important unsolved problem in number theory.


next up previous
Next: Fine distribution of primes Up: Multiplicative Number Theory and Previous: Primality testing and factorization
David J. Wright
2000-08-24