🔢 mathematics

Hamilton decompositions of all directed tori at odd modulus

Dieser Artikel beweist, dass das gerichtete kartesische Produkt von $d$ gerichteten $m$ -Zyklen für alle Dimensionen $d \geq 2$ und alle ungeraden Moduli $m \geq 3$ eine gerichtete Hamilton-Zerlegung zulässt, wobei eine Kombination aus neuen Abschlussmechanismen, Ergebnissen für Basisdimensionen und formaler Verifikation in Lean 4 verwendet wird.

Ursprüngliche Autoren: SangHyun Park

Veröffentlicht 2026-05-07

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: SangHyun Park

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 einen riesigen, mehrdimensionalen Donut vor, der aus einem Gitter von Punkten besteht. In der Mathematik wird dies als Torus bezeichnet. Stellen Sie sich nun vor, dass an jedem einzelnen Punkt dieses Donuts mehrere Einbahnstraßen (Pfeile) zu benachbarten Punkten führen. Das von Ihnen bereitgestellte Papier behandelt ein sehr spezifisches Rätsel: Können wir all diese Einbahnstraßen mit verschiedenen Farben so einfärben, dass jede Farbe eine einzelne, riesige Schleife bildet, die jeden einzelnen Punkt auf dem Donut genau einmal besucht?

Wenn wir dies tun können, haben wir den Donut in perfekte, sich nicht überlappende Schleifen „zerlegt". Das Papier beweist, dass für eine bestimmte Art von Donut (bei der die Anzahl der Punkte entlang jeder Seite eine ungerade Zahl wie 3, 5, 7 usw. ist) die Antwort ja, wir können dies immer tun lautet, unabhängig davon, wie viele Dimensionen der Donut hat.

Hier ist, wie die Autoren dieses Rätsel gelöst haben, erklärt durch einfache Analogien:

1. Das Ziel: Die perfekte Schleife

Stellen Sie sich den Donut als eine Stadt mit $d$ verschiedenen Fahrtrichtungen vor (Norden, Osten, Oben usw.). Die Stadt ist riesig, und jede Kreuzung hat genau $d$ Straßen, die von ihr wegführen.

Die Herausforderung: Sie müssen jede Straße in der Stadt mit $d$ verschiedenen Farben streichen.
Die Regel: Wenn Sie nur den „Roten" Straßen folgen, müssen Sie schließlich jede einzelne Kreuzung in der Stadt durchfahren und zu Ihrem Startpunkt zurückkehren, ohne jemals dieselbe Kreuzung zweimal zu besuchen. Das Gleiche muss für „Blau", „Grün" und jede andere Farbe gelten.
Die Behauptung des Papiers: Für jede Stadtgröße, bei der die Anzahl der Blöcke in jede Richtung eine ungerade Zahl ist, ist diese perfekte Einfärbung immer möglich.

2. Die zwei Hauptwerkzeuge

Die Autoren haben nicht einfach geraten; sie bauten zwei verschiedene „Maschinen", um das Rätsel zu lösen, je nachdem, wie groß die Stadt im Vergleich zur Anzahl der Richtungen ist.

Werkzeug A: Die „Hochhaus"-Maschine (Für große Städte)

Wann sie funktioniert: Wenn die Stadt sehr groß ist (die Anzahl der Blöcke $m$ größer ist als die Anzahl der Richtungen $d$ ).
Wie sie funktioniert: Stellen Sie sich die Stadt als ein Hochhaus mit vielen Etagen vor. Die Autoren verwenden einen cleveren Zähltrick namens „Prefix-Count" (Präfix-Zählung).

Sie weisen jedem Schritt, den Sie unternehmen, eine „Punktzahl" zu.
Sie stellen sicher, dass, wenn Sie einer bestimmten Farbe folgen, sich Ihre Punktzahlen so summieren, dass garantiert wird, dass Sie nicht in einer kleinen Schleife stecken bleiben. Sie sind gezwungen, weiterzuklettern, bis Sie jede Etage und jeden Raum besucht haben.
Sie verwenden eine „vorzeichenbehaftete Binär"-Methode (wie eine Balkenwaage mit positiven und negativen Gewichten), um sicherzustellen, dass die Mathematik perfekt aufgeht, damit sich die Schleife erst schließt, nachdem jeder besucht wurde.

Werkzeug B: Die „Basis-und-Schwanz"-Maschine (Für kleine Städte)

