Exact diameter of the symmetric group with LRX generators
Let be the undirected Cayley graph of generated by the cyclic shift , its inverse and the transposition of the first two positions: a row of cards, where one move sends the first card to the end, brings the last card to the front, or swaps the first two. What is the diameter of ? The values for are OEIS A186783 (2011), where it is conjectured that the diameter is for all . Before this work Chervov et al. had proved , and Antiufeev (arXiv, January 2026) had given a proof of the sharp lower bound .
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Computation
- Field
- Cayley graphs, permutation groups, diameter
- Posed by
- OEIS A186783 (Tony Bartoletti, 2011); the formula n(n-1)/2 was conjectured there by A. Wesolowski (2013) and P. W. Alexandersson (2020)
- Year posed
- 2011
- Years open
- 15y
- Solved
- 2026-11-10
- Model
- GPT-6 Astra (agentic system, OpenAI Codex); Claude Opus 5.5
- Vendor
- OpenAI; Anthropic
- Collaborators
- Sergei Uskov, Alexander Chervov, Fedor Levkovich-Maslyuk, Ivan Litvak, Andrei Smolensky, Alexander Soibelman, Dia Taha
- Verification
- Lean-checked, statement unaudited
- Publication
- Preprint
- Significance
- 12 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: for every the diameter of is , attained between the identity and . The sharp lower bound had been obtained earlier by Antiufeev and is reproved here independently; the matching upper bound, a word of at most letters between any two arrangements, is the new part. The paper's proof reduces the upper bound to a finite set of cases ( and finitely many parameters) cleared by a C++17 program printed in Appendix E. The Lean 4 formalization proves both bounds, with its finite certificates checked by the Lean kernel. The Lean theorems do not name or classify the extremal permutations, and uniqueness of the farthest element, also conjectured in OEIS, is not claimed. The authors note that A. Guerrieri independently obtained a proof (in preparation).
What the AI did
From the Hexagon 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". Section 1.4 of the paper adds that the key steps of the proof and the Lean formalization were obtained by the agentic system, developed mainly by S. Uskov. Hexagon labels the work "A mix of human-written and AI-generated text" and "Human understanding: some parts".
Verification
Lean-checked on this site's ladder, not Lean-verified. Checked here on 19 November 2026: the Hexagon paper 2611.00333v1 and its AI statement. Palomar entry PALOMAR-2026-11-10-000010 v1 read: source snow-ghost/lrx-lean at commit 9cffbfb, Lean v4.35.0, Comparator theorems PalomarLRX.boundedRouting and PalomarLRX.exactDiameter, permitted axioms propext, Quot.sound and Classical.choice, kernel replay by Palomar. Challenge.lean (54 lines, Mathlib imports only) was read in full: states are Equiv.Perm (Fin n), the generators are finRotate n, its inverse and swap 0 1, the graph is Mathlib's SimpleGraph.mulCayley on that set, and exactDiameter says its diam is n(n-1)/2 for all n >= 4. That is Theorem 1.1 without the named extremal element. A grep of all 1,146 Lean files at that commit found no sorry outside the two Challenge placeholders and no axiom declarations, native_decide, unsafe, implemented_by or extern. The repository's Actions build and Palomar preflight on that commit both succeeded. Not rebuilt here. A breadth-first search written here gave diameters 6, 10, 15, 21, 28, 36, 45 for n = 4 to 10, each time with the unique farthest vertex. The statement audit is this site's alone; no independent expert has reviewed the proof.
Sources
- PaperAntiufeev, A lower bound for the diameter of the Cayley graph of S_n generated by (12), (12...n), (1n...2)Chervov et al., CayleyPy RL: pathfinding and reinforcement learning on Cayley graphs (earlier bounds)
- Lean proofLean 4 formalization at the commit Palomar verified (snow-ghost/lrx-lean, 9cffbfb)GitHub Actions build and axiom audit on that commit
- Lean statementChallenge.lean: the headline statements, Mathlib imports only
- Palomar listingPalomar registry entry PALOMAR-2026-11-10-000010 v1
- Problem recordOEIS A186783
- OtherHexagonRelated entry: exact directed L/X diameter of the symmetric group (same authors)
Submitted by MellowGander562 on