Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori
Abstract
A de Bruijn sequence packs all n-bit binary words into a cycle of length 2n. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when n = 2m + 1 is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into 2m−1 matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized 𝒪(1)-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.
Related
- Quadratic-size Random Permutations are Universal
- Existence of Reeb Chords from the Generation-Criteria
- Universal Feature Selection with Noisy Observations and Weak Symmetry Conditions
- Quantitative Analysis of Second-Harmonic Generation in Plasmonic Nanowires: Symmetry Breaking and a Topological Defect
- A Short Proof of Zhang's Conjecture on Stack-Sortable Permutations
BibTeX
@misc{gerlach2026shorthand,
title = {{Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori}},
author = {Tim Gerlach and Elizabeth Hartung and Pia Herkenrath and Joe Sawada and Aaron Williams},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27583},
eprint = {2609.27583},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27583},
}
RIS
TY - UNPB
TI - Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori
AU - Tim Gerlach
AU - Elizabeth Hartung
AU - Pia Herkenrath
AU - Joe Sawada
AU - Aaron Williams
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27583
UR - https://arxiv.org/abs/2609.27583
AB - A de Bruijn sequence packs all n-bit binary words into a cycle of length 2^n. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when n = 2m + 1 is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into 2^m−1 matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized 𝒪(1)-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.
ER -