🤖 AI

Improved lower bounds for the Shannon capacity of odd cycles

Diese Arbeit präsentiert verbesserte untere Schranken für die Shannon-Kapazität der ungeraden Zyklen $C_7$ , $C_{11}$ , $C_{13}$ und $C_{15}$ , indem durch iterative Zusammenarbeit mit einem Large Language Model größere unabhängige Mengen in deren starken Produkten konstruiert werden.

Ursprüngliche Autoren: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

Veröffentlicht 2026-07-31

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

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 über einen verrauschten Funkkanal zu senden. Jedes Mal, wenn Sie sprechen, könnte statisches Rauschen Ihre Worte verzerren und ein „Ja“ in ein „Nein“ verwandeln. In der Welt der Informationstheorie stellen Wissenschaftler eine sehr spezifische Frage: Was ist die maximale Geschwindigkeit, mit der wir Nachrichten senden können, damit der Empfänger sie perfekt und ohne Fehler versteht, egal wie viel statisches Rauschen in der Luft liegt? Diese Grenze wird als Shannon-Kapazität bezeichnet.

Um dies herauszufinden, verwenden Mathematiker ein Werkzeug namens „Graph“, was im Grunde nur ein schicker Begriff für eine Karte aus Punkten ist, die durch Linien verbunden sind. Stellen Sie sich diese Punkte als verschiedene Nachrichten vor, die man senden könnte, und die Linien als die verwirrenden Ähnlichkeiten zwischen ihnen. Wenn zwei Punkte miteinander verbunden sind, bedeutet das, dass diese beiden Nachrichten durch das Rauschen miteinander verwechselt werden könnten. Das Ziel ist es, eine Gruppe von Punkten (Nachrichten) auszuwählen, die nicht miteinander verbunden sind, damit sie alle unterscheidbar und sicher vor Verwechslungen sind. Je größer diese Gruppe ist, desto mehr Informationen kann man senden.

Der knifflige Teil ist, dass wir diese Karten kombinieren können, um sogar noch größere, komplexere Karten zu erstellen. Durch das Übereinanderstapeln dieser Karten können wir manchmal riesige Gruppen sicherer Nachrichten finden, die wir zuvor nicht gesehen haben. Für bestimmte Formen, wie etwa gerade Zahlen von Ringen, kennen wir die Antwort perfekt. Aber für ungerade Ringe (wie eine 7- oder 11-seitige Form) ist die Antwort seit Jahrzehnten ein hartnäckiges Rätsel. Es ist, als versuche man, die größte Anzahl an nicht berührenden Punkten auf einem verdrehten, verknoteten Armband zu finden, und niemand konnte bisher die absolut beste Anordnung finden.

In dieser Arbeit geht es um ein Team von Forschern, die beschlossen haben, diese hartnäckigen ungeraden Ringe mit einem ganz neuen Helfer anzugehen: einem Large Language Model (LLM), dem gleichen Typ KI, der intelligente Chatbots antreibt. Anstatt einfach nur Code zu schreiben, um nach der Antwort zu suchen, behandelten sie die KI wie einen kreativen Partner. Sie baten die KI, sich die bisher besten bekannten Anordnungen sicherer Nachrichten für diese ungeraden Ringe anzusehen und dann zu versuchen, diese nur ein winziges Stück zu verändern, um sie noch größer zu machen.

Die Ergebnisse waren überraschend erfolgreich. Das Team entdeckte gemeinsam mit der KI neue, größere Gruppen sicherer Nachrichten für Ringe mit 7, 11, 13 und 15 Seiten. Für den 7-seitigen Ring fanden sie eine Gruppe von 134.753 sicheren Nachrichten, was größer ist als der bisherige Rekord von 367. Für den 11-seitigen Ring fanden sie 21.909 sichere Nachrichten. Für den 13-seitigen Ring entdeckten sie 62.530 und für den 15-seitigen Ring eine massive Menge von 8.076.974.

Diese Zahlen mögen wie bloße Listen von Ziffern erscheinen, aber sie repräsentieren eine echte Verbesserung unseres Verständnisses davon, wie viel Information ohne Fehler übertragen werden kann. Indem sie diese größeren Gruppen fanden, bewiesen die Forscher, dass die Geschwindigkeitsbegrenzung für das Senden perfekter Nachrichten über diese spezifischen verrauschten Kanäle etwas höher liegt, als wir bisher dachten. Beispielsweise ist das Tempolimit für den 7-seitigen Ring nun bekannt als größer als 3,258020, während es zuvor nur als größer als 3,257865 bekannt war.

