# Identification ## Identification as an Abstract Group ### `NameSimple(G): GrpPerm -> ` Given a simple group $G$, determine the isomorphism type of $G$. The type is returned in the form of a triple of three integers $f, d$ and $q$, where the interpretation of these integers is that given in the description of the function `CompositionFactors`. ## Identification as a Permutation Group The first functions described in this subsection detect whether or not a permutation group is alternating or symmetric in its natural representation. They are based on the algorithm ‘Detect Alternating’ outlined in [[Cannon and Bosma, 1992](../../references.md#cite-struct-gps)]. ### `IsAlternating(G): GrpPerm -> BoolElt` Returns `true` if the permutation group $G$ defined as acting on $X$ is the alternating group ${\operatorname{Alt}}(X)$. ### `IsSymmetric(G): GrpPerm -> BoolElt` Returns `true` if the permutation group $G$ defined as acting on $X$ is the symmetric group ${\operatorname{Sym}}(X)$. ### `IsAltsym(G : parameters): GrpPerm -> BoolElt` ```magma Limit: RngIntElt Default: 0 Proof: BoolElt Default: true ``` Returns `true` if the permutation group $G$ defined as acting on $X$ contains the alternating group ${\operatorname{Alt}}(X)$. The `Limit` argument controls the number of random elements of the group inspected in an attempt to show that the group does contain ${\operatorname{Alt}}(X)$ cheaply. The 0 value indicates the default strategy. The `Proof` argument set to false will restrict the algorithm to its probabilistic part. This will mean that there is a chance that a return value of false is incorrect. Return value of true is always correct. ### `TwoTransitiveGroupIdentification(G): GrpPerm -> Tup` Given a $2$-transitive group $G$, return a tuple giving the abstract isomorphism type of the group. This is an implementation of the method of Cameron and Cannon [[Cameron and Cannon, 1991](../../references.md#cite-two-trans)]. ### `IsEven(G): GrpPerm -> BoolElt` Given a permutation group $G$ check if $G$ is even, ie. contained in the alternating group. ### `RecogniseAlternatingOrSymmetric(G : parameters): Grp, RngIntElt -> BoolElt, Map, Map, Map, Map, BoolElt` ```magma N : RngIntElt Default: 0 Extension : BoolElt Default: false Epsilon : FldRElt Default: 0.01 Asymptotic: BoolElt Default: false ``` The input group $G$ is isomorphic to $H$, the alternating or symmetric group for some $n \geq 5$. Note that $G$ can be either a matrix or permutation representation of $H$. The algorithm used is that of [[Jambor *et al.*, 2013](../../references.md#cite-altsymrecogn)]. Since this is Las Vegas, there is a small probability controlled by the optional parameter `Epsilon` that it returns `false` incorrectly. If the algorithm succeeds, then it returns `true`, an isomorphism from $G$ to $H$, an isomorphism from $H$ to $G$, the map from $G$ to its word group, and the map from the word group to $G$. The sixth value returned is `true` if $H$ is the symmetric group, otherwise `false`. The optional parameter `N` is an upper bound for the degree of $H$. If `N` is 0, then the maximal theoretically possible bound for the degree is assumed; this is the degree of $G$ if $G$ is a permutation group, and $\max(9, d + 2)$ or $\max(9, d+1)$ if $G$ is a matrix group of degree $d$, depending on the characteristic of the field. If the optional parameter `Extension` is `true`, then $G$ is isomorphic to a central extension of $H$ for some $n \geq 5$. Now the first two maps returned are an epimorphism from $G$ onto $H$ with kernel $Z(G)$ and a map from $H$ to $G$ that induces an isomorphism from $H$ onto $G/Z(G)$. If the optional parameter `Asymptotic` is `true`, then the map from $H$ to $G$ implements the asymptotically efficient algorithm of Beals et al. [[Beals *et al.*, 2003](../../references.md#cite-altsymrecog1)]. Otherwise, the algorithm employed for this map is that of [[Bratus and Pak, 2000](../../references.md#cite-bratus-pak)], which is usually faster for moderate degrees. If the algorithm is not successful, then `false` is returned. The algorithm consists of two parts. The first part finds the degree of the alternating group and constructs standard generators, cf. [[Jambor *et al.*, 2013](../../references.md#cite-altsymrecogn)]. The second part verifies that these elements generate $G$, and constructs isomorphisms between $G$ and $H$, cf. [[Beals *et al.*, 2003](../../references.md#cite-altsymrecog1)]. The implementation of the first part was developed by Sebastian Jambor. The implementation of the second part was developed by Jonathan Conder; he also extended the algorithm to work for both $n \in \{5,\ldots,10\}$ and central extensions. ### `AlternatingOrSymmetricElementToWord(G, g): Grp, GrpElt -> BoolElt, GrpSLPElt` If $g \in G$ and $G$ has been recognised by `RecogniseAlternatingOrSymmetric`, this function returns `true` and an element of the word group for $G$ which evaluates to $g$. Otherwise, it returns `false`. This facilitates membership testing in $G$. The implementation was developed by Jonathan Conder. ### `Example: Recognise Altsym2 (ex-29961f)` We illustrate the use of these functions for a representation of $A_{13}$. ```magma > A:= AlternatingGroup (13); > H:= Stabiliser(A, {1,2}); > G := CosetImage (A, H); > Degree (G); 78 > success, bb_to_perm, perm_to_bb, bb_to_wg, wg_to_bb, is_sym := > RecogniseAlternatingOrSymmetric (G); > > success; true > is_sym; false > > x:= Sym(78)!(1, 35, 16, 28, 14, 26, 69, 5, 74)(2, 54, > 67, 18, 51, 63, 6, 50, 77)(3, 33, 78, 12, 34, 29, 19, 15, 73) > (4, 52, 61, 24, 49, 60, 68, 38, 64)(7, 20, 71, 17, > 32, 11, 72, 8, 36)(9, 76, 47, 31, 56, 62, 13, 53, 59) > (10, 70, 57, 23, 37, 22, 21, 27, 25)(30, 45, 46, 43, 42, > 44, 40, 41, 75)(39, 55, 65)(48, 66, 58); > > flag, w := AlternatingOrSymmetricElementToWord (G, x); > "Is x in G?", flag; Is x in G? true > Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq x; true > > perm_image:= bb_to_perm(x); > perm_image; (1, 4, 9)(2, 6, 3, 5, 10, 7, 8, 11, 12) > > y := Random (G); > w := bb_to_wg (y); > Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq y; true ``` ### `RecogniseSymmetric(G, n: parameters): Grp, RngIntElt -> BoolElt, Map, Map, Map, Map, BoolElt` ```magma maxtries : RngIntElt Default: 100n + 5000 Extension: BoolElt Default: false ``` The group $G$ should be known to be isomorphic to the symmetric group $S_n$ for some $n \ge 8$. The Bratus-Pak algorithm [[Bratus and Pak, 2000](../../references.md#cite-bratus-pak)] (implemented by Derek Holt) is used to define an isomorphism between $G$ and $S_n$. If successful, return `true`, homomorphism from $G$ to $S_n$, homomorphism from $S_n$ to $G$, the map from $G$ to its word group and the map from the word group to $G$. If the optional parameter `Extension` is set, then the group $G$ should be known to be isomorphic either to $S_n$ or to a perfect central extension $2.S_n$. In that case, the first two maps returned will be a homomorphism from $G$ to $S_n$ and a map from $S_n$ to $G$ that induces a homomorphism onto $G/Z(G)$. The sixth value returned will be `true`, if $G \cong 2.S_n$ and `false`, if $G \cong 2.A_n$. If unsuccessful, `false` is returned. This will always occur if the input group is not isomorphic to $S_n$ (or $2.S_n$ when `Extension` is set) with $n \ge 8$, and may occur occasionally even when $G$ is isomorphic to $S_n$. The optional parameter `maxtries` (default $100n + 5000$) can be used to control the number of random elements chosen before giving up. ### `SymmetricElementToWord(G, g): Grp, GrpElt -> BoolElt, GrpSLPElt` If $g$ is an element of $G$ which has been constructively recognised to be isomorphic to $S_n$ (or $2.S_n$), then return `true` and element of word group for $G$ which evaluates to $g$. Otherwise return `false`. This facilitates membership testing in $G$. ### `RecogniseAlternating(G, n: parameters): Grp, RngIntElt -> BoolElt, Map, Map, Map, Map, BoolElt` ```magma maxtries : RngIntElt Default: 100n + 5000 Extension: BoolElt Default: false ``` The group $G$ should be known to be isomorphic to the alternating group $A_n$ for some $n \ge 9$. The Bratus-Pak algorithm [[Bratus and Pak, 2000](../../references.md#cite-bratus-pak)] (implemented by Derek Holt) is used to define an isomorphism between $G$ and $A_n$. If successful, return `true`, homomorphism from $G$ to $A_n$, homomorphism from $A_n$ to $G$, the map from $G$ to its word group and the map from the word group to $G$. If the optional parameter `Extension` is set, then the group $G$ should be known to be isomorphic either to $A_n$ or to a perfect central extension $2.A_n$. In that case, the first two maps returned will be a homomorphism from $G$ to $A_n$ and a map from $A_n$ to $G$ that induces a homomorphism onto $G/Z(G)$. The sixth value returned will be `true`, if $G \cong 2.A_n$ and `false` otherwise. If unsuccessful, `false` is returned. This will always occur if the input group is not isomorphic to $A_n$ (or $2.A_n$ when `Extension` is set) with $n \ge 9$, and may occur occasionally even when $G$ is isomorphic to $A_n$. The optional parameter `maxtries` (default $100n + 5000$) can be used to control the number of random elements chosen before giving up. ### `AlternatingElementToWord(G, g): Grp, GrpElt -> BoolElt, GrpSLPElt` If $g$ is an element of $G$ which has been constructively recognised to be isomorphic to $A_n$ (or $2.A_n$), then return `true` and element of word group for $G$ which evaluates to $g$. Otherwise return `false`. This facilitates membership testing in $G$. ### `GuessAltsymDegree(G: parameters): Grp -> BoolElt, MonStgElt, RngIntElt` ```magma maxtries : RngIntElt Default: 5000 Extension: BoolElt Default: false ``` The group $G$ should be believed to be isomorphic to $S_n$ or $A_n$ for some $n > 6$, or to $2.S_n$ or $2.A_n$ if the optional parameter `Extension` is set. This function attempts to determine $n$ and whether $G$ is symmetric or alternating. It does this by sampling orders of elements. It returns either `false`, if it is unable to make a decision after sampling `maxtries` elements (default $5000$), or `true`, `type` and $n$, where `type` is “Symmetric” or “Alternating”, and $n$ is the degree. If $G$ is not isomorphic to $S_n$ or $A_n$ (or $2.S_n$ or $2.A_n$ when `Extension` is set) for $n > 6$, then the output is meaningless - there is no guarantee that `false` will be returned. There is also a small probability of a wrong result or `false` being returned even when $G$ is $S_n$ or $A_n$ with $n > 6$. This function was written by Derek Holt. ### `Example: Recognise Altsym2 (ex-51196d)` For a group $G$ which is believed to be isomorphic to $S_n$ or $A_n$ for some unknown value of $n > 6$, the function `GuessAltsymDegree` can be used to try to guess $n$, and then `RecogniseSymmetric` or `RecogniseAlternating` can be used to confirm the guess. ```magma > SetSeed(1); > G:= sub< GL(10,5) | > PermutationMatrix(GF(5),Sym(10)![2,3,4,5,6,7,8,9,1,10]), > PermutationMatrix(GF(5),Sym(10)![1,3,4,5,6,7,8,9,10,2]) >; > GuessAltsymDegree(G); true Alternating 10 > flag, m1, m2, m3, m4 := RecogniseAlternating(G,10); > flag; true > x:=Random(G); Order(x); 8 > m1(x); (1, 2, 4, 9, 10, 8, 6, 3)(5, 7) > m2(m1(x)) eq x; true > m4(m3(x)) eq x; true > flag, w := AlternatingElementToWord(G,x); > flag; true > m4(w) eq x; true > y := Random(Generic(G)); > flag, w := AlternatingElementToWord(G,y); > flag; false > flag, m1, m2, m3, m4 := RecogniseAlternating(G,11); > flag; false > flag, m1, m2, m3, m4 := RecogniseSymmetric(G,10); > flag; false ``` The nature of the `GuessAltsymDegree` function is that it assumes that its input is either an alternating or symmetric group and then tries to guess which one and the degree. As such, it is almost always correct when the input is an alternating or symmetric group, but will often return a bad guess when the input group is not of this form, as in the following example. ```magma > GuessAltsymDegree(Sym(50)); true Symmetric 50 > GuessAltsymDegree(Alt(73)); true Alternating 73 > GuessAltsymDegree(PSL(5,5)); true Alternating 82 ```