Twisted Bracelets for Sorting by Transpositions: the Transposition Diameter of S16
Abstract
Sorting By Transpositions (SBT) seeks the minimum number of transpositions required to sort a permutation π on n symbols into the identity ι. Let N=n+1. A cyclic-target pair (ω,β) consists of an even permutation ω and an N-cycle β for which ρ=ωβ is an N-cycle. An SBT instance is the special case (ι̅π̅−1,π̅), where π̅ and ι̅ encode π and ι, and ι̅π̅−1π̅=ι̅. For a prescribed fixed-point-free cycle type, fixed-content words encode ω, with colors distinguishing cycles and ranks recording their orientations relative to β. A word is realizable exactly when ρ=ωβ is an N-cycle. Permutations of equal-part colors and shifts of rank origins form auxiliary symmetries that, together with word rotation and position reflection coupled to rank inversion, define a twisted dihedral action. Its orbits are twisted bracelets, and its realizable orbits correspond bijectively to extended-toric equivalence classes of cyclic-target pairs, where reflection is adjoined to classical toric equivalence. The correspondence yields a Burnside identity, and our method generates one encoding word for each such class. The transposition diameter TD(n) is the largest transposition distance in Sn. Combining fixed-point contraction and reductions of the ambient instance space based on cycle structure with exhaustive verification of every remaining twisted bracelet, we prove TD(16)=9, closing a twenty-five-year gap. This result also yields TD(19)=11 and, for every n≡1pmod3 with n≥16, TD(n)≤⌊(2n−2)/3⌋−1, improving the previous general upper bound by one for these n.
Related
- Conjugating Full Cycles by Adjacent Transpositions: Diameter and Sorting Time
- Type C transpositions and strong marked tableaux
- Finite Orders of Products of Two Class Transpositions Divide 840
- Restricted monodromy containing transpositions
- Time Emergence in Economics: Conceptual Transpositions from Quantum Systems
BibTeX
@misc{silva2026twisted,
title = {{Twisted Bracelets for Sorting by Transpositions: the Transposition Diameter of $S_16$}},
author = {Luiz A. G. Silva and Luis A. B. Kowada and Noraí R. Rocco and Maria E. M. T. Walter},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.17493},
eprint = {2609.17493},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17493},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Twisted Bracelets for Sorting by Transpositions: the Transposition Diameter of S_16
AU - Luiz A. G. Silva
AU - Luis A. B. Kowada
AU - Noraí R. Rocco
AU - Maria E. M. T. Walter
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2609.17493
UR - https://arxiv.org/abs/2609.17493
AB - Sorting By Transpositions (SBT) seeks the minimum number of transpositions required to sort a permutation π on n symbols into the identity ι. Let N=n+1. A cyclic-target pair (ω,β) consists of an even permutation ω and an N-cycle β for which ρ=ωβ is an N-cycle. An SBT instance is the special case (ι̅π̅^−1,π̅), where π̅ and ι̅ encode π and ι, and ι̅π̅^−1π̅=ι̅. For a prescribed fixed-point-free cycle type, fixed-content words encode ω, with colors distinguishing cycles and ranks recording their orientations relative to β. A word is realizable exactly when ρ=ωβ is an N-cycle. Permutations of equal-part colors and shifts of rank origins form auxiliary symmetries that, together with word rotation and position reflection coupled to rank inversion, define a twisted dihedral action. Its orbits are twisted bracelets, and its realizable orbits correspond bijectively to extended-toric equivalence classes of cyclic-target pairs, where reflection is adjoined to classical toric equivalence. The correspondence yields a Burnside identity, and our method generates one encoding word for each such class. The transposition diameter TD(n) is the largest transposition distance in S_n. Combining fixed-point contraction and reductions of the ambient instance space based on cycle structure with exhaustive verification of every remaining twisted bracelet, we prove TD(16)=9, closing a twenty-five-year gap. This result also yields TD(19)=11 and, for every n≡1pmod3 with n≥16, TD(n)≤⌊(2n−2)/3⌋−1, improving the previous general upper bound by one for these n.
ER -