Tagsüber arbeitend und nachts forschend, lösten die Forscher von Google Brain eine Vermutung, die die mathematische Gemeinschaft seit Jahrzehnten verwirrt.

Mitte Oktober 2022 flog Justin Gilmer von Kalifornien nach New York, um seinen ehemaligen Mentor Michael Saks, einen Mathematiker an der Rutgers University, an der Ostküste zu besuchen.

Während der Erinnerungen sprachen sie nicht über Mathematik. Tatsächlich hat Gilmer seit seiner Promotion an der Rutgers University im Jahr 2015 nicht mehr ernsthaft über Mathematik nachgedacht. Zu diesem Zeitpunkt entschied er sich gegen eine akademische Laufbahn und begann, sich selbst das Programmieren beizubringen. Beim Abendessen mit Saks erzählte Gilmer seinem Mentor von seiner Arbeit bei Google: maschinelles Lernen und künstliche Intelligenz.

Als Gilmer den Campusweg entlangging, erinnerte er sich, dass er 2013 mehr als ein Jahr damit verbracht hatte, diesen Weg zu gehen, und über ein Problem namens „Union Closed Set Conjecture (auch bekannt als Frankl-Vermutung)“ nachgedacht hatte. Das war schon immer ein erfolgloses Problem. Trotz all seiner Bemühungen gelang es Gilmer nur, sich selbst beizubringen, warum dieses scheinbar einfache Problem einer Zahlensammlung so schwer zu lösen war.

Aber nach diesem Besuch sieben Jahre später hatte Gilmer plötzlich eine neue Inspiration. Er begann darüber nachzudenken, wie er die Informationstheorie anwenden könnte, um die Mengenvermutung zu lösen und abzuschließen. Nach einem Monat Recherche öffnete sich immer wieder der Weg zum Beweis. Im November veröffentlichte er die Ergebnisse auf arXiv und kündigte damit erhebliche Fortschritte beim Beweis der gesamten Vermutung an.

Link zum Papier: https://arxiv.org/pdf/2211.09055.pdf

Dieses Papier löste eine Welle von Folgeforschungen aus. Mathematiker unter anderem der Universität Oxford, des MIT und des Institute for Advanced Study begannen schnell mit der Arbeit an Gilmers neuer Methode.

Was ist die Union-Closed-Set-Vermutung?

Die Vermutung über geschlossene Mengen bezieht sich auf Zahlenmengen wie {1, 2} und {2, 3, 4}. Sie können Operationen an Mengen ausführen, einschließlich der Vereinigung ihrer Mengen. Beispielsweise ist die Vereinigung von {1, 2} und {2, 3, 4} {1, 2, 3, 4}.

