Completing Turing's parabolic-contour extension of his 1943 method for calculating the zeta-function

A. M. Turing's 1943 paper 'A Method for the Calculation of the Zeta-Function' gave one of the first algorithms for computing the Riemann zeta function $\zeta(s)$ with fully explicit, rigorous error bounds, based on evaluating a contour integral by the trapezoidal rule. Section 7 of the paper presents an alternative version, built on another standard integral representation of $\zeta(s)$, in which the contour near the positive real axis is a straight line at angle $\pi/4$; Turing states that this variant 'is only applicable for large values of $t$', and remarks that the restriction 'is possible to remove ... by integrating along a parabola, e.g., the parabola $x^2=2\mu y+\mu^2$', because the conformal mapping $u^2=z$ transforms that parabola into a straight line. He displays the transformed integral and the paper ends there: no quadrature formula, error bound, or computational prescription for the parabolic contour was ever published, by Turing or by later authors. This record states the problem of completing that construction: derive the explicit quadrature formula for the parabolic contour, prove a fully explicit error bound valid down to moderate $t$ (where the Riemann-Siegel asymptotic formula is not yet accurate and Euler-Maclaurin summation is expensive), and give the parameter-choice prescription. Later literature solved the underlying computational problem by other means (smoothed formulas, alternative quadratures, fast multipoint evaluation), so the expected impact of a completion is chiefly historical and pedagogical, with possible value as a simple reference algorithm with a priori error control.

Background

The Riemann zeta function $\zeta(s)$, defined for $\Re s>1$ by $\zeta(s)=\sum_{n\ge1}n^{-s}$ and extended to all $s\ne1$ by analytic continuation, governs the distribution of prime numbers through its zeros in the critical strip $0<\Re s<1$; locating these zeros numerically requires evaluating $\zeta(s)$, especially on the critical line $\Re s=1/2$, with certified accuracy.

