Mitte Oktober 2022 flog Justin Gilmer zur Hochzeit eines Freundes von Kalifornien nach New York. Er nutzte die Zeit an der Ostküste für einen Besuch bei seinem ehemaligen Doktorvater, dem Mathematiker Michael Saks von der Rutgers University. Dort hatte Gilmer sieben Jahre zuvor promoviert.

Saks und Gilmer unterhielten sich beim Mittagessen, aber sie sprachen nicht über Mathematik. Tatsächlich hatte Gilmer seit seinem Abschluss im Jahr 2015 nicht mehr ernsthaft über das Fach nachgedacht. Damals entschied er, keine akademische Karriere zu verfolgen, und wandte sich stattdessen der Softwareentwicklung zu. Während er und Saks beisammensaßen, erzählte Gilmer seinem früheren Mentor von seinem Job bei Google, wo er inzwischen an der Entwicklung künstlicher Intelligenz arbeitet.

Nach dem Essen nutzte Gilmer den sonnigen Tag in New Brunswick–Piscataway, um durch seine Alma Mater zu spazieren. Während er herumlief, erinnerte er sich daran, wie er 2013 fast ein ganzes Jahr lang über dieselben Wege auf dem Campus geschritten war, um über »Frankls Vermutung« nachzudenken. Es war eine fixe Idee gewesen, wenn auch eine erfolglose: Trotz all seiner Bemühungen war es Gilmer nur gelungen, zu verstehen, weshalb sich das einfach erscheinende Problem so schwer lösen lässt. »Ich glaube, viele Leute denken so lange darüber nach, bis sie erkennen, warum es so kompliziert ist. Ich habe wahrscheinlich mehr Zeit damit verbracht als die meisten anderen«, sagt Gilmer.

Nach seinem Besuch der Rutgers University im Oktober 2022 geschah etwas Unerwartetes: Gilmer hatte eine neue Idee. Er begann darüber zu grübeln, wie man Techniken aus der Informationstheorie anwenden könnte, um Frankls Vermutung zu lösen. Er verfolgte den Gedanken einen Monat lang weiter und rechnete ständig damit, auf ein unüberwindbares Hindernis zu stoßen und zu scheitern. Doch stattdessen offenbarte sich der Weg zu einer Lösung. Am 16. November 2022 veröffentlichte er schließlich sein Ergebnis, das die Fachwelt auf dem Weg zu einem endgültigen Beweis der Vermutung ein gutes Stück weiterbringt. Der Aufsatz löste sofort eine Flut weiterer Arbeiten aus. Mehrere Mathematiker bauten unabhängig voneinander auf Gilmers neuen Ansatz auf.

Wie oft kommt ein Element in einer Mengenfamilie vor?

Frankls Vermutung bezieht sich auf Zahlenmengen wie {1, 2} und {2, 3, 4}. Mit Mengen lassen sich Rechenoperationen durchführen, zum Beispiel kann man sie vereinigen. So ergibt die Vereinigung von {1, 2} und {2, 3, 4} die größere Menge {1, 2, 3, 4}. Eine Familie von Mengen wird als »unter Vereinigung abgeschlossen« (hier kurz: abgeschlossen) bezeichnet, wenn die Vereinigung von zwei beliebigen Mengen wieder in der Familie enthalten ist. Ein Beispiel dafür ist diese Familie von vier Mengen: {1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}. Egal, welches Paar man miteinander vereinigt, das Ergebnis ist Teil der Familie.

In den 1960er Jahren kursierten erstmals Versionen einer Vermutung über Familien von Mengen, die unter Vereinigung abgeschlossen sind. Die erste formale Definition findet sich jedoch erst in einem 1979 veröffentlichten Aufsatz von Péter Frankl, einem ungarischen Mathematiker. Er ging davon aus, dass eine abgeschlossene Familie zumindest ein Element enthält, das in mindestens der Hälfte aller Mengen vorkommt. Für die Familie {1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4} trifft die Vermutung auf jede Zahl zu.

»Wie viele andere Probleme, die einfach klingen, entzieht sich auch Frankls Vermutung hartnäckig allen Beweisversuchen«Will Sawin, Mathematiker