Was diese Geschichte besonders spannend macht, ist nicht nur die Zahlenfolge, sondern auch wie sie gefunden wurden. Die Forscher versuchten es mit traditionellen Computersuchmethoden, wie etwa Simulated Annealing (was so ähnlich ist wie das Schütteln einer Box mit Puzzleteilen, bis sie zusammenpassen), aber diese Methoden scheiterten daran, die neuen, größeren Gruppen zu finden. Selbst mit KI-gestützte lokale Suchalgorithmen konnten diese neuen Höhen nicht erreicht werden. Es war erst durch den Austausch mit der KI – wobei die Forscher Hinweise gaben und die KI kreative Modifikationen der bestehenden Muster vorschlug –, dass diese neuen Rekorde gebrochen wurden.

Das Paper behauptet nicht, das gesamte Rätsel der Shannon-Kapazität für alle ungeraden Ringe gelöst zu haben; dieses Problem bleibt offen. Es zeigt jedoch, dass wir durch die Kombination von menschlicher mathematischer Intuition und der Mustererkennung moderner KI die Grenzen dessen, was wir wissen, verschieben können. Die Forscher verifizierten jede einzelne ihrer neuen Nachrichtengruppen, um sicherzustellen, dass sie mathematisch korrekt waren, und bewiesen damit, dass die KI nicht nur geraten, sondern tatsächlich gültige, größere Lösungen gefunden hatte, die menschlichen Experten entgangen waren. Dies deutet darauf hin, dass die Zukunft des Lösens komplexer mathematischer Rätsel aus einem Team von Menschen und KI bestehen könnte, bei dem die KI als kreativer Funke dient, der uns hilft, den nächsten Schritt im Tanz der Zahlen zu sehen.

Technisches Resümee: Verbesserte untere Schranken für die Shannon-Kapazität von ungeraden Zyklen

Problemstellung
Die Shannon-Kapazität $\Theta(G)$ eines Graphen $G$ quantifiziert die maximale fehlerfreie Kommunikationsrate über einen verrauschten Kanal, der durch $G$ definiert ist. Sie ist definiert als $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$ , wobei $\alpha(G^d)$ die Unabhängigkeitszahl des $d$ -ten starken Produkts von $G$ ist. Während $\Theta(C_p) = p/2$ für gerade Zyklen und $\Theta(C_5) = \sqrt{5}$ gilt, bleiben die Werte für ungerade Zyklen $C_{2r+1}$ mit $r > 2$ unbekannt. Die Bestimmung von $\Theta(C_7)$ ist ein notorisch schwieriges offenes Problem. Der Standardansatz zur Etablierung unterer Schranken besteht darin, große unabhängige Mengen in starken Produkten $C_k^d$ zu konstruieren, um die Größe der Menge $\alpha(C_k^d)^{1/d}$ zu maximieren.

Methodik
Die Autoren nutzen eine iterative Interaktion mit einem Large Language Model (LLM), spezifisch ChatGPT-5.6 Sol Pro, um explizite kombinatorische Konstruktionen unabhängiger Mengen zu entdecken. Die Methodik unterscheidet sich von traditionellen heuristischen Suchverfahren (wie Simulated Annealing oder lokalen Suchalgorithmen), welche die Autoren als gescheitert beschreiben, da diese trotz intensiver Versuche nicht die berichteten Schranken erreichen konnten.

Der Prozess umfasste:

Prompting: Die Autoren versorgten das LLM mit spezifischen Parametern: der Zykluslänge ( $k$ ), der Produktdimension ( $d$ ), der bisher besten bekannten Konstruktion und einer Zielgröße für eine Verbesserung.
Generierung und Ausführung: Das Modell generierte Suchprogramme, führte diese in seiner Umgebung aus und lieferte Kandidaten für unabhängige Mengen zurück.
Iterative Verfeinerung: Die Autoren führten Folge-Prompts durch, um die Kardinalität über die vom Modell ursprünglich gefundenen Ergebnisse hinaus zu steigern.
Verifizierung: Alle konstruierten Mengen wurden von den Autoren rigoros verifiziert, um sicherzustellen, dass es sich um gültige unabhängige Mengen handelt (d. h. keine zwei Vektoren unterscheiden sich in jeder Koordinate modulo $k$ um höchstens 1).

Wesentliche Beiträge und Ergebnisse
Die Arbeit präsentiert verbesserte untere Schranken für die Shannon-Kapazität von vier spezifischen ungeraden Zyklen, indem sie größere unabhängige Mengen in deren starken Produkten konstruiert:

