Das erstaunliche Verhalten rekursiver Sequenzen | Quanta-Magazin

In der Mathematik können einfache Regeln Universen voller Komplexität und Schönheit erschließen. Nehmen Sie die berühmte Fibonacci-Folge, die wie folgt definiert ist: Sie beginnt mit 1 und 1, und jede nachfolgende Zahl ist die Summe der beiden vorherigen. Die ersten paar Zahlen sind:

1, 1, 2, 3, 5, 8, 13, 21, 34 …

Ja, einfach, aber dieses bescheidene Rezept führt zu einem Muster von weitreichender Bedeutung, das in das Gewebe der natürlichen Welt eingewoben zu sein scheint. Es ist in den Wirbeln von Nautilusmuscheln, den Knochen unserer Finger und der Anordnung der Blätter auf Baumzweigen zu sehen. Seine mathematische Reichweite erstreckt sich unter anderem auf Geometrie, Algebra und Wahrscheinlichkeit. Acht Jahrhunderte nach der Einführung der Folge im Westen – indische Mathematiker untersuchten sie lange vor Fibonacci – erregen die Zahlen weiterhin das Interesse von Forschern, ein Beweis dafür, wie viel mathematische Tiefe selbst der elementarsten Zahlenfolge zugrunde liegen kann.

In der Fibonacci-Folge baut jeder Begriff auf den vorhergehenden auf. Solche rekursiven Sequenzen können ein breites Spektrum an Verhaltensweisen aufweisen, von denen einige wunderbar kontraintuitiv sind. Nehmen wir zum Beispiel eine merkwürdige Familie von Folgen, die erstmals in den 1980er Jahren von dem amerikanischen Mathematiker beschrieben wurde Michael Somos.

Wie die Fibonacci-Folge beginnt auch eine Somos-Folge mit einer Reihe von Einsen. Ein Somos-k Die Sequenz beginnt mit k von ihnen. Jede neue Amtszeit eines Somos-k Die Reihenfolge wird definiert, indem vorherige Terme gepaart werden, jedes Paar miteinander multipliziert wird, die Paare addiert werden und dann durch den Term dividiert wird k Positionen in der Reihenfolge zurück.

Die Sequenzen sind nicht sehr interessant, wenn k gleich 1, 2 oder 3 – sie sind nur eine Reihe sich wiederholender Einsen. Aber für k = 4, 5, 6 oder 7 haben die Sequenzen eine seltsame Eigenschaft. Auch wenn viele Divisionen erforderlich sind, tauchen keine Brüche auf.

„Normalerweise haben wir ein solches Phänomen nicht“, sagte Somos. „Es ist eine täuschend einfache Wiederholung, ähnlich wie bei Fibonacci. Aber hinter dieser Einfachheit steckt viel.“

Andere Mathematiker entdecken weiterhin verblüffende Verbindungen zwischen Somos-Folgen und scheinbar nicht zusammenhängenden Bereichen der Mathematik. In einem im Juli veröffentlichten Artikel werden sie verwendet Lösungen konstruieren zu einem System von Differentialgleichungen, mit denen alles modelliert wird, von Räuber-Beute-Interaktionen bis hin zu Wellen, die sich in hochenergetischen Plasmen ausbreiten. Sie werden auch zur Untersuchung der Struktur sogenannter mathematischer Objekte verwendet Clusteralgebren und verbunden sind elliptische Kurven – die der Schlüssel zur Lösung von Fermats letztem Satz waren.

Janice Malouf, ein Doktorand an der University of Illinois, veröffentlichte den ersten Beweis für Somos-4- und Somos-5-Sequenzen sind integral (was bedeutet, dass alle ihre Terme ganze Zahlen sind) im Jahr 1992. Andere Beweise des gleichen Ergebnisses durch verschiedene Mathematiker erschienen ungefähr zur gleichen Zeit, zusammen mit Beweisen, dass die Somos-6- und Somos-7-Folgen ganzzahlig sind.

Diese seltsame Eigenschaft der Somos-Folgen verblüffte die Mathematiker. „Somos-Sequenzen faszinierten mich, sobald ich davon erfuhr“, sagte er Jakob Propp, Professor für Mathematik an der University of Massachusetts, Lowell. „Die Tatsache, dass Somos-4 bis Somos-7 immer ganze Zahlen liefern, egal wie weit man hinausgeht, erschien einem wie ein Wunder, wenn man die Dinge aus einer naiven Perspektive betrachtete. Daher war eine andere Perspektive erforderlich.“

Eine neue Perspektive fand Propp Anfang der 2000er Jahre, als er und seine Kollegen entdeckten, dass die Zahlen in der Somos-4-Sequenz tatsächlich etwas zählen. Die Terme in der Sequenz entsprechen Strukturen, die in bestimmten Diagrammen vorkommen. Bei einigen Diagrammen ist es möglich, Scheitelpunkte (Punkte) mit Kanten (Linien) zu paaren, sodass jeder Scheitelpunkt mit genau einem anderen Scheitelpunkt verbunden ist – es gibt keine ungepaarten Scheitelpunkte und kein Scheitelpunkt ist mit mehr als einer Kante verbunden. Die Terme in der Somos-4-Folge zählen die Anzahl verschiedener perfekter Übereinstimmungen für eine bestimmte Folge von Graphen.

Die Entdeckung bot nicht nur eine neue Perspektive auf Somos-Sequenzen, sondern führte auch neue Wege ein, über Graphtransformationen nachzudenken und sie zu analysieren. Propp und seine Schüler feierten das Ergebnis, indem sie es auf einer Bühne präsentierten T-Shirt.