Two classical evaluation methods frame the problem. Euler-Maclaurin summation (a classical formula expressing a series or integral in terms of a finite sum plus derivative corrections at the endpoints) is valid at all heights but needs on the order of $t$ terms to compute $\zeta(\sigma+it)$. The Riemann-Siegel formula reduces the work to a main sum of about $\sqrt{t/2\pi}$ terms plus asymptotic correction terms; it is accurate for large $t$, but its remainder is governed by a sharp cut-off at the saddle point (the point where the integrand's phase is stationary, so the main contribution concentrates there), which makes explicit remainder bounds laborious, and such bounds are available only above a few hundred in $t$. Between the two regimes lies an intermediate range of $t$ that is expensive for Euler-Maclaurin and not yet accurate for the Riemann-Siegel asymptotics.

Turing's 1943 paper (read March 16, 1939; published in the journal volume of 1943) pursued a method with completely explicit error control. His main method (Sections 2-6) evaluates a contour integral of an elementary integrand — containing factors of the form $(1-e^{\mp 2\pi i z})^{-1}$, whose poles sit at the integers — by the trapezoidal rule (the classical quadrature rule approximating $\int f\,dx$ by $h\sum_n f(nh)$), which converges exponentially fast when the integrand is analytic in a strip around the path and decays like $e^{-t^2}$; this exponential convergence is the observation for which the paper is still cited in numerical analysis. Turing makes all constants explicit: his central inequality (5.20) is valid for $t>25$, and Section 6 gives parameter choices (with a stated small total error) applying for $t>350$.

Section 7, 'A similar method', starts from what Turing calls 'an alternative, and better known, integral representation of the zeta-function' (obtained from the functional equation), integrated along a contour $C_m$ coming from infinity in the first quadrant, crossing the real axis between $m$ and $m+1$ (with $m$ a positive integer) and again between $-m$ and $-m-1$, and going to infinity in the second quadrant — threading between the poles at the integers. If the part of $C_m$ near the positive real axis is a straight line cutting the negatively directed real axis at $\mu$ at an angle of $\pi/4$, then for large $t$ 'the only appreciable contribution to the integral comes from the neighbourhood of the positive real axis', and the same trapezoidal machinery yields the displayed approximate formula. Turing highlights an advantage: for points not on the critical line, only two real integrals must be evaluated rather than four, 'of value for calculation of zeros not on the critical line'. But, in his words, 'the method is only applicable for large values of $t$; it is, however, possible to remove this restriction by integrating along a parabola, e.g., the parabola

$$x^2 = 2\mu y + \mu^2 \quad (m < \mu < m+1).$$

The conformal mapping $u^2 = z$ transforms this parabola into a straight line' (a conformal map is an angle-preserving one-to-one analytic change of variables; writing $z=x+iy$ and $u=\alpha+i\beta$ gives $z=u^2=(\alpha^2-\beta^2)+2i\alpha\beta$, under which a straight line at $45^\circ$ through $-i\beta_0$ maps exactly onto $x^2=2\beta_0^2 y+\beta_0^4$, i.e. the stated parabola with $\mu=\beta_0^2\in(m,m+1)$). The paper displays the resulting $u$-plane integral — whose line of integration cuts the imaginary axis between $-im^{1/2}$ and $-i(m+1)^{1/2}$ — and ends. No formula, error bound, or prescription for the parabolic contour follows.

Problem Statement

Complete the construction that Turing left as an unproved remark at the end of Section 7 of his 1943 paper. The three components below jointly constitute one objective — a complete, correct, explicit algorithm of Turing's type for computing $\zeta(s)$ at points $s=\sigma+it$ (so that $t$ is the height of the point), valid at moderate heights.

(1) Contour deformation and change of variables. Starting from the integral representation of $\zeta(s)$ stated in Section 7, with contour $C_m$ crossing the real axis between $m$ and $m+1$ and again between $-m$ and $-m-1$ (with $m$ a positive integer), replace the part of the contour near the positive real axis by the parabola $x^2=2\mu y+\mu^2$ in the $z$-plane (where $z=x+iy$), with $m<\mu<m+1$, and perform the substitution $z=u^2$ so that the integral becomes an integral along a straight line in the $u$-plane, matching the transformed integral displayed at the end of the paper (line cutting the imaginary axis between $-im^{1/2}$ and $-i(m+1)^{1/2}$). The pole bookkeeping forced by the factors $(1-e^{\mp 2\pi i z})^{-1}$ in the integrand (poles at the integers) must be carried out explicitly: the deformation must be shown to enclose exactly the poles it should, with their residues appearing correctly in the final formula.

(2) Explicit quadrature formula and rigorous error bound. Derive the trapezoidal-rule (or equivalent) quadrature formula for $\zeta(s)$ based on (1) — the parabolic analogue of the large-$t$ formula displayed in Section 7 — together with a theorem bounding the total error (quadrature error, series truncation, and residue terms) in which every constant is explicit and no step is asymptotic in $t$. The bound must hold for all $t\ge t_0$ with $t_0$ an explicitly stated finite threshold that removes the 'only applicable for large values of $t$' restriction of the straight-line $\pi/4$ variant and reaches into the moderate-$t$ intermediate range that motivated the parabolic extension, and it must also cover points $\sigma+it$ with $\sigma\ne1/2$, where the method needs only two real integrals.

(3) Computational prescription. Specify how to choose $m$, $\mu$, the step size, and the truncation to attain a target accuracy $\eta$ at a given $s$, completing an algorithm of Turing's type. Numerical validation at moderate $t$, including a point off the critical line, supports the demonstration that the prescription works as intended.

The problem can also be resolved negatively: a proof that the construction as sketched cannot be made to work — for example, that any deformation of $C_m$ to the stated parabola necessarily crosses poles of the integrand in an unrepairable way, or that the transformed integrand fails the strip-analyticity or exponential-decay conditions required for exponentially convergent trapezoidal evaluation at moderate $t$. Such a result resolves this problem negatively for the displayed example; since Turing's assertion as quoted is existential over parabolas ('a parabola, e.g., the parabola $x^2=2\mu y+\mu^2$'), it would refute that assertion only if impossibility were established for parabolic contours generally, not merely for the single displayed example.

References

1. A. M. Turing, 'A Method for the Calculation of the Zeta-Function', Proceedings of the London Mathematical Society (2) 48 (1943), 180-197. DOI: 10.1112/plms/s2-48.1.180, https://doi.org/10.1112/plms/s2-48.1.180. King's College Cambridge Turing Digital Archive, AMT/B/17, https://turingarchive.kings.cam.ac.uk/method-calculation-zeta-function
2. A. M. Turing, 'Some Calculations of the Riemann Zeta-Function', Proceedings of the London Mathematical Society (3) 3 (1953), 99-117. DOI: 10.1112/plms/s3-3.1.99, https://doi.org/10.1112/plms/s3-3.1.99
3. A. M. Turing, 'Collected Works of A. M. Turing: Pure Mathematics', edited by J. L. Britton, with a section on Turing's statistical work by I. J. Good, North-Holland, Amsterdam (1992), xxii+287 pp. ISBN 0-444-88059-3; zbMATH 0751.01017, https://zbmath.org/52515
4. Andrew R. Booker, 'Turing and the Riemann Hypothesis', Notices of the American Mathematical Society 53 (2006), no. 10, 1208-1211, https://www.ams.org/notices/200610/fea-booker.pdf
5. Ghaith A. Hiary, 'An alternative to Riemann-Siegel type formulas', Mathematics of Computation 85 (2016), 1017-1032. DOI: 10.1090/mcom/3019, https://doi.org/10.1090/mcom/3019; arXiv:1403.0317, https://arxiv.org/abs/1403.0317
6. Michael Rubinstein, 'Computational methods and experiments in analytic number theory', in: F. Mezzadri and N. C. Snaith (eds.), Recent Perspectives in Random Matrix Theory and Number Theory, London Mathematical Society Lecture Note Series 322, Cambridge University Press (2005), pp. 425-510. DOI: 10.1017/cbo9780511550492.015, https://doi.org/10.1017/cbo9780511550492.015; arXiv:math/0412181, https://arxiv.org/abs/math/0412181
7. A. M. Odlyzko and A. Schönhage, 'Fast algorithms for multiple evaluations of the Riemann zeta function', Transactions of the American Mathematical Society 309 (1988), 797-809. DOI: 10.1090/s0002-9947-1988-0961614-2, https://doi.org/10.1090/s0002-9947-1988-0961614-2
8. Mohammad Alazah, Simon N. Chandler-Wilde and Scott La Porte, 'Computing Fresnel integrals via modified trapezium rules', Numerische Mathematik 128 (2014), 635-661. DOI: 10.1007/s00211-014-0627-z, https://doi.org/10.1007/s00211-014-0627-z; arXiv:1209.3451, https://arxiv.org/abs/1209.3451
9. S. Barry Cooper and Jan van Leeuwen (eds.), 'Alan Turing: His Work and Impact', Elsevier (2013); the mathematics section 'Some Calculations of the Riemann Zeta function: On a Theorem of Littlewood' (pp. 265-320) contains the historical commentary 'Alan Turing and the Riemann Zeta function' by Dennis A. Hejhal and Andrew M. Odlyzko (pp. 265-279) together with Hejhal's 'A Few Comments About Turing's Method'. DOI: 10.1016/B978-0-12-386980-7.50011-3, https://doi.org/10.1016/B978-0-12-386980-7.50011-3
10. Pieter Moree, Izabela Petrykiewicz and Alisa Sedunova, 'A computational history of prime numbers and Riemann zeros' (2018). arXiv:1810.05244, https://arxiv.org/abs/1810.05244