Berechnungsverfahren zur Riemannschen Zeta-Funktion

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Bei Berechnungsverfahren zur Riemannschen Zeta-Funktion handelt es sich um Algorithmen, die Zahlenwerte für komplexe Werte möglichst genau und zeitschnell ermitteln. Über mehrere Jahrhunderte wurden dabei immer effizientere Verfahren entwickelt. Durch den Einsatz von Computern sind insbesondere seit Beginn des 21. Jahrhunderts sehr umfangreiche Berechnungen möglich.

Die Riemannsche Zetafunktion

[Bearbeiten | Quelltext bearbeiten]
Riemannsche Zetafunktion in der komplexen Ebene, horizontal und vertikal . Eine Reihe weißer Flecken markiert die Nullstellen bei Für eine vollständige Darstellung des Vorschaubildes hier klicken.

Die Riemannsche Zetafunktion ist eine komplexwertige Funktion, die für eine komplexe Zahl mit einem Realteil durch die unendliche Summe

definiert ist.

Eine der wichtigsten Eigenschaften der Riemannschen Zetafunktion ist ihr Zusammenhang mit den Primzahlen. Sie stellt eine Beziehung zwischen komplexer Analysis und Zahlentheorie her (siehe analytische Zahlentheorie) und bildet den Ausgangspunkt der Riemannschen Vermutung. Der folgende Ausdruck, der auf Leonhard Euler (1748) zurückgeht, stellt den Zusammenhang formelhaft dar als

wobei ein unendliches Produkt über alle Primzahlen darstellt. Der Ausdruck folgt unmittelbar aus dem Satz über die Eindeutigkeit der Primzahlzerlegung und der Summationsformel für die geometrische Reihe.

Die Funktion lässt sich über den ursprünglichen Konvergenzbereich der Eulerschen Summen- bzw. Produktformel hinaus auf die gesamte komplexe Ebene – mit Ausnahme von  – eindeutig analytisch fortsetzen. Man erhält eine meromorphe Funktion: Im Punkt besitzt sie einen einfachen Pol.

wobei die Gammafunktion und die Bernoulli-Zahlen sind.[1]

Von großer Wichtigkeit für die Verteilung der Primzahlen ist die genaue Lage der Nullstellen der Zeta-Funktion. Durch numerische Verfahren kann damit in etwa die Riemannsche Vermutung gestützt (jedoch nicht bewiesen) werden.

Die in der zweiten Hälfte des 20. Jahrhunderts aufkommenden leistungsstarken Computer boten neue Möglichkeiten. Bereits im Jahr 1936 hatte der in Oxford wirkende Mathematiker Edward Charles Titchmarsh mit einer Maschine, die ursprünglich für astronomische Berechnungen konstruiert worden war, die ersten 1041 nicht-trivialen Nullstellen der Zeta-Funktion berechnet.[2] Im Jahr 1953 wurden diese Berechnungen von Alan Turing fortgesetzt. Seine Methode wird bis heute benutzt. Erstmals kam dabei ein Computer zum Einsatz.[3][4] In der Forschung rund um die Riemannsche Zeta-Funktion wurden Computer vor allem nun dazu benutzt, die Korrektheit der Riemannsche Vermutung für möglichst viele Nullstellen zu überprüfen. Obwohl es sich bei allen Rechnungen um numerische Verfahren handelt, zeigen diese exakt und nicht nur annähernd, dass sich die untersuchten Nullstellen auf der kritischen Geraden befinden.[5]

Zweifelte lange an der Richtigkeit der Riemannschen Vermutung: Don Zagier
Galt stets als Verfechter der Richtigkeit der Riemannschen Vermutung: Enrico Bombieri

Die Richtigkeit der Riemannschen Vermutung wurde von vielen Mathematikern angezweifelt, unter anderem von Don Zagier. Bei einer Konferenz Anfang der 70er in Bonn spitzte sich eine Diskussion zwischen ihm und Enrico Bombieri schließlich zu und endete in einer Wette: Zagier sagte voraus, es müsse eine Nullstelle der Zeta-Funktion geben, die nicht Riemanns Vorhersage gehorche, Bombieri hielt dagegen. Da beide jedoch nicht davon ausgingen, noch zu Lebzeiten Zeuge eines rigorosen Beweises zu sein, einigten sie sich darauf, dass Zagier verlöre, wenn die ersten 300 Millionen Nullstellen die Vermutung erfüllten. Zu diesem Zeitpunkt waren bereits einige Tausend Nullstellen lokalisiert, doch es gab theoretische Gründe, dass diese auch auf der kritischen Geraden liegen müssten. Wurde die Zahl größer, so wurden diese Gründe schwächer und ab einer gewissen Größenordnung gab es sogar Hinweise, dass die Vermutung falsch sein könnte. Bei den ersten 300 Millionen sei es deswegen laut Zagier „ein Wunder“, falls diese immer noch ausnahmslos auf der kritischen Geraden lägen. Mit der Zeit stieg die Rechenleistung von Computern rasant. Die Größenordnung der Nullstellenzahl aus der Wette geriet damit schon bald in Reichweite. Im Jahr 1979 hatte eine Gruppe aus Amsterdam um Herman te Riele und Richard P. Brent schließlich 200 Millionen Nullstellen überprüft – alle lagen auf der kritischen Geraden. Zagier kommentierte dazu:

