🔢 mathematics

Hamilton decompositions of all directed tori at odd modulus

Ce papier démontre que le produit cartésien orienté de $d$ cycles orientés de longueur $m$ admet une décomposition hamiltonienne orientée pour toutes les dimensions $d \geq 2$ et tous les modules impairs $m \geq 3$ , en utilisant une combinaison de nouveaux mécanismes de clôture, de résultats sur la dimension de base et de vérification formelle dans Lean 4.

Auteurs originaux : SangHyun Park

Publié 2026-05-07

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : SangHyun Park

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un beignet géant, multidimensionnel, constitué d'une grille de points. En mathématiques, cela s'appelle un tore. Maintenant, imaginez qu'à chaque point unique de ce beignet, plusieurs rues à sens unique (des flèches) partent vers les points voisins. L'article que vous avez fourni porte sur une énigme très spécifique : Pouvons-nous colorer toutes ces rues à sens unique avec des couleurs différentes de sorte que chaque couleur forme une seule, immense boucle qui visite chaque point du beignet exactement une fois ?

Si nous pouvons le faire, nous avons « décomposé » le beignet en boucles parfaites et non superposées. L'article prouve que pour un type spécifique de beignet (où le nombre de points le long de chaque côté est un nombre impair comme 3, 5, 7, etc.), la réponse est oui, nous pouvons toujours le faire, peu importe le nombre de dimensions du beignet.

Voici comment les auteurs ont résolu cette énigme, expliqué à travers des analogies simples :

1. L'Objectif : La Boucle Parfaite

Imaginez le beignet comme une ville avec $d$ directions différentes dans lesquelles vous pouvez conduire (Nord, Est, Haut, etc.). La ville est immense, et chaque intersection possède exactement $d$ routes qui en partent.

Le Défi : Vous devez peindre chaque route de la ville en utilisant $d$ couleurs de peinture différentes.
La Règle : Si vous ne suivez que les routes « Rouges », vous devez éventuellement traverser chaque intersection de la ville et revenir à votre point de départ sans jamais visiter la même intersection deux fois. La même chose doit être vraie pour le « Bleu », le « Vert » et toutes les autres couleurs.
L'Affirmation de l'Article : Pour toute taille de ville où le nombre de pâtés de maisons dans chaque direction est un nombre impair, ce coloriage parfait est toujours possible.

2. Les Deux Outils Principaux

Les auteurs n'ont pas simplement deviné ; ils ont construit deux « machines » différentes pour résoudre l'énigme selon la taille de la ville par rapport au nombre de directions.

Outil A : La Machine « Immeuble de Grande Hauteur » (Pour les Grandes Villes)

Quand cela fonctionne : Lorsque la ville est très grande (le nombre de pâtés de maisons $m$ est supérieur au nombre de directions $d$ ).
Comment cela fonctionne : Imaginez la ville comme un gratte-ciel avec de nombreux étages. Les auteurs utilisent une astuce de comptage ingénieuse appelée « Comptage des Préfixes ».

Ils attribuent un « score » à chaque pas que vous faites.
Ils s'assurent que si vous suivez une couleur spécifique, vos scores s'additionnent d'une manière qui garantit que vous ne resterez pas coincé dans une petite boucle. Vous êtes forcé de continuer à monter jusqu'à ce que vous visitiez chaque étage et chaque pièce.
Ils utilisent une méthode « binaire signée » (comme une balance avec des poids positifs et négatifs) pour s'assurer que les mathématiques fonctionnent parfaitement afin que la boucle ne se referme qu'après avoir visité tout le monde.

Outil B : La Machine « Base et Queue » (Pour les Petites Villes)

Quand cela fonctionne : Lorsque la ville est petite (le nombre de pâtés de maisons $m$ est inférieur au nombre de directions $d$ ).
Comment cela fonctionne : C'est comme construire une nouvelle ville complexe en prenant une ville plus petite, déjà résolue, et en y attachant une « queue ».

La Base : Ils commencent par une version plus petite du problème qu'ils savent déjà résoudre (comme une ville à 5 dimensions).
La Queue : Ils ajoutent des dimensions supplémentaires (la « queue »).
L'Échange : Ils utilisent une astuce d'« échange local ». Imaginez que vous êtes à une intersection spécifique. Vous avez quelques routes menant vers la « queue ». Les auteurs montrent que vous pouvez échanger les couleurs de ces routes localement (comme échanger des cartes avec un voisin) pour corriger toute erreur. En effectant suffisamment de ces petits échanges, ils peuvent organiser les couleurs de sorte que toute la nouvelle ville, plus grande, fonctionne parfaitement.

3. La Stratégie « Lego » (Fermer la Boucle)

La partie la plus puissante de l'article est la façon dont ils combinent ces outils pour résoudre toute taille possible.

