Exact formula for U_t(n) lazy transpositions
Problem 3 · arXiv:2208.06629
Status partial medium confidence
Problem 3 asks whether U_t(n) = tn - C(t+1,2) holds for all t, where the upper bound is already established by sweeping/divide-and-conquer constructions and the t=n case is answered negatively by Theorem 2 of the source paper. A follow-up by Janzer, Johnson, and Leader (arXiv:2210.13286, October 2022) proves that U_2(n) = 2n-3, confirming the formula for t=2 and settling the corresponding conjecture of Groenland et al. Whether the formula holds for intermediate values of t remains open.
Cited literature (1)
-
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. The formula U_t(n) = tn - C(t+1,2) is confirmed for t=2 by Janzer et al. (arXiv:2210.13286); the case t=n is answered negatively in the source paper itself (Theorem 2). The general problem for intermediate t remains open. Confidence is medium because the Janzer et al. abstract was verified but the full paper was not read to confirm exact scope.
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