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

Source 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 $β$ such that $ρ=ωβ$ is also an $N$-cycle. An SBT instance is the special case $(\barι {\barπ}^{-1},\barπ)$, where $\barπ$ and $\barι$ are $N$-cycles corresponding to $π$ and $ι$, respectively, and $\barι {\barπ}^{-1}\barπ=\barι$, so its target is $\barι$. For each prescribed fixed-point-free cycle type with specified cycle orientations relative to $β$, fixed-content words encode the corresponding permutations $ω$. Colors identify cycles and ranks record their orientations. A word is realizable when the associated product $ρ=ωβ$ is an $N$-cycle. Permuting equal-part colors and shifting rank origins give auxiliary symmetries. Together with word rotation and position reflection combined with rank inversion, they define a twisted dihedral action. Its orbits are twisted bracelets, and the realizable orbits are in bijection with extended-toric equivalence classes of cyclic-target pairs. Here extended-toric equivalence means Eriksson et al.'s toric equivalence with reflection adjoined. This correspondence yields exact orbit counts and direct generation of one representative per realizable extended-toric class. The transposition diameter $TD(n)$ is the largest transposition distance in $S_n$. Previously, $9\leq TD(16)\leq10$ was known, and $16$ was the only unresolved value for $n\leq17$. 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.