Save products you love by clicking the heart icon.
We use privacy-friendly analytics (Plausible + Umami) to understand how visitors use this site. No analytics are loaded without your consent. Privacy Policy
Das Cap-Set-Problem und FunSearch: Wie ein LLM ein 20 Jahre altes Rätsel löste | Articles | Tobias Weiss
Das Cap-Set-Problem und FunSearch: Wie ein LLM ein 20 Jahre altes Rätsel löste
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.
Was ist das Cap-Set-Problem?
Definition
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.
Die Verbindung zum Kartenspiel Set
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.
Bekannte exakte Werte
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
Never miss a deep-dive
Get notified when I publish new articles on AI infrastructure, DevOps, and XR development.
· ~8 min read
Wieso heißt Vibe Coding eigentlich Vibe Coding?
Ein Blick auf die Herkunft, Bedeutung und kulturelle Verschiebung hinter dem Begriff »Vibe Coding« — und warum ausgerechnet »Vibe« das richtige Wort war.
AIVibe CodingSoftware Development
≥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.
Die Geschichte der Schranken
Untere Schranken (wie groß kann ein Cap-Set sein?)
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
Obere Schranken (wie klein muss ein Cap-Set sein?)
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.
Der Durchbruch 2016: Die Polynommethode
Croot-Lev-Pach: Der Auslöser
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.
Ellenberg und Gijswijt passen die Methode an
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:
Sei A ⊆ F₃ⁿ ein Cap-Set. Wir betrachten das Polynom
Dieses Polynom hat Grad ≤ n(q-1) und verschwindet auf A.
Man zerlegt f in seine Monomanteile und nutzt, dass die Nullstellenmenge die Struktur von A erzwingt.
Das zählt man ab und erhält die obere Schranke.
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.
Formalisierung in Lean
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: Evolutionäre Programmsuche mit LLMs
Die Kernidee
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.
Die sechs Komponenten von FunSearch
Problemspezifikation: Ein Python-Skelett mit einer evaluate()-Funktion, einer solve()-Funktion und einer mit @funsearch.evolve markierten Funktion, die vom System verbessert werden soll.
Vortrainiertes Sprachmodell: DeepMind nutzte Codey (auf Basis von PaLM 2), eingefroren, kein Fine-Tuning.
Best-Shot-Prompting: Aus dem aktuellen Pool werden die k = 2 besten Programme als Beispiele in den Prompt eingefügt. Das Modell vervollständigt daraus eine neue Variante.
Island-Modell: Mehrere unabhängige Subpopulationen ("Inseln"). Alle vier Stunden werden die schlechtesten 50% der Inseln zurückgesetzt, um Stagnation zu vermeiden.
Sandbox-Evaluator: Jedes Programm läuft in einer isolierten Umgebung mit 30-Sekunden-Timeout. Rekursive Aufrufe werden abgelehnt.
Der evolutionäre Zyklus
Der Ablauf sieht so aus:
Wähle eine Insel aus dem Pool.
Wähle die k = 2 besten Programme von dieser Insel.
Baue einen Prompt aus dem Problemskelett und den beiden Programmen.
Das LLM generiert eine neue Programmvariante.
Evaluiere die Variante in der Sandbox.
Wenn sie gültig und besser ist, füge sie zum Pool hinzu.
Alle vier Stunden: Reset der unteren Hälfte der Inseln.
Die Selektion nutzt Softmax mit einer annealing-Temperatur über Programm-Cluster und bevorzugt kürzere Programme, was eine Art impliziter Regularisierung darstellt.
FunSearch und das Cap-Set-Problem
Die Formulierung
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.
Das Ergebnis
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.
Die entdeckte Prioritätsfunktion
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
Die Spiegelsymmetrie
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.
Die Mensch-KI-Schleife
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.
Verbindungen zu anderen Problemen
Das Cap-Set-Problem steht nicht isoliert. Es verknüpft sich mit einigen der tiefsten offenen Fragen der Mathematik und Informatik.
Die Sunflower-Vermutung
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.
Matrixmultiplikation
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.
Roths Satz und der Satz von Szemerédi
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₃ⁿ.
Stark reguläre Graphen
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.
Das größere Bild: AlphaEvolve und darüber hinaus
AlphaEvolve (2025)
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 (2025)
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.
Stand der Dinge (April 2026)
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.
Fazit
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.
Quellen
Romera-Paredes, B. et al. "Mathematical discoveries from program search with large language models." Nature 625, 468-475 (2023). DOI: 10.1038/s41586-023-06924-6
Ellenberg, J. & Gijswijt, D. "On large subsets of F_q^n with no three-term arithmetic progression." arXiv:1605.09223 (2016).
Croot, E., Lev, V. & Pach, P.P. "Progression-free sets in Z_4^n are exponentially small." arXiv:1605.01506 (2016).
Tyrrell, F. "New lower bounds for cap sets." Discrete Analysis (2022).
Croot, Lev, Pach. "Past and future of the cap set problem." arXiv:2408.02328 (2024).