Manchmal gerät die Addition außer Kontrolle. Wenn man eine Sammlung von zufälligen Zahlen paarweise addiert, ergibt sich eine Menge, die meist viel mehr Zahlen enthält als die ursprüngliche Zusammenstellung. Angenommen, man startet mit zehn zufälligen Zahlen, dann wird die so genannte Summenmenge etwa 50 Elemente enthalten. Beginnt man mit 100 zufälligen Werten, besteht die Summenmenge aus grob 5000 Elementen; 1000 Zufallszahlen führen zu einer Summenmenge mit 500 000 Zahlen. Und so weiter.

Wenn die anfängliche Menge jedoch strukturiert ist, kann die Summenmenge sogar kleiner ausfallen als die ursprüngliche. Für die Menge aller geraden Zahlen von 2 bis 20 ergeben zum Beispiel verschiedene Paare dieselbe Summe: 10 + 12 ist dasselbe wie 8 + 14 und 6 + 16. In diesem Fall besteht die Summenmenge nur aus 19 Zahlen, nicht 50. Der Unterschied zwischen zufälligen und strukturierten Mengen wird deutlicher, je größer die Mengen sind.

In den 1960er Jahren untersuchte der Mathematiker Gregory Freiman Mengen mit kleinen Summenmengen, um den Zusammenhang zwischen Addition und Mengenstruktur zu ergründen – eine Verbindung, die das mathematische Gebiet der additiven Kombinatorik definiert. Freiman konnte beweisen, dass Mengen mit kleinen Summenmengen Teil einer größeren Menge sind, deren Elemente ein regelmäßiges Muster besitzen. Doch dann stagnierte das Gebiet. »Freimans ursprünglicher Beweis war außerordentlich schwer zu verstehen, bis zu dem Punkt, an dem niemand wirklich sicher war, ob er korrekt war. Die Arbeit hatte also nicht den Einfluss, den sie hätte haben können«, sagt der Mathematiker und Fields-Medaillen-Gewinner Timothy Gowers vom Collège de France und der University of Cambridge. »Doch dann kam Imre Ruzsa.«

In den 1990er Jahren bewies der ungarische Mathematiker Ruzsa in zwei Arbeiten erneut Freimans Theorem mittels eines neuen, eleganten Arguments. Einige Jahre später ging die 2019 verstorbene ungarische Mathematikerin Katalin Marton der Frage nach, was eine kleine Summenmenge über die Struktur der ursprünglichen Menge aussagt. Dabei formulierte sie eine tief greifende Vermutung, die Verbindungen zu Beweissystemen, Codierungstheorie und Kryptografie hat und einen wichtigen Platz in der additiven Kombinatorik einnimmt. »Ihre Vermutung fühlt sich wie eine absolut grundlegende Sache an, die wir nicht verstanden haben«, stellt der Mathematiker Ben Green von der University of Oxford fest.

Green schloss sich mit Gowers, Freddie Manners von der University of California in San Diego sowie dem Fields-Medaillen-Gewinner Terence Tao von der University of California in Los Angeles zu einem »A-Team« zusammen, wie es der israelische Mathematiker und Blogger Gil Kalai nannte. Gemeinsam bewiesen sie am 9. November 2023 eine Version von Martons Vermutung. »Dieses Ergebnis kam mehr oder weniger aus heiterem Himmel«, sagt der Mathematiker Nets Katz von der Rice University, der nicht an der Arbeit beteiligt war.

Die wesentlichen Ideen für den Beweis hatte Gowers schon vor mehreren Jahrzehnten konzipiert. Aber es dauerte mehr als 20 Jahre, um den »Heiligen Gral des Fachgebiets« tatsächlich zu finden und einen lückenlosen Beweis zu formulieren.

Tao begann kurz darauf, die Arbeit in Lean zu formalisieren, einer Programmiersprache, mit der sich mathematische Ergebnisse durch Computer verifizieren lassen. Am Dienstagmorgen des 5. Dezember 2023 gab Tao bekannt, dass Lean die Vermutung bestätigt hat. Das ist einer der bedeutendsten Einsätze eines solchen computergestützten Beweisassistenten. Wenn diese Werkzeuge einfach genug für die Nutzung werden, könnten Computer laut Gowers das oft langwierige und lästige Peer-Review-Verfahren ersetzen.

Eine weit reichende Vermutung

