🔢 mathematics

Hamilton decompositions of all directed tori at odd modulus

This paper proves that the directed Cartesian product of $d$ directed $m$ -cycles admits a directed Hamilton decomposition for all dimensions $d \geq 2$ and all odd moduli $m \geq 3$ , utilizing a combination of new closure mechanisms, base dimension results, and formal verification in Lean 4.

Original authors: SangHyun Park

Published 2026-05-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: SangHyun Park

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a giant, multi-dimensional donut made of a grid of points. In mathematics, this is called a torus. Now, imagine that at every single point on this donut, there are several one-way streets (arrows) leading out to neighboring points. The paper you provided is about a very specific puzzle: Can we color all these one-way streets with different colors so that each color forms a single, giant loop that visits every single point on the donut exactly once?

If we can do this, we have "decomposed" the donut into perfect, non-overlapping loops. The paper proves that for a specific type of donut (where the number of points along each side is an odd number like 3, 5, 7, etc.), the answer is yes, we can always do this, no matter how many dimensions the donut has.

Here is how the authors solved this puzzle, explained through simple analogies:

1. The Goal: The Perfect Loop

Think of the donut as a city with $d$ different directions you can drive (North, East, Up, etc.). The city is huge, and every intersection has exactly $d$ roads leaving it.

The Challenge: You need to paint every road in the city using $d$ different paint colors.
The Rule: If you follow only the "Red" roads, you must eventually drive through every single intersection in the city and return to your start without ever visiting the same intersection twice. The same must be true for "Blue," "Green," and every other color.
The Paper's Claim: For any city size where the number of blocks in each direction is an odd number, this perfect coloring is always possible.

2. The Two Main Tools

The authors didn't just guess; they built two different "machines" to solve the puzzle depending on how big the city is compared to how many directions there are.

Tool A: The "High-Rise" Machine (For Big Cities)

When it works: When the city is very large (the number of blocks $m$ is bigger than the number of directions $d$ ).
How it works: Imagine the city is a skyscraper with many floors. The authors use a clever counting trick called "Prefix-Count."

They assign a "score" to every step you take.
They ensure that if you follow a specific color, your scores add up in a way that guarantees you won't get stuck in a small loop. You are forced to keep climbing until you visit every floor and every room.
They use a "signed binary" method (like a balance scale with positive and negative weights) to make sure the math works out perfectly so that the loop closes only after visiting everyone.

Tool B: The "Base-and-Tail" Machine (For Small Cities)

When it works: When the city is small (the number of blocks $m$ is smaller than the number of directions $d$ ).
How it works: This is like building a new, complex city by taking a smaller, already-solved city and attaching a "tail" to it.

The Base: They start with a smaller version of the problem that they already know how to solve (like a 5-dimensional city).
The Tail: They add extra dimensions (the "tail").
The Trade: They use a "local swap" trick. Imagine you are at a specific intersection. You have a few roads going into the "tail." The authors show that you can swap the colors of these roads locally (like trading cards with a neighbor) to fix any errors. By doing enough of these small trades, they can arrange the colors so that the whole new, bigger city works perfectly.

3. The "Lego" Strategy (Closing the Loop)

The most powerful part of the paper is how they combine these tools to solve every possible size.

The Product Rule: If you can solve the puzzle for a 2D donut and a 3D donut, you can automatically solve it for a 6D donut (because $2 \times 3 = 6$ ). It's like saying if you can build a perfect 2x2 block and a perfect 3x3 block, you can stack them to make a perfect 6x6 block.
The Successor Rule: If you can solve it for a 5D donut, you can automatically solve it for an 11D donut (because $2 \times 5 + 1 = 11$ ). This is a new "magic step" the authors discovered.

The Grand Conclusion:
The authors proved that if you have the solutions for the small, basic building blocks (dimensions 2, 3, 5, and 7), you can use these "Product" and "Successor" rules to build the solution for any dimension, no matter how huge.

They proved the basics for dimensions 2 and 3 themselves.
They used known results for dimensions 5 and 7.
They combined these with their new rules to prove that every odd-sized torus in every dimension has a perfect Hamilton decomposition.

4. The "Computer Proof"

The authors didn't just write this on paper; they also translated their entire proof into code for a computer program called Lean. This is like writing a recipe and then having a robot chef follow every single step to ensure there are no mistakes. The computer verified that their logic holds up perfectly, giving them extra confidence that their "perfect loop" claim is 100% true.

Summary

In short, this paper solves a decades-old puzzle about routing traffic on multi-dimensional donuts. It proves that as long as the donut has an odd number of stops in every direction, you can always color the roads so that every color creates a perfect, non-repeating tour of the entire city. They did this by inventing two new construction methods and showing how to combine them like Lego bricks to build solutions for any size city imaginable.

Technical Summary: A Prefix-Count Closure Theorem for Hamilton Decompositions of Directed Tori at Odd Moduli

Problem Statement
The paper addresses the problem of Hamilton decomposition for directed Cartesian products of cycles, specifically the oriented equal-side $d$ -torus $D_d(m) = \text{Cay}((\mathbb{Z}/m\mathbb{Z})^d, \{e_0, \dots, e_{d-1}\})$ . A Hamilton decomposition requires partitioning the $d|V|$ arcs of the graph into exactly $d$ disjoint directed Hamilton cycles. While Hamiltonicity (the existence of a single spanning cycle) for such graphs is well-studied, the stronger arc-partition problem for all dimensions $d \ge 2$ and odd moduli $m \ge 3$ remained unresolved. The paper aims to prove that $D_d(m)$ admits a directed Hamilton decomposition for every integer $d \ge 2$ and every odd integer $m \ge 3$ .

