CS Paper Radar

A constructive ATLAS of finite simple groups in Lean

Gerald Höhn

cs.SC cs.LOmath.GR ·submitted 2026-09-25 04:51 UTC · v1
unusual

Abstract

We present a constructive atlas of finite simple groups with proofs of their orders, simplicity, and structural properties. The eight completed families are cyclic groups of prime order, alternating groups, the classical series $A_r(q)$, $B_r(q)$, $C_r(q)$, $D_r(q)$, and the exceptional series $G_2(q)$ and the small Ree groups $ {}^2G_2(3^{2m+1})$, $m\geq1$. The fifteen sporadic entries are $M_{11}$, $M_{12}$, $M_{22}$, $M_{23}$, $M_{24}$, $\mathrm{Co}_1$, $\mathrm{Co}_2$, $\mathrm{Co}_3$, $\mathrm{McL}$, $\mathrm{HS}$, $\mathrm{Suz}$, $J_2$, and $\mathrm{Fi}_{22}$, $\mathrm{Fi}_{23}$, $\mathrm{Fi}_{24}'$. The simple parameter ranges and exceptional cases are stated explicitly. The models arise from codes, lattices, forms, algebras, and finite geometries, including the split octonions and the Conway--Parker algebra. They retain natural actions, stabilizers, central quotients, and comparison maps for subsequent group theory. Several classical comparison isomorphisms relate the models, while involution-class counts distinguish the equal-order orthogonal and symplectic families in odd characteristic and rank at least three. Drawing on classical sources and companion mathematical work, the project develops the construction side of finite simple group theory, not the exhaustiveness proof of the classification. The completed models and stated proofs are formalized in Lean for verification and reuse.

Comment
29 pages. Lean formalization, catalogue, and verification material available from the source repository linked in the paper

Closest papers

Nearest neighbours by meaning across the whole index.

Conjugator Length in Iterated Cyclic Amalgams of Free Groups

cs.DM math.GR ·2026-09-17 ·Conan Gillis
similarity 0.52
Abstract · Includes appendix by author

Let $\mathcal{A}_0$ be the set of finitely generated free groups on some countable alphabet and and define $\mathcal{A}_r$ inductively as the union of $\mathcal{A}_{r-1}$ with the set of amalgamated free products $G_1\ast_{\ZZ}G_2$, where $G_1,G_2\in \mathcal{A}_{r-1}$. We show, for all $r$, that every element of $\mathcal{A}_r$ has linear conjugator length, quantifying a result of Larsen and extending a result of Kharlampovich and Myasnikov. This is achieved by a linear conjugator length bound on a family of iterated HNN extensions of free groups. Also, in an appendix, we adapt a proof of A. Wei$ß$ to show that all Generalized Baumslag-Solitar Groups have linear conjugator length. As a consequence, we obtain that one-relator groups with non-trivial center have linear conjugator length, giving evidence for a conjecture of Bridson, Riley, and Sale.

0.20

Faster Isomorphism for Groups of Class 2

cs.DS ·2026-11-04 ·Xiaorui Sun
similarity 0.51
Abstract

The finite-group isomorphism problem asks whether two groups, given by their Cayley tables, are isomorphic. Despite decades of study, obtaining an $N^{o(\log N)}$-time algorithm for general groups of order $N$ remains a major open challenge. Groups of nilpotency class $2$ have long been a central obstacle to achieving this goal. Recent breakthroughs have established $N^{o(\log N)}$-time algorithms for $p$-groups of class $2$ with odd $p$ (Sun, STOC '23; Ivanyos-Mendoza-Qiao-Sun-Zhang, FOCS '24; Grochow-Qiao-Stange-Sun, STOC '25) and for groups of Frattini class $2$ (Grochow-Ivanyos-Qiao-Sun, FOCS '26). However, the problem remained open for general groups of class $2$. In this paper, we present an algorithm for testing isomorphism of groups of class $2$, with running time $N^{O((\log N)^{25/26} \log \log N)}$. Our algorithm combines a tensor-based restriction of the search space, an encoding of group relations by alternating matrix tuples, and an orbit computation to recover the remaining central power information.

