Subgroups#

Construction of a Subgroup#

sub<G | L>: GrpPerm, List -> GrpPerm#

Given the permutation group \(G\), construct the subgroup \(H\) of \(G\), generated by the elements specified by the list \(L\), where \(L\) is a list of one or more items of the following types:

(a): A sequence of \(n\) integers defining a permutation of \(G\);
(b): A set or sequence of sequences of type (a);
(c): An element of \(G\);
(d): A set or sequence of elements of \(G\);
(e): A subgroup of \(G\);
(f): A set or sequence of subgroups of \(G\).

Each element or group specified by the list must belong to the same generic permutation group. The subgroup \(H\) will be constructed as a subgroup of some group which contains each of the elements and groups specified in the list. The generators of \(H\) consist of the elements specified by the terms of the list \(L\) together with the stored generators for groups specified by terms of the list.

ncl<G | L>: GrpPerm, List -> GrpPerm#: Given the permutation group \(G\), construct the subgroup \(H\) of \(G\) that is the normal closure of the subgroup \(H\) generated by the elements specified by the list \(L\) (see [Butler and Cannon, 1982]), where the possibilities for \(L\) are the same as for the sub-constructor.

Example: Constructors (ex-dfcc0d)#

The group \({\operatorname{PGL}}(2, 7)\) in its natural action on projective points is generated by the set of permutations \(\{ (1,2,3,4,5,6,7), (2,4,3,7,5,6), (1,8)(2,7)(3,4)(5,6) \}\).

Using the above syntax, the group may be defined in any of the following ways: By means of a list of generating permutations written as products of cycles:

> PGL27 := sub< Sym(8) | (1,2,3,4,5,6,7), (2,4,3,7,5,6), (1,8)(2,7)(3,4)(5,6)>;
> PGL27;
Permutation group PGL27 acting on a set of cardinality 8
    (1, 2, 3, 4, 5, 6, 7)
    (2, 4, 3, 7, 5, 6)
    (1, 8)(2, 7)(3, 4)(5, 6)

Run in calculator

By means of a list of integer sequences representing generators:

> PGL27 := sub< Sym(8) |
>               [2,3,4,5,6,7,1,8], [1,4,7,3,6,2,5,8], [8,7,4,3,6,5,2,1] >;

Run in calculator

In terms of preassigned elements of the symmetric group of degree 8:

> S8 := Sym(8);
> a := S8!(1,2,3,4,5,6,7);
> b := S8!(2,4,3,7,5,6);
> c := S8!(1,8)(2,7)(3,4)(5,6);
> PGL27 := sub<S8 | a, b, c>;

Run in calculator

By means of a set of generators:

> S8 := Sym(8);
> gens := { S8 | (1,2,3,4,5,6,7), (2,4,3,7,5,6), (1,8)(2,7)(3,4)(5,6) };
> PGL27 := sub<S8 | gens>;

Run in calculator

By means of a sequence of generators:

> S8 := Sym(8);
> gens := [ S8 | (1,2,3,4,5,6,7), (2,4,3,7,5,6), (1,8)(2,7)(3,4)(5,6) ];
> PGL27 := sub<S8 | gens>;

Run in calculator

Example: Constructors 2 (ex-f29910)#

A representation \(H\) of a \(2\)-generator transitive group \(G\) in its action on unordered pairs is constructed as follows:

> G := AlternatingGroup(7);
> deg1 := Degree(G);
> pairs := [ { i, j } : j in [i+1..deg1], i in [1..deg1-1] ];
> deg2 := #pairs;
> h1 := [ Position(pairs, pairs[i] ^ G.1): i in [1..deg2] ];
> h2 := [ Position(pairs, pairs[i] ^ G.2): i in [1..deg2] ];
> H := sub<Sym(deg2) | h1, h2>;
> H;
Permutation group H acting on a set of cardinality 21
 (2,3,4,5,6)(7,8,9,10,11)(12,16,19,21,15)(13,17,20,14,18),
 (1,7,2)(3,8,12)(4,9,13)(5,10,14)(6,11,15)

Run in calculator

Example: Constructors 3 (ex-9bd7f8)#

We illustrate the ncl-constructor by using it to construct the derived subgroup of the Hessian group \(H\). We exploit the fact that the derived subgroup may be obtained as the normal closure of the subgroup generated by the commutators of the generators of \(H\).

