🔢 mathematics

Hamilton decompositions of all directed tori at odd modulus

Dit artikel bewijst dat het gerichte Cartesisch product van $d$ gerichte $m$ -cycli een gerichte Hamilton-decompositie toelaat voor alle dimensies $d \geq 2$ en alle oneven moduli $m \geq 3$ , met gebruikmaking van een combinatie van nieuwe sluitingsmechanismen, resultaten voor basisdimensies en formele verificatie in Lean 4.

Oorspronkelijke auteurs: SangHyun Park

Gepubliceerd 2026-05-07

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: SangHyun Park

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een gigantische, multidimensionale donut voor, gemaakt van een rooster van punten. In de wiskunde heet dit een torus. Stel je nu voor dat op elk enkel punt op deze donut meerdere eenrichtingsstraten (pijlen) uitkomen die leiden naar aangrenzende punten. Het door jou aangeleverde artikel gaat over een zeer specifiek raadsel: Kunnen we al deze eenrichtingsstraten met verschillende kleuren inkleuren, zodat elke kleur één enkele, gigantische lus vormt die elk punt op de donut precies één keer bezoekt?

Als we dit kunnen, hebben we de donut "ontbonden" in perfecte, niet-overlappende lussen. Het artikel bewijst dat voor een specifiek type donut (waarbij het aantal punten langs elke zijde een oneven getal is, zoals 3, 5, 7, enz.), het antwoord ja is, we kunnen dit altijd doen, ongeacht hoeveel dimensies de donut heeft.

Hier is hoe de auteurs dit raadsel oplossen, uitgelegd via eenvoudige analogieën:

1. Het Doel: De Perfecte Lus

Stel je de donut voor als een stad met $d$ verschillende rijrichtingen (Noord, Oost, Omhoog, enz.). De stad is enorm, en elk kruispunt heeft precies $d$ wegen die er vandaan lopen.

De Uitdaging: Je moet elke weg in de stad verven met $d$ verschillende verfkleuren.
De Regel: Als je alleen de "Rode" wegen volgt, moet je uiteindelijk elk enkel kruispunt in de stad passeren en terugkeren naar je startpunt, zonder ooit hetzelfde kruispunt twee keer te bezoeken. Dit moet ook gelden voor "Blauw", "Groen" en elke andere kleur.
De Bewering van het Artikel: Voor elke stadsomvang waarbij het aantal blokken in elke richting een oneven getal is, is deze perfecte kleuring altijd mogelijk.

2. De Twee Hoofdtools

De auteurs gokten niet zomaar; ze bouwden twee verschillende "machines" om het raadsel op te lossen, afhankelijk van hoe groot de stad is in verhouding tot het aantal richtingen.

Tool A: De "Hoge-Rise"-Machine (Voor Grote Steden)

Wanneer het werkt: Wanneer de stad zeer groot is (het aantal blokken $m$ groter is dan het aantal richtingen $d$ ).
Hoe het werkt: Stel je de stad voor als een wolkenkrabber met vele verdiepingen. De auteurs gebruiken een slimme teltruc genaamd "Prefix-Count".

Ze wijzen elke stap die je zet een "score" toe.
Ze zorgen ervoor dat als je een specifieke kleur volgt, je scores zo optellen dat je gegarandeerd niet vastzit in een kleine lus. Je wordt gedwongen te blijven klimmen tot je elke verdieping en elke kamer hebt bezocht.
Ze gebruiken een "signed binary"-methode (zoals een balansschaal met positieve en negatieve gewichten) om ervoor te zorgen dat de wiskunde perfect uitkomt, zodat de lus pas sluit nadat iedereen is bezocht.

Tool B: De "Basis-en-Staart"-Machine (Voor Kleine Steden)

Wanneer het werkt: Wanneer de stad klein is (het aantal blokken $m$ kleiner is dan het aantal richtingen $d$ ).
Hoe het werkt: Dit is als het bouwen van een nieuwe, complexe stad door een kleinere, al opgeloste stad te nemen en er een "staart" aan te bevestigen.

De Basis: Ze beginnen met een kleinere versie van het probleem die ze al weten op te lossen (zoals een 5-dimensionale stad).
De Staart: Ze voegen extra dimensies toe (de "staart").
De Ruil: Ze gebruiken een "lokale swap"-truc. Stel je voor dat je op een specifiek kruispunt staat. Je hebt een paar wegen die de "staart" in gaan. De auteurs tonen aan dat je de kleuren van deze wegen lokaal kunt verwisselen (zoals kaarten ruilen met een buurman) om eventuele fouten te herstellen. Door genoeg van deze kleine ruilen te doen, kunnen ze de kleuren zo rangschikken dat de hele nieuwe, grotere stad perfect werkt.

3. De "Lego"-Strategie (De Lus Sluiten)

Het krachtigste deel van het artikel is hoe ze deze tools combineren om elke mogelijke omvang op te lossen.

