For example, to compute the zeroes of the Riemann zeta function using the Euler-Maclaurin summation method one has to do O(T) work. The Euler-Maclaurin summation method for zeta is given by $ \zeta(s)= \sum^{N-1}_{n=1} \frac{1}{n^{s}} + \frac{N^{1-s}}{s-1}+\frac{N^{-s}}{2}+\frac{B_2}{2}sN^{-s-1} +\ldots + \\ \frac{B_{2v}}{(2v)!} \frac{(s+2v-2)!}{(s-1)!}N^{-s-2v+1} + R_{2v}$


$R_{2v}=-\frac{s(s+1) \ldots (s+2v-1)}{(2v+1)!} \int^\infty_N B_{2v+1}(x-[x]-\frac{1}{2}x^{-s-2v-1} \mathrm{d} x.$

may be computed in O(t) time. The Riemann-Siegel formula counterpart may be computed in $O\sqrt(t)$ time. I haven't the first clue of why this is true and this concept of time taken for computations. Anybody care to direct me somewhere which would give an explanation? Thanks.


(this is a kind of follow up to a discussion about partial sums starting with an introduction to $\zeta\,$)

Let's compare the two proposed methods to evaluate $\zeta\left(s\right)$ with $s=\frac 12+i\,t\ $ (Euler-Maclaurin may be applied everywhere, Riemann-Siegel may be used too if $\,\Re(s)\not =\frac 12$ but this is less documented) :

  • Using Euler-Maclaurin you will need to compute the sum of at least the $\,N\approx \dfrac t{2\pi}\ $ first terms to get an accurate result (ignoring the 'cost' of a few Bernoulli terms and neglecting the remainder $R_{2v}$) from your expression : $$\zeta(s)= \sum^{N}_{n=1} \frac{1}{n^{s}} + \frac{N^{1-s}}{s-1}-\frac 1{2\,N^s}+\frac{B_2}{2}sN^{-s-1} +\ldots + R_{2v}$$ To illustrate this let's add $3000$ terms ($\displaystyle 1,\,2^{-1/2-it},\,3^{-1/2-it},\cdots$) in the complex plane with the first term at the right at $1+0\,i$ and finishing near the middle at $0+0\,i\ $ because I choose $t$ to be the first value larger than $10000$ such that $\zeta\left(\frac 12+i\,t\right)=0\,$. This gave the picture :

method 1

At this point let's apply the functional equation to the $N$ first terms of the series for $\zeta$ (consider every power term at $1-s$ instead of $s$ and multiply by $\gamma(1-s)$ as exposed at Wikipedia or at the bottom of this text) then we will get :

functional equation

(in the simple case $\,\Re(s)=\frac 12\,$ this is merely a 'mirror effect' applied to the first picture : complex numbers are replaced by their conjugates and a global rotation depending smoothly of $t$ is applied)

Now let's superpose the second picture turned $180^\circ$ to the first one : result

and observe the superposition of the first values (at the right on the first picture) to the final 'nodes' (at the left of the first picture).

  • This is the whole point of the Riemann-Siegel formula :
    from the $\,N\approx \dfrac {\Im(s)}{2\pi}\,$ terms needed to evaluate $\zeta(s)$ the first $[\sqrt{N}]$ terms provide half of the contribution while the remainder may be obtained with the $[\sqrt{N}]$ first terms terms of $\zeta(1-s)$ multiplied by $\,\gamma(1-s)$.

Replacing a sum over $N$ terms for Euler-Maclaurin by a sum over $[\sqrt{N}]$ terms is not uninteresting!

This may be done because of the functional equation : $$\zeta(s)=\gamma(1-s)\zeta(1-s)$$ with $\;\displaystyle\gamma(s):=\pi^{1/2-s}\frac{\Gamma(s/2)}{\Gamma((1-s)/2)}\;$ to give the "approximate functional equation" : $$\zeta(s)=\sum_{n=1}^m\frac 1{n^s}+\gamma(1-s)\sum_{n=1}^m\frac 1{n^{1-s}} + R(s)$$ the price is a not so easy to evaluate remainder : $$R(s)=\frac{\Gamma(1-s)}{2\pi i}\int_{C_m}\frac{(-x)^{s-1}e^{-mx}}{e^x-1}dx$$ (an approximation of this integral is needed for a precise evaluation)

The $\gamma$ notation used in the approximate functional equation is from Carl Erickson's very interesting and recommended article " A Geometric Perspective on the Riemann Zeta Function's Partial Sums".

For a formal derivation of these expressions your may consult too Titchmarsh's book about zeta or the chap.7 of Edwards' excellent book with a direct link to similar formulas here.

The details of actual computations are clearly exposed by Takusagawa and Gourdon&Sebah (for more see Edwards' book or Pugh's thesis.

  • 2
    $\begingroup$ Nice curlicues! $\endgroup$ – J. M. isn't a mathematician Apr 12 '13 at 13:00
  • $\begingroup$ Thanks @J.M. I have a generator for that ! $\endgroup$ – Raymond Manzoni Apr 12 '13 at 13:15
  • 1
    $\begingroup$ Nice wall-paper. Look familiar? math.harvard.edu/~elkies/M229.09/index.html $\endgroup$ – user12802 Sep 11 '13 at 22:00
  • 1
    $\begingroup$ @Andrew: The basic motif is deeper than you think. See this picture from Feynman's Masterpiece 'QED: The Strange Theory of Light and Matter. Quantum Electodynamics behaves this way as well as the other fundamental interactions QCD and Weak interactions ! (concerning gravity I don't know...) $\endgroup$ – Raymond Manzoni Sep 11 '13 at 22:16
  • 1
    $\begingroup$ For your R(s), I calculated the remainder R(s) for the Riemann-Siegel Z function using Ken Takusagawa's code and just divided it by exp(iθ(t)). It worked! $\endgroup$ – user258279 Mar 16 '17 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.