Metraipolis › archive › dc_af5cf77ae467
Machine-Checked Computational Group Theory in Lean 4: Operational Schreier-Sims Stabilizer Chains, BSGS Sifting, and Backtrack Ordered Partitions — arXiv:2609.38492
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.38492
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:17:53.694Z
- SHA-256 of the archived text
368de6579b80fd3ab561ee8289efa27f479a2ce44a3096e7dc17d65c897e074e- Stable URL of this page
https://metraipolis.com/documento/dc_af5cf77ae467
How to cite
Machine-Checked Computational Group Theory in Lean 4: Operational Schreier-Sims Stabilizer Chains, BSGS Sifting, and Backtrack Ordered Partitions — arXiv:2609.38492 — arXiv (en), https://arxiv.org/abs/2609.38492 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_af5cf77ae467 (Metraipolis archive dc_af5cf77ae467, sha256 368de6579b80fd3ab561ee8289efa27f479a2ce44a3096e7dc17d65c897e074e)
BibTeX
@misc{dcaf5cf77ae467,
title = {Machine-Checked Computational Group Theory in Lean 4: Operational Schreier-Sims Stabilizer Chains, BSGS Sifting, and Backtrack Ordered Partitions — arXiv:2609.38492},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.38492},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_af5cf77ae467; sha256 368de6579b80fd3ab561ee8289efa27f479a2ce44a3096e7dc17d65c897e074e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.38492. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We present gap-lean4-port (Release v0.2.0), a machine-checked formalization of foundational algorithms in computational discrete algebra and permutation group theory within the Lean 4 interactive theorem prover and Mathlib4. While modern proof assistants feature extensive abstract algebraic hierarchies, constructive and operational permutation group algorithms, such as Charles Sims' 1970 Schreier-Sims algorithm, transversal tree lookups, and backtrack ordered partition refinement, have remained largely unformalized in dependent type theory. Here, we formalize the operational algorithmic core of the Groups, Algorithms, Programming (GAP) system library across four foundational modules, proving 35 machine-checked theorems with zero unproven conjectures (sorry) and zero custom axioms under standard Lean 4 foundations (propext, this http URL , this http URL ). We machine-check: (1) Schreier-Sims stabilizer chain hierarchies (StabLevel, StabChain) and the invariance of incremental transversal tree extensions (extendSchreierPoint_invariant); (2) single-level and multi-level Schreier sifting reductions (siftOneLevel, siftFull), proving that full sifting strictly fixes all base points (siftFull_fixes_all_basePoints); (3) constructive soundness and completeness of Base and Strong Generating Set (BSGS) membership testing (membershipTestKnownBase_iff_mem); (4) backtrack ordered partition cell refinement (splitCellByPred), proving mutual cell disjointness, union conservation, and exact cardinality preservation; (5) cyclotomic extension rings Z/nZ(eps_m) and machine-check GAP's exact size theorem |Z/nZ(eps_m)| = n^m; and (6) executable Bezout inverses via Extended Euclidean GCD ( this http URL ) over residue rings Z/nZ. The entire codebase compiles deterministically under 'lake build RequestProject' and is openly available at this https URL . Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.LO). Categorie arXiv: Logic in Computer Science (cs.LO) ; Symbolic Computation (cs.SC). Pagina del lavoro: https://arxiv.org/abs/2609.38492 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T14:51:10.182Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).