🔢 mathematics

A Census of New Snake-in-the-Box Records

Diese Arbeit präsentiert neue, längere induzierte Pfade (Schlangen) in Hyperwürfel-Graphen für die Dimensionen 9 bis 13, wodurch die bekannten unteren Schranken für das Snake-in-the-Box-Problem verbessert und ein computerverifizierbarer Datensatz dieser rekordlangen Pfade bereitgestellt wird.

Ursprüngliche Autoren: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

Veröffentlicht 2026-07-17

📖 3 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

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, durch ein riesiges, mehrdimensionales Labyrinth zu navigieren, das vollständig aus Lichtschaltern besteht. In dieser Welt ist jedes Zimmer eine einzigartige Kombination von Schaltern, die entweder „an“ oder „aus“ sind. Um von einem Zimmer zum nächsten zu gelangen, können Sie genau einen Schalter umlegen. Dies ist der „Hyperwürfel“, eine Form, die in der Mathematik existiert, sich aber wie ein digitales Labyrinth anfühlt. Stellen Sie sich nun vor, Sie möchten durch so viele Räume wie möglich wandern, ohne jemals einen Raum zu betreten, den Sie bereits besucht haben, und mit einer speziellen Regel: Sie können keine Abkürzung nehmen. Wenn Sie sich in Raum A und Raum B befinden und beide mit Raum C verbunden sind, können Sie nicht einfach von A nach B springen, nur weil sie Nachbarn sind; Sie müssen dem Pfad folgen, den Sie begonnen haben. Diese spezielle Art des Wanderns wird als „Snake“ bezeichnet.

Warum kümmert sich überhaupt jemand um diese digitalen Schlangen? Es stellt sich heraus, dass das Finden der längstmöglichen Snake in diesen Labyrinthen entscheidend für den Bau besserer Fehlererkennungscodes ist. Denken Sie an diese Codes als an Sicherheitsnetze, die Ihre Textnachrichten, Satellitensignale und Computerdaten davor bewahren, beim Reisen durch das verrauschte Universum verstümmelt zu werden. Je länger die Schlange ist, desto robuster ist der Code. Jahrzehntelang haben Mathematiker darum gerannt, die längstmögliche Schlange für Labyrinthe verschiedener Größen zu finden, aber für die größeren, komplexeren Labyrinthe blieb der Rekord lange Zeit stehen.

Dieses Paper ist ein bedeutendes Update in diesem Rennen. Die Autoren, ein Team von Forschern, haben leistungsstarke Computer verwendet, um neue, längere Schlangen in Labyrinthen der Dimensionen 9 bis 13 zu finden. Vor dieser Arbeit waren die besten bekannten Schlangen in diesen Dimensionen die längsten, die jemals gesehen worden waren. Das Team hat nicht nur einen oder zwei gefunden; sie haben signifikant längere Pfade gefunden und damit die bisherigen Rekorde in jeder der von ihnen getesteten Dimensionen gebrochen. In einem 9-dimensionalen Labyrinth fanden sie beispielsweise eine Schlange mit 191 Schritten und übertrafen damit den alten Rekord von 190. Im massiven 13-dimensionalen Labyrinth trieben sie die Länge auf 2.922 Schritte und übertrafen damit den bisherigen Bestwert von 2.900.

Die Forscher haben nicht nur mit der Suche nach einem Pfad aufgehört; sie agierten wie digitale Archäologen, die ganze Familien dieser rekordverdächtigen Schlangen ausgruben. Im 9-dimensionalen Fall entdeckten sie 1.311 verschiedene Wege, um eine Schlange dieser neuen Rekordlänge zu bauen. Sie wandten ihre Methoden auch an, um längere „Coils“ (die wie Schlangen sind, die zum Ausgang zurückkehren) und „symmetrische Coils“ (bei denen sich die zweite Hälfte der Schleife an der ersten spiegelt) zu finden. Ihre Ergebnisse zeigen, dass die bisherigen Grenzen nicht die wahre Decke waren; es gibt noch Raum zum Wachsen. Alle diese neuen, längeren Pfade wurden in einem öffentlichen Datensatz gespeichert, sodass jeder die Mathematik überprüfen oder diese neuen, längeren Pfade nutzen kann, um noch bessere Fehlererkennungscodes zu bauen. Obwohl sie das Rätsel nicht für jede mögliche Dimension gelöst haben, haben sie erfolgreich die bekannten Grenzen dessen, was möglich ist, im digitalen Labyrinth erweitert und bewiesen, dass wir mit genügend Rechenleistung immer noch neue, längere Wege finden können, um durch die Dunkelheit zu wandern.

Technisches Resümee: Eine Zählung neuer „Snake-in-the-Box“-Rekorde

Problemdefinition
Die Arbeit befasst sich mit dem „Snake-in-the-Box“-Problem, das ursprünglich 1958 von Kautz im Kontext fehlererkennender Codes formuliert wurde. Das Problem sucht nach dem längsten induzierten (chordlosen) Pfad, bezeichnet als „Snake“, innerhalb des Hyperwürfel-Graphen $Q_n$ . In $Q_n$ repräsentieren Vertices binäre Zeichen der Länge $n$ , und Kanten verbinden Zeichen, die sich in genau einer Koordinate unterscheiden. Ein Snake ist als eine Sequenz distinkter Vertices definiert, bei der aufeinanderfolgende Vertices benachbart sind und keine zwei nicht-aufeinanderfolgenden Vertices benachbart sind. Die maximale Länge eines solchen Pfades wird als $a(n)$ bezeichnet.

