Fast algorithms for multiple evaluations of the Riemann zeta function

Abstract:

The best previously known algorithm for evaluating the Riemann zeta function, $\zeta (\sigma + it)$, with $\sigma$ bounded and $t$ large to moderate accuracy (within $\pm {t^{ - c}}$ for some $c > 0$, say) was based on the Riemann-Siegel formula and required on the order of ${t^{1/2}}$ operations for each value that was computed. New algorithms are presented in this paper which enable one to compute any single value of $\zeta (\sigma + it)$ with $\sigma$ fixed and $T \leqslant t \leqslant T + {T^{1/2}}$ to within $\pm {t^{ - c}}$ in $O({t^\varepsilon })$ operations on numbers of $O(\log t)$ bits for any $\varepsilon > 0$, for example, provided a precomputation involving $O({T^{1/2 + \varepsilon }})$ operations and $O({T^{1/2 + \varepsilon }})$ bits of storage is carried out beforehand. These algorithms lead to methods for numerically verifying the Riemann hypothesis for the first $n$ zeros in what is expected to be $O({n^{1 + \varepsilon }})$ operations (as opposed to about ${n^{3/2}}$ operations for the previous method), as well as improved algorithms for the computation of various arithmetic functions, such as $\pi (x)$. The new zeta function algorithms use the fast Fourier transform and a new method for the evaluation of certain rational functions. They can also be applied to the evaluation of $L$-functions, Epstein zeta functions, and other Dirichlet series.