La Règle du Produit : Si vous pouvez résoudre l'énigme pour un beignet à 2D et un beignet à 3D, vous pouvez automatiquement la résoudre pour un beignet à 6D (car $2 \times 3 = 6$ ). C'est comme dire que si vous pouvez construire un bloc parfait de 2x2 et un bloc parfait de 3x3, vous pouvez les empiler pour former un bloc parfait de 6x6.
La Règle du Successeur : Si vous pouvez la résoudre pour un beignet à 5D, vous pouvez automatiquement la résoudre pour un beignet à 11D (car $2 \times 5 + 1 = 11$ ). C'est une nouvelle « étape magique » que les auteurs ont découverte.

La Grande Conclusion :
Les auteurs ont prouvé que si vous avez les solutions pour les petits blocs de construction de base (dimensions 2, 3, 5 et 7), vous pouvez utiliser ces règles « Produit » et « Successeur » pour construire la solution pour n'importe quelle dimension, peu importe sa taille.

Ils ont prouvé les bases pour les dimensions 2 et 3 eux-mêmes.
Ils ont utilisé des résultats connus pour les dimensions 5 et 7.
Ils ont combiné ceux-ci avec leurs nouvelles règles pour prouver que chaque tore de taille impaire dans chaque dimension possède une décomposition hamiltonienne parfaite.

4. La « Preuve par Ordinateur »

Les auteurs n'ont pas seulement écrit cela sur papier ; ils ont également traduit toute leur preuve en code pour un programme informatique appelé Lean. C'est comme écrire une recette et ensuite demander à un chef robot de suivre chaque étape pour s'assurer qu'il n'y a pas d'erreurs. L'ordinateur a vérifié que leur logique tient parfaitement, leur donnant une confiance supplémentaire que leur affirmation de « boucle parfaite » est vraie à 100 %.

Résumé

En bref, cet article résout une énigme vieille de plusieurs décennies concernant la circulation routière sur des beignets multidimensionnels. Il prouve que tant que le beignet a un nombre impair d'arrêts dans chaque direction, vous pouvez toujours colorier les routes de sorte que chaque couleur crée un tour parfait et sans répétition de toute la ville. Ils ont fait cela en inventant deux nouvelles méthodes de construction et en montrant comment les combiner comme des briques Lego pour construire des solutions pour n'importe quelle taille de ville imaginable.

Résumé Technique : Un Théorème de Clôture par Comptage de Préfixes pour les Décompositions Hamiltoniennes des Torses Dirigés à Modules Impairs

Énoncé du Problème
L'article aborde le problème de la décomposition hamiltonienne pour les produits cartésiens dirigés de cycles, spécifiquement le $d$ -torse orienté à côtés égaux $D_d(m) = \text{Cay}((\mathbb{Z}/m\mathbb{Z})^d, \{e_0, \dots, e_{d-1}\})$ . Une décomposition hamiltonienne exige de partitionner les $d|V|$ arcs du graphe en exactement $d$ cycles hamiltoniens dirigés disjoints. Bien que l'hamiltonicité (l'existence d'un cycle couvrant unique) pour de tels graphes soit bien étudiée, le problème plus fort de la partition des arcs pour toutes les dimensions $d \ge 2$ et tous les modules impairs $m \ge 3$ restait non résolu. L'article vise à prouver que $D_d(m)$ admet une décomposition hamiltonienne dirigée pour tout entier $d \ge 2$ et tout entier impair $m \ge 3$ .

Méthodologie
La stratégie de preuve repose sur deux mécanismes de clôture principaux permettant la construction de décompositions pour des dimensions arbitraires à partir d'un ensemble de dimensions de base « résolues ». La méthodologie est divisée en deux branches selon la relation entre le module $m$ et la dimension $d$ :

