Berechnungsverfahren zur Riemannschen Zeta-Funktion
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.
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.
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.
Geschichte
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]
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.“
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.
Verfahren
Euler-Maclaurin-Summenformel
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]
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]
Beispiele
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
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
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
Riemann-Siegel-Formel
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
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]
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
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]
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]
↑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
↑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: 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
↑Calculations relating to the zeros. Kapitel 15. In: Titchmarsh: The Theory of the Riemann Zeta function.
↑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.
↑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.
↑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.
↑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.
↑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.
↑Gram, J. P. (1903), Note sur les zéros de la fonction ζ(s) de Riemann (PDF), Acta Mathematica, 27: 289–304
↑Backlund, R. J. (1914), Sur les Zéros de la Fonction ζ(s) de Riemann, C. R. Acad. Sci. Paris, 158: 1979–1981
↑Hutchinson, J. I. (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, D. H. (1956), Extended computation of the Riemann zeta-function, Mathematika. A Journal of Pure and Applied Mathematics, 3 (2): 102–108
↑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
↑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
↑Odlyzko, A. M. (1987), "On the distribution of spacings between zeros of the zeta function", Mathematics of Computation, 48 (177): 273–308
↑Odlyzko, A. M. (1992), The 1020-th zero of the Riemann zeta function and 175 million of its neighbors(PDF)
↑Odlyzko, A. M. (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)