Das Cap-Set-Problem und FunSearch: Wie ein LLM ein 20 Jahre altes Rätsel löste
~10 min read
CombinatoricsAIFunSearchDeepMindCap SetEllenberg-GijswijtPolynomial Method
Back openDesk Edu for a sovereign, open-source education — every vote counts.
Vote nowSave products you love by clicking the heart icon.
Ein Blick auf die Herkunft, Bedeutung und kulturelle Verschiebung hinter dem Begriff »Vibe Coding« — und warum ausgerechnet »Vibe« das richtige Wort war.
Unter den offenen Problemen der additiven Kombinatorik gibt es eines, das durch seine Eleganz und seine Hartnäckigkeit gleichermaßen besticht: das Cap-Set-Problem. Terence Tao nannte es einst seinen "perhaps favourite open question", und das aus gutem Grund. Die Fragestellung lässt sich in einem Satz formulieren, aber ihre Lösung hat einige der tiefsten Werkzeuge der modernen Mathematik hervorgebracht.
Im Dezember 2023 erschien dann ein Ergebnis, das das Feld auf eine völlig neue Art erschütterte. FunSearch, ein System von DeepMind, verbesserte eine 20 Jahre alte untere Schranke für das Problem, und es tat dies nicht durch einen neuen mathematischen Beweis, sondern durch evolutionäre Programmsuche mit einem Sprachmodell. DieIronie der Geschichte: Jordan Ellenberg, einer der Autoren des FunSearch-Papiers, war bereits 2016 an dem Durchbruch der oberen Schranke beteiligt. Derselbe Mensch half also, das Problem von beiden Seiten einzukreisen.
Ein Cap-Set ist eine Teilmenge C des Vektorraums F₃ⁿ (dem n-dimensionalen Vektorraum über dem Körper mit drei Elementen ), die keine drei kollinearen Punkte enthält. Formell bedeutet das: es gibt keine drei verschiedenen Elemente x, y, z ∈ C mit x + y + z = 0. Da wir in F₃ arbeiten, ist das äquivalent zu der Bedingung, dass kein arithmetictripel existiert, also keine drei Punkte auf einer Geraden liegen.
Jeder, der das Kartenspiel "Set" gespielt hat, hat bereits intuitiv mit Cap-Sets gearbeitet. Jede Set-Karte hat vier Eigenschaften (Farbe, Form, Füllung, Anzahl), jede mit drei Ausprägungen. Eine Karte lässt sich also als Vektor in F₃⁴ darstellen. Drei Karten bilden genau dann ein "Set", wenn die entsprechenden Vektoren kollinear sind, also x + y + z = 0 erfüllen. Eine Cap-Set-Menge entspricht einer Handvoll Karten, in der sich kein einziges Set finden lässt.
Die zentrale Frage lautet: Wie groß kann eine solche menge maximal sein? Definieren wir r₃(n) als die Größe des größten Cap-Sets in F₃ⁿ. Die Kapazität C des Problems ist dann definiert als:
C = lim_{n → ∞} r₃(n)^{1/n}
Dieser Grenzwert existiert nach einem Subadditivitätsargument und gibt die "exponentielle Wachstumsrate" der maximalen Cap-Set-Größe an.
Für kleine Dimensionen sind die exakten Werte bekannt:
| n | r₃(n) | Fund |
|---|---|---|
| 1 | 2 | |
| 2 | 4 | Alle Vektoren außer (0,0) |
| 3 | 9 | Affin-unabhängiges System |
| 4 | 20 | 1971, Pellegrino |
| 5 | 45 | 1993, Edel |
| 6 | 112 | 2002, Edel |
| ≥7 | ? | Unbekannt |
Ab n = 7 wird es rasend schwer. Die Lücke zwischen oberer und unterer Schranke ist gewaltig: Wir wissen, dass C ≤ 2.756 liegt (Ellenberg-Gijswijt 2016), aber die beste untere Schranke ist C ≥ 2.2202 (FunSearch 2023). Der gesamte Bereich dazwischen ist terra incognita.
| Jahr | Autor | Schranke | Methode |
|---|---|---|---|
| trivial | - | 2ⁿ | Nur pro Koordinate wählen |
| 2004 | Edel | 2.2173ⁿ | Algebraische Konstruktion |
| 2022 | Tyrrell | 2.2180ⁿ | SAT-Solver |
| Dez. 2023 | FunSearch | 2.2202ⁿ | LLM + evolutionärer Algorithmus |
| Jahr | Autor | Schranke | Methode |
|---|---|---|---|
| 1995 | Meshulam | O(3ⁿ/n) | Fourier-analytisch |
| 2012 | Bateman-Katz | O(3ⁿ/n^) | Fourier + Polynommethode |
| 2016 | Ellenberg-Gijswijt | 2.756ⁿ | Polynommethode |
Der Sprung von 2002 (O(3ⁿ/n)) zu 2016 (2.756ⁿ) war dramatisch. Die Exponentialbasis fiel von 3 auf unter 2.76, was bedeutet, dass Cap-Sets exponentiell klein sein müssen. Die Cap-Set-Vermutung war damit bewiesen.
Im Mai 2016 publizierten Ernie Croot, Vsevolod Lev und Péter Pach ein Ergebnis, das auf den ersten Blick gar nichts mit Cap-Sets zu tun hatte. Sie bewiesen, dass progressionfreie Mengen in Z₄ⁿ exponentiell klein sein müssen. Der Beweis nutzte eine elegante Idee: Man konstruiert ein Polynom, das auf der gegebenen Menge verschwindet, zerlegt es in Monome und zählt die Koeffizienten.
Jordan Ellenberg und Dion Gijswijt erkannten innerhalb von nur zehn Tagen, wie sich die Croot-Lev-Pach-Methode auf F₃ⁿ übertragen lässt. Das Resultat war ein Beweis, der auf ganzen drei Seiten passte und eine der am längsten offenen Vermutungen der Kombinatorik löste.
Die Kernidee ist überschaubar:
f_A(x) = ∏_{a ∈ A} (1 - (x₁ - a₁)^{q-1} · (x₂ - a₂)^{q-1} · ... · (xₙ - aₙ)^{q-1})
Die konkrete Schranke ergibt sich aus der Optimierung: Man maximiert die Summe der größten Multinomialkoeffizienten unter der Nebenbedingung, dass alle Exponenten ≤ 2(q-1)/3 sind. Für q = 3 liefert das die magische Zahl 2.756.
Tim Gowers, Fields-Medaillist, kommentierte: "I could sit down and understand the proof in half an hour." So zugänglich war die Kombinatorik selten.
2019 formalisierten Sander Dahmen, Johannes Hölzl und Robert Y. Lewis den gesamten Beweis in dem Beweisassistenten Lean. Ein Meilenstein für die mathematische Informatik und ein Beweis dafür, dass selbst moderne Forschungsergebnisse maschinell verifiziert werden können.
FunSearch steht für "searching in the function space". Die Grundidee ist bestechend einfach: Anstatt nach Lösungen zu suchen, sucht man nach Programmen, die Lösungen generieren. Ein Sprachmodell erzeugt Programmvarianten, eine Evaluationsfunktion bewertet sie, und ein evolutionärer Prozess wählt die besten aus.
Die Arbeit erschien im Dezember 2023 in Nature (Band 625, Seiten 468-475), was die Bedeutung des Ansatzes unterstreicht.
evaluate()-Funktion, einer solve()-Funktion und einer mit @funsearch.evolve markierten Funktion, die vom System verbessert werden soll.Der Ablauf sieht so aus:
Die Selektion nutzt Softmax mit einer annealing-Temperatur über Programm-Cluster und bevorzugt kürzere Programme, was eine Art impliziter Regularisierung darstellt.
FunSearch formuliert das Cap-Set-Problem als Greedy-Konstruktion mit einer zu entwickelnden priority()-Funktion. Der Algorithmus geht alle Vektoren in F₃ⁿ durch und fügt sie in absteigender Priorität zu einer Menge hinzu, sofern sie kein Tripel bilden. Die Kunst besteht darin, eine Prioritätsfunktion zu finden, die die richtige Insertionsreihenfolge wählt.
Für n = 8 fand FunSearch ein Cap-Set der Größe 512. Der bisherige Rekord lag bei 496. Das ist die größte Verbesserung der unteren Schranke seit etwa 20 Jahren.
Das ist der Code, den FunSearch generierte:
def priority(el: tuple[int, ...], n: int) -> float:
score = n
in_el = 0
el_count = el.count(0)
if el_count == 0:
score += n ** 2
if el[1] == el[-1]:
score *= 1.5
if el[2] == el[-2]:
score *= 1.5
if el[3] == el[-3]:
score *= 1.5
else:
if el[1] == el[-1]:
score *= 0.5
if el[2] == el[-2]:
score *= 0.5
for e in el:
if e == 0:
if in_el == 0:
score *= n * 0.5
elif in_el == el_count - 1:
score *= 0.5
else:
score *= n * 0.5 ** in_el
in_el += 1
else:
score += 1
if el[1] == el[-1]:
score *= 1.5
if el[2] == el[-2]:
score *= 1.5
return score
Ellenberg fiel bei der Analyse des generierten Codes ein strukturelles Muster auf: Das Programm prüft wiederholt, ob der zweite Eintrag dem vorletzten entspricht (el[1] == el[-1], el[2] == el[-2]). Das ist eine Spiegelsymmetrie, die mathematisch nutzbar ist. Vektoren mit dieser Eigenschaft bilden eine besondere Teilstruktur in F₃ⁿ, und die Prioritätsfunktion nutzt sie geschickt aus.
Hier zeigt sich das wahre Potenzial des Ansatzes. Die KI entdeckt ein Programm. Menschen analysieren es, verstehen die zugrundeliegende mathematische Struktur, und können sie dann manuell erweitern und verbessern. FunSearch fand eine admittable Menge I(12, 7), die eine Schranke von 2.2184ⁿ lieferte. Durch Ellenbergs manuelle Analyse der Spiegelsymmetrie wurde das auf 2.2202ⁿ verbessert.
Das ist kein Ersatz für Mathematiker, sondern ein neues Werkzeug in ihrem Arsenal.
Das Cap-Set-Problem steht nicht isoliert. Es verknüpft sich mit einigen der tiefsten offenen Fragen der Mathematik und Informatik.
Die Sunflower-Vermutung (Erdős und Rado, 1960) besagt, dass jede ausreichend große Familie von Mengen eine "Sunflower" (Blüte) enthält: drei Mengen, deren paarweise Schnittmengen alle gleich sind. Der Ellenberg-Gijswijt-Beweis für Cap-Sets führte 2017 unmittelbar zu einer Teillösung durch Naslund und Sawin. Der gleiche polynomialtechnische Ansatz funktioniert in beiden Kontexten.
Die Methode von Cohn und Umans zur Konstruktion schneller Matrixmultiplikationsalgorithmen steht in enger Verbindung zu Cap-Sets. Die obere Schranke für Cap-Sets schränkt die Größe gewisser Gruppenkonstruktionen ein, die wiederum die Komplexität der Matrixmultiplikation bestimmen. Bessere Cap-Set-Schranken könnten also theoretisch zu schnelleren Matrixmultiplikationsalgorithmen führen.
Das Cap-Set-Problem ist der endliche-Körper-Analogon von Roths Satz über arithmetische Progressionen der Länge 3 in den ganzen Zahlen. Roths Satz besagt, dass jede Teilmenge der natürlichen Zahlen mit positiver oberer Dichte eine 3-elementige arithmetische Progression enthält. Szemerédi verallgemeinerte dies auf beliebige Progressionslängen. Das Cap-Set-Problem fragt nach dem analogen Ergebnis in F₃ⁿ.
Der Games-Graph mit 729 Knoten (ein stark regulärer Graph mit bemerkenswerten Eigenschaften) entsteht aus dem eindeutigen 56-Punkt-Cap-Set in F₃⁶. Diese Verbindung zwischen Cap-Sets und algebraischer Graphentheorie ist seit langem bekannt und liefert eine der schönsten Anwendungen der Theorie.
AlphaEvolve, der Nachfolger von FunSearch, nutzt Gemini-Sprachmodelle anstelle von PaLM 2 und arbeitet mit vollständigen Codebasen statt einzelner Funktionen. Das System hat bereits bemerkenswerte Ergebnisse erzielt, darunter Algorithmen für die Multiplikation 4×4 komplexer Matrizen mit nur 48 Multiplikationen. Das ist die erste Verbesserung gegenüber Strassens Algorithmus seit 56 Jahren.
EvoTune erweitert den evolutionären Ansatz um Reinforcement Learning, genauer gesagt Direct Preference Optimization (DPO). Die generierten Programme werden nicht nur evaluiert, sondern das Sprachmodell wird aktiv durch die Ergebnisse trainiert, was die Qualität der generierten Varianten über die Zeit verbessert.
FunSearchs untere Schranke von 2.2202ⁿ steht immer noch. Zwei Jahre nach der Veröffentlichung hat niemand eine bessere Schranke gefunden, weder mit klassischen Methoden noch mit KI-Unterstützung. Die Lücke zwischen 2.2202ⁿ und 2.756ⁿ bleibt enorm.
Das Cap-Set-Problem illustriert auf exemplarische Weise, wie menschliche mathematische Intuition und KI-gestützte Exploration sich ergänzen können. Die Polynommethode von 2016 beantwortete die Frage "Sind Cap-Sets exponentiell klein?" mit einem klaren Ja. FunSearch von 2023 schob die Frage "Wie klein genau?" ein Stück weiter in Richtung der Wahrheit.
Die Mensch-KI-Schleife ist der Schlüssel: Die KI erkundet den Lösungsraum auf Weise, die einem Menschen nicht auffallen würde, und die Menschen interpretieren die Ergebnisse, erkennen Muster und erweitern sie manuell. Weder die KI allein noch der Mensch allein wäre zu diesen Ergebnissen gekommen.
Die exakte Kapazität C bleibt unbekannt. Die Lücke zwischen 2.2202ⁿ und 2.756ⁿ ist immer noch gewaltig. Aber die Werkzeuge, die wir heute haben, sind mächtiger als je zuvor. Die nächsten Jahre werden zeigen, ob die Kombination aus Polynommethode und evolutionärer Programmsuche die Lücke weiter schließen kann.