Optimal single-track Gray codes from Gray-ordered necklaces

Chris Dzoba

For prime word length n≥7n \ge 7, if the Degni–Drisko order gives a Gray path through the nonconstant binary necklaces, then explicit rotations of that path close a Hamiltonian cycle. The resulting single-track Gray code has optimal period 2n−22^{n} - 2.

What was already known

The optimal-period upper bound follows from the work of Hiltgen, Paterson and Brandestini. Degni and Drisko proposed the necklace ordering. Optimal prime-length examples were documented through 19.

AI involvement AI-led

Chris Dzoba credits Claude with finding closing pivots by search, producing proofs, running verifiers and formalizing the implication. Codex contributed independent finite checkers.

Importance Notable

The construction turns the proposed ordering into a full cycle and an optimal code for prime lengths where the assumption holds.

Technical verification Formal (Lean)

Dzoba reports that Lean 4’s stgc_of_DD verifies the conditional implication with standard axioms and adjacency of consecutive nonconstant necklaces as hypothesis. Finite tests have separate checking scope.

Formal checking

Dzoba reports that Lean 4’s stgc_of_DD verifies the conditional implication with standard axioms and adjacency of consecutive nonconstant necklaces as hypothesis. Finite tests have separate checking scope.

Checker
Chris Dzoba, reporting Lean checks
Scope
Dzoba reports that Lean 4’s stgc_of_DD verifies the conditional implication with standard axioms and adjacency of consecutive nonconstant necklaces as hypothesis. Finite tests have separate checking scope.
Basis
Reported by the linked checker

Human understanding Few

The source attributes the closing pivots and proof to Claude. A human explanation of the model’s argument is undocumented.

Correction and publication history