OFFSET
2,4
COMMENTS
Arrange n distinct labels 0,..,n-1 clockwise around a circle. A swap exchanges the labels on two positions of the circle. Then a(n) is the maximum, over all starting arrangements, of the minimum number of swaps required to reach the clockwise order 0,1,..,n-1 (up to rotation).
In terms of permutations of Z_n (the integers mod n), we have
a(n) = max_{pi in S(Z_n)} (n - max_{k in Z_n} cyc(x -> pi(x + k))), where cyc(sigma) is the number of cycles of the permutation sigma.
In terms of the Cayley graph of S_n generated by all transpositions, a(n) is the maximum distance to the subgroup generated by the n-cycle (1 2 .. n).
Introduced in "Circular sorting" (Adin, Alon, Roichman, 2025) and further studied in "Circular sorting, strong complete mappings and wreath product constructions" (Bastide, Bishnoi, Groenland, Gijswijt, Joshi, 2025).
The upper bound a(n)<=n-2 is known to hold with equality for n prime. Also, a(3n)=3n-3 for n prime. Other known values are: a(25)=22, a(27)=24.
A permutation pi in S(Z_n) achieving the bound n-2 (optimal permutation) is necessarily a strong complete mapping of Z_n (see A071607).
For primes p<=19 all optimal permutations are affine. For certain primes p>=23, optimal permutations exist that are quadratic orthomorphisms (see A390047).
For all composite n<=21 we have a(n)=n-3. It is unknown if this is true for all composite n, the smallest open case being n=22.
LINKS
Ron M. Adin, Noga Alon, and Yuval Roichman, Circular sorting, arXiv:2502.14398 [math.CO], 2025.
Paul Bastide, Anurag Bishnoi, Carla Groenland, Dion Gijswijt, and Rohinee Joshi, Circular sorting, strong complete mappings and wreath product constructions, arXiv:2510.18529 [math.CO], 2025.
FORMULA
a(n) = max_{pi in S_n} min_{k = 0..n-1} cyc(x -> pi(x + k mod n)), where cyc(sigma) is the number of cycles of permutation sigma.
EXAMPLE
For n = 6, consider the clockwise order 0,3,5,1,2,4.
Swapping 0<->5, then 3<->4, then 4<->5 yields 4,5,0,1,2,3, a rotation of 0,1,2,3,4,5.
Hence the labels are in clockwise order after 3 swaps.
The same cannot be achieved with only 2 swaps, so a(6) >= 3.
Every other starting arrangement can be sorted in 3 or fewer swaps, so a(6) = 3.
PROG
(Python)
from itertools import permutations
def a(n):
def cyc(f):
seen=[False]*n; c=0
for x in range(n):
if not seen[x]:
c+=1; y=x
while not seen[y]: seen[y]=True; y=f[y]
return c
best=0
for pi in permutations(range(n)):
mx=0
for k in range(n):
f = [pi[(x+k)%n] for x in range(n)]
mx=max(mx, cyc(f))
best=max(best, n-mx)
return best
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Dion Gijswijt, Oct 25 2025
STATUS
approved
