HEXAGONbeta

Exact diameter of the symmetric group with LX generators

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.GR — Group Theory

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

Version 1 / Nov 03, 2026 / CC BY 4.0

Abstract

We prove an exact formula for the diameter of the directed Cayley graph for the symmetric group SnS_n with generators LL (left cyclic shift) and XX (exchange of the first two elements). For every n≥5n \geq 5, we show that the diameter equals (3n2−8n+12)/4(3n^2-8n+12)/4 for even nn and (3n2−8n+9)/4(3n^2-8n+9)/4 for odd nn. This resolves a longstanding question first proposed in the 1960's and refined in more recent work. The proof is AI-assisted and is based on a variety of combinatorial arguments. We also describe the agentic system we developed that led to this proof and looks highly promising for attacking other questions of this type. An accompanying Lean 4 formalization rigorously verifies the result.

Provenance statement

Section 1 of the paper is mostly human-written, while the subsequent text and figures, including the proof, are AI-generated with minor human edits. The proof was obtained by our agentic system with relatively minor human intervention that amounted mostly to workflow orchestration. We mainly used GPT-6 Astra (with reasoning level from Medium to Ultra) within the agentic system as well as within OpenAI Codex. We also used Opus 5.5 for minor checks and editing

Formalizations

Tools used

OpenAI
Codex
Anthropic
Claude Opus

References

  1. https://doi.org/10.1007/BF01073731).DOI
  2. Chervov, A.; Fedoriaka, D.; Konstantinova, E.; others. CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version). 2025. Version 2, 1 April 2026. Section 4.1, Conjecture 11arXiv
  3. Babai, L.; Seress, Á. On the diameter of Cayley graphs of the symmetric group. Journal of Combinatorial Theory, Series A, vol. 49, no. 1, pp. 175–179. 1988DOI
  4. Babai, L.; Seress, Á. On the diameter of permutation groups. European Journal of Combinatorics, vol. 13, no. 4, pp. 231–243. 1992DOI
  5. Babai, L.; Beals, R.; Seress, Á. On the diameter of the symmetric group: polynomial bounds. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 1108–1112. 2004
  6. Breuillard, E.; Green, B.; Tao, T. Approximate subgroups of linear groups. Geometric and Functional Analysis, vol. 21, no. 4, pp. 774–819. 2011DOI
  7. Helfgott, H. A.; Seress, Á. On the diameter of permutation groups. Annals of Mathematics, vol. 179, no. 2, pp. 611–658. 2014DOI
  8. Chervov, A.; Levkovich-Maslyuk, F.; Smolensky, A.; others. CayleyPy-4: AI-Holography. Towards analogs of holographic string dualities for AI tasks. 2026arXiv
  9. Glukhov, M. M.; Zubov, A. Yu. On the lengths of symmetric and alternating permutation groups in various generating systems (a survey). Matematicheskie Voprosy Kibernetiki, vol. 8, pp. 5–32. 1999. In Russianlink
  10. Pogorelov, B. A. On a problem of V. M. Glushkov. Kibernetika, no. 5, pp. 141–143. 1973. In Russian. English translation: A problem of V. M. Glushkov, Cybernetics 9 (1973), 895–899, doi:10.1007/BF01069732 (https://doi.org/10.1007/BF01069732). Historical results and this bibliographic record are also given in \cite[pp. 20–21 and reference 48]glukhovzubov1999link
Show all 25 referencesShow fewer references
  1. Zubov, A. Yu. On the diameter of the group SNS_N with respect to a system of generators consisting of a complete cycle and a transposition. Trudy po Diskretnoi Matematike, vol. 2, pp. 112–150. 1998. In Russianlink
  2. https://doi.org/10.1007/s10958-010-9887-z).DOI
  3. https://doi.org/10.17223/20710410/31/2). https://www.mathnet.ru/eng/pdm540.DOI
  4. D. desJardins; contributors. A039745: Diameter of symmetric group SnS_n when generated by (1,2)(1,2) and (1,2,3,…,n)(1,2,3,\ldots,n). Accessed 29 October 2026. The On-Line Encyclopedia of Integer Sequenceslink
  5. K. Ryde; contributors. A378881: Irregular triangle listing permutations of {1,…,m}\{1,\ldots,m\} which are at maximum distance from the identity permutation under steps rotate left (L) or exchange first two elements (E). 2024. Accessed 29 October 2026. The On-Line Encyclopedia of Integer Sequenceslink
  6. Chervov, A.; Soibelman, A.; Lytkin, S.; others. CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs. 2025. Version 3, 15 May 2026arXiv
  7. RnR_n with LE , https://doi.org/10.1142/S1793830920500330). https://bpb-us-e2.wpmucdn.com/sites.utdallas.edu/dist/f/1052/files/2023/03/LE.pdf.DOI
  8. Williams, A. Hamiltonicity of the Cayley digraph on the symmetric group generated by σ=(1 2 ⋯ n)\sigma=(1\ 2\ \cdots\ n) and τ=(1 2)\tau=(1\ 2). 2013. Version 3, 6 July 2017arXiv
  9. https://doi.org/10.1145/3359589).DOI
  10. Adin, R. M.; Alon, N.; Roichman, Y. Circular sorting. 2025. Version 2, 6 August 2025arXiv
  11. https://doi.org/10.1111/j.2517-6161.1977.tb01624.x).DOI
  12. Andrea Guerrieri. In preparation.
  13. Uskov, S.; Chervov, A.; Levkovich-Maslyuk, F.; Litvak, I.; Smolensky, A.; Soibelman, A. Exact directed L/X diameter in Lean 4. 2026. Lean 4 formalization, version v1.0.0, commit \texttt9e04062. https://github.com/snow-ghost/glushkov-lx-lean/releases/tag/v1.0.0link
  14. https://doi.org/10.1007/978-3-030-79876-5_37).DOI
  15. https://doi.org/10.1145/3372885.3373824).DOI

Version history

  1. v1Submitted by Sergei UskovInitial depositCurrentNov 02, 2026