„A-Team“ der Mathematik beweist einen entscheidenden Zusammenhang zwischen Addition und Mengen | Quanta-Magazin

In einer zufällig ausgewählten Zahlenmenge kann die Addition wild werden.

Addieren Sie jedes Paar aus einem solchen Satz, und am Ende erhalten Sie eine neue Liste, die wahrscheinlich viel mehr Zahlen enthält als die, mit der Sie begonnen haben. Beginnen Sie mit 10 Zufallszahlen, und diese neue Liste (Summenmenge genannt) wird etwa 50 Elemente enthalten. Beginnen Sie mit 100 und die Summe wird wahrscheinlich etwa 5,000 betragen; 1,000 zufällige Anfangszahlen ergeben eine Summenmenge mit einer Länge von 500,000 Zahlen.

Wenn Ihre anfängliche Menge jedoch eine Struktur hat, kann die Summenmenge am Ende weniger Zahlen als diese haben. Betrachten Sie eine andere 10er-Zahlenmenge: alle geraden Zahlen von 2 bis 20. Da sich verschiedene Paare zur gleichen Zahl addieren – 10 + 12 ist dasselbe wie 8 + 14 und 6 + 16 – hat die Summenmenge nur 19 Zahlen, nicht 50. Dieser Unterschied wird mit zunehmender Größe der Sets immer deutlicher. Eine strukturierte Liste mit 1,000 Zahlen könnte eine Summenmenge mit nur 2,000 Zahlen enthalten.

In den 1960er Jahren wurde ein Mathematiker namens Gregor Freimann begann mit der Untersuchung von Mengen mit kleinen Summenmengen, um den Zusammenhang zwischen Addition und Mengenstruktur zu untersuchen – ein entscheidender Zusammenhang, der das mathematische Gebiet der additiven Kombinatorik definiert. Freiman machte beeindruckende Fortschritte und bewies, dass eine Menge mit einer kleinen Summenmenge in einer größeren Menge enthalten sein muss, deren Elemente in einem äußerst regelmäßigen Muster angeordnet sind. Doch dann stagnierte das Feld. „Freimans ursprünglicher Beweis war außerordentlich schwer zu verstehen, so dass niemand wirklich sicher war, dass er richtig war. Es hatte also nicht wirklich die Auswirkungen, die es hätte haben können“, sagte er Timothy Gowers, Mathematiker am Collège de France und der University of Cambridge sowie Fields-Medaillengewinner. "Aber dann Imre Ruzsa platzte auf den Plan.“

In einer Reihe von XNUMX Papiere In den 1990er Jahren bewies Ruzsa den Satz von Freiman mit einem eleganten neuen Argument. Ein paar Jahre später, Katalin Marton, ein einflussreicher ungarischer Mathematiker, der 2019 starb, stellte die Frage, was eine kleine Summenmenge über die Struktur der ursprünglichen Menge aussagt. Sie ersetzte die Arten von Elementen, die in der Menge auftraten, und die Art der Struktur, nach der Mathematiker suchen sollten, und dachte, dass Mathematiker dadurch noch mehr Informationen extrahieren könnten. Martons Vermutung weist Verbindungen zu Beweissystemen, Codierungstheorie und Kryptographie auf und nimmt in der additiven Kombinatorik einen hohen Stellenwert ein.

Ihre Vermutung „fühlt sich wirklich wie eines der grundlegendsten Dinge an, die wir nicht verstanden haben“, sagte sie Ben Grün, ein Mathematiker an der Universität Oxford. Es „untermauerte einfach viele Dinge, die mir wichtig sind.“

Green schloss sich mit Gowers zusammen, Freddie Manieren der University of California, San Diego, und Terence tao, ein Fields-Medaillengewinner an der University of California, Los Angeles, um den israelischen Mathematiker und Blogger zu bilden Gil kalai genannt „Eine Mannschaft“ von Mathematikern. Sie bewiesen eine Version der Vermutung in einer Arbeit geteilt am 9. November.

Netz Katz, ein Mathematiker der Rice University, der nicht an der Arbeit beteiligt war, beschreibt den Beweis als „wunderbar einfach“ – und „mehr oder weniger völlig aus heiterem Himmel“.

