\documentstyle{psapm-l}
\newcommand{\dd}{\ldots}
\newcommand{\tht}{\theta}
\newcommand{\af}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\la}{\lambda}
\newcommand{\cd}{\cdots}
\newcommand{\mem}{\in}
\newcommand{\lt}{\left(}
\newcommand{\rt}{\right)}
\newcommand{\lf}{\lfloor}
\newcommand{\rf}{\rfloor}
\def\binom#1#2{{#1}\choose{#2}}
\newcommand{\dis}{\displaystyle}
\newcommand{\df}{\displaystyle\frac}
\newcommand{\ds}{\displaystyle\sum}
\newcommand{\In}{\infty}
\newcommand{\wg}{\sim}
\newcommand{\Tht}{\Theta}
\newcommand{\sq}{\sqrt}
\newcommand{\ep}{\epsilon}
\newcommand{\RR}{{\Bbb R}}
\newcommand{\CC}{{\Bbb C}}
\newcommand{\ZZ}{{\Bbb Z}}
\newcommand{\Om}{\Omega}
\begin{document}
\title[ANALYTIC COMPUTATIONS IN NUMBER THEORY]{Analytic Computations in Number Theory}
\author[ANDREW M. ODLYZKO]{Andrew M. Odlyzko}
\address{AT\&T Bell Laboratories, Murray Hill, New Jersey 07974}
\email{amo@@research.att.com}
\subjclass{Primary 11Y35, 11E45, 11M26.
Secondary 11N05}
\thanks{This paper is in final form and no version of it will be submitted for publication elsewhere.}
\maketitle
\begin{abstract}
Number theory has been intimately associated with computation since
ancient times.
The early calculations were all with integers
or rationals.
However, starting with Riemann's discovery of the connection between
distribution of primes and zeros of the Riemann zeta function, there
has been intensive work on computation of analytic functions, concentrating
on their zeros.
The most extensive computations were those designed to test
the truth of the Riemann Hypothesis as well as some other conjectures
about the distribution of zeros of the Riemann zeta function and some related $L$-functions.
Large computations of zeros have also been carried out to
disprove conjectures about distributions of arithmetical functions,
and to prove explicit bounds for various
functions.
This paper surveys the general area of computations of zeros of
Dirichlet series and their applications, as well as of other computations in number theory that deal with analytic functions.
\end{abstract}
\section{Introduction}
Number theory and computation have been intimately connected
since ancient times.
The computations were usually those on the integers, involving
factorizations into primes or solving diophantine equations.
However, there is also a large area of computational
number theory that involves analytic functions.
Its origins are often dated to Riemann, who was the first one
to discover the close connection between the distribution of primes and zeros of $\zeta (s)$, the Riemann zeta function.
This function is defined for $s \in \CC$, $\mbox{Re} (s) > 1$, by
\begin{equation}
\zeta (s) = \sum_{n=1}^\infty \frac{1}{n^s} ~.
\label{eq101}
\end{equation}
It is possible to trace this history even further back, about two centuries before Riemann.
In 1650 Pietro Mengoli, an Italian mathematician, published a book on
summation of series.
In it he raised the question of evaluating
\begin{equation}
\sum_{n=1}^\In \frac{1}{n^2} = \zeta (2) ~.
\label{eq102}
\end{equation}
Mengoli's question stimulated substantial research, with the
most significant contributions coming from Euler.
(See \cite{Ay} for a beautiful survey of Euler's contributions in this area.)
In attempting to evaluate $\zeta (2)$ numerically, Euler
invented what is today called the Euler-Maclaurin summation
formula, which we will discuss further in \S2.
This established an early connection between numerical
analysis and number theory.
Later, Euler discovered the exact formula
\begin{equation}
\zeta (2) = \sum_{n=1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6}
\label{eq103}
\end{equation}
(as well as similar formulas for $\zeta (4), \zeta (6) , \dd$).
His argument was not rigorous by modern standards,
but can be made rigorous using the theory of
analytic functions that was developed in the 19th century.

Euler's contributions to the theory of the zeta function that are mentioned above were all to numerical or closed-form summations.
Perhaps the most important observation that Euler made, though,
was that the zeta function has connections to number theory.
He obtained the Euler product formula
\begin{equation}
\zeta (s) = \prod_p (1-p^{-s} )^{-1} ,~~~
\mbox{Re} (s) > 1 ~,
\label{eq104}
\end{equation}
where $p$ runs over all the primes.
This shows that $\zeta (s)$ determines the distribution of primes.
The product formula (\ref{eq104}) allowed Euler to deduce, for example, that the sum of the reciprocals of the primes diverges.

Euler's work did not deal with the behavior of $\zeta (s)$ as an analytic function, and neither did that of various other mathematicians who
followed him during the next century.
Dirichlet, for example, introduced the Dirichlet $L$-functions,
\begin{equation}
L(s, \chi ) = \sum_{n=1}^\infty \chi (n) n^{-s} , ~~~
\mbox{Re} (s) > 1 ~,
\label{eq105}
\end{equation}
where $\chi$ is a Dirichlet character modulo an integer $q$.
He used them in his proof that there are infinitely many primes
in any arithmetic progression $a$, $a+q$, $a+2q, \ldots$
for which $(a,q) =1$.
While he did have to show that these $L$-functions do not have zeros at $s=1$, he did not consider their behavior far away from the real axis.

The importance of the analytic behavior of $\zeta (s)$ for number
theory was pointed out by Riemann in his path-breaking paper \cite{R}.
The definition (\ref{eq101}) applies only for $\mbox{Re} (s) > 1$ and
shows easily that $\zeta (s)$ is analytic there.
Riemann showed that $\zeta (s)$ can be continued analytically to the entire complex plane with the exception of $s=1$,
where it has a first-order pole.
Further, Riemann observed that the zeros of $\zeta (s)$ determine the distribution of primes.
His formulas relating primes to zeros were only proved in the 1890s, after the necessary analytic machinery was developed by
Hadamard, Weierstrass, and others.
However, he did outline the path that was
eventually followed in the study of the distribution of primes, and
eventually yielded the proof of the Prime Number Theorem
(PNT),
\begin{equation}
\pi (x) \sim \frac{x}{\log x} \text{\,\,\,\,\,\,\,\,as\,\,\,\,\,\,\,\,}  x \to \In ~,
\label{eq107}
\end{equation}
which had been conjectured by Gauss and Legendre.
(Throughout the paper, $\log x$ denotes the natural logarithm of $x$.)
Moreover, this approach gave a more precise form of the PNT, namely
\begin{equation}
\label{eq108}
| \pi (x) - \text{li} \,(x) | \le c_1 \exp
(-c_2 ( \log x)^{1/2} )
\end{equation}
for some constants $c_1, c_2 > 0$, where
\begin{equation}
\label{eq109}
\text{li}\, (x) = \int_0^x \frac{du}{\log u} ~,
\end{equation}
and the integral is the Cauchy principal value.
We note that
\begin{equation}
\label{eq110}
\text{li}\,(x) \sim \frac{x}{\log x} \text{\,\,\,\,\,\,\,\,as\,\,\,\,\,\,\,\,} x \to \In ~.
\end{equation}

The best bounds for the error term in the PNT that are known are not much smaller than the one in (\ref{eq108}).
On the other hand, if the Riemann Hypothesis (RH) is true, so that all the zeros of $\zeta (s)$ in $\mbox{Re} (s) > 0$ lie on the critical line
$\mbox{Re} (s) = 1/2$, then
\begin{equation}
\label{eq111}
| \pi (x) - \text{li} \, (x) | \le c_3 x^{1/2} \log x
\end{equation}
for some $c_3 > 0$.
Hence if the RH is true, the error term in the PNT
is only about the square root of the main term.

It is not known what led Riemann to conjecture the RH.
It was thought by some mathematicians, such as Felix Klein, that Riemann was motivated by a
sense of general beauty and symmetry in mathematics.
However, as a result of C.~L. Siegel's study \cite{Sie1} of Riemann's
unpublished notes, we now know that
Riemann did obtain extensive numerical data about $\zeta (s)$ and its zeros, and that to do so he derived advanced computational techniques.
We will discuss this in \S2.

The importance of the RH has led to numerous attempts to prove it.
At first it was not realized just how difficult a problem this is.
Eventually, however, the perception of the difficulty of the RH changed, and a series of attempts were made to verify it
numerically for initial sets of zeros.
Section~2 describes these computations.

While computations designed to verify the RH are the most
widely known, there have been many others as well,
dealing with the zeta function as well as other functions
in analytic number theory.
Many, especially the large-scale ones, were designed to test
conjectures such as the RH and its generalizations.
However, there have also been many computations aimed at indirect disproofs of number-theoretic conjectures, explicit bounds for arithmetical functions,
and others.
The purpose of this paper is to present a brief survey of this wide variety of different analytic computations.
An excellent introduction to analytic number theory is given by \cite{Daven}, and readers not
familiar with this subject can find definitions and motivation there.
\section{Algorithms and computations}
We first consider zeros of the Riemann zeta function.
(For general information about $\zeta (s)$, see the
books \cite{Iv,Pat,Tit2}.)
Since $\zeta (s) \in \RR$ for $s \in \RR$, $s > 1$,
we find that $\zeta ( \overline{\rho}) =0$ whenever $\zeta ( \rho ) =0$.
Therefore we need to consider only the zeros $\rho$ with $\mbox{Im} ( \rho ) \ge 0$.
The Euler product (\ref{eq104}) shows $\zeta (s)$ has no zeros in
$\mbox{Re} (s) > 1$.
The functional equation of the zeta function,
\begin{equation}
\xi (s) = \xi (1-s)~,
\label{Neq201}
\end{equation}
where
\begin{equation}
\xi (s) = \frac{1}{2} s(s-1) \pi^{-s/2} \Gamma (s/2) \zeta (s) ~,
\label{Neq202}
\end{equation}
then shows that
$\zeta (s)$ has no zeros in $\mbox{Re} (s) < 0$ except
for the {\em trivial zeros} at $s = -2,-4,-6 , \ldots$.
All the {\em nontrivial zeros} (i.e., those in the {\em critical strip}
$0 \le \mbox{Re} (s) \le 1$) are strictly inside the critical
strip, and none are real.
The first 5 zeros in the upper half-plane
$1/2 + i \gamma_n$, $1 \le n \le 5$ (first in order of distance from the real axis) are
listed in Table~1.
They all lie on the {\em critical line} $\mbox{Re} (s) = 1/2$, and thus
satisfy the RH.
\begin{table}[htb]
$$
\begin{array}{c|c}
n & \gamma_n \\ \hline
1 & 14.13472514173469379045... \\
2 & 21.02203963877155499262... \\
3 & 25.01085758014568876321... \\
4 & 30.42487612585951321031... \\
5 & 32.93506158773918969066... \\
\end{array}
$$

\caption{Ordinates of first 5 zeros of $\zeta (s)$.}
\end{table}

Table~2 lists the successive published records in proving that the first $n$ zeros of the zeta function
satisfy the RH.
Thus the first such result was that of Gram in 1903, who showed that
the RH holds for the first 15 zeros.
The latest result is that of van~de Lune, te~Riele,
and Winter \cite{LRW2},
who showed that the RH is valid for the first $1.5 \times 10^9$ zeros.
\begin{table}[htb]
$$
\begin{array}{l|r}
\multicolumn{1}{c}{\mbox{Investigator}} &
\multicolumn{1}{c}{n} \\ \hline
\mbox{Gram (1903)} & 15 \\
\mbox{Backlund (1914)} & 79 \\
\mbox{Hutchinson (1925)} & 138 \\
\mbox{Titchmarsh et al. (1936)} & 1,041 \\
\mbox{Turing (1953)} & 1,104 \\
\mbox{Lehmer (1956)} & 25,000 \\
\mbox{Meller (1958)} & 35,337 \\
\mbox{Lehman (1966)} & 250,000 \\
\mbox{Rosser et al. (1969)} & 3,500,000 \\
\mbox{Brent (1979)} & 81,000,001 \\
\mbox{van de Lune et al. (1986)} & 1,500,000,000 \\
\end{array}
$$

\caption{Numerical verification of the Riemann Hypothesis for the first $n$ zeros.}
\end{table}

It should be emphasized that the verifications that the RH holds for a given number of
zeros are in principle completely rigorous.
The functional equation~(\ref{Neq201}) and the relation $\zeta (s) = \overline{\zeta ( \overline{s})}$ imply that $\xi (1/2 + it) \in \RR$ for
$t \in \RR$.
Therefore, sign changes of $\xi (1/2 + it)$ correspond to
zeros of $\zeta (s)$ that are exactly on the critical line, not just
close to it.
If we find $n$ sign changes in the range $0 < t < T$, and then
establish using the principle of the argument that there are exactly
$n$ zeros of $\zeta (s)$ in $0 < \mbox{Im} (s) < T$, then all the
zeros in that region have to lie on the critical line.
(In practice one does not even have to use the principle of
the argument, as there is a beautiful method of Turing
\cite{Ed,Od3}, based on a theorem of Littlewood, which gives the same conclusion from
just the calculations on the critical line.)
What is required for this approach to the verification of the RH for a certain number of zeros to work is an effective algorithm for computing
$\zeta (s)$ with a guaranteed error term.
It is also necessary that all the zeros be simple and lie on the critical line.
This has been shown to hold for all the zeros that have been examined.

The increase by a factor of $10^8$ between 1903 and 1986 in the
numbers of zeros for which the RH has been verified was due to a large extent to advances in technology,
with the van~de Lune et~al. \cite{LRW2} calculations taking around two months on a large supercomputer.
However, just as important have been advances in algorithms.
The early computations, namely those of Gram, Backlund, and Hutchinson, were all
carried out using the Euler-Maclaurin summation formula.
This method is effective and is still used today for
high-precision computations of low-order zeros, since it is simple to implement.
However, it is not efficient
for only moderately accurate calculations of high zeros, since it
requires on the order of $t$ steps to compute $\zeta (1/2 +it)$.
Zero number $1.5 \times 10^9$ of $\zeta (s)$ is at height approximately $5 \times 10^8$,
so extensive computations at that height would be impractical with the
Euler-Maclaurin formula.
Fortunately, there are better methods.
All the computations listed in Table~2, starting
with that of Titchmarsh in the 1930s, have used the Riemann-Siegel formula, which
allows one to compute $\zeta (1/2 + it)$ in about $t^{1/2}$ steps.
The Riemann-Siegel formula is not a general-purpose
tool like the Euler-Maclaurin one.
The latter can be used for a variety of computations of sums where the terms vary smoothly with the index of summation.
The Riemann-Siegel formula applies only to the zeta function (although there are generalizations to some similar Dirichlet series, as we will mention later).

A remarkable fact about the Riemann-Siegel formula is that it was known
to Riemann in the 1850s! It was discovered in Riemann's unpublished
notes by Siegel \cite{Sie1}.
Siegel's name deserves to be associated with it, since it
required extensive work and deep insight to figure out what Riemann had done.
Riemann had computed several zeros of the zeta function and possessed a deep understanding of its analytic behavior.
It is not certain how large an influence this had in his proposal of the RH.
However, it does prove that he did not make that conjecture in the absence of any
numerical data, as Klein had thought.

Recently, an even faster method for simultaneous computation of
large sets of zeros of the zeta function was invented by
A. Sch\"{o}nhage and the author \cite{Od1,Od4,OS}.
It makes possible the computation of the approximately
$T^{1/2}$ zeros of $\zeta ( 1/2 + it)$ in an interval
$T \le t \le T + T^{1/2}$ in time on the order of $T^{1/2}$.
This algorithm is based on the Riemann-Siegel formula, but has several new features,
including use of the Fast Fourier Transform, of
band-limited function interpolation, and of an
algorithm similar to the multipole expansion of Greengard and Rokhlin \cite{GR1}.
It has been implemented and used to compute $1.75 \times 10^8$ zeros
near zero number $10^{20}$, for example \cite{Od4}.
It can also be adapted to check the validity of the RH
beyond the $1.5 \times 10^9$ zeros that were treated in
\cite{LRW2}.

An important stimulus for the invention and implementation of the algorithm of \cite{OS} was the desire to check conjectures that in many ways
go beyond the RH.
A proof of the RH would still leave open many questions about the distribution of primes,
such as those about gaps between consecutive primes.
Answers to many of these problems
depend on the vertical distribution of zeros of the zeta function.
There are conjectures, originating with the work of Montgomery on the
pair-correlation function \cite{Mon1}, that connect the
Hilbert-P\'{o}lya conjecture (which says that the RH is true because zeros of
$\zeta (s)$ correspond to eigenvalues of a positive operator)
together with the extensive work in physics on quantum chaos
and random matrix theories \cite{Be2,Be3,BG,BFFMPW,Meh}.
For further details on the number-theoretic aspects of this work,
see \cite{Od3}.
However, it seems safe to say that there will be additional
work in this area,
and new algorithms are likely to be invented \cite{Od4,Schon}.