Eine Menge oder Familie wird als „geschlossene Vereinigung“ bezeichnet, wenn die Vereinigung zweier beliebiger Mengen in der Familie gleich einer vorhandenen Menge in der Familie ist. Betrachten Sie zum Beispiel diese Familie aus vier Mengen: {1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.

Durch die Kombination eines beliebigen Paares erhalten Sie ein Set, das bereits in der Familie vorhanden ist. Daher wird diese Familie als geschlossenes Set bezeichnet.

Mathematiker haben die Mengenvermutung bereits in den 1960er Jahren diskutiert und abgeschlossen, aber erst 1979 erhielt sie ihre erste formelle Aussage in einer Arbeit von Péter Frankl, einem ungarischen Mathematiker, der in den 1980er Jahren nach Japan emigrierte Neben Mathematik liebt er auch Straßenaufführungen.

Frankl vermutete, dass, wenn eine Mengenfamilie eine durch Vereinigung abgeschlossene Menge ist, sie mindestens ein Element (oder eine Zahl) haben muss, das in mindestens der Hälfte der Mengen vorkommt. Dies ist aus zwei Gründen ein natürlich vorkommender Schwellenwert.

​

Justin Gilmer

Zuerst am Beispiel einer fertigen und geschlossenen Familie von Sets, bei der alle Elemente in genau 50 % der Sets vorkommen. Sie könnten beispielsweise die Zahlen 1 bis 10 verwenden, um alle verschiedenen Mengen zu bilden, was insgesamt 1024 solcher Mengen ergibt. Sie bilden eine geschlossene Familie von 512 Mengen, in denen jedes der 10 Elemente vorkommt.

Als Frankl diese Vermutung vorschlug, hatte noch niemand ein Beispiel für eine geschlossene Menge vorgeschlagen, bei der die Vermutung ungültig war. 50 % scheinen also eine korrekte Vorhersage zu sein.

Das bedeutet nicht, dass es leicht zu beweisen ist. Vor Gilmers Arbeit war es vielen Veröffentlichungen nur gelungen, Schwellenwerte festzulegen, die mit der Anzahl der Sets in der Familie variierten (anstelle eines 50 %-Schwellenwerts, der für alle Größen von Setfamilien gleich war).

Will Sawin von der Columbia University sagte: „Es fühlt sich an, als ob es einfach sein sollte, und es ähnelt vielen einfachen Problemen, aber es wurde nie gelöst

.“

Der mangelnde Fortschritt spiegelt sowohl die Hartnäckigkeit des Problems als auch die Tatsache wider, dass viele Mathematiker lieber nicht darüber nachdenken möchten. Sie befürchten, dass sie Jahre ihrer Karriere damit verschwenden, einem unmöglichen Problem nachzujagen. Gilmer erinnert sich an einen Tag im Jahr 2013, als er in Saks‘ Büro ging und dies und die Closed-Set-Vermutung erwähnte und die Dozenten, die sich ebenfalls mit dem Problem auseinandergesetzt hatten, ihn aus dem Raum warfen.

Einblicke in die Unsicherheit

Nach seinem Besuch bei Rutgers ging Gilmer die Frage durch den Kopf und versuchte zu verstehen, warum es so schwierig war. Er erinnerte sich an eine grundlegende Tatsache: Wenn Sie eine Familie mit 100 Satzkombinationen haben, gibt es 4950 verschiedene Möglichkeiten, zwei auszuwählen und zu kombinieren. Dann dachte er: Wie könnten 4950 verschiedene Kombinationen auf 100 Mengen abgebildet werden, wenn in diesen Kombinationen kein Element zumindest einigermaßen häufig vorkäme?

Zu diesem Zeitpunkt ist er bereits auf dem Weg zur Lösung, auch wenn er es noch nicht weiß.

Die Informationstheorie wurde in der ersten Hälfte des 20. Jahrhunderts entwickelt, insbesondere in Claude Shannons 1948 erschienener Arbeit „A Mathematical Theory of Communication“. Dieses Dokument bietet eine genaue Möglichkeit, die Menge an Informationen zu berechnen, die zum Senden einer Nachricht erforderlich ist, basierend auf der Unsicherheit darüber, was die Nachricht ausdrückt. Dieser Zusammenhang zwischen Information und Unsicherheit ist Shannons bemerkenswerte Erkenntnis.

Informationstheorie taucht häufig in der Kombinatorik auf, einem Bereich der Mathematik, der sich mit dem Zählen von Objekten beschäftigt und den Gilmer als Doktorand studierte. Doch als er nach Hause nach Kalifornien flog, befürchtete er, dass die Art und Weise, wie er die Informationstheorie mit der Unions-Closed-Set-Vermutung in Verbindung brachte, die Naivität eines Amateurs sei.

„Um ehrlich zu sein, bin ich ein wenig überrascht, dass noch niemand daran gedacht hat“, sagte Gilmer. „Aber vielleicht sollte ich nicht überrascht sein, denn ich habe selbst ein Jahr lang darüber nachgedacht und verstehe die Informationstheorie.“ Wochentags ist er hauptsächlich mit seiner täglichen Arbeit bei Google beschäftigt und widmet sich in seiner Freizeit dem Studium mathematischer Probleme. Außerdem hat er zur Arbeit ein Mathe-Lehrbuch dabei, um vergessene Formeln jederzeit nachschlagen zu können. Gilmer bleibt auf dem Boden, blickt aber auch zu den Sternen – er liest gerne die Blogs des berühmten Mathematikers Tim Gowers, die ihn immer wieder inspirieren.

Gilmer sagte bescheiden: „Vielleicht denken Sie, dass Leute, die mathematische Probleme lösen, Kapitel 2 von „Elemente der Informationstheorie (Grundlagen der Informationstheorie)“ nicht konsultieren sollten, aber ich habe es getan.“

Die von Gilmer vorgeschlagene Methode ist Stellen Sie sich eine Familie geschlossener Mengen vor, in der die Wahrscheinlichkeit, dass ein Element in allen Mengen vorkommt, weniger als 1 % beträgt. Dies ist ein Gegenbeispiel, das, wenn es wahr wäre, Frankls Vermutung widerlegen würde.

Angenommen, zwei Mengen A und B werden zufällig aus dieser Familie ausgewählt. Fragen Sie sich: Wie hoch ist die Wahrscheinlichkeit, dass Menge A die Zahl 1 enthält? Was ist mit Set B? Da die Wahrscheinlichkeit, dass jedes Element in einer bestimmten Menge vorkommt, etwas weniger als 1 % beträgt, sollten Sie nicht erwarten, dass A oder B 1 enthalten. Das bedeutet, dass wir uns nicht wundern würden, wenn keines von beiden tatsächlich 1 enthalten würde, und sicherlich nicht viele Informationen gewinnen würden.

Als nächstes betrachten wir die Wahrscheinlichkeit, dass die Vereinigung von A und B 1 enthält. Dies ist immer noch unwahrscheinlich, aber etwas größer als die Wahrscheinlichkeit, dass 1 in einem der beiden Sätze allein vorkommt, und ist die Summe der Wahrscheinlichkeit, dass 1 in A vorkommt, und der Wahrscheinlichkeit, dass 1 in B vorkommt, minus der Wahrscheinlichkeit, dass 1 in beiden vorkommt. Die Wahrscheinlichkeit, dass die Vereinigung von A und B 1 enthält, beträgt also etwa weniger als 2 %.

Das ist immer noch niedrig, liegt aber eher bei einer Schätzung von 50 %, was bedeutet, dass weitere Informationen erforderlich sind, bevor die Ergebnisse geteilt werden können. Mit anderen Worten: Wenn es eine vereinigungsübergreifende Familie von Mengen gibt, in der die Wahrscheinlichkeit, dass ein Element in allen Mengen vorkommt, weniger als 1 % beträgt, dann enthält die Vereinigung der beiden Mengen mehr Informationen als jede Menge für sich.

„Die Idee, die Vermutung Element für Element zu beweisen, ist sehr clever“, kommentierte Ryan Alweiss von der Princeton University.

Gilmers Arbeit kommt Frankls Vermutung immer näher. Dies liegt daran, dass es leicht zu zeigen ist, dass in einer Familie von durch Vereinigung geschlossenen Mengen die Vereinigung zweier Mengen weniger Informationen enthalten muss als die beiden Mengen selbst – nicht mehr.

Der Grund ist einfach. Nehmen Sie die Familie der geschlossenen Mengen, die 1024 verschiedene Mengen enthält. Die Elemente in jeder Menge sind Zahlen von 1 bis 10. Wenn zwei dieser Mengen zufällig ausgewählt werden, erhält man im Durchschnitt eine Vereinigung von fünf Elementen. (Von den 1024 Mengen enthalten 252 fünf Elemente, was die häufigste Mengengröße darstellt.) Es ist auch möglich, dass wir eine Vereinigung von etwa sieben Elementen erhalten. Es gibt jedoch nur 120 verschiedene Kombinationsmöglichkeiten, um eine Vereinigung von sieben Elementen zu erhalten.

Der Punkt ist, dass zwei zufällig ausgewählte Mengen Elemente mit mehr Unsicherheit als ihre Vereinigung enthalten. Eine Union ist eher eine größere Menge mit mehr Elementen und weniger Möglichkeiten. Wenn Sie eine Vereinigungsoperation für zwei Mengen in einer durch Vereinigung geschlossenen Mengengruppe durchführen, kennen Sie möglicherweise das Ergebnis der Vereinigung, genau wie beim Werfen einer voreingenommenen Münze. Sie können leicht erraten, auf welcher Seite die Union landen wird als die beiden Sets selbst.

Auf dieser Grundlage geht Gilmer davon aus, dass die Wahrscheinlichkeit, dass mindestens ein Element in der Menge vorkommt, größer oder gleich 1 % ist.

Was du verlierst, gewinnst du etwas

Als Gilmer am 16. November seinen Beweis veröffentlichte, fügte er eine Notiz bei: Er glaubte, dass die Verwendung seiner Methode dem Beweis der vollständigen Vermutung näher kommen könnte und dass dies auch möglich sein könnte Der Schwellenwert wird auf 38 % angehoben.

Fünf Tage später veröffentlichten drei verschiedene Gruppen von Mathematikern innerhalb weniger Stunden voneinander Aufsätze, die auf Gilmers Arbeit basierten. Der Ausbruch scheint Gilmers Ansatz auf die Spitze getrieben zu haben, doch um 50 Prozent zu erreichen, sind möglicherweise weitere neue Ideen erforderlich.

Einige der Autoren nachfolgender Arbeiten fragten sich jedoch, warum Gilmer die relativ einfache 38-Prozent-Studie nicht selbst durchgeführt hat. Tatsächlich ist der Grund nicht kompliziert: Nach mehr als fünf Jahren ohne Mathematik wusste Gilmer einfach nicht, wie er die technische Analyse durchführen sollte, um dieses Ziel zu erreichen.

„Ich bin ein bisschen eingerostet und ehrlich gesagt stecke ich fest“, sagte Gilmer. „Aber ich bin gespannt, wohin die mathematische Gemeinschaft es bringen wird.“

Aber Gilmer glaubt auch, dass die gleichen Gründe, die ihn die Gelegenheit gekostet haben, es zu üben, zum Teil diejenigen sind, die seinen Beweis überhaupt möglich gemacht haben Ort: „Dies ist die einzige Erklärung dafür, warum ich in der Graduiertenschule ein Jahr lang keine Fortschritte beim Nachdenken über dieses Problem gemacht habe und dann einen Durchbruch geschafft habe, als ich mich diesem Problem erneut widmete, nachdem ich die Mathematik sechs Jahre lang verlassen hatte. Zusätzlich zu den Veränderungen in meinem Denken.“ verursacht durch maschinelles Lernen, ich kenne keine andere Erklärung.“

Das obige ist der detaillierte Inhalt vonTagsüber arbeitend und nachts forschend, lösten die Forscher von Google Brain eine Vermutung, die die mathematische Gemeinschaft seit Jahrzehnten verwirrt.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!