Tao startete daraufhin einen Versuch, den Beweis zu formalisieren Lehnen, eine Programmiersprache, die Mathematikern hilft, Theoreme zu überprüfen. Innerhalb weniger Wochen war dieser Versuch erfolgreich. Am frühen Dienstagmorgen des 5. Dezember verkündete Tao dass Lean die Vermutung ohne „Sorrys“ bewiesen hatte – die Standardaussage, die erscheint, wenn der Computer einen bestimmten Schritt nicht überprüfen kann. Dies ist die bekannteste Verwendung davon Verifizierungstools seit 2021und markiert einen Wendepunkt in der Art und Weise, wie Mathematiker Beweise in Begriffen schreiben, die ein Computer verstehen kann. Wenn diese Werkzeuge für Mathematiker einfach genug werden, können sie möglicherweise den oft langwierigen und mühsamen Peer-Review-Prozess ersetzen, sagte Gowers.

Die Zutaten für den Beweis brodelten schon seit Jahrzehnten. Gowers plante seine ersten Schritte in den frühen 2000er Jahren. Aber es dauerte 20 Jahre, um zu beweisen, was Kalai als „heiligen Gral“ auf diesem Gebiet bezeichnete.

Die In-Group

Um Martons Vermutung zu verstehen, ist es hilfreich, mit dem Konzept einer Gruppe vertraut zu sein, einem mathematischen Objekt, das aus einer Menge und einer Operation besteht. Denken Sie an die ganzen Zahlen – eine unendliche Menge von Zahlen – und die Additionsoperation. Jedes Mal, wenn Sie zwei ganze Zahlen addieren, erhalten Sie eine weitere ganze Zahl. Die Addition unterliegt auch einigen anderen Regeln für Gruppenoperationen, beispielsweise der Assoziativität, mit der Sie die Reihenfolge der Operationen ändern können: 3 + (5 + 2) = (3 + 5) + 2.

Innerhalb einer Gruppe finden Sie manchmal kleinere Mengen, die alle Gruppeneigenschaften erfüllen. Wenn Sie beispielsweise zwei beliebige gerade Zahlen addieren, erhalten Sie eine weitere gerade Zahl. Die geraden Zahlen sind eine Gruppe für sich und somit eine Untergruppe der ganzen Zahlen. Die ungeraden Zahlen hingegen sind keine Untergruppe. Wenn Sie zwei ungerade Zahlen addieren, erhalten Sie eine gerade Zahl – nicht in der ursprünglichen Menge. Aber Sie können alle ungeraden Zahlen erhalten, indem Sie einfach 1 zu jeder geraden Zahl addieren. Eine solche verschobene Untergruppe wird Nebenklasse genannt. Es verfügt nicht über alle Eigenschaften einer Untergruppe, behält aber in vielerlei Hinsicht die Struktur seiner Untergruppe bei. Beispielsweise haben die ungeraden Zahlen genau wie die geraden Zahlen alle den gleichen Abstand.

Marton ging davon aus, dass wir anrufen würden, wenn Sie ein Set hätten A bestehend aus Gruppenelementen, deren Summe nicht viel größer ist als A selbst, dann gibt es eine Untergruppe – nennen wir sie G – mit einer besonderen Eigenschaft. Schicht G ein paar Mal, um Nebenmengen zu erstellen, und diese Nebenmengen zusammengenommen enthalten die ursprüngliche Menge A. Darüber hinaus nahm sie an, dass die Anzahl der Nebenmengen nicht viel schneller wächst als die Größe der Summenmenge – sie glaubte, dass dies durch einen Polynomfaktor zusammenhängen sollte, im Gegensatz zu einem viel schnelleren exponentiellen Wachstum.

