# Automorphism Group ## General Soluble Group In the case of a soluble non-$p$-group there are two algorithms available. By default, a lifting-based algorithm developed by M. Smith [[Smith, 1994](../../references.md#cite-smith-thesis)] and extended by Smith and Slattery to use second cohomology is used. Alternatively, there is also an algorithm developed by D. Howden [[Howden, 2012](../../references.md#cite-howden-thesis)], which uses the automorphism group of a Sylow $p$-subgroup of $G$ to construct the automorphism group of $G$. ### Lifting Algorithm The automorphism group is computed step-by-step considering a series of factors of $G$ by terms of a characteristic series $$ G = G_1 > G_2 > \cdots > G_k > 1 $$ such that $G_i/G_{i+1}$ is elementary abelian for each $i$. We compute the automorphism group ${\operatorname{Aut}}(G/G_2)\cong{\operatorname{GL}}(d,p)$ for some integer $d$ and prime $p$, and then lift through each of the elementary abelian layers $G/G_3,\dots, G/G_{k-1}$, finally arriving at ${\operatorname{Aut}}(G/G_k) = {\operatorname{Aut}}(G)$. A group of type `GrpAuto` is returned. Details of the computation can be seen by setting the verbose flag `AutomorphismGroup` to `true`, and the characteristic series is available as the attribute `CharacteristicSeries` on the returned group. In addition to the usual properties of `GrpAuto` (such as `Order`, `Ngens`, etc.), two special fields, `GenWeights` and `WeightSubgroupOrders`, are provided for automorphism groups of (non $p$-group) pc-groups. These each relate to weight subgroups of the automorphism group. Let $i$ be the largest subscript such that the automorphism acts trivially on $G/G_i$. Then the automorphism is said to have weight $2i+1$ if it acts non-trivially on $G_i/G_{i+1}$, and weight $2i+2$ if it acts trivially on $G_i/G_{i+1}$. Note that there are no automorphisms of weight 2. The automorphisms of weight greater than or equal to a given value form a normal subgroup of $A$. #### `AutomorphismGroup(G): GrpPC -> GrpAuto` Given a soluble group $G$ presented by a pc-presentation, this function returns the automorphism group of $G$ as a group of type `GrpAuto`. #### `HasAttribute(A, "GenWeights"): GrpAuto, MonStgElt -> BoolElt, [ RngIntElt ]` If the attribute `GenWeights` is defined for $A$ then the function returns `true`, and a sequence of integers. This integer sequence indicates where each generator lies in the normal series of $A$ corresponding to the action of the group on $G$ (as described at the beginning of the section). If the attribute is not set then the sequence is unassigned. The function call `AutomorphismGroup(G)`, where $G$ has type `GrpPC`, always returns an automorphism group with this attribute set. In this case the sequence may also be obtained by the short form `A`GenWeights`. #### `HasAttribute({A, }{"WeightSubgroupOrders"}): GrpAuto, MonStgElt -> BoolElt, [ RngIntElt ]` If the attribute `WeightSubgroupOrders` is defined for $A$ then the function returns `true`, and a sequence of integers. This sequence of integers gives the orders for the normal series of weight subgroups described at the beginning of the section. If the attribute is not set then the sequence is unassigned. The function call `AutomorphismGroup(G)`, where $G$ has type `GrpPC`, always returns an automorphism group with this attribute set. In this case the sequence may also be obtained by the short form `A`WeightSubgroupOrders`. #### `Example: Automorphism Group (ex-29a2d6)` An example using `AutomorphismGroup` and some related features. We build a group based on the structure of a finite field (multiplicative group acting on the additive group) and then compute its automorphism group. First, we set up the field. ```magma > E := GF(2); > F := GF(8); > V,phi := VectorSpace(F,E); > d := Dimension(V); > x := PrimitiveElement(F); ``` Then, define a pc-group to act and define the action based on the multiplication in the field. Compute the matrix by mapping the vectors back to the field, multiplying by x, and then recording the result. ```magma > C := CyclicGroup(GrpPC,Order(x)); > MR := MatrixRing(E, d); > s := []; > for i := 1 to d do > y := ((V.i)@@phi)*x; > s cat:= Eltseq(y); > end for; ``` Turn the sequence of image components into a matrix and use the matrix to create a C-module. Then use that module to create the split extension. ```magma > t := MR!s; > M := GModule(C,[t]); > G := Extension(M,C); > G; GrpPC : G of order 56 = 2^3 * 7 PC-Relations: G.1^7 = Id(G), G.2^2 = Id(G), G.3^2 = Id(G), G.4^2 = Id(G), G.2^G.1 = G.3, G.3^G.1 = G.4, G.4^G.1 = G.2 * G.3 ``` Then we can compute the automorphism group of $G$. ```magma > A := AutomorphismGroup(G: Algorithm := "Default"); > A; A group of automorphisms of GrpPC : G Generators: Automorphism of GrpPC : G which maps: G.1 |--> G.1^2 G.2 |--> G.3 * G.4 G.3 |--> G.2 * G.4 G.4 |--> G.3 Automorphism of GrpPC : G which maps: G.1 |--> G.1 G.2 |--> G.2 * G.3 G.3 |--> G.3 * G.4 G.4 |--> G.2 * G.3 * G.4 Automorphism of GrpPC : G which maps: G.1 |--> G.1 * G.2 * G.3 G.2 |--> G.2 G.3 |--> G.3 G.4 |--> G.4 Automorphism of GrpPC : G which maps: G.1 |--> G.1 * G.3 * G.4 G.2 |--> G.2 G.3 |--> G.3 G.4 |--> G.4 Automorphism of GrpPC : G which maps: G.1 |--> G.1 * G.4 G.2 |--> G.2 G.3 |--> G.3 G.4 |--> G.4 > [Order(x):x in Generators(A)]; [ 3, 2, 7, 2, 2 ] ``` Next, we can use the automorphisms to create an extension of $G$. ```magma > b := A.1; > Order(b); 3 > tau := homG|[b(G.i):i in [1..NPCgens(G)]]>; > D := CyclicGroup(GrpPC,Order(b)); > K := Extension(G,D,[tau]); > K; GrpPC : K of order 168 = 2^3 * 3 * 7 PC-Relations: K.1^3 = Id(K), K.2^7 = Id(K), K.3^2 = Id(K), K.4^2 = Id(K), K.5^2 = Id(K), K.2^K.1 = K.2^2, K.3^K.1 = K.4 * K.5, K.3^K.2 = K.4, K.4^K.1 = K.3 * K.5, K.4^K.2 = K.5, K.5^K.1 = K.4, K.5^K.2 = K.3 * K.4 > #Classes(K); 8 ``` Finally, we examine information about the weight subgroups. We list only the orders of the terms of the characteristic series in $G$ in order to save space. ```magma > [Order(H): H in A`CharacteristicSeries]; [ 56, 8, 1 ] > A`GenWeights; [ 1, 3, 4, 4, 4 ] > A`WeightSubgroupOrders; [ 168, 56, 56, 8 ] ``` ### Lifting from the Automorphism Group of a Sylow $p$-subgroup The algorithm developed by D. Howden [[Howden, 2012](../../references.md#cite-howden-thesis)] follows a different strategy to the Smith-Slattery lifting approach. Given a soluble group $G$, the algorithm determines a suitable Sylow $p$-subgroup $P$ of $G$, and uses the automorphism group of $P$ (using the algorithm for $p$-groups detailed below) to construct the automorphism group of $G$. In cases where the automorphism group is soluble, the algorithm automatically constructs a pc-representation for it. Solubility of the returned group can then be tested via the `IsSoluble` intrinsic. The pc-representation obtained using the `PCGroup` intrinsic, and pc-generators (as automorphism maps) via the `PCGenerators` intrinsic. In some cases where the automorphism group is not soluble, the algorithm will construct a permutation representation during its construction. A group of type `GrpAuto` is returned. Details of the computation can be seen by setting the verbose flag `AutomorphismGroupSolubleGroup` to 1. A variation of this algorithm can be used for isomorphism testing. #### `AutomorphismGroupSolubleGroup(G: parameters): GrpPC -> GrpAuto` ```magma p: [RngIntElt] Default: 1 ``` Given a soluble group $G$ presented by a pc-presentation, this function returns the automorphism group of $G$ as a group of type GrpAuto. A prime $p$ dividing the order of $G$. The automorphism group of the Sylow $p$-subgroup is then used to construct the automorphism group of $G$. If the $p$-core of $G$ is trivial then an error is given. The default value of $p = 1$ indicates that the algorithm should take $p$ to be the prime giving the largest Sylow $p$-subgroup of $G$. #### `IsIsomorphicSolubleGroup(G, H: parameters): GrpPC, GrpPC -> BoolElt, Map` ```magma p: [RngIntElt] Default: 1 ``` Returns `true` if the soluble groups $G$, $H$ presented by pc-presentations, are isomorphic, and `false` otherwise. Where the groups are isomorphic, a mapping $G\to H$ is also returned. A prime $p$ dividing the order of $G$ (assuming that the orders of $G$ and $H$ are the same). The algorithm then tests Sylow $p$-subgroups of $G$ and $H$ for isomorphism and attempts to extend these isomorphisms to an isomorphism $G\to H$. If the $p$-cores of $G$ and $H$ are trivial then an error is given. The default value of $p = 1$ indicates that the algorithm should take $p$ to be the prime giving the largest Sylow $p$-subgroup of $G$. #### `Example: Automorphism Group Soluble Group (ex-249c9b)` An example using `AutomorphismGroupSolubleGroup` and some related features. We use a group from the `solgps` library. ```magma > load solgps; > G := G10(); > FactoredOrder(G); [ <2, 18>, <7, 4> ] > time A := AutomorphismGroupSolubleGroup(G); Time: 18.220 > time R_A, phi_A := PCGroup(A); Time: 0.000 > FactoredOrder(R_A); [ <2, 20>, <3, 2>, <7, 6> ] ``` ## $p$-group For a description of the algorithm used to construct the automorphism group of a $p$-group, see [[Eick *et al.*, 2002](../../references.md#cite-elo-auts)]. While it is difficult to state very firm guidelines for the performance of the algorithm, our experience suggests that it has most difficulty in constructing automorphism groups of $p$-groups of “large” Frattini rank (say rank larger than about 6) and $p$-class 2. If the group has larger $p$-class, then it usually has more characteristic structure and the algorithm exploits this. The *order* of a group is *not* a useful guide to the difficulty of the computation. `SetVerbose ("AutomorphismGroup", 1)` provides information on the progress of the algorithm. ### `AutomorphismGroup(G: parameters): GrpPC -> GrpAuto` ```magma CharacteristicSubgroups: [GrpPC] Default: [] ``` The group $G$ is a $p$-group described by a pc-presentation. The function returns the automorphism group of $G$ as a group of type `GrpAuto`. A list of known characteristic subgroups of $G$; these may improve the efficiency of the construction. Note that the algorithm simply accepts that the supplied subgroups are fixed under the action of the automorphism group; it does *not* verify that they are in fact characteristic. ### `Example: p Automorphism Group (ex-f1bbe5)` ```magma > G := SmallGroup (64, 78); > A := AutomorphismGroup (G); > #A; 1024 > A.1; Automorphism of GrpPC : G which maps: G.1 |--> G.1 G.2 |--> G.2 G.3 |--> G.1 * G.3 G.4 |--> G.4 G.5 |--> G.5 G.6 |--> G.4 * G.6 > Order (A.1); 4 > a := A.1^2; [a (G.i): i in [1..6]]; [ G.1, G.2, G.3 * G.5, G.4, G.5, G.6 ] ``` ### `OrderAutomorphismGroupAbelianPGroup(A): SeqEnum -> RngIntElt` Order of automorphism group of abelian $p$-group $G$ where $A = [a_1, a_2, \ldots]$ and $G = C_{a_1} \times C_{a_2} \times \ldots$. ### `Example: subgroupsabelianpgroups (ex-c99f0c)` Subgroups of $C_4 \times C_8 \times C_{64}$. ```magma > NumberOfSubgroupsAbelianPGroup ([4, 8, 64]); [ 7, 35, 91, 139, 171, 171, 139, 91, 35, 7, 1 ] ``` Hence, for example, there are 7 subgroups of order 2 and 139 subgroups of order $2^4$. ```magma > OrderAutomorphismGroupAbelianPGroup ([4, 8, 64]); 4194304 ``` ## Isomorphism and Standard Presentations The `pQuotient` command returns a power-conjugate presentation for a given $p$-group but this presentation depends on the user-supplied description of the group. The Standard Presentation algorithm computes a “canonical” presentation for the $p$-group, which is independent of the user-supplied description. For a description of this algorithm, see [[O'Brien, 1994](../../references.md#cite-obrien-isom)]. The canonical or *standard* presentation of a given $p$-group is the power-conjugate presentation obtained when a description of the group is computed using the default implementation of the $p$-group generation algorithm. Hence, two groups in the same isomorphism class have identical standard presentations. Given two $p$-groups, if their standard presentations are identical, then the groups are isomorphic, otherwise they are not. Hence to decide whether two groups are isomorphic, we can first construct the standard presentation of each using the `StandardPresentation` function and then compare these presentations using the `IsIdenticalPresentation` function. While it is difficult to state very firm guidelines for the performance of the algorithm, our experience suggests that the difficulty of deciding isomorphism between $p$-groups is governed by their Frattini rank and is most practical for $p$-groups of rank at most 5. The *order* of a group is *not* a useful guide to the difficulty of the computation. `SetVerbose ("Standard", 1)` will provide information on the progress of the algorithm. ### `StandardPresentation(G): GrpPC -> GrpPC, Map` ### `StandardPresentation(G: parameters): GrpPC -> GrpAuto` ```magma StartClass: RngIntElt Default: 1 ``` The group $G$ is a $p$-group presented by an arbitrary pc-presentation. The group $H$ defined by its standard presentation is returned together with a map from $G$ to $H$. If `StartClass` is $k$, then use `pQuotient` to construct the class $k - 1$ $p$-quotient of $G$ and standardize the presentation only from class $k$ onwards. ### `IsIdenticalPresentation(G, H): GrpPC, GrpPC -> BoolElt` Returns `true` if $G$ and $H$ have identical presentations, `false` otherwise. ### `IsIsomorphic(G, H): GrpPC, GrpPC -> BoolElt, Map, GrpPC` The function returns `true` if the $p$-groups $G$ and $H$ are isomorphic, `false` otherwise. It constructs their standard presentations class by class, and checks for equality. If they are isomorphic, it also returns an isomorphism from $G$ to $H$ and the isomorphism class representative. ### `Example: Standard Presentation (ex-75ee54)` In the next two examples, we investigate whether particular $p$-quotients of fp-groups are isomorphic. ```magma > F := FreeGroup(3); > G := quo< F | x*y^2*x^-1=y^-2, y*x^2*y^-1=x^-2, x^2=t^2, y^2=(t^-1*x)^2, > t*(x*y)^2=(x*y)^2*t >; > Q1 := pQuotient(G, 2, 3: Print := 1); Lower exponent-2 central series for G Group: G to lower exponent-2 central class 1 has order 2^3 Group: G to lower exponent-2 central class 2 has order 2^7 Group: G to lower exponent-2 central class 3 has order 2^11 > H := quo< F | x*y^2*x^-1=y^-2, y*x^2*y^-1=x^-2, x^2=t^2*(x*y)^2, > y^2=(t^-1*x)^2, t*(x*y)^2=(x*y)^2*t >; > Q2 := pQuotient(H, 2, 3: Print := 1); Lower exponent-2 central series for H Group: H to lower exponent-2 central class 1 has order 2^3 Group: H to lower exponent-2 central class 2 has order 2^7 Group: H to lower exponent-2 central class 3 has order 2^11 ``` Now check whether the class 3 2-quotients are isomorphic. ```magma > IsIsomorphic(Q1, Q2); false ``` In the next example, we construct an explicit isomorphism between two 5-groups. ```magma > F := Group; > G := pQuotient (F, 5, 6 : Print := 1); Lower exponent-5 central series for F Group: F to lower exponent-5 central class 1 has order 5^2 Group: F to lower exponent-5 central class 2 has order 5^3 Group: F to lower exponent-5 central class 3 has order 5^4 Group: F to lower exponent-5 central class 4 has order 5^5 Group: F to lower exponent-5 central class 5 has order 5^7 Group: F to lower exponent-5 central class 6 has order 5^8 > G; GrpPC : G of order 390625 = 5^8 PC-Relations: G.2^G.1 = G.2 * G.3, G.3^G.1 = G.3 * G.4, G.3^G.2 = G.3 * G.6 * G.7^4 * G.8^4, G.4^G.1 = G.4 * G.5, G.4^G.2 = G.4 * G.7 * G.8, G.4^G.3 = G.4 * G.7^4 * G.8, G.5^G.1 = G.5 * G.6, G.5^G.2 = G.5 * G.7, G.5^G.3 = G.5 * G.8^2, G.6^G.2 = G.6 * G.8, G.7^G.1 = G.7 * G.8^3 > K := Group; > H := pQuotient (K, 5, 6 : Print := 1); Lower exponent-5 central series for K Group: K to lower exponent-5 central class 1 has order 5^2 Group: K to lower exponent-5 central class 2 has order 5^3 Group: K to lower exponent-5 central class 3 has order 5^4 Group: K to lower exponent-5 central class 4 has order 5^5 Group: K to lower exponent-5 central class 5 has order 5^7 Group: K to lower exponent-5 central class 6 has order 5^8 > H; GrpPC : H of order 390625 = 5^8 PC-Relations: H.2^H.1 = H.2 * H.3, H.3^H.1 = H.3 * H.4, H.3^H.2 = H.3 * H.6^2 * H.7^2 * H.8^2, H.4^H.1 = H.4 * H.5, H.4^H.2 = H.4 * H.7, H.4^H.3 = H.4 * H.7^4 * H.8, H.5^H.1 = H.5 * H.6, H.5^H.2 = H.5 * H.7, H.5^H.3 = H.5 * H.8^2, H.6^H.2 = H.6 * H.8, H.7^H.1 = H.7 * H.8^3 > flag, phi := IsIsomorphic (G, H); > flag; true > for g in PCGenerators (G) do print g, "--->", phi (g); end for; G.1 ---> H.1 G.2 ---> H.2^3 * H.4^3 * H.5^3 * H.6^2 * H.7^4 * H.8^3 G.3 ---> H.3^3 * H.5^3 * H.6^4 * H.8^3 G.4 ---> H.4^3 * H.6^3 * H.7^2 * H.8^3 G.5 ---> H.5^3 * H.8 G.6 ---> H.6^3 G.7 ---> H.7^4 G.8 ---> H.8^4 ``` The functions `IsIsomorphic` and `StandardPresentation` are expensive. Here we have a list of groups and we want to find any isomorphisms among the collection. Rather than repeatedly applying `IsIsomorphic`, we first construct and store standard presentations for each group in the sequence, and then quickly compare these using `IsIdenticalPresentation`. ```magma > F := FreeGroup (2); > p := 7; > Q := []; > for k := 1 to p - 1 do > G := quo< F | a^p = (b, a, a), b^p = a^(k*p), (b, a, b)>; > H := pQuotient (G, p, 10); > Q[k] := StandardPresentation (H); > end for; ``` Now run over the list of standard presentations and check for equality. ```magma > for i in [2..p - 1] do > for j in [1.. i - 1] do > if IsIdenticalPresentation (Q[i], Q[j]) then > print "Standard Presentations ", i, " and ", j, " are identical"; > end if; > end for; > end for; Standard Presentations 2 and 1 are identical Standard Presentations 4 and 1 are identical Standard Presentations 4 and 2 are identical Standard Presentations 5 and 3 are identical Standard Presentations 6 and 3 are identical Standard Presentations 6 and 5 are identical ```