Optimal single-track gray codes found for all prime lengths up to 47
Optimal single-track Gray codes from Gray-ordered necklaces
Discrete MathematicsInformation Theory
Summary
This work solves a long-standing open problem about special sequences called single-track Gray codes, which list binary strings so that each changes just a bit at a time in a repeating pattern. The authors link a previous mathematical conjecture about ordering sets called necklaces to the existence of longest possible such sequences for every prime number length. They verify this via computer checks up to length 47, giving optimal codes for all odd primes up to that point. This combines theoretical insight with computation to advance understanding of these code patterns.
What this means in practice
- •For circuit designers: Design cyclic binary sequences with minimal bit changes and rotational symmetry for low-power or error-minimizing circuits.
- •For digital system developers: Implement optimized sequences for testing and enumeration tasks that require structured binary patterns with specific symmetry properties.
A theory result. No direct application yet.
Authors
Chris Dzoba
Abstract
A single-track Gray code of length $n$ is a cyclic Gray code of $n$-bit words in which every column is a cyclic shift of the first. For prime $n$ the longest possible period is $2^n-2$. Whether it is attained for every prime has been open since Hiltgen, Paterson and Brandestini introduced these codes in 1996, and optimal codes were known for primes $n\le 19$. We show that a conjecture of Degni and Drisko (2007) on the reflected Gray code order of necklaces implies optimal single-track Gray codes for every prime. Their list of necklaces, conjecturally a Gray path for prime $n$, closes into a Hamilton cycle of the necklace graph after $(n-3)/2$ explicit Pósa rotations, and such a cycle lifts to an optimal code. This implication is formalized in Lean 4. Together with computation it gives optimal single-track Gray codes for every odd prime $n\le 47$: for $n\le 37$ explicit codes checked word by word by a program independent of the generator, and for $n=41$, $43$ and $47$ codes obtained from the implication after the Degni-Drisko property was verified at these lengths by two independently written programs.