Calculation method for the Riemann zeta function
The calculation methods for the Riemann zeta function are algorithms that determine numerical values for complex values as precisely and quickly as possible. More and more efficient processes have been developed over several centuries. The use of computers has made very extensive calculations possible, especially since the beginning of the 21st century.
The Riemann zeta function
![](https://upload.wikimedia.org/wikipedia/commons/f/f8/Thumbnail-of-Riemann_Zeta.png)
The Riemann zeta function is a complex-valued function that works for a complex number with a real part through the infinite sum
is defined.
One of the most important properties of the Riemann zeta function is its connection with the prime numbers . It establishes a relationship between complex analysis and number theory (see analytical number theory ) and forms the starting point of the Riemann Hypothesis. The following expression, which goes back to Leonhard Euler (1748), represents the connection in a formulaic way as
where represents an infinite product over all prime numbers. The expression follows directly from the theorem about the uniqueness of prime number decomposition and the summation formula for the geometric series .
The function can be clearly analytically continued beyond the original convergence range of Euler's sum or product formula to the entire complex level - with the exception of . A meromorphic function is obtained : it has a simple pole at the point .
where are the gamma function and the Bernoulli numbers .
The exact position of the zeros of the zeta function is of great importance for the distribution of prime numbers. By means of numerical methods, the Riemann Hypothesis can be supported (but not proven).
history
The powerful computers that emerged in the second half of the 20th century offered new possibilities. As early as 1936, the mathematician Edward Charles Titchmarsh , who worked in Oxford , calculated the first 1041 non-trivial zeros of the zeta function with a machine that had originally been designed for astronomical calculations. In 1953, these calculations were continued by Alan Turing . His method is still used today. A computer was used for the first time. In research on the Riemann zeta function, computers were mainly used to check the correctness of the Riemann Hypothesis for as many zeros as possible. Although all calculations are numerical methods, they show exactly and not only approximately that the examined zeros are on the critical straight line.
The correctness of the Riemann Hypothesis has been questioned by many mathematicians, including Don Zagier . At a conference in Bonn in the early 1970s, a discussion between him and Enrico Bombieri finally came to a head and ended in a bet: Zagier predicted that there must be a zero of the zeta function that did not obey Riemann's prediction, Bombieri held against it. However, since neither of them assumed they would witness rigorous evidence during their lifetime, they agreed that Zagier would lose if the first 300 million zeros met the conjecture. At this point in time, several thousand zeros had already been located, but there were theoretical reasons that these should also be on the critical straight line. If the number got bigger, these reasons got weaker and from a certain size there were even indications that the assumption could be wrong. In the case of the first 300 million, it is “a miracle”, according to Zagier, if they are still without exception on the critical straight. Over time, the computing power of computers increased rapidly. The order of magnitude of the number of zeros from the bet soon came within reach. In 1979, a group from Amsterdam led by Herman te Riele and Richard P. Brent had finally checked 200 million zeros - all of them were on the critical straight. Zagier commented:
“I breathed a sigh of relief because it was a huge project. Thank goodness they had stopped at 200 million. Obviously they could have gone up to 300 million, but luckily they hadn't. Now I had a few years of air again.
However, Hendrik Lenstra , a good friend of Zagier, knew about his bet and pointed out to te Riele that Zagier would lose if the first 300 million zeros were on the critical straight. So the group counted up to 300 million and Zagier had to redeem his bet. With two bottles of Bordeaux wine he went to Bombieri and emphasized:
“200 million had nothing to do with my bet. They did that for themselves. But the last 100 million, they only made this calculation because of my bet. For that extra 100 million, they used about 1000 hours of CPU time. The cost of an hour back then was around $ 700. Since they only made this bill so that I would lose my bet and have to pay for the two bottles of wine, it's fair to say that each of these bottles is worth around $ 350,000. And that is truly more than the most expensive bottle of wine that has ever come under the hammer at an auction. "
Until 2005, the first 10 trillion zeros were checked by distributed computers as part of the so-called ZetaGrid Project . Everyone was on the critical straight.
Procedure
Euler-Maclaurin molecular formula
The “broken” molecular formula, which is obtained with the help of the Euler-Maclaurin empirical formula , has proven to be a good and historically used method . In general, any natural number is defined first, which should also apply. The following then applies:
The following applies to the remaining term
With the (free) choice of , it should also be noted that the remainder of the term only converges on the half-plane . Therefore must always apply. The error therefore decreases rapidly for increasing values of .
By using the functional equation (a quick calculation of the gamma function and the exponential function is easy to implement), it can also be assumed without restriction . Here the empirical formula is much faster. A disadvantage of this method, however, is that it loses its efficiency for growing imaginary parts.
The usefulness of this approximation has been known for some time. For example, Leonhard Euler determined the value of approx. 1734 with an accuracy of about 20 digits before he solved the Basel problem, which dealt with the analytically "exact" value of . For him, this numerical evaluation was the practical confirmation of the correctness of his precisely determined value.
Furthermore, the Danish mathematician Jørgen Pedersen Gram found numerical values of the first 15 non-trivial zeros in 1903, determining the first 10 zeros to six and the further 5 to one place after the decimal point.
Examples
One example is the numerical approximation of the numerical value of
on. The values and are sufficient for a very good approximation . Insertion gives:
The following table shows the numerical evaluation of this calculation.
term | Numerical value |
---|---|
This approximation, obtained with little effort, agrees with the actual value
already matched to six decimal places (rounded) after the comma. To underline the efficiency, it should be noted that if Euler had simply added up for the value of the term instead , around a million summands would have been necessary for the same approximation quality. If one assumes that Euler needed an average of 20 seconds of computing time per term, this would have meant around eight months of uninterrupted computing.
The decimal value of can be approximated in the same way. The choice of and is sufficient here .
term | Numerical value |
---|---|
This value is also accurate to six decimal places.
Alternating sums
A method using broken alternating rows comes from Borwein. Based on convergence accelerating transformations applied to the series
you get the easy to implement formula
where also depends on the choice of . This can be used for all values . The error may with to be estimated by
For , however, results
However, it also applies here that the method loses its efficiency on the positive real side for increasingly larger imaginary parts.
Calculation on the critical straight line
Riemann Siegel formula
Many methods lose their precision if the imaginary part of the argument is chosen to be very large, which is problematic when searching for roots along the critical straight line. Therefore, other methods are used here, one of which is the Riemann-Siegel formula.
For
follows quickly with the functional equation of the zeta function , ie , d. i.e., maps along the critical straight line only to values of the unit circle. So there can be a continuous real-valued function implicitly by the equation
define, where . This is also known as the Riemann-Siegel theta function . This finally defines the Riemann-Siegel function :
It is easy to show d. H. is even a real-valued function , but becomes zero if and only if there is a non-trivial zero of . It is chosen to be sufficiently large. For values it now follows with the approximate functional equation
The error term can be due to an asymptotic expansion
can be improved at will. Exact upper limits for result for about
The functions that can be explicitly determined become quite complicated with increasing ; the first are given by
Overall, a fairly precise calculation results in an outlay in arithmetic operations in the form of term calculations with subsequent addition . In order to find zeros, it is sufficient to identify areas with a change in sign (and then to perform an interval nesting for their precise determination ).
If in the range , then the choice is sufficient for a precision with one error , whereby only addends are required. Less special procedures (such as the alternating sum) require approx. Summands for a similar accuracy .
Procedure by Odlyzko and Schönhage
In 1988, AM Odlyzko and A. Schönhage developed a very fast method to determine values of the Riemann zeta function on the critical line. This is based on the ideas of the Riemann-Siegel formula, but only requires instead of arithmetic operations, whereby arbitrarily small can be chosen. The refinement of the computational techniques is based on the fast Fourier transform .
Progress in computing zeros
year | Number of zeros | author |
---|---|---|
1859? | 3 | B. Riemann used the Riemann-Siegel formula (unpublished but recorded). |
1903 | 15th | Jørgen Pedersen Gram used the Euler – Maclaurin molecular formula and discovered Gram's law. He showed that all 10 zeros (with an imaginary part of a maximum of 50) lie on the critical line with real part 1/2 by calculating the sum of the inverse tenth powers of the roots found. |
1914 | 79 (γ n ≤ 200) | RJ Backlund improved the previous methodology to determine that all zeros found so far lie on the critical straight line. |
1925 | 138 (γ n ≤ 300) | JI Hutchinson exposed the failure of Gram's Law at point g 126 . |
1935 | 195 | EC Titchmarsh made use of the recently rediscovered Riemann-Siegel formula. This is faster than the Euler-Maclaurin empirical formula: It takes about O ( T 3/2 + ε ) to track down zeros with an integral part smaller than T , while the latter takes about O ( T 2 + ε ) steps. |
1936 | 1041 | EC Titchmarsh and LJ Comrie are the last to calculate zeros by hand. |
1953 | 1104 | AM Turing found a more efficient way to check whether all zeros found up to a certain point actually lie on the straight line by checking that the function Z (t) has the correct sign at successive Gram's points (and that S ( T ) has an average value of 0). This required virtually no new work, since the signs of Z (t) were already known at the Gram's points from previous searches for zeros. This method is still used today. A computer was used for the first time. |
1956 | 15,000 | Derrick Henry Lehmer discovered a few cases in which zeros are “just about” on the straight line: two zeros are so close together that it is unusually difficult to recognize the change in sign. Today this is called "Lehmer's phenomenon" and occurs for the first time at the zeros with imaginary parts 7005.063 and 7005.101, which differ by only .04, while an average distance of 1 is expected in this region. |
1956 | 25,000 | DH Lehmer |
1958 | 35,337 | NA Meller |
1966 | 250,000 | RS Lehman |
1968 | 3,500,000 | Rosser , JM Yohe and Lowell Schoenfeld formulated Rosser's rule. |
1977 | 40,000,000 | RP Brent |
1979 | 81,000,001 | RP Brent |
1982 | 200,000,001 | RP Brent, J. van de Lune, HJJ te Riele , DT Winter |
1983 | 300,000,001 | J. van de Lune, HJJ te Riele |
1986 | 500,000,001 | van de Lune, te Riele and Winter gave statistical data on the zeros and various graphs of the function Z (t) in places with unusual behavior. |
1987 | Some with height of the order of (~ 10 12 ) | AM Odlyzko calculated a few zeros with imaginary parts around 10 12 to numerically test Montgomery's pair correlation conjecture . |
1992 | Some with height of the order (~ 10 20 ) | AM Odlyzko calculated around 175 million zeros with imaginary parts around 10 20 and discussed the results in detail. |
1998 | 10,000 with height of the order of (~ 10 21 ) | AM Odlyzko calculated some zeros with imaginary parts around 10 21 |
2001 | 10,000,000,000 | J. van de Lune (unpublished) |
2004 | 900,000,000,000 | S. Wedeniwski ( ZetaGrid project ) |
2004 | 10,000,000,000,000 and a few more in the altitude range (up to ~ 10 24 ) | X. Gourdon and Patrick Demichel use the method of Odlyzko and Schönhage . They also check two billion zeros in the ranges 10 13 , 10 14 ..., 10 24 . |
Individual evidence
-
↑ The following applies to the definition of the Bernoulli numbers used here :
- ↑ Marcus du Sautoy: The music of the prime numbers. On the trail of the greatest puzzle in mathematics. 5th edition. Beck, Munich 2006, ISBN 978-3-423-34299-5 , p. 234
- ↑ Turing, Alan M. (1953), Some calculations of the Riemann zeta-function , Proceedings of the London Mathematical Society, Third Series, 3: 99-117
- ↑ Marcus du Sautoy: The music of the prime numbers. On the trail of the greatest puzzle in mathematics. 5th edition. Beck, Munich 2006, ISBN 978-3-423-34299-5 , p. 238
- ^ Calculations relating to the zeros. Chapter 15. In: Titchmarsh: The Theory of the Riemann Zeta function.
- ↑ Marcus du Sautoy: The music of the prime numbers. On the trail of the greatest puzzle in mathematics. 5th edition. Beck, Munich 2006, ISBN 978-3-423-34299-5 , p. 268.
- ↑ Marcus du Sautoy: The music of the prime numbers. On the trail of the greatest puzzle in mathematics. 5th edition. Beck, Munich 2006, ISBN 978-3-423-34299-5 , p. 269.
- ↑ Ed Pegg Jr. "Ten Trillion Zeta Zeros"
- ^ HM Edwards: Riemann's Zeta Function. Dover, ISBN 978-0-486-41740-0 , p. 114.
- ↑ R. Backlund: About the zeros of the Riemann zeta function. Dissertation, Helsinki 1916.
- ^ HM Edwards: Riemann's Zeta Function. Dover, ISBN 978-0-486-41740-0 , p. 115.
- ^ HM Edwards: Riemann's Zeta Function. Dover, ISBN 978-0-486-41740-0 , p. 114.
- ↑ Julian Havil: Gamma. Springer-Verlag, Berlin et al. 2007, ISBN 978-3-540-48495-0 , p. 50.
- ↑ JP Gram: Sur les Zéros de la Fonction de Riemann. Acta Math. 27: 289-304 (1903).
- ↑ a b H. M. Edwards: Riemann's Zeta Function. Dover, ISBN 978-0-486-41740-0 , p. 116.
- ↑ P. Borwein: An efficient algorithm for the Riemann zeta function. In Théra, Michel A. (ed.). Constructive, Experimental, and Nonlinear Analysis (PDF). Conference Proceedings, Canadian Mathematical Society. 27. Providence, RI: American Mathematical Society, on behalf of the Canadian Mathematical Society. pp. 29-34. ISBN 978-0-8218-2167-1 .
- ^ X. Gourdon, P. Sebah: Numerical evaluation of the Riemann Zeta-function. Numbers, constants and computation.
- ↑ P. Borwein: An efficient algorithm for the Riemann zeta function. In Théra, Michel A. (ed.). Constructive, Experimental, and Nonlinear Analysis (PDF). Conference Proceedings, Canadian Mathematical Society. 27. Providence, RI: American Mathematical Society, on behalf of the Canadian Mathematical Society. pp. 29-34. ISBN 978-0-8218-2167-1 .
- ^ HM Edwards: Riemann's Zeta Function. Dover, ISBN 978-0-486-41740-0 , p. 154.
- ^ HM Edwards: Riemann's Zeta Function. Dover, ISBN 978-0-486-41740-0 , p. 154.
- ↑ Xavier Gourdon and Pascal Sebah: Numerical evaluation of the Riemann Zeta-function , Numbers, constants and computation , (PDF) , p. 6
- ↑ AM Odlyzko and A. Schoenhage: Fast algorithms for multiple evaluations of the Riemann zeta function. Trans. Am. Math. Soc., 309, pp. 797-809 (1988).
- ^ Siegel, CL (1932), About Riemann's bequest on analytical number theory , sources studies on the history of Math. Astron. And phys. Dept. B: Studies 2: 45–80, reprinted in Gesammelte Abhandlungen, Vol. 1. Berlin: Springer-Verlag, 1966.
- ↑ Gram, JP (1903), Note sur les zéros de la fonction ζ (s) de Riemann (PDF), Acta Mathematica, 27: 289-304
- ^ Backlund, RJ (1914), Sur les Zéros de la Fonction ζ (s) de Riemann , CR Acad. Sci. Paris, 158: 1979-1981
- ^ Hutchinson, JI (1925), On the Roots of the Riemann Zeta-Function , Transactions of the American Mathematical Society, 27 (1): 49-60
- ^ Titchmarsh, Edward Charles (1935), The Zeros of the Riemann Zeta-Function , Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, The Royal Society, 151 (873): 234-255
- ^ Titchmarsh, Edward Charles (1936), The Zeros of the Riemann Zeta-Function , Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, The Royal Society, 157 (891): 261-263
- ↑ Turing, Alan M. (1953), Some calculations of the Riemann zeta-function , Proceedings of the London Mathematical Society, Third Series, 3: 99-117
- ^ Lehmer, DH (1956), Extended computation of the Riemann zeta-function , Mathematika. A Journal of Pure and Applied Mathematics, 3 (2): 102-108
- ↑ Rosser, J. Barkley; Yohe, JM; Schoenfeld, Lowell (1969), Rigorous computation and the zeros of the Riemann zeta-function. (including discussion) , Information Processing 68 (Proc. IFIP Congress, Edinburgh, 1968), Vol. 1: Mathematics, Software, Amsterdam: North-Holland, pp. 70-76
- ^ Van de Lune, J .; te Riele, HJJ; Winter, DT (1986), On the zeros of the Riemann zeta function in the critical strip. IV , Mathematics of Computation, 46 (174): 667-681
- ↑ Odlyzko, AM (1987), "On the distribution of spacings between zeros of the zeta function," Mathematics of Computation, 48 (177): 273-308
- ↑ Odlyzko, AM (1992), The 1020-th zero of the Riemann zeta function and 175 million of its neighbors (PDF)
- ↑ Odlyzko, AM (1998), The 1021st zero of the Riemann zeta function (PDF)
- ↑ Gourdon, Xavier (2004): The 1013 first zeros of the Riemann Zeta function, and zeros computation at very large height (PDF)