betaFeedback

WorksMathematics

Digital Finite Group Theory

Abstract

This book develops a digital formulation of finite group theory, in which every finite group of order NN is represented as the alphabet {0,1,…,N−1}\{0,1,\dots,N-1\} endowed with the transported group product. Multiplication, inversion and related structure are written explicitly as integer operations on labels. The foundations treat digit functions, codes of permutations and rr-ary operators, finite magmas, and constructions of laws from diagrams. Classical parts of finite group theory, including conjugacy classes, stabiliser chains and characters, are recast as identities between digits of codes. The book gives explicit digital laws for all groups of order at most 32, the finite quotients of the 17 plane and 230 space crystallographic groups, the symmetric and alternating groups, the finite simple groups of Lie type, and all 26 sporadic groups. For most sporadic groups the laws are obtained by chain constructions; for the Baby Monster and the Monster they are computed structurally from the 196884-dimensional representation and evaluated with the mmgroup package. The accompanying software archive reproduces the laws, tables and worked examples as verifiable integer data.

Preface

The idea of the book

By an alphabet we mean the set AN={0,1,…,N−1}\mathcal{A}_N = \{0,1,\ldots,N-1\} of the first NN non-negative integers; it is the model of a finite set of size NN. Its elements are labels: a finite set XX with NN elements is identified with AN\mathcal{A}_N through a bijection λ:X→AN\lambda:X\to\mathcal{A}_N, its labelling. A label is an integer in its own right and should not be confused with a digit. Each label mm has its own digits, in a base or in a mixed radix adapted to the structure at hand, and it is in these digits that operations on the alphabet are written.

The idea of the book is to describe every finite group GG as an alphabet endowed with the group operation, that is, as a pair (AN,∗)(\mathcal{A}_N,*), where N=∣G∣N=|G| is the order of the group and ∗* is the product of GG transported to AN\mathcal{A}_N. This is achieved for all finite groups, and it is explained in detail for all the infinite families of finite simple groups—the cyclic groups of prime order, the alternating groups and the groups of Lie type—and for the 26 sporadic groups.

A finite operation on an alphabet is read off the digits of a single integer, its code. The basic tool is the digit function

dN(k,x)=⌊xNk⌋−N⌊xNk+1⌋d_N(k,x)=\left\lfloor\frac{x}{N^k}\right\rfloor-N\left\lfloor\frac{x}{N^{k+1}}\right\rfloor

which returns the kk-th digit of xx in base NN. An rr-ary operation on AN\mathcal{A}_N is the integer whose NrN^r base-NN digits are its values, so a magma, a permutation or a whole Cayley table is one number. A group of order NN becomes a digital law: a labelling λ:G→AN\lambda:G\to\mathcal{A}_N, its inverse, and the transported product m∗n=λ(λ−1(m)λ−1(n))m*n=\lambda(\lambda^{-1}(m)\lambda^{-1}(n)) written as a closed formula in the digits of mm and nn. For a cyclic group this formula is addition modulo NN; for a metacyclic group it is the two-digit rule m∗n=dq(0,m+rm1n1)+q ds(0,m1+n1)m*n=d_q(0,m+r^{m_1}n_1)+q\,d_s(0,m_1+n_1); for a finite simple group it packs the coordinates of a normal form or of a stabiliser chain into mixed-radix digits. Every finite group has such a law, since any bijection transports the product. The point of the book is that the bijection can be chosen so that the law is explicit, short and computable, and that the structural properties of the group—associativity, inverses, conjugacy, normal subgroups, characters—become identities between digits of codes.

The book has grown in three directions, and it is worth saying plainly what each contributes. The first is foundational: the digit function and the B\mathcal{B}-function, codes of permutations and of rr-ary operators, and the observation that every finite structure is a single integer. The second is a re-reading of the general theory of finite groups in digital terms: the construction of laws by diagrams, the classical theorems, conjugacy classes, stabiliser chains and characters. Here the abstract statements are kept, and the digital form supplies explicit and checkable instances of them. The third is a catalogue: laws for all groups of order at most 32, for the finite quotients of the plane and space crystallographic groups, for the symmetric and alternating groups, for the families of finite simple groups of Lie type and for the sporadic groups, all in one format, so that they can be compared, transmitted and verified as integer arithmetic. The catalogue is accompanied by worked products in the largest groups and by a software archive that recomputes every law, table and example of the book. Nothing in the book changes what is known about the structure of these groups; the classical background is that of the standard texts [1, 2, 3, 4, 5]. What changes is that the groups become concrete data.

