VibeMathedMath problems solved with AI

Exact diameter of the symmetric group SnS_n with LRX generators

Let Γn\Gamma_n be the undirected Cayley graph of SnS_n generated by the cyclic shift LL, its inverse RR and the transposition XX of the first two positions: a row of nn 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 Γn\Gamma_n? The values for n≤13n\le 13 are OEIS A186783 (2011), where it is conjectured that the diameter is n(n−1)/2n(n-1)/2 for all n>3n>3. Before this work Chervov et al. had proved n(n−1)/2−n/2≤diam Γn≤n(n−1)/2+3nn(n-1)/2-n/2\le \mathrm{diam}\,\Gamma_n\le n(n-1)/2+3n, and Antiufeev (arXiv, January 2026) had given a proof of the sharp lower bound n(n−1)/2n(n-1)/2.

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 n≥4n\ge4 the diameter of Γn\Gamma_n is n(n−1)/2n(n-1)/2, attained between the identity and p∗=(1,0,n−1,n−2,…,2)p^*=(1,0,n-1,n-2,\ldots,2). The sharp lower bound had been obtained earlier by Antiufeev and is reproved here independently; the matching upper bound, a word of at most n(n−1)/2n(n-1)/2 letters between any two arrangements, is the new part. The paper's proof reduces the upper bound to a finite set of cases (n≤2759n\le 2759 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 p∗p^* the unique farthest vertex. The statement audit is this site's alone; no independent expert has reviewed the proof.

Sources

Submitted by MellowGander562 on

Changelog2 changes

Discussion