# Conjugacy Classes of Subgroups Magma contains a new algorithm for computing representatives of the conjugacy classes of subgroups. Let $R$ denote the maximal normal soluble subgroup of the finite group $G$. The algorithm first constructs representatives for the conjugacy classes of subgroups of $Q = G/R$, and then successively extends these to larger and larger quotients of $G$ until $G$ itself is reached. If $G$ is soluble, then $Q$ is trivial and so its subgroups are known. If $G$ is non-soluble, we 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$, $S_4(q)$, $U_3(q)$ and $U_4(q)$ for all $q$, $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. ## Conjugacy Classes of Subgroups In this section we describe the functions that allow a user to create representatives of the conjugacy classes of subgroups, possibly subject to conditions. The main function, `Subgroups`, finds representatives for conjugacy classes of subgroups subject to certain user-supplied conditions on the order. The alternative functions `ElementaryAbelianSubgroups` and `AbelianSubgroups`, `CyclicSubgroups`, `NilpotentSubgroups`, `SolubleSubgroups`, `PerfectSubgroups`, `NonsolvableSubgroups`, `SimpleSubgroups` and `RegularSubgroups` allow the user to construct particular classes of subgroups. Most of the features described in this section are currently only available for groups in the category `GrpPerm`, `GrpMat` or `GrpPC`. ### `SubgroupClasses(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` ### `Subgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` ### `Subgroups(G, N: parameters): GrpFin, GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` ```magma Presentation : BoolElt Default: false OrderEqual : RngIntElt Default: OrderDividing: RngIntElt Default: IsNormal : BoolElt Default: false IsRegular : BoolElt Default: false LayerSizes : SeqEnum Default: see below ``` Representatives for the conjugacy classes of subgroups for the group $G$. If $N$ is given, it must be a soluble normal subgroup of $G$. The subgroups returned are subgroups of $G$ containing $N$. 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)** [Optionally] A presentation for $H$ (field name `presentation`). `Presentation := true`: In the case in which $G$ is a permutation group, 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$. `IsNormal := true`: Only construct normal subgroups. `IsRegular := true`: In the case in which $G$ is a permutation group, only construct regular subgroups. `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. ### `ElementaryAbelianSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of elementary abelian subgroups for the group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `AbelianSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of abelian subgroups for the group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `CyclicSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of cyclic subgroups for the group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `NilpotentSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of nilpotent subgroups for the group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `SolubleSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` ### `SolvableSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of solvable subgroups for the group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `NonsolvableSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of nonsolvable subgroups for the group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `PerfectSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of perfect subgroups for the group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `SimpleSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of non-abelian simple subgroups for the group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `RegularSubgroups(G: parameters): GrpFin -> [ rec< Grp, RngIntElt, RngIntElt, GrpFP> ]` Representatives for the conjugacy classes of regular subgroups for the permutation group $G$. The subgroups are returned as a sequence of records having the same format as `Subgroups`. The optional parameters are also the same as for `Subgroups`. ### `SetVerbose("SubgroupLattice", i): MonStgElt, RngIntElt` Turn on verbose printing for the subgroup algorithm. The level $i$ can be 2 for maximal printing or 1 for moderate printing. The algorithm works down an elementary abelian series of the group and at each level, the possible extensions of each subgroup are listed. ### `Class(G, H): GrpFin, GrpFin -> { GrpFin }` ### `Conjugates(G, H): GrpFin, GrpElt -> { GrpElt }` The $G$-conjugacy class of subgroups containing the group $H$. ### `Example: Subgroups (ex-ca0e1e)` We construct the conjugacy classes of subgroups for the dihedral group of order $12$. ```magma > G := DihedralGroup(6); > S := Subgroups(G); > S; Conjugacy classes of subgroups ------------------------------ [ 1] Order 1 Length 1 Permutation group acting on a set of cardinality 6 Order = 1 Id($) [ 2] Order 2 Length 3 Permutation group acting on a set of cardinality 6 (2, 6)(3, 5) [ 3] Order 2 Length 3 Permutation group acting on a set of cardinality 6 (1, 4)(2, 3)(5, 6) [ 4] Order 2 Length 1 Permutation group acting on a set of cardinality 6 (1, 4)(2, 5)(3, 6) [ 5] Order 3 Length 1 Permutation group acting on a set of cardinality 6 (1, 5, 3)(2, 6, 4) [ 6] Order 4 Length 3 Permutation group acting on a set of cardinality 6 (2, 6)(3, 5) (1, 4)(2, 5)(3, 6) [ 7] Order 6 Length 1 Permutation group acting on a set of cardinality 6 (1, 5, 3)(2, 6, 4) (1, 4)(2, 5)(3, 6) [ 8] Order 6 Length 1 Permutation group acting on a set of cardinality 6 (2, 6)(3, 5) (1, 5, 3)(2, 6, 4) [ 9] Order 6 Length 1 Permutation group acting on a set of cardinality 6 (1, 4)(2, 3)(5, 6) (1, 5, 3)(2, 6, 4) [10] Order 12 Length 1 Permutation group acting on a set of cardinality 6 (2, 6)(3, 5) (1, 5, 3)(2, 6, 4) (1, 4)(2, 5)(3, 6) > // We extract the representative subgroup for class 7 > h := S[7]`subgroup; > h; Permutation group h acting on a set of cardinality 6 (1, 3, 5)(2, 4, 6) (1, 4)(2, 5)(3, 6) ``` ## The Poset of Subgroup Classes In addition to finding representatives for conjugacy classes of subgroups, Magma allows the user to create the poset $L$ of subgroup classes. The elements of the poset correspond to the conjugacy classes of subgroups. Two lattice elements $a$ and $b$ are joined by an edge if either some subgroup of the conjugacy class $a$ is a maximal subgroup of some subgroup of conjugacy class $b$ or vice-versa. The elements of $L$ are called *subgroup-poset elements* and are numbered from 1 to $n$, where $n$ is the cardinality of $L$. Various functions allow the user to identify maximal subgroups, normalizers, centralizers and other relatives in the lattice. Given an element $e$ of $L$, one can easily create the subgroup $H$ of $G$ corresponding to $e$ and one can also create the element of $L$ corresponding to a subgroup of $G$. The features described in this section are currently only available for groups in the category `GrpPerm` or `GrpPC`. ### Creating the Poset of Subgroup Classes #### `SubgroupLattice(G): GrpFin -> SubGrpLat` ```magma Properties : BoolElt Default: false Centralizers: BoolElt Default: false Normalizers : BoolElt Default: false ``` Create the poset $L$ of subgroup classes of $G$. `Properties := true`: As the subgroup classes are put into the poset, record their abstract type, i.e., elementary abelian, abelian, nilpotent, soluble, simple or perfect. `Centralizers := true`: As each subgroup class $e$ is put into the poset, record the class in which the centralizers of the subgroups of $e$ lie. `Normalizers := true`: As each subgroup class $e$ is put into the poset, record the class in which the normalizers of the subgroups of $e$ lie. #### `Example: Create Subgroup Poset (ex-c15cda)` We create the subgroup poset for the group ${\operatorname{ASL}}(2, 3)$. ```magma > G := ASL(2, 3); > L := SubgroupLattice(G : Properties := true, Normalizers:= true, > Centralizers:= true); > L; Partially ordered set of subgroup classes ----------------------------------------- [ 1] Order 1 Length 1 C = [20] N = [20] Maximal Subgroups: --- [ 2] Order 2 Length 9 Cyclic. C = [16] N = [16] Maximal Subgroups: 1 [ 3] Order 3 Length 12 Cyclic. C = [14] N = [14] Maximal Subgroups: 1 [ 4] Order 3 Length 24 Cyclic. C = [10] N = [10] Maximal Subgroups: 1 [ 5] Order 3 Length 4 Cyclic. C = [15] N = [18] Maximal Subgroups: 1 --- [ 6] Order 4 Length 27 Cyclic. C = [6] N = [12] Maximal Subgroups: 2 [ 7] Order 6 Length 12 Soluble. C = [3] N = [14] Maximal Subgroups: 2 5 [ 8] Order 6 Length 36 Cyclic. C = [8] N = [8] Maximal Subgroups: 2 3 [ 9] Order 9 Length 4 Elementary Abelian. C = [9] N = [18] Maximal Subgroups: 3 5 [10] Order 9 Length 8 Elementary Abelian. C = [10] N = [15] Maximal Subgroups: 4 5 [11] Order 9 Length 1 Elementary Abelian. C = [11] N = [20] Maximal Subgroups: 5 --- [12] Order 8 Length 9 Nilpotent. C = [2] N = [16] Maximal Subgroups: 6 [13] Order 18 Length 1 Soluble. C = [1] N = [20] Maximal Subgroups: 7 11 [14] Order 18 Length 12 Soluble. C = [3] N = [14] Maximal Subgroups: 7 8 9 [15] Order 27 Length 4 Nilpotent. C = [5] N = [18] Maximal Subgroups: 9 10 11 --- [16] Order 24 Length 9 Soluble. C = [2] N = [16] Maximal Subgroups: 8 12 [17] Order 36 Length 3 Soluble. C = [1] N = [19] Maximal Subgroups: 6 13 [18] Order 54 Length 4 Soluble. C = [1] N = [18] Maximal Subgroups: 13 14 15 --- [19] Order 72 Length 1 Soluble. C = [1] N = [20] Maximal Subgroups: 12 17 --- [20] Order 216 Length 1 Soluble. C = [1] N = [20] Maximal Subgroups: 16 18 19 ``` ### Operations on Subgroup Class Posets In the following, $L$ is the poset of subgroup classes for a group $G$. #### `# L: SubGrpLat -> RngIntElt` The cardinality of $L$, i.e., the number of conjugacy classes of subgroups of $G$. #### `L ! i: SubGrpLat, RngIntElt -> SubGrpLatElt` Create the $i$-th element of the poset $L$. The elements of $L$ are sorted so that classes $i$ and $j$ of groups whose orders $o_i$ and $o_j$ are the products of $e_i$ and $e_j$ prime numbers respectively will be ordered so that $i$ comes before $j$ is $e_i SubGrpLatElt` Create the element of the poset $L$ corresponding to the subgroup $H$ of the group $G$. #### `Bottom(L): SubGrpLat -> SubGrpLatElt` Create the bottom of the poset $L$, i.e., the element of $L$ corresponding to the trivial subgroup of $G$. If the poset was created with restrictions on the type of subgroups constructed, the bottom of the poset may not be the trivial subgroup. #### `Top(L): SubGrpLat -> SubGrpLatElt` Create the top of the poset $L$, i.e., the element of $L$ corresponding to $G$. #### `Random(L): SubGrpLat -> SubGrpLatElt` Create a random element of $L$. #### `Example: Lattice Operations (ex-b91cf9)` We create the subgroup lattice of ${\operatorname{A\Gamma L}}(1, 8)$ and locate the Fitting subgroup in the lattice. ```magma > G := AGammaL(1, 8); > L := SubgroupLattice(G); > L; Subgroup Lattice ---------------- [ 1] Order 1 Length 1 Maximal Subgroups: --- [ 2] Order 2 Length 7 Maximal Subgroups: 1 [ 3] Order 3 Length 28 Maximal Subgroups: 1 [ 4] Order 7 Length 8 Maximal Subgroups: 1 --- [ 5] Order 4 Length 7 Maximal Subgroups: 2 [ 6] Order 6 Length 28 Maximal Subgroups: 2 3 [ 7] Order 21 Length 8 Maximal Subgroups: 3 4 --- [ 8] Order 8 Length 1 Maximal Subgroups: 5 [ 9] Order 12 Length 7 Maximal Subgroups: 3 5 --- [10] Order 24 Length 7 Maximal Subgroups: 6 8 9 [11] Order 56 Length 1 Maximal Subgroups: 4 8 --- [12] Order 168 Length 1 Maximal Subgroups: 7 10 11 > F := FittingSubgroup(G); > F; Permutation group F acting on a set of cardinality 8 Order = 8 = 2^3 (1, 2)(3, 6)(4, 8)(5, 7) (1, 6)(2, 3)(4, 7)(5, 8) (1, 5)(2, 7)(3, 4)(6, 8) > L!F; 8 ``` We now construct a chain from the bottom to the top of the lattice. ```magma > H := Bottom(L); > Chain := [H]; > while H ne Top(L) do > H := Representative(MinimalOvergroups(H)); > Chain := Append(Chain, H); > end while; > Chain; [ 1, 2, 5, 8, 10, 12 ] ``` ### Operations on Poset Elements In the following, $L$ is the poset of subgroups for a group $G$. Elements of $L$ are identified with the integers $[1..\#L]$. #### `IntegerRing() ! e: SubGrpLatElt -> RngIntElt` The integer corresponding to poset element $e$. #### `e eq f: SubGrpLatElt, SubGrpLatElt -> SubGrpLatElt` Returns `true` if and only if poset elements $e$ and $f$ are equal. #### `e ge f: SubGrpLatElt, SubGrpLatElt -> BoolElt` Returns `true` if and only if poset element $e$ contains poset element $f$. #### `e ge f: SubGrpLatElt, SubGrpLatElt -> BoolElt` Returns `true` if and only if poset element $e$ strictly contains poset element $f$. #### `e le f: SubGrpLatElt, SubGrpLatElt -> BoolElt` #### `e subset f: SubGrpLatElt, SubGrpLatElt -> SubGrpLatElt` Returns `true` if and only if poset element $e$ is contained in poset element $f$. #### `e lt f: SubGrpLatElt, SubGrpLatElt -> BoolElt` Returns `true` if and only if poset element $e$ is strictly contained in poset element $f$. ### Class Information from a Conjugacy Class Poset In the following, $L$ is the poset of subgroups for a group $G$. Elements of $L$ are identified with the integers $[1..\#L]$. #### `Group(e): SubGrpLatElt -> GrpFin` The subgroup of $G$ that is the chosen class representative corresponding to the element $e$ of the poset $L$. #### `Centraliser(e, f): SubGrpLatElt, SubGrpLatElt -> SubGrpLatElt` #### `Centralizer(e, f): SubGrpLatElt, SubGrpLatElt -> SubGrpLatElt` Given poset elements $e$ and $f$, return the poset element that corresponds to the class of subgroups that contains the centralizers of the subgroups of class $f$ (taken in a subgroup of class $e$). If no subgroup of class $f$ lies in class $e$, the construction fails. #### `Normaliser(e, f): SubGrpLatElt, SubGrpLatElt -> SubGrpLatElt` #### `Normalizer(e, f): SubGrpLatElt, SubGrpLatElt -> SubGrpLatElt` Given poset elements $e$ and $f$, return the poset element that corresponds to the class of subgroups that contain the normalizers of the subgroups of class $f$ (taken in a subgroup of class $e$). If no subgroup of class $f$ lies in class $e$, the construction fails. #### `Length(e): SubGrpLatElt -> RngIntElt` The number of subgroups in the class corresponding to $e$. #### `Order(e): SubGrpLatElt -> RngIntElt` The order of the subgroup of $G$ corresponding to $e$. #### `MaximalSubgroups(e): SubGrpLatElt -> { SubGrpLatElt }` The maximal subgroups of $e$, returned as a set of poset elements. #### `MinimalOvergroups(e): SubGrpLatElt -> { SubGrpLatElt }` The minimal overgroups of $e$, returned as a set of poset elements. #### `NumberOfInclusions(e, f): SubGrpLatElt, SubGrpLatElt -> RngIntElt` The number of elements of the conjugacy class of subgroups $e$ that lie in a fixed representative of the conjugacy class of subgroups $f$.