Outline of the chapters

Foundations (Chapters 1 and 2). Chapter 1 introduces the digit function and the digital expansion of integers (Section 1.1), and the B\mathcal{B}-function, which tests digits and expresses comparisons and carries of positional arithmetic in closed form (Section 1.3). Chapter 2 begins with permutations as codes—composition, inversion, cycles, conjugacy and sign (Section 2.1)—and then encodes arbitrary finite magmas and rr-ary operators, their homomorphisms and relabellings, and direct products. Everything that follows uses these two chapters.

General theory in digital form (Chapters 3–6). Chapter 3 is a method for producing group laws: the digits of a label are arranged in layers, and a diagram of arrows prescribes how carries couple them. Associativity is built in by construction, and a gallery of recipes recovers many familiar groups, including simple ones. Chapter 4 restates the main theorems—Cayley, Lagrange, group actions, conjugacy classes and the counting of colourings (Pólya–Redfield and de Bruijn), the isomorphism theorems, the Sylow theorems and the series theorems of Zassenhaus and Schreier—for digital laws, with proofs that run in the digits. Chapter 5 is algorithmic. It presents the Schreier–Sims algorithm [6, 7, 8, 9], whose base and strong generating set is precisely a mixed-radix labelling, and then computes conjugacy classes (their basic theory is in Section 4.4.2), power maps, rationality and fusion, ending with a complete example for M12M_{12}. Chapter 6 develops ordinary character theory—Maschke, Schur and Wedderburn, the orthogonality relations, integrality, induction and restriction—and turns it into a roadmap for computing character tables from class data [3, 4, 10, 11].

Families of groups (Chapters 7–9). Chapter 7 gives the laws of cyclic groups, additive and multiplicative, and of finite Abelian groups as direct sums, with explicit isomorphisms for coprime factors. Chapter 8 treats semidirect products, dicyclic, dihedral and metacyclic groups, wreath products and transitive actions; its Section 8.4 computes the characters of metacyclic, dihedral and dicyclic groups directly from the two digits of their laws. Chapter 9 classifies the groups of order at most 32 and gives a law for each of them [12, 13].

Crystallographic groups (Chapter 10). Chapter 10 gives digital laws for the finite quotients G/mLG/mL of the 17 plane groups and of the 230 space groups. An element {Ri∣ti+24s}\{R_i \mid t_i+24s\} receives the label im3+s1m2+s2m+s3i m^3+s_1m^2+s_2m+s_3; the product adds the rotated translation digits, and the carry c(i,j)c(i,j) is an integer cocycle determined by the conventional operations. The quotients modulo 2T2T, 6T6T and 2L2L are identified in the small groups library and separated by their invariants.

Finite simple groups (Chapters 11–13). Chapter 11 treats Sym⁡n\operatorname{Sym}_n and Alt⁡n\operatorname{Alt}_n: generators and presentations, conjugacy classes, simplicity, maximal subgroups, automorphisms including the outer automorphism of Sym⁡6\operatorname{Sym}_6, the characters of Sym⁡n\operatorname{Sym}_n and Alt⁡n\operatorname{Alt}_n [14, 15, 16, 17, 18], and the Lehmer and rotation laws. Chapter 12 builds finite fields in digital form and then the groups of Lie type, from PSL⁡(2,N)\operatorname{PSL}(2,N) through the classical families, the Suzuki and Ree groups, G2(q)G_2(q) and 3D4(q){}^{3}D_4(q) to F4(q)F_4(q), 2F4(q){}^{2}F_4(q) and the groups of type EE. Their product rules are transcriptions of the Bruhat normal form and the Chevalley commutator relations [19, 20, 21, 22, 23, 24, 25]. Chapter 13 gives laws for the sporadic groups, from the Mathieu groups through the Conway, Fischer and Janko groups to the Monster and the Baby Monster, relative to standard generators [26, 27, 28, 29]. It ends with canonical labels and with the recomputation of a character table from a printed law.

