On the 5-Permutation Invariant of Generalizable Hamiltonian Decompositions of Cayley Digraphs: An Erratum and New Structural Results for Knuth's "Claude's Cycles"

Read full text Summarise with VIRAT
Authors: Frederic David Blum
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Title On the 5-Permutation Invariant of Generalizable Hamiltonian Decompositions of Cayley Digraphs: An Erratum and New Structural Results for Knuth's "Claude's Cycles" Authors Frédéric David Blum (ORCID: 0009-0009-2487-2974) Description We present an independent computational verification of D. E. Knuth's paper "Claude's Cycles" (Stanford CS, February/March 2026), which describes how Claude Opus 4.6 discovered a construction for decomposing the Cayley digraph Cay(Z_m^3, {e_0, e_1, e_2}) into three directed Hamiltonian cycles for all odd m > 2. We confirm all numerical results (11,502 Hamiltonian cycles; 996 generalizable cycles; 4,554 decompositions; 760 generalizable decompositions) except for one error: Knuth writes "136 of the 760" on page 4, but the correct statement is "136 of the 996" — he conflated the count of generalizable decompositions (760) with that of individual generalizable cycles (996). The jki-invariant decompositions number 92, not 136. We discover two new structural results: The 5-Permutation Invariant (Theorem 1): Every generalizable Claude-like decomposition uses exactly 5 of the 6 elements of S_3 in its permutation assignment, with the identity always included. This is specific to generalizability — 43.2% of non-generalizable decompositions use all 6 permutations. The Mono-Freeze Exclusion Principle (Theorem 2): The only fiber-pair combinations that could employ all 6 permutations require all "frozen directions" (where both permutations in a fiber assign the same direction to a cycle) to align on a single coordinate. We prove that no generalizable decomposition exhibits such mono-directional freezing (0 out of 760), thus establishing the 5-permutation invariant as a necessary condition for generalizability. We further characterize the odd-even dichotomy: even-m decompositions require all 6 permutations (verified on 50 CP-SAT solutions for m=4), and no simple parametrization produces valid decompositions for both odd and even m simultaneously (exhaustive search over 10+ parametrization families). All code is included and independently reproducible. Keywords Hamiltonian decomposition, Cayley digraph, permutation invariant, generalizability, Claude's Cycles, Knuth, combinatorial group theory, graph theory License Creative Commons Attribution 4.0 International (CC BY 4.0) Related identifiers References: https://cs.stanford.edu/~knuth/papers/claude-cycles.pdf (Knuth's original paper) References: https://github.com/kim-em/KnuthClaudeLean/ (Lean formalization by Kim Morrison) Resource type Preprint Communities (Optional: Mathematics, Computer Science, Combinatorics)

Fields of Study & Subjects

Finite Group Theory Research Advanced Combinatorial Mathematics Advanced Graph Theory Research

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
21 March 2026
Language
EN