Repository navigation
Formalization of the exact undirected Cayley diameter of the symmetric group Sₙ generated by L (cyclic shift), R = L⁻¹, and X (exchange of the first two positions). Every generator costs one move. For every n ≥ 4, the diameter is n(n−1)/2.
Authors: S. Uskov, A. Chervov, F. Levkovich-Maslyuk, I. Litvak, A. Smolensky, A. Soibelman, Dia Taha. License: MIT.
The main results are LRX.exact_diameter_all, LRX.sharp_diameter_all, and LRX.nonzero_lift_routing. The independent Palomar interface proves PalomarLRX.exactDiameter and PalomarLRX.boundedRouting, including a literal word of at most n(n−1)/2 letters between every ordered pair of permutations.
The repository contains the substantive proof, both diameter bounds, kernel-checked finite certificates, and verification tools. The original extraction removed 66 unused modules and 460 declarations; mathematical minimality is not claimed.
Lean 4.35.0 and Mathlib v4.35.0 are pinned; exact dependency revisions are recorded in lake-manifest.json.
git clone --branch v1.0.0 https://github.com/snow-ghost/lrx-lean.git
cd lrx-lean
lake exe cache get
bash scripts/verify.sh
# With Bubblewrap installed:
lake comparator --config comparator.jsonThe proof sources passed the full local build, the axiom audit of 16032 theorems in 1139 package modules, the sandboxed Comparator with Lean default kernel replay, and GitHub CI. Only propext, Classical.choice, and Quot.sound are permitted. The two deliberate proof placeholders occur only in the independent Challenge.lean; Solution.lean and the substantive proof have none.
Those checks apply to source commit 9cffbfbab7e1d6f5be1012c3caf608478f5af5b6; the release preserves its proof sources, dependencies, and Comparator configuration. Later changes update documentation and make the optional preflight manual only.
Palomar submission verification is running separately. This release does not assert completed Palomar registration or independent human peer review.
The formalization uses classical existence proofs and does not provide an executable shortest-word solver.