🔢 mathematics

Lean-verified lower bounds for the Shannon capacity of odd cycles

Diese Arbeit präsentiert neue, in Lean vollständig formalisierte untere Schranken für die Shannon-Kapazitäten mehrerer kleiner ungerader Zyklen ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ), die mittels eines iterativen Verfahrens abgeleitet wurden, das auf jüngsten Methoden von Gao und Itty et al. basiert.

Ursprüngliche Autoren: Pjotr Buys, Sven Polak, Jeroen Zuiddam

Veröffentlicht 2026-08-03

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Pjotr Buys, Sven Polak, Jeroen Zuiddam

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, eine geheime Nachricht durch eine laute, chaotische Stadt zu senden. Die Stadt ist voller Ablenkungen, und manchmal vermischt sich Ihr Signal mit den falschen Straßennamen. In der Welt der Informationstheorie ist dies ein echtes Problem: Wie sendet man Daten perfekt, ohne dass Fehler auftreten? In den 1950er Jahren fand ein Mathematiker namens Claude Shannon heraus, dass man, wenn man einen „verrauschten“ Kanal hat, Nachrichten immer noch perfekt senden kann, aber nur, wenn man geschickt damit umgeht, wie man seine Buchstaben gruppiert. Er führte das Konzept der „Shannon-Kapazität“ ein, was im Wesentlichen eine Punktzahl ist, die die maximale Geschwindigkeit angibt, mit der man perfekte Nachrichten durch ein bestimmtes verrauschtes Netzwerk senden kann.

Um dies zu visualisieren, stellen Sie sich ein Spiel auf einer Karte der Stadt vor. Die Karte ist ein Graph, bei dem die Kreuzungen Punkte und die Straßen Linien sind. Einige Straßen sind „sicher“ zu befahren, während andere gefährlich sind und zu einem Crash führen würden, wenn man sie vermischt. Das Ziel besteht darin, die größtmögliche Gruppe von Kreuzungen (eine „unabhängige Menge“) auszuwählen, die man besuchen kann, ohne jemals eine gefährliche Straße zwischen zwei von ihnen zu nehmen. Die „Shannon-Kapazität“ stellt eine knifflige Frage: Wenn man dieses Spiel nicht nur einmal spielt, sondern mehrere Kopien der Karte übereinander stapelt, um eine riesige, mehrdimensionale Stadt zu erschaffen, wie viel größer kann Ihre sichere Gruppe werden? Für einige Formen kennen wir die Antwort. Für andere, speziell die ungleichmäßig geformten Schleifen in der Stadt (wie ein Fünfeck oder ein Siebeneck), war die Antwort jahrzehntelang ein Rätsel. Es ist, als wüsste man die Geschwindigkeitsbegrenzung auf einer geraden Straße, hätte aber keine Vorstellung davon, wie schnell man auf einer gewundenen, siebeneckigen Strecke fahren kann.

In dieser Arbeit geht es darum, dieses Rätsel für mehrere dieser kniffligen, siebeneckigen (und größeren) Bahnen zu lösen. Die Autoren, ein Team aus Mathematikern und Informatikern, haben neue, etwas schnellere Wege gefunden, um perfekte Nachrichten durch diese spezifischen Schleifen zu senden. Sie haben nicht einfach nur geraten; sie haben ein kluges, schrittweises Rezept verwendet, um immer größere Gruppen sicherer Kreuzungen aufzubauen. Um sicherzustellen, dass sie nicht den kleinsten Fehler in ihrer komplexen Mathematik gemacht haben, hatte ein superstrenger digitaler Schiedsrichter namens „Lean“ die Aufgabe, jeden einzelnen Schritt ihrer Arbeit zu überprüfen. Das Ergebnis? Sie haben bewiesen, dass die Shannon-Kapazität für diese spezifischen ungeraden Schleifen höher ist, als bisher berechnet wurde.

Das Spiel der sicheren Kreuzungen

Lassen Sie uns aufschlüsseln, was die Autoren tatsächlich getan haben. Sie untersuchten Graphen, die wie einfache Ringe mit einer ungeraden Anzahl von Punkten aussehen: ein Ring mit 7, 11, 13, 15, 19, 21 und 23 Punkten. Lange Zeit kannten Mathematiker die „Geschwindigkeitsbegrenzung“ (die Shannon-Kapazität) für einen 5-Punkte-Ring. Aber für Ringe mit 7 Punkten oder mehr war die Antwort jedoch im Nebel gefangen. Wir wussten, dass sie mindestens eine bestimmte Zahl war, aber wir wussten nicht, ob sie höher sein konnte.