Worked products and software (Chapters 14 and 15). Chapter 14 multiplies explicit labels in PSL⁡2(7)\operatorname{PSL}_2(7), PSL⁡3(2)\operatorname{PSL}_3(2), Sz⁡(8)\operatorname{Sz}(8), 2G⁡2(3){}^{2}\operatorname{G}_2(3), M⁡24\operatorname{M}_{24}, Co⁡0\operatorname{Co}_0, J⁡4\operatorname{J}_4, Th⁡\operatorname{Th} and the Monster, and computes the inverses and orders of the factors and products within the digital laws themselves, with an independent check by decoding. Chapter 15 describes the published archives, their installation and layout, the reproduction workflow, and each program and data file, including those for the crystallographic groups.

Chapter 16 contains solutions to the exercises of all chapters.

Dependencies and reading paths

Figure 1 shows the main dependencies. Chapter 1 is used everywhere, and the permutation codes of § 7.1 reappear wherever groups act. Chapter 4 builds on the diagrammatic construction of Chapter 3. Chapter 5 combines the Schreier–Sims algorithm with conjugacy classes, and Chapter 6 uses both parts. The families of Chapters 7–9 need essentially only Chapters 1 and 2; the exceptions are § 14.4, which uses Chapter 6, and § 14.13, which uses Chapters 4 and 6. These chapters are placed after the general theory so that Chapters 3–6 form one block, but a reader who prefers examples first can read them directly after Chapter 2. Chapters 11–13 draw on all of this: Chapter 11 on § 7.1 and on Chapters 5 and 6, Chapter 12 on Chapter 11, and Chapter 13 on the stabiliser chains of Chapter 5, the transitive laws of Theorem 8.32 and the groups of Lie type. Chapter 10 uses the semidirect products of Chapter 8 and the identification of small groups in Chapter 9. Chapter 14 draws on Chapters 12 and 13, and Chapter 15 can be consulted at any point alongside the chapter whose computations it reproduces.

Main dependencies between the chapters

Figure 1. Main dependencies between the chapters. An arrow A→BA \to B means that Chapter BB uses results of Chapter AA; Chapter 1 and § 7.1 are used throughout, and only their first arrows are drawn. The dashed arrows into Chapter 8 mark § 14.4 and § 14.13. Chapter 15, which documents the programs of all chapters, is not drawn.

Three routes through the book are natural. A first course in finite groups in digital form reads Chapters 1 and 2, then Chapters 7–9, and then Chapter 4. A reader interested in computation reads Chapters 1 and 2, then Chapters 5 and 6. A reader interested in the simple groups can go from Chapters 1 and 2 directly to Chapters 11–13, consulting Chapters 5–6 and Chapter 8 when they are cited.

Verification and reproducibility

Every law in the book is a finite object, and most of them are small enough to be checked exhaustively. Generated tables—for instance the character data of § 14.4 and the tables of Chapter 11—are produced by scripts kept with the source of the book. They rebuild each group from its printed law, verify the stated identities in exact arithmetic and compare the results with GAP [30]; the single command python3 scripts/sn_verify.py regenerates and checks all of them. For the large groups the laws are tied to standard generators [26, 27] and come with fingerprints, so that they can be reproduced independently of this book. Chapter 15 lists the published archives and describes every program and data file; the same scripts reproduce the crystallographic laws and identifications of Chapter 10 and the worked products and inverses of Chapter 14.

Conventions

Throughout, AN={0,1,…,N−1}\mathcal{A}_N = \{0,1,\ldots,N-1\}, dN(k,x)d_N(k,x) is the kk-th base-NN digit of xx, and Dh(m)D_h(m) is the hh-th digit of mm in a mixed radix fixed by the context. Permutations are composed from right to left, as in (12). Group laws are written m∗nm * n on labels; when a group is given by generators,

xayαx^{a}y^{\alpha} denotes the element whose label has digits aa and α\alpha. The preface closes with a survey of related work and a list of what we believe is new.