$C_7$ (7-Zyklus): Die Autoren konstruierten eine unabhängige Menge der Größe 134.753 im starken 10-fachen Produkt $C_7^{10}$ . Dies verbessert die bisher beste Schranke von $367^{1/5}$ (aus einer unabhängigen Menge der Größe 367 in $C_7^5$ ).
- Neue untere Schranke: $\Theta(C_7) \geq 134753^{1/10} > 3,258020$ (zuvor $> 3,257865$ ).
- Konstruktionsstrategie: Die Menge wurde durch Modifikation der bekannten Größe-367 Menge $R$ von Polak und Schrijver abgeleitet. Die Autoren entfernten spezifische Vektoren aus $R$ , um eine Teilmenge $B$ zu bilden, und konstruierten die endgültige Menge $I$ mittels des kartesischen Produkts $B \times B$ , ergänzt um zusätzliche Vektoren, die aus $R$ und spezifischen Transformationen abgeleitet wurden.
$C_{11}$ (11-Zyklus): Eine unabhängige Menge der Größe 21.909 wurde in $C_{11}^6$ gefunden.
- Neue untere Schranke: $\Theta(C_{11}) \geq 21909^{1/6} > 5,289773$ (zuvor $148^{1/3} > 5,289572$ ).
- Konstruktionsstrategie: Ausgehend von der Größe-148 Menge in $C_{11}^3$ definierten die Autoren spezifische Teilmengen ($DL, DR, BL, BR$) sowie Hilfsvektormengen ( $F_A, F_B, \dots$ ), um die Menge im 6-fachen Produkt zu konstruieren.
$C_{13}$ (13-Zyklus): Eine unabhängige Menge der Größe 62.530 wurde in $C_{13}^6$ gefunden.
- Neue untere Schranke: $\Theta(C_{13}) \geq 62530^{1/6} > 6,300109$ (zuvor $247^{1/3} > 6,274305$ ).
- Konstruktionsstrategie: Das LLM implementierte eine randomisierte lokale Suche auf einem Hilfsgraphen $G_A$ (mit 134 Vertices), um eine große unabhängige Menge $S$ von 370 Vektoren in $\mathbb{Z}_{13}^4$ zu finden. Die endgültige Menge $I$ wurde als $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$ definiert.
$C_{15}$ (15-Zyklus): Eine unabhängige Menge der Größe 8.076.974 wurde in $C_{15}^8$ gefunden.
- Neue untere Schranke: $\Theta(C_{15}) \geq 8076974^{1/8} > 7,301399$ (zuvor $2842^{1/4} > 7,301397$ ).
- Konstruktionsstrategie: Beginnend mit der Größe-2842 Menge in $C_{15}^4$ , entfernten die Autoren spezifische Vektoren und fügten andere hinzu, um eine Basismenge $R$ zu bilden. Die endgültige Menge wurde durch $B \times B$ (wobei $B \subset R$ ) gebildet, ergänzt um Vektoren, die durch Nachbarschaftsbedingungen über Nachschlagetabellen ( $W_0, W_1$ ) bestimmt wurden.

Zusätzlich berichtet das Paper über verbesserte untere Schranken für die Unabhängigkeitszahlen mehrerer einzelner starker Produkte, die die Shannon-Kapazität nicht direkt verbessern (z. B. $\alpha(C_{11}^4) \geq 766$ , $\alpha(C_{15}^3) \geq 383$ ).

Bedeutung und Ansprüche
Das Paper behauptet, dass diese Ergebnisse moderate Verbesserungen der bekannten unteren Schranken für $\Theta(C_7)$ , $\Theta(C_{11})$ und $\Theta(C_{15})$ darstellen sowie eine signifikante Verbesserung für $\Theta(C_{13}$ liefern.

Die primäre Bedeutung der Arbeit liegt in der Methodik:

Effektivität von LLMs: Die Konstruktionen wurden durch die iterative Interaktion mit einem LLM entdeckt, welches unabhängige Mengen hervorbrachte, die manuelle Suchheuristiken (einschließlich Simulated Annealing und KI-konstruierter lokaler Suchalgorithmen) trotz monatelanger Bemühungen nicht finden konnten.
Rolle des Wissens: Die Autoren legen nahe, dass der Erfolg des LLMs daraus resultieren könnte, dass es in der Lage ist, bestehendes mathematisches Wissen zu nutzen und bekannte unabhängige Mengen durch „kleine“ Änderungen zu modifizieren. Dies unterstreicht das Potenzial von LLMs für das Finden expliziter kombinatorischer Konstruktionen.
Zukünftige Forschung: Das Paper postuliert, dass die Untersuchung der Mechanismen, die es LLMs ermöglichen, traditionelle Suchheuristiken beim Finden unabhängiger Mengen zu übertreffen, eine wertvolle zukünftige Forschungsrichtung darstellt.

Die Autoren bleiben hinsichtlich der Größenordnung der numerischen Verbesserungen bescheiden (z. B. ist die Steigerung von $\Theta(C_{15})$ in der sechsten Dezimalstelle), betonen jedoch die Neuartigkeit des Entdeckungsprozesses. Alle Konstruktionen und der Code werden in einem öffentlichen Repository zur Verfügung gestellt.

Technisches Resümee: Verbesserte untere Schranken für die Shannon-Kapazität von ungeraden Zyklen

Mehr davon