Das mag nach einer hochtechnischen Kuriosität klingen. Da es sich jedoch um einen einfachen Test handelt: Was passiert, wenn Sie der Menge nur zwei Elemente hinzufügen? – für die übergreifende Struktur einer Untergruppe ist es für Mathematiker und Informatiker sehr wichtig. Die gleiche allgemeine Idee zeigt sich, wenn Informatiker versuchen, Nachrichten zu verschlüsseln, sodass man jeweils nur einen Teil der Nachricht entschlüsseln kann. Es kommt auch in probabilistisch überprüfbaren Beweisen vor, einer Beweisform, die Informatiker durch die Überprüfung nur einiger isolierter Informationsbits überprüfen können. In jedem dieser Fälle arbeiten Sie mit nur wenigen Punkten in einer Struktur – indem Sie nur ein paar Bits einer langen Nachricht dekodieren oder einen kleinen Teil eines komplizierten Beweises überprüfen – und schließen daraus etwas über eine größere Struktur auf einer höheren Ebene.

„Man kann entweder so tun, als wäre alles eine große Teilmenge einer Gruppe“, sagte er Tom Sanders, ein ehemaliger Schüler von Gowers, der jetzt ein Kollege von Green in Oxford ist, oder Sie können „alles, was Sie wollten, aus der Existenz vieler additiver Zufälle herausholen.“ Beide Perspektiven sind nützlich.“

Ruzsa veröffentlichte Martons Vermutung im Jahr 1999, was ihr volle Anerkennung zollt. „Sie kam unabhängig von mir und Freiman und wahrscheinlich vor uns zu dieser Vermutung“, sagte er. „Als ich mit ihr sprach, beschloss ich deshalb, es ihre Vermutung zu nennen.“ Dennoch bezeichnen Mathematiker sie heute als polynomische Freiman-Ruzsa-Vermutung oder PFR.

Nullen und Einsen

Gruppen nehmen, wie viele mathematische Objekte, viele verschiedene Formen an. Marton ging davon aus, dass ihre Vermutung für alle Gruppen gilt. Dies muss noch gezeigt werden. Das neue Papier beweist dies für eine bestimmte Art von Gruppe, deren Elemente Listen von Binärzahlen wie (0, 1, 1, 1, 0) sind. Da Computer binär arbeiten, ist diese Gruppe in der Informatik von entscheidender Bedeutung. Aber es hat sich auch in der additiven Kombinatorik als nützlich erwiesen. „Es ist wie in dieser Spielzeugumgebung, in der man herumspielen und Dinge ausprobieren kann“, sagte Sanders. „Die Algebra ist viel, viel schöner“ als die Arbeit mit ganzen Zahlen, fügte er hinzu.