„Ich atmete erleichtert auf, denn das war ein Riesenprojekt. Gott sei Dank hatten sie bei 200 Millionen aufgehört. Offensichtlich hätten sie auch bis 300 Millionen gehen können, aber zum Glück hatten sie es nicht getan. Jetzt hatte ich wieder einige Jahre Luft.“

Don Zagier[6]

Jedoch wusste Hendrik Lenstra, ein guter Freund Zagiers, von dessen Wette und machte te Riele darauf aufmerksam, dass Zagier verlöre, wenn die ersten 300 Millionen Nullstellen auf der kritischen Geraden lägen. Also rechnete die Gruppe bis 300 Millionen und Zagier musste seine Wette einlösen. Mit zwei Flaschen Wein aus Bordeaux ging er zu Bombieri und betonte:

„200 Millionen hatten nichts mit meiner Wette zu tun. Das haben die für sich gemacht. Doch die letzten 100 Millionen, diese Rechnung haben sie damals nur wegen meiner Wette gemacht. Für diese zusätzlichen 100 Millionen haben sie ungefähr 1000 Stunden CPU-Zeit verbraucht. Die Kosten für eine Stunde beliefen sich damals auf rund 700 Dollar. Da sie diese Rechnung nur gemacht haben, damit ich meine Wette verliere und die beiden Flaschen Wein bezahlen muss, kann man gut und gerne sagen, dass jede dieser Flaschen rund 350.000 Dollar wert ist. Und das ist wahrlich mehr als die teuerste Flasche Wein, die jemals auf einer Versteigerung unter den Hammer gekommen ist.“

Bis 2005 wurden im Rahmen des sog. ZetaGrid Project durch verteilte Rechner die ersten 10 Billionen Nullstellen überprüft.[8] Alle lagen auf der kritischen Geraden.

Euler-Maclaurin-Summenformel

[Bearbeiten | Quelltext bearbeiten]

Als gute und historisch betrachtet früh verwendete Methode erweist sich die „abgebrochene“ Summenformel, die mit Hilfe der Euler-Maclaurin-Summenformel gewonnen wird. Generell wird zunächst eine beliebige natürliche Zahl festgelegt, für die außerdem gelten sollte. Es gilt dann:[9]

Dabei gilt für das Restglied[10][11]

Bei der (freien) Wahl von ist außerdem zu beachten, dass das Restglied nur auf der Halbebene konvergiert. Daher muss stets gelten. Für größer werdende Werte von verkleinert sich der Fehler demnach rapide.[12]

Durch Anwendung der Funktionalgleichung (eine schnelle Berechnung der Gamma-Funktion und der Exponentialfunktion ist leicht zu implementieren), kann zudem ohne Einschränkung angenommen werden. Hier ist die Summenformel deutlich schneller. Ein Nachteil dieser Methode ist aber, dass sie für wachsende Imaginärteile an Effizienz einbüßt.

Die Nützlichkeit dieser Approximation ist bereits länger bekannt. Beispielsweise ermittelte Leonhard Euler ca. 1734 den Wert von auf etwa 20 Stellen genau, bevor er das Basler Problem, das sich mit dem analytisch „exakten“ Wert von befasste, löste. Diese numerische Auswertung war für ihn die praktische Bestätigung für die Richtigkeit seines exakt ermittelten Wertes.[13]

Weiters fand der dänische Mathematiker Jørgen Pedersen Gram im Jahr 1903 numerische Werte der ersten 15 nicht-trivialen Nullstellen, wobei er die ersten 10 Nullstellen auf sechs und die weiteren 5 auf jeweils eine Stelle nach dem Komma ermittelte.[14]

Als ein Beispiel bietet sich die numerische Annäherung des Zahlenwertes von

an. Für eine sehr gute Approximation reichen die Werte und vollkommen aus. Einsetzen ergibt:

Die folgende Tabelle zeigt die numerische Auswertung dieser Rechnung.

Term Numerischer Wert

Diese mit wenig Aufwand gewonnene Approximation stimmt mit dem tatsächlichen Wert

bereits in sechs Dezimalstellen (gerundet) nach dem Komma überein.[15] Zur Unterstreichung der Effizienz sei bemerkt: Hätte Euler stattdessen einfach nur auch für den Wert des Terms aufsummiert, so wären für die gleiche Approximationsgüte zirka eine Million Summanden nötig gewesen. Geht man davon aus, dass Euler per Hand pro Term durchschnittlich 20 Sekunden Rechenzeit benötigte, hätte dies zirka acht Monate ununterbrochenes Rechnen bedeutet.

Analog kann der Dezimalwert von angenähert werden. Hier reicht die Wahl von und .

Term Numerischer Wert

Auch dieser Wert stimmt auf sechs Dezimalstellen genau.[15]

Alternierende Summen

[Bearbeiten | Quelltext bearbeiten]

Ein Verfahren mittels abgebrochener alternierender Reihen stammt von Borwein.[16] Basierend auf konvergenzbeschleunigenden Transformationen angewandt auf die Reihe

erhält man die leicht zu implementierende Formel

wobei ebenfalls von der Wahl von abhängt. Diese ist für alle Werte verwendbar. Der Fehler kann mit für abgeschätzt werden durch

Für ergibt sich hingegen[17][18]

Jedoch gilt auch hier, dass das Verfahren für größer werdende Imaginärteile auf der positiven reellen Seite an Effizienz verliert.

Berechnung auf der kritischen Geraden

[Bearbeiten | Quelltext bearbeiten]

Riemann-Siegel-Formel

[Bearbeiten | Quelltext bearbeiten]

Viele Methoden verlieren an Präzision, wenn der Imaginärteil des Arguments sehr groß gewählt wird, was bei der Nullstellensuche entlang der kritischen Geraden problematisch ist. Daher greift man hier auf andere Methoden zurück, eine davon ist die Riemann-Siegel-Formel.

Für

folgt mit der Funktionalgleichung der Zeta-Funktion schnell , also , d. h., bildet entlang der kritischen Geraden nur auf Werte des Einheitskreises ab. Es kann also eine stetige reellwertige Funktion implizit durch die Gleichung

definieren werden, wobei . Diese wird auch als Riemann-Siegelsche Theta-Funktion bezeichnet. Damit lässt sich schließlich die Riemann-Siegelsche -Funktion definieren:

Man zeigt leicht , d. h. ist sogar eine reellwertige Funktion , wird aber genau dann Null an der Stelle , falls eine nicht-triviale Nullstelle von ist. Es sei hinreichend groß gewählt. Für Werte folgt nun mit der Approximate functional equation

Der Fehlerterm kann durch eine asymptotische Entwicklung[19]

beliebig verbessert werden. Exakte obere Grenzen für ergeben sich für über

Die explizit bestimmbaren Funktionen werden mit wachsendem recht kompliziert, die ersten sind gegeben durch[20]

Insgesamt ergibt sich für eine ziemlich präzise Berechnung ein Aufwand von Rechenoperationen in Form von Termberechnungen mit anschließender Addition. Um Nullstellen zu finden, reicht es schon aus, Bereiche mit Vorzeichenwechsel zu identifizieren (und für deren präzise Bestimmung dann eine Intervallschachtelung durchzuführen).

Ist im Bereich , so reicht die Wahl für eine Präzision mit einem Fehler , wobei lediglich Summanden benötigt werden. Für eine ähnliche Genauigkeit benötigen weniger spezielle Verfahren (wie die alternierende Summe) ca. Summanden.[21]

Verfahren von Odlyzko und Schönhage

[Bearbeiten | Quelltext bearbeiten]

Im Jahr 1988 entwickelten A. M. Odlyzko und A. Schönhage ein sehr schnelles Verfahren, um Werte der Riemannschen Zeta-Funktion auf der kritischen Geraden zu bestimmen. Dieses basiert auf den Ideen der Riemann-Siegel-Formel, benötigt jedoch nur noch anstatt Rechenoperationen, wobei beliebig klein gewählt werden kann. Die Verfeinerung der Rechentechniken basiert auf der schnellen Fouriertransformation.[22]

Fortschritte bei der Berechnung von Nullstellen

