3 Groups

Group theory has been one of the Computational Algebra Group's traditional strengths and Magma provides the user with access to nearly all of the significant algorithms for finite groups and finitely presented infinite groups (fp-groups). The important categories of group include:

In addition, Magma provides extensive machinery for the representation theory of groups which is discussed in the Representation Theory section of this document.

3.1 Permutation Groups

A permutation action may be defined on any finite set using a G-set mechanism. A huge range of permutation group algorithms (some 300) are incorporated—many of them being developed specifically for Magma. All algorithms are either deterministic or Las Vegas, that is if an answer is returned it is guaranteed correct but it is possible no answer will be returned.

3.1.1 Construction

  • Permutation representations for classical groups, e.g. PGL(n,q), PSp(n,q), PSU(n,q2), P Ω(n,q)

  • Construction of standard groups, e.g., Sn, An.

  • Construction of wreath products with both types of action

  • Random generation of elements (Leedham-Green &Murray (2002)),

3.1.2 Base and Strong Generating Set

  • Sims-Schreier algorithm for constructing a base and strong generating set (BSGS)

  • Random Schreier algorithm for constructing a BSGS (Monte Carlo algorithm)

  • Todd-Coxeter Schreier algorithm for constructing a BSGS

  • Sims variation of Schreier method for soluble groups

  • Fast construction of BSGS when group order is known

  • Brownie-Cannon-Sims algorithm for verifying a BSGS

The key concept for representing a permutation group is that of a base and strong generating set (BSGS). Given a BSGS for a group, its order may be deduced immediately. Brownie, Cannon and Sims (1991) showed that it is practical, in some cases at least, to construct a BSGS for short-base groups having degree up to ten million. For example, starting with six permutations of degree 8 835 156, generating the Lyons simple group, it takes Magma 5.0 hours to provably determine the order of the group they generate.

The ability to construct a BSGS, coupled with the use of algorithms that make heavy use of the classification theorem for finite simple groups, allow the determination of a great deal of structural information, such as composition factors, for short base groups of degree up to at least a million.

3.1.3 Elementary Properties

The functions listed in this section require a BSGS to be computed.

  • Order

  • Exponent

  • Whether abelian, nilpotent, soluble etc

  • Whether perfect, simple etc.

3.1.4 Conjugacy Classes

The conjugacy classes of elements of a group G are found using a lifting algorithm which first finds the classes of the trivial Fitting quotient of G and then lifts these classes through the layers of an elementary abelian series for G. For example, all classes in the group 212.(SL2(4) ≀ S3) of degree 4096 and order 5,308,416,000 are computed in 4 seconds.

  • Testing a pair of elements for conjugacy

  • Conjugacy classes of elements (lifting algorithm)

  • Power map

  • Class map, i.e. return the number of the class to which a given element belongs

  • Class matrix

3.1.5 Subgroup Constructions

  • Construction of subgroups, quotient groups

  • Normal closure, core of a subgroup

  • Normalizer, centralizer

  • Testing subgroups for conjugacy

  • Intersection of subgroups

  • Sylow p-subgroup (reduction algorithm)

A key application of our work on the O'Nan-Scott decomposition has been a Sylow algorithm that reduces the problem to computing Sylow subgroups of simple groups. Though this work is not complete (the algorithm involves many complex stages), we have succeeded in computing Sylow subgroups in short-base groups having degree up to 500 000.

3.1.6 Actions

  • Stabilizer of a point, set of points, sequence of points

  • Stabilizer of an ordered partition, conjugacy of partitions

  • Orbits on points, sets of points, and sequences of points

  • Homomorphisms induced by actions on orbits

  • Systems of imprimitivity (Schönert-Seress algorithm)

  • Homomorphisms induced by actions systems of imprimitivity

  • Induced actions on G-sets

  • Action properties: Semiregular, regular, transitive, primitive, Frobenius

  • Permutation representation on the cosets of a subgroup

  • Fast tests for the alternating/symmetric group

3.1.7 Analysis of a Primitive Group

  • Elementary abelian regular normal subgroup (EARNS)

  • Action of an affine primitive group on its EARNS

  • Construction of the socle of a non-affine group via the O'Nan-Scott theorem

  • Action of a primitive group on its socle

  • Permutation representation of G/N, where G is a primitive group and N is its socle

  • O'Nan-Scott decomposition of a primitive group

  • Identification of a 2-transitive group

