In mathematics, the Odlyzko–Schönhage algorithm is a fast

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

for evaluating the

Riemann zeta function The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...

at many points, introduced by . The main point is the use of the

fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...

to speed up the evaluation of a finite

Dirichlet series In mathematics, a Dirichlet series is any series of the form \sum_^\infty \frac, where ''s'' is complex, and a_n is a complex sequence. It is a special case of general Dirichlet series. Dirichlet series play a variety of important roles in analyti ...

of length ''N'' at O(''N'') equally spaced values from O(''N''²) to O(''N''^1+ε) steps (at the cost of storing O(''N''^1+ε) intermediate values). The

Riemann–Siegel formula In mathematics, the Riemann–Siegel formula is an asymptotic formula for the error of the approximate functional equation of the Riemann zeta function, an approximation of the zeta function by a sum of two finite Dirichlet series. It was found by ...

used for calculating the Riemann zeta function with imaginary part ''T'' uses a finite Dirichlet series with about ''N'' = ''T''^1/2 terms, so when finding about ''N'' values of the Riemann zeta function it is sped up by a factor of about ''T''^1/2. This reduces the time to find the zeros of the zeta function with imaginary part at most ''T'' from about ''T''^3/2+ε steps to about ''T''^1+ε steps. The algorithm can be used not just for the Riemann zeta function, but also for many other functions given by Dirichlet series. The algorithm was used by to verify the

Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in ...

for the first 10¹³ zeros of the zeta function.

References

* * * This unpublished book describes the implementation of the algorithm and discusses the results in detail. * Analytic number theory Computational number theory Zeta and L-functions {{algorithm-stub