Claude's cycles: decomposing a 3D torus digraph into Hamiltonian cycles

The problem

The digraph has the $m^3$ vertices $ijk$ with $0 \le i, j, k < m$, and from each vertex an arc that increases $i$, $j$ or $k$ by 1 modulo $m$. The question, which arose in Donald Knuth's draft section on Hamiltonian cycles for The Art of Computer Programming, is whether its arcs can be split into three directed Hamiltonian cycles for every $m > 2$. For $m = 2$ it is impossible.

What AI did

Filip Stappers posed the problem to Claude Opus 4.6 and coached it through a series of explorations. On the 31st, Claude produced a construction that worked for every odd $m$ from 3 to 11; Stappers then tested it for every odd $m$ up to 101. Knuth described the episode in a note titled "Claude's Cycles" (28 February 2026, revised 14 April 2026), and counted exactly 760 "Claude-like" decompositions that work for all odd $m$.

How it was checked

Knuth wrote the rigorous proof for all odd $m$ himself, and Kim Morrison formalized it in Lean.

Limitations

The record covers the odd case. For even $m$, Claude made only partial progress; Ho Boon Suan's code written with gpt-5.3-codex covers even $m \ge 8$ (tested up to 2000), and GPT-5.4 Pro then wrote a 14-page proof that Knuth calls "apparently flawless" but that has not been independently verified. This is a research problem from Knuth's book, not a long-standing famous conjecture.

∎