The Magma group has developed efficient methods for obtaining the O'Nan-Scott decomposition of a primitive group. The elementary abelian regular normal subgroup of an affine primitive group is constructed by a polynomial-time algorithm based on ideas published by P. Neumann (1986). For example, Magma finds the EARNS of AGL(10,3) which has degree 59,049 and order 17046196453240220939126401085378073952125928970649600 in 36 seconds. The construction of the socle and the analysis of a non-affine primitive group is performed by algorithms based on ideas of Cannon, Holt and Kantor. A 2-transitive group is identified as an abstract group using an algorithm published by Cameron and Cannon.

3.1.8 Normal Structure

  • Derived subgroup, derived series, soluble residual

  • Lower central series, nilpotent residual

  • p-core, Fitting subgroup, soluble radical (Unger's polynomial-time algorithm)

  • Centre, upper central series

  • Elementary abelian series, p-central series

  • Socle, socle action

  • Chief series, chief factors, composition factors

  • Agemo, omega subgroups (of a p-group)

  • Minimal normal subgroups

  • Maximal normal subgroups

  • All normal subgroups

3.1.9 Standard Quotients

  • Maximal abelian quotient

  • Maximal soluble quotient

  • Socle quotient (for primitive and trivial Fitting groups)

  • Conjugation action on socle factors (trivial Fitting groups)

  • Quotient by an abelian normal subgroup

  • Radical quotient

  • Presentation on given generators (for groups of moderate order)

  • Presentation on strong generators

  • Presentation of quotient by a normal subgroup

A variety of methods are used for quotient constructions. Quotients by abelian groups use the algorithm of Luks &Seress (1997). Finitely presented quotients use a combination of the Schreier-Todd-Coxeter-Sims method of Leon (1980) and the presentation implicit in Sims' verification of a BSGS (see Gebhardt (2000)).

3.1.10 Subgroup Structure

  • Maximal subgroups

  • Frattini subgroup

  • Conjugacy classes of complements of a soluble normal subgroup

  • Conjugacy classes of subgroups, poset of subgroup classes

  • Conjugacy classes of subgroups satisfying a condition: cyclic, elementary abelian, abelian, nilpotent

  • Low index subgroups

Magma V2.14 contains an implementation of a very powerful algorithm for computing the maximal subgroups of a group G of moderate degree. The algorithm first determines the maximal subgroups of the trivial Fitting quotient of G and then lifts these maximal subgroups down an elementary abelian series. Magma finds the maximal subgroups of the group of Rubik's cube (degree 48, order 43252003274489856000) in 2.4 seconds.

3.1.11 Automorphisms

  • Automorphism group (new algorithm)

  • Test for two permutation groups being isomorphic

The automorphism group of a permutation group G is found using a lifting algorithm which first finds the automorphisms of the trivial Fitting quotient of G by looking up the automorphism groups of any non-cyclic factors in a database. Then these automorphisms are lifted through the layers of an elementary abelian series for G. For example, the automorphism group of the group of Meffert's puzzle (a non-soluble permutation group of degree 30 and order 28 3105) is found in 4 seconds. The group has 16 outer automorphisms.

3.1.12 Cohomology and Representations

  • Character table

  • Irreducible representations (for groups of moderate order)

  • KG-module corresponding to an elementary abelian section

  • p-part of Schur multiplicator, p-cover

  • Dimensions of first and second cohomology groups

  • Split and non-split extensions of a group by a module (D. Holt's package)

  • Schur indices, rewriting representations over minimal fields

3.1.13 Databases

  • Transitive groups up to degree 30 (Butler, Hulpke)

  • Primitive groups up to degree 2499 (Sims, Roney-Dougal &Unger, Roney-Dougal)

  • Irreducible soluble subgroups of GL(n,p) for pn < 256 (Short)

  • Almost simple groups of order less than 1.6×108, plus M24, HS, L6(2), J3, McL, Sz(32) stored with their automorphism groups and maximal subgroups

  • A collection of permutation representations of some sporadic simple groups

  • Representations of ATLAS groups from the Birmingham ATLAS of finite group representations (R. Wilson).

In V2.14 the database of almost simple groups is augmented by the ability to compute automorphism groups and maximal subgroups for alternating groups up degree 999, families of low degree classical groups (Holt &Roney-Dougal): L2(q), L3(q), L4(q) and L5(q) for all q, S4(q), U3(q) and U4(q) for all q, Ld(2) for d ≤ 14, and the following groups: L6(3), L7(3), U6(2), S8(2), S10(2), O±8(2), O±10(2), S6(3), O7(3), O-8(3), G2(4), G2(5), 3D4(2), 2F4(2)', Co2, Co3, He, Fi22.

3.2 Matrix Groups

Matrix groups may be defined over any ring over which the echelonization of matrices is possible. For example, matrix groups may be defined over function fields K(x). The matrix group facilities are mainly restricted to finite groups since there are, as yet, few algorithms of general interest known for infinite groups. Techniques for working with finite matrix groups divide into methods for groups of small degree and methods for groups of large degree.

3.2.1 Construction

A matrix group is always constructed as a subgroup of the appropriate general linear group, GL(n,R).

  • Generators for linear groups: GL(n,q), SL(n,q)

  • Generators for symplectic groups: CSp(n,q), Sp(n,q)

  • Generators for unitary groups: CU(n,q), GU(n,q), U(n,q)

  • Generators for orthogonal groups: GO(2n + 1,q), SO(2n + 1,q), Ω(2n + 1,q), GO+(2n,q), SO+(2n,q), Ω+(2n,q), GO-(2n,q), SO-(2n,q), Ω-(2n,q)

  • Generators for all exceptional families of groups of Lie type except E8.

  • Direct product, tensor wreath product, tensor power, exterior square

  • Construction of semi-linear groups

  • Group obtained by applying a homomorphism φ: R→S to the matrix coefficients.

  • Group obtained by restricting the matrix coefficients to a subring of R.

3.2.2 Arithmetic with Elements

  • Random generation of elements (Leedham-Green &Murray (2002))

  • Invariants of a matrix: Trace, determinant, minimal and characteristic polynomials, Jordan form, rational canonical form

  • Order of a matrix (Leedham-Green algorithm for finite fields)

  • Test whether a matrix has infinite order

3.2.3 Actions

  • Tests for irreducibility, absolute irreducibility, semi-linearity

  • Test whether a group over a field of characteristic zero has infinite order

  • Orbit, stabilizer of a vector or subspace

  • Orbit representatives and orbit lengths for the action of a matrix group (defined over a prime field) on the k-dimensional subspaces of the natural vector space

  • Estimate the size of the orbit of a given subspace

  • Approximation to the stabilizer of a given subspace

  • Enumerate number of k-dimensional subspaces fixed under the action of an element of GL(d,q)

  • Homomorphism induced by action of a reducible group on a G-invariant submodule and its quotient module

  • Homomorphism induced by action on an orbit of vectors or subspaces

3.2.4 Base and Strong Generating Set

For matrix groups of small degree, we use an analogue of the methods used for permutation groups. We try to find some sequences of objects (subspaces and vectors) in the underlying vector space that defines a stabilizer chain which has the property that the basic orbits are not excessively large. Thus, we have a concept of a base and strong generating set (BSGS) similar to that employed in the case of permutation groups. Once such a BSGS is available, analogues of the permutation group backtrack searches for centralizer, normalizer etc may be described.

  • Random Schreier algorithm for constructing a BSGS

  • Todd-Coxeter Schreier algorithm for constructing a BSGS

  • Murray-O'Brien base selection strategy

3.2.5 Elementary Properties

With the exception of the first, all of the functions listed in this section require the group to be finite and a BSGS to be computed.

  • Whether finite or infinite (only for groups defined over Z or Q)

  • Order

  • Exponent

  • Whether abelian, nilpotent, soluble etc

  • Whether perfect, simple etc.

3.2.6 Conjugacy Classes

  • Testing a pair of elements for conjugacy and finding a conjugating element

  • Conjugacy classes of elements (lifting algorithm, classic algorithm)

  • Power map

  • Class map, i.e. return the number of the class to which a given element belongs

  • Class matrix

3.2.7 Subgroup Constructions

  • Construction of a subgroup in terms of generators

  • Normal closure, core of a subgroup

  • Centralizer

  • Intersection of subgroups

  • Sylow p-subgroup (reduction algorithm)

  • Homomorphism induced by action on the cosets of a subgroup

  • Computing subgroup normalizers

3.2.8 Normal Structure

  • Derived subgroup

  • Soluble residual

  • Centre, Fitting subgroup

  • Derived series, upper central series, lower central series

  • Soluble radical, elementary abelian series, p-central series

  • Composition series, composition factors, chief series

  • Agemo, omega subgroups (of a p-group)

  • Jennings series (of a p-group)

3.2.9 Standard Quotients

  • Maximal abelian quotient, elementary abelian quotient

  • Maximal p-quotient, nilpotent quotient

  • Maximal soluble quotient

  • Presentation on strong generators

  • Quotient by soluble radical

3.2.10 Automorphisms

In V2.14, Holt's algorithm for computing automorphism groups and testing isomorphism may be applied to matrix groups with BSGS.

3.2.11 Cohomology and Representations

The Magma machinery for matrix groups together with fast Gröbner basis techniques (see below) provide a very efficient algorithm for computing a Cohen-Macaulay basis for the ring of invariants together with its syzygies.

  • Character table

  • KG-module corresponding to an elementary abelian section

  • Molien series

  • Ring of invariants

3.2.12 Aschbacher Analysis

The basic facilities provided by Magma for computing with matrix groups over finite fields depend upon being able to construct a chain of stabilizers. However, there are many examples of groups of moderately small degree where we cannot find a suitable chain. An on-going international research project seeks to develop algorithms to explore the structure of such groups. The main theoretical underpinning of the project comes from the classification by Aschbacher (1984) of the (maximal) subgroups of GL(d,q) into nine families. Much of the research effort to date has been devoted to designing algorithms to decide whether G belongs to one of the eight families whose members have a normal subgroup preserving a "natural linear structure"; here, we plan to exploit this information to explore G further, ultimately producing a composition series for G.

  • Determine whether a group preserves a form modulo scalars.

  • The Niemeyer-Prager classical group recognition algorithm as implemented in Magma by Alice Niemeyer and Anthony Pye.

  • Determine whether a subgroup G of GL(d,q) acts imprimitively on the underlying vector space. a block system, respectively.

  • Test whether a matrix group G acts as a semilinear group of automorphisms on some vector space.

  • Test whether a matrix group G preserves a non-trivial tensor product decomposition.

  • Test whether a matrix group G is tensor-induced.

  • Search for decompositions (corresponding to certain Aschbacher families) with respect to the normal closure of a supplied subgroup.

  • The Glasby-Howlett algorithm to decide if the absolutely irreducible group G ≤ GL(d,K) has an equivalent representation over a subfield of K.

  • Given a group G of d×d matrices over a finite field E having degree e and a subfield F of E having degree f, write G as a group generated by the matrices of G written as de/f×de/f matrices over F.

  • Roney-Dougal's algorithm for determining conjugacy of subgroups of GL(d,q)

3.2.13 Databases of Matrix Groups

  • Maximal finite subgroups of GL(n,ℚ) for n up to 31

  • The finite absolutely irreducible subgroups of GLn(D) where D is a definite quaternion algebra whose centre has degree d over and nd ≤ 10

  • Irreducible subgroups of GL(n,p) where p is prime and pn < 2500.

  • Representations of ATLAS groups from the Birmingham ATLAS of finite group representations (R. Wilson).

3.3 Constructive Recognition

Given generators for a finite group, we may be able to determine an isomorphism to a "well-known" group using black-box group methods. Magma is developing its capabilities in this area. In V2.14 the following are available.

  • Alternating and Symmetric groups using the algorithm of Bratus &Pak (2000), implemented by Holt.

  • Alternating and Symmetric groups using the algorithm of Beals et al (2003), implemented by Roney-Dougal.

  • SL(d,q) and PSL(d,q) groups using the algorithm of Kantor &Seress (2001), implemented by Brooksbank.

3.4 Finitely Presented Groups

Given a finitely presented group (fp-group) about which nothing is known, the immediate problems are to determine whether it is trivial, finite, infinite, free etc. and to determine its finite homomorphic images, finite index subgroups and so on. The central strategy for analyzing an fp-group is to attempt to construct non-trivial homomorphisms, which may be onto an abelian group, p-group, nilpotent group, soluble group, permutation group (the Todd-Coxeter algorithm) or matrix group (vector enumeration).

3.4.1 Free Groups

  • Construction

  • Reduction of a word to normal form

  • Product, exponentiation, inverse, equality

3.4.2 Construction

  • Construction as a quotient of a free group

  • Standard groups: Sn, An, dihedral groups, Coxeter groups, braid groups

  • Permutation groups, matrix groups, polycyclic groups as fp-groups

  • Direct product, free product

  • Maximal central extension

3.4.3 Arithmetic on Elements

  • Arithmetic (free reduction only on words)

  • Substring operations on words

  • Definition of and calculation with homomorphisms

3.4.4 Basic Properties

Determining global properties of an fp-group is known to be intrinsically difficult. If it is suspected that a given fp-group is finite, a function is provided that will attempt to determine the order of the group. While this function basically employs coset enumeration, it does so in a fairly sophisticated manner so that it is able to handle groups that are much too large for a coset enumeration of the trivial subgroup to succeed.

3.4.5 Quotients

  • Abelian quotient, elementary abelian quotient

  • p-quotient

  • Process version of p-quotient allowing the user complete control over its execution

  • Nilpotent quotient (W. Nickel's algorithm)

  • Soluble quotient (Plesken-Brückner algorithm)

  • Process version of the soluble quotient allowing the user complete control over its execution

  • Natural homomorphism onto any of the above standard quotients

  • Equivalence classes of homomorphisms to an arbitrary permutation group with application to perfect quotients

  • Process version of search for equivalence classes of homomorphisms allowing the user complete control over its execution

  • Kernel of of the natural homomorphism onto any standard quotient (provided that the quotient is not too large)

The p-quotient program has been developed over a number of years by George Havas, Mike Newman and Eamonn O'Brien. It has been used to construct p-quotients of composition length several thousand for small primes p. Soluble quotients are computed using Herbert Brückner's implementation of the Plesken algorithm and is capable of constructing soluble quotients having order in excess of a million. Unlike previous algorithms, no information is required other than the fp-group.

The computation of equivalence classes of homomorphisms to a permutation group uses a well known backtrack algorithm. Volker Gebhardt's implementation of this algorithm is capable of determining all classes of homomorphisms from a 2- or 3-generator group to a permutation group of order up to 108 in reasonable time.

3.4.6 Constructing a Subgroup

  • Construction of a subgroup in terms of generators

  • Construction of a subgroup in terms of a coset table

  • Coset enumeration (Todd-Coxeter procedure)

  • Process version of coset enumeration allowing the user complete control over its execution

  • Schreier generators for a subgroup

  • Presentation for a subgroup (Reidemeister-Schreier rewriting)

Coset enumeration is performed using George Havas's ACE version of the Todd-Coxeter procedure. It has the capability of enumerating up to one hundred million cosets on a sufficiently large machine.

3.4.7 Operations on Subgroups of Finite Index

The fp-group package also includes a collection of functions for computing with subgroups of (small) finite index represented by coset tables. Hence the operations in this group assume that the subgroup has finite index and that it is possible to enumerate its cosets.

  • Normal closure

  • Membership and equality of subgroups

  • Core, intersection and normalizer

  • All maximal (minimal) overgroups of a subgroup

  • Test for conjugacy, maximality, normality

  • Schreier system and Schreier coset map

3.4.8 Enumeration of Subgroups

Subgroups of small index may be enumerated using the so-called low index subgroups algorithm. The low index algorithm used in Magma is the backtrack method described by Sims in his book Computation in Finitely Presented Groups, CUP, 1993.

  • Enumeration of low index subgroups (Sims backtrack algorithm)

  • Process version of low index subgroups to return subgroups one at a time

3.4.9 Simplifying a Presentation

  • Automatic simplification of a presentation

  • Interactive simplification of a presentation via a Tietze process

  • Tietze process: Eliminate specified generators

  • Tietze process: Control of substring searching

  • Bijection between original and simplified presentations

3.4.10 Actions

  • Actions on coset spaces (Todd-Coxeter procedure)

  • Actions on vector spaces (Linton vector enumeration)

  • Permutation representation on the cosets of a subgroup

3.4.11 Representation Theory

It is frequently useful to construct the G-modules corresponding to the conjugation action of a finitely presented group G on an elementary abelian section. This can be useful when attempting to construct normal subgroups of G.

  • Determine the finite primes dividing the order of the abelian quotient of a subgroup A of a fp-group G

  • Given subgroups A and B defining an abelian section of G, construct the G-module corresponding to the conjugation action of G on the maximal p-elementary abelian quotient of A/B

  • Given a map f from a normal subgroup A of G onto the G-module M corresponding to the conjugation action of G on the maximal p-elementary abelian quotient of an abelian section A/B of G and a submodule N of M, compute the preimage of N under f using a fast pullback method.

3.4.12 Databases of Finitely Presented Groups

  • Fundamental groups of small-volume closed hyperbolic 3-manifolds (Dunfield &Thurston, based on Hodgson &Weeks' census of manifolds).

3.5 Generic Abelian Groups

A generic abelian group is a set whose elements form an abelian group with respect to a given law of composition. The user specifies the set A together with functions for composing two elements of A, constructing the inverse of an element of A, and recognizing the identity element of A.

  • Definition as a set with given operations

  • Arithmetic

  • Random elements

  • Order of an element: Baby-step giant-step algorithm; Pollard-rho algorithm

  • Discrete logarithm: Baby-step giant-step algorithm; Pohlig-Hellman algorithm; Pollard-rho algorithm

  • Order of the group

  • Generating set and presentation

  • Torsion invariants

  • Construction of subgroups from generators

  • Sylow p-subgroup

  • Homomorphisms and isomorphisms

The three major calculations supported are: find the order of an element, compute the discrete logarithm of an element relative to a given base and determine the structure of the group. The algorithms used are improvements of those described in J. Buchmann, M.J. Jacobson and E. Teske [teske_bsgs].

3.6 Finitely-Presented Abelian Groups

Abelian groups are of interest not only for their intrinsic interest but also because many of the important groups arising in number theory and topology are abelian.

  • Construction as a quotient of a free abelian group

  • Direct product, free product

  • Arithmetic

  • Construction of subgroups, quotient groups and complements

  • Elementary divisors, primary invariants

  • Factor basis, divisor basis, primary basis

  • Torsion subgroup, torsion-free subgroup, p-primary component

  • Homomorphisms: Image, kernel, cokernel

  • Composition series, maximal subgroups, subgroup lattice (of a finite group)

  • Character table of a finite group

  • The group of homomorphisms Hom(A,B), where A and B are finite abelian groups

  • Abelian quotient of any group (with its natural homomorphism)

  • Conversion between -modules and abelian groups

  • Functors from rings and fields onto abelian groups

The Hermite and Smith normal form algorithms are used to construct a normal form for subgroups and quotient groups of abelian groups.

3.7 Polycyclic Groups

The category described here comprises the family of all groups defined by a polycyclic presentation. Note that such a group may be infinite. Even so, algorithms for element arithmetic analogous to those used for finite soluble groups are available and a growing number of structural computations are possible within such a group.

3.7.1 Polycyclic Groups: Construction and Arithmetic

  • Construction as a quotient of a free group

  • Standard groups as polycyclic groups

  • Permutation groups, matrix groups, abelian groups and finite soluble groups as polycyclic groups

  • Nilpotent quotient of a finitely presented group (W. Nickel's algorithm)

  • Direct products

  • Wreath products

  • Product, inverse, conjugate, commutator for elements; improved collector, much faster, better complexity

  • Element normal form and equality testing

  • Element order

  • Random element generation

3.7.2 Polycyclic Groups: Basic Invariants

  • Test finiteness, group order

  • Test for abelian, elementary abelian, cyclic, nilpotent

  • Nilpotency class

  • Hirsch number

3.7.3 Polycyclic Groups: Subgroup Constructions

  • Subgroup and quotient group construction

  • Normal closure of a subgroup

  • Conjugation of subgroups

  • Commutator subgroups

  • Test subgroup membership and inclusion

  • Test for normal and central subgroups

  • Centraliser of elements (in a nilpotent group)

  • Normaliser and centraliser of subgroups (nilpotent group)

  • Test for conjugacy of elements and subgroups (nilpotent group)

  • Intersection of subgroups (nilpotent group)

3.7.4 Polycyclic Groups: Normal Structure

  • Normal series with free- or elementary-abelian factors

  • Centre, upper central series

  • Lower central series, derived subgroup and series

  • Fitting subgroup, Fitting series

  • G-module construction from action on free- or elementary abelian sections

  • Abelian quotient structure

3.8 Finite Soluble Groups

A large number of efficient algorithms have been developed for computing information about finite soluble groups defined by a polycyclic presentation. The category described here comprises the family of all finite soluble groups defined by polycyclic presentations. Note that while p-groups are not considered as a separate formal category, in many cases more efficient algorithms are employed. Further, some important operations particular to p-groups are described in a separate section.

3.8.1 Construction

  • Construction of polycyclic presentation for the maximal finite p-quotient of an fp-group (O'Brien's program)

  • Construction of polycyclic presentation for the maximal finite soluble quotient of an fp-group (Plesken-Brückner algorithm)

  • Construction of a polycyclic presentation for a soluble group given as a permutation group or a matrix group

  • Split and non-split extensions, wreath products

  • Representation of a soluble group in terms of a SAG-presentation

  • The soluble groups contained in the Small Groups Library developed by Besche, Eick and O'Brien. This database contains all groups of order up to 2000, except the groups of order 1024, and a number of infinite series of larger groups.

In 1991, Leedham-Green with Brownie and Cannon developed an echelonization algorithm capable of constructing a form of polycyclic presentation for a finite soluble group which exhibits much of the structure. This polycyclic presentation (known as a SAG-presentation) is given in terms of generators defining a chain of subgroups which refines a nilpotent series for the group. Each nilpotent section exhibits a lower p-central series for each prime p involved. Finally, the quotient of the group by a term of the nilpotent series splits over the layer below.

3.8.2 Conjugacy Classes

  • Testing a pair of elements for conjugacy

  • Conjugacy classes of elements

  • Power map

  • Class map, i.e. return the number of the class to which a given element belongs

  • Class matrix

  • Exponent

3.8.3 Subgroup Constructions

  • Construction of subgroups, quotient groups

  • Normal closure, core of a subgroup

  • Normalizer, centralizer

  • Testing subgroups for conjugacy

  • Intersection of subgroups

  • Permutation representation on the cosets of a subgroup

  • System of double coset representatives for a pair of subgroups (Slattery algorithm)

  • Sylow p-subgroup

  • Hall π-subgroups, Sylow basis, complement basis

  • System normalizer, relative system normalizer

Simple variations of the SAG-algorithm may be used to compute normal closures, the lower central series and the derived series. Sylow p-subgroups, Hall π-subgroups, a Sylow basis, and a complement basis may be read directly from the presentation. The availability of such a presentation together with sophisticated module theory machinery allowed us to design fast algorithms for finding the centre and maximal subgroups.

3.8.4 Normal Structure

  • Centre, hypercentre, derived subgroup

  • Derived series, upper central series, lower central series

  • Chief series, composition series

  • Elementary abelian series, p-central series

  • Fitting subgroup

  • Frattini subgroup

  • Normal subgroups

3.8.5 Subgroup Structure

  • Maximal subgroups

  • Conjugacy classes of complements of a normal subgroup

  • Conjugacy classes of subgroups, poset of subgroup classes

  • Conjugacy classes of subgroups satisfying a condition: Cyclic, elementary abelian, abelian, nilpotent

The availability of an SAG-presentation combined with sophisticated module theory machinery allowed us to design fast a algorithm for finding the maximal subgroups of a soluble group.

3.8.6 Automorphisms and Representations

  • Automorphism group of a soluble group (M Smith's algorithm)

  • Character table (Dixon-Schneider algorithm)

  • Character degrees (Conlon's Algorithm)

  • Modular irreducible representations (Glasby-Howlett algorithm)

  • Ordinary irreducible representations (Brückner algorithm)

  • KG-module corresponding to an elementary abelian section

3.9 Finite p-Groups

Following the development, in the early 1970's, of the p-quotient algorithm for constructing polycyclic presentations of a finitely presented p-group, Leedham-Green and others developed an extensive family of elegant and efficient algorithms for finite p-groups. The facilities described here apply to the family of all finite p-groups defined by so-called power-conjugate presentations. Note that as p-groups form a subcategory of the category of finite soluble groups discussed above, most of the soluble group operations apply to p-groups. However, in some cases more efficient algorithms are employed for p-groups than for soluble groups.

3.9.1 Construction

  • As for finite soluble groups

  • Construction of polycyclic presentation for the maximal finite p-quotient of an fp-group (O'Brien algorithm)

  • p-group generation (Eamonn O'Brien algorithm)

3.9.2 Normal Structure

  • As for finite soluble groups

  • Agemo, omega subgroups

  • Jennings series of a p-group

3.9.3 Isomorphisms and Automorphism Groups

  • Construct a standard presentation for a p-group

  • Test two p-groups for isomorphism

  • Automorphism group of a p-group (E O'Brien's algorithm)

3.9.4 Character Theory

  • Degrees of irreducible characters (Slattery's algorithm)

  • Character Table (Conlon's algorithm)

3.10 Groups Defined by Rewrite Systems

This is a category of finitely presented groups where the relations are interpreted as rewrite rules. If the group is defined by a confluent system of rewrite rules then we have a normal form for its elements and hence a solution to the word problem. A group belonging to this category is typically constructed by applying the Knuth-Bendix procedure. As in the case of monoids, Magma uses the Knuth-Bendix developed by Derek Holt as part of his package kbmag.

  • Construction of an RWS group from an fp-group using the Knuth-Bendix procedure. Orderings supported include: RT-recursive, recursive, ShortLex, WT-ShortLex and Wreath

  • Test a rewrite system for confluence

  • Reduction of a word to normal form

  • Operations on words: Product, exponentiation, inverse, equality

  • Enumeration of elements

  • Test for a group being finite

  • Definition of homomorphisms whose domain or codomain is an RWS group

3.11 Automatic Groups

This category corresponds to short-lex automatic groups. A group is represented by four automata: first and second word-difference machines, a word-acceptor, and a multiplier. These automata are constructed using the Knuth-Bendix procedure. This category is implemented by Derek Holt's package kbmag.

  • Construction of an automatic group from an fp-group using the Knuth-Bendix procedure.

  • Reduction of a word to normal form

  • Product, exponentiation, inverse, equality of elements

  • Enumeration of words without repetition

  • Test for a group being finite

  • Growth function for a group

  • Definition of homomorphisms whose domain or codomain is an automatic group

3.12 Groups with Elements given as Straight-Line Programs

This is a class of finitely generated free groups whose elements are represented as "straight-line" programs and which are referred to as SLP-groups for brevity. Typically a SLP-group is used when it is necessary to evaluate long words in a permutation or matrix group G. If G is defined on d generators then a d-generator SLP-group F is defined together with the homomorphism of F onto G which sends the i-th generator of F to the i-th generator of G. Words corresponding to elements of G are built as elements of F where they are represented as expression trees thereby allowing very fast evaluation of long words in G.

  • Construction

  • Arithmetic with straight-line programs

  • Homomorphism from a blackbox group onto an arbitrary group

  • Random generation of elements (Leedham-Green &Murray (2002))

3.13 Braid Groups

This category comprises the family of all braid groups. Note that this special class of finitely presented groups has a solvable word problem. Recently, braid groups have received some interest as possible sources of cryptosystems.

The Magma implementation by Volker Gebhardt supports both Artin's original presentation and the band generator presentation introduced by Birman, Ko and Lee. Elements can be defined as words in the generators or as products of simple elements for either presentation. All possible representations of elements can be used simultaneously; conversions are done automatically if necessary, completely transparent to the user.

3.13.1 Constructing and Accessing Braid Groups

  • Definition of a braid group on n strings.

  • Controlling default presentation, print format for elements and element representation used for group operations.

3.13.2 Constructing and Accessing Elements

  • Identity element and fundamental element.

  • Artin generators and band generators.

  • Generation of pseudo random elements.

  • Representations of an element as words and as products of simple elements for Artin presentation and band generator presentation.

  • Infimum, supremum and canonical length of an element with respect to either presentation.

3.13.3 Normal Forms of Elements

  • Left and right normal form with respect to either presentation.

  • Left and right mixed canonical form with respect to either presentation.

3.13.4 Arithmetic Operations with Elements

  • Product, left and right quotient, left and right conjugate of two elements.

  • Inverse of an element.

  • Cycling and decycling operation for an element with respect to either presentation.

3.13.5 Boolean Predicates

  • Functions determining whether an element is the identity, simple, or a representative of its super summit class (with respect to either presentation), respectively.

  • Tests for equality and conjugacy of elements.

  • Partial orderings of elements with respect to either presentation.

3.13.6 Lattice Operations

  • GCD and LCM with respect to either presentation and either partial ordering.

3.13.7 Conjugates

  • Infimum, supremum and canonical length of the super summit class of an element with respect to either presentation.

  • Computing a representative of the super summit set of an element with respect to either presentation.

  • Computing the set of positive conjugates of an element with respect to either presentation.

  • Computing the super summit set of an element with respect to either presentation.

  • Process versions of the above algorithms for computing positive conjugates and super summit elements.

3.13.8 Homomorphisms

  • Natural symmetric representation.

  • Integral and modular Burau representations.

  • Construction and evaluation of a homomorphism whose domain or codomain is a braid group.

3.14 Subgroups of PSL(2,R)

The group GL+2(ℝ) of 2 by 2 matrices defined over with positive determinant acts on the upper half complex plane ℍ = {x∈C | Im(x) > 0}} by fractional linear transformation:

(
ab
cd
) : z ↦ az + bcz+d.
Any subgroup Γ of GL+2(ℝ) also acts on . A fundamental domain for the action of Γ is a region of * containing a representative of each orbit of the action. Magma contains a package written by Helena Verrill for working with * and with congruence subgroups and their action on *. The subgroups of PSL2(Z) currently allowed are those of the form Γ0(N), Γ1(N), Γ(N), Γ1(N), Γ0(N), and intersections of these groups. The package allows the computation of generators for congruence subgroups, and various other information, such as coset representatives.

  • Computation of generators of congruence subgroups

  • Coset representatives for a subgroup of finite index in PSL2(ℤ)

  • Construction of cusps, cusp widths, and elliptic points of congruence subgroups

  • Farey symbols for congruence subgroups

  • Action of elements of PSL2(ℝ) on the upper half complex plane

  • Determination of vertices of a fundamental domain for the action of a congruence subgroup

  • Equivalence of points under the action of a congruence subgroup

  • Graphics: postscript output of pictures of fundamental domains, points and geodesics, and polygons with geodesic edges (all on the upper half complex plane)