Hamilton decompositions of the directed 7-torus at odd modulus via root-flat certificates and a prefix-count construction

AIPR assessment

Problem difficulty is high: this is a hard combinatorial decomposition problem in a saturated area with a long history, and the paper addresses a prime-dimensional family rather than a low-hanging special case. The strengths reinforce each other well, since the new certificate formalism, the uniform large-modulus construction, and the Lean-checked boundary cases jointly produce a complete theorem. The main weaknesses are mostly around compression and scope, not correctness: the proof is speciali

Abstract

We prove that the directed seven-dimensional equal-side torus D_7(m) = Cay((Z/mZ)^7, {e_0, e_1, ..., e_6}) admits a directed Hamilton decomposition for every odd integer m >= 3. The proof has two main contributions. First, we introduce the root-flat certificate: a named verification framework in which a Hamilton decomposition of D_n(m) follows from three local conditions on a single root flat -- row Latinness, layer bijectivity, and primitive return maps. This abstraction was used informally in the earlier odd D_5(m) construction; here it appears as a definition and a theorem, providing a common verification interface for prime-dimensional base cases. Second, for every odd m >= 7, we give a uniform prefix-coordinate construction: one-layer prefix maps, a symbol-count criterion, and explicit 7x7 count matrices produce all seven Hamilton factors without a finite search. The remaining moduli m = 3 and m = 5 are exactly the boundary where the prefix-count method provably cannot work; they are handled by finite root-flat certificates whose validity is checked in Lean 4. A Lean 4 formalization verifies the Cayley statement, with the symbolic branch and the finite boundary certificates checked in the same development.

Score Breakdown

More from this week

• Beyond Visual Fidelity: Benchmarking Super-Resolution Models for Large-Scale Remote Sensing Imagery via Downstream Task Integration
• Eliminating Hidden Serialization in Multi-Node Megakernel Communication
• Succinct Graph Representations and Algorithmic Applications
• A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
• Beyond Benchmarks: MathArena as an Evaluation Platform for Mathematics with LLMs

More in Discrete Mathematics

• On Thin Perfect Matchings up to Polylogarithmic Factors
• \(\mathit{SB}(3,n)\) has no Hamiltonian cycle when \(n\) is even: a sign-of-permutation proof, with extension to all odd \(m\equiv 3\pmod 4\)
• Weak Order on the MacNeille Completion of Bruhat Order
• A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
• Succinct Graph Representations and Algorithmic Applications