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:
Permutation groups
Matrix groups
Finitely presented groups
Coxeter groups
Generic abelian groups
Finitely-presented abelian groups
Polycyclic groups
Finite soluble groups
Finite p-groups
Automorphism groups
Groups defined by rewrite systems
Automatic groups
Groups with elements given as straight-line programs
Black-box groups
Braid groups
Congruence subgroups of PSL(2,ℝ)
In addition, Magma provides extensive machinery for the representation theory of groups which is discussed in the Representation Theory section of this document.
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.
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 (Product-replacement algorithm),
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 ten million.
The functions listed in this section require a BSGS to be computed.
Order
Exponent
Whether abelian, nilpotent, soluble, etc.
Whether perfect, simple, etc.
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 (algorithm of D. Holt) 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
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)
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
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 1.49 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.
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
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)).
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 and later 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 0.42 seconds.
Automorphism group
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 0.14 seconds. The group has 16 outer automorphisms.
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
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.16 the database of almost simple groups is augmented by the ability to compute automorphism groups and maximal subgroups for alternating groups up to degree 999, families of low degree classical groups (Holt &Roney-Dougal): Ln(q) for 2 ≤ n ≤ 7 and all q, Ln(2) for n ≤ 14, S4(q), U3(q) and U4(q) for all q, and the following groups: 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, Suzi, Ru.
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.
A matrix group is always constructed as a subgroup of the appropriate general linear group, GL(n,R).
Generators for linear groups: GL(n,R), SL(n,R) where R is a finite field, R = ℤ, or R = ℤ/nℤ.
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
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.
Random generation of elements (Product-replacement algorithm)
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 over a number field has infinite order
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
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
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 a number field)
Order
Exponent
Whether abelian, nilpotent, soluble, etc.
Whether perfect, simple, etc.
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
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
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)
Maximal abelian quotient, elementary abelian quotient
Maximal p-quotient, nilpotent quotient
Maximal soluble quotient
Presentation on strong generators
Quotient by soluble radical
Holt's algorithm for computing automorphism groups and testing isomorphism may be applied to matrix groups with BSGS.
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
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" (the geometric maximal subgroups); 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)
In addition, V2.16 of Magma has rotuines to compute all maximal subgroups of Magma's standard copies of the classical groups of dimension < 12 over finite fields. In dimension ≥ 12 this is restricted to computing the geometric maximal subgroups.
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).
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. 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.
Sp(d,q), U(3,q), and U(4,q) algorithms supplied by P. Brooksbank.
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).
Construction
Reduction of a word to normal form
Product, exponentiation, inverse, equality
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
Arithmetic (free reduction only on words)
Substring operations on words
Definition of and calculation with homomorphisms
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.
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 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.
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.
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
Magma uses Havas' rewriting Todd-Coxeter to write elements of a subgroup as words in the subgroup generators.
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
Enumeration of low index normal subgroups (Holt's homomorphism algorithm)
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
Actions on coset spaces (Todd-Coxeter procedure)
Actions on vector spaces (Linton vector enumeration)
Permutation representation on the cosets of a subgroup
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.
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].
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.
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.
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
Test finiteness, group order
Test for abelian, elementary abelian, cyclic, nilpotent
Nilpotency class
Hirsch number
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)
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
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.
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.
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
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.
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
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.
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
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.
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)
As for finite soluble groups
Agemo, omega subgroups
Jennings series of a p-group
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
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
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))
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.
Definition of a braid group on n strings.
Controlling default presentation, print format for elements and element representation used for group operations.
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.
Left and right normal form with respect to either presentation.
Left and right mixed canonical form with respect to either presentation.
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.
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.
GCD and LCM with respect to either presentation and either partial ordering.
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.