[Bearbeiten | Quelltext bearbeiten]
Jahr Anzahl der Nullstellen Autor
1859? 3 B. Riemann benutzte die Riemann-Siegel-Formel (unveröffentlicht, aber aufgezeichnet[23]).
1903 15 Jørgen Pedersen Gram benutzte die Euler–Maclaurin-Summenformel und entdeckte das Gramsche Gesetz.[24] Er zeigte, dass alle 10 Nullstellen (mit Imaginärteil von maximal 50) auf der kritischen Linie mit Realteil 1/2 liegen, indem er die Summe der inversen zehnten Potenzen der gefundenen Wurzeln berechnete.
1914 79 (γn ≤ 200) R. J. Backlund verbesserte die bisherige Methodik, um festzustellen, dass alle bisher gefundenen Nullstellen auf der kritischen Geraden liegen.[25]
1925 138 (γn ≤ 300) J. I. Hutchinson deckte das Scheitern des Gramschen Gesetzes am Punkt g126 auf.[26]
1935 195 E. C. Titchmarsh machte sich die kürzlich wiederentdeckte Riemann–Siegel-Formel zu Nutze. Diese ist schneller als die Euler-Maclaurin-Summenformel: Sie benötigt in etwa O(T3/2+ε) um Nullstellen mit Imiginärteil kleiner als T aufzuspüren, während letztere in etwa O(T2+ε) Schritte braucht.[27]
1936 1041 E. C. Titchmarsh und L. J. Comrie gelten als die Letzten, die Nullstellen per Hand berechneten.[28]
1953 1104 A. M. Turing fand einen effizienteren Weg, um zu überprüfen, ob bis zu einem gewissen Punkt alle gefundenen Nullstellen auch wirklich auf der Geraden liegen, indem er überprüfte, dass die Funktion Z(t) das richtige Vorzeichen an aufeinanderfolgenden Gramschen Punkten hat (und dass S(T) den Durchschnittswert 0 hat). Dies benötigte quasi keine neue Arbeit, da die Vorzeichen von Z(t) bereits an den Gramschen Punkten aus vergangenen Nullstellensuchen bekannt waren. Diese Methode wird bis heute benutzt. Erstmals kam ein Computer zum Einsatz.[29]
1956 15.000 Derrick Henry Lehmer entdeckte ein paar Fälle, in welchen Nullstellen „gerade so“ auf der Geraden liegen: zwei Nullstellen liegen dabei so nahe beieinander, dass es ungewöhnlich schwer ist den Vorzeichenwechsel zu erkennen. Dies nennt man heute „Lehmersches Phänomen“, und tritt das erste Mal bei den Nullstellen mit Imaginärteilen 7005.063 und 7005.101 auf, die sich lediglich um .04 unterscheiden, während in dieser Region ein durchschnittlicher Abstand von 1 erwartet wird.[30]
1956 25.000 D. H. Lehmer
1958 35.337 N. A. Meller
1966 250.000 R. S. Lehman
1968 3.500.000 Rosser, J. M. Yohe und Lowell Schoenfeld formulierten die Rossersche Regel.[31]
1977 40.000.000 R. P. Brent
1979 81.000.001 R. P. Brent
1982 200.000.001 R. P. Brent, J. van de Lune, H. J. J. te Riele, D. T. Winter
1983 300.000.001 J. van de Lune, H. J. J. te Riele
1986 500.000.001 van de Lune, te Riele und Winter gaben statistische Daten über die Nullstellen und verschiedene Graphen der Funktion Z(t) an Stellen mit ungewöhnlichem Verhalten.[32]
1987 Einige mit Höhe der Größenordnung (~1012) A. M. Odlyzko berechnete einige wenige Nullstellen mit Imaginärteilen um 1012 um Montgomery's pair correlation conjecture numerisch zu prüfen.[33]
1992 Einige mit Höhe der Größenordnung (~1020) A. M. Odlyzko berechnete ca. 175 Millionen Nullstellen mit Imaginärteilen um 1020 und diskutierte die Ergebnisse eingehend.[34]
1998 10.000 mit Höhe der Größenordnung (~1021) A. M. Odlyzko berechnete einige Nullstellen mit Imaginärteilen um 1021[35]
2001 10.000.000.000 J. van de Lune (unveröffentlicht)
2004 900.000.000.000 S. Wedeniwski (ZetaGrid Projekt)
2004 10.000.000.000.000 und ein paar weitere im Höhenbereich (bis zu ~1024) X. Gourdon and Patrick Demichel verwenden das Verfahren von Odlyzko und Schönhage. Sie überprüfen auch zwei Milliarden Nullstellen in den Bereichen 1013, 1014 …, 1024.[36]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Bei der hier verwendeten Definition der Bernoulli-Zahlen gilt:
  2. Marcus du Sautoy: Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik. 5. Auflage. Beck, München 2006, ISBN 978-3-423-34299-5, S. 234
  3. Turing, Alan M. (1953), Some calculations of the Riemann zeta-function, Proceedings of the London Mathematical Society, Third Series, 3: 99–117
  4. Marcus du Sautoy: Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik. 5. Auflage. Beck, München 2006, ISBN 978-3-423-34299-5, S. 238
  5. Calculations relating to the zeros. Kapitel 15. In: Titchmarsh: The Theory of the Riemann Zeta function.
  6. Marcus du Sautoy: Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik. 5. Auflage. Beck, München 2006, ISBN 978-3-423-34299-5, S. 268.
  7. Marcus du Sautoy: Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik. 5. Auflage. Beck, München 2006, ISBN 978-3-423-34299-5, S. 269.
  8. Ed Pegg Jr. «Ten Trillion Zeta Zeros»
  9. H. M. Edwards: Riemann’s Zeta Function. Dover, ISBN 978-0-486-41740-0, S. 114.
  10. R. Backlund: Uber die Nullstellen der Riemannschen Zetafunktion. Dissertation, Helsinki 1916.
  11. H. M. Edwards: Riemann’s Zeta Function. Dover, ISBN 978-0-486-41740-0, S. 115.
  12. H. M. Edwards: Riemann’s Zeta Function. Dover, ISBN 978-0-486-41740-0, S. 114.
  13. Julian Havil: Gamma. Springer-Verlag, Berlin et al. 2007, ISBN 978-3-540-48495-0, S. 50.
  14. J. P. Gram: Sur les Zéros de la Fonction de Riemann. Acta Math. 27, 289–304 (1903).
  15. a b H. M. Edwards: Riemann’s Zeta Function. Dover, ISBN 978-0-486-41740-0, S. 116.
  16. 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.
  17. X. Gourdon, P. Sebah: Numerical evaluation of the Riemann Zeta-function. Numbers, constants and computation.
  18. 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.
  19. H. M. Edwards: Riemann’s Zeta Function. Dover, ISBN 978-0-486-41740-0, S. 154.
  20. H. M. Edwards: Riemann’s Zeta Function. Dover, ISBN 978-0-486-41740-0, S. 154.
  21. Xavier Gourdon and Pascal Sebah: Numerical evaluation of the Riemann Zeta-function, Numbers, constants and computation, (PDF), S. 6
  22. A. M. Odlyzko and A. Schoenhage: Fast algorithms for multiple evaluations of the Riemann zeta function. Trans. Am. Math. Soc., 309 (1988), S. 797–809.
  23. 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, Neu gedruckt in Gesammelte Abhandlungen, Vol. 1. Berlin: Springer-Verlag, 1966.
  24. Gram, J. P. (1903), Note sur les zéros de la fonction ζ(s) de Riemann (PDF), Acta Mathematica, 27: 289–304
  25. Backlund, R. J. (1914), Sur les Zéros de la Fonction ζ(s) de Riemann, C. R. Acad. Sci. Paris, 158: 1979–1981
  26. Hutchinson, J. I. (1925), On the Roots of the Riemann Zeta-Function, Transactions of the American Mathematical Society, 27 (1): 49–60
  27. 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
  28. 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
  29. Turing, Alan M. (1953), Some calculations of the Riemann zeta-function, Proceedings of the London Mathematical Society, Third Series, 3: 99–117
  30. Lehmer, D. H. (1956), Extended computation of the Riemann zeta-function, Mathematika. A Journal of Pure and Applied Mathematics, 3 (2): 102–108
  31. Rosser, J. Barkley; Yohe, J. M.; Schoenfeld, Lowell (1969), Rigorous computation and the zeros of the Riemann zeta-function. (einschließlich Diskussion), Information Processing 68 (Proc. IFIP Congress, Edinburgh, 1968), Vol. 1: Mathematics, Software, Amsterdam: North-Holland, pp. 70–76
  32. van de Lune, J.; te Riele, H. J. J.; Winter, D. T. (1986), On the zeros of the Riemann zeta function in the critical strip. IV, Mathematics of Computation, 46 (174): 667–681
  33. Odlyzko, A. M. (1987), "On the distribution of spacings between zeros of the zeta function", Mathematics of Computation, 48 (177): 273–308
  34. Odlyzko, A. M. (1992), The 1020-th zero of the Riemann zeta function and 175 million of its neighbors (PDF)
  35. Odlyzko, A. M. (1998), The 1021st zero of the Riemann zeta function (PDF)
  36. Gourdon, Xavier (2004): The 1013 first zeros of the Riemann Zeta function, and zeros computation at very large height (PDF)