> H := PermutationGroup< 9 | (1,2,4)(5,6,8)(3,9,7), (4,5,6)(7,9,8) >;
> Order(H);
216
> D := ncl< H | (H.1, H.2) >;
> D;
Permutation group D acting on a set of cardinality 9
Order = 72 = 2^3 * 3^2
    (1, 7, 3, 6)(4, 5, 9, 8)
    (2, 9, 3, 5)(4, 6, 7, 8)
    (2, 6, 3, 8)(4, 5, 7, 9)

Run in calculator

Membership and Equality#

g in G: GrpPermElt, GrpPerm -> BoolElt#: Given a permutation \(g\) and a permutation group \(G\), return true if \(g\) is an element of \(G\), false otherwise.

g notin G: GrpPermElt, GrpPerm -> BoolElt#: Given a permutation \(g\) and a permutation group \(G\), return true if \(g\) is not an element of \(G\), false otherwise.

S subset G: { GrpPermElt }, GrpPerm -> BoolElt#: Given a permutation group \(G\) and a set \(S\) of permutations belonging to a group \(H\), where \(G\) and \(H\) belong the same generic group, return true if \(S\) is a subset of \(G\), false otherwise.

S notsubset G: { GrpPermElt }, GrpPerm -> BoolElt#: Given a permutation group \(G\) and a set \(S\) of permutations belonging to a group \(H\), where \(G\) and \(H\) belong the same generic group, return true if \(S\) is not a subset of \(G\), false otherwise.

H subset G: GrpPerm, GrpPerm -> BoolElt#
IsSubgroup(H, G): GrpPerm, GrpPerm -> BoolElt#: Given permutation groups \(G\) and \(H\) belonging to the same generic group, return true if \(H\) is a subgroup of \(G\), false otherwise.

H notsubset G: GrpPerm, GrpPerm -> BoolElt#: Given permutation groups \(G\) and \(H\) belonging to the same generic group, return true if \(H\) is not a subgroup of \(G\), false otherwise.

H eq G: GrpPerm, GrpPerm -> BoolElt#: Given permutation groups \(G\) and \(H\) belonging to the same generic group, return true if \(G\) and \(H\) are the same group, false otherwise.

H ne G: GrpPerm, GrpPerm -> BoolElt#: Given permutation groups \(G\) and \(H\) belonging to the same generic group, return true if \(G\) and \(H\) are distinct groups, false otherwise.

Elementary Properties of a Subgroup#

Index(G, H): GrpPerm, GrpPerm -> RngIntElt#: The index of the subgroup \(H\) in the group \(G\). The index is returned as an integer. If the orders of \(G\) and \(H\) are not known, they will be computed.

FactoredIndex(G, H): GrpPerm, GrpPerm -> [ <RngIntElt, RngIntElt> ]#: The index of the subgroup \(H\) in the group \(G\). The index is returned as a factored integer. The format is the same as for FactoredOrder. If the orders of \(G\) and \(H\) are not known, they will be computed.

IsCentral(G, H): GrpPerm, GrpPerm -> BoolElt#: Returns true if the subgroup \(H\) of the group \(G\) lies in the centre of \(G\), false otherwise.

IsNormal(G, H): GrpPerm, GrpPerm -> BoolElt#: Returns true if the subgroup \(H\) of the group \(G\) is a normal subgroup of \(G\), false otherwise.

IsSelfNormalizing(G, H): GrpPerm, GrpPerm -> BoolElt#
IsSelfNormalising(G, H): GrpPerm, GrpPerm -> BoolElt#: Returns true if the subgroup \(H\) of the group \(G\) is self-normalizing in \(G\), false otherwise.

IsSubnormal(G, H): GrpPerm, GrpPerm -> BoolElt#: Returns true if the subgroup \(H\) of the group \(G\) is subnormal in \(G\), false otherwise.

Standard Subgroups#

Unless the order is already known, each of the functions in this family will create a base and strong generating set for the group if one does not already exist.

H ^ g: GrpPerm, GrpPermElt -> GrpPerm#
Conjugate(H, g): GrpPerm, GrpPermElt -> GrpPerm#: Construct the conjugate \(g^{-1}*H*g\) of the permutation group \(H\) by the permutation \(g\). The group \(H\) and the element \(g\) must belong to the same symmetric group.

H meet K: GrpPerm, GrpPerm -> GrpPerm#: Given groups \(H\) and \(K\) which belong to the same symmetric group, construct the intersection of \(H\) and \(K\). The intersection is found using the backtrack search of J. Leon [Leon, 1997].

IntersectionWithNormalSubgroup(G, N: parameters): GrpPerm, GrpPerm -> GrpPerm#

Check: BoolElt                    Default: true