Martons Vermutung hängt mit dem mathematischen Konzept einer Gruppe zusammen. Diese symbolisiert meist eine symmetrische Struktur. Eine Gruppe besteht aus einer Menge und einer Operation. Ein Beispiel dafür sind die ganzen Zahlen (…, –3, –2, –1, 0, 1, 2, 3, …) und die Addition. Wenn man zwei ganze Zahlen addiert, ergibt sich daraus wieder eine ganze Zahl. Zudem erfüllt die Addition die anderen Gruppenregeln wie Assoziativität, mit der man die Reihenfolge der Operationen ändern kann, zum Beispiel: 3 + (5 + 2) = (3 + 5) + 2.

Innerhalb einer Gruppe kann man manchmal kleinere Mengen finden, die ebenfalls alle Gruppeneigenschaften erfüllen. Wenn man zum Beispiel zwei gerade Zahlen addiert, erhält man wieder eine gerade Zahl. Demnach bilden die geraden Zahlen eine Gruppe für sich und sind damit eine »Untergruppe« der ganzen Zahlen. Die ungeraden Zahlen sind hingegen keine Untergruppe, da die Summe zweier ungerader Zahlen ein gerades Ergebnis liefert – und dieses ist nicht in der ursprünglichen Menge (den ungeraden Zahlen) enthalten. Addiert man jedoch 1 zu den geraden Ergebnissen, dann kann man alle ungeraden Zahlen erhalten. Eine solche verschobene Untergruppe wird als Nebenklasse bezeichnet. Diese hat nicht alle Eigenschaften einer Untergruppe, doch sie behält in vielerlei Hinsicht die Struktur ihrer Untergruppe bei. So sind etwa die ungeraden Zahlen genau wie die geraden Zahlen gleichmäßig verteilt.

Martons Vermutung lautet: Wenn eine Menge A aus Elementen besteht, deren Summenmenge nicht viel größer ist als A, dann gibt es eine Untergruppe G mit einer besonderen Eigenschaft: Verschiebt man G ein paar Mal, um Nebenklassen zu bilden, enthalten diese zusammengenommen die ursprüngliche Menge A. Damit besitzen die Elemente von A eine gewisse Symmetrie. Außerdem vermutete Marton, dass die Anzahl der Nebenklassen nicht viel schneller anwächst als die Größe der Summenmenge – sie glaubte, dass beide über einen polynomialen Faktor zusammenhängen.

Die Vermutung mag sehr abstrakt klingen, aber sie verbindet eine einfache Frage – was passiert, wenn man zwei Elemente in der Menge addiert? – mit der übergreifenden Struktur einer Untergruppe. Das macht die Vermutung für die Mathematik sehr interessant – und für die Informatik. Denn dort taucht eine ähnliche Idee auf, wenn man Nachrichten so verschlüsselt, dass sich jeweils nur ein Teil davon entschlüsseln lässt. Außerdem erscheint der Ansatz in bestimmten Beweisen, die sich verifizieren lassen, indem man nur einige wenige isolierte Bits an Informationen überprüft. In diesen Fällen arbeitet man mit wenigen Details – man entschlüsselt lediglich ein paar Bits einer langen Nachricht oder überprüft einen kleinen Teil eines komplizierten Beweises – und schließt daraus auf eine größere, übergeordnete Struktur.

»Man kann entweder so tun, als sei alles eine große Teilmenge einer Gruppe«, sagt Tom Sanders, ein ehemaliger Student von Gowers, der jetzt mit Green in Oxford arbeitet, »oder man kann alles aus der Existenz vieler Additionen schließen. Beide Sichtweisen sind nützlich.«

Diese Vermutung wurde nicht von Marton selbst, sondern im Jahr 1999 von Ruzsa veröffentlicht. »Sie kam unabhängig vor mir und Freiman zu dieser Vermutung«, berichtet er. »Ich beschloss deshalb, sie nach ihr zu benennen. Dennoch wird sie inzwischen als polynomiale Freiman-Ruzsa-Vermutung oder PFR-Vermutung bezeichnet.«

Ein Beweis für Nullen und Einsen

Gruppen können viele verschiedene Formen annehmen. Marton nahm an, dass ihre Vermutung für alle Gruppen gilt. Ein Beweis dafür steht noch aus. Die neue Arbeit betrifft nur eine bestimmte Art von Gruppe, deren Elemente aus Folgen von Binärzahlen wie (0, 1, 1, 1, 1, 0) bestehen. Da Computer im Binärsystem arbeiten, ist diese Gruppe in der Informatik von entscheidender Bedeutung. Aber auch in der additiven Kombinatorik ist sie nützlich. »Die Gruppe ist wie ein Spielzeug, mit dem man Dinge ausprobieren kann«, sagt Sanders. »Die Algebra ist viel, viel angenehmer als bei ganzen Zahlen.«