Es gibt viele weitere Beispiele für abgeschlossene Familien, in denen alle Elemente in mindestens 50 Prozent der Mengen vorkommen – etwa die Mengen, die man aus den Zahlen 1 bis 10 konstruieren kann: Davon gibt es 1024 Stück, und sie bilden eine abgeschlossene Familie, wobei jede Zahl in exakt 512 Mengen vorkommt. Weder Frankl noch andere Fachleute konnten ein Beispiel für eine unter Vereinigung abgeschlossene Familie finden, auf welche die Vermutung nicht zutrifft. 50 Prozent schien also die richtige Vorhersage zu sein.

Dass die Hypothese einleuchtend ist, bedeutet aber nicht, dass sie leicht zu beweisen ist. In den Jahren nach Frankls Arbeit gab es nur wenige Fortschritte. Fachleuten gelang es zwar, Schwellenwerte festzulegen – diese hingen aber von der Anzahl der Mengen in einer Familie ab. Frankls Vermutung legt hingegen den Wert von 50 Prozent als Schwellenwert für Familien jeglicher Größe fest. »Es fühlt sich an, als ob es einfach zu lösen sein sollte«, sagt Will Sawin von der Columbia University. »Doch wie viele andere Probleme, die einfach klingen, entzieht sich auch diese Vermutung hartnäckig allen Beweisversuchen.«

Der mangelnde Fortschritt ist unter anderem der Tatsache geschuldet, dass viele Mathematiker es vorzogen, sich anderen Aufgaben zu widmen. Sie befürchteten, wertvolle Jahre ihrer Karriere zu verlieren, indem sie einem Problem nachjagen, das unmöglich zu lösen ist. Gilmer erinnert sich an einen Tag im Jahr 2013, als er in Saks' Büro ging und Frankls Vermutung zur Sprache brachte. Sein Betreuer – der in der Vergangenheit selbst damit gerungen hatte – warf ihn fast aus dem Zimmer. »Er sagte: ›Justin, du bringst mich dazu, wieder über dieses Problem nachzudenken, und das will ich nicht‹«, erzählt Gilmer.

Eine Einsicht aus der Ungewissheit

Nach seinem Besuch an der Ostküste ging Gilmer das Problem noch einmal gedanklich durch und versuchte sich daran zu erinnern, warum es so schwierig war. Dabei kam ihm eine grundlegende Tatsache in den Sinn: Bei einer Familie mit 100 Mengen gibt es 4950 Optionen, zwei Stück miteinander zu vereinigen. Wie sollte es dann möglich sein, dass sich 4950 verschiedene Vereinigungen auf nur 100 Mengen zurückführen lassen, wenn kein Element zumindest mit einer gewissen Häufigkeit vorkommt?

Zu diesem Zeitpunkt war er schon einem Beweis auf der Spur, obwohl er es noch nicht ahnte. Letztlich führten ihn Methoden aus der Informationstheorie zum Ziel, die es ihm erlaubten, Erwartungswerte zu untersuchen, wenn man zwei Objekte nach dem Zufallsprinzip auswählt.

Die Informationstheorie entstand in der ersten Hälfte des 20. Jahrhunderts. Am bekanntesten wurde sie durch Claude Shannons 1948 veröffentlichte Arbeit »A Mathematical Theory of Communication«. Darin beschrieb Shannon eine Methode, um die Informationsmenge zu berechnen, die bei der Übermittlung einer Nachricht erforderlich ist. Das Verfahren stützt sich auf die Ungewissheit über den genauen Inhalt der Nachricht. Diese Verbindung zwischen Information und Unsicherheit war Shannons grundlegende Erkenntnis.

Angenommen, jemand wirft fünfmal eine Münze und übermittelt Ihnen die Ergebnisse. Bei einem normalen Geldstück sind mindestens fünf Informationsbits für die Übertragung erforderlich – ein Bit pro Wurf. Handelt es sich jedoch um eine gezinkte Münze, die mit einer Wahrscheinlichkeit von 99 Prozent auf Kopf landet, sind weniger Informationen nötig. Die Person könnte beispielsweise im Voraus mit Ihnen vereinbaren, ein einzelnes Informationsbit zu senden, falls die Münze alle fünf Mal auf Kopf gefallen ist – was sehr wahrscheinlich ist. Ein ausgeglichenes Ergebnis wäre im gezinkten Fall deutlich überraschender als bei einer gewöhnlichen Münze.

»Um ehrlich zu sein, bin ich überrascht, dass niemand vorher daran gedacht hat«Justin Gilmer, Softwareentwickler

