Groenland, Johnston, Radcliffe and Scott's conjecture for two-element shuffles

For integers knk\leq n, let Uk(n)U_k(n) be the minimum length of a sequence of independent lazy transpositions whose product maps the elements 1,,k1,\dots,k uniformly to the n(n1)(nk+1)n(n-1)\dots(n-k+1) possible ordered kk-tuples; such a sequence is called a (k,n)(k,n)-shuffle. Groenland, Johnston, Radcliffe and Scott's conjecture. For all n2n\geq 2,

U2(n)=2n3.U_2(n)=2n-3.

The general construction gives Uk(n)kn(k+12)U_k(n)\leq kn-\binom{k+1}{2}, and the cited work improves this bound for every k3k\geq3. The case k=2k=2 remains the conjectured sharp case, and proving it would establish that the displayed upper bound cannot be improved for two-element shuffles.

Sources & referencesView supporting material

Primary source

Barnabás Janzer, J. Robert Johnson and Imre Leader, “Partial shuffles by lazy swaps”, arXiv:2210.13286 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.