Twisted Bracelets for Sorting by Transpositions: the Transposition Diameter of $S_{16}$

Abstract

Sorting By Transpositions (SBT) seeks the minimum number of transpositions required to sort a permutation $\pi$ on $n$ symbols into the identity $\iota$. Let $N=n+1$. A cyclic-target pair $(\omega ,\beta )$ consists of an even permutation $\omega$ and an $N$-cycle $\beta$ for which $\rho =\omega \beta$ is an $N$-cycle. An SBT instance is the special case $(\bar{\iota }{\bar{\pi }}^{-1},\bar{\pi })$, where $\bar{\pi }$ and $\bar{\iota }$ encode $\pi$ and $\iota$, and $\bar{\iota }{\bar{\pi }}^{-1}\bar{\pi }=\bar{\iota }$. For a prescribed fixed-point-free cycle type, fixed-content words encode $\omega$, with colors distinguishing cycles and ranks recording their orientations relative to $\beta$. A word is realizable exactly when $\rho =\omega \beta$ 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. This correspondence yields exact orbit counts and directly generates one representative per realizable class. The transposition diameter $TD(n)$ is the largest transposition distance in $S_n$. Combining fixed-point contraction and structural reductions with exhaustive verification of the remaining twisted bracelets, we prove $TD(16)=9$, closing a twenty-five-year gap. This result also yields $TD(19)=11$ and, for every $n\equiv 1(\mathrm{mod}3)$ with $n\ge 16$, $TD(n)\le \lfloor (2n-2)/3\rfloor -1$, improving the previous general upper bound by one for these $n$.