Methodology
The proof strategy relies on two primary closure mechanisms that allow the construction of decompositions for arbitrary dimensions based on a set of "solved" base dimensions. The methodology is divided into two branches based on the relationship between the modulus $m$ and the dimension $d$ :

High-Modulus Count Branch ( $m \ge d$ ):
- Root-Flat Certificates: The authors introduce a "root-flat certificate," a structure defined on the layer sum $S(x) = \sum x_i = 0$ . This reduces the global decomposition problem to constructing local maps on a root-flat slice $A_{d,m}$ .
- Prefix Coordinates and One-Layer Factorization: The root-flat space is mapped to prefix coordinates via a triangular bijection. The decomposition is constructed layer-by-layer using maps $M^\sigma_c$ that permute prefix coordinates based on symbol sets $\{0, \Delta, 2, \dots, d-1\}$ .
- Prefix-Count Primitivity: A key criterion (Theorem 4.4) ensures that the composition of these layer maps forms a single cycle. This requires specific count conditions on the symbols used in the sequence: $\gcd(N_0, m) = 1$ and $\gcd(N_k - N_\Delta, m) = 1$ for $k \ge 2$ .
- Signed Binary Layers: To satisfy these count conditions for $m \ge d$ (where $d$ is odd), the authors construct "prefix-admissible count matrices." For $q \ge 2$ (where $m = (d-1)q + r$ ), they utilize signed binary layers (matrices with entries $\{-2, -1, 1, 2\}$ ) to balance row and column sums while maintaining the required modular units. A separate matching correction handles the restricted case $q=1$ .
Base-Tail Modular-Trade Branch ( $m < d$ ):
- Base-Tail Lift: When the modulus is small relative to the dimension, the paper employs a "base-tail" construction. A solved base dimension $b$ (where $D_b(m)$ is decomposable) is combined with a tail of dimension $T = d-b$ .
- Cylinder Decomposition: The base multigraph is decomposed into cylinders. Active arcs in the base are assigned symbols from a tail alphabet to schedule "local symbol trades."
- Active Residue Scheduling: Using a "cylinder trade reservoir," the authors reserve specific vertices to perform local swaps of symbols between colors. This allows the adjustment of color-symbol count residues to satisfy the prefix-count primitivity conditions required for the tail dimension, effectively lifting the base decomposition to the full dimension $d$ .

Key Contributions

Two Closure Mechanisms: The paper establishes two distinct closure rules for the set $S$ $S$ of solved dimensions:
- Product Closure: If $a, b \in S$ , then $ab \in S$ .
- Successor Closure: If $b \in S$ and $b \ge 5$ , then $2b + 1 \in S$ .
High-Modulus Construction: A uniform construction for odd $d \ge 5$ and $m \ge d$ using signed binary layers and prefix-count matrices, independent of any pre-solved base dimensions.
Base-Tail Modular-Trade Theorem: A general theorem (Theorem 1.3) that solves $D_d(m)$ for $m < d$ given a solved base $b$ , provided $d$ can be decomposed into sums of units modulo $m$ and specific size inequalities ( $T > b$ and $mb > m \cdot d \cdot T$ ) hold.
Formalization: The results are accompanied by a Lean formalization (Lean 4) that verifies the all-dimensions theorem and the specific dependency structure of the proof.

Results
The paper proves Theorem 1.5: For every integer $d \ge 2$ and every odd integer $m \ge 3$ , the directed basis Cayley torus $D_d(m)$ admits a directed Hamilton decomposition.

The proof proceeds by identifying a minimal set of base dimensions:

Dimensions 2 and 3: Proved in Appendix B (Dimension 2 is classical; Dimension 3 is proved for odd $m$ ).
Dimensions 5 and 7: Sourced from cited external theorems ([22], [23]).

Using the closure rules:

Product closure generates dimensions $4, 6, 8, 9, 10, \dots$ .
Successor closure (starting from $b=5$ ) generates $11$, and subsequently higher odd dimensions.
A "dyadic-triadic interval-hitting" argument (Lemma 10.3) shows that for any odd $d \ge 29$ , there exists a solved base $b \in \langle 2, 3 \rangle$ such that the base-tail conditions are met.
Strong induction confirms that every $d \ge 2$ is covered.

Significance and Claims
The paper claims to resolve the Hamilton decomposition problem for the entire class of equal-side directed tori with odd moduli. It positions this work as a solution to the arc-partition problem, which is stronger than the Hamiltonicity problem addressed in prior literature (e.g., Trotter–Erdős, Curran–Witte).

The authors emphasize the structural nature of the proof:

It unifies the high-modulus and low-modulus cases through distinct but complementary mechanisms (count matrices vs. modular trades).
It reduces the infinite problem of all dimensions to a finite set of base inputs (2, 3, 5, 7) and two algebraic closure operations.
The inclusion of a machine-checkable formalization serves as a verification artifact for the complex combinatorial arguments, particularly the intricate counting and matching conditions in the base-tail branch.

The paper does not claim to solve the problem for even moduli or non-equal-side tori, nor does it propose new applications beyond the theoretical resolution of this specific decomposition problem. The significance lies in the completeness of the result for the specified class of graphs and the rigorous formal verification provided.