HEXAGONbeta

The exact diameter of the symmetric group 𝑆𝑛 with LRX 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 β†—, Dia Taha β†—

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

We consider the undirected Cayley graph of the symmetric group 𝑆𝑛 with respect to the cyclic shift 𝐿, its inverse 𝑅, and the transposition 𝑋 of the first two positions. We prove that its diameter is given by 𝑛(𝑛 βˆ’ 1)/2 for every 𝑛 β‰₯ 4, thus settling a conjecture open since at least 2011. This is done by separately establishing sharp upper and lower bounds, invoking a variety of combinatorial and group-theoretic arguments which leave a finite set of special cases that are verified in the accompanying C++ code. We also provide a Lean formalization of the results.

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. 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
  2. Babai, L.; Seress, Á. On the diameter of permutation groups. European Journal of Combinatorics, vol. 13, no. 4, pp. 231–243. 1992DOI
  3. 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
  4. Breuillard, E.; Green, B.; Tao, T. Approximate subgroups of linear groups. Geometric and Functional Analysis, vol. 21, no. 4, pp. 774–819. 2011DOI
  5. Helfgott, H. A.; Seress, Á. On the diameter of permutation groups. Annals of Mathematics, vol. 179, no. 2, pp. 611–658. 2014DOI
  6. Chervov, A.; Fedoriaka, D.; Konstantinova, E.; Naumov, A.; others. CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version). 2026. First submitted in 2025; version 2, 1 April 2026; Conjecture 11. arXiv:2509.19162v2 [math.CO]link
  7. Alexander Chervov; Kirill Khoruzhii; Nikita Bukhal; Jalal Naghiyev; Vladislav Zamkovoy; Ivan Koltsov; Lyudmila Cheldieva; Arsenii Sychev; Arsenii Lenin; Mark Obozov; Egor Urvanov; Alexey M. Romanov. A Machine Learning Approach That Beats Rubik's Cubes. Advances in Neural Information Processing Systems, vol. 38, pp. 191182–191204. 2025DOI
  8. A. Chervov; F. Levkovich-Maslyuk; A. Smolensky; F. Khafizov; I. Kiselev; D. Melnikov; I. Koltsov; S. Kudashev; D. Shiltsov; M. Obozov; S. Krymskii; V. Kirova; E. V. Konstantinova; A. Soibelman; S. Galkin; L. Grunwald; A. Kotov; A. Alexandrov; S. Lytkin; D. Fedoriaka; A. Chevychelov; Z. Kogan; A. Natyrova; L. Cheldieva; O. Nikitina; S. Fironov; A. Vakhrushev; A. Lukyanenko; V. Ilin; D. Gorodkov; N. Bogachev; I. Gaiur; M. Zaitsev; F. Petrov; L. Petrov; T. Gaintseva; A. Gavrilova; M. N. Smirnov; N. Kalinin; A. Khan; K. Jung; H. Mousset; H. Isambert; O. Debeaupuis. CayleyPy-4: AI-Holography. Towards Analogs of Holographic String Dualities for AI Tasks. 2026arXiv
  9. Michael R. Douglas; Kit Fraser-Taliente. Diffusion Models for Cayley Graphs. 2025arXiv
  10. He, Yang-Hui; Yau, Shing-Tung. Graph Laplacians, Riemannian Manifolds and their Machine-Learning. Mathematics, Computation and Geometry of Data, vol. 2, no. 1, pp. 1–48. 2022arXivDOI