Die Folgen haben eine feste Länge, und jedes Bit kann entweder die Werte 0 oder 1 annehmen. Man kann die Listen addieren, indem man jeden Eintrag zu seinem Gegenstück summiert, wobei 1 + 1 = 0 ergibt. Beispielsweise entspricht (0, 1, 1, 1, 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). Marton wollte herausfinden, wie eine Menge aussehen kann, die zwar keine Untergruppe ist, aber gruppenähnliche Merkmale aufweist.

Angenommen, es gibt eine Menge A mit binären Folgen. Nun nimmt man jedes Paar von Elementen aus A und addiert sie. Die Ergebnisse bilden die Summenmenge, genannt A + A. Wenn die Elemente von A zufällig ausgewählt wurden, dann unterscheiden sich die meisten addierten Werte voneinander. Besitzt die Menge A insgesamt \(k\) Elemente, dann besteht die Summenmenge aus etwa \(\frac{k^2}{2}\) Elementen. Falls A hingegen eine Untergruppe ist, dann ist jedes Element von A + A in A enthalten, wodurch A + A genau so groß ist wie A selbst.

Die PFR-Vermutung dreht sich um Mengen, die weder völlig zufällig noch strukturierte Untergruppen sind. In diesen ist die Anzahl der Elemente in A + A eher klein und beträgt etwa \(10k\) oder \(100k\). Laut der Vermutung hängt die Summenmenge mit einer Untergruppe über Nebenklassen zusammen.

Alle bekannten Mengen, deren Summenmengen nicht viel größer sind als sie selbst, »sind ziemlich nah an tatsächlichen Untergruppen«, erklärt Tao. »Deswegen nahm man an, dass es keine anderen, ›falschen‹ Gruppen gibt, die eine solche Eigenschaft haben.« Freiman hatte eine Version dieser Aussage in seiner ursprünglichen Arbeit bewiesen: Falls die Anzahl der Elemente in A + A um ein Vielfaches größer ist als A, dann ist A in einer Untergruppe enthalten. 1999 erweiterte Ruzsa das Theorem auf den Bereich binärer Listen.

»Ich hatte das große Glück, dass Ruzsa kurz zuvor diesen absolut herausragenden Beweis geliefert hatte«Timothy Gowers, Mathematiker

Das Theorem von Ruzsa setzt jedoch voraus, dass die Untergruppe riesig ist. Martons Einsicht bestand darin, dass A nicht in einer riesigen Untergruppe enthalten sein muss, sondern zu einer polynomiellen Anzahl von Nebenklassen einer Untergruppe gehört, die nicht größer als die ursprüngliche Menge A ist.

Ein Plan schlägt fehl

Um die Jahrtausendwende stieß Gowers auf Ruzsas Arbeiten, als er sich mit einem anderen Problem beschäftigte. Er untersuchte damals Mengen, die Folgen mit gleichmäßig verteilten Zahlen enthielten. »Ich brauchte so etwas wie PFR, um strukturelle Informationen über eine bestimmte Menge zu erhalten«, erzählt Gowers. »Ich hatte das große Glück, dass Ruzsa kurz zuvor diesen absolut herausragenden Beweis geliefert hatte.«

Gowers begann mit der Ausarbeitung eines möglichen Beweises der Vermutung. Seine Idee bestand darin, mit einer Menge A zu starten, deren Summenmenge relativ klein ist, und dann A schrittweise in eine Untergruppe zu verwandeln. Wenn er beweisen konnte, dass die resultierende Untergruppe der ursprünglichen Menge A ähnelt, ließe sich folgern, dass die PFR-Vermutung wahr ist. Gowers teilte seine Ideen mit Kolleginnen und Kollegen, aber niemand konnte sie zu einem vollständigen Beweis ausbauen. Obwohl Gowers' Strategie in einigen Fällen erfolgreich war, führten die Schritte manchmal dazu, dass sich A von der gewünschten Schlussfolgerung entfernte. Er steckte fest.

