Directed diameter of the symmetric group
Arrange n distinct cards in a row. A move either shifts the first card to the end or swaps the first two cards. For each ordered pair of rows, count the fewest moves needed to reach the second row from the first. The directed diameter is the largest of those counts. What is its exact value for each ?
Why it matters and what counts as progress
Why it matters: This is an exact worst-case sorting problem with two restricted moves. The answer shows how much the direction of rotation and the parity of the number of cards affect the bound.
What counts as progress: A sharp upper bound must give a route within the claimed number of moves for every pair of rows. A matching lower bound must exhibit a pair that needs that many moves. Count each left shift and swap separately, including the shifts needed to reach the final orientation.
How the problem developed
- 1968 · Diameter question [1]
V. M. Glushkov Asked for the directed diameter when the only moves are a left cyclic shift and a swap of the first two positions.
A. Yu. Zubov Established that the diameter grows as to leading order.
- 1 Apr 2026 · Exact conjecture and computations [1]
Alexander Chervov and CayleyPy collaborators Stated separate quadratic formulas for even and odd n and reported exhaustive computations through .
Sergei Uskov and coauthors with GPT-6 Astra Proved the conjectured formula for every . The authors’ later Lean release reports checking both the diameter and bounded-routing statements.
AI contribution
Exact diameter of the symmetric group with LX generators
For every , the directed diameter of the symmetric group generated by a left cyclic shift and a swap of the first two positions is for even n and for odd n. Each move costs one. The diameter is the largest shortest-path length over all ordered pairs of permutations.
Sources
Publication history
Daily emails by default, only when there’s an update.