Characterisation of maximum circular sorting permutations

Conjecture 3.6 · arXiv:2502.14398

arXiv Conjecture medium confidence— first stated 2025-08-06

Authors: Ron M. Adin, Noga Alon, Yuval Roichman

Status disproved high confidence

Conjecture 3.6, which asserts that any permutation π satisfying cyc(σ)=2 for every σ∈πC_n must have n prime and be of the affine form π_{n,a}, is disproved by Bastide, Bishnoi, Groenland, Gijswijt, and Joshi (arXiv:2510.18529). The smallest counterexample occurs at n=23: a specific non-affine permutation satisfies t([π])=21=n−2 yet is not of the form π_{n,a}; all counterexamples found have the structure of quadratic orthomorphisms. The implied Conjecture 3.4 (t(n)=n−2 iff n is prime) remains open but is further supported.

Cited literature (1)

counterexample Circular sorting, strong complete mappings and wreath product constructions (2025)

Paul Bastide, Anurag Bishnoi, Carla Groenland, Dion Gijswijt, Rohinee Joshi · arXiv preprint · arXiv:2510.18529

Disproves Conjecture 3.6 by exhibiting non-affine quadratic orthomorphisms achieving t([π])=n−2 for prime n, with the smallest counterexample an explicit permutation of length n=23.

Reviewer notes. Conjecture 3.6 is a structural strengthening of Conjecture 3.4; its disproof does not immediately disprove 3.4. arXiv:2510.18529 also provides evidence for Conjecture 3.4 (t(n)≤n−3 when n is composite) and proves a tight upper bound for n=25 via exhaustive search using strong complete mappings.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. If $n>2$ and $\pi\in S_{n}$ satisfies [the condition that $\operatorname{cyc}(\sigma)=2$ for every $\sigma\in\pi C_{n}$], then $n$ is prime and [\pi = \pi_{n,a}$] for some $a\in{\mathbb{Z}}_{n}^{\times}$.

Context

Conjecture 3.6 is a structural strengthening of Conjecture 3.4: it characterises the permutations $\pi$ achieving $t([\pi])=n-2$ as exactly the permutations $\pi_{n,a}$ (defined via multiplication by $a$ in $\mathbb{Z}_n$) when $n$ is prime. The implication 'Conjecture 3.6 $\Rightarrow$ Conjecture 3.4' holds, and both have been verified for $n\leq 11$.

Notes. PDF source — the hypothesis clause of the statement is garbled (a condition on $\pi$ is missing from the extracted text). The statement has been reconstructed from context.

Source paper

Circular sorting
Ron M. Adin, Noga Alon, Yuval Roichman · 2025-08-06
https://arxiv.org/abs/2502.14398