Exact formula for U_t(n) lazy transpositions
Problem 3 · arXiv:2208.06629
Status disproved high confidence
The proposed identity is false: the source paper's bound for full shuffles already gives strict counterexamples, and these also yield counterexamples with t=n-1<n.
Cited literature (2)
-
The proposed identity is false: the source paper's bound for full shuffles already gives strict counterexamples, and these also yield counterexamples with t=n-1<n.
-
Proves U_2(n) = 2n-3, confirming the t=2 case of Problem 3 (since 2n-3 = 2n - C(3,2)) and explicitly settling a conjecture of Groenland, Johnston, Radcliffe, and Scott.
Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: This settles the yes/no question, not the exact values of U_t(n) for t>=3.
Context
This generalises Problem 1 to the setting of shuffling $t$ distinguishable counters across $n$ positions using the fewest lazy transpositions. The upper bound $U_t(n)\leq tn-\binom{t+1}{2}$ is achieved by existing sweeping/divide-and-conquer constructions. When $t=n$ the problem reduces to Problem 1, which Theorem 2 answers negatively; the paper asks whether the trivial bound is tight for other values of $t$.
Notes. PDF source — binomial-coefficient notation garbled in raw extraction; LaTeX reconstructed from context. The paper also proves (Theorem 4) that for $3\leq t\leq n$ the bound can likewise be beaten by a constant factor, so the answer is negative for all $t\geq 3$.
Source paper
Perfect shuffling with fewer lazy transpositions
Carla Groenland, Tom Johnston, Jamie Radcliffe, Alex Scott · 2022-08-13
https://arxiv.org/abs/2208.06629
PDF source