The Dirichlet $L$-function $L(s, \chi )$ for a character $\chi$
modulo $q$ is defined by
\begin{equation}
L(s, \chi ) = \sum_{n=1}^\In \chi (n) n^{-s}\,\,\,\,\,\,
\mbox{for}\,\,\,\,\, \mbox{Re} (s) > 1 ~.
\label{Neq401}
\end{equation}
These functions play an important role in number theory, especially in the study of the distribution of primes in arithmetic progressions.
They have many properties in common with the zeta function,
especially an Euler product and a functional equation.
The Generalized Riemann Hypothesis says that all their
nontrivial zeros are on the critical line.
All the evidence so far supports this conjecture, although it is not anywhere near as extensive as the data for the zeta function.

The Euler-Maclaurin formula can be used to compute zeros of $L(s, \chi )$.
That was the method used in the early computations.
The drawback to this approach is that at large heights the number
of operations that
are required becomes prohibitive.

Much more extensive computations of zeros of Dirichlet
$L$-functions were carried out recently by Rumely \cite{Rum}.
He used a network of PCs to compute low zeros of many
$L(s, \chi)$ with small conductors.
The method Rumely used was also based on the Euler-Maclaurin formula, but he used also some ingredients inspired by \cite{Od4,OS} that involve precomputations
and reusing intermediate results from one $L$-function to another.
He computed accurate values of zeros of $L(s, \chi)$ up to height $10^4$
for all $ \chi$ with conductors $\le 13$, up to $2.5 \times 10^3$
for all $ \chi$ with conductors $\le 72$, and several other interesting
collections of characters.

