Permutation groups in Magma may be defined by giving the support set and a generating set for the group. In addition, Magma provides a large number of standard constructions for permutation groups, as well as databases of permutation groups.
Standard constructions include the symmetric and alternating groups, as well as projective linear groups and the other families (unitary, symplectic, orthogonal) of projective classical groups, affine linear groups, projective Suzuki groups, cyclic groups, abelian groups, dihedral groups, and extraspecial groups. Standard functions for constructing permutation groups from other groups include direct products, wreath products, and primitive wreath products. Coset enumeration in arbitrary groups (including permutation groups) also leads to permutation groups.
Magma includes a database of all transitive groups of degree up to 48 (Butler, Hulpke, Cannon, Holt) and a database containing all primitive permutation groups of degree up to 4095 (Sims, Roney-Dougal, Unger, Coutts). Magma also contains a version of the online finite simple groups database of Wilson et al., which contains many permutation representations of simple and nearly simple groups.
To determine the order of a permutation group and most other structural information it is necessary to first construct a suitable representation of the set of group elements. In 1970 C. Sims introduced the notion of a base and strong generating set (BSGS) for a permutation group G. The base is a sequence B = β1,…,βk of points chosen from the set on which G acts such that the only element of G that fixes B pointwise is the identity. Thus, B defines a chain of stabilisers G⊃Gβ1⊃Gβ1,β2,⊃…,⊃Gβ1,β2,…,βk = 1 from G down to the trivial subgroup. The strong generating set associated with B is a subset of G containing a generating set for each of these stabilisers.
The construction of a BSGS for a large group of high degree is a challenging task. Magma contains a number of different algorithms for this task. The usual strategy for a hard example is to apply the Random Schreier–Sims to get a probable BSGS and then verify its correctness using the Sims–Cannon–Brownie algorithm. This has been successfully applied to short base groups of degree up to 108.
Having a BSGS for a group G immediately gives the order of G and this suffices for some applications, such as completion of the proof of the Hall–Paige conjecture. The availability of a BSGS also provides an efficient method for testing membership of G. Having a BSGS for G allows a BSGS for any subgroup H of G to be constructed efficiently. These capabilities make efficient the computation of the normal closure of any subgroup H. This in turn enables various series, such as the derived series, to be computed efficiently.
Fundamental to the study of a permutation group G are various actions of the group on the support Ω itself as well as subsets and partitions of Ω. We first consider the action on Ω. Subgroups stabilising points and sequences of points of Ω are efficiently computed applying a technique known as base change to the group's BSGS. The next class of groups related to Ω are the stabilisers of subsets and partitions (both ordered and unordered). These are harder to compute and in most cases they have to found using a backtrack search.
Magma's functionality for determining the G-invariant subsets and partitions of Ω is highly optimised. The corresponding actions on orbits and block systems may be constructed, along with the corresponding homomorphisms onto quotients of G. These homomorphisms support calculation of the image and preimage of elements and subgroups. While these actions will seldom be faithful, these actions can be used to design algorithms which work by reducing the problem down to a primitive group. In the current version of Magma this approach is used to find the Sylow p-subgroup for any prime divisor p of |G|.
Many applications need the conjugacy classes of elements of a group G. For example, this information is needed when computing irreducible characters or representations. The central algorithm used is a lifting algorithm which reduces the problem to determining the conjugacy classes for each non-abelian composition factor of G. In the case of the classical groups, theory and code have been developed by E. O'Brien and D. Taylor for all types of classical groups. For the other types of simple group an inductive method devised by G. Butler is used. For soluble groups a lifting method is used and can be very efficient, particularly in the case of p-groups.
The BSGS makes it straightforward to compute the normal closure NH of a subgroup H of G. One simply initialises the subgroup NH to be equal to H and then forms its closure under the operation of conjugating its generators by those of G. Being able to compute normal closures makes it straightforward to compute the derived subgroup, the derived series, and lower central series of G.
Many advanced permutation group functions rely on constructing certain normal subgroups of the group and representations of the corresponding group quotients. These include methods by W. Unger (Magma) for computing the soluble radical of the group and the method of J. Cannon and D. Holt (Warwick) for computing the socle of a permutation group, which W. Unger has recently extended to degree 232. The socle is found using a divide-and-conquer method using natural homomorphisms which reduce down to a primitive group. The socle of a primitive group is then found by application of the O'Nan–Scott Theorem.
Other standard normal subgroup constructions available in Magma and based on normal closure are derived series, lower central series, p-cores, Fitting subgroup, and minimal normal subgroups. Magma can also name the composition factors and chief factors of a permutation group, and find corresponding normal and subnormal series in the group.
In this section we consider the construction of several important normal subgroups of G as well as series. The key subgroup is the socle (subgroup generated by all the minimal normal subgroups). This is found by a divide-and-conquer method using natural homomorphisms which reduce down to a primitive group. The socle of a primitive group is then found by application of the O'Nan–Scott Theorem. Once the socle is available it is straightforward to find the composition series, composition factors, chief series, and chief factors.
A normal subgroup that is important for algorithmic purposes is the solvable radical, the largest solvable normal subgroup. The algorithm used in Magma is due to W. Unger (Magma).
There are a number of subgroup (and conjugacy) functions which are are currently hard to compute. The more important include:
The non-existence of polynomial-time algorithms for the general case of some of these problems has been established. In the case of permutation groups, J. Cannon and G. Butler developed a large family of backtrack search algorithms for this type of problem. Recently the partition refinement method developed by J. Leon was slightly improved and implemented by W. Unger. While it is often quite fast it is not hard to find examples where the complexity of the search leads to slower runtimes than desired.
A key capability for the analysis of finite groups is the ability to determine the maximal subgroups of a group G. In 2004, J. Cannon and D. Holt described an algorithm which reduced the problem to that of determining the maximal subgroups of the composition factors of G. Algorithms were then devised which can quickly produce the maximal subgroups of those simple groups which can arise in practice.
A function devised by J. Cannon and D. Holt can construct the subgroups of a permutation group up to conjugacy. A simpler version efficiently computes the normal subgroups. Subgroups satisfying various restrictions such abelian, nilpotent, soluble, regular, having a specific order, etc., can be obtained using the subgroups function together with an appropriate filter. As an example, the 111,004 conjugacy classes of subgroups of the sporadic simple group F22 of order 64,561,751,654,400 are computed in 231,300 seconds.
The automorphism group of a finite group is normally computed using a lifting algorithm using a generalised elementary series. An algorithm due to J. Cannon and D. Holt is used for permutation groups. In the case of soluble groups, a version of the lifting algorithm developed by Michael Smith is used, while for p-groups an algorithm designed and implemented by E. O'Brien is employed. A new approach to computing the automorphism group of soluble groups has recently been developed by D. Howden. For each of the above automorphism group algorithms a slight variant has been produced which tests a pair of groups for isomorphism.