Given groups \(G\) and \(N\) which belong to the same symmetric group and so that \(G\) normalises \(N\), construct the intersection of \(G\) and \(N\). The algorithm used is that of Cooperman, Finkelstein and Luks [Cooperman et al., 1989], which uses a permutation representation of double the degree of \(G\) and \(N\). Setting Check to false suppresses checking that \(G\) normalises \(N\).

CommutatorSubgroup(G, H, K): GrpPerm, GrpPerm, GrpPerm -> GrpPerm#
CommutatorSubgroup(H, K): GrpPerm, GrpPerm -> GrpPerm#: Given groups \(H\) and \(K\), both subgroups of the group \(G\), construct the commutator subgroup of \(H\) and \(K\) in the group \(G\). If \(K\) is a subgroup of \(H\), then the group \(G\) may be omitted. The algorithm used is described in [Butler and Cannon, 1982].

Centralizer(G, g: parameters): GrpPerm, GrpPermElt -> GrpPerm#

Centraliser(G, g: parameters): GrpPerm, GrpPermElt -> GrpPerm#

Subgroup: GrpPerm                    Default: 

Construct the centralizer of the permutation \(g\) in the group \(G\); \(g\) and \(G\) must belong to a common symmetric group. A backtrack search through \(G\) as described in [Leon, 1997] is employed.

The parameter Subgroup may be used to supply a known subgroup of the centralizer. This may speed the search.

Centralizer(G, H): GrpPerm, GrpPerm -> GrpPerm#
Centraliser(G, H): GrpPerm, GrpPerm -> GrpPerm#: Construct the centralizer of the group \(H\) in the group \(G\); \(G\) and \(H\) must belong to a common symmetric group. A backtrack search through \(G\) as described in [Leon, 1997] is employed.

CentralizerOfNormalSubgroup(G, H): GrpPerm, GrpPerm -> GrpPerm#: Given \(G\) and \(H\), belonging to a common symmetric group, with the restriction that \(H\) is a normal subgroup of \(G\), construct the centralizer of \(H\) in \(G\). A polynomial-time reduction algorithm described in Beals [Beals, 1993] is used.

SectionCentraliser(G, H, K): GrpPerm, GrpPerm, GrpPerm -> GrpPerm#
SectionCentralizer(G, H, K): GrpPerm, GrpPerm, GrpPerm -> GrpPerm#: Return the full preimage in \(G\) of the centralizer in \(G/K\) of \(H/K\). The groups \(H\) and \(K\) must be normal subgroups of \(G\) with \(K\) contained in \(H\). An algorithm of Luks [Luks, 1993] is employed which involves computing the core of a subgroup in a group having twice the degree of \(G\).

Core(G, H): GrpPerm, GrpPerm -> GrpPerm#: Given a subgroup \(H\) of the permutation group \(G\), construct the maximal normal subgroup of \(G\) that is contained in the subgroup \(H\). The algorithm employs repeated conjugation and intersection using the backtrack search of Leon [Leon, 1997].

H ^ G: GrpPerm, GrpPerm -> GrpPerm#
NormalClosure(G, H): GrpPerm, GrpPerm -> GrpPerm#: Given a subgroup \(H\) of the permutation group \(G\), construct the normal closure of \(H\) in \(G\).

Normalizer(G, H: parameters): GrpPerm, GrpPerm -> GrpPerm#

Normaliser(G, H: parameters): GrpPerm, GrpPerm -> GrpPerm#

Subgroup: GrpPerm                      Default: H
Bound   : RngIntElt                    Default: 

Given a subgroup \(H\) of the group \(G\), construct the normalizer of \(H\) in \(G\). A backtrack search as described in Leon [Leon, 1997] is employed.

The parameter Subgroup may be used to pass the search a known subgroup of the normalizer. The default value of the starting subgroup is \(H\). If Bound is set, the search will be terminated once the normalizing group found has order at least equal to Bound. If this does not happen, the search will complete as normal.

SymmetricNormalizer(G): GrpPerm -> GrpPerm#

SymmetricNormaliser(G): GrpPerm -> GrpPerm#

Subgroup: GrpPerm                      Default: H
Bound   : RngIntElt                    Default: 

Given a permutation group \(G\) acting on the set \(X\), return the normalizer of \(G\) in the symmetric group on \(X\). The parameters are as for Normalizer above.

SylowSubgroup(G, p): GrpPerm, RngIntElt -> GrpPerm#
Sylow(G, p): GrpPerm, RngIntElt -> GrpPerm#: Given a group \(G\) and a prime \(p\), construct a Sylow \(p\)-subgroup of \(G\). The algorithm used is that of Cannon, Cox and Holt [Cannon et al., 1997].

