Mitte Oktober, Justin Gilmer flog von Kalifornien nach New York, um an der Hochzeit eines Freundes teilzunehmen. An der Ostküste besuchte er seinen ehemaligen Berater, Michael Saks, Mathematiker an der Rutgers University, wo Gilmer sieben Jahre zuvor promoviert hatte.

Saks und Gilmer tauschten sich beim Mittagessen aus, aber sie sprachen nicht über Mathe. Tatsächlich hatte Gilmer seit seinem Abschluss bei Rutgers im Jahr 2015 nicht mehr ernsthaft über Mathematik nachgedacht. Zu diesem Zeitpunkt hatte er entschieden, dass er keine Karriere in der Wissenschaft anstrebte und stattdessen begann, sich selbst das Programmieren beizubringen. Während er und Saks aßen, erzählte Gilmer seinem alten Mentor von seinem Job bei Google, wo er an maschinellem Lernen und künstlicher Intelligenz arbeitet.

An dem Tag, an dem Gilmer Rutgers besuchte, war es sonnig. Als er herumging, erinnerte er sich daran, wie er 2013 den größten Teil des Jahres damit verbracht hatte, dieselben Campuspfade zu gehen und über ein Problem nachzudenken, das als gewerkschaftsgeschlossene Vermutung bezeichnet wurde. Es war eine Fixierung gewesen, wenn auch eine vergebliche: Gilmer war es trotz all seiner Bemühungen nur gelungen, sich selbst beizubringen, warum das einfach erscheinende Problem mit Zahlenmengen so schwer zu lösen war.

„Ich denke, viele Leute denken über das Problem nach, bis sie zufrieden sind, dass sie verstehen, warum es schwierig ist. Ich habe wahrscheinlich mehr Zeit damit verbracht als die meisten Leute“, sagte Gilmer.

Nach seinem Besuch im Oktober geschah etwas Unerwartetes: Er hatte eine neue Idee. Gilmer begann darüber nachzudenken, wie man Techniken aus der Informationstheorie anwenden könnte, um die Union-Closed-Vermutung zu lösen. Er verfolgte die Idee einen Monat lang und erwartete auf Schritt und Tritt, dass sie scheitern würde. Doch stattdessen öffnete sich immer wieder der Weg zu einem Beweis. Schließlich, am 16. November er veröffentlichte ein einzigartiges Ergebnis das bringt Mathematiker einen großen Schritt in Richtung Beweis der vollständigen Vermutung.

Das Papier löste eine Flut von Folgearbeiten aus. Mathematiker an der University of Oxford, dem Massachusetts Institute of Technology und dem Institute for Advanced Study, neben anderen Institutionen, bauten schnell auf Gilmers neuartigen Methoden auf. Aber bevor sie das taten, stellten sie sich selbst eine Frage: Wer ist dieser Typ?

Halb voll

Bei der Union-Closed-Vermutung geht es um Sammlungen von Zahlen, die als Mengen bezeichnet werden, wie z. B. {1, 2} und {2, 3, 4}. Sie können Operationen an Mengen ausführen, einschließlich ihrer Vereinigung, was bedeutet, dass sie kombiniert werden. Beispielsweise ist die Vereinigung von {1, 2} und {2, 3, 4} {1, 2, 3, 4}.

Eine Sammlung oder Familie von Mengen wird als „vereinigungsgeschlossen“ betrachtet, wenn die Vereinigung zweier beliebiger Mengen in der Familie gleich einer beliebigen vorhandenen Menge in der Familie ist. Betrachten Sie zum Beispiel diese Familie von vier Sätzen:

