\documentclass[11pt]{article} %\input amssym.def %\input amssym.tex \usepackage{epsfig,psfig,amsfonts,amssymb} \setlength{\textwidth}{6.2in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{.2in} \setlength{\topmargin}{-0.25in} \setlength{\headheight}{0in} %%%GREEK LETTERS \newcommand{\La}{\Lambda} \newcommand{\Ga}{\Gamma} \newcommand{\Dt}{\Delta} \newcommand{\bDt}{\mbox{\boldmath $\Delta$}} \newcommand{\la}{\lambda} \newcommand{\af}{\alpha} \newcommand{\be}{\beta} \newcommand{\ep}{\epsilon} \newcommand{\vp}{\varphi} \newcommand{\vt}{\vartheta} \newcommand{\om}{\omega} \newcommand{\Om}{\Omega} \newcommand{\Th}{\Theta} \newcommand{\tht}{\theta} \newcommand{\Sg}{\Sigma} \newcommand{\In}{\infty} \newcommand{\dr}{\Rightarrow} \newcommand{\dt}{\delta} \newcommand{\ga}{\gamma} \newcommand{\RR}{{\mathbb R}} \newcommand{\CC}{{\mathbb C}} \newcommand{\sig}{\sigma} \newcommand{\zt}{\zeta} \newcommand{\et}{\eta} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \newcommand{\lc}{\lceil} \newcommand{\rc}{\rceil} \newcommand{\lt}{\left(} \newcommand{\rt}{\right)} \newcommand{\dd}{\ldots} \newcommand{\ZZ}{{\mathbb Z}} \newcommand{\df}{\displaystyle\frac} \newcommand{\dis}{\displaystyle} \newcommand{\ds}{\displaystyle\sum} \newcommand{\bzero}{{\mathbf 0}} \newtheorem{coro}{Corollary}[section] \newtheorem{conj}{Conjecture}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{theorem}{Theorem}[section] \newtheorem{prop}{Proposition}[section] \newtheorem{remark}{\bf Remark}[section] \newtheorem{exam}{Example}[section] \newtheorem{defi}{Definition}[section] \newcommand{\eqn}[1]{(\ref{#1})} \newcommand{\hsp}{\hspace*{\parindent}} \newcommand{\vsp}{\vspace{.1in}} \newcommand{\pf}{\noindent{\bf Proof.~}} \newcommand{\eeq}{\end{equation}} \newcommand{\beql}[1]{\begin{equation}\label{#1}} \def\binom#1#2{{#1}\choose{#2}} \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} \catcode`\@=11 \renewcommand{\section}{ \setcounter{equation}{0} \@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\large\bf} } \catcode`@=12 \newcommand{\Bnu}{\mbox{\boldmath $\nu$}} \newcommand{\Bmu}{\mbox{\boldmath $\mu$}} %%%Filename is periodsec.sty%%% \makeatletter % put a period after section or subsection number in header \def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}\else \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname {#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}}\fi \@xsect{#5}} % put a period after theorem and theorem-like numbers \def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]} \makeatother \makeatletter \def\eqalignno#1{\displ@y \tabskip\@centering \halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip &$\@lign\displaystyle{{}##}$\hfil\tabskip\@centering &\llap{$\@lign##$}\tabskip\z@skip\crcr #1\crcr}} \makeatother \thispagestyle{empty} \begin{document} \begin{center} {\Large {\bf An improved bound for the de Bruijn-Newman constant}} \\ \vspace{\baselineskip} {\em A. M. Odlyzko} \\ \vspace{0.5\baselineskip} AT\&T Labs - Research \\ Florham Park, New Jersey 07932 \\ amo@research.att.com \\ \vspace*{1.5\baselineskip} {\em Dedicated to Richard Varga} \\ \vspace{\baselineskip} \today \\ \vspace{1.5\baselineskip} {\bf ABSTRACT} \vspace{.5\baselineskip} \end{center} The Riemann Hypothesis is equivalent to the conjecture that the de Bruijn-Newman constant $\Lambda$ satisfies $\Lambda \leq 0$. However, so far all the bounds that have been proved for $\Lambda$ go in the other direction, and provide support for the conjecture of Charles Newman that $\Lambda \geq 0$. This paper shows how to improve previous lower bounds and prove that \[ -2.7 \cdot 10^{-9} < \Lambda. \] This can be done using a pair of zeros of the Riemann zeta function near zero number $10^{20}$ that are unusually close together. The new bound provides yet more evidence that the Riemann Hypothesis, if true, is just barely true. \clearpage \thispagestyle{empty} \setcounter{page}{1} \begin{center} {\Large {\bf An improved bound for the de Bruijn-Newman constant}} \\ \vspace{\baselineskip} {\em A. M. Odlyzko} \\ \vspace{0.5\baselineskip} AT\&T Labs - Research \\ amo@research.att.com \\ \vspace*{1.5\baselineskip} {\em Dedicated to Richard Varga} \\ \vspace{1.5\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} \section{Introduction} \hsp The Riemann Hypothesis is currently the most famous unsolved problem in mathematics. Since more general results have often been easier to prove than the special cases that were originally sought, many attempts have been made to embed the Riemann zeta function into a larger family, and prove a generalized Riemann Hypothesis for the entire family. One of the more interesting approaches of this type is due to P\'olya, and is based on considering a one-parameter family of trigonometric integrals. The Riemann Hypothesis is trivially equivalent to all zeros of the Riemann function $\Xi$ being real \cite{Titchmarsh}. This function can be written (see p. 255 of \cite{Titchmarsh}) as \beql{AMO12} \Xi \left(\frac{x}{2}\right) /8 = \dis{\int_{0}^{\infty}} ~ \Phi (u) \cos (xu) du ~~~~~ (x \in {\CC}), \eeq where \beql{AMO13} \Phi (u) := \dis{\sum_{n=1}^{\infty}} ~ \left(2\pi^{2} n^{4} e^{9u} - 3\pi n^{2} e^{5u}\right) \exp \left( -\pi n^{2} e^{4u}\right) ~~~~~ (0 \leq u < \infty). \eeq P\'olya considered the more general trigonometric integral \beql{AMO14} H_{t} (x) := \dis{\int_{0}^{\infty}} ~ e^{tu^{2}} \Phi(u) \cos (xu) du ~~~~~ (t \in {\RR}; x \in {\CC}). \eeq With this definition, $H_{0}$ and the $\Xi$-function are related through \beql{AMO15} H_{0} (x) = \Xi \left(\frac{x}{2}\right)/8, \eeq so that the Riemann Hypothesis is also equivalent to the statement that all zeros of $H_{0}$ are real. De Bruijn \cite{deBruijn} showed that \\ \begin{tabular}{rp{5in}} ({\em i}) & $H_{t}$ has only real zeros for $t \geq 1/2$; \\ & \\ ({\em ii}) & if $H_{t}$ has only real zeros for some real $t$, then $H_{t'}$ has only real zeros \newline for any $t'\geq t$. \\ & \\ \end{tabular} Charles Newman \cite{Newman} proved that there exists a real $t$ such that $H_{t}$ has at least one zero that is not real. (Therefore, by the symmetry properties of $H_{t}$, it must have at least 4 zeros that are not real.) Combined with de Bruijn's result, this proves that there is a real constant $\Lambda$, which satisfies $-\infty < \Lambda \leq 1/2$, such that \beql{AMO16} H_{t} {\rm \ has\ only\ real\ zeros\ if\ and\ only\ if\ } t \geq \Lambda. \eeq The constant $\Lambda$ is referred to as the {\bf de Bruijn-Newman constant}. The Riemann Hypothesis is equivalent to the conjecture that $\Lambda \leq 0$. Unfortunately no upper bound for $\Lambda$ better than de Bruijn's original $\Lambda \leq 1/2$ has been proved. On the other hand, there has been a series of lower bounds for $\Lambda$. Csordas, Norfolk, and Varga \cite{CsordasNV} showed that \beql{AMO165} -50 < \Lambda, \eeq te~Riele \cite{teRiele} improved this to \beql{AMO17} -5 < \Lambda, \eeq Norfolk, Ruttan, and Varga proved \beql{AMO175} -0.385 < \Lambda, \eeq and this was improved further by Csordas, Ruttan, and Varga \cite{CsordasRV} to \beql{AMO18} -0.0991 < \Lambda. \eeq That result was followed by the Csordas, Smith, and Varga \cite{CsordasSV} bound \beql{AMO19} -4.379 \cdot 10^{-6} < \Lambda, \eeq which was then improved by Csordas, Odlyzko, Smith, and Varga \cite{CsordasOSV} to \beql{AMO20} -5.895 \cdot 10^{-9} < \Lambda. \eeq The lower bounds support the conjecture of Newman \cite{Newman} that $\Lambda \geq 0$. This conjecture says that if the Riemann Hypothesis is true, it is barely true, in that even small perturbations to the zeta function lead to counterexamples. This paper shows how to obtain an improved lower bound, \beql{AMO21} -2.7 \cdot 10^{-9} < \Lambda. \eeq This result by itself serves to provide additional evidence in favor of the Newman conjecture that $\Lambda \geq 0$. Further evidence is provided by the methodology used in the proof. All the published lower bounds for $\Lambda $ were obtained using extensive numerical computations. Those of \cite{CsordasSV, CsordasOSV} relied on finding extreme examples of what are called Lehmer pairs, namely two zeros of the Riemann zeta function very close to each other on the critical line. The best previous bound, that of \cite{CsordasOSV}, used an unusually extreme Lehmer pair near zero number $10^{9}$ of the zeta function. That example was found by van de Lune, te~Riele, and Winter during their verification of the Riemann Hypothesis for the first $1.5 \cdot 10^{9} $ zeros of the zeta function. The bound \eqn{AMO21} is obtained using a pair of zeros near zero number $10^{20}$ found during the computations reported in \cite{Odlyzko3}. It might seem disappointing that huge computations in the vicinity of zero number $10^{20}$ produced an improvement only by a factor of 2 over the results obtained with zeros at much lower heights. However, this was not unexpected. As is explained in the last section of this paper, the method of \cite{CsordasSV} for producing lower bounds for $\Lambda $ by finding extreme Lehmer pairs benefits much more from examining many zeros than from examining high zeros. Further, the Lehmer pair of van de Lune, te~Riele, and Winter was an unusually extreme one. Thus the surprise is not that the new bound \eqn{AMO21} is weak, but that the bound \eqn{AMO20} is strong. In any large numerical computation, especially one dealing with floating point numbers, there is a serious question about the validity of the final results. In the calculations of \cite{Odlyzko2,Odlyzko3}, the basic method is completely rigorous. However, in the interests of computing large sets of high zeros, assurance of accuracy was abandoned. Reported results are correct only if roundoff errors cancel about as much as if they were independent. The computational method used there has many checks built on, checks not only on whether roundoff errors cancel to the expected extent, but also on correctness of the programs, of the operating system, and of the hardware. (There is extensive discussion of this in \cite{Odlyzko2,Odlyzko3}.) Still, sometimes it is desirable to produce more rigorous results by controlling roundoff errors more precisely. One way to do this is to modify the codes of \cite{Odlyzko2,Odlyzko3} to operate with high enough precision to guarantee that the output is correct. One purpose of this paper is to show that it is possible to obtain such rigorous results with much less computation and with simpler codes than those of \cite{Odlyzko2,Odlyzko3}, at least for small sets of zeros. Thus it is possible to use the large-scale computations with the method of \cite{Odlyzko2,Odlyzko3} as a heuristic device, and then prove rigorous results about a few interesting phenomena that are observed. The computations reported in this paper do not obtain full control of roundoff errors, and thus are still not completely rigorous. That is why the claims in the Abstract and earlier in this section are stated so indirectly (about showing how to improve previous lower bounds, and not about improving previous lower bounds). However, there are again special checks built into the computational procedures to ensure that final results are convincing. To obtain complete control over roundoff errors would require somewhat more effort, both in programming and in processor time. \section{Lehmer pairs and bounds for the de Bruijn-Newman constant} \hsp This section outlines the basic method. It shows how an extreme Lehmer pair of zeros leads to the bound \eqn{AMO21} for the de Bruijn-Newman constant $ \Lambda $. We will assume the Riemann Hypothesis throughout the rest of this paper. If it were false, then we would have $ \Lambda > 0$, so \eqn{AMO21} would be trivially true. The theoretical method is exactly the same as that of \cite{CsordasSV, CsordasOSV}, and we will follow the notation of those papers with only some slight simplifications. Since we are assuming the Riemann Hypothesis, the zeros of $H_{0}$ are all real, and for every zero $x$, $-x$ is also a zero. We number the positive zeros (there is no zero at 0) of $H_{0}$ in increasing order, \beql{AMO31} 0 < x_1 \leq x_2 \leq x_3 \leq \cdots, \eeq where each zero appears with the proper multiplicity. (It is conjectured that there are no multiple zeros, and none have been found, but there is no proof there are none. A multiple zero would provide an immediate proof of Newman's conjecture $ \Lambda \ge 0$, see \cite{CsordasSV}.) We also let \beql{AMO32} x_{-j} = - x_{j} ~~~~~ (j = 1, 2, \cdots). \eeq We note that the zeros of the Riemann zeta function in the upper half plane are precisely of the form $ 1/2 + i \cdot x_{j} /2 $ for $j = 1, 2, \cdots.$ Following \cite{CsordasSV}, we next define a Lehmer pair of zeros. \begin{defi}\label{de21} {\rm With $k$ a positive integer, let $x_{k}$ and $x_{k+1}$ be two consecutive simple positive zeros of $H_{0}$, and set \beql{AMO33} \Delta_{k} := x_{k+1} - x_{k}. \eeq Then, $( x_{k}, x_{k+1} )$ is a {\em Lehmer pair of zeros} of $H_{0}$ if \beql{AMO34} \Delta_{k}^{2} \cdot g_{k} < 4/5, \eeq where \beql{AMO35} g_{k} = \dis{\sum_{j\neq k, k+1}}\!\!\! ' ~ \left\{ \frac{1}{(x_{k}-x_{j})^{2}} + \frac{1}{(x_{k+1}-x_{j})^{2}}\right\} ; \eeq here (and in what follows), the prime in the above summation means that $j \neq 0$, so that the above summation extends over all positive and negative integers with $j \neq 0, k, k+1$. } \end{defi} With the above definition, we have the following result from \cite{CsordasSV}, basic to our bound, as well as the bounds of \cite{CsordasSV, CsordasOSV}: \begin{theorem}\label{th21} Let $(x_{k}, x_{k+1})$ be a Lehmer pair of zeros of $H_{0}$. Set \beql{AMO36} \lambda_{k} := \frac{(1-\frac{5}{4} \Delta_{k}^{2} \cdot g_{k})^{4/5}-1}{8g_{k}}, \eeq so that $-1/[8g_{k}] < \lambda_{k} < 0$. Then, the de Bruijn-Newman constant $\Lambda$ satisfies \beql{AMO37} \lambda_{k} \leq \Lambda. \eeq \end{theorem} If we expand $ \lambda_{k} $ in a Taylor series, we find that \beql{AMO38} \lambda_{k} = - ~ \frac{\Delta_{k}^{2}}{8} - \frac{\Delta_{k}^{4} g_{k}}{64} - \frac{\Delta_{k}^{6} g_{k}^{2}}{128} - \frac{11 \Delta_{k}^{8} g_{k}^{3}}{2048} - \cdots ~ , \eeq Thus if $g_{k}$ is not too large, $\lambda_{k}$ is close to $ - {\Delta_{k}^{2}}/8$. Therefore to obtain a good lower bound for $ \Lambda $ we should look for $k$ with $\Delta_{k}$ as small as possible, and then verify that for that $k$, $g_{k}$ is not large enough to cause any problems. \section{Specific Lehmer pairs and the bounds they yield} \hsp The bound \eqn{AMO20} of \cite{CsordasOSV} was obtained by applying Theorem 2.1 with $k = 1,048,449,114$, where $x_{k} = 7.777177... \cdot 10^{8}$. Van de Lune, te~Riele, and Winter noted in their work \cite{vandeLunetRW} that $x_{k}$ and $x_{k+1}$ were unusually close. The result of \cite{CsordasOSV} was obtained by carefully computing precise values for $x_{k}$ and $x_{k+1}$ and a few thousand neighboring zeros. It turned out that \beql{AMO51} \Delta_{k} = 2.171392\ldots~ \cdot 10^{-4}, \eeq and $g_{k} < 24,058$, which yields \eqn{AMO20}. (The bound of Theorem 2.1 is monotone decreasing in $g_{k}$, so only an upper bound for $g_{k}$ is necessary.) The new bound \eqn{AMO21} is obtained by taking $k = K$, where \beql{AMO52} K = 10^{20} + 718,107,321. \eeq This appeared to be the best choice from around $5 \cdot 10^{9}$ high zeros of the Riemann zeta function that had been computed by March 1999 \cite{Odlyzko3}. (The title of \cite{Odlyzko3} refers to additional zeros that were to be computed in the future.) The values of $x_{j}/2$ (that is, the ordinates of the corresponding zeros of the zeta function) for several values of $j$ with $j - K$ small are shown in Table 1. We find that \beql{AMO53} \Delta_{K} \leq 0.000145. \eeq We next obtain an upper bound for $g_{K}$. \begin{defi}\label{de31} {\rm For $y \ge 0$, let \beql{N34} N^\ast (y) = | \{ j: y \le x_j < y + 2 \} | ~. \eeq } \end{defi} Lemma 2.1 of \cite{CsordasOSV} (derived from classical estimates for the zeta function) then yields the following result. \begin{lemma}\label{le31} $N^\ast (y)$ satisfies \beql{N35} N^\ast (y) \le \log y \quad\mbox{for}\quad y \ge 6 \cdot 10^8 ~. \eeq \end{lemma} %\noindent Next, for $n \ge 0$, define \beql{N36} S_n = \{ j : x_{K+1} + 2n \le x_j < x_{K+1} + 2n + 2 \} ~, \eeq and \beql{N37} T_n = \{ j : |j| > 1048449114, x_K -2n-2 \le x_j < x_K - 2n \} ~. \eeq (The choice of the bound 1048449114 in the definition above is arbitrary, and is made just because the value of $x_{k}$ for $k = 1048449114$ has been quoted in the first paragraph of this section.) Then for $j \in S_n$, $n \ge 1$, \beql{N38} \frac{1}{(x_K - x_j )^2} + \frac{1}{(x_{K+1} - x_j)^2} \le \frac{2}{(x_{K+1} - x_j )^2} \le \frac{1}{2n^2} ~, \eeq while for $j \in S_0$, \beql{N39} \frac{1}{(x_K - x_j)^2} + \frac{1}{(x_{K+1} - x_j )^2} \le \frac{2}{(x_{K+1} - x_{K+2} )^2} ~. \eeq Therefore by Lemma \ref{le31}, \begin{eqnarray}\label{N310} && \sum_{n=0}^\infty \sum_{j \in S_n} \left\{ \frac{1}{(x_K - x_j)^2} + \frac{1}{(x_{K+1} - x_j)^2} \right\} \nonumber \\ & \le & \frac{2 \log x_{K+1}}{(x_{K+1} - x_{K+2} )^2} + \sum_{n=1}^\infty \frac{\log (x_{K+1} + 2n)}{2n^2} \nonumber \\ & \le & \frac{2 \log x_{K+1}}{(x_{K+1} - x_{K+2} )^2} + \sum_{n=1}^\infty \frac{\log x_{K+1}}{2n^2} + \sum_{n=1}^\infty \frac{\log (2n)}{2n^2} \nonumber \\ & \le & \frac{90}{(x_{K+1} - x_{K+2} )^2} + 40 ~. \end{eqnarray} A similar argument shows that \beql{N311} \sum_{n=1}^\infty \sum_{j \in T_n} \left\{ \frac{1}{(x_K - x_j )^2} + \frac{1}{(x_{K+1} - x_j )^2} \right\} \le \frac{90}{(x_K - x_{K-1} )^2} + 40 \,. \eeq Finally, \beql{N312} \sum_{|j| \le 1048449114 \atop j \neq 0} \left\{ \frac{1}{(x_K - x_j)^2} + \frac{1}{(x_{K+1} - x_j)^2} \right\} \le \frac{2 \cdot 2 \cdot 1048449114}{(1.5 \cdot 10^{19})^2} \le 2\cdot 10^{-27} \,. \eeq Combining all these estimates we find that \beql{N313} g_K \le \frac{90}{(x_K - x_{K-1} )^2} + \frac{90}{(x_{K+1} - x_{K+2} )^2} + 81 \,. \eeq So far we have only used an approximate value for $x_K$ to obtain this bound, whereas we needed precise values of $x_K$ and $x_{K+1}$ to estimate $\Delta_K$. If we now use the values for $x_{K-1}$ and $x_{K+2}$ from Table 1, we find \beql{N314} g_K \le 1830 \,. \eeq Together with \eqn{AMO52}, this shows that $$\lambda_K \ge - 2.63 \cdot 10^{-9} \,,$$ which proves the desired bound \eqn{AMO21} for $\Lambda$. Note that all we needed were very precise values of $x_K$ and $x_{K+1}$, and moderately precise values of $x_{K-1}$ and $x_{K+2}$. \section{Computations and their validity} \hsp The computations of \cite{Odlyzko2,Odlyzko3} are based on the algorithm of \cite{OdlyzkoS}. The only substantial modification is that band-limited function interpolation is used in place of Taylor expansions in the final computation of individual values of the zeta function. This algorithm enables computation of large sets of zeros at large heights. However, in the implementations of \cite{Odlyzko2,Odlyzko3}, the results are correct only if the floating point roundoff errors cancel almost to the extent they would if they were independent. There are two steps in the algorithm, a rational function evaluation step (similar to, but independent of, the fast multi-pole method of Greengard and Rokhlin), and a giant FFT step, which make it hard to control roundoff. In principle it can be done, but it would require much greater use of multiprecision arithmetic, and would slow down the computation substantially. There are numerous checks built into the algorithm (based on comparison of separate runs that compute totally unrelated numbers, and whose results coincide only because of mathematical analysis). These checks serve to verify the correctness not only of the assumption about random cancellation of roundoff errors, but also of the code, the operating system, and the hardware. Still, the results are not completely rigorous. However, as we next show, more rigor can be obtained relatively easily if one is interested in smaller sets of zeros than the billions computed in \cite{Odlyzko2,Odlyzko3}. The previous section showed that to obtain the new bound for $\Lambda$, it is only necessary to compute $x_K$ and $x_{K+1}$ to within about $10^{-6}$, and $x_{K-1}$ and $x_{K+2}$ to within about $10^{-2}$. That appears to require a total of 8 function evaluations of $H_{0}(t)$, one on either side of each of the four zeros. (The points of evaluation can be taken from the less rigorous large scale computations of \cite{Odlyzko3}.) Actually, somewhat more is required. We need to know that the values of $x_{K-1}, x_K, x_{K+1},$ and $x_{K+2}$ are indeed the values of 4 consecutive zeros of $H_{0}(t)$. We do not need to know the value of $K$, but the correctness of the estimates for $g_K$ in the previous section depends crucially on the gaps between $x_{K-1}$ and $x_K$ and between $x_{K+1}$ and $x_{K+2}$ not being much smaller than Table 1 shows they are. To ensure that there are no undesired zeros hiding close to $x_K$, we use the nice technique of Turing (see \cite{Edwards,Odlyzko1} for details). It allows one to conclude that all zeros of the zeta function in an interval on the critical line has been found based just on computations on the critical line. In our application, it requires finding about 25 zeros below $x_K$ and about that many above $x_{K+1}$. The algorithm that was used is a simplified version of that in \cite{Odlyzko2,Odlyzko3,OdlyzkoS}. We do not go into the details, and only point out the key differences. The basic step is to compute values of the trigonometric sum \beql{N450} f(t) = \sum_{n=500}^N n^{-1/2} e^{i t \log n} \eeq on a grid of evenly spaced points, where $N= 1555488184$ is the number of terms in the Riemann-Siegel formula. Afterwards, band-limited function interpolation is used to compute individual values, as in \cite{Odlyzko2,Odlyzko3}. (The interpolation process is easy, and does not introduce large roundoff errors.) Two separate grids were used for the computations (in addition to the one in \cite{Odlyzko3} that first found the zeros). They were both of the form \beql{N451} t = T - M \delta, ~T - (M-1) \delta, ~\ldots, ~T + (M-1) \delta, \eeq where $N= 1555488184$. The values of $T$, $M$ and $\delta$ used in the two runs were \begin{eqnarray*} T & = & 1.5202440116027338057 \cdot 10^{19} ~, \\ M & = & 3000~, \\ \delta & = & 0.288061 ~, \end{eqnarray*} and \begin{eqnarray*} T & = & 1.5202440116027338092 \cdot 10^{19} ~, \\ M & = & 500~, \\ \delta & = & 0.07 ~, \end{eqnarray*} respectively. They allowed the computation of over 10,000 and over 300 zeros $x_j$ near $x_K$, respectively. Computations of $f(t)$ at the grid points \eqn{N451} were partitioned, in order to lessen roundoff errors, into computations on smaller grids of the form \beql{N4511} t = U, ~U + \delta, U + 2 \cdot \delta, ~\ldots, ~U + 99 \cdot \delta. \eeq The values of $f(t)$ at these grid points were computed by considering blocks of values of $n$, say $H_1 \le n < H_2$. For any such block, $U \cdot \log (H_1 )$ was computed using the Bailey multiple precision package and reduced modulo $2 \pi$. This value was then used to compute the values of $U \cdot \log (H_1 +1) , \ldots$, $U \cdot \log (H_2 -1)$, all reduced modulo $2 \pi$, using Taylor expansions of the logarithm function. This enabled the computation of double precision values of $$n^{-1/2} e^{i U \log n}, \quad H_1 \le n < H_2 ~.$$ These values were then multiplied repeatedly (in double precision arithmetic) by $\exp (i \delta \log n )$ to obtain the contribution of $n$ to $f(U)$, $f(U + \delta), \ldots$. This computational approach makes the roundoff problem much less severe than it is in \cite{Odlyzko2,Odlyzko3}, but at the cost of reducing the scale of the computation. It also does not provide complete rigor, in that the addition of 1.5 billion terms in the sum \eqn{N450}, even though carried out in 52-bit precision, could potentially lead to errors that would destroy the accuracy of the values for zeros of the zeta function. The standard 52-bit precision of double precision floating point on the computers that were used is not quite enough, at least not with the simple programs that were used. With more care devoted to programming, one could protect against possible mistakes. However, as is discussed extensively in \cite{Odlyzko2,Odlyzko3}, that would still leave the possibilities of problems with other software or the hardware. The basic argument for correctness of the results of \cite{Odlyzko2,Odlyzko3} is that results of overlapping computations agree within the expected bounds, even though the intermediate steps in the computations are totally different. That is also how we can argue for the correctness of the values of zeros calculated for this paper. There were 350 zeros $x_j$ that were computed twice, once from each of the two grids \eqn{N451}. The maximal difference in the values was $3.6 \cdot 10^{-8}$. All the values for the zeros in Table 1 agreed to all the digits shown there. On the other hand, when the values computed in these two runs are compared to those from \cite{Odlyzko3}, all differences were below $8 \cdot 10^{-8}$, except for the values of $x_K$ and $x_{K+1}$. The fractional parts of the values of $x_K/2$ and $x_{K+1}/2$ computed in \cite{Odlyzko3} were 0.8183171... and 0.8183847... This serves to show the greater effect of roundoff in that large computation. It also demonstrates that inaccuracies in values of zeros tend to be much larger when the zeros are close together. All the computations were performed on SGI computers with R10000 200 MHz chips. Total run time, for a single processor, was a few months, and could easily have been decreased, both by more careful programming, and by computing fewer zeros. (Note that only about 50 zeros were needed, whereas one of the computations produced values for over 10,000 zeros.) \section{Discussion and Conclusions} \hsp The computations of \cite{vandeLunetRW} were designed only to establish the truth of the Riemann Hypothesis, not to compute precise values of zeros. Thus there is no guarantee that there is no other value of $k < 1.5 \cdot 10^{9}$ that might yield a smaller $\Delta_{k}$ than the one of \eqn{AMO51}. However, that is unlikely, since that $\Delta_{k}$ is already far better than one could normally hope for, as we will explain. The calculations of \cite{Odlyzko1,Odlyzko2,Odlyzko3} all computed precise values for zeros of the zeta function. They were designed from the beginning not just to verify the Riemann Hypothesis numerically for some zeros, but to collect detailed statistics of the zeros. The purpose was to provide evidence about some conjectures that go beyond the Riemann Hypothesis, and relate the distribution of zeros of the zeta function to that of eigenvalues of certain classes of random matrices. These conjectures suggest, among other things, that for $y$ small \beql{N51} {\rm Prob} (\Delta_k \le y) \approx \frac{y^3 (\log x_k )^3}{576 \pi} ~. \eeq The computations of \cite{Odlyzko1,Odlyzko2,Odlyzko3} found remarkably good agreement between these speculative conjectures and the data for the zeta function. In particular, if we continue to compute more zeros of the zeta function, and the agreement continues to hold, we should find $k$ with $\Delta_k$ arbitrarily small. Further, a small $\Delta_k$ almost guarantees a small value for $\lambda_{k}$, since zeros of the zeta function repel each other, and it is very rare to find three zeros close to each other. Searching at large heights does increase the chances of finding a small $\Delta_k$ (because of the $(\log x_k )^3$ factor in \eqn{N51}). However, it is more important to check many values than it is to consider high zeros. The Lehmer pair $(x_K, x_{K+1} )$ that gave the bound \eqn{AMO21} is the best one that was found among roughly 5 billion zeros near zeros number $10^{20}$, $10^{21}$, and $10^{22}$ \cite{Odlyzko3}. However, it is only about as extreme as \eqn{N51} would lead one to expect among that many zeros, and so serves to provide more evidence for the conjecture that zeros of the Riemann zeta function behave like eigenvalues of random matrices. On the other hand, the Lehmer pair found by van~de~Lune et al. that led to the bound \eqn{AMO20} is truly exceptional, since by \eqn{N51}, the probability of finding it among the first 1.5 billion zeros of the zeta function is around 7\%. How far can we expect to improve the bounds for the de Bruijn-Newman constant by methods of this and preceding papers? One can certainly hope for small additional improvements on the order of the gain from the bound of \cite{CsordasOSV} to that of this paper. Something like that could even result from the completion of the computations of \cite{Odlyzko3}. However, even with more time on faster computers, we cannot expect dramatic improvements. Suppose, for example, that we wished to prove $- 10^{-20} < \Lambda$. That would probably require finding a $k$ with $\Delta_k < 3 \cdot 10^{-10}$. However, the conjecture \eqn{N51} suggests that to do this we would need to examine on the order of $10^{30}$ zeros. The total number of simple arithmetic operations that have been performed by all digital computers in history is only on the order of $10^{23}$ (close to Avogadro's number). Even with improvements in hardware, we cannot hope to compute $10^{30}$ zeros of the zeta function using existing methods in the next couple of decades. Thus research on better algorithms for bounding the de Bruijn-Newman constant is a wiser course than continuing with current approaches. \clearpage \begin{thebibliography}{vandeLunetRW} {\small \bibitem[deBruijn]{deBruijn} N. G. de Bruijn, The roots of trigonometric integrals, {\em Duke J. Math. 17} (1950), 197--226. \bibitem[CsordasNV]{CsordasNV} G. Csordas, T. S. Norfolk, and R. S. Varga, A lower bound for the de Bruijn-Newman constant $\Lambda$, {\em Numer. Math. 52} (1988), 483--497. \bibitem[CsordasOSV]{CsordasOSV} 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 Electron. Trans. Numer. Anal. 1} (1993), 104--111. Available at $\langle$http://etna.mcs.kent.edu$\rangle$ and at $\langle$http://www.research.att.com/$\sim$amo$\rangle$. \bibitem[CsordasRV]{CsordasRV} G. Csordas, A. Ruttan, and R. S. Varga, The Laguerre inequalities with applications to a problem associated with the Riemann hypothesis, {\em Numer. Algorithms 1} (1991), 305--329. \bibitem[CsordasSV]{CsordasSV} 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. 10} (1994), 107--129. \bibitem[Edwards]{Edwards} H. M. Edwards, {\em Riemann's Zeta Function}, Academic Press, 1974. \bibitem[Newman]{Newman} C. M. Newman, Fourier transforms with only real zeros, {\em Proc. Amer. Math. Soc. 61} (1976), 245--251. \bibitem[NorfolkRV]{NorfolkRV} T. S. Norfolk, A. Ruttan, and R. S. Varga, A lower bound for the de Bruijn-Newman constant $ \Lambda$. II, pp. 403--418 in {\em Progress in Approximation Theory}, A. A. Gonchar and E. B. Saff, eds., Springer-Verlag, 1992. \bibitem[Odlyzko1]{Odlyzko1} A. M. Odlyzko, On the distribution of spacings between zeros of the zeta function, {\em Math. Comp. 48} (1987), 273--308. Available at $\langle$http://www.research.att.com/$\sim$amo$\rangle$. \bibitem[Odlyzko2]{Odlyzko2} A. M. Odlyzko, The $10^{20}$-th zero of the Riemann zeta function and 70 million of its neighbors, unpublished manuscript, 1989. Available at $\langle$http://www.research.att.com/$\sim$amo$\rangle$. \bibitem[Odlyzko3]{Odlyzko3} A. M. Odlyzko, {\em The Riemann Zeta Function: The $10^{22}$-nd Zero and Ten Billion of its Neighbors}, manuscript in preparation. \bibitem[OdlyzkoS]{OdlyzkoS} A. M. Odlyzko and A. Sch\"onhage, Fast algorithms for multiple evaluations of the Riemann zeta function, {\em Trans. Am. Math. Soc. 309} (1988), 797--809. Available at $\langle$http://www.research.att.com/$\sim$amo$\rangle$. \bibitem[teRiele]{teRiele} H. J. J. te~Riele, A new lower bound for the de Bruijn-Newman constant, {\em Numer. Math. 58} (1991), 661--667. \bibitem[Titchmarsh]{Titchmarsh} E. C. Titchmarsh, {\em The Theory of the Riemann Zeta-function}, 2nd ed. (revised by D. R. Heath-Brown), Oxford Univ. Press, 1986. \bibitem[vandeLunetRW]{vandeLunetRW} 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. 46} (1986), 667--681. } \end{thebibliography} \clearpage \begin{table} \caption{ High zeros of the Riemann zeta function. For each index $j$, presents the height of the $j$-th non-trivial zero of the zeta function.} %{\footnotesize $$ \begin{array}{c|c} j & x_{j}/2 \\ \hline 10^{20} + 718,107,310 & 15202440116027338091.2242705... \\ 10^{20} + 718,107,311 & 15202440116027338091.3996817... \\ 10^{20} + 718,107,312 & 15202440116027338091.5582027... \\ 10^{20} + 718,107,313 & 15202440116027338091.6199370... \\ 10^{20} + 718,107,314 & 15202440116027338091.7996865... \\ 10^{20} + 718,107,315 & 15202440116027338091.8904349... \\ 10^{20} + 718,107,316 & 15202440116027338092.0427716... \\ 10^{20} + 718,107,317 & 15202440116027338092.1653606... \\ 10^{20} + 718,107,318 & 15202440116027338092.3170162... \\ 10^{20} + 718,107,319 & 15202440116027338092.4882758... \\ 10^{20} + 718,107,320 & 15202440116027338092.6841839... \\ 10^{20} + 718,107,321 & 15202440116027338092.8183149... \\ 10^{20} + 718,107,322 & 15202440116027338092.8183868... \\ 10^{20} + 718,107,323 & 15202440116027338093.0316170... \\ 10^{20} + 718,107,324 & 15202440116027338093.1807310... \\ 10^{20} + 718,107,325 & 15202440116027338093.3490216... \\ 10^{20} + 718,107,326 & 15202440116027338093.5183145... \\ 10^{20} + 718,107,327 & 15202440116027338093.7585243... \\ 10^{20} + 718,107,328 & 15202440116027338093.8237557... \\ 10^{20} + 718,107,329 & 15202440116027338093.9173261... \\ \end{array} $$ %} \end{table} \end{document}