Example: Subgroup Constructions (ex-ea0914)#

We illustrate the use of these functions by applying them to a group of degree \(30\).

> M := PermutationGroup< 30 |
>         (1,2,3)(4,14,8)(5,15,9)(6,13,7)(25,27,26),
>         (4,20,13)(5,21,14)(6,19,15)(16,17,18)(27,28,29),
>         (1, 15)(2, 13)(3, 14)(4, 22)(5, 23)(6, 24)(7, 18)(8, 16)
>           (9, 17)(10, 21)(11, 19)(12, 20)(25, 29)(26, 27)(28, 30) >;
> FactoredOrder(M);
[ <2, 8>, <3, 10>, <5, 1> ]
> S2 := SylowSubgroup(M, 2);
> S2;
Permutation group S2 acting on a set of cardinality 30
Order = 256 = 2^8
    (1, 10)(2, 11)(3, 12)(4, 8)(5, 9)(6, 7)(13, 19)(14, 20)(15, 21)
        (16, 22)(17, 23)(18, 24)
    (1, 24)(2, 22)(3, 23)(4, 14)(5, 15)(6, 13)(7, 19)(8, 20)(9, 21)
        (10, 18)(11, 16)(12, 17)
    (4, 8)(5, 9)(6, 7)(13, 19)(14, 20)(15, 21)
    (4, 14)(5, 15)(6, 13)(7, 19)(8, 20)(9, 21)(25, 26)(29, 30)
    (1, 4)(2, 5)(3, 6)(7, 12)(8, 10)(9, 11)(13, 23)(14, 24)(15, 22)
        (16, 21)(17, 19)(18, 20)(25, 26)
    (27, 28)(29, 30)
    (27, 29)(28, 30)
    (25, 26)(29, 30)

Run in calculator

We try to find a second Sylow subgroup \(S2a\) that has trivial intersection with \(S2\).

> b := exists(t){ x : x in M | Order(S2 meet S2^x) eq 1 };
> b;
true
> S2a := S2^t;
> N := Normalizer(M, S2);
> N;
Permutation group N acting on a set of cardinality 30
Order = 768 = 2^8 * 3
    (4, 8)(5, 9)(6, 7)(13, 19)(14, 20)(15, 21)
    (4, 14)(5, 15)(6, 13)(7, 19)(8, 20)(9, 21)
    (1, 10)(2, 11)(3, 12)(4, 8)(5, 9)(6, 7)(13, 19)(14, 20)(15, 21)
        (16, 22)(17, 23)(18, 24)
    (1, 24)(2, 22)(3, 23)(4, 14)(5, 15)(6, 13)(7, 19)(8, 20)(9, 21)
        (10, 18)(11, 16)(12, 17)
    (1, 22, 12)(2, 23, 10)(3, 24, 11)(4, 21, 13)(5, 19, 14)(6, 20, 15)
        (7, 8, 9)(16, 17, 18)
    (27, 29)(28, 30)
    (1, 14, 24, 4)(2, 15, 22, 5)(3, 13, 23, 6)(7, 12, 19, 17)(8, 10, 20, 18)
        (9, 11, 21, 16)(29, 30)
    (4, 14)(5, 15)(6, 13)(7, 19)(8, 20)(9, 21)(25, 26)(29, 30)
    (27, 28)(29, 30)

Run in calculator

Thus the Sylow 2-subgroup is normalized by an element of order 3.

Maximal Subgroups#

IsMaximal(G, H: parameters): GrpPerm, GrpPerm -> BoolElt#

Al: MonStgElt                    Default: "Subgroups"

Returns true if the subgroup \(H\) of the group \(G\) is a maximal subgroup of \(G\). The algorithm used depends on the value of the parameter Al. The default value Subgroups computes the maximal subgroups of \(G\) if the index of \(H\) in \(G\) is over 1000 and the maximal subgroups are computable.The subgroup \(H\) is then tested for conjugacy with each class found. In the other cases, or when the Al parameter is set to CosetImage, the function is evaluated by first calling IsProbablyMaximal and if that returns true then constructing the permutation representation of \(G\) on the cosets of \(H\) and testing this representation for primitivity.

IsProbablyMaximal(G, H: parameters): GrpPerm, GrpPerm -> BoolElt#

Tries: RngIntElt                    Default: 20

Given a group \(G\) and a subgroup \(H\) of \(G\), this function performs a probabilistic test for the maximality of \(H\) in \(G\). The test involves adjoining random elements of \(G\) to \(H\) and determining if the result \(G\). If not, then false is returned, otherwise true s returned. The number of random elements used is controlled by the parameter Tries, which is set to \(20\) by default.

MaximalSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of maximal subgroup classes of \(G\). This is equivalent to the command Subgroups(G: Al := "Maximal"). The same parameters as for Subgroups are available to limit the search. The algorithm is described in [Cannon and Holt, 2004].

Example: Maximals (ex-aa3565)#

The Subgroups family of commands can deal with fairly large groups. We look at the maximal subgroups of the group of the \(4\times4\times4\) Rubik’s cube. This group has order about \(1.7\times10^{55}\).

> load rubik444;
Loading "/home/magma/libs/pergps/rubik444"
The automorphism group of the 4 x 4 x 4 Rubik cube.
The group is represented as a permutation group of degree 72.
Its order is
2^50 * 3^29 * 5^9 * 7^7 * 11^4 * 13^2 * 17^2 * 19^2 * 23^2.
Group: G
> time max := MaximalSubgroups(G);
Time: 100.559
> #max;
46
> [Index(G, x`subgroup) : x in max];
[ 51090942171709440000, 51090942171709440000, 9161680528000,
9161680528000, 4509264634875, 4509264634875, 316234143225,
316234143225, 96197645544, 96197645544, 1577585295,
1577585295, 2496144, 2496144, 1961256, 1961256, 1307504,
1307504, 346104, 346104, 42504, 42504, 2187, 1352078,
1352078, 735471, 735471, 134596, 134596, 10626, 10626, 2024,
2024, 120, 276, 276, 56, 24, 24, 105, 28, 8, 35, 2, 2, 2 ]

Run in calculator

MaximalSubgroups(G, N: parameters): GrpPerm, GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of maximal subgroup classes of \(G\) that contain the normal subgroup \(N\) of \(G\). So this is equivalent to computing the maximal subgroups of \(G\) that contain \(N\). Warning: Some parameters may have no effect.

Conjugacy Classes of Subgroups#

SubgroupClasses(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#

Subgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#

Al                 : MonStgElt                    Default: "All"
LayerSizes         : SeqEnum                      Default: See below
Series             : SeqEnum                      Default: See below
Presentation       : BoolElt                      Default: false
OrderEqual         : RngIntElt                    Default: 
OrderDividing      : RngIntElt                    Default: 
OrderMultipleOf    : RngIntElt                    Default: 
IndexLimit         : RngIntElt                    Default: 
IsElementaryAbelian: BoolElt                      Default: false
IsCyclic           : BoolElt                      Default: false
IsAbelian          : BoolElt                      Default: false
IsNilpotent        : BoolElt                      Default: false
IsSolvable         : BoolElt                      Default: false
IsNotSolvable      : BoolElt                      Default: false
IsPerfect          : BoolElt                      Default: false
IsRegular          : BoolElt                      Default: false
IsTransitive       : BoolElt                      Default: false

Representatives for the conjugacy classes of subgroups for the group \(G\). The subgroups are returned as a sequence of records where the \(i\)-th record contains:

(a): A representative subgroup \(H\) for the \(i\)-th conjugacy class (field name subgroup).
(b): The order of the subgroup (field name order).
(c): The number of subgroups in the class (field name length).
(d): [Optional] A presentation for \(H\) (field name presentation).

Al := "All": Construct all subgroups of \(G\).

Al := "Maximal": Only construct maximal subgroups of \(G\). This option reduces the number of intersections with any elementary abelian layer that need be considered and eliminates the need to recursively apply the algorithm.

Al := "Normal": Only construct normal subgroups of \(G\). This option does not use database lookup to find the normal subgroups of the radical quotient of \(G\) and also reduces the number of intersections with any layer that need be considered.

LayerSizes := [ 2, 5, 3, 4, 7, 3, 11, 2, 17, 1] is equivalent to the default. When constructing an Elementary Abelian series for the group, attempt to split 2-layers of size gt \(2^5\), 3-layers of size gt \(3^4\), etc. The implied exponent for 13 is 2 and for all primes greater than 17 the exponent is 1.

Use the given elementary abelian series rather than constructing the default series. The first subgroup in the series must be the solvable radical of \(G\). The subgroups must form a descending chain of normal subgroups of \(G\), such that each quotient is elementary abelian. The last subgroup in the series must be either elementary abelian or trivial.

Presentation := true: Construct a presentation for each subgroup.

OrderEqual := n: Only construct subgroups having order equal to \(n\).

OrderDividing := n: Only construct subgroups having order dividing \(n\).

OrderMultipleOf := n: Only construct subgroups having order a multiple of \(n\).

IndexLimit := n: Only construct subgroups having index in \(G\) less than or equal to \(n\).

IsElementaryAbelian := true: Only construct elementary abelian subgroups of \(G\).

IsCyclic := true: Only construct cyclic subgroups of \(G\).

IsAbelian := true: Only construct abelian subgroups of \(G\).

IsNilpotent := true: Only construct nilpotent subgroups of \(G\).

IsSolvable := true: Only construct solvable subgroups of \(G\).

IsNotSolvable := true: Only construct insolvable subgroups of \(G\).

IsPerfect := true: Only construct perfect subgroups of \(G\).

IsRegular := true: Only construct regular subgroups of \(G\).

IsTransitive := true: Only construct transitive subgroups of \(G\).

The Algorithm: (See Cannon, Cox and Holt [Cannon et al., 2001]) This command proceeds by first constructing an elementary abelian series for \(G\) together with \(G\)’s radical quotient \(Q\). We first attempt to locate the quotient in a database of groups with trivial Fitting subgroup. This database contains all such groups of order up to \(216\,000\), and all such which are perfect of order up to \(1\,000\,000\). If \(Q\) is found then either all its subgroups, or its maximal subgroups are read from the database. (In some cases only the maximal subgroups are stored.) If \(Q\) is not found then we attempt to find the maximal subgroups of \(Q\) using a method of Derek Holt. For this to succeed all simple factors of the socle of \(Q\) must be found in a second database which currently contains all simple groups of order less than \(1.6 \times 10^7\), as well as \(M_{24}\), \(HS\), \(J_3\), \(McL\), \(Sz(32)\) and \(L_6(2)\). There are also special routines to handle numerous other groups. These include: \(A_n\) for \(n \le 2499\), \(L_2(q)\), \(L_3(q)\), \(L_4(q)\), \(L_5(q)\), \(L_6(q)\) and \(L_7(q)\) for all \(q\), \(U_3(q)\) for all \(q\), \(U_4(q)\) for all \(q\), \(S_4(q)\) for all \(q\), \(L_d(2)\) for \(d \le 14\), and the following groups: \(L_8(3)\), \(L_9(3)\), \(U_5(3)\), \(U_5(4)\), \(U_6(2)\), \(U_6(3)\), \(U_7(2)\), \(U_8(2)\), \(S_6(3)\), \(S_6(4)\), \(S_6(5)\), \(S_8(2)\), \(S_8(3)\), \(S_{10}(2)\), \(S_{12}(2)\), \(S_{14}(2)\), \(O^\pm_8(2)\), \(O^\pm_8(4)\), \(O^\pm_{10}(2)\), \(O^\pm_{12}(2)\), \(O^\pm_{14}(2)\), \(O^\pm_8(3)\), \(O^\pm_{10}(3)\), \(O_7(3)\), \(O_7(5)\), \(O_9(3)\), \(G_2(4)\), \(G_2(5)\), \({}^3D_4(2)\), \({}^2F_4(2)'\), \(F_2(4)\), \(R(27\), \(Co_2\), \(Co_3\), \(He\), \(Fi_{22}\), \(Fi_{23}\), \(Ru\), \(Suz\), \(ON\), \(HN\).

If we have only maximal subgroups of \(Q\), and more are required, we apply the algorithm recursively to the maximal subgroups to determine all subgroups of \(Q\). This may take some time.

The subgroups are then extended to the whole group by stepwise extension through each layer of the elementary abelian series. For each layer this involves determining all possible intersections of a subgroup with this layer and all extensions with this intersection.

The limitations are that the simple factors of the socle of \(Q\) must be in the database, which is limited as above. Further, it may take some time to construct all subgroups from the maximal subgroups first found, and, if there is a large elementary abelian layer, there will be many possible intersections, which could also make the algorithm prohibitively slow.

There are numerous parameters for this function which allow the user to place restrictions on which subgroup classes are constructed. Using these restrictions may help overcome the problems noted above.

SubgroupsLift(G, A, B, Q: parameters): GrpPerm, GrpPerm, GrpPerm, SeqEnum -> SeqEnum#: This function isolates one step of the extension process used by the Subgroups family of functions. The argument \(Q\) is a sequence of records such as returned by Subgroups(G). The groups \(A\) and \(B\) are normal subgroups of \(G\) with \(A/B\) elementary abelian. The records in \(Q\) are interpreted as subgroups of \(G/A\), which are lifted to all possible corresponding subgroups of \(G/B\), subject to the parameters given.

LowIndexSubgroups(G, n: parameters): GrpPerm, RngIntElt -> SeqEnum#
LowIndexSubgroups(G, t: parameters): GrpPerm, Tup -> SeqEnum#: Returns a sequence of subgroups of \(G\), each with index at most \(n\). The sequence will contain one representative from each conjugacy class of \(G\)-subgroups satisfying the index constraint. The algorithm used is described in Cannon, Holt, Slattery & Steel [Cannon et al., 2003]. The previous version of the algorithm is available by setting the parameter Algorithm to the string "Subgroups". In this case the group \(G\) is subject to the same restrictions as the group input to the Subgroups function above. In the second form \(t\) should be a pair of integers \(\langle a,b\rangle\), and subgroups with index in the interval \([a,b]\) will be returned. Other parameters are Presentation which may be set true to return a second sequence of presentations of the groups found, and Print which may be set to a positive integer to turn on diagnostic printing of the progress of the algorithms.

LowIndexSubgroups(G, N, n: parameters): GrpPerm, RngIntElt -> SeqEnum#
LowIndexSubgroups(G, N, t: parameters): GrpPerm, Tup -> SeqEnum#: Same as above, but only those subgroups containing the normal subgroup \(N\) of \(G\) are returned. This is equivalent to computing the low index subgroups of \(G/N\). Only the Print parameter is available for this command.

Example: Subgroups (ex-24cf2d)#

With the Subgroups family of commands we can get the entire collection of (classes of) subgroups of a group \(G\). We look at the double cover of \(M_{12}\).

> load m12cover;
Loading "/home/magma/libs/pergps/m12cover"
The two-fold cover of the Mathieu group M12 on 24 letters.
Order is 190080 = 2^7 * 3^3 * 5 * 11.
Group: G
> time s := SubgroupClasses(G);
Time: 4.469
> #s;
293

Run in calculator

This may be too many. The parameters allow us to restrict attention to a subset of the subgroups. We specify that the function is to return only the elementary abelian \(2\)-subgroups of \(G\).

> se := SubgroupClasses(G : IsElementaryAbelian := true,
>               OrderMultipleOf := 2);
> #se;
14
> se : Minimal;
Conjugacy classes of subgroups
------------------------------

[ 1]    Order 2            Length 1
        GrpPerm: $, Degree 24, Order 2
[ 2]    Order 2            Length 495
        GrpPerm: $, Degree 24, Order 2
[ 3]    Order 2            Length 495
        GrpPerm: $, Degree 24, Order 2
[ 4]    Order 4            Length 495
        GrpPerm: $, Degree 24, Order 2^2
[ 5]    Order 4            Length 495
        GrpPerm: $, Degree 24, Order 2^2
[ 6]    Order 4            Length 1485
        GrpPerm: $, Degree 24, Order 2^2
[ 7]    Order 4            Length 1980
        GrpPerm: $, Degree 24, Order 2^2
[ 8]    Order 4            Length 5940
        GrpPerm: $, Degree 24, Order 2^2
[ 9]    Order 8            Length 495
        GrpPerm: $, Degree 24, Order 2^3
[10]    Order 8            Length 495
        GrpPerm: $, Degree 24, Order 2^3
[11]    Order 8            Length 1485
        GrpPerm: $, Degree 24, Order 2^3
[12]    Order 8            Length 1980
        GrpPerm: $, Degree 24, Order 2^3
[13]    Order 8            Length 1980
        GrpPerm: $, Degree 24, Order 2^3
[14]    Order 16           Length 495
        GrpPerm: $, Degree 24, Order 2^4

Run in calculator

Example: Low Index Subs (ex-157d91)#

Other options when restricting computation of the subgroups of a group are to find low index subgroups or maximal subgroups.

> G := TransitiveGroup(33,31);
> lix :=  LowIndexSubgroups(G, <2,47>);
> [Index(G, H) : H in lix];
[ 3, 4, 6, 12, 33, 44 ];
> m := MaximalSubgroups(G);
> [Index(G, r`subgroup) : r in m];
[ 1331, 4, 3 ]
> #Subgroups(G);
60

