# Subgroups ## Construction of Subgroups ### `sub: GrpMat, List -> GrpMat` Given the matrix 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 matrix 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 matrix 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. Repetitions of an element and occurrences of the identity element are removed. ### `ncl: GrpMat, List -> GrpMat` Given the matrix 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$, where the possibilities for $L$ are the same as for the `sub`-constructor. ### `Example: Subgroups (ex-494271)` We define $O^{-}(4,2)$ as a subgroup of ${\operatorname{GL}}(4, 2)$. Recall that $O^{-}(4,2)$ is isomorphic to $S_5$. We then locate a subset of its generators that lie within the subgroup isomorphic to $A_5$. ```magma > GL42 := GeneralLinearGroup(4, GF(2)); > Ominus42 := sub< GL42 | [1,0,0,0, 1,1,0,1, 1,0,1,0, 0,0,0,1 ], > [0,1,0,0, 1,0,0,0, 0,0,1,0, 0,0,0,1 ], > [0,1,0,0, 1,0,0,0, 0,0,1,0, 0,0,1,1 ] >; > Order(Ominus42); 120 > H := sub< Ominus42 | $.1, $.3 >; print Order(H); 10 > N := ncl< Ominus42 | $.1, $.3 >; > Order(N); 60 ``` ## Elementary Properties of Subgroups ### `Index(G, H): GrpMat, GrpMat -> 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): GrpMat, GrpMat -> [ ]` The index of the subgroup $H$ in the group $G$. The index is returned as a factored integer. The factorization is returned in the form of a sequence $Q$ which is defined as follows: If $[ G : H ] = p_1^{e_1}\ldots p_n^{e_n}, \quad e_i \neq 0$, then $Q$ will be the integer sequence $[ , \ldots, ]$. If the orders of $G$ and $H$ are not known, they will be computed. ### `IsCentral(G, H): GrpMat, GrpMat -> BoolElt` Returns `true` if the subgroup $H$ of the group $G$ lies in the centre of $G$, `false` otherwise. ### `IsMaximal(G, H): GrpMat, GrpMat -> BoolElt` Returns `true` if the subgroup $H$ of the group $G$ is a maximal subgroup of $G$. This function is evaluated by constructing the permutation representation of $G$ on the cosets of $H$ and testing this representation for primitivity. For this reason, the use of `IsMaximal` should be avoided if the index of $H$ in $G$ exceeds a few thousand. ### `IsNormal(G, H): GrpMat, GrpMat -> BoolElt` Returns `true` if the subgroup $H$ of the group $G$ is a normal subgroup of $G$, `false` otherwise. ### `IsSubnormal(G, H): GrpMat, GrpMat -> BoolElt` Returns `true` if the subgroup $H$ of the group $G$ is subnormal in $G$, `false` otherwise. ## Standard Subgroups ### `H ^ g: GrpMat, GrpMatElt -> GrpMat` ### `Conjugate(H, g): GrpMat, GrpMatElt -> GrpMat` Construct the conjugate $g^{-1}*H*g$ of the matrix group $H$ by the matrix $g$. The group $H$ and the element $g$ must belong to a common matrix group. ### `H meet K: GrpMat, GrpMat -> GrpMat` Given groups $H$ and $K$ which belong to the same matrix group, construct the intersection of $H$ and $K$. ### `CommutatorSubgroup(G, H, K): GrpMat, GrpMat, GrpMat -> GrpMat` ### `CommutatorSubgroup(H, K): GrpMat, GrpMat -> GrpMat` Given subgroups $H$ and $K$ of the group $G$, construct the commutator subgroup of $H$ and $K$ as a subgroup of $G$. If $K$ is a subgroup of $H$, then $G$ may be omitted. ### `Centraliser(G, g): GrpMat, GrpMatElt -> GrpMat` ### `Centralizer(G, g): GrpMat, GrpMatElt -> GrpMat` Construct the centralizer of the matrix $g$ in the group $G$; $g$ and $G$ must belong to a common matrix group. ### `Centraliser(G, H): GrpMat, GrpMat -> GrpMat` ### `Centralizer(G, H): GrpMat, GrpMat -> GrpMat` Construct the centralizer of the group $H$ in the group $G$; $G$ and $H$ must belong to a common matrix group. ### `Core(G, H): GrpMat, GrpMat -> GrpMat` Given a subgroup $H$ of the matrix group $G$, construct the maximal normal subgroup of $G$ that is contained in the subgroup $H$. ### `H ^ G: GrpMat, GrpMat -> GrpMat` ### `NormalClosure(G, H): GrpMat, GrpMat -> GrpMat` Given a subgroup $H$ of the matrix group $G$, construct the normal closure of $H$ in $G$. ### `Normalizer(G, H): GrpMat, GrpMat -> GrpMat` Given a subgroup $H$ of the group $G$, construct the normalizer of $H$ in $G$. ### `GLNormalizer(H : parameter): GrpMat -> GrpMat` ```magma Print : RngIntElt Default: 0 OverGroup: RngIntElt Default: 0 ``` Given $H \leq GL_n(q)$, return the normalizer of $H$ in $GL_n(q)$. The algorithm is described in Coutts [[Coutts, 2011](../../references.md#cite-coutts-phd)]. It exploits Aschbacher’s description of the maximal subgroups of a classical group to obtain an overgroup $M$ of the normaliser $N$ and, where necessary, then applies `LMGNormaliser` $(M, H)$ to construct $N$. If the optional argument `OverGroup` is `true`, then return $M$, so skipping the last step. The optional argument `Print` takes values between 0 and 2, and determines the amount of information printed. ### `SylowSubgroup(G, p): GrpMat, RngIntElt -> GrpMat` ### `Sylow(G, p): GrpMat, RngIntElt -> GrpMat` Given a group $G$ and a prime $p$, construct the Sylow $p$-subgroup of $G$. ### `pCore(G, p): GrpMat, RngIntElt -> GrpMat` Given a group $G$ and a prime $p$ dividing the order of $G$, construct the maximal normal $p$-subgroup of $G$. ## Low Index Subgroups ### `LowIndexSubgroups(G, n: parameters): GrpMat, RngIntElt -> SeqEnum` ### `LowIndexSubgroups(G, t: parameters): GrpMat, 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](../../references.md#cite-chss-lix)]. 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): GrpMat, RngIntElt -> SeqEnum` ### `LowIndexSubgroups(G, N, t: parameters): GrpMat, 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. ### `LowIndexSubgroupsCT(G, R : parameters): GrpMat, RngIntElt -> [ GrpMat ]` ### `LowIndexSubgroupsCT(G, R: parameters): GrpMat, -> [ GrpMat ]` ```magma Limit: RngIntElt Default: Infinity() Print: RngIntElt Default: 0 ``` Given a matrix group $G$, and an expression $R$ defining a positive integer range (see below), determine the conjugacy classes of subgroups of $G$ whose indices lie in the range specified by $R$. The subgroups are returned as a sequence of subgroups of $G$. The argument $R$ is one of the following: **(a)** An integer $n$ representing the range $[1, n]$; **(b)** A tuple $$ representing the range $[a, b]$. This is an alternative method for computing low index subgroups that uses an algorithm due to Leedham-Green & O’Brien [[Leedham-Green and O'Brien, 2002](../../references.md#cite-crlg-eaob)]. In practice, the algorithm is most useful for small values of $n$, say up to 8. The algorithm proceeds by iteratively constructing better approximations to finite presentations for $G/K$, where $K$ is the intersection of kernels of all homomorphisms from $G$ into $S_n$, and applying `LowIndexSubgroups` to the resulting finitely-presented group. The output information displayed for various values of the `Print` parameter about the number and existence of putative subgroups of index at most $n$ refers to the current finite presentation only, may change as this presentation is further refined, and need not be reflected in the final answer. Terminate after finding $n$ conjugacy classes of subgroups satisfying the designated conditions. The `Print` parameter takes values from 0 to 3. ### `Example: Low Index Matrix Group (ex-39331d)` ```magma > G := GL (4, 5); > L := LowIndexSubgroups (G, 4); > #L; 3 > L[3]; MatrixGroup(4, GF(5)) Generators: [4 0 0 4] [1 0 0 0] [0 4 0 0] [0 0 4 0] [4 0 0 3] [3 0 0 0] [0 4 0 0] [0 0 4 0] [4 0 0 1] [4 0 0 0] [0 4 0 0] [0 0 4 0] [4 0 0 2] [2 0 0 0] [0 4 0 0] [0 0 4 0] ``` ## Conjugacy Classes of Subgroups ### `SubgroupClasses(G: parameters): GrpMat -> [ rec< GrpMat, RngIntElt, RngIntElt, GrpFP> ]` ### `Subgroups(G: parameters): GrpMat -> [ rec< GrpMat, RngIntElt, RngIntElt, GrpFP> ]` ```magma 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 ``` 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$. **The Algorithm:** (See Cannon, Cox and Holt [[Cannon *et al.*, 2001](../../references.md#cite-subgroups-permg)]) This command proceeds by first constructing an elementary abelian series for $G$ together with $G$’s radical quotient $Q$ as a permutation group. (Thus this function is limited to matrix groups over fields, where the group has a BSGS.) The required subgroups of $Q$ are then found as for permutation groups. 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 999$, $L_2(q)$, $L_3(q)$, $L_4(q)$ and $L_5(q)$ for all $q$, $U_3(q)$ for $q$ prime and $q=8,9,16,25$, $U_4(q)$ for $q=4,5,7$, $S_4(q)$ for all odd $q$ and even $q\le 16$, $L_d(2)$ for $d \le 14$, and the following groups: $L_6(3)$, $L_7(3)$, $U_6(2)$, $S_8(2)$, $S_{10}(2)$, $O^\pm_8(2)$, $O^\pm_{10}(2)$, $S_6(3)$, $O_7(3)$, $O^-_8(3)$, $G_2(4)$, $G_2(5)$, ${}^3D_4(2)$, ${}^2F_4(2)'$, $Co_2$, $Co_3$, $He$, $Fi_{22}$. 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 of $Q$ are then pulled back to $G$ and 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 list 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. ### `MaximalSubgroups(G: parameters): GrpMat -> [ rec< GrpMat, RngIntElt, RngIntElt, GrpFP> ]` Construct the sequence of maximal subgroup classes of the matrix group $G$. This is equivalent to the command `Subgroups(G: Al := "Maximal")`. The same parameters as for `Subgroups` are available to limit the search. ### `MaximalSubgroups(G, N: parameters): GrpMat, GrpMat -> [ rec< GrpMat, 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. ### `SubgroupsLift(G, A, B, Q: parameters): GrpMat, GrpMat, GrpMat, SeqEnum -> SeqEnum` This function isolates one step of the extension process used by the `Subgroups` family of functions. $Q$ is a sequence of records such as returned by `Subgroups(G)`. $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. ### `IsConjugate(G, H, K): GrpMat, GrpMat, GrpMat -> BoolElt, GrpMatElt | Unass` Given a group $G$ and subgroups $H$ and $K$ belonging to $G$, return the value `true` if $H$ and $K$ are conjugate in $G$. The function returns a second value in the event that the subgroups are conjugate: an element $z$ which conjugates $H$ into $K$. ### `IsGLConjugate(H, K): GrpMat, GrpMat -> BoolElt, GrpMatElt | Unass` Given $H$ and $K$, both subgroups of the same general linear group $G = GL_n(q)$, return the value `true` if $H$ and $K$ are conjugate in $G$. The function returns a second value in the event that the subgroups are conjugate: an element $z$ which conjugates $H$ into $K$. The algorithm is described in Roney-Dougal [[Roney-Dougal, 2004](../../references.md#cite-isglconjugate)].