Gleiches gilt für die Informationen in Zahlenmengen. Wenn eine Familie unter Vereinigung abgeschlossen ist, kann man zufällig zwei Mengen auswählen und die darin enthaltenen Elemente an einen Empfänger übermitteln. Die benötigte Information, um diese Nachricht zu senden, spiegelt die Ungewissheit über den Inhalt der Mengen wider: Bei den 1024 Mengen, die aus den Zahlen von 1 bis 10 gebildet werden können, besteht zum Beispiel eine 50-prozentige Wahrscheinlichkeit, dass die erste zufällig ausgewählte Menge eine 1 enthält (weil die 1 in der Hälfte aller Mengen der Familie vorkommt).

Die Informationstheorie taucht häufig in der Kombinatorik auf, einem Teilgebiet der Mathematik, das sich mit dem Zählen von Objekten befasst und mit dem sich Gilmer als Doktorand beschäftigt hatte. Als er nach seinem Ausflug an die Ostküste nach Kalifornien zurückkehrte, befürchtete er, dass seine Idee, die Informationstheorie mit Frankls Vermutung zu verbinden, bloß die naive Einsicht eines Amateurs war. Sicherlich hatten Fachleute schon einmal diesen Ansatz verfolgt und als unbrauchbar verbucht. »Um ehrlich zu sein, bin ich ein wenig überrascht, dass niemand vorher daran gedacht hat«, sagt Gilmer. »Andererseits hatte ich mich selbst ein Jahr lang damit beschäftigt, ohne darauf zu kommen.«

Ein Beweis über einen Widerspruch

Von da an ließ ihn das Thema nicht mehr los. Im Oktober und November 2022 widmete sich Gilmer nachts, nach seiner Arbeit bei Google, und an den Wochenenden der Vermutung. Ihn ermutigten Ideen, die eine Forschergruppe Jahre zuvor auf dem Blog des Mathematikers Tim Gowers präsentiert hatte. Gilbert hatte dabei stets ein Standardlehrbuch an seiner Seite, um Formeln nachzuschlagen, die er vergessen hatte. »Man sollte meinen, dass jemand, der ein wichtiges Ergebnis erzielt, nicht im zweiten Kapitel von ›Elements of Information Theory‹ nachschauen muss – aber das musste ich«, sagt Gilmer.

Er wollte sich an einem Widerspruchsbeweis versuchen. Dabei trifft man eine Annahme und folgert daraus eine widersprüchliche Aussage, wodurch man automatisch bewiesen hat, dass die Annahme falsch ist. Anstatt es aber direkt mit Frankls Vermutung aufzunehmen, die behauptet, dass zumindest ein Element in mindestens der Hälfte aller Mengen vertreten sein muss, tastete sich Gilmer langsam voran. Er wollte zuerst widerlegen, dass es abgeschlossene Familien gibt, in denen die Elemente in nicht einmal einem Prozent aller Mengen vorkommen. Für seinen Widerspruchsbeweis musste er also annehmen, dass eine solche Familie existiert, und daraus einen Widerspruch herleiten. Damit hätte er zwar nicht Frankls Vermutung bewiesen, jedoch gezeigt, dass zumindest eine Zahl in mindestens einem Prozent aller Mengen vertreten sein muss – unabhängig von der Anzahl der Mengen innerhalb der Familie. Das wäre bereits ein großer Fortschritt.

Angenommen, Sie wählen zufällig zwei Mengen A und B aus einer abgeschlossenen Familie, in der jedes Element in weniger als einem Prozent der Mengen vorkommt. Wie wahrscheinlich ist es, dass die Menge A die Zahl 1 enthält? Und wie lautet das Ergebnis für die Menge B? Da die Wahrscheinlichkeit, ein Element in einer Menge anzutreffen, weniger als ein Prozent beträgt, erwartet man eher nicht, die 1 in A oder B zu finden. Damit gibt es kaum einen Informationsgewinn, wenn Sie erfahren, dass die 1 weder in A noch in B liegt.

Wie hoch ist hingegen die Wahrscheinlichkeit, dass die Vereinigung von A und B die Zahl 1 enthält? Obwohl gering, fällt diese Wahrscheinlichkeit etwas größer aus, als wenn man A und B einzeln betrachtet. Tatsächlich entspricht die Wahrscheinlichkeit nun der Summe aus den zwei Einzelereignissen, abzüglich der Wahrscheinlichkeit, dass die 1 in beiden Mengen vorkommt. Das ergibt folglich eine Zahl, die etwas geringer ist als 2 Prozent.