Run in calculator

Example: Subgroups 2 (ex-672b95)#

Using the SubgroupLattice function we obtain a representative subgroup for each conjugacy class together with the inclusion relations between subgroups.

WARNING: Computing the inclusions is very time consuming and should only be performed for small groups.

> G := PSL(2,9);
> time L := SubgroupLattice(G);
Time: 0.20O
> L;
Partially ordered set of subgroup classes
-----------------------------------------

[ 1]  Order 1    Length 1   Maximal Subgroups:
---
[ 2]  Order 2    Length 45  Maximal Subgroups: 1
[ 3]  Order 3    Length 20  Maximal Subgroups: 1
[ 4]  Order 3    Length 20  Maximal Subgroups: 1
[ 5]  Order 5    Length 36  Maximal Subgroups: 1
---
[ 6]  Order 4    Length 15  Maximal Subgroups: 2
[ 7]  Order 4    Length 15  Maximal Subgroups: 2
[ 8]  Order 4    Length 45  Maximal Subgroups: 2
[ 9]  Order 6    Length 60  Maximal Subgroups: 2 3
[10]  Order 6    Length 60  Maximal Subgroups: 2 4
[11]  Order 9    Length 10  Maximal Subgroups: 3 4
[12]  Order 10   Length 36  Maximal Subgroups: 2 5
---
[13]  Order 8    Length 45  Maximal Subgroups: 6 7 8
[14]  Order 12   Length 15  Maximal Subgroups: 4 6
[15]  Order 12   Length 15  Maximal Subgroups: 3 7
[16]  Order 18   Length 10  Maximal Subgroups: 9 10 11
---
[17]  Order 24   Length 15  Maximal Subgroups: 10 13 14
[18]  Order 24   Length 15  Maximal Subgroups: 9 13 15
[19]  Order 36   Length 10  Maximal Subgroups: 8 16
[20]  Order 60   Length 6   Maximal Subgroups: 9 12 15
[21]  Order 60   Length 6   Maximal Subgroups: 10 12 14
---
[22]  Order 360  Length 1   Maximal Subgroups: 17 18 19 20 21