Branche de Comptage à Module Élevé ( $m \ge d$ ) :
- Certificats à Racine Plate : Les auteurs introduisent un « certificat à racine plate », une structure définie sur la somme des couches $S(x) = \sum x_i = 0$ . Cela réduit le problème de décomposition global à la construction de cartes locales sur une tranche à racine plate $A_{d,m}$ .
- Coordonnées de Préfixes et Factorisation à Une Couche : L'espace à racine plate est mappé vers des coordonnées de préfixes via une bijection triangulaire. La décomposition est construite couche par couche en utilisant des cartes $M^\sigma_c$ qui permutent les coordonnées de préfixes basées sur des ensembles de symboles $\{0, \Delta, 2, \dots, d-1\}$ .
- Primalité du Comptage de Préfixes : Un critère clé (Théorème 4.4) garantit que la composition de ces cartes de couches forme un cycle unique. Cela nécessite des conditions spécifiques de comptage sur les symboles utilisés dans la séquence : $\gcd(N_0, m) = 1$ et $\gcd(N_k - N_\Delta, m) = 1$ pour $k \ge 2$ .
- Couches Binaires Signées : Pour satisfaire ces conditions de comptage pour $m \ge d$ (où $d$ est impair), les auteurs construisent des « matrices de comptage admissibles par préfixe ». Pour $q \ge 2$ (où $m = (d-1)q + r$ ), ils utilisent des couches binaires signées (matrices avec des entrées $\{-2, -1, 1, 2\}$ ) pour équilibrer les sommes de lignes et de colonnes tout en maintenant les unités modulaires requises. Un ajustement d'appariement séparé gère le cas restreint $q=1$ .
Branche d'Échange Modulaire Base-Queue ( $m < d$ ) :
- Relèvement Base-Queue : Lorsque le module est petit par rapport à la dimension, l'article emploie une construction « base-queue ». Une dimension de base résolue $b$ (où $D_b(m)$ est décomposable) est combinée avec une queue de dimension $T = d-b$ .
- Décomposition en Cylindres : Le multigraphe de base est décomposé en cylindres. Les arcs actifs dans la base se voient attribuer des symboles d'un alphabet de queue pour planifier des « échanges locaux de symboles ».
- Planification des Résidus Actifs : En utilisant un « réservoir d'échange de cylindres », les auteurs réservent des sommets spécifiques pour effectuer des échanges locaux de symboles entre couleurs. Cela permet d'ajuster les résidus de comptage couleur-symbole pour satisfaire les conditions de primalité du comptage de préfixes requises pour la dimension de queue, relevant ainsi efficacement la décomposition de base à la dimension complète $d$ .

Contributions Clés

Deux Mécanismes de Clôture : L'article établit deux règles de clôture distinctes pour l'ensemble $S$ $S$ des dimensions résolues :
- Clôture par Produit : Si $a, b \in S$ , alors $ab \in S$ .
- Clôture par Successeur : Si $b \in S$ et $b \ge 5$ , alors $2b + 1 \in S$ .
Construction à Module Élevé : Une construction uniforme pour $d \ge 5$ impair et $m \ge d$ utilisant des couches binaires signées et des matrices de comptage de préfixes, indépendante de toute dimension de base pré-résolue.
Théorème d'Échange Modulaire Base-Queue : Un théorème général (Théorème 1.3) qui résout $D_d(m)$ pour $m < d$ étant donné une base résolue $b$ , à condition que $d$ puisse être décomposé en sommes d'unités modulo $m$ et que des inégalités de taille spécifiques ( $T > b$ et $mb > m \cdot d \cdot T$ ) soient vérifiées.
Formalisation : Les résultats sont accompagnés d'une formalisation Lean (Lean 4) qui vérifie le théorème pour toutes les dimensions et la structure de dépendance spécifique de la preuve.

Résultats
L'article prouve le Théorème 1.5 : Pour tout entier $d \ge 2$ et tout entier impair $m \ge 3$ , le tore de Cayley de base dirigé $D_d(m)$ admet une décomposition hamiltonienne dirigée.

La preuve procède en identifiant un ensemble minimal de dimensions de base :

Dimensions 2 et 3 : Prouvées dans l'Annexe B (la dimension 2 est classique ; la dimension 3 est prouvée pour $m$ impair).
Dimensions 5 et 7 : Issues de théorèmes externes cités ([22], [23]).

En utilisant les règles de clôture :

La clôture par produit génère les dimensions $4, 6, 8, 9, 10, \dots$ .
La clôture par successeur (en partant de $b=5$ ) génère $11$, et ensuite des dimensions impaires plus élevées.
Un argument de « frappe d'intervalles dyadiques-triadiques » (Lemme 10.3) montre que pour tout $d \ge 29$ impair, il existe une base résolue $b \in \langle 2, 3 \rangle$ telle que les conditions base-queue sont remplies.
Une induction forte confirme que chaque $d \ge 2$ est couvert.

Signification et Revendications
L'article revendique la résolution du problème de décomposition hamiltonienne pour l'ensemble de la classe des tores dirigés à côtés égaux avec des modules impairs. Il positionne ce travail comme une solution au problème de partition des arcs, qui est plus fort que le problème d'hamiltonicité abordé dans la littérature antérieure (par exemple, Trotter–Erdős, Curran–Witte).

Les auteurs soulignent la nature structurelle de la preuve :

Elle unifie les cas à module élevé et à module faible grâce à des mécanismes distincts mais complémentaires (matrices de comptage contre échanges modulaires).
Elle réduit le problème infini de toutes les dimensions à un ensemble fini d'entrées de base (2, 3, 5, 7) et deux opérations de clôture algébriques.
L'inclusion d'une formalisation vérifiable par machine sert d'artefact de vérification pour les arguments combinatoires complexes, en particulier les conditions de comptage et d'appariement intricées dans la branche base-queue.

L'article ne revendique pas la résolution du problème pour les modules pairs ou les tores non à côtés égaux, ni ne propose de nouvelles applications au-delà de la résolution théorique de ce problème de décomposition spécifique. La signification réside dans l'exhaustivité du résultat pour la classe de graphes spécifiée et dans la vérification formelle rigoureuse fournie.