Alan Turing (right) with two engineers at the console of the Ferranti Mark I computer in 1951 (Photo: New Atlas)
Alan Turing (1912-54) is a well-known name for a variety of reasons. To the general public, he is probably best known for his work on the cryptanalysis of the Enigma ciphering system during the World War II. To mathematicians, however, he is perhaps best known for being one of the founders of computer science. He was the person who formalized the core concepts of computation and algorithms via his invention of the Turing machine. He also solved Hilbert’s Entscheidungsproblem (see essay below).
Few, however, are aware of his significant contributions to analytic number theory via his work on the non-trivial zeros of the Riemann zeta function and, by extension, the Riemann hypothesis.
The Problem
The first essay I ever wrote about mathematics was on the Riemann zeta function and its association with the distribution of prime number, the so-called Riemann hypothesis (see technical essay below).
Very briefly, German mathematician Bernhard Riemann (1826-66)’s unsolved 1859 hypothesis asserts that all the non-trivial zeros of the Riemann zeta function lie on the “critical line” Re(s) = 1/2. The Riemann zeta function is defined for complex s with Re(s) > 1 by
When extended analytically, the function can be defined for the entire complex plane except for the point s = 1 where there is a pole of order 1 (a singularity). The extended function has trivial zeros at s = -2, -4, -6, … and, according to Riemann’s hypothesis, “non-trivial” zeros of the form s = 1/2 + it.
Riemann’s initial computations of zeros found that they all (three!) have Re(s) = 1/2 and so he asserted it to be true for all non-trivial zeros, of which G.H. Hardy (1877-1947) in 1914 proved that there are infinitely many. In 2020, Dave Platt and Timothy Trudgian showed that the Riemann hypothesis is true for the first 1.2363×1013 zeros, as well as for large blocks of zeros much higher up, some around zero number 1024.
“If I were to awaken after having slept a thousand years, my first question would be: has the Riemann Hypothesis been proven?” — David Hilbert (1862-1943)
First posed by Riemann in the only paper he ever published on number theory, Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse (“On prime numbers less than a given magnitude”) the hypothesis remains open to this day, despite considerable efforts by a variety of mathematicians over the last 166 years. I still receive purported proofs via email1 every few weeks or so.
Early Computations of Zeros
Following Riemann’s initial calculations of non-trivial zeros in the 1850s various mathematicians took it upon themselves to numerically verify (or falsify) his hypothesis. Among the most prominent in the early years were Jørgen P. Gram (1850-1916), R. J. Backlund and John I. Hutchinson (1867-1935). Curiously, much of this work was accomplished using a less efficient method (Euler-Maclaurin summations) than the method employed by Riemann, which was not widely known until Carl L. Siegel (1896-1981) discovered it in Riemann’s unpublished notes in the early 1930s. He published what he found, now known as the Riemann-Siegel formula2, in the paper:
Siegel, C. L. (1932). "Über Riemanns Nachlaß zur analytischen Zahlentheorie", Quellen Studien zur Geschichte der Math. Astron. Und Phys. Abt. B: Studien 2: 45–80.
In terms of computational efficiency, where the Euler-Maclaurin method requires t steps, the Riemann-Siegel formula only requires √t steps. Following the publication of Riemann’s formula, Oxford mathematician Edward C. Titchmarsh (1899-1963) in the 1930s obtained a grant to “computationally” verify more zeros. With the assistance of astronomer Leslie Comrie (1893-1950) and various (female) operators3 of punched-card equipment (typically used to calculate astronomical predictions) he was able to verify that the first 1041 zeros lie on the critical strip Re(s) = 1/2 (Hejhal & Odlyzko, 2012). This result, published in 1936, was the last published paper to report on non-trival zeros calculated by hand.
Enter Alan Turing
By 1936, 23-year-old Alan Turing had graduated from Cambridge and become the youngest ever fellow of King’s College. Interested in continuing his work on Hilbert’s Entscheidungsproblem he applied and was accepted for graduate school at Princeton University (see essay below).
Apparently, Turing grew interested in the Riemann hypothesis around the same time he matriculated at King’s College as an undergraduate student in 1931. As with many mathematicians before and after, his curiousity stemmed from his own studies of prime numbers. We know that he was quick to obtain a copy of Cambridge mathematician Albert E. Ingham (1900-67)’s (now) classic book The Distribution of Prime Numbers* which was published in 1932 (Hodges, 1983). The following year, Turing’s rowing partner (and J.E. Littlewood (1885-1977)’s Ph.D. student) Stanley Skewes (1899-1988) proved that if Riemann’s hypothesis is true, then the smallest x for which the prime-counting function π(x) > Li(x) must satisfy the property x < 10A where A = 10B and B = 1034. The number x is often referred to as the first Skewes’ number4.
Li(x) is the Logarithmic integral function, defined by:
Li(x) gives a very good approximation of the number of primes less than a given magnitude
After reading Titchmarsh’s 1936 paper (verifying the first 1041 zeros using human computers), Turing had the idea of building a special purpose analog computer to make verification of the first 5598 zeros more efficient. He obtained a grant of £40 from the Royal Society for this purpose. By all accounts, Turing was skeptical of Riemann’s hypothesis and believed that he would be able to falsify the claim by finding a zero where Re(s) ≠ 1/2.
By 1937, Turing was in Princeton working with Church on his PhD thesis. He kept in touch with both Ingham and Hardy (who was a visiting scholar at Princeton in the spring semester of that year). From Ingham’s archive, it appears that Turing was looking to attack the hypothesis by “sharpening up” the reasoning used by Littlewood when he in 1914 proved that Li(x) and π(x) cross infinitely many times. Ingham replied encouragingly, but suggested an alternative, more recent proof of Littlewood’s theorem and made note of the fact that Skewes has already tried this approach and gotten a better upper bound for B at 1019.
“It may be that, like with π(x) − Li(x), ζ(12 + it) may go on for a very long time before revealing its true character.”5 — Edward C.Titchmarsh (1899-1963)
Returning to Cambridge in the summer of 1937, Turing pursues the upper bound for ψ(x) − x (a function closely related to π(x) > Li(x), called the second Chebyshev function, denoted by psi of x), and obtains a much better bound than Skewes. The draft of a paper outlining the result contains several estimates of Riemann’s zeta function, including one from Titchmarsh’s paper. Likely due to the outbreak of war, his findings were not published until 1945:
Ingham responded positively to Turing’s results, but also conveys that Littlewood and Skewes were in the process of deriving a bound wherein nothing is assumed about the truth of RH (a key assumption in Titchmarsh and Turing’s findings). Around this time, Turing realizes that verifying a larger set of zeros would enable him to obtain an even better bound. Thus, he returns to his idea of building a special purpose computer for this purpose.
See Hejhal & Odlyzko (2012, p. 8) for a complete summary of Turing’s correspondence with Ingham, Titchmarsh, Skewes and others regarding their work on the Riemann zeta function.
The Turing Zeta Computer (1939)
Turing’s first idea for a special purpose machine to assist in the calculation of non-trivial zeros consisted of an assortment of relays. It was built by Turing himself with the help of a graduate student named Malcolm MacPhail6 in the workshop the Princeton physics department (Casselman, 2006). The machine only did one thing: it multiplied two integers in binary format. At the time, this was an innovation.
By 1939, Turing had graduated from Princeton and returned to Cambridge. There, he applied for and received a grant from the Royal Society to cover the costs of parts for a new machine.
Turing’s Grant Application (March, 1939)
It is proposed to make calculations of the Riemann zeta-function on the critical line for 1450 < t < 6000 with a view to discovering whether all the zeros of the function in this range of t lie on the critical line. An investigation for 0 < t < 1464 has already been made by Titchmarsh. The most laborious part of such calculations consists in the evaluation of certain trigonometrical sums
In the present calculation it is intended to evaluate these sums approximately in most cases by the use of apparatus somewhat similar to what is used for tide prediction. When this method does not give sufficient accuracy it will be necessary to revert to the straightforward calculation of the trigonometric sums, but this should be only rarely necessary. I am hoping that the use of the tidepredicting machine will reduce the amount of such calculation necessary in a ratio of 50:1 or better. It will not be feasible to use already existing tide predictors because the frequencies occurring in the tide problems are entirely different from those occurring in the zeta- function problem. I shall be working in collaboration with D. C. MacPhail, a research student who is an engineer. We propose to do most of the machine-shop work ourselves, and are therefore applying only for the cost of materials, and some preliminary computation.
The formula Turing provides as an example of a trigonometric sum in the application is the formula by Riemann that was discovered by Siegel. As Turing admits in the application, this “apparatus would be of little permanent value”, but assist in the locating of “likely locations for zeros” which could later be checked by more traditional means (Casselman, 2006). Again, Turing was assisted by a graduate student in the construction of the device, however this time around it was Malcolm’s brother Donald MacPhail. In a letter to Turing’s mother after his death, Malcolm described the usefulness of the machine as follows (Casselman, 2006): “Alan’s zeta function computer was a device for adding up a large number of sines and cosines of various periods and amplitudes... The gears, of which there were to behundreds, were to provide an approximation to the required periods... Alan obtained rational approximations to [the periods]... by the method of continued fractions. A pair of gears having the numberof teeth indicated respectively by the numerator and denominator of the fraction would then rotate at speeds having approximately the desired ratio.”
Due to the onset of World War II, Turing’s proposed machine was never completed. Famously, Turing spent the war at Bletchley Park working on cryptanalysis. Between 1945-47, he lived in Hampton, London where he worked on the ACE (Automatic Computing Engine) at the National Physical Laboratory (NPL). For the academic year 1947-48, he was back in Cambridge where, as it happens, Skewes was on sabbatical and the two worked together again. By September of 1948, Turing had joined his former professor Max Newman (1897-1984) in Manchester to help build the Manchester Mark I prototype, a machine for which Newman had received a large grant from the Royal Society to build. A description of this machine written by its designers Williams & Kilburn (1948) was published in Nature and is available here.
The Manchester Mark I prototype computer (Photo: Manchester Future)
Turing, who had been assigned the rank of reader (professor without a chair) at Manchester University was put in charge of leading software development for this machine. Still interested in the non-trivial zeros of the Riemann zeta function, Turing eventually set it to work on investigating their locations. As he later writes of this effort,
The calculations had been planned some time in advance, but had in fact to be carried out in great haste. If it had not been for the fact that the computer remained in serviceable condition for an unusually long period from 3 p.m. one afternoon to 8 a.m. the following morning it is probable that the calculations would never have been done at all. As it was, the interval 2π.632 < t < 2π.642 was investigated during that period, and very little more was accomplished.
Evidently, Turing was disappointed with the results he obtained. However, to this day, one of the methods he presented in the paper7 remains a “small but essential ingredient” in computations of non-trivial zeros of the Riemann zeta function. The paper is:
After Turing’s death in 1954, errors were found in the paper and a correction was published by Russell Sherman Lehman (1930-2023) in 1970:
Lehman, R. S. 1970. "On the Distribution of Zeros of the Riemann Zeta-Function". Proceedings of the London Mathematical Society. s3-20 (2): 303–320
Those interested in reading more about Alan Turing and his work on the Riemann zeta function are encouraged to obtain the definitive biography of his life, written by Andrew Hodges, entitled Alan Turing: The Enigma*.
The Riemann-siegel formula is an asymptotic formula for the error of the approximate function equation of the Riemann zeta function. It is an approximation of the zeta function by a sum of two finite Dirichlet series.
Skewes discovered the second Skewes’ number in 1955, an x that is larger than eˆeˆeˆeˆ7.705 but smaller than 10ˆ10ˆ10ˆ964. Further refinements have been made since.
Curiously, For small x, the logarithmic integral function Li(x) is larger than the prime counting function, but the difference changes sign an infinite number of times as x increases. The first time that this happens, though, is somewhere between 1019 and 1.4×10316 !
In Hodges’ biography of Turing, MacPhail described his contributions to the project as “to lend Turing the key to the shop, which was probably against all the regulations, and to show him how to use the lathe, drill press, (etc.) without chopping off his fingers. And so, he wound the relays; and to our surprise and delight, the calculator worked”
Donald Michie, the founder of the Turing Institute in Glasgow, was one of Turing's colleagues at Bletchley Park. In 1960, Michie used 300 matchboxes to build MENACE (Matchbox Educable Noughts And Crosses Engine), a machine capable of learning to play a perfect game of noughts and crosses. Martin Gardner popularized this fun experiment in his column in "Scientific American" https://www.scientificamerican.com/article/mathematical-games-1962-03/ It was an example of what is now called Reinforcement Learning, a technology capable of beating humans in chess, Go, and poker. The Turing Institute lacked support from the British government and went out of business in 1994 https://www.heraldscotland.com/business_hq/13189678.connected-scientist-whose-life-inspires-major-new-film-obscure-research-unit-scotland-flying-space-shuttle-invention-internet/