Das Cap-Set-Problem und FunSearch: Wie ein LLM ein 20 Jahre altes Rätsel löste

Einleitung

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
≥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:

1. Sei A ⊆ F₃ⁿ ein Cap-Set. Wir betrachten das Polynom

f_A(x) = ∏_{a ∈ A} (1 - (x₁ - a₁)^{q-1} · (x₂ - a₂)^{q-1} · ... · (xₙ - aₙ)^{q-1})

2. Dieses Polynom hat Grad ≤ n(q-1) und verschwindet auf A.
3. Man zerlegt f in seine Monomanteile und nutzt, dass die Nullstellenmenge die Struktur von A erzwingt.
4. 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

1. Problemspezifikation: Ein Python-Skelett mit einer evaluate()-Funktion, einer solve()-Funktion und einer mit @funsearch.evolve markierten Funktion, die vom System verbessert werden soll.
2. Vortrainiertes Sprachmodell: DeepMind nutzte Codey (auf Basis von PaLM 2), eingefroren, kein Fine-Tuning.
3. 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.
4. Island-Modell: Mehrere unabhängige Subpopulationen ("Inseln"). Alle vier Stunden werden die schlechtesten 50% der Inseln zurückgesetzt, um Stagnation zu vermeiden.
5. Verteiltes System: 15 GPU-Sampler generieren Programmvarianten, 150 CPU-Evaluatoren bewerten sie parallel.
6. 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:

1. Wähle eine Insel aus dem Pool.
2. Wähle die k = 2 besten Programme von dieser Insel.
3. Baue einen Prompt aus dem Problemskelett und den beiden Programmen.
4. Das LLM generiert eine neue Programmvariante.
5. Evaluiere die Variante in der Sandbox.
6. Wenn sie gültig und besser ist, füge sie zum Pool hinzu.
7. 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).
• DeepMind GitHub: github.com/google-deepmind/funsearch