Die Autoren verwendeten eine Methode, die sich wie ein magisches Rezept für das Wachstum Ihrer sicheren Gruppe anfühlt. Stellen Sie sich vor, Sie haben einen kleinen, sicheren Club von Freunden (eine Menge von Punkten) auf einer einzelnen Karte. Das Papier beschreibt ein „Produkttheorem“, das wie eine Maschine funktioniert, die zwei dieser Karten nimmt und sie zusammenschlägt, um eine neue, größere Karte zu erstellen. Wenn Sie einen sicheren Club auf der ersten Karte und einen sicheren Club auf der zweiten Karte haben, können Sie diese kombinieren, um einen sicheren Club auf der neuen, größeren Karte zu erstellen. Normalerweise ist die Größe dieses neuen Clubs einfach die Größe des ersten Clubs multipliziert mit der Größe des zweiten. Aber die Autoren fanden ein spezielles „Gadget“ oder einen Trick. Durch die Verwendung eines spezifischen Verbindungsmusters (eines sogenannten „gültigen Tupels“) konnten sie den neuen Club größer machen, als die einfache Multiplikation vermuten ließe.

Stellen Sie es sich so vor: Wenn Sie ein Team von 2 Personen haben, die zusammenarbeiten können, ohne sich zu streiten, und Sie kombinieren zwei solche Teams, würden Sie vielleicht ein Team von 4 Personen erwarten. Aber mit diesem speziellen Trick fanden die Autoren einen Weg, die beiden zu kombinieren und ein Team von 5 Personen zu erhalten, die alle perfekt miteinander auskommen. Durch das wiederholte Anwenden dieses Tricks, indem man die Karten immer höher stapelt, konnten sie diese sicheren Teams in massive Gruppen wachsen lassen.

Die neuen Rekorde

Das Team wandte dieses Rezept auf sieben verschiedene ungerade Ringe an: jene mit 7, 11, 13, 15, 19, 21 und 23 Punkten. Für jeden von ihnen starteten sie mit einer bekannten sicheren Gruppe und ließen ihre „Stapelfunktion“ viele Male laufen. Das Ergebnis war eine neue, höhere untere Schranke für die Shannon-Kapazität.

Hier ist das, was sie fanden, mit den Zahlen exakt so, wie sie berechnet wurden:

Für den 7-Punkte-Ring bewiesen sie, dass die Kapazität mindestens 3.258805369885 beträgt. Dies ist ein winziges Stück höher als die bisher beste Vermutung.
Für den 11-Punkte-Ring liegt die neue Untergrenze bei 5.294502522149.
Für den 13-Punkte-Ring drückten sie das Limit auf 6.302455083464.
Für den 15-Punkte-Ring liegt die Zahl bei 7.301600534487.
Für den 19-Punkte-Ring erreichten sie 9.357192705918.
Für den 21-Punkte-Ring liegt die Schranke bei 10.342455853338.
Und für den 23-Punkte-Ring fanden sie eine Kapazität von mindestens 11.328224257774.

Diese Zahlen mögen wie eine Folge von Zufallsziffern aussehen, aber in der Welt der Informationstheorie stellen sie eine konkrete Verbesserung dar. Sie bedeuten, dass wir für diese spezifischen Netzwerke nun sicher wissen, dass wir Nachrichten etwas schneller senden können, als wir es zuvor für möglich gehalten haben.

Der digitale Schiedsrichter

Was dieses Paper besonders macht, ist nicht nur die Zahlen, sondern die Art und Weise, wie sie zustande gekommen sind. Die Mathematik dahinter ist unglaublich komplex und umfasst riesige Datensätze sowie tausende von Schritten. Es ist die Art von Arbeit, bei der ein Mensch leicht einen winzigen Fehler übersehen könnte. Um dies zu lösen, schrieben die Autoren ihr gesamtes Beweisverfahren in einer Programmiersprache namens Lean.

Betrachten Sie Lean als einen hyperstrengen, digitalen Schiedsrichter, der kein „Ich denke, das ist richtig“ oder „Es sieht gut aus für mich“ akzeptiert. Er verlangt für jeden einzelnen Schritt einen absoluten, logischen Beweis. Wenn die Autoren einen Fehler in ihrer Logik gemacht hätten, hätte Lean gestoppt und gesagt: „Nein, das folgt daraus nicht.“ Die Tatsache, dass das Paper „Lean-verifiziert“ ist, bedeutet, dass ein Computer jeden einzelnen Schritt ihrer Argumentation überprüft und bestätigt hat, dass ihre neuen Schranken mathematisch solide sind. Sie haben die Ergebnisse nicht nur simuliert; sie haben sie formal bewiesen.

