Ein wichtiger Durchbruch bei der Lösung der 60 Jahre alten Hypothese wirft ein Licht darauf, wie mit dem Wachstum zufälliger Systeme Ordnung in ihnen entsteht
Ein Team von Mathematikern und Informatikern demonstrierte schließlich Fortschritte bei der Lösung einer einfachen Aufgabe, die Forscher seit fast sechs Jahrzehnten plagte.
Diese Aufgabe, die 1960 von den Mathematikern Pal Erdös und Richard Rado gestellt wurde, betrifft die Häufigkeit, mit der man erwarten kann, dass Muster, die einer Sonnenblume ähneln, in großen Ansätzen von Objekten auftreten - beispielsweise in einer großen Anzahl von Punkten, die auf einer Ebene verstreut sind. Obwohl das
neue Ergebnis die Erdös- und Rado-Hypothese nicht vollständig löst, fördert es das Verständnis der Mathematiker für das Auftreten überraschend komplexer Strukturen in zufälligen Clustern. Zu diesem Zweck wurde die Aufgabe in Form einer Computerfunktion umformuliert, wobei das wachsende Verhältnis zwischen theoretischer Informatik und reiner Mathematik genutzt wurde.
„In dieser Arbeit manifestiert sich eine mathematische Idee auf eine neue Art und Weise, die zur Hauptidee unserer Zeit werden wird. Das Ergebnis selbst ist erstaunlich “, sagte
Gil Kalai von der Hebrew University in Jerusalem.
Die Sonnenblumenhypothese bezieht sich auf Mengen oder Mengen von Objekten. Es ist am einfachsten, sich das Beispiel einer Punktmenge auf der xy-Ebene vorzustellen. Wählen Sie zunächst eine feste Anzahl von Punkten aus, die in jedem Satz enthalten sein sollen. Zeichnen Sie dann Zufallsschleifen, sodass jede Schleife oder jeder Satz eine ausgewählte Anzahl von Punkten enthält. Die Schleifen können sich kreuzen und einige Punkte können in mehrere Sätze fallen, ähnlich einem Venn-Diagramm.
Wenn Sie viele Schleifen mit einer großen Anzahl von Punkten zeichnen, überschneiden sich die meisten und ähneln den Feinheiten von Reben. Erdös und Rado sagten jedoch voraus, dass sich auch eine verfeinerte Struktur ergeben würde: Drei oder mehr Mengen würden sich überschneiden, wobei dieselbe Teilmenge von Punkten an der Überschneidung verbleiben würde, während keine dieser Mengen andere Mengen überschneiden würde.
Wenn Sie diese gemeinsame Untergruppe von Punkten entfernen, befinden sich die drei Gruppen um die Leere und sind vollständig voneinander getrennt - wie Blütenblätter um die dunkle Mitte der Sonnenblume. Die einfachste Sonnenblume besteht aus drei Gruppen, die sich nicht mit anderen überschneiden. Solche Inseln werden disjunkte Mengen genannt.
Erdös und Rado schlugen vor, dass mit zunehmender Anzahl von Schleifen solche Sonnenblumen zwangsläufig entweder in Form von nicht zusammenhängenden Mengen oder in Form von Mengen auftreten, die auf die angegebene Weise übereinandergelegt werden. Diese Sonnenblumenhypothese ist Teil eines allgemeineren Gebiets der Mathematik,
der Ramsey-Theorie, die untersucht, wie Ordnung in ihnen mit zunehmender Größe zufälliger Systeme zu erscheinen beginnt.
"Wenn Sie ein ausreichend großes mathematisches Objekt haben, muss eine Struktur darin versteckt sein", sagte
Shachar Lovet von der University of California in San Diego, Mitautor einer neuen Arbeit, an der auch
Ryan Alweis von der Princeton University und Keven Wu von der Peking University gearbeitet haben und
Jiapeng Zhang von der Harvard University.
Erdös und Rado wollten genau wissen, wie viele Sets und welche Größe benötigt werden, um eine Sonnenblume zu garantieren. Sie haben den ersten bescheidenen Schritt zur Lösung des Problems unternommen, indem sie den Parameter w definiert haben, der die Anzahl der Punkte in jedem der Sätze angibt. Dann haben sie bewiesen, dass es ungefähr w
w Sätze von Größe w braucht, um sicherzustellen, dass eine Sonnenblume, die aus drei Sätzen besteht, garantiert in ihnen erscheint. Wenn Sie also Sätze mit 100 Punkten verwenden möchten, benötigen Sie 100 bis
100 Sätze, um das Erscheinungsbild einer Sonnenblume zu gewährleisten.
Gleichzeitig schlugen Erdös und Rado vor, dass die Anzahl der Sätze, die eine Sonnenblume garantieren, viel geringer ist als w
w - und eher einer Konstante in w (zum Beispiel 3
w oder 80
w oder 5 000 000
w ). Sie konnten jedoch keinen Weg finden, ihre Vermutung zu beweisen.
"Sie sagten, dass die Aufgabe äußerst einfach zu sein schien, und waren überrascht, dass sie darin keine Fortschritte erzielen konnten", sagte Alveys.
Und sie waren nicht alleine. In der Zeit von ihrem ersten Ergebnis und dieser neuen Arbeit, die 60 Jahre später erschien, machten nur zwei Mathematiker zumindest einige Fortschritte in dieser Frage - und dann machten sie schrittweise einen Schritt 1997 und den
zweiten in diesem Jahr .
"Jeder hat bereits alle Ideen ausprobiert, mit denen sich die Menschen wohl fühlen", sagte
Anup Rao von der University of Washington, der
zusätzliche Arbeiten veröffentlichte, die die im neuen Ergebnis erzielten Methoden vereinfachten. "Und niemand konnte die Basislinie von Erds und Rado verbessern."
Aber die neuen Beweise machten einen großen Durchbruch.
Vier Forscher, darunter Mathematiker und Informatiker, konnten dies tun, indem sie die Aufgabe in zwei verschiedene Szenarien aufteilten. In der ersten, einfacheren Version wurde untersucht, was passieren würde, wenn sich die Sets erheblich überschneiden, was es viel einfacher macht zu verstehen, wann eine Sonnenblume dort erscheinen sollte.
"Wenn Sie eine Menge von Elementen haben, die zu einer größeren Menge von Mengen gehören, können Sie diese Struktur verwenden", sagte Lovet, um nach einer Sonnenblume zu suchen.
Zuerst fragten sich die Forscher, ob es eine Menge von Punkten gibt, die zu einem ausreichend großen Teil aller Mengen im System gehören. Nachdem sie auf der Suche nach einer Sonnenblume solche Punkte gefunden hatten, beschränkten sie sich auf den Teil der Mengen, die diese Punktmenge enthielten. Dann verhielten sie sich genauso und verfeinerten die Suche, einschließlich immer weniger Systemmengen, die immer mehr gemeinsame Punkte haben. Dieser Schnitt ging weiter, bis sie ihre Sonnenblume fanden.
In einem zweiten, komplexeren Szenario analysieren sie, was passieren wird, wenn sich die Mengen nicht stark überschneiden. In diesem Fall ist der wahrscheinlichste Weg, eine Sonnenblume zu bekommen, die Einnahme von drei nicht zusammenhängenden Sätzen. Es ist jedoch nicht einfach zu beweisen, dass sich drei separate Mengen in sich geringfügig überschneidenden Mengen verstecken.
Hier kommt die Informatik ins Spiel. Zwei Koautoren, Lovet und Zhang, haben seit mehreren Jahren versucht, das Sonnenblumenproblem mit denselben Tools zu analysieren, mit denen Informatiker die booleschen Funktionen untersuchen. Diese Funktionen führen Operationen an einer Folge von Bits - Einsen und Nullen - aus und erzeugen am Ende ein einzelnes Bit, je nachdem, ob eine Rechenanweisung wahr oder falsch ist. Beispielsweise kann eine Boolesche Funktion so programmiert werden, dass sie 1 zurückgibt, wenn mindestens eines der Eingabebits 1 ist, und 0, wenn keines der Eingabebits 1 ist.
Vor drei Jahren erkannten Lovet und Zhang, dass dieselbe Frage gestellt werden könnte, ob es drei disjunkte Mengen unter einer Menge von Mengen gibt, die sich nicht stark überschneiden. Weisen Sie zunächst jedem Punkt in der Menge eine Bezeichnung zu: 1, wenn er nur in dieser Menge enthalten ist, und 0 in einem anderen Fall. Eine Boolesche Funktion gibt 1 (wahr) zurück, wenn jeder Punkt am Eingang 1 ist. Das heißt, jeder Punkt der Menge existiert ausschließlich in dieser Menge, wodurch diese Menge disjunkt wird. Das wahre Ergebnis deutet darauf hin, dass es geeignete Bedingungen gibt, um eine Sonnenblume zu finden.
Um diese Entsprechung zu beweisen, verwendeten die Forscher umfangreiches Wissen über die Booleschen Funktionen, um das Sonnenblumenproblem anzugreifen, für das es bisher an Ressourcen mangelte. Sie haben bewiesen, dass (log w)
w Sätze ausreichen, um eine Sonnenblume zu bekommen. Ein solches Ergebnis reicht nicht aus, um die Hypothese zu beweisen, dass eine bestimmte Konstante des Grades w ausreicht, um eine Sonnenblume zu erhalten. Dies ist jedoch ein um eine Größenordnung besseres Ergebnis als w
w von Erdös und Rado, und es stimmt ungefähr mit der Anzahl der von ihnen vorhergesagten Mengen überein.
Nach einem halben Jahrhundert des Scheiterns deutet die neue Arbeit darauf hin, dass wir bald eine vollständige Lösung sehen werden. Es verbessert auch das Verständnis dafür, wie unweigerlich besondere Formen in der wilden mathematischen Natur des Zufalls entstehen.