PreprintarXiv licencearXiv
Genlex Gray codes for Sn with the fewest operations: classification and symmetry
Abstract
A Gray code for Sn is \emph{genlex} when words sharing a suffix are consecutive. We determine the genlex Gray codes for Sn that use the fewest possible operations: Zaks' recursion generalises to a superfactorial family of such codes, and no code outside this family attains the minimum. Every code in the family closes into a cycle, and the cycle is invariant under a group of left translations, cyclic of order n or dihedral of order 2n according to an explicit criterion on the operations. In the pancake graph the family reduces to a single member, the classical Zaks order; with respect to the standard parabolic chain of W(An−1), that order attains one extreme of total Coxeter length.
Related
- Classification of binary, ternary and quaternary Hermitian LCD codes
- A machine-checked proof of the Dong-Yang classification of optimal (n,4) binary codes for BSCs
- Neural Ideals and Neural Codes: An Algebraic Framework for Neural Network Classification and Feature Interpretation
- Finite Classification of Transversal Diagonal Gates Beyond Stabilizer Codes
- Nonlinear Curvature-Free Periodic Folding in Origami via Symmetry Classification of Linear Modes
BibTeX
@misc{sharvit2026genlex,
title = {{Genlex Gray codes for $S_n$ with the fewest operations: classification and symmetry}},
author = {Yehonathan Sharvit},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13214},
eprint = {2609.13214},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13214},
}
RIS
TY - UNPB
TI - Genlex Gray codes for S_n with the fewest operations: classification and symmetry
AU - Yehonathan Sharvit
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.13214
UR - https://arxiv.org/abs/2609.13214
AB - A Gray code for S_n is \emph{genlex} when words sharing a suffix are consecutive. We determine the genlex Gray codes for S_n that use the fewest possible operations: Zaks' recursion generalises to a superfactorial family of such codes, and no code outside this family attains the minimum. Every code in the family closes into a cycle, and the cycle is invariant under a group of left translations, cyclic of order n or dihedral of order 2n according to an explicit criterion on the operations. In the pancake graph the family reduces to a single member, the classical Zaks order; with respect to the standard parabolic chain of W(A_n−1), that order attains one extreme of total Coxeter length.
ER -