Die Autoren erwähnen auch, dass sie große Sprachmodelle (wie fortgeschrittene KI-Chatbots) verwendet haben, um ihnen bei der Suche nach den anfänglichen Mustern und Rezepten für diese sicheren Gruppen zu helfen. Es ist ein wenig so, als hätte man einen kreativen Assistenten, der eine wilde Idee vorschlägt, und dann nutzen die Mathematiker ihre rigorosen Werkzeuge, um zu testen, ob diese Idee tatsächlich Bestand hat. In diesem Fall schlug die KI einen Pfad vor, und das Mensch-Mathematiker-KI-Team ging diesen Pfad bis zu einem verifizierten Ziel zurück.

Warum es wichtig ist

Sie fragen sich vielleicht: „Und was nun? Wir wissen nur, dass die Zahl ein wenig höher ist.“ Die Antwort liegt in der Natur des Problems. Seit Jahrzehnten ist die Kapazität dieser ungeraden Ringe eine offene Frage. Wir wussten, dass die Antwort irgendwo zwischen einer unteren Grenze und einer oberen Grenze (der Lovász-Schranke) liegt, aber wir konnten sie nicht genau festlegen. Jedes Mal, wenn wir die untere Grenze nach oben verschieben, selbst um einen winzigen Bruchteil, verengen wir die Lücke. Wir kommen der wahren Antwort näher.

Diese Arbeit zeigt, dass es selbst für Probleme, die schon lange feststecken, Raum für Verbesserungen gibt, wenn man die richtigen Werkzeuge und die nötige Geduld hat, um seine Arbeit mit den strengsten Standards zu prüfen. Die Autoren haben das gesamte Rätsel der Shannon-Kapazität für alle ungeraden Ringe nicht gelöst, aber sie haben einige der nebligen Ecken aufgeklärt und bewiesen, dass wir für Ringe mit 7, 11, 13, 15, 19, 21 und 23 Punkten ein wenig schneller kommunizieren können, als wir zuvor geglaubt haben.

Technisches Resümee: Lean-verifizierte untere Schranken für die Shannon-Kapazität ungerader Zyklen

Problemstellung
Die Arbeit befasst sich mit dem langjährigen offenen Problem der Bestimmung der Shannon-Kapazität $\Theta(G)$ für ungerade Zyklen $C_n$ mit $n \geq 7$ . Die Shannon-Kapazität ist definiert als $\Theta(G) := \sup_{d \geq 1} \alpha(G^{\boxtimes d})^{1/d}$ , wobei $\alpha$ die Unabhängigkeitszahl und $\boxtimes$ das starke Graphprodukt bezeichnet. Während Lovász $\Theta(C_5) = \sqrt{5}$ mittels der Theta-Funktion $\vartheta(G)$ bestimmte, bleiben die exakten Kapazitäten für alle ungeraden Zyklen der Länge sieben oder größer unbekannt. Die primäre Herausforderung besteht darin, größere unabhängige Mengen in höheren starken Potenzen dieser Zyklen zu finden, um die bekannten unteren Schranken zu verbessern.

Methodik
Die Autoren verwenden ein iteratives Verfahren, das auf einer „Gadget-Konstruktion“ und einem „Produkt-Lemma“ basiert, welches kürzlich von Gao (2026) vorgeschlagen wurde und selbst auf Methoden von Itty, Rosin, Carstensen und Reichman (2026) aufbaut. Der Kern der Methodik umfasst:

Gültige Tupel: Für einen Graphen $G$ wird ein gültiges Tupel $\tau = (I, S, f_0, f_1, X)$ definiert, wobei $I$ eine unabhängige Menge, $S \subseteq I$ und $f_0, f_1$ spezifische Abbildungen sind, die strikte Nachbarschaftsbeschränkungen erfüllen. Dieses Tupel erzeugt ein „Profil“ $\Pi(\tau) = (|I|, |S|, |X|, |X \setminus (N_G[f_0(S)] \cup N_G[f_1(S)])|)$ .
Produktoperation: Eine binäre Operation $\star$ wird auf Profilen definiert. Theorem 1 stellt fest, dass es, wenn $\tau$ und $\tau'$ gültige Tupel für die Graphen $G$ und $H$ sind, ein gültiges Tupel für das starke Produkt $G \boxtimes H$ gibt, dessen Profil das $\star$ -Produkt der einzelnen Profile ist.
Iterative Konstruktion: Ausgehend von einem computergestützt entdeckten gültigen Tupel in einer spezifischen Potenz eines ungeraden Zyklus wenden die Autoren iterativ das $\star$ -Produkt an, um Profile für höhere Potenzen zu erzeugen. Dieser Prozess konstruiert unabhängige Mengen in starken Potenzen $C_n^{\boxtimes d}$ , die größer sind als jene, die durch einfache kartesische Produkte der Basismengen erreicht werden können.
Formale Verifizierung: Eine kritische Komponente der Methodik ist die vollständige Formalisierung dieser Schranken im Lean-Theorembeweiser. Die Basistupel (Mengen $I, S, X$ und Abbildungen $f_0, f_1$ ) werden als explizite Literale kodiert, und ihre Gültigkeit wird innerhalb der Lean-Umgebung mechanisch verifiziert.