0.06

Word Length and Diameter in Permutation Groups

cs.CC math.GR ·2026-09-22 ·Markus Lohrey, Alexander Thumm
similarity 0.50
Abstract

In the binary diameter problem, the input consists of explicitly given permutations generating a finite group $G$ and a binary-encoded number $k$, and the question is whether every element of $G$ is a product of at most $k$ of the given generators. In the binary length problem, the input additionally contains a permutation $g \in G$, and the question is whether $g$ is such a product. We show that the binary diameter problem is PSPACE-complete, thereby confirming a conjecture of Lohrey and Rosowski (2023). Moreover, we show that PSPACE-hardness already holds for solvable groups of derived length at most 3, whereas the problem is $Π_2^{\mathrm{P}}$-complete for 2-step nilpotent groups. For the binary length problem, we establish a sharp complexity threshold: the problem is NP-complete for 2-step nilpotent groups, which extends a result of Lohrey and Rosowski for abelian groups, and PSPACE-complete for groups that are simultaneously 3-step nilpotent and metabelian, which strengthens the main result of Jerrum (1985). Finally, we show that the unary diameter problem, where $k$ is encoded in unary, is $Π_2^{\mathrm{P}}$-complete for generating sets of the full symmetric group, confirming another conjecture of Lohrey and Rosowski.

0.28

Three Infinite Classes of APN Permutations on $Z_n$

cs.IT math.CO ·2026-09-05 ·Deng Tang
similarity 0.50
Abstract

For any permutation of a nontrivial finite abelian group, the differential uniformity is at least two; permutations attaining this bound are called almost perfect nonlinear (APN). We construct three infinite classes of APN permutations on the cyclic group $\mathbb{Z}_n$ using Singer cycles, binomials inducing projective permutations, and completed reciprocals combined with parity and quadratic characters. The respective domain orders are $q+1$ for prime powers $q>2$, $(3^d-1)/2$ for integers $d\ge2$, and $2p$ for primes $p>5$ with $p\equiv5\pmod6$. Each class contains an infinite subclass of composite orders outside the standard forms $r-1$, $r-2$, $r-3$, and $r-4$, where $r$ is a prime power. These forms arise in the Welch--Costas, Panario--Sakzad--Stevens--Wang, and Golomb constructions. To the best of our knowledge, these are the first infinite APN constructions on $\mathbb{Z}_n$ reported since 2011 that yield infinitely many composite orders outside these standard forms.

0.37

Coset Lifted Product Codes: Constructing Quantum LDPC Codes from Non-Normal Subgroup Actions

cs.IT quant-ph ·2026-10-08 ·Rajendra Prasad Rajpurohit, V. Lalitha, Shayan Srinivasa Garani
similarity 0.49
Abstract

We introduce coset lifted product (CLP) codes, a family of quantum LDPC codes that combine the protograph structure of lifted product codes with the coset action of Aydin, Tamo, and Barg \cite{AydinTamoBarg2026}. Given a finite group $G$, a subgroup $H \le G$ that need not be normal, a protograph $A$ over $\mathbb F_2[G]$, and a protograph $B$ over $\mathbb F_2[N_G(H)]$, the two protographs act on the cosets $G/H$ from the left and from the right to produce quantum CSS codes. Further, for groups of odd order, we give an explicit formula for the dimension as a sum over the irreducible representations $ρ$ of $G$ of hypergraph product dimensions. A search over $14,843$ pairs $(G,H)$ with $H$ restricted to be non-normal and $120 \le n \le 400$ yields certified codes that exceed the best published value of $Q=kd^2/n$ at check weights $6,7$ and $9$, i.e., we obtain $[[360,20,20]]$ at $w=6$, a $[[360,24,20]]$ code at $w=7$, and codes $[[252,16,18]]$ and $[[288,16,20]]$ at $w=9$. Our search also produce high-distance codes with parameters $[[168,10,14]], [[240,8,20]]$ at $w=6$ and $[[216,8,18]]$ at $w=7$.