A digital law is a bijection λ ⁣:G→A∣G∣\lambda\colon G \to A_{\lvert G\rvert} together with the transported product m∗n=λ(λ−1(m)λ−1(n))m \ast n = \lambda\bigl(\lambda^{-1}(m)\lambda^{-1}(n)\bigr). Bijections of this kind are not new; what this book adds is a uniform, explicit and reproducible catalogue of them. We list the known ingredients first.

Stabiliser chains. Sims introduced bases and strong generating sets [6]: for a base (b1,…,bk)(b_1,\ldots,b_k) every element of a permutation group factors uniquely as s1,t1⋯sk,tks_{1,t_1}\cdots s_{k,t_k}, with sl,ts_{l,t} running over a transversal of the ll-th basic orbit. Reading the indices tlt_l in mixed radix is exactly the chain law of Chapter 13 and the iterated transitive law of Theorem 8.32. This factorisation is the basis of permutation group algorithms [7, 8, 9]; GAP enumerates the elements of a permutation group through it [30], Knuth uses “Sims tables” to generate all elements of a group [31], and Jerrum studied compact representations built on it [32]. The bijection underlying a chain law is therefore classical; the contribution here is to treat the resulting integer law as the object of study and to publish it.

Ranking and unranking. The permutation codes of Section 2.1 are relatives of the Lehmer code and the factorial number system [33]. Ranking and unranking combinatorial objects, including permutations in lexicographic order and in linear time, is a developed subject [34, 35, 36]. Its emphasis is on efficient bijections for whole classes of objects, not on transporting a group product.

Normal forms in groups of Lie type. The laws of Chapter 12 pack the coordinates of the Bruhat normal form G=⨆wUTwU˙wG = \bigsqcup_{w} U T w \dot{U}_{w} into one integer. The normal form and the Chevalley commutator relations that drive the product are classical [20, 21], and algorithms that multiply in these coordinates are implemented in Magma [37]. Our product rules for 3D4(q){}^{3}D_{4}(q), F4(q)F_{4}(q), 2F4(q){}^{2}F_{4}(q) and the EE series are explicit transcriptions of this theory, checked against matrix models.

Canonical representatives. The lexicographically least element of a coset, and more generally the smallest image under a group, is a standard tool in backtrack search [7, 8, 38]. The canonical lexicographic law uses this greedy step; what is new is to use it to fix a labelling that depends only on the permutation group.

The Monster and the Baby Monster. The smallest permutation degrees of B\mathbb{B} and M\mathbb{M}, about 1.4⋅10101.4\cdot10^{10} and 102010^{20}, exclude the orbit enumeration that works for the other sporadic groups, so the coset digits must be computed from the structure. Our starting point is the Python package mmgroup of Seysen, which multiplies elements of M\mathbb{M} and reduces them to a normal form, together with the 196884196884-dimensional representation, in which the 2A2A involutions correspond to axes. The package is a model of M\mathbb{M}, not a labelling of it: it does not give a canonical coset representative, and we construct one from the orbits of K=CGx0(β+)K = C_{G_{x_0}}(\beta^+) on the axes.

Crystallographic groups. The 17 plane and 230 space groups and their symmetry operations are classical and tabulated in the International Tables for Crystallography [39]. A space group is an extension of its lattice by its point group, described by a cohomology class with values in the translations, and its finite quotients by sublattices are a standard tool for studying subgroups of finite index. The laws of Chapter 10 make this extension explicit as integer arithmetic: the label is the point-group index followed by the translation digits modulo mm, and the carry is the integer cocycle c(i,j)c(i,j) of the conventional operations. The quotients modulo 2T2T, 6T6T and 2L2L are identified with GAP [30].

Groups as data. The Atlas [26] and the online Atlas of group representations [27] fix standard generators, which is what makes the generator fingerprints of this book reproducible. Integer-labelled group operations have recently become benchmarks in machine learning [40, 41], where they are mostly limited to cyclic and small symmetric groups.