There do exist analogs of the Riemann-Siegel formula for Dirichlet $L$-functions, derived by
Davies \cite{Dav} and Deuring \cite{Deu}.
They were used by Hejhal \cite{Hej5} to compute high zeros of certain $L$-functions.
For larger computations one could adapt the methods of \cite{Od4,OS}.

Since Dedekind zeta functions of abelian number fields are essentially products of Dirichlet $L$-functions, there is no difficulty in computing their zeros.
(Some computations of this type are reported in \cite{Hej5}.
The goal of that investigation was to determine how the distribution
of spacings of the Dedekind zeta function compared to the distribution
of spacings of individual $L$-functions.)
The situation is quite different when one considers
zeros of Dedekind zeta functions of nonabelian number fields.
There the only computation that has been carried out so far is that of
J. Lagarias and the author \cite{LO1}, and it deals only with
pure cubic fields and only with low zeros.
There are some other methods that might be used in the future,
though, such as those of \cite{BerryK,Friedman}.

If $Q(m,n) = am^2 + b mn + cn^2$ is a positive definite
quadratic form, then the Epstein zeta function $Z(s)$ of $Q$ is defined by
\begin{equation}
\label{Neq21}
Z(s) = \frac{1}{2} \mathop{{\sum}'}_{m,n} Q(m,n)^{-s} ~,~~~~
\mbox{Re} (s) > 1 ~,
\end{equation}
where $\sum'$ means the summation runs over all pairs of
integers $m$ and $n$ except for the term $m=n=0$.
The function $Z(s)$ can be
continued analytically to the entire complex plane except for $s=1$, where it has a first-order pole.
Epstein zeta functions play an important role in the study of quadratic forms and number fields.
They do satisfy functional equations similar to those of the zeta function and
Dirichlet $L$-functions, but with few exceptions they do not have Euler products and
therefore are not expected to satisfy the RH.
It is even known that most of them have many zeros away from the critical line.
Extensive computations have been done by Hejhal to investigate
how many of their zeros are on the critical line \cite{Hej5}.
There are also interesting questions about the behavior of zeros
of parametrized families of Epstein zeta functions as the parameter
passes through values for which these functions are expected to satisfy the RH.
Some initial results in this area have been obtained by Arenstorf
and Brewer \cite{ArenB}.
(For other results on tracking of zeros of parametric families
of functions that include the zeta function as a special case,
see \cite{FornK}.)

Computations have been carried out of the zeros of some number-theoretic functions even more exotic than the ones mentioned
above.
For example, $L$-functions with Gr\"{o}ssencharakteren were 
investigated in \cite{Davies0}.
Zeros of $L$-functions associated with elliptic curves were studied
by Fermigier \cite{Fermigier},
and zeros of the $L$-function with the Ramanujan $\tau$-function as
coefficients were computed by Keiper \cite{Keiper}.

Extensive work has been carried out in recent years on Selberg zeta
functions and related topics.
Some references in this area are \cite{Hej8,HejA,HejhalR}.
\section{Indirect disproofs of conjectures}
Values of zeros of $\zeta (s)$ and related functions have been used in many ways other than just to
study the RH and its generalizations.
For example, Stark \cite{Stark0} used high-precision values of the first few zeros
of $\zeta (s)$ to obtain large lower bounds for the
class number one problem.
This result helped in completing some of the proofs
of Gauss' conjecture that all imaginary quadratic fields
with class number one have discriminants with absolute value $\le 163$.
In a similar vein, the class number two problem was solved with the help of several high-precision values of low zeros of the zeta function \cite{St} and independently by computing zeros of Dirichlet $L$-functions
\cite{MW,Weinb}.

Zeros of the zeta function have also been used in disproofs of various conjectures, or in
obtaining effective bounds for least counterexamples to conjectures.
For example, Littlewood showed around 1920 that the famous
conjecture that $\pi (x) < \text{li}\, (x)$ for all
$x \ge 2$ is false for infinitely many integer values of $x$.
The first bound for the smallest counterexample was found by
Skewes, and was huge.
However, Lehman \cite{Ln2} used precise values for large numbers
of zeros of $\zeta (s)$ to bring the bound down to $10^{1166}$.
Later, te~Riele \cite{Rie} used Lehman's method together with more extensive
computations to lower this bound to $10^{371}$.
(It is known there are no counterexamples below $10^{13}$, and probably there are none below $10^{30}$.)
The disproof of the Mertens conjecture \cite{OtR} involved
computation of the first 2000 zeros of $\zeta (s)$ to 100 decimal
places.

Consider the function
\begin{equation}
\label{Neq31}
H_t (z) = \int_0^\In e^{tu^2} \Phi (u) \cos (zu) du ,~~~
t \in \RR , ~~z \in \CC ~,
\end{equation}
where
\begin{equation}
\label{Aneq32}
\Phi (u) =
\sum_{n=1}^\infty (2 \pi^2 n^4 e^{9u} - 3 \pi n^2 e^{5u} )
\exp (- \pi n^2 e^{4u} ) ~.
\end{equation}
Then
\begin{equation}
\label{Neq32}
H_0 (z) = \xi (1/2 + iz/2) /8 ~,
\end{equation}
and so the RH is equivalent to the statement that all the zeros of $H_0 (z)$ are real.
P\'{o}lya raised the question of what happens to the zeros of $H_t (z)$ for $t \neq 0$.
De~Bruijn \cite{Bru} and Newman \cite{New} showed there is a
real constant
$\Lambda \in (- \infty , 1/2 ]$ such that for $t \ge \Lambda$,
$H_t (z)$ has only real zeros, and for every $t < \Lambda$,
$H_t (z)$ has some nonreal zeros.
This constant $\Lambda$ is now called the de~Bruijn-Newman constant.
The RH is equivalent to the statement that $\Lambda \le 0$.
On the other hand, Newman \cite{New} conjectured that
$\Lambda=0$.
If true, this would be another piece of evidence that if the RH is true, it is barely true.
Because of this connection with the RH, considerable work has been put into investigating $\Lambda$ by
Csordas, Norfolk, te~Riele, Ruttan, Smith, and Varga.
The latest result \cite{COSV}, which uses the techniques of Csordas, Smith, and Varga \cite{CSV} is that
\begin{equation}
\label{Neq33}
\Lambda > - 5.895 \times 10^{-9} ~.
\end{equation}
The proof uses extensive mathematical analysis of the
behavior of zeros of $H_t (z)$ and numerical values for a pair of unusually close zeros of $\zeta (s)$.
\section{Explicit bounds for number-theoretic functions}
An important use of values of zeros or even just of the knowledge
that many initial zeros lie on the critical line is in proving precise estimates of number theoretic functions.
Rosser and Schoenfeld \cite{RosserS} have used the results
of their verification of the RH for the first
$3.5 \times 10^{6}$ zeros of $\zeta (s)$ to prove a variety of estimates that have been used widely in number theory, combinatorics, and algebra.
For example, the Prime Number Theorem says that
for every $\epsilon > 0$,
\begin{equation}
\label{AMO401}
(1- \epsilon ) \frac{x}{\log x} < \pi (x) < (1+ \epsilon )
\frac{x}{\log x} \,\,\,\,\mbox{for}\,\,\,\,
x \ge x_0 ( \epsilon ) ~,
\end{equation}
but does not immediately say what $x_0 ( \epsilon )$ is.
Even forms of the prime number theorem with explicit remainder terms typically do not give good
estimates for $x_0 (\epsilon)$.
Rosser and Schoenfeld have shown,
for example, that
\begin{equation}
\label{AMO402}
\frac{x}{\log x} \left( 1 + \frac{1}{2 \log x} \right) < \pi (x)\,\,\,\,\mbox{for}\,\,\,\, x \ge 59
\end{equation}
and
\begin{equation}
\label{eqAMO403}
\pi (x) < \frac{x}{\log x} \left( 1 + \frac{3}{2 \log x} \right) \,\,\,\,\mbox{for}\,\,\,\, x > 1~.
\end{equation}
These estimates are explicit and easy to use.
For improvements of some of the results in \cite{RosserS},
see \cite{RosserS2,Schoen}.
Based on the knowledge that the first $1.5 \times 10^9$ zeros of
$\zeta (s)$ lie on the critical line, it should be possible
to obtain substantial improvements of many of these estimates.

Ramar\'{e} and Rumely \cite{Ramare1} have used Rumely's results \cite{Rum}
to obtain estimates for primes in arithmetic progressions.
For example, they show that if $1 \le q \le 72$, $(a,q)=1$, and $x \ge \exp (30)$, then
\begin{equation}
\label{Neq41}
\displaystyle\max_{y \le x}
\left| \psi (y; q,a) - \frac{y}{\phi (q)} \right|
\le 0.012 \frac{x}{\phi (q)} ~,
\end{equation}
where
$\phi (q)$ is the Euler $\phi$-function,
\begin{equation}
\label{Neq42}
\psi (y; q,a) = \sum_{n \equiv a ( \bmod~q) \atop n \le y}
\Lambda (n) ~,
\end{equation}
and $\Lambda(n)$ is the von~Mangoldt function,
$\Lambda (p^r) = \log p$ if $p$ is a prime and $r \in {\bold Z}^+$, $\Lambda (n) =0$ otherwise.
Estimates of this type played a crucial role in Ramar\'{e}'s proof \cite{Ramare2} that every integer $n \ge 2$ is a sum of at most 7 primes.
\section{Computation of arithmetic functions}
Analytic functions, such as the Riemann zeta function $\zeta (s)$, can be used to compute exactly certain arithmetic functions such as
$\pi (x)$.
There are exact formulas expressing $\pi (x)$ as a sum over the zeros of $\zeta (s)$, but they converge slowly and so cannot be used directly
for efficient computation.
(Formulas for $\pi (x)$ and related ones can be used for primality testing, since $p$ is prime if and only if
\linebreak
$\pi (p) - \pi (p-1) > 0$, but again
there does not seem to be any way to make them efficient.)
However, there is a method that uses analytic computations of
$\zeta (s)$ (but does not use zeros of $\zeta (s)$) to compute
$\pi (x)$ exactly and efficiently \cite{LO3,LO4}.
One can write down formulas of the form
\begin{equation}\label{eq501}
\sum_{p \le x} c(p) +
\sum_{p^m \le x \atop m \ge 2} \frac{1}{m} c(p^m) =
\frac{1}{2 \pi i}
\int_{2-i \infty}^{2+ i \infty}
F(s) \log \zeta (s) ds~,
\end{equation}
where $p$ ranges over primes and
\begin{equation}\label{eq502}
c(u) = \frac{1}{2 \pi i}
\int_{2-i \infty}^{2+ i \infty} F(s) u^{-s} du ~,
\end{equation}
and $F(s)$ belongs to a certain class of functions.
It turns out (see \cite{LO4}) that one can choose $F(s)$ so that
$c(p^m) =1$ for $2 \le p^m \le x-y$,
where $y=x^{1/2 + o(1)}$,
$c(p^m) =0$ for $p^m > x$,
with individual values of $c(u)$ and of $F(s)$ easy to compute, and so that
$F(2+ it)$ is rapidly decreasing for $|t| > x^{1/2}$.
The integral in (\ref{eq501}) can then be evaluated to within $1/10$ in
$x^{1/2 + o(1)}$ steps.
The sum on the left of (\ref{eq501}) differs from $\pi (x)$
by the contribution of primes $p \in [x-y,x]$ and proper prime powers $\le x$, and those terms can be estimated in $x^{1/2 + o(1)}$ steps to
within $1/10$.
Since $\pi (x)$ is an integer, this yields a value of $\pi (x)$ in
a total of $x^{1/2 +o(1)}$ steps as $x \to \infty$.

In contrast to the analytic method of computing $\pi (x)$ that is sketched above, the best combinatorial techniques that are known require time $x^{2/3 +o(1)}$ as
\linebreak
$x \to \infty$ \cite{LMO,LO3}.
However, those methods are much easier to implement, and are the ones that have been used in the calculations of the largest values of $\pi (x)$ that are
known, namely for $x=4 \times 10^{16}$ \cite{LMO} and more recently for $x=10^{18}$ by M. Deleglise
and J. Rivat \cite{DelR}.

Both the combinatorial and analytic methods mentioned above can be
extended to the computation of other arithmetic functions \cite{LMO,LO4,Shiu}.
\subsection*{Acknowledgements.}
Richard Brent, Keith Conrad, Walter Gautschi, and Hugh Montgomery provided corrections and helpful comments on an earlier version of this paper.

\begin{thebibliography}{99}
\bibitem{ArenB}
R.~F. Arenstorf and L.~L. Brewer,
A study of the motion of zeros of the Epstein zeta function
associated to $m^2 + y^2 n^2$ as $y$ varies from 1 to
$\sqrt{6}$,
{\em Comput. Math. Appl.} {\bf 26}, no.~5, (1993), 57--69.
\bibitem{Ay}
R. Ayoub, Euler and the zeta function, {\em Amer. Math. Monthly} {\bf 81}
(1974), 1067--1086.
\bibitem{Be2}
M. V. Berry, Riemann's zeta function: A model for
quantum chaos?, pp. 1--17 in {\em Quantum Chaos and Statistical
Nuclear Physics}, T. Seligman and H. Nishioka, eds.,
Lecture Notes in Phys. {\bf 263}, Springer, Berlin, 1986.
\bibitem{Be3}
M. V. Berry, Quantum chaology, {\em Proc. Royal Soc. London A} {\bf 413}
(1987), 183--198.
\bibitem{BerryK}
M.~V. Berry and J.~P. Keating,
A new asymptotic representation for $\zeta ( \frac{1}{2} +it)$ and
quantum spectral determinants,
{\em Proc. Royal Soc. London A} {\bf 437} (1992), 151--173.
\bibitem{BG}
O. Bohigas and M.-J. Giannoni, Chaotic motion and random
matrix theories, pp. 1--99 in {\em Mathematical and Computational
Methods in Nuclear Physics}, J. S. Dehesa,
J.~M.~G. Gomez, and A. Polls, eds., Lecture Notes in Phys.
{\bf 209}, Springer, Berlin, 1984.
\bibitem{BH}
E. Bombieri and D. A. Hejhal, Sur les
z\'{e}ros des fonctions
z\^{e}ta
d'Epstein, {\em C. R. Acad. Sci. Paris S\'{e}r. I} {\bf 304}
(1987), 213--217.
%\bibitem{Br5}
%R. P. Brent, On the zeros of the Riemann zeta function in
%the critical strip, {\em Math. Comp. 33} (1979), 1361--1372.
\bibitem{BFFMPW}
T. A. Brody, J. Flores, J. P. French, P. A. Mello, A. Pandey,
and S. S. M. Wong, Random-matrix physics: spectrum and strength
fluctuations, {\em Rev. Modern Phys.} {\bf 53} (1981), 385--479.
\bibitem{Bru}
N. G. de~Bruijn, The roots of trigonometric integrals,
{\em Duke Math. J.} {\bf 17} (1950), 197--226.
\bibitem{COSV}
G. Csordas, A. M. Odlyzko, W. Smith, and R. S. Varga,
A new Lehmer pair of zeros and a new lower bound for the de~Bruijn-Newman constant $\Lambda$,
{\em Electr. Trans. Numer. Anal.} {\bf 1} (1993),
104--111.
\bibitem{CSV}
G. Csordas, W. Smith, and R.~S. Varga,
Lehmer pairs of zeros, the de~Bruijn-Newman constant $\Lambda$,
and the Riemann Hypothesis, {\em Constr. Approx.} {\bf 10} (1994), 107--129.
\bibitem{Daven}
H. Davenport,
Multiplicative Number Theory, 2nd ed.,
revised by H.~L. Montgomery, Springer, New York, 1980.
\bibitem{Davies0}
D. Davies,
The computation of the zeros of Hecke zeta functions in the Gaussian field,
{\em Proc. Royal Soc. Ser. A} {\bf 264} (1961), 496--502.
\bibitem{Dav}
D.~Davies, An approximate functional equation for
Dirichlet L-functions,
{\em Proc. Royal Soc. Ser. A} {\bf 284} (1965), 224--236.
\bibitem{DelR}
M. Deleglise and J. Rivat,
Computing $\pi (x)$:
the Meissel, Lehmer, Lagarias, Miller, Odlyzko method, to be published.
\bibitem{Deu}
M. Deuring, Asymptotische Entwicklungen der Dirichletschen
L-Reihen, {\em Math. Ann.} {\bf 168} (1967), 1--30.
\bibitem{Ed}
H. M. Edwards, {\em Riemann's Zeta Function}, Academic Press, New York, 1974.
\bibitem{Fermigier}
S. Fermigier,
Z\'{e}ros des fonctions $L$ de courbes elliptiques,
{\em Experimental Math.} {\bf 1} (1992), 167--173.
\bibitem{FornK}
B. Fornberg and K.~S. K\"{o}lbig,
Complex zeros of the Jonqui\`{e}re or polylogarithm function,
{\em Math. Comp.} {\bf 29} (1975), 582--599.
\bibitem{Friedman}
E. Friedman,
Hecke's integral formula, Sem. Th\'{e}orie des Nombres Bordeaux,
1987--99, No.~5.
%\bibitem{Gab}
%W. Gabcke, {\em Neue Herleitung und explizite Restabsch\"{a}tzung
%der Riemann-Siegel-Formel}, Ph.D. Dissertation, G\"{o}ttingen,
%1979.
%\bibitem{Gram}
%J. Gram, Sur les z\'{e}ros de la fonction
%$\zeta (s) $ de~Riemann,
%{\em Acta Math. 27} (1903), 289--304.
\bibitem{GR1}
L. Greengard and V. Rokhlin, A fast algorithm for particle simulations,
{\em J. Computational Phys.} {\bf 73} (1987), 325--348.
\bibitem{Has}
C. B. Haselgrove (in collaboration with J. C. P. Miller),
{\em Tables of the Riemann Zeta Function,} Royal Soc. Math. Tables
No. 6, Cambridge Univ. Press, 1960.
%\bibitem{Hej1}
%D. A. Hejhal, The Selberg trace formula and Riemann zeta function,
%{\em Duke Math. J. 43} (1976), 441--482.
\bibitem{Hej5}
D. A. Hejhal, Zeros of Epstein zeta functions and supercomputers,
pp. 1362--1384 
in {\em Proc. Internat. Congress Math. 1986}, Amer. Math. Soc., Providence, 1987.
\bibitem{Hej8}
D. A. Hejhal,
Eigenvalues of the Laplacian for Hecke triangle groups,
{\em Memoirs Amer. Math. Soc.} {\bf 469} (1992).
\bibitem{HejA}
D.~A. Hejhal and S. Arno,
On Fourier coefficients of Maass waveforms for $PSL(2, \ZZ )$,
{\em Math. Comp.} {\bf 61} (1993), 245--267 and S11--S16.
\bibitem{HejhalR}
D.~A. Hejhal and B.~N. Rackner,
On the topography of Maass waveforms for $PSL(2,Z)$,
{\em Experimental Math.} {\bf 1} (1992), 275--305.
\bibitem{Iv}
A. Ivi\'{c},
{\em The Riemann Zeta-function: The Theory of the Riemann Zeta-function with Applications}, Wiley, New York, 1985.
\bibitem{Keiper}
J.~B. Keiper,
On the zeros of the Ramanujan $\tau$-Dirichlet series in the critical strip, to be published.
\bibitem{LMO}
J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing 
$ \pi (x)  $ : The Meissel-Lehmer method,
{\em Math. Comp.} {\bf 44} (1985), 537--560.
\bibitem{LO1}
J. C. Lagarias and A. M. Odlyzko, On computing Artin L-functions
in the critical strip, {\em Math. Comp.} {\bf 33} (1979), 1081--1095.
%\bibitem{LO2}
%J. C. Lagarias and A. M. Odlyzko, Solving low-density subset
%sum problems, {\em J. Assoc. Comput. Mach. 32} (1985), 229--246.
\bibitem{LO3}
J. C. Lagarias and A. M. Odlyzko, New algorithms for computing 
$\pi (x)  $,
pp. 176--193 in {\em Number Theory: New York 1982},
D. V. Chudnovsky, G. V. Chudnovsky, H. Cohn, and M. B. Nathanson, eds.,
Springer-Verlag, Lecture Notes in Math. {\bf 1052}, 1984.
\bibitem{LO4}
J. C. Lagarias and A. M. Odlyzko, 
Computing 
$\pi (x)  $: An analytic method,
{\em J. Algorithms} {\bf 8} (1987), 173--191.
\bibitem{Ln2}
R. S. Lehman, On the difference $\pi (x) - \mathrm{li} \,(x) $,
{\em Acta Arith.} {\bf 11} (1966), 397--410.
%\bibitem{Ln3}
%R. S. Lehman, On the distribution of zeros of the Riemann zeta
%function, {\em Proc. London Math. Soc.} {\bf 20} (1970), 303--320.
\bibitem{Lr1}
D. H. Lehmer, Extended computation of the Riemann zeta-function,
{\em Mathematika} {\bf 3} (1956), 102--108.
\bibitem{Lr2}
D.~H. Lehmer, On the roots of the Riemann zeta-function,
{\em Acta Math.} {\bf 95} (1956), 291--298.
\bibitem{Low}
M.~E. Low,
Real zeros of the Dedekind zeta function of an imaginary quadratic field,
{\em Acta Arith.} {\bf 14} (1967/68), 117--140.
\bibitem{LuneR}
J. van de Lune and H. J. J. te Riele,
Numerical computation of special zeros of partial sums of
Riemann's zeta function,
pp.~371--387 in {\em Computational Methods in Number Theory},
Part~II, H.~W. Lenstra,~Jr., and R. Tijdeman, eds.,
Mathematisch Centrum, Amsterdam, 1982.
\bibitem{LRW2}
J. van de Lune, H. J. J. te Riele, and D. T. Winter, On the zeros
of the Riemann zeta function in the critical strip.~IV., {\em Math. Comp.} {\bf 46} (1986), 667--681.
\bibitem{McCurley}
K.~S. McCurley,
Explicit estimates for the error term in the prime number theorem
in arithmetic progressions,
{\em Math. Comp.} {\bf 42} (1984), 265--285.
\bibitem{Meh}
M. L. Mehta, {\em Random Matrices},
2nd revised and enlarged ed.,
Academic Press, Boston, 1991.
%\bibitem{Mert}
%F. Mertens, \"{U}ber eine zahlentheoretische Funktion,
%{\em Sitzungsberichte Akad. Wiss. Wien IIa 106} (1897), 761--830.
\bibitem{Mon1}
H. L. Montgomery, The pair correlation of zeros of the zeta
function, pp. 181--193 in {\em Analytic Number Theory,} H. G. Diamond, ed., 
Proc. Symp. Pure Math. {\bf 24}, Amer. Math. Soc., Providence, 1973.
\bibitem{MW}
H. L. Montgomery and P. J. Weinberger, Notes on small class
numbers, {\em Acta Arith.} {\bf 24} (1973/74), 529--542.
\bibitem{New}
C. M. Newman, Fourier transforms with only real zeros,
{\em Proc. Amer. Math. Soc.} {\bf 61} (1976), 245--251.
\bibitem{Od1}
A. M. Odlyzko, New analytic algorithms in number theory,
pp. 466--475 
in {\em Proc. Internat. Congress Math. 1986}, Amer. Math. Soc., Providence, 1987.
\bibitem{Od2}
A. M. Odlyzko, On the distribution of spacings between zeros of
the zeta function, {\em Math. Comp.} {\bf 48} (1987), 273--308.
\bibitem{Od3}
A. M. Odlyzko, Zeros of the Riemann
zeta function: Conjectures and computations, manuscript in preparation.
\bibitem{Od4}
A. M. Odlyzko, {\em The 
$ 10^{20} $-th Zero of the Riemann Zeta Function
and 175 Million of its Neighbors},
manuscript in preparation.
\bibitem{OtR}
A. M. Odlyzko and H. J. J. te Riele, Disproof of the
Mertens conjecture, {\em J. reine angew. Math.} {\bf 357} (1985), 138--160.
\bibitem{OS}
A. M. Odlyzko and A. Sch\"{o}nhage, Fast algorithms for
multiple evaluations of the Riemann zeta function, {\em Trans.
Amer. Math. Soc.} {\bf 309} (1988), 797--809.
\bibitem{Pat}
S. J. Patterson, {\em An Introduction to the Theory of the
Riemann Zeta-Function,} Cambridge Univ. Press, 1988.
\bibitem{Ramare2}
O. Ramar\'{e}, On \v{S}nirel'man's constant, to be published.
\bibitem{Ramare1}
O. Ramar\'{e} and R. Rumely, Primes in arithmetic progressions,
to be published.
\bibitem{Rie}
H. J. J. te Riele, On the sign of the difference $ \pi (x) - \mathrm{li}\,(x)$,
{\em Math. Comp.} {\bf 48} (1987), 323--328.
\bibitem{R}
B. Riemann, \"{U}ber die Anzahl der Primzahlen unter einer
gegebenen Gr\"{o}sse,
{\em Monatsberichte der Berliner Akad.}
(1858/60), 671--680.  Reprinted in {\em Gesammelte Mathematische Werke},
Teubner, Leipzig, 1892, and later by Dover Publications.
English translation by H. M. Edwards, pp. 299--305 in \cite{Ed}.
\bibitem{RosserS}
J. B. Rosser and L. Schoenfeld,
Approximate formulas for some functions of prime numbers,
{\em Illinois J. Math.} {\bf 6} (1962), 64--94.
\bibitem{RosserS2}
J. B. Rosser and L. Schoenfeld,
Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$,
{\em Math. Comp.} {\bf 29} (1975), 243--269.
\bibitem{RYS}
J. B. Rosser, J. M. Yohe, and L. Schoenfeld, Rigorous computation and
the zeros of the Riemann zeta function, pp. 70--76 in {\em Information Processing 68,
Proc. IFIP Congress, Edinburgh, 1968}, vol. 1, North-Holland, Amsterdam, 1969.
Errata in {\em Math. Comp.} {\bf 29} (1975), 243.
\bibitem{Rum}
R. Rumely, Numerical computations concerning the ERH,
{\em Math. Comp.} {\bf 61} (1993), 415--440 and S17--S23.
\bibitem{Schoen}
L. Schoenfeld,
Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$.~II,
{\em Math. Comp.} {\bf 30} (1976), 337--360.
\bibitem{Schon}
A. Sch\"{o}nhage,
Numerik analytischer Funktionen und Komplexit\"{a}t,
{\em Jahresber. Deutsch. Math.-Verein.} {\bf 92} (1990), 1--20.
\bibitem{Shiu}
P. Shiu,
Counting sums of two squares:
The Meissel-Lehmer method,
{\em Math. Comp.} {\bf 47} (1986), 351--360.
\bibitem{Sie1}
C. L. Siegel, \"{U}ber Riemanns Nachlass zur analytischen
Zahlentheorie, {\em Quellen und Studien zur Geschichte der Math. Astr. Phys.} {\bf 2}
(1932), 45--80.
Reprinted in C. L. Siegel, {\em Gesammelte Abhandlungen}, Springer, Berlin,
1966, Vol. 1, pp. 275--310.
\bibitem{Sie2}
C. L. Siegel, Contributions to the theory of the Dirichlet $L$-series
and the Epstein zeta functions, {\em Ann. Math.} {\bf 44} (1943), 143--172.
Reprinted in C. L. Siegel, {\em Gesammelte Abhandlungen}, Springer,
Berlin, 1966, Vol. 2, pp. 360--389.
%\bibitem{Sk}
%S. Skewes, On the difference $ \pi (x) - li(x) $. II,
%{\em Proc. London Math. Soc. (3) 5} (1955), 48--70.
\bibitem{Spina1}
R. Spira, 
Zeros of approximate functional approximations,
{\em Math. Comp.} {\bf 21} (1967), 41--48.
\bibitem{Spina2}
R. Spira,
Zeros of Hurwitz zeta functions,
{\em Math. Comp.} {\bf 30} (1976), 863--866.
\bibitem{Stark0}
H. M. Stark,
On complex quadratic fields with class number equal to one,
{\em Trans. Amer. Math. Soc.} {\bf 122} (1968), 112--119.
\bibitem{St}
H. M. Stark, On complex quadratic fields with class number two,
{\em Math. Comp.} {\bf 29} (1975), 289--302.
%\bibitem{Tit1}
%E. C. Titchmarsh, The zeros of the Riemann zeta-function,
%{\em Proc. Royal Soc. London 151} (1935), 234--255 and
%{\em 157} (1936), 261--263.
\bibitem{Tit2}
E. C. Titchmarsh, {\em The Theory of the Riemann Zeta-function},
2nd ed. (revised by D. R. Heath-Brown),
Oxford Univ. Press, 1986.
%\bibitem{Tu1}
%A. M. Turing, A method for the calculation of the zeta-function,
%{\em Proc. London Math. Soc. ser. 2}, {\bf 48} (1943), 180--197.
%\bibitem{Tu2}
%A. M. Turing, Some calculations of the Riemann zeta-function,
%{\em Proc. London Math. Soc. ser. 3, 3} (1953), 99--117.
\bibitem{Weinb}
P. J. Weinberger,
On small zeros of Dirichlet $L$-functions,
{\em Math. Comp.} {\bf 29} (1975), 319--328.
\end{thebibliography}
\end{document}