DIE SONNENBLUMEN-VERMUTUNG FÄLLT

Nehmen Sie die Zahlen von 1 bis n und betrachten Sie alle Möglichkeiten, einige davon auszuwählen: Es gibt 2ⁿ solcher Teilmengen. Wählen Sie nun einige Teilmengen, die genau denselben gemeinsamen Teil haben, und sonst nichts. Mathematiker nennen das eine Sonnenblume (sunflower): Der gemeinsame Teil ist der Kern, und was von jeder Menge übrig bleibt, ist ein Blütenblatt, das kein anderes Blütenblatt berührt.

Sonnenblumen sind ein Grundwerkzeug der Kombinatorik. Das Paper nennt Verbindungen zu den Grenzen bestimmter logischer Schaltkreise, zum „Cap-Set“-Problem, zur schnellen Matrixmultiplikation und zur Informationstheorie.

Eine Frage aus dem Jahr 1970

Die naheliegendste Frage zu ihnen geht laut den Autoren auf eine Arbeit von Paul Erdős aus dem Jahr 1970 zurück. Wie groß kann eine Sammlung von Teilmengen von {1, …, n} sein, wenn keine k ihrer Mengen eine Sonnenblume bilden?

In den 1970er-Jahren vermuteten Erdős und Endre Szemerédi, dass eine solche Sammlung exponentiell kleiner sein muss als die 2ⁿ möglichen Teilmengen: höchstens cⁿ, für eine Zahl c strikt unter 2.

Jahrzehntelang kratzten die besten Schranken nur ein wenig ab, nie genug, um die Basis unter 2 zu drücken. Nur der Fall mit drei Blütenblättern (k = 3) wurde 2016 geklärt, durch den Durchbruch beim Cap-Set-Problem und eine Reduktion von Alon, Shpilka und Umans.

Die Schranke

Matija Bucić und Fankang He (Universität Wien) sowie Hyunwoo Lee (KAIST und Institute for Basic Science, Südkorea) beweisen die Vermutung für jedes k ≥ 3. Ihr Hauptsatz: Eine Sammlung ohne Sonnenblume mit k Blütenblättern hat höchstens

3 · (2 − 1/(16k³))ⁿ

Elemente. Die Basis liegt knapp unter 2, aber sie ist eine feste Zahl unter 2, und genau das verlangten Erdős und Szemerédi. Eine Konstruktion von 1997 zeigt, dass der wahre Wert für große k nicht viel niedriger sein kann.

Von Mengen zu Vektoren

Der Beweis führt über eine Version des Problems mit Vektoren. Teilen Sie die Zahlen in n Blöcke zu je D Elementen und wählen Sie ein Element pro Block: Jede solche Wahl ist ein Vektor. Mehrere Vektoren bilden eine Sonnenblume, wenn ihre Einträge an jeder Position entweder alle gleich oder alle verschieden sind.

Die Autoren bauen dann einen „Sonnenblumen-Tester“: eine Funktion, die auf einer sonnenblumenfreien Sammlung nur dann ungleich null ist, wenn alle ihre Eingaben derselbe Vektor sind. Die neue Zutat besteht darin, diese Funktion Schritt für Schritt mit Interpolationspolynomen niedrigen Grades zu schreiben. Das Abzählen dieser Polynome beschränkt die Größe der Sammlung (ihr Satz 2). Ein probabilistisches Argument, zufällige Blöcke gemittelt über alle Mengengrößen, überträgt die Schranke zurück auf gewöhnliche Mengen.

Von einer Maschine gefunden, von einer anderen geprüft

Die Aussage des Papers zur KI ist ungewöhnlich direkt. Der Beweis von Satz 2 wurde von ChatGPT 6 Astra Pro gefunden, nach einer kurzen Diskussion, die mit der Bitte begann, das bekannte Argument für drei Blütenblätter zu verallgemeinern. Die Autoren brauchten diesen Schritt für ein anderes Ziel: eine induzierte Version eines von Szemerédi gestellten Graphenproblems, die sie für eine spätere Notiz ankündigen.

Das Modell schrieb seinen Beweis in der Sprache des „Slice Rank“. Die Autoren schrieben ihn in der Sprache der Polynommethode neu, die sie für Leser zugänglicher finden. Sie erklären, dass sie jedes Ergebnis überprüft haben und die volle Verantwortung übernehmen, und dass der Beweis in Lean 4.35 verifiziert wurde, einer Software zur Beweisprüfung; die Verifikation soll im Palomar-Repository veröffentlicht werden.

Was offen bleibt

Die Autoren haben nicht versucht, die Basis zu optimieren. Für drei Blütenblätter schlägt sie die Schranke von Naslund und Sawin aus dem Jahr 2017, etwa 1,89, nicht. Und das stärkere Schwesterproblem, die Erdős-Rado-Sonnenblumen-Vermutung, bleibt offen: Ihre Schranken hängen noch stark von der Blockgröße D ab, und genau das verbietet jenes Problem.