Die Arbeit betrachtet auch verwandte Strukturen: „Coils“ (induzierte Zyklen in $Q_n$ ) mit der maximalen Länge $b(n)$ sowie „symmetrische Coils“ (Coils, bei denen die zweite Hälfte des Zyklus die erste Hälfte über eine feste XOR-Operation spiegelt) mit der maximalen Länge $c(n)$ . Während exakte Werte für $a(n)$ und $b(n)$ für Dimensionen $n \le 8$ bekannt sind und $c(n)$ für $n \le 7$ bekannt ist, bleibt das Problem für $n \ge 9$ (und $n \ge 8$ für symmetrische Coils) ungelöst, wobei bisher nur durch verschiedene computergestützte Suchen untere Schranken etabliert wurden.

Methodik und Ansatz
Die Autoren setzen anhaltende computergestützte Bemühungen ein, um längere Snakes, Coils und symmetrische Coils in den Dimensionen 9 bis 13 zu finden. Der vorliegende Text beschreibt keine spezifische neuartige algorithmische Architektur, ordnet die Arbeit jedoch als einen Fortschritt gegenüber bisherigen Methoden ein, zu denen genetische Algorithmen, populationsbasierte evolutionäre Suchen, permutationsbasierte Konstruktionen und Monte-Carlo-Baum-Suchen gehörten.

Der Ansatz der Autoren konzentriert sich auf das Generieren und Verifizieren rekordlanger Pfade. Sie verwenden eine Standardnotation, bei der ein Snake als Übergangssequenz – die geordnete Liste der 0-indizierten Koordinatenindizes, die entlang des Pfades geflippt werden – dargestellt wird. Um die Gültigkeit ihrer Ergebnisse sicherzustellen, stellen die Autoren einen computerverifizierbaren Datensatz zur Verfügung. Zudem führen sie eine Zählung des Lösungsraums durch, indem sie die Anzahl der äquivalenten Snakes bei Rekordlängen zählen. Die Äquivalenz wird durch die Symmetrien von $Q_n$ bestimmt, welche $n!$ Koordinatenpermutationen, $2^n$ Translationen (XORing) und Pfadumkehrung umfassen.

Wesentliche Beiträge und Ergebnisse
Der primäre Beitrag der Arbeit liegt in der Etablierung neuer unterer Schranken für $a(n)$ , $b(n)$ und $c(n)$ in den Dimensionen 9 bis 13, welche alle bisher bekannten Rekorde übertreffen.

Snake-Längen ( $a(n)$ ): Die Autoren präsentieren Snakes, die in jeder Dimension von 9 bis 13 länger sind als die bisher bestbekannten.
- $n=9$ : Eine neue Länge von 191 (Verbesserung gegenüber 190). Die Autoren identifizierten 1.311 in äquivalente Snakes dieser Länge.
- $n=10$ : Eine neue Länge von 379 (Verbesserung gegenüber 376).
- $n=11$ : Eine neue Länge von 746 (Verbesserung gegenüber 737).
- $n=12$ : Eine neue Länge von 1.476 (Verbesserung gegenüber 1.465).
- $n=13$ : Eine neue Länge von 2.922 (Verbesserung gegenüber 2.900).
- Die Verbesserungen reichen von +1 bis +22 gegenüber den vorherigen Rekorden.
Coil-Längen ( $b(n)$ ): Die Arbeit berichtet über verbesserte untere Schranken für die längsten Coils in den Dimensionen 9, 10 und 11, mit neuen Längen von 192, 374 bzw. 732.
Symmetrische Coil-Längen ( $c(n)$ ): Verbesserte untere Schranken werden für die Dimensionen 10 und 11 bereitgestellt, mit den neuen Längen 370 und 726.

Die Autoren liefern ein konkretes Beispiel für einen Snake der Länge 191 in $Q_9$ , indem sie dessen vollständige Übergangssequenz auflisten. Sie merken an, dass unter Millionen von Stichproben der Länge-191-Snakes genau 131 Symmetrieklassen für $n=9$ gefunden wurden, was zu der Vermutung führt, dass keine weiteren Klassen existieren; eine solche Vollständigkeitsbehauptung machen sie jedoch nicht für $n \ge 10$ .

Bedeutung und Ansprüche
Die Arbeit beansprucht ihre Bedeutung primär durch die empirische Fortschreitung der bekannten Schranken für das Snake-in-the-Box-Problem. Indem die Autoren Snakes bereitstellen, die in den Dimensionen 9 bis 13 streng länger sind als alle zuvor bekannten, haben sie die unteren Schranken für die maximale mögliche Länge induzierter Pfade in Hyperwürfeln verschärft.

Die Arbeit dient als „Zählung“ dieser neuen Rekorde und bietet einen umfassenden Datensatz, der die spezifischen Übergangssequenzen für alle gefundenen distinkten rekordlangen Snakes enthält. Dieser Datensatz wird in einem computerverifizierbaren Format öffentlich zugänglich gemacht, um eine unabhängige Verifizierung der Ergebnisse zu ermöglichen. Die Autoren rahmen ihre Arbeit als Fortsetzung der computergestützten Linie ein, die von früheren Forschern (wie Ace, Echols, Meyerson und anderen) etabliert wurde, und verschieben die Grenze dessen, was computergestützt in diesem kombinatorischen Optimierungsproblem erreichbar ist, ohne dabei zu behaupten, das Problem für diese Dimensionen gelöst oder die Optimalität ihrer neuen Schranken bewiesen zu haben.

Technisches Resümee: Eine Zählung neuer „Snake-in-the-Box“-Rekorde

Mehr davon