Papers for

digital system developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Optimal single-track gray codes found for all prime lengths up to 47

Optimal single-track Gray codes from Gray-ordered necklaces

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.

Sat 17 OctDiscrete MathematicsInformation Theory
The gist
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.
Open → 2610.24758v1