Wann sie funktioniert: Wenn die Stadt klein ist (die Anzahl der Blöcke $m$ kleiner ist als die Anzahl der Richtungen $d$ ).
Wie sie funktioniert: Dies ist wie der Bau einer neuen, komplexen Stadt, indem man eine kleinere, bereits gelöste Stadt nimmt und einen „Schwanz" daran anhängt.

Die Basis: Sie beginnen mit einer kleineren Version des Problems, von der sie bereits wissen, wie man sie löst (wie eine 5-dimensionale Stadt).
Der Schwanz: Sie fügen zusätzliche Dimensionen hinzu (den „Schwanz").
Der Tausch: Sie verwenden einen Trick des „lokalen Tauschs". Stellen Sie sich vor, Sie befinden sich an einer bestimmten Kreuzung. Sie haben ein paar Straßen, die in den „Schwanz" führen. Die Autoren zeigen, dass Sie die Farben dieser Straßen lokal tauschen können (wie beim Tauschen von Karten mit einem Nachbarn), um etwaige Fehler zu beheben. Indem sie genügend dieser kleinen Tauschvorgänge durchführen, können sie die Farben so anordnen, dass die gesamte neue, größere Stadt perfekt funktioniert.

3. Die „Lego"-Strategie (Schließen der Schleife)

Der mächtigste Teil des Papiers ist, wie sie diese Werkzeuge kombinieren, um jede mögliche Größe zu lösen.

Die Produktregel: Wenn Sie das Rätsel für einen 2D-Donut und einen 3D-Donut lösen können, können Sie es automatisch für einen 6D-Donut lösen (weil $2 \times 3 = 6$ ). Es ist, als würde man sagen: Wenn man einen perfekten 2x2-Block und einen perfekten 3x3-Block bauen kann, kann man sie stapeln, um einen perfekten 6x6-Block zu bauen.
Die Nachfolger-Regel: Wenn man es für einen 5D-Donut lösen kann, kann man es automatisch für einen 11D-Donut lösen (weil $2 \times 5 + 1 = 11$ ). Dies ist ein neuer „magischer Schritt", den die Autoren entdeckt haben.

Das große Fazit:
Die Autoren bewiesen, dass wenn man die Lösungen für die kleinen, grundlegenden Bausteine (Dimensionen 2, 3, 5 und 7) hat, man diese „Produkt"- und „Nachfolger"-Regeln verwenden kann, um die Lösung für jede Dimension zu bauen, egal wie riesig sie ist.

Sie bewiesen die Grundlagen für die Dimensionen 2 und 3 selbst.
Sie verwendeten bekannte Ergebnisse für die Dimensionen 5 und 7.
Sie kombinierten diese mit ihren neuen Regeln, um zu beweisen, dass jeder ungeradzahlige Torus in jeder Dimension eine perfekte Hamilton-Zerlegung besitzt.

4. Der „Computerbeweis"

Die Autoren haben dies nicht nur auf Papier geschrieben; sie haben ihren gesamten Beweis auch in Code für ein Computerprogramm namens Lean übersetzt. Dies ist wie das Schreiben eines Rezepts und dann das Befolgen jedes einzelnen Schritts durch einen Roboter-Koch, um sicherzustellen, dass keine Fehler auftreten. Der Computer verifizierte, dass ihre Logik perfekt standhält, und gab ihnen zusätzliches Vertrauen, dass ihre Behauptung über die „perfekte Schleife" zu 100 % wahr ist.

Zusammenfassung

Kurz gesagt löst dieses Papier ein jahrzehntealtes Rätsel über die Verkehrslenkung auf mehrdimensionalen Donuts. Es beweist, dass solange der Donut in jede Richtung eine ungerade Anzahl von Haltestellen hat, man die Straßen immer so einfärben kann, dass jede Farbe eine perfekte, sich nicht wiederholende Tour durch die gesamte Stadt erstellt. Dies gelang ihnen durch die Erfindung zweier neuer Konstruktionsmethoden und die Demonstration, wie man sie wie Lego-Steine kombinieren kann, um Lösungen für jede denkbare Stadtgröße zu bauen.

Technische Zusammenfassung: Ein Prefix-Count-Abschlusssatz für Hamilton-Zerlegungen gerichteter Tori bei ungeraden Moduln

Problemstellung
Der Artikel behandelt das Problem der Hamilton-Zerlegung für gerichtete kartesische Produkte von Zyklen, speziell den orientierten gleichseitigen $d$ -Torus $D_d(m) = \text{Cay}((\mathbb{Z}/m\mathbb{Z})^d, \{e_0, \dots, e_{d-1}\})$ . Eine Hamilton-Zerlegung erfordert eine Partitionierung der $d|V|$ Bögen des Graphen in genau $d$ disjunkte gerichtete Hamilton-Zyklen. Während die Hamilton-Eigenschaft (die Existenz eines einzigen aufspannenden Zyklus) für solche Graphen gut untersucht ist, blieb das stärkere Bogen-Partitionierungsproblem für alle Dimensionen $d \ge 2$ und ungerade Moduln $m \ge 3$ ungelöst. Der Artikel zielt darauf ab zu beweisen, dass $D_d(m)$ für jede ganze Zahl $d \ge 2$ und jede ungerade ganze Zahl $m \ge 3$ eine gerichtete Hamilton-Zerlegung zulässt.

Methodik
Die Beweisstrategie stützt sich auf zwei primäre Abschlussmechanismen, die die Konstruktion von Zerlegungen für beliebige Dimensionen auf Basis einer Menge „gelöster" Basisdimensionen ermöglichen. Die Methodik wird in zwei Zweige unterteilt, die auf der Beziehung zwischen dem Modul $m$ und der Dimension $d$ basieren:

Hoher-Modulus-Zählzweig ( $m \ge d$ ):
- Wurzel-Flache Zertifikate: Die Autoren führen ein „wurzel-flaches Zertifikat" ein, eine Struktur, die auf der Schichtensumme $S(x) = \sum x_i = 0$ definiert ist. Dies reduziert das globale Zerlegungsproblem auf die Konstruktion lokaler Abbildungen auf einem wurzel-flachen Schnitt $A_{d,m}$ .
- Prefix-Koordinaten und Ein-Schicht-Faktorisierung: Der wurzel-flache Raum wird über eine dreieckige Bijektion auf Prefix-Koordinaten abgebildet. Die Zerlegung wird schichtweise unter Verwendung von Abbildungen $M^\sigma_c$ konstruiert, die Prefix-Koordinaten basierend auf Symbolmengen $\{0, \Delta, 2, \dots, d-1\}$ permutieren.
- Prefix-Zähl-Primitivität: Ein entscheidendes Kriterium (Satz 4.4) stellt sicher, dass die Komposition dieser Schichtabbildungen einen einzigen Zyklus bildet. Dies erfordert spezifische Zählbedingungen für die in der Sequenz verwendeten Symbole: $\gcd(N_0, m) = 1$ und $\gcd(N_k - N_\Delta, m) = 1$ für $k \ge 2$ .
- Vorzeichenbehaftete Binärschichten: Um diese Zählbedingungen für $m \ge d$ (wobei $d$ ungerade ist) zu erfüllen, konstruieren die Autoren „prefix-zulässige Zählmatrizen". Für $q \ge 2$ (wobei $m = (d-1)q + r$ ) nutzen sie vorzeichenbehaftete Binärschichten (Matrizen mit Einträgen $\{-2, -1, 1, 2\}$ ), um Zeilen- und Spaltensummen auszugleichen, während die erforderlichen modularen Einheiten erhalten bleiben. Eine separate Matching-Korrektur behandelt den eingeschränkten Fall $q=1$ .
Basis-Schwanz-Modul-Tauschzweig ( $m < d$ ):
- Basis-Schwanz-Hebung: Wenn der Modul im Verhältnis zur Dimension klein ist, verwendet der Artikel eine „Basis-Schwanz"-Konstruktion. Eine gelöste Basisdimension $b$ (wobei $D_b(m)$ zerlegbar ist) wird mit einem Schwanz der Dimension $T = d-b$ kombiniert.
- Zylinder-Zerlegung: Der Basis-Multigraph wird in Zylinder zerlegt. Aktive Bögen in der Basis erhalten Symbole aus einem Schwanz-Alphabet, um „lokale Symbol-Tauschvorgänge" zu planen.
- Aktive Restwert-Planung: Unter Verwendung eines „Zylinder-Tausch-Reservoirs" reservieren die Autoren bestimmte Knoten, um lokale Vertauschungen von Symbolen zwischen Farben durchzuführen. Dies ermöglicht die Anpassung der Farb-Symbol-Zähl-Restwerte, um die für die Schwanzdimension erforderlichen Prefix-Zähl-Primitivitätsbedingungen zu erfüllen, und hebt effektiv die Basiszerlegung auf die volle Dimension $d$ an.

Hauptbeiträge

Zwei Abschlussmechanismen: Der Artikel etabliert zwei verschiedene Abschlussregeln für die Menge $S$ $S$ gelöster Dimensionen:
- Produkt-Abschluss: Wenn $a, b \in S$ , dann $ab \in S$ .
- Nachfolger-Abschluss: Wenn $b \in S$ und $b \ge 5$ , dann $2b + 1 \in S$ .
Hoher-Modulus-Konstruktion: Eine einheitliche Konstruktion für ungerade $d \ge 5$ und $m \ge d$ unter Verwendung vorzeichenbehafteter Binärschichten und Prefix-Zählmatrizen, unabhängig von vorab gelösten Basisdimensionen.
Basis-Schwanz-Modul-Tausch-Satz: Ein allgemeiner Satz (Satz 1.3), der $D_d(m)$ für $m < d$ unter Angabe einer gelösten Basis $b$ löst, sofern $d$ in Summen von Einheiten modulo $m$ zerlegt werden kann und bestimmte Größenungleichungen ( $T > b$ und $mb > m \cdot d \cdot T$ ) gelten.
Formalisierung: Die Ergebnisse werden von einer Lean-Formalisierung (Lean 4) begleitet, die den All-Dimensionen-Satz und die spezifische Abhängigkeitsstruktur des Beweises verifiziert.

Ergebnisse
Der Artikel beweist Satz 1.5: Für jede ganze Zahl $d \ge 2$ und jede ungerade ganze Zahl $m \ge 3$ zulässt der gerichtete Basis-Cayley-Torus $D_d(m)$ eine gerichtete Hamilton-Zerlegung.

Der Beweis erfolgt durch die Identifizierung einer minimalen Menge von Basisdimensionen:

Dimensionen 2 und 3: Bewiesen in Anhang B (Dimension 2 ist klassisch; Dimension 3 wird für ungerade $m$ bewiesen).
Dimensionen 5 und 7: Entnommen aus zitierten externen Sätzen ([22], [23]).

Unter Verwendung der Abschlussregeln:

Der Produkt-Abschluss erzeugt Dimensionen $4, 6, 8, 9, 10, \dots$ .
Der Nachfolger-Abschluss (beginnend bei $b=5$ ) erzeugt $11$ und anschließend höhere ungerade Dimensionen.
Ein „dyadisch-triadischer Intervall-Treffer"-Argument (Lemma 10.3) zeigt, dass für jedes ungerade $d \ge 29$ eine gelöste Basis $b \in \langle 2, 3 \rangle$ existiert, sodass die Basis-Schwanz-Bedingungen erfüllt sind.
Starke Induktion bestätigt, dass jedes $d \ge 2$ abgedeckt ist.

Bedeutung und Behauptungen
Der Artikel behauptet, das Problem der Hamilton-Zerlegung für die gesamte Klasse der gleichseitigen gerichteten Tori mit ungeraden Moduln gelöst zu haben. Er positioniert diese Arbeit als Lösung des Bogen-Partitionierungsproblems, das stärker ist als das Hamilton-Eigenschafts-Problem, das in der vorherigen Literatur behandelt wurde (z. B. Trotter–Erdős, Curran–Witte).

Die Autoren betonen die strukturelle Natur des Beweises:

Er vereint die Fälle mit hohem und niedrigem Modul durch unterschiedliche, aber komplementäre Mechanismen (Zählmatrizen vs. modulare Tauschvorgänge).
Er reduziert das unendliche Problem aller Dimensionen auf eine endliche Menge von Basisinputs (2, 3, 5, 7) und zwei algebraische Abschlussoperationen.
Die Einbeziehung einer maschinenprüfbaren Formalisierung dient als Verifikationsartefakt für die komplexen kombinatorischen Argumente, insbesondere die komplizierten Zähl- und Matching-Bedingungen im Basis-Schwanz-Zweig.

Der Artikel behauptet nicht, das Problem für gerade Moduln oder nicht-gleichseitige Tori gelöst zu haben, noch schlägt er neue Anwendungen jenseits der theoretischen Lösung dieses spezifischen Zerlegungsproblems vor. Die Bedeutung liegt in der Vollständigkeit des Ergebnisses für die angegebene Graphklasse und der rigorosen formalen Verifizierung.