Die Originalversion von diese Geschichte erschien in Quanta-Magazin.
Dieses Jahr bisher Quanten hat drei große Fortschritte in der Ramsey-Theorie aufgezeichnet, der Untersuchung, wie man die Entstehung mathematischer Muster vermeiden kann. Der erstes Ergebnis Setzen Sie eine neue Obergrenze dafür, wie groß eine Menge von ganzen Zahlen sein kann, ohne drei gleichmäßig verteilte Zahlen wie 2, 4, 6 oder 21, 31, 41 zu enthalten. Der zweite Und dritte Ebenso werden neue Grenzen für die Größe von Netzwerken ohne Cluster von Punkten gesetzt, die entweder alle miteinander verbunden oder alle voneinander isoliert sind.
Die Beweise befassen sich damit, was passiert, wenn die beteiligten Zahlen unendlich groß werden. Paradoxerweise kann dies manchmal einfacher sein, als mit lästigen realen Größen umzugehen.
Betrachten Sie zum Beispiel zwei Fragen zu einem Bruch mit einem wirklich großen Nenner. Sie fragen sich vielleicht, was die Dezimalentwicklung von beispielsweise 1/42503312127361 ist. Oder Sie könnten fragen, ob diese Zahl mit zunehmendem Nenner näher an Null herankommt. Bei der ersten Frage handelt es sich um eine spezifische Frage zu einer realen Größe, und sie ist schwieriger zu berechnen als die zweite, bei der gefragt wird, wie die Größe 1/N wird sich „asymptotisch“ ändern als N wächst. (Es kommt immer näher an 0.)
„Dies ist ein Problem, das die gesamte Ramsey-Theorie plagt“, sagte er William Gasarch, ein Informatiker an der University of Maryland. „Die Ramsey-Theorie ist dafür bekannt, dass sie asymptotisch sehr schöne Ergebnisse liefert.“ Aber die Analyse von Zahlen, die kleiner als unendlich sind, erfordert einen ganz anderen mathematischen Werkzeugkasten.
Gasarch hat Fragen der Ramsey-Theorie untersucht, bei denen es um endliche Zahlen geht, die zu groß sind, als dass das Problem mit roher Gewalt gelöst werden könnte. In einem Projekt nahm er sich der endlichen Version des ersten Durchbruchs dieses Jahres an – einem Februar-Artikel von Zander Kelleyein Doktorand an der University of Illinois, Urbana-Champaign, und Raghu Meka der University of California, Los Angeles. Kelley und Meka haben eine neue Obergrenze dafür gefunden, wie viele ganze Zahlen zwischen 1 und liegen N Sie können sie in einen Satz einteilen und dabei Drei-Term-Progressionen oder Muster gleichmäßig verteilter Zahlen vermeiden.
Obwohl das Ergebnis von Kelley und Meka gilt, selbst wenn N relativ klein ist, ergibt sich in diesem Fall keine besonders nützliche Grenze. Für sehr kleine Werte von N, bleiben Sie besser bei sehr einfachen Methoden. Wenn N ist beispielsweise 5, schauen Sie sich einfach alle möglichen Zahlenmengen zwischen 1 und an Nund wählen Sie den größten progressionsfreien aus: 1, 2, 4, 5.
Doch die Zahl der unterschiedlichen Antwortmöglichkeiten wächst sehr schnell und macht es zu schwierig, eine so einfache Strategie anzuwenden. Es gibt mehr als 1 Million Sätze, die aus Zahlen zwischen 1 und 20 bestehen. Es gibt über 1060 unter Verwendung von Zahlen zwischen 1 und 200. Das Finden des besten progressionsfreien Satzes für diese Fälle erfordert eine beträchtliche Dosis Rechenleistung, selbst mit effizienzsteigernden Strategien. „Man muss in der Lage sein, viel Leistung aus den Dingen herauszuholen“, sagte er James Glenn, Informatiker an der Yale University. Im Jahr 2008 haben Gasarch, Glenn und Clyde Kruskal der University of Maryland habe ein Programm geschrieben um die größten progressionsfreien Sätze bis zu einem zu finden N von 187. (Vorherige Arbeiten hatten die Antworten auf 150 und auch auf 157 gebracht.) Trotz einer Liste von Tricks habe es Monate gedauert, bis ihr Programm fertig sei, sagte Glenn.