De Productregel: Als je het raadsel kunt oplossen voor een 2D-donut en een 3D-donut, kun je het automatisch oplossen voor een 6D-donut (omdat $2 \times 3 = 6$ ). Het is alsof je zegt: als je een perfecte 2x2-blok kunt bouwen en een perfecte 3x3-blok, kun je ze stapelen om een perfecte 6x6-blok te maken.
De Opvolgerregel: Als je het kunt oplossen voor een 5D-donut, kun je het automatisch oplossen voor een 11D-donut (omdat $2 \times 5 + 1 = 11$ ). Dit is een nieuwe "magische stap" die de auteurs hebben ontdekt.

De Grote Conclusie:
De auteurs bewezen dat als je de oplossingen hebt voor de kleine, fundamentele bouwstenen (dimensies 2, 3, 5 en 7), je deze "Product"- en "Opvolger"-regels kunt gebruiken om de oplossing te bouwen voor elke dimensie, hoe enorm ook.

Ze bewezen de basis zelf voor dimensies 2 en 3.
Ze gebruikten bekende resultaten voor dimensies 5 en 7.
Ze combineerden deze met hun nieuwe regels om te bewijzen dat elke torus met een oneven grootte in elke dimensie een perfecte Hamilton-decompositie heeft.

4. Het "Computerbewijs"

De auteurs schreven dit niet alleen op papier; ze vertaalden hun hele bewijs ook naar code voor een computerprogramma genaamd Lean. Dit is alsof je een recept schrijft en vervolgens een robotchef elke enkele stap laat volgen om zeker te zijn dat er geen fouten zijn. De computer verifieerde dat hun logica perfect standhoudt, wat hen extra vertrouwen gaf dat hun claim van "perfecte lus" 100% waar is.

Samenvatting

Kortom, dit artikel lost een decennia oud raadsel op over verkeersrouting op multidimensionale donuts. Het bewijst dat zolang de donut in elke richting een oneven aantal stops heeft, je de wegen altijd zo kunt inkleuren dat elke kleur een perfecte, niet-herhalende tour van de hele stad creëert. Ze deden dit door twee nieuwe constructiemethoden uit te vinden en te laten zien hoe ze te combineren als Lego-blokken om oplossingen te bouwen voor elke denkbeeldige stadsomvang.

Technische Samenvatting: Een Sluitstelling voor Prefix-aantallen voor Hamilton-decomposities van Gerichte Tori bij Oneven Moduli

Probleemstelling
Het artikel behandelt het probleem van Hamilton-decompositie voor gerichte Cartesische producten van cycli, specifiek de georiënteerde gelijkzijdige $d$ -torus $D_d(m) = \text{Cay}((\mathbb{Z}/m\mathbb{Z})^d, \{e_0, \dots, e_{d-1}\})$ . Een Hamilton-decompositie vereist een partitie van de $d|V|$ bogen van het graaf in precies $d$ disjuncte gerichte Hamilton-cycli. Hoewel Hamiltoniciteit (het bestaan van een enkele doorloopende cyclus) voor dergelijke grafen goed bestudeerd is, bleef het sterkere probleem van boog-partitie voor alle dimensies $d \ge 2$ en oneven moduli $m \ge 3$ onopgelost. Het artikel beoogt te bewijzen dat $D_d(m)$ een gerichte Hamilton-decompositie toestaat voor elke gehele $d \ge 2$ en elke oneven gehele $m \ge 3$ .

Methodologie
De bewijsstrategie steunt op twee primaire sluitmechanismen die het mogelijk maken decomposities voor willekeurige dimensies te construeren op basis van een set "opgeloste" basisdimensies. De methodologie is verdeeld in twee takken, gebaseerd op de relatie tussen de modulus $m$ en de dimensie $d$ :

Tak voor Hoge-Modulus-aantallen ( $m \ge d$ ):
- Root-Flat Certificaten: De auteurs introduceren een "root-flat certificaat", een structuur gedefinieerd op de laag-som $S(x) = \sum x_i = 0$ . Dit reduceert het globale decompositieprobleem tot het construeren van lokale afbeeldingen op een root-flat snede $A_{d,m}$ .
- Prefix-coördinaten en Één-laags Factorisatie: De root-flat-ruimte wordt via een driehoekige bijectie afgebeeld op prefix-coördinaten. De decompositie wordt laag-voor-laag geconstrueerd met behulp van afbeeldingen $M^\sigma_c$ die prefix-coördinaten permuteren op basis van symboolsets $\{0, \Delta, 2, \dots, d-1\}$ .
- Prefix-aantal Primitiviteit: Een cruciaal criterium (Stelling 4.4) garandeert dat de samenstelling van deze laag-afbeeldingen een enkele cyclus vormt. Dit vereist specifieke aantalvoorwaarden voor de symbolen gebruikt in de reeks: $\gcd(N_0, m) = 1$ en $\gcd(N_k - N_\Delta, m) = 1$ voor $k \ge 2$ .
- Getekende Binaire Laagjes: Om aan deze aantalvoorwaarden te voldoen voor $m \ge d$ (waarbij $d$ oneven is), construeren de auteurs "prefix-toelaatbare aantal-matrices". Voor $q \ge 2$ (waarbij $m = (d-1)q + r$ ) maken ze gebruik van getekende binaire laagjes (matrices met elementen $\{-2, -1, 1, 2\}$ ) om rij- en kolom-sommen in evenwicht te brengen terwijl de vereiste modulaire eenheden behouden blijven. Een aparte matching-correctie behandelt het beperkte geval $q=1$ .
Tak voor Basis-Staart Modulaire-ruil ( $m < d$ ):
- Basis-Staart Lift: Wanneer de modulus klein is ten opzichte van de dimensie, hanteert het artikel een "basis-staart" constructie. Een opgeloste basisdimensie $b$ (waarbij $D_b(m)$ decomposeerbaar is) wordt gecombineerd met een staart van dimensie $T = d-b$ .
- Cilinder-decompositie: De basis-multigraaf wordt gedecomposeerd in cilinders. Actieve bogen in de basis krijgen symbolen toegewezen uit een staart-alphabet om "lokale symboolruilen" te plannen.
- Actief Restant Plannen: Met behulp van een "cilinder-ruil-reservoir" reserveren de auteurs specifieke hoekpunten om lokale wisselingen van symbolen tussen kleuren uit te voeren. Dit maakt het aanpassen van kleur-symbool-aantal-restanten mogelijk om te voldoen aan de prefix-aantal primitiviteitsvoorwaarden die vereist zijn voor de staartdimensie, waardoor de basisdecompositie effectief wordt gelift naar de volledige dimensie $d$ .

