Directed L/XL/X 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 n≥5n \ge 5?

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

  1. 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.

  2. 1979 · Leading asymptotic term [2][3]

    A. Yu. Zubov Established that the diameter grows as 3n2/43n^{2}/4 to leading order.

  3. 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 n=15n = 15.

  4. 3 Nov 2026 · Exact diameter theorem [3][4]

    Sergei Uskov and coauthors with GPT-6 Astra Proved the conjectured formula for every n≥5n \ge 5. 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

Sergei Uskov, Alexander Chervov, Fedor Levkovich-Maslyuk, Ivan Litvak, Andrei Smolensky, Alexander Soibelman

For every n≥5n \ge 5, the directed diameter of the symmetric group SnS_{n} generated by a left cyclic shift and a swap of the first two positions is (3n2−8n+12)/4(3n^{2} - 8n + 12)/4 for even n and (3n2−8n+9)/4(3n^{2} - 8n + 9)/4 for odd n. Each move costs one. The diameter is the largest shortest-path length over all ordered pairs of permutations.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean 4)
Human understandingPartial
Paper date:

Sources

  1. CayleyPy Growth, Conjecture 11
  2. Glukhov and Zubov’s survey of permutation lengths
  3. Uskov and coauthors’ paper and AI disclosure
  4. Lean 4 release and verification results
Publication history