Show all 34 referencesShow fewer references
  1. Stephen McAleer; Forest Agostinelli; Alexander Shmakov; Pierre Baldi. Solving the Rubik's Cube with Approximate Policy Iteration. International Conference on Learning Representations. 2019
  2. Forest Agostinelli; Stephen McAleer; Alexander Shmakov; Pierre Baldi. Solving the Rubik's Cube with Deep Reinforcement Learning and Search. Nature Machine Intelligence, vol. 1, no. 8, pp. 356–363. 2019DOI
  3. Kyo Takano. Self-Supervision is All You Need for Solving Rubik's Cube. Transactions on Machine Learning Research. 2023arXiv
  4. Colin G. Johnson. Solving the Rubik's Cube with Learned Guidance Functions. 2018 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 2082–2089. 2018DOI
  5. Rashid Barket; Enrico Grimaldi; Yacoub Hendi; Edward Hirst; Adam Onus; Harmeet Singh. Learning the Graphical Nature of Symmetries. 2026arXiv
  6. OEIS Foundation Inc. A186783: Diameter of the symmetric group SnS_n when generated by the transposition (1,2)(1,2) and both left and right rotations by (1,2,…,n)(1,2,\ldots,n). 2026. Entry created by Tony Bartoletti in 2011; accessed 4 November 2026. The On-Line Encyclopedia of Integer Sequenceslink
  7. Chervov, A.; Obozov, M.; Soibelman, A.; Lytkin, S.; others. CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs. 2026. First submitted in 2025; version 3, 15 May 2026; Sections 4.1–4.3. arXiv:2502.18663v3 [cs.LG]link
  8. Antiufeev, Grigorii. A Lower Bound for the Diameter of Cayley Graph of the Symmetric Group SnS_n Generated by (12)(12), (12…n)(12\dots n), (1n…2)(1n\dots2). 2026. Version 3, 4 June 2026; Theorem 2. arXiv:2601.08715v3 [math.CO]link
  9. Glushkov, V. M. Completeness of a system of operations in digital computers. Cybernetics, vol. 4, no. 2, pp. 1–4. 1968. Translated from Kibernetika 4(2) (1968), 1–5DOI
  10. Pogorelov, B. A. A problem of V. M. Glushkov. Cybernetics, vol. 9, pp. 895–899. 1973. Translated from Kibernetika (1973), no. 5, 141–143DOI
  11. 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
  12. OEIS Foundation Inc. A039745: Diameter of symmetric group SnS_n when generated by (1,2)(1,2) and (1,2,3,…,n)(1,2,3,\ldots,n). 2026. Entry by D. desJardins; accessed 5 November 2026. The On-Line Encyclopedia of Integer Sequenceslink
  13. Uskov, Sergei; Chervov, Alexander; Levkovich-Maslyuk, Fedor; Litvak, Ivan; Smolensky, Andrei; Soibelman, Alexander. Exact diameter of the symmetric group with LX generators. 2026. Version 1, 3 November 2026. Hexagon preprint hexagon:2611.00039v1hexagon
  14. BjΓΆrner, Anders; Brenti, Francesco. Combinatorics of Coxeter Groups. Springer, vol. 231. 2005. Proposition 1.4.7, Corollary 1.4.8, Proposition 1.5.2, Theorems 2.1.5 and 2.2.2, Corollary 2.2.5, Propositions 2.2.7 and 2.3.1DOI
  15. BjΓΆrner, Anders; Brenti, Francesco. Affine Permutations of Type AA. The Electronic Journal of Combinatorics, vol. 3, no. 2, pp. R18. 1996. Propositions 3.1 and 3.3, pp. 6–8DOI
  16. Diaconis, Persi; Graham, R. L. Spearman's Footrule as a Measure of Disarray. Journal of the Royal Statistical Society. Series B (Methodological), vol. 39, no. 2, pp. 262–268. 1977. Theorem 2, pp. 264–266DOI
  17. Petersen, T. Kyle; Tenner, Bridget Eileen. The Depth of a Permutation. Journal of Combinatorics, vol. 6, no. 1–2, pp. 145–178. 2015. Theorem 1.1, Remark 1.2, Proposition 3.2; arXiv:1202.4765v3, 19 August 2014arXivDOI
  18. Berman, Yosef; Tenner, Bridget Eileen. Pattern-Functions, Statistics, and Shallow Permutations. The Electronic Journal of Combinatorics, vol. 29, no. 4, pp. P4.43. 2022. Definition 2, Corollaries 25 and 31; journal numberingDOI
  19. Nathanson, Melvyn B. The Muirhead–Rado Inequality, 1: Vector Majorization and the Permutohedron. 2024. Version 3, 5 May 2024; Section 3 and Theorem 7. arXiv:2109.01746v3 [math.CO]link
  20. Harary, Frank; Kabell, Jerald A. Counting Balanced Signed Graphs Using Marked Graphs. Proceedings of the Edinburgh Mathematical Society, vol. 24, no. 2, pp. 99–104. 1981. Structure Theorem for Balance, Section 1, p. 99DOI
  21. Easley, David; Kleinberg, Jon. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press. 2010. Section 5.2, pp. 123–126: Balance Theorem and prooflink
  22. Andrea Guerrieri. In preparation.
  23. 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/lrx-lean/releases/tag/v1.0.0link
  24. Schwertman, Neil C.; Gilks, A. J.; Cameron, J. A Simple Noncalculus Proof That the Median Minimizes the Sum of the Absolute Deviations. The American Statistician, vol. 44, no. 1, pp. 38–39. 1990DOI

Version history

  1. v1 Β· 43 pagesSubmitted by Sergei UskovInitial depositCurrentNov 11, 2026