{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.

Kombinieren Sie ein beliebiges Paar und Sie erhalten ein Set, das bereits in der Familie ist, wodurch die Familienunion geschlossen wird.

Mathematiker unterhielten sich bereits in den 1960er Jahren über Versionen der Union-Closed-Vermutung, aber sie erhielt ihre erste formelle Erklärung 1979 in einem Artikel von Peter Frankl, ein ungarischer Mathematiker, der in den 1980er Jahren nach Japan emigrierte und Straßenauftritte zu seinen Interessen zählt.

Frankl vermutete, dass, wenn eine Familie von Mengen geschlossen ist, sie mindestens ein Element (oder eine Zahl) haben muss, das in mindestens der Hälfte der Mengen vorkommt. Es war aus zwei Gründen eine natürliche Schwelle.

Erstens gibt es leicht verfügbare Beispiele von Union-Closed-Familien, in denen alle Elemente in genau 50% der Mengen vorkommen. Wie all die verschiedenen Sets, die Sie zum Beispiel aus den Zahlen 1 bis 10 machen können. Es gibt 1,024 solcher Mengen, die eine geschlossene Familie bilden, und jedes der 10 Elemente kommt in 512 von ihnen vor. Und zweitens hatte zu der Zeit, als Frankl die Vermutung aufstellte, niemand jemals ein Beispiel einer gewerkschaftlich geschlossenen Familie vorgelegt, in der die Vermutung nicht zutraf.

50 % schienen also die richtige Vorhersage zu sein.

Das bedeutete nicht, dass es leicht zu beweisen war. In den Jahren seit Frankls Arbeit gab es nur wenige Ergebnisse. Vor Gilmers Arbeit gelang es diesen Papieren nur, Schwellenwerte festzulegen, die mit der Anzahl der Sets in der Familie variierten (im Gegensatz zu dem gleichen 50%-Schwellenwert für Set-Familien aller Größen).

„Es fühlt sich an, als sollte es einfach sein, und es ähnelt vielen einfachen Problemen, aber es hat Angriffen widerstanden“, sagte er Will Sawin der Columbia University.

Der Mangel an Fortschritt spiegelte sowohl die knifflige Natur des Problems als auch die Tatsache wider, dass viele Mathematiker es vorzogen, nicht darüber nachzudenken; sie befürchteten, dass sie Jahre ihrer Karriere verlieren würden, wenn sie einem verführerischen Problem nachjagten, das unmöglich zu lösen war. Gilmer erinnert sich an einen Tag im Jahr 2013, als er zu Saks' Büro ging und die gewerkschaftlich geschlossene Vermutung zur Sprache brachte. Sein Berater – der früher selbst mit dem Problem gekämpft hatte – hätte ihn beinahe aus dem Zimmer geworfen.

„Mike sagte: ‚Justin, du bringst mich dazu, wieder über dieses Problem nachzudenken, und das will ich nicht tun'“, sagte Gilmer.

Ein Einblick in die Ungewissheit

Nach seinem Besuch bei Rutgers ging Gilmer das Problem durch den Kopf und versuchte zu verstehen, warum es so schwierig war. Er forderte sich mit einer grundlegenden Tatsache auf: Wenn Sie eine Familie mit 100 Paaren haben, gibt es 4,950 verschiedene Möglichkeiten, zwei auszuwählen und ihre Vereinigung zu erreichen. Dann fragte er sich: Wie ist es möglich, dass 4,950 verschiedene Vereinigungen auf nur 100 Mengen abgebildet werden, wenn in diesen Vereinigungen kein Element zumindest mit einer gewissen Häufigkeit vorkommt?

Schon damals war er auf dem Weg zu einem Beweis, obwohl er ihn noch nicht kannte. Techniken aus der Informationstheorie, die eine rigorose Denkweise darüber liefern, was zu erwarten ist, wenn man zufällig zwei Objekte zieht, würden ihn dorthin führen.

Die Informationstheorie entwickelte sich in der ersten Hälfte des 20. Jahrhunderts, am bekanntesten mit Claude Shannons Arbeit von 1948: „Eine mathematische Theorie der Kommunikation.“ Das Papier bot eine genaue Methode zur Berechnung der Menge an Informationen, die zum Senden einer Nachricht erforderlich sind, basierend auf der Unsicherheit darüber, was genau die Nachricht sagen würde. Dieser Link - zwischen Information und Ungewissheit – war Shannons bemerkenswerte, grundlegende Einsicht.

Um ein Spielzeugbeispiel zu nehmen, stellen Sie sich vor, ich werfe fünfmal eine Münze und sende Ihnen die resultierende Sequenz. Wenn es sich um eine normale Münze handelt, werden fünf Informationsbits zur Übertragung benötigt. Aber wenn es sich um eine geladene Münze handelt – sagen wir, mit einer Wahrscheinlichkeit von 99 %, auf Kopf zu landen – braucht es viel weniger. Zum Beispiel könnten wir im Voraus vereinbaren, dass ich Ihnen eine 1 (eine einzelne Information) schicke, wenn die geladene Münze alle fünf Mal Kopf landet, was sehr wahrscheinlich der Fall ist. Das Ergebnis eines fairen Münzwurfs ist überraschender als bei einem voreingenommenen und daher mehr Informationen.

Dasselbe gilt für die Informationen, die in Zahlenmengen enthalten sind. Wenn ich eine Familie von gewerkschaftlich geschlossenen Sets habe – sagen wir die 1,024 Sets, die aus den Zahlen 1 bis 10 bestehen – könnte ich zwei Sets nach dem Zufallsprinzip auswählen. Dann könnte ich Ihnen die Elemente jedes Sets mitteilen. Die Menge an Informationen, die erforderlich ist, um diese Nachricht zu senden, spiegelt die Unsicherheit darüber wider, was diese Elemente sind: Es besteht beispielsweise eine Wahrscheinlichkeit von 50 %, dass das erste Element im ersten Satz eine 1 ist (weil 1 in der Hälfte der Sätze vorkommt der Familie), genauso wie es eine 50-prozentige Chance gibt, dass das erste Ergebnis in einer Folge von fairen Münzwürfen Kopf ist.

Informationstheorie taucht häufig in der Kombinatorik auf, einem Bereich der Mathematik, der sich mit dem Zählen von Objekten befasst, was Gilmer als Doktorand studiert hatte. Aber als er nach Hause nach Kalifornien zurückflog, befürchtete er, dass die Art und Weise, wie er die Informationstheorie mit der Closed-Union-Vermutung verbinden wollte, die naive Einsicht eines Amateurs war: Sicherlich waren Mathematiker schon früher auf dieses glänzende Objekt gestoßen und hatten es als Katzengold erkannt .

„Um ehrlich zu sein, bin ich etwas überrascht, dass noch niemand daran gedacht hat“, sagte Gilmer. „Aber vielleicht sollte ich nicht überrascht sein, weil ich selbst ein Jahr lang darüber nachgedacht hatte und mich mit Informationstheorie auskannte.“

Eher wahrscheinlich

Gilmer arbeitete nachts, nachdem er seine Arbeit bei Google beendet hatte, und an den Wochenenden in der zweiten Oktoberhälfte und Anfang November an dem Problem. Er wurde durch Ideen ermutigt, die eine Gruppe von Mathematikern Jahre zuvor in einem untersucht hatte offene Zusammenarbeit im Blog eines prominenten Mathematikers namens Tim Gowers. Er arbeitete auch mit einem Lehrbuch an seiner Seite, damit er Formeln nachschlagen konnte, die er vergessen hatte.

„Man könnte meinen, jemand, der ein großartiges Ergebnis erzielt, sollte nicht Kapitel 2 von konsultieren müssen Elemente der Informationstheorie, aber ich habe es getan “, sagte Gilmer.

Gilmers Strategie bestand darin, sich eine gewerkschaftlich geschlossene Familie vorzustellen, in der kein Element in sogar 1 % aller Sets auftauchte – ein Gegenbeispiel, das, wenn es wirklich existierte, Frankls Vermutung widerlegen würde.

Angenommen, Sie wählen zufällig zwei Mengen A und B aus dieser Familie aus und betrachten die Elemente, die in diesen Mengen enthalten sein könnten, eines nach dem anderen. Fragen Sie nun: Wie hoch ist die Wahrscheinlichkeit, dass Satz A die Zahl 1 enthält? Und Satz B? Da jedes Element mit einer Wahrscheinlichkeit von etwas weniger als 1 % in einer bestimmten Menge auftaucht, würden Sie nicht erwarten, dass entweder A oder B 1 enthalten. Das bedeutet, dass es wenig Überraschung – und wenig gewonnene Informationen – gibt, wenn Sie erfahren, dass beides nicht der Fall ist tut.

Denken Sie als Nächstes über die Wahrscheinlichkeit nach, dass die Vereinigung von A und B 1 enthält. Es ist immer noch unwahrscheinlich, aber es ist wahrscheinlicher als die Wahrscheinlichkeit, dass es in einem der einzelnen Sätze vorkommt. Es ist die Summe der Wahrscheinlichkeit, dass es in A auftritt, und der Wahrscheinlichkeit, dass es in B auftritt, minus der Wahrscheinlichkeit, dass es in beiden auftritt. Also vielleicht knapp unter 2%.

Dies ist immer noch niedrig, aber näher an einem 50-50-Angebot. Das bedeutet, dass mehr Informationen erforderlich sind, um das Ergebnis zu teilen. Mit anderen Worten, wenn es eine geschlossene Familie gibt, in der kein Element in mindestens 1 % aller Mengen vorkommt, gibt es mehr Informationen in der Vereinigung zweier Mengen als in jeder der Mengen selbst.

„Die Idee, Dinge Element für Element aufzudecken und sich die Menge an Informationen anzusehen, die man lernt, ist äußerst clever. Das ist die Hauptidee des Beweises“, sagte er Ryan Alweiss der Princeton-Universität.

An diesem Punkt begann Gilmer Frankls Vermutung näher zu kommen. Das liegt daran, dass es leicht zu demonstrieren ist, dass in einer Union-Closed-Familie die Vereinigung zweier Mengen notwendigerweise weniger Informationen enthält als die Mengen selbst – nicht mehr.

Um zu verstehen, warum, denken Sie an diese gewerkschaftlich geschlossene Familie mit den 1,024 verschiedenen Sets, die Sie aus den Zahlen 1 bis 10 erstellen können. Wenn Sie zwei dieser Sets zufällig auswählen, erhalten Sie im Durchschnitt Sets mit fünf Elementen. (Von diesen 1,024 Mengen enthalten 252 fünf Elemente, was die häufigste Mengengröße darstellt.) Sie werden wahrscheinlich auch eine Vereinigung erhalten, die etwa sieben Elemente enthält. Aber es gibt nur 120 verschiedene Möglichkeiten, Sets mit sieben Elementen zu erstellen.

Der Punkt ist, dass es mehr Ungewissheit über den Inhalt zweier zufällig ausgewählter Mengen gibt als über ihre Vereinigung. Die Vereinigung verschiebt sich zu größeren Mengen mit mehr Elementen, für die es weniger Möglichkeiten gibt. Wenn Sie die Vereinigung zweier Mengen in einer Familie mit geschlossener Vereinigung vornehmen, wissen Sie irgendwie, was Sie bekommen werden – wie wenn Sie eine voreingenommene Münze werfen – was bedeutet, dass die Vereinigung weniger Informationen enthält als die Mengen, aus denen sie besteht.

Damit hatte Gilmer einen Beweis. Er wusste, dass die Vereinigung gezwungen ist, mehr Informationen zu enthalten, wenn in 1 % der Sets kein Element vorkommt. Aber die Union muss weniger Informationen enthalten. Daher muss mindestens ein Element in mindestens 1 % der Sets vorkommen.

Der Schub auf 50

Als Gilmer seinen Beweis am 16. November veröffentlichte, fügte er eine Notiz hinzu, dass er es für möglich hielt, seine Methode zu verwenden, um einem Beweis der vollständigen Vermutung noch näher zu kommen, wodurch die Schwelle möglicherweise auf 38 % angehoben würde.

Fünf Tage später, nach drei anders Gruppen der Mathematiker veröffentlichten innerhalb weniger Stunden Artikel, die auf Gilmers Arbeit aufbauten, um genau das zu tun. Zusätzliche Papiere gefolgt, aber der anfängliche Ausbruch scheint Gilmers Methoden so weit gebracht zu haben, wie sie nur gehen können; 50 % zu erreichen, erfordert wahrscheinlich zusätzliche neue Ideen.

Dennoch war es für einige der Autoren der Folgepapiere relativ einfach, auf 38 % zu kommen, und sie fragten sich, warum Gilmer es nicht einfach selbst tat. Die einfachste Erklärung erwies sich als die richtige: Nach mehr als einem halben Jahrzehnt ohne Mathematik wusste Gilmer einfach nicht, wie er einen Teil der technischen Analysearbeit erledigen sollte, die erforderlich war, um es durchzuziehen.

„Ich war ein bisschen eingerostet, und um ehrlich zu sein, steckte ich fest“, sagte Gilmer. „Aber ich war gespannt, wohin die Community es führen würde.“

Gilmer glaubt jedoch, dass die gleichen Umstände, die ihn aus der Übung gebracht haben, seinen Beweis wahrscheinlich überhaupt erst ermöglicht haben.

„Nur so kann ich erklären, warum ich ein Jahr lang in der Graduiertenschule über das Problem nachgedacht und keine Fortschritte gemacht habe, ich habe Mathe für sechs Jahre aufgegeben, mich dann wieder dem Problem zugewandt und diesen Durchbruch erzielt“, sagte er. „Ich weiß nicht, wie ich es anders erklären soll, als dass ich beim maschinellen Lernen voreingenommen bin.“

Korrektur: 3. Januar 2023
Die ursprüngliche Überschrift bezog sich auf Gilmer als „Google-Ingenieur“. Eigentlich ist er Forscher.