2012 hätte Sanders beinahe die PFR-Vermutung bewiesen. Die Anzahl der von ihm benötigten verschobenen Untergruppen lag jedoch über der Polynomgrenze – wenn auch nur ein kleines Stück. »Als er das geschafft hatte, wurde das Problem weniger dringlich«, sagt Gowers.

Dennoch lebten Gowers' ursprüngliche Ideen zur Lösung des Problems in den Erinnerungen seiner Kollegen weiter. Im Sommer 2023 gelang es Green, Manners und Tao schließlich, Gowers' Ansatz nachzugehen.

Die drei Mathematiker hatten bereits 37 Seiten zu dem Thema zu Papier gebracht, bevor sie auf die 20 Jahre alten Ideen von Gowers zurückkamen. In einer im Juni 2023 veröffentlichten Arbeit hatten sie erfolgreich ein Konzept aus der Wahrscheinlichkeitstheorie verwendet, so genannte Zufallsvariablen, um die Struktur von Mengen mit kleinen Summenmengen zu untersuchen. »Der Umgang mit Zufallsvariablen ist irgendwie viel weniger starr als mit Mengen«, stellt Manners fest.

Anstatt die Anzahl der Elemente in einer Menge zu untersuchen, widmeten sich Green, Manners und Tao der in einer Zufallsvariablen enthaltenen Information – eine Größe, die Entropie genannt wird. Die Entropie war für Forschende der additiven Kombinatorik nicht neu, Tao hatte das Konzept bereits in den 2000er Jahren etabliert. Allerdings hatte bis dahin niemand versucht, Entropie auf die PFR-Vermutung anzuwenden. Der Ansatz schien viel versprechend, aber die Mathematiker konnten die Vermutung immer noch nicht beweisen.

Doch dann erkannten die Forscher, dass sie endlich eine Umgebung geschaffen hatten, in der Gowers' schlummernde Ideen gedeihen konnten. Wenn man die Größe einer Menge anhand ihrer Entropie anstatt der Anzahl ihrer Elemente beschreibt, funktionieren die technischen Details viel besser. »Irgendwann wurde uns klar, dass diese alten Ideen von vor 20 Jahren eher funktionieren würden als die, die wir gerade ausprobierten«, sagt Tao. »Und so holten wir Tim zurück ins Projekt. Und dann passte alles erstaunlich gut zusammen.«

»Man möchte dieses großartige Ergebnis veröffentlichen und der Welt mitteilen, aber eigentlich musste ich noch meine Zwischenprüfungen schreiben«Freddie Manners, Mathematiker

Dennoch gab es noch viele Details zu klären, bevor der Beweis gelang. »Es war irgendwie dumm, dass wir alle vier mit anderen Dingen beschäftigt waren«, erinnert sich Manners. »Man möchte dieses großartige Ergebnis veröffentlichen und der Welt mitteilen, aber eigentlich musste ich noch meine Zwischenprüfungen schreiben.« Doch schließlich veröffentlichte die Gruppe am 9. November ihre Arbeit, in der sie Folgendes bewies: Wenn A + A nicht größer ist als das \(k\)-Fache der Größe von A, dann kann A durch höchstens \(k^{12}\) Verschiebungen einer Untergruppe abgedeckt werden, die nicht größer ist als A. Das können zwar immer noch extrem viele Verschiebungen sein – aber deren Anzahl wächst bloß polynomiell mit der Größe von \(k\) an.

Ein paar Tage später begann Tao, den Beweis zu formalisieren. Er nutzte dabei die Plattform GitHub, um die Beiträge von 25 Freiwilligen aus aller Welt zu koordinieren. Sie verwendeten ein Programm namens Blueprint des Mathematikers Patrick Massot von der Université Paris-Saclay, um das »mathematische Englisch« in Computercode zu übersetzen. Blueprint kann unter anderem Diagramme erstellen, welche die verschiedenen logischen Schritte eines Beweises visualisieren. Das Team entdeckte ein paar kleine Tippfehler in der ursprünglichen Arbeit – aber konnte schließlich belegen, dass die Lösung korrekt war.

»Für mich hat das immer noch etwas Magisches«Timothy Gowers, Mathematiker

Marton starb nur wenige Jahre, bevor ihre berühmte Vermutung bewiesen wurde. Der Beweis der PFR-Vermutung spiegelt ihr Lebenswerk über Entropie und Informationstheorie wider. »Alles funktioniert viel besser, wenn man es in diesem Entropie-Rahmen macht«, sagt Gowers. »Für mich hat das immer noch etwas Magisches.«