← All papers
First page of Short Second Proof of the Odd-Modulus Directed Torus Hamilton Decomposition Theorem

Short Second Proof of the Odd-Modulus Directed Torus Hamilton Decomposition Theorem

SangHyun Park

math.CO Jun 19, 2026 · v1 math.GR
Formally verifies in Lean 4 a second proof of the odd-modulus directed torus Hamilton decomposition theorem.
Let $D_d(m)=\operatorname{Cay}((\mathbb Z/m\mathbb Z)^d,\{e_1,\ldots,e_d\})$, with all generators oriented positively. We give a second proof that $D_d(m)$ decomposes into $d$ directed Hamilton cycles for every $d\ge 2$ and every odd $m\ge 3$. The combinatorial core is a fixed-row-sum selection theorem for replicated supports: when each indexed support $A$ is repeated in $m$ identical rows, one can select $\lfloor |A|/2\rfloor$ entries from each row so that every column total is a unit modulo $m$. Applied to the Hamilton factors using a chosen coordinate direction, these selections prescribe the voltages in a cyclic lift that splits the direction into two. In fibre coordinates, the lifted successor is $\widehat h_j(x,z)=(h_j(x),z+\mathbf 1_{\{j\in M(x)\}})$. After one traversal of the base Hamilton cycle, the fibre return is translation by the total carry. Since this carry is a unit modulo $m$, the return is a single $m$-cycle and the lifted factor is Hamilton. The new fibres also preserve the direction-constant block structure required for the next split. Iterating from a directed $m$-cycle with $d$ parallel copies of each arc yields the desired decomposition. The proof strategy was proposed with the assistance of OpenAI GPT-5.5 Pro and formally verified in Lean 4.

Give a second proof that the directed torus Cayley graph D_d(m) decomposes into d directed Hamilton cycles for every d>=2 and odd m>=3.

The core is a fixed-row-sum selection theorem for replicated supports, applied to Hamilton factors via a chosen coordinate to prescribe voltages in a cyclic lift that splits the direction. Since the total fibre carry is a unit modulo m, the return is a single m-cycle. The strategy was proposed with OpenAI GPT-5.5 Pro and formally verified in Lean 4.

Iterating the construction from a directed m-cycle yields the desired Hamilton decomposition, machine-checked in Lean 4.