Wenn man Punkte zufällig in einer Ebene verteilt und gruppiert, kann man nach genauem Hinsehen sicherlich gewisse komplizierte Muster erkennen. Doch wie viele gruppierte Punkte braucht man mindestens, damit garantiert eine bestimmte Struktur entsteht? Dieses »Sonnenblumenproblem« formulierten die berühmten Mathematiker Paul Erdős und Richard Rado 1960, was etliche ihrer Kollegen fast sechs Jahrzehnte lang in Schach hielt.

Doch nun sind Ryan Alweiss von der Princeton University, Kewen Wu von der Universität Peking sowie Shachar Lovett und Jiapeng Zhang, beide an der University of California in San Diego, einer Lösung erstaunlich nahegekommen. In ihrer kürzlich auf dem Preprint-Server ArXiv veröffentlichten Arbeit beantworten die Forscher die Frage von Erdős und Rado zwar nicht vollständig, doch dank einer gängigen Methode aus der theoretischen Informatik haben sie erstaunliche Fortschritte gemacht.

Versteckte Sonnenblumen

Beim Sonnenblumenproblem geht es um willkürlich verteilte Punkte in der Ebene, die man in Mengen gruppieren kann. Zuerst legt man eine Anzahl an Punkten fest, die jede Menge enthalten soll, und grenzt dann zufälligerweise Bereiche ab, in der sich jeweils die gewünschte Anzahl an Punkten befinden. Die Bereiche können sich dabei auch überlappen, so dass einige Punkte in der gleichen Menge landen. Je mehr Bereiche und Punkte man zeichnet, desto häufiger überschneiden sie sich. Dadurch ergeben sich wirre Muster verknoteter Abgrenzungen, die sich über die Ebene erstrecken.

Doch sie sind nicht so chaotisch, wie sie auf den ersten Blick erscheinen – das vermuteten zumindest Erdős und Rado. Gibt es genügend Punkte und abgesteckte Mengen, taucht den zwei Mathematikern zufolge immer eine gewisse Struktur auf, die der Blüte einer Sonnenblume ähnelt: Drei oder mehr Bereiche überlappen sich dabei in der gleichen Teilmenge, ohne weitere Bereiche zu schneiden.

Entfernt man die gemeinsame Teilmenge, dann sind die Mengen völlig getrennt voneinander in der Ebene angeordnet, so wie die Blütenblätter um das dunkle Zentrum einer Sonnenblume. Findet man drei oder mehr abgesteckte Bereiche, die sich mit keinen anderen Mengen überlappen, stellt auch diese Konstellation eine Sonnenblume dar. Solche einsamen Inseln nennen Mathematiker »disjunkt«.

Erdős und Rado wollten herausfinden, wie viele Mengen gewisser Größe mindestens nötig sind, damit garantiert eine Sonnenblume entsteht. Ihnen gelang es, zu beweisen, dass unter w^w Mengen der Größe w (also jeweils w Punkte enthalten) immer eine solche Struktur aus drei Mengen auftaucht. Wenn jeder Bereich also 100 Punkte enthält, braucht man etwa 100¹⁰⁰ Mengen, um sicher eine Sonnenblume zu finden.

Aber Erdős und Rado gingen davon aus, dass ihre Abschätzung nicht wirklich gut war. Sie vermuteten, dass die tatsächliche Anzahl benötigter Mengen viel kleiner ist als w^w – es sollte sich dabei eher um eine Konstante potenziert mit w handeln (wie 3^w, 80^w oder 5 000 000 000^w). Ihr Verdacht fällt in den Bereich der Ramseytheorie, die untersucht, wie geordnete Strukturen in zufälligen Konstellationen entstehen. Die beiden Mathematiker fanden allerdings keinen Weg, um die »Sonnenblumenvermutung« zu beweisen.

Sie taten sich nicht als Einzige schwer damit. Nach Erdős und Rados erstem Ergebnis machten bloß zwei Mathematiker 1997 und Anfang 2019 sehr bescheidene Fortschritte in dieser Frage. Die aktuelle Arbeit stellt dagegen eine gewaltige Entwicklung dar. Dafür unterteilten die vier Forscher das Problem in zwei Fälle, die sie mit Werkzeugen aus der theoretischen Informatik behandelten, um darin Sonnenblumen zu identifizieren und ihre Existenz zu beweisen.

Informatik hilft Mathematikern

Im ersten – und einfacheren – Szenario betrachten sie Mengen, die sich stark überlappen. Zunächst identifizieren die Wissenschaftler Punkte, die in möglichst vielen Bereichen vorkommen. Anstatt das gesamte System zu durchstöbern, suchen sie dann lediglich unter diesen Mengen nach Sonnenblumen. Die Prozedur wiederholen sie und verfeinern dabei ihre Suche, indem sie sich auf immer weniger Mengen mit gemeinsamen Punkten konzentrieren – bis sie irgendwann eine Sonnenblume finden.

Im zweiten Fall untersuchen sie, was passiert, wenn sich die Bereiche kaum überlappen. Dann besteht eine Sonnenblume am wahrscheinlichsten aus drei disjunkten Mengen ohne gemeinsamen Kern. Allerdings ist es sehr schwierig zu beweisen, dass sich drei einsame Inseln unter extrem vielen leicht überlappenden Mengen verstecken.

Hier kommt die Verbindung zur Informatik ins Spiel. Lovett und Zhang untersuchten seit einigen Jahren das Sonnenblumenproblem mit Methoden, die Informatiker für so genannte boolesche Funktionen nutzen. Übergibt man solchen Funktionen eine Folge von Bits, spucken sie am Ende ein einzelnes Bit aus: Eins, wenn die Rechenanweisung wahr ist, ansonsten ist sie null. Zum Beispiel kann man eine boolesche Funktion programmieren, die eine Eins ausgibt, wenn die Eingangsbits eine Eins enthalten.

Vor drei Jahren erkannten Lovett und Zhang dann, dass man die Frage, ob drei disjunkte Mengen in einem System leicht überlappender Mengen auftauchen, in die theoretische Informatik übersetzen kann. Zuerst weist man jedem Punkt in einer bestimmten Menge eine Bezeichnung zu: Eins, wenn er ausschließlich in dieser Menge vorkommt, und null sonst. Die boolesche Funktion gibt dann eine Eins (wahr) aus, wenn jeder Eingabepunkt eine Eins ist – was bedeutet, dass die Menge disjunkt ist. Ein »wahres« Ergebnis zeigt also an, dass die richtigen Bedingungen für eine Sonnenblume gegeben sind.

Damit verfrachteten die Forscher das Problem in die theoretische Informatik. Dieser Bereich enthält eine Fülle an Methoden, die es ermöglichen, erstaunliche Fortschritte zu erzielen. So konnten die vier Wissenschaftler beweisen, dass bereits (log w)^w Mengen ausreichen, um garantiert eine Sonnenblume zu finden. Ihr Ergebnis bestätigt zwar nicht die Vermutung von Erdős und Rados, wonach man bloß eine Konstante hoch w Mengen braucht, dennoch verbesserten sie die ursprüngliche Abschätzung von w^w um eine Größenordnung.