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 2n−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≤ 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≤ 47: for n≤ 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.
Related
- Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes
- Optimal Quantum ( r , δ )-Locally Repairable Codes From Matrix-Product Codes
- Computing with necklaces on elliptic curves
- A new class of optimal binary linear complementary pairs of codes
- Embedding Linear Codes into Optimal Self-Orthogonal Codes Based on Constraint-Preserving Genetic Algorithms
BibTeX
@misc{dzoba2026optimal,
title = {{Optimal single-track Gray codes from Gray-ordered necklaces}},
author = {Chris Dzoba},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24758},
eprint = {2610.24758},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24758},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal single-track Gray codes from Gray-ordered necklaces
AU - Chris Dzoba
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24758
UR - https://arxiv.org/abs/2610.24758
AB - 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≤ 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≤ 47: for n≤ 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.
ER -