Adin–Alon–Roichman affine-permutation conjecture for extremal circular sorting
Statement
Let denote the permutations of , let be the coset of a permutation under cyclic shifts, and let be the minimum number of transpositions needed to sort that coset. A permutation is affine if
for some and . Adin–Alon–Roichman affine-permutation conjecture. If , then is prime and is affine.
The conjecture refines the claim that the upper bound can be attained only for prime . The paper gives counterexamples to its affine conclusion, so the conjecture is refuted, although the composite-order part remains a separate open problem.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.