„Für mich besteht ein großer Teil des Reizes der Mathematik darin, dass man auf verschiedenen Wegen zum gleichen Ziel gelangt und es scheint, als ob etwas Wunderbares oder Tiefgreifendes vor sich geht“, sagte Propp. „Das Coole an diesen Sequenzen ist, dass es verschiedene Gesichtspunkte gibt, die erklären, warum man ganze Zahlen erhält. Da gibt es verborgene Tiefen.“

Die Geschichte ändert sich für Somos-Sequenzen mit höherer Nummer. Die ersten 18 Terme von Somos-8 sind ganze Zahlen, aber der 19. Term ist ein Bruch. Jede darauffolgende Somos-Folge enthält auch Bruchwerte.

Ein anderer Sequenztyp, der in den 1970er Jahren vom deutschen Mathematiker Fritz Göbel entwickelt wurde, ist ein interessanter Kontrapunkt zu den Somos-Sequenzen. Der nDer vierte Term der Göbel-Folge ist definiert als die Summe der Quadrate aller vorherigen Terme plus 1 dividiert durch n. Wie die Somos-Folgen beinhaltet auch die Göbel-Folge eine Division, sodass wir davon ausgehen können, dass Terme keine ganzen Zahlen bleiben. Aber für eine Weile – während die Sequenz enorm wird – scheinen sie es zu sein.

Der 10. Term in der Göbel-Folge beträgt etwa 1.5 Millionen, der 11. 267 etwa eine Milliarde. Der 43. Term ist viel zu groß, um ihn zu berechnen – er hat etwa 178 Milliarden Stellen. Doch 1975 kam der niederländische Mathematiker Hendrik Lenstra zeigte, dass dieser 42. Term im Gegensatz zu den ersten 43 Termen keine ganze Zahl ist.

Göbel-Folgen können verallgemeinert werden, indem die Quadrate in der Summe durch Kubikzahlen, vierte Potenzen oder noch höhere Exponenten ersetzt werden. (Nach dieser Konvention wird seine ursprüngliche Sequenz als 2-Göbel-Sequenz bezeichnet.) Diese Sequenzen zeigen auch einen überraschenden Trend, mit einer längeren Strecke ganzzahliger Terme zu beginnen. 1988 Henry Ibstedt zeigte dass die ersten 89 Terme der 3-Göbel-Folge (die Würfel anstelle von Quadraten verwendet) ganze Zahlen sind, der 90. jedoch nicht. Nachfolgende Untersuchungen zu anderen Göbel-Sequenzen ergaben sogar noch längere Abschnitte. Die 31-Göbel-Folge beispielsweise beginnt mit satten 1,077 ganzzahligen Termen.

Im Juli haben die Mathematiker der Kyushu-Universität Rinnosuke Matsuhira, Toshiki Matsusaka und Koki Tsuchida teilte ein Papier zeige das für a k-Göbel-Sequenz, egal welche Wahl k, die ersten 19 Terme der Folge sind immer ganze Zahlen. Inspiriert wurden sie von einem japanischen Manga namens Seisū-tan, was übersetzt „Die Geschichte der ganzen Zahlen“ bedeutet. A Rahmen im Comic bat die Leser, den minimal möglichen Wert von herauszufinden N_k, der Punkt, an dem a k-Göbel-Sequenz produziert keine ganzzahligen Terme mehr. Die drei Mathematiker machten sich daran, die Frage zu beantworten. „Das unerwartete Fortbestehen ganzer Zahlen über einen so langen Zeitraum widerspricht unserer Intuition“, sagte Matsusaka. „Wenn Phänomene entgegen der Intuition auftreten, ist meiner Meinung nach immer Schönheit vorhanden.“

Sie fanden ein Muster sich wiederholenden Verhaltens als k erhöht sich. Indem sie sich auf eine endliche Anzahl sich wiederholender Fälle konzentrierten, machten sie die Berechnung nachvollziehbar und konnten den Beweis vervollständigen.

Ein genauerer Blick auf die Sequenz N_k enthüllt eine weitere Überraschung: N_k ist viel häufiger eine Primzahl, als man erwarten würde, wenn es rein zufällig wäre. "Mit dem k„Es ist nicht nur bemerkenswert, dass es sich bei der Göbel-Folge um ganze Zahlen handelt“, sagte er Richard Green, ein Mathematiker an der University of Colorado. „Bemerkenswert ist, dass die Primzahlen so oft auftauchen. Das lässt es so aussehen, als ob etwas Tieferes im Gange wäre.“

Das neue Papier liefert jedoch einen Beweis dafür N_k ist immer mindestens 19, es ist nicht bekannt, ob es immer endlich ist oder ob es ein gibt k für die die Folge unendlich viele ganze Zahlen enthält. „N_k verhält sich mysteriös. … Es besteht ein grundlegender Wunsch, das zugrunde liegende Muster zu verstehen“, sagte Matsusaka. „Es ähnelt vielleicht der Freude, die ich als Kind empfand, als ich die von Lehrern gestellten Rätsel löste. Auch heute noch sind diese Gefühle von damals in mir spürbar.“

Wie viel führt eine Reihe von Umfragen durch, um unser Publikum besser zu bedienen. Nimm unser Leserbefragung Mathematik und Sie nehmen an der kostenlosen Verlosung teil Wie viel Merch.