0.18

A Counterexample to the Gyarmati-Matolcsi-Ruzsa Conjecture

cs.IT math.CO ·2026-10-30 ·Chandra Nair, Aref Namayandeh, Zhaobang Zhu
similarity 0.49
Abstract · 12 pages

We provide a counterexample to the non-abelian Gyarmati-Matolcsi-Ruzsa conjecture. The construction comes from an equivalent maximal-coupling entropy inequality, for which a counterexample can be found in a lower-dimensional group. We give an explicit cardinality counterexample in $D_4^{14}$, the fourteenth direct power of the dihedral group of order $8$.

0.48

Subgroup and Submonoid Membership in the lampshuffler of $\mathbb{Z}$

cs.DM math.GR ·2026-10-05 ·Corentin Bodart, Ruiwen Dong
top venuetheory similarity 0.49
Abstract · appears in SODA'27

The lampshuffler group of $\mathbb{Z}$ is the semidirect product $\operatorname{FSym}(\mathbb{Z}) \rtimes \mathbb{Z}$, which consists of all permutations of $\mathbb{Z}$ that act as a translation outside a finite set. This infinite permutation group naturally contains as subgroups the wreath products $H \wr \mathbb{Z}$ for every finite group $H$. We prove that the Subgroup Membership Problem, and more generally, the Submonoid Membership Problem, are decidable in $\operatorname{FSym}(\mathbb{Z}) \rtimes \mathbb{Z}$. Our proof reduces Subgroup and Submonoid Membership in $\operatorname{FSym}(\mathbb{Z}) \rtimes \mathbb{Z}$ to Subgroup Membership in the wreath products $H \wr \mathbb{Z}$, which was shown to be decidable by Lohrey, Steinberg and Zetzsche (2015).

0.28

Boxicity of Power Graphs of Finite Nilpotent Groups

cs.DM math.COmath.GR ·2026-11-04 ·L. Sunil Chandran, Jinia Ghosh, Suraj Kumar Sahoo
theory similarity 0.48
Abstract · 28 pages

The \textit{boxicity} of an undirected graph $Γ$, denoted as $\operatorname{box}(Γ)$, is the smallest non-negative integer $d$ such that $Γ$ can be represented as the intersection graph of axis-parallel rectangular boxes in $\mathbb{R}^d$. The \emph{power graph} of a group $G$, denoted as $\operatorname{Pow}(G)$, is an undirected graph whose vertex set is the group itself, with two elements being adjacent if one is a power of the other. We determine the exact boxicity of power graphs of finite nilpotent groups. For a cyclic group of order $n=\prod_{i=1}^{r}p_i^{e_i}>1$, where the $p_i$ are distinct primes, we prove that its power graph has boxicity $\sum_{i=1}^{r}e_i-\max_i e_i$. For a finite nilpotent group $G$, let the number of noncyclic odd Sylow subgroups be denoted by $t(G)$. If $G$ has odd order or if $G$ has a cyclic Sylow $2$-subgroup, then $\operatorname{box}(\operatorname{Pow}(G))=\operatorname{box}(\operatorname{Pow}(\mathbb{Z}_{\operatorname{exp}(G)}))+t(G)$, where $\operatorname{exp}(G)$ denotes the \emph{exponent} of a group $G$. When the Sylow $2$-subgroup is noncyclic, and the odd part is nontrivial, the boxicity equals this value or one more, and we characterise precisely when each of these values is attained. The boxicity of power graphs of arbitrary finite groups and the exact boxicity of the comparability graph of the Boolean lattice were posed as open questions in Discrete Mathematics, 349(7):115017, 2026. As a consequence of our results, we answer the latter question completely and the former question partially, by computing the exact boxicity of the power graphs of nilpotent groups.

0.27