For a permutation pi∈ S_n, let d_T(pi,iota) be the minimum number of transpositions whose product sends pi to the identity permutation iota. Define the transposition diameter by TD(n)=max_pi∈ S_nd_T(pi,iota). Determine the exact value of TD(16). The cited preprint claims that TD(16)=9.

Transposition diameter problem

The problem asks for the exact transposition diameter $TD(n)$ , the largest minimum number of transpositions needed to sort a permutation. The latest claim concerns the previously unresolved value at $n=16$ .

Known results

Elias and Hartman disproved the conjectural upper bound $TD(n)\le (n+1)/2$ by establishing $TD(n)\ge (n+1)/2+1$ .
Lu and Yang proved the computational lower bound $TD(n)\ge \frac{17}{33}n+\frac{1}{33}$ and reported a super-bad permutation in $S_{10}$ .
Before the latest claim, the exact value was unknown, with $9\le TD(16)\le 10$ .

September 2026 claimed determination

Luiz A. G. Silva, Luis A. B. Kowada, Noraí R. Rocco, and Maria E. M. T. Walter claim that $TD(16)=9$ , closing the remaining unresolved case among $n\le 17$ . The claim appears in the preprint Twisted Bracelets for Sorting by Transpositions: the Transposition Diameter of $S_{16}$ , but no independent corroboration was found.

Current status (as of September 2026): $TD(16)=9$ is claimed by a preprint, while the exhaustive component remains independently unchecked; no other cases are reported as newly unsettled.

Transposition diameter problem

Primary source

Additional references

Progress summary

Solutions 0