Belangrijkste Bijdragen

Twee Sluitmechanismen: Het artikel stelt twee distincte sluitregels vast voor de set $S$ $S$ van opgeloste dimensies:
- Productsluiting: Als $a, b \in S$ , dan $ab \in S$ .
- Opvolgersluiting: Als $b \in S$ en $b \ge 5$ , dan $2b + 1 \in S$ .
Hoge-Modulus Constructie: Een uniforme constructie voor oneven $d \ge 5$ en $m \ge d$ met behulp van getekende binaire laagjes en prefix-aantal-matrices, onafhankelijk van enige vooraf opgeloste basisdimensies.
Basis-Staart Modulaire-ruil Stelling: Een algemene stelling (Stelling 1.3) die $D_d(m)$ oplost voor $m < d$ gegeven een opgeloste basis $b$ , mits $d$ kan worden ontbonden in sommen van eenheden modulo $m$ en specifieke grootte-ongelijkheden ( $T > b$ en $mb > m \cdot d \cdot T$ ) gelden.
Formalisatie: De resultaten worden begeleid door een Lean-formalisatie (Lean 4) die de stelling voor alle dimensies verifieert en de specifieke afhankelijkheidsstructuur van het bewijs.

Resultaten
Het artikel bewijst Stelling 1.5: Voor elke gehele $d \ge 2$ en elke oneven gehele $m \ge 3$ , staat de gerichte basis Cayley-torus $D_d(m)$ een gerichte Hamilton-decompositie toe.

Het bewijs verloopt door een minimale set basisdimensies te identificeren:

Dimensies 2 en 3: Bewezen in Aanhangsel B (Dimensie 2 is klassiek; Dimensie 3 is bewezen voor oneven $m$ ).
Dimensies 5 en 7: Geput uit geciteerde externe stellingen ([22], [23]).

Met gebruikmaking van de sluitregels:

Productsluiting genereert dimensies $4, 6, 8, 9, 10, \dots$ .
Opvolgersluiting (beginnend bij $b=5$ ) genereert $11$, en vervolgens hogere oneven dimensies.
Een "dyadisch-triadisch interval-raak" argument (Lemma 10.3) toont aan dat voor elke oneven $d \ge 29$ er een opgeloste basis $b \in \langle 2, 3 \rangle$ bestaat zodat aan de basis-staartvoorwaarden wordt voldaan.
Sterke inductie bevestigt dat elke $d \ge 2$ is gedekt.

Betekenis en Aanspraken
Het artikel claimt het probleem van Hamilton-decompositie op te lossen voor de gehele klasse van gelijkzijdige gerichte tori met oneven moduli. Het positioneert dit werk als een oplossing voor het boog-partitieprobleem, wat sterker is dan het Hamiltoniciteitsprobleem dat in eerdere literatuur werd aangepakt (bijv. Trotter–Erdős, Curran–Witte).

De auteurs benadrukken de structurele aard van het bewijs:

Het verenigt de hoge- en lage-modulusgevallen via distincte maar complementaire mechanismen (aantal-matrices versus modulaire ruilen).
Het reduceert het oneindige probleem van alle dimensies tot een eindige set basisinputs (2, 3, 5, 7) en twee algebraïsche sluitoperaties.
De opname van een machine-controleerbare formalisatie dient als verificatie-artefact voor de complexe combinatorische argumenten, met name de ingewikkelde tel- en matchingvoorwaarden in de basis-staarttak.

Het artikel claimt niet het probleem op te lossen voor even moduli of niet-gelijkzijdige tori, noch stelt het nieuwe toepassingen voor buiten de theoretische oplossing van dit specifieke decompositieprobleem. De betekenis ligt in de volledigheid van het resultaat voor de gespecificeerde klasse van grafen en de rigoureuze formele verificatie die wordt geboden.