Wesentliche Beiträge und Ergebnisse
Die Arbeit präsentiert neue, verbesserte untere Schranken für die Shannon-Kapazitäten von sieben kleinen ungeraden Zyklen ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ). Diese Schranken werden durch die Identifizierung spezifischer Basistupel und die Anwendung des iterativen Produktverfahrens abgeleitet. Die Ergebnisse sind:

$\Theta(C_7)$ : Verbessert auf $\geq 3.258805369885\dots$ (zuvor $3.2587891\dots$ durch Gao 2026). Die Konstruktion nutzt ein Basistupel in $C_7^{\boxtimes 5}$ , das auf die Potenz 200 iteriert wurde.
$\Theta(C_{11})$ : Verbessert auf $\geq 5.294502522149\dots$ (zuvor $5.2897736\dots$ durch Itty et al. 2026). Das Basistupel liegt in $C_{11}^{\boxtimes 3}$ und wurde auf die Potenz 174 iteriert.
$\Theta(C_{13})$ : Verbessert auf $\geq 6.302455083464\dots$ (zuvor $6.3001091\dots$ durch Itty et al. 2026). Das Basistupel liegt in $C_{13}^{\boxtimes 6}$ und wurde auf die Potenz 432 iteriert.
$\Theta(C_{15})$ : Verbessert auf $\geq 7.301600534487\dots$ (zuvor $7.3013990\dots$ durch Itty et al. 2026). Das Basistupel liegt in $C_{15}^{\boxtimes 4}$ und wurde auf die Potenz 4096 iteriert.
$\Theta(C_{19})$ : Verbessert auf $\geq 9.357192705918\dots$ (zuvor $9.3571200\dots$ durch Baumert et al. 1971). Das Basistupel liegt in $C_{19}^{\boxtimes 4}$ und wurde auf die Potenz 16384 iteriert.
$\Theta(C_{21})$ : Verbessert auf $\geq 10.342455853338\dots$ (zuvor $10.3422729\dots$ durch Baumert et al. 1971). Das Basistupel liegt in $C_{21}^{\boxtimes 4}$ und wurde auf die Potenz 4096 iteriert.
$\Theta(C_{23})$ : Verbessert auf $\geq 11.328224257774\dots$ (zuvor $11.3278379\dots$ durch Baumert et al. 1971). Das Basistupel liegt in $C_{23}^{\boxtimes 4}$ und wurde auf die Potenz 2048 iteriert.

Die Verbesserungen, obwohl numerisch klein (im Bereich von $10^{-5}$ bis $10^{-3}$ ), stellen den aktuellen Stand der Technik für diese spezifischen Zyklen dar.

Bedeutung und Ansprüche
Die Arbeit beansprucht ihre Bedeutung primär durch die rigorose Verifizierung dieser Ergebnisse. Durch die Formalisierung der gesamten Konstruktion und der resultierenden Schranken in Lean stellen die Autoren sicher, dass die komplexen kombinatorischen Argumente und die spezifischen Mengenkonstruktionen frei von menschlichen Fehlern sind. Die Arbeit folgt dem Pfad der jüngeren Forschung, die Large Language Models (LLMs) zur Entdeckung initialer Konstruktionen nutzt (wie in [IRCR26] und [Gao26] gesehen), unterscheidet sich jedoch dadurch, dass sie einen vollständig formalisierten, maschinell geprüften Beweis für die Gültigkeit der Basistupel und die Korrektheit der Anwendung des iterativen Produkt-Theorems liefert. Die Autoren behaupten nicht, das allgemeine Problem der Shannon-Kapazität für ungerade Zyklen gelöst zu haben, noch schlagen sie neue theoretische Rahmenbedingungen über die Anwendung von Gaos bestehendem Produkt-Lemma hinaus vor; vielmehr liefern sie die derzeit besten bekannten numerischen unteren Schranken für diese spezifischen Instanzen, verifiziert mit mathematischer Gewissheit.

Das Spiel der sicheren Kreuzungen

Die neuen Rekorde

Der digitale Schiedsrichter

Warum es wichtig ist

Mehr davon