> NumberOfInclusions(L!5, L!20);
6
> L[5];
Permutation group acting on a set of cardinality 10
Order = 5
  (1, 8, 9, 3, 4)(2, 7, 5, 10, 6)

Run in calculator

The order and class length of each class of subgroups is listed, along with the information about where to find the maximal subgroups of a member of this class. Further information about inclusions is available from the lattice. We see that 6 members of class 5 are contained in any fixed member of class 20.

SubgroupLattice(G): GrpPerm -> SubGrpLat#: The lattice of conjugacy classes of subgroups of \(G\).

BurnsideMatrix(G): GrpPerm -> AlgMatElt#: The Burnside matrix corresponding to the lattice of subgroups of \(G\). The \((i,j)\)th entry of the matrix is the number of subgroups in class \(i\) contained in a single subgroup of class \(j\) when \(i\le j\), and is the number of subgroups of class \(i\) containing a given subgroup in class \(j\) when \(i\ge j\).

DisplayBurnsideMatrix(G): GrpPerm#: Pretty-print the Burnside matrix corresponding to the lattice of subgroups of \(G\).

TableOfMarks(G): GrpPerm -> AlgMatElt#: Burnside’s table of marks corresponding to the lattice of subgroups of \(G\). Rows correspond to marks for transitive permutation representations of \(G\), while the entries in column \(j\) are the number of fixed points of subgroup class \(j\) in each transitive representation.

