Optimal single-track Gray codes

A binary Gray code lists distinct words so each step flips one bit. In a single-track Gray code, each bit position reads the same cyclic pattern with a different shift. How long can such a code be for a given word length?

Why it matters and what counts as progress

Why it matters: A long single-track code gives many distinct positions while using the same repeating pattern for each track.

What counts as progress: Construct a code of proved period or establish a matching upper bound. For prime lengths, prove the needed necklace ordering or find a different construction.

How the problem developed

  1. 17 Oct 2026 · AI-assisted result [1]

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

AI contribution

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.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Optimal single-track Gray codes from Gray-ordered necklaces
  2. Single-track Gray code artifacts
Publication history