Die Listen haben feste Längen und jedes Bit kann entweder 0 oder 1 sein. Sie addieren sie, indem Sie jeden Eintrag zu seinem Gegenstück in einer anderen Liste hinzufügen, mit der Regel, dass 1 + 1 = 0. Also (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR ist ein Versuch herauszufinden, wie eine Menge aussehen kann, wenn sie keine echte Untergruppe ist, aber einige gruppenähnliche Merkmale aufweist.

Um PFR präziser zu machen, stellen Sie sich vor, Sie hätten eine Reihe von Binärlisten namens A. Nehmen Sie nun jedes Elementpaar aus A und addiere sie. Die resultierenden Summen bilden die Summe von A, Rief A + A. Wenn die Elemente von A werden zufällig ausgewählt, dann unterscheiden sich die meisten Summen voneinander. Wenn es gibt k Elemente in A, das heißt, es wird rund sein k²/2 Elemente im Summensatz. Wann k ist groß – sagen wir 1,000 – k²/2 ist viel größer als k. Aber falls A ist eine Untergruppe, jedes Element von A + A in A, bedeutet, dass A + A hat die gleiche Größe wie A sich.

PFR berücksichtigt Mengen, die nicht zufällig, aber auch keine Untergruppen sind. In diesen Mengen ist die Anzahl der Elemente in A + A ist etwas klein – sagen wir, 10kOder 100k. „Es ist wirklich nützlich, wenn Ihre Vorstellung von Struktur viel umfassender ist als nur eine exakte algebraische Struktur“, sagte er Shachar Lovett, Informatiker an der University of California, San Diego.

Alle den Mathematikern bekannten Mengen, die dieser Eigenschaft gehorchen, „sind ziemlich nahe an tatsächlichen Untergruppen“, sagte Tao. „Das war die Intuition, dass es keine anderen Fake-Gruppen gab.“ Freiman hatte in seinem Originalwerk eine Version dieser Aussage bewiesen. 1999 erweiterte Ruzsa den Satz von Freiman von den ganzen Zahlen auf die Einstellung binärer Listen. Er hat es bewiesen dass, wenn die Anzahl der Elemente in A + A ist ein konstantes Vielfaches der Größe von A, A ist in einer Untergruppe enthalten.

Aber Ruzsas Theorem erforderte eine enorme Untergruppe. Martons Einsicht bestand darin, zu postulieren, dass sie nicht in einer riesigen Untergruppe enthalten sind, sondern A könnte in einer polynomialen Anzahl von Nebenmengen einer Untergruppe enthalten sein, die nicht größer als die ursprüngliche Menge ist A.

„Ich erkenne eine echte Idee, wenn ich eine echte Idee sehe“

Um die Jahrtausendwende stieß Gowers auf Ruzsas Beweise des Freiman-Theorems, als er ein anderes Problem über Mengen untersuchte, die Zeichenfolgen gleichmäßig verteilter Zahlen enthielten. „Ich brauchte so etwas, um Strukturinformationen aus viel lockereren Informationen über eine bestimmte Menge zu gewinnen“, sagte Gowers. „Ich hatte großes Glück, dass Ruzsa vor nicht allzu langer Zeit diesen absolut großartigen Beweis erbracht hat.“

Gowers begann mit der Ausarbeitung eines möglichen Beweises für die Polynomversion der Vermutung. Seine Idee war, mit einem Set zu beginnen A Deren Summe war relativ klein, und manipulierte sie dann allmählich A in eine Untergruppe. Wenn er nachweisen könnte, dass die resultierende Untergruppe der ursprünglichen Menge ähnlich ist A, konnte er leicht zu dem Schluss kommen, dass die Vermutung wahr war. Gowers teilte seine Ideen mit Kollegen, aber niemand konnte sie in einen vollständigen Beweis umwandeln. Obwohl Gowers‘ Strategie in einigen Fällen erfolgreich war, schlugen die Manipulationen in anderen Fällen fehl A weiter von der gewünschten Schlussfolgerung der polynomischen Freiman-Ruzsa-Vermutung entfernt.

Schließlich zog das Feld weiter. Im Jahr 2012, Sanders fast bewiesener PFR. Aber die Anzahl der verschobenen Untergruppen, die er benötigte, lag über dem Polynomniveau, wenn auch nur geringfügig. „Nachdem er das getan hatte, bedeutete das, dass es eine weniger dringende Sache wurde, aber immer noch ein wirklich schönes Problem, das mir sehr am Herzen liegt“, sagte Gowers.

Aber Gowers' Ideen lebten in den Erinnerungen und Festplatten seiner Kollegen weiter. „Da steckt eine echte Idee dahinter“, sagte Green, der auch ein Schüler von Gowers gewesen war. „Ich erkenne eine echte Idee, wenn ich eine echte Idee sehe.“ In diesem Sommer befreiten Green, Manners und Tao endlich die Ideen von Gowers aus ihrem Fegefeuer.

Green, Tao und Manners arbeiteten 37 Seiten intensiv zusammen, bevor sie daran dachten, zu Gowers‘ 20 Jahre alten Ideen zurückzukehren. In einem 23. Juni Krepppapierhatten sie erfolgreich ein Konzept aus der Wahrscheinlichkeitstheorie namens Zufallsvariablen verwendet, um die Struktur von Mengen mit kleinen Summenmengen zu untersuchen. Durch diesen Wechsel konnte die Gruppe ihre Sets raffinierter manipulieren. „Der Umgang mit Zufallsvariablen ist irgendwie viel weniger starr als der Umgang mit Mengen“, sagte Manners. Mit einer Zufallsvariablen „kann ich eine der Wahrscheinlichkeiten um einen kleinen Betrag anpassen und dadurch möglicherweise eine bessere Zufallsvariable erhalten.“

Mit dieser probabilistischen Perspektive könnten Green, Manners und Tao von der Arbeit mit der Anzahl der Elemente in einer Menge zu einer Messung der in einer Zufallsvariablen, einer Größe namens Entropie, enthaltenen Informationen übergehen. Entropie war für die additive Kombinatorik nichts Neues. Tatsächlich, Tao hatte versucht um das Konzept Ende der 2000er Jahre bekannt zu machen. Aber noch hatte niemand versucht, es auf die Polynom-Freiman-Ruzsa-Vermutung anzuwenden. Green, Manners und Tao entdeckten, dass es mächtig war. Aber sie konnten die Vermutung immer noch nicht beweisen.

Als die Gruppe über ihre neuen Ergebnisse nachdachte, wurde ihnen klar, dass sie endlich eine Umgebung geschaffen hatten, in der Gowers‘ schlummernde Ideen gedeihen konnten. Wenn sie die Größe einer Menge anhand ihrer Entropie und nicht anhand ihrer Anzahl an Elementen messen würden, könnten die technischen Details möglicherweise viel besser funktionieren. „Irgendwann wurde uns klar, dass diese alten Ideen von Tim von vor 20 Jahren tatsächlich eher funktionieren würden als die, die wir versuchten“, sagte Tao. „Und so holten wir Tim zurück in das Projekt. Und dann passen alle Teile überraschend gut zusammen.“

Dennoch mussten viele Details geklärt werden, bevor ein Beweis erbracht werden konnte. „Es war irgendwie dumm, dass wir alle vier unglaublich mit anderen Dingen beschäftigt waren“, sagte Manners. „Sie möchten dieses großartige Ergebnis veröffentlichen und es der Welt erzählen, aber Sie müssen eigentlich noch Ihre Zwischenprüfungen schreiben.“ Schließlich setzte sich die Gruppe durch und veröffentlichte am 9. November ihr Papier. Sie haben bewiesen, dass wenn A + A ist nicht größer als k mal so groß A und dann A kann durch nicht mehr als etwa abgedeckt werden k¹² Verschiebungen einer Untergruppe, die nicht größer ist als A. Dies ist möglicherweise eine enorme Anzahl von Schichten. Da es sich jedoch um ein Polynom handelt, wächst es nicht exponentiell schneller als k wird größer, als ob k waren im Exponenten.

Ein paar Tage später, Tao begann zu den Beweis formalisieren. Er leitete das Formalisierungsprojekt gemeinsam und nutzte das Versionskontrollpaket GitHub, um die Beiträge zu koordinieren 25 Freiwillige auf der ganzen Welt. Sie verwendeten ein Werkzeug namens Entwurf entwickelt von Patrick Massot, ein Mathematiker an der Universität Paris-Saclay, um die Bemühungen zu organisieren, das Tao zu übersetzen namens „Mathematisches Englisch“ in Computercode. Blueprint kann unter anderem eine erstellen Tabelle Darstellung der verschiedenen logischen Schritte des Beweises. Sobald alle Blasen mit einem „schönen Grünton“, wie Tao es nannte, bedeckt waren, war das Team fertig. Sie entdeckten ein paar sehr kleine Tippfehler in der Zeitung – in einem Online-Artikel NachrichtTao bemerkte, dass „die mathematisch interessantesten Teile des Projekts relativ einfach zu formalisieren waren, aber es waren die technischen ‚offensichtlichen‘ Schritte, die am längsten dauerten.“

Marton starb nur wenige Jahre bevor ihre berühmte Vermutung bewiesen wurde, aber der Beweis bestätigt sie Lebenswerk zur Entropie- und Informationstheorie. „Alles funktioniert viel besser, wenn man es in diesem Entropie-Framework macht, als in dem Framework, das ich versucht habe“, sagte Gowers. „Für mich wirkt es immer noch etwas magisch.“

Wie viel führt eine Reihe von Umfragen durch, um unser Publikum besser zu bedienen. Nimm unser Leserbefragung Mathematik und Sie nehmen an der kostenlosen Verlosung teil Wie viel Merch.