Classes of Subgroups Satisfying a Condition#

NormalSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of normal subgroup classes of \(G\). This is equivalent to Subgroups(G: Al := "Normal"). The same parameters as for Subgroups are available to limit the search.

ElementaryAbelianSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of elementary abelian subgroups of \(G\). This is equivalent to Subgroups(G: IsElementaryAbelian := true). The same parameters as for Subgroups are available to limit the search.

CyclicSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of cyclic subgroups of \(G\). This is equivalent to Subgroups(G: IsCyclic := true). The same parameters as for Subgroups are available to limit the search.

AbelianSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of abelian subgroups of \(G\). Equivalent to Subgroups(G: IsAbelian := true). The same parameters as for Subgroups are available to limit the search.

NilpotentSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of nilpotent subgroups of \(G\). This is equivalent to Subgroups(G: IsNilpotent := true). The same parameters as for Subgroups are available to limit the search.

SolvableSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of solvable subgroups of \(G\). This is equivalent to Subgroups(G: IsSolvable := true). The same parameters as for Subgroups are available to limit the search.

PerfectSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of perfect subgroups of \(G\). Equivalent to Subgroups(G: IsNotSolvable := true). The same parameters as for Subgroups are available to limit the search.

NonsolvableSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of insolvable subgroups of \(G\). This is equivalent to Subgroups(G: IsNotSolvable := true). The same parameters as for Subgroups are available to limit the search.

SimpleSubgroups(G: parameters): GrpPerm -> [ rec< GrpPerm, RngIntElt, RngIntElt, GrpFP> ]#: Construct the sequence of non-abelian simple subgroup classes of \(G\). This is equivalent to Subgroups(G: Al := "Simple"). The same parameters as for Subgroups are available to limit the search.