Damit ist mehr Information nötig, um das Ergebnis mitzuteilen. Falls also eine abgeschlossene Familie existiert, in der jedes Element in weniger als einem Prozent aller Mengen vorkommt, enthält die Vereinigung zweier Mengen mehr Information als die beiden Mengen selbst.

»Die Idee, die Situation erst einmal Element für Element zu betrachten und die Menge an Informationen zu untersuchen, ist äußerst clever. Das ist die Hauptidee des Beweises«, sagt Ryan Alweiss von der Princeton University. Nun musste Gilmer noch einen Widerspruch herbeiführen. Und wie sich herausstellt, ist es leicht zu zeigen, dass die Vereinigung zweier Mengen in einer abgeschlossenen Familie zwangsweise weniger Informationen enthalten muss als die einzelnen Mengen – und nicht mehr, wie er zuvor gefolgert hatte.

Um zu erkennen, warum das so ist, kann man wieder die abgeschlossene Familie mit den 1024 verschiedenen Mengen betrachten, in denen die Zahlen von 1 bis 10 vorkommen. Die Vereinigung zweier zufällig ausgewählter Mengen enthält meist mehr Elemente als die beiden Ursprungsmengen. Somit gibt es weniger Ungewissheit über den Inhalt der Vereinigung. Deshalb muss sie weniger Informationen enthalten als die einzelnen Mengen, aus denen sie besteht.

Damit hatte Gilmer einen gültigen Beweis. Er wusste einerseits, dass die Vereinigung mehr Informationen haben muss, wenn jedes Element in weniger als einem Prozent der Mengen vorkommt. Andererseits enthält die Vereinigung zweier Mengen aus einer abgeschlossenen Familie aber stets geringere Informationen als die Einzelmengen. Da sich beide Aussagen widersprechen, ist die Grundannahme falsch. Gilbert hatte damit bewiesen, dass es in unter Vereinigung abgeschlossenen Familien mindestens ein Element gibt, das in einem Prozent der Mengen (oder häufiger) vorkommt.

Immer weiter auf die 50 zu

Ein Prozent sind aber noch nicht die 50 aus Frankls Vermutung. Als Gilmer seinen Beweis am 16. November 2022 veröffentlichte, fügte er eine Anmerkung hinzu: Er hielt es für möglich, durch seine Methode einer Lösung der vollständigen Vermutung näher zu kommen und den Schwellenwert von einem Prozent auf bis zu 38 Prozent zu erhöhen.

Fünf Tage später veröffentlichten dreiverschiedeneGruppen von Mathematikern unabhängig voneinander Arbeiten, die auf Gilmers Ansatz aufbauten, um genau das zu tun. Es folgtenweitereAufsätze, aber inzwischen scheinen Gilmers Methoden ausgeschöpft zu sein. Um die von Frankl vermuteten 50 Prozent zu erreichen, sind wahrscheinlich neue Ideen erforderlich.

»Ich war ein bisschen eingerostet, und ich kam nicht weiter«Justin Gilmer, Softwareentwickler

Den Wert von einem Prozent auf 38 zu steigern, war für die Forscherinnen und Forscher relativ einfach. Sie fragten sich, warum Gilmer das nicht selbst getan hatte. Die ehrliche Antwort lautet: Nachdem er sieben Jahre außerhalb der Mathematik tätig war, scheiterte der Softwareentwickler an einigen der technischen Berechnungen. »Ich war ein bisschen eingerostet, und ich kam nicht weiter«, sagt Gilmer. »Doch ich war gespannt darauf, was die Gemeinschaft daraus machen würde.« Deswegen veröffentlichte er sein vorläufiges Ergebnis.

Nach Gilmers Meinung haben genau die Umstände, die ihn in der Praxis beschränkt haben, seinen Beweis letztlich überhaupt erst möglich gemacht: »Nur so kann ich mir erklären, warum ich ein Jahr lang über das Problem nachgedacht hatte, ohne Fortschritte zu machen, und dann nach meiner Rückkehr nach mehreren Jahren schließlich diesen Durchbruch erzielte.«