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.

What was already known

Glushkov posed the diameter problem in 1968. Earlier work established quadratic bounds and the leading term 3n2/43n^{2}/4. Chervov and collaborators conjectured the exact even and odd formulas and reported exhaustive computations through n=15n = 15.

AI involvement AI-led

The authors report that their agent workflow produced the proof chiefly with GPT-6 Astra, including through OpenAI Codex. The authors mainly coordinated the workflow and made minor edits. They used Claude Opus 5.5 for limited checking and editing.

Importance Notable

The theorem resolves the exact diameter conjecture for these two generators. It determines both the worst-case number of moves and its dependence on parity, beyond the previously known leading term.

Technical verification Formal (Lean 4)

The pinned Lean 4 release reports a successful build, an axiom audit, and Comparator checks against a separately stated all-pairs diameter theorem and bounded-routing theorem. The formal statements use literal unit-cost L and X moves and cover every n≥5n \ge 5. The release reports only standard Lean axioms.

Formal checking

The pinned Lean 4 release reports a successful build, an axiom audit, and Comparator checks against a separately stated all-pairs diameter theorem and bounded-routing theorem. The formal statements use literal unit-cost L and X moves and cover every n≥5n \ge 5. The release reports only standard Lean axioms.

Checker
Lean 4 kernel and Comparator, reported by the authors
Scope
Exact all-pairs directed diameter and sharp route bound for n≥5n \ge 5 with literal L and X moves
Basis
Reported by the linked checker

Human understanding Partial

The authors explain the move model and their workflow. They report understanding some parts of the work and say they have yet to understand the proof in detail. The paper’s detailed proof exposition is model-generated.

Correction and publication history

2026-11-07 · publication

Newly source-reviewed proof of the exact directed L/XL/X diameter, with documented central AI work and a checked Lean release.

Read this published revision