What is new. To our knowledge the following are not available elsewhere in one place:

  • a digital law, with explicit λ\lambda, λ−1\lambda^{-1} and ∗\ast on A∣G∣\mathcal{A}_{|G|}, for every family of finite simple groups treated here, in a single format;

  • explicit coordinate product rules for the exceptional families, verified over every field tested;

  • canonical laws that depend only on the group and its standard generators, with fingerprints that allow independent reproduction;

  • complete laws for all groups of order at most 32;

  • digital laws for the finite quotients G/mLG/mL of all 17 plane and 230 space crystallographic groups, with integer cocycles as carries, and identifications of the quotients modulo 2T2T, 6T6T and 2L2L in the small groups library (Chapter 10);

  • the observation, carried out for M11M_{11}, that the printed laws suffice to recompute classical invariants such as the character table;

  • a method that produces associative laws layer by layer from diagrams of carries (Chapter 3), and digital versions of the main theorems of finite group theory (Chapter 4);

  • character theory carried out on codes, with closed formulas in the digits of the labels for the characters of metacyclic, dihedral and dicyclic groups (§ 14.4) and with generated character data for Sym⁡n\operatorname{Sym}_n and Alt⁡n\operatorname{Alt}_n (Chapter 11);

  • a digital law for M\mathsf{M} whose coset digit indexes the 2A2A involution (equivalently its axis) and whose fibre digit is a law of 2.B2.B (Proposition 13.74), and a digital law for B\mathsf{B} obtained from it (Theorem 13.72), in both cases with canonical coset representatives built from orbits of axes and checked against mmgroup on random elements;

  • worked products, inverses and orders of explicit labels in groups from PSL⁡2(7)\operatorname{PSL}_2(7) to the Monster, computed within the digital laws and checked independently by decoding (Chapter 14);

  • generated tables whose scripts rebuild each group from its printed law, verify the stated identities exactly and compare them with GAP [30], published with all other programs and data in the versioned archives described in Chapter 15.

Nothing in this book changes what is known about the structure of these groups. The aim is to make them explicit, computable and comparable as integer arithmetic.

The digit function

Digits of integers and the digital expansion

Definition 1.1. Let N≥2N \ge2 be an integer. For x∈Rx \in\mathbb{R} and k∈Zk \in\mathbb{Z} the digit function is

dN(k,x)=⌊xNk⌋−N⌊xNk+1⌋(1)d_N(k,x)=\left\lfloor\frac{x}{N^k}\right\rfloor-N\left\lfloor\frac{x}{N^{k+1}}\right\rfloor \tag*{(1)}

The set AN={0,1,…,N−1}\mathcal{A}_N=\{0,1,\ldots,N-1\} is the digital alphabet of size NN.

Lemma 1.2 (Basic properties). Let x∈Rx \in\mathbb{R} and k∈Zk \in\mathbb{Z}.

  1. dN(k,x)∈ANd_N(k,x) \in\mathcal{A}_N and dN(k,x)=dN(0,x/Nk)d_N(k,x)=d_N(0,x/N^k).

  2. If x∈Zx \in\mathbb{Z}, then dN(0,x)=x mod Nd_N(0,x)=x \bmod N.

  3. If x∈Zx \in\mathbb{Z} and 0≤x<NM0 \le x < N^M, then dN(k,x)=0d_N(k,x)=0 for k≥Mk \ge M and x=∑k=0M−1dN(k,x)Nkx=\sum_{k=0}^{M-1}d_N(k,x)N^k.

Proof. Put y=x/Nky=x/N^k. Since ⌊⌊y⌋/N⌋=⌊y/N⌋\left\lfloor\lfloor y\rfloor/N\right\rfloor=\lfloor y/N\rfloor, Euclidean division gives ⌊y⌋=N⌊y/N⌋+r\lfloor y\rfloor=N\lfloor y/N\rfloor+r with r∈ANr \in\mathcal{A}_N, and r=dN(k,x)r=d_N(k,x); this proves (1) and (2). For (3) the sum telescopes:

∑k=0M−1(⌊xNk⌋−N⌊xNk+1⌋)Nk=x−NM⌊xNM⌋=x.\sum_{k=0}^{M-1}\left(\left\lfloor\frac{x}{N^k}\right\rfloor-N\left\lfloor\frac{x}{N^{k+1}}\right\rfloor\right)N^k=x-N^M\left\lfloor\frac{x}{N^M}\right\rfloor=x.

References

  1. [5][5]
  2. [21][21]

Paper details

vlnc:W_za4g5c2c
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents