Identification

Identification as an Abstract Group

NameSimple(G): GrpPerm -> <RngIntElt, RngIntElt, RngIntElt>

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].

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

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].

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

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]. 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]. Otherwise, the algorithm employed for this map is that of [Bratus and Pak, 2000], 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]. The second part verifies that these elements generate \(G\), and constructs isomorphisms between \(G\) and \(H\), cf. [Beals et al., 2003]. 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}\).

> 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

Run in calculatorCopy input

RecogniseSymmetric(G, n: parameters): Grp, RngIntElt -> BoolElt, Map, Map, Map, Map, BoolElt

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] (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

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] (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

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.

> 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

Run in calculatorCopy input

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.

> GuessAltsymDegree(Sym(50));
true Symmetric 50
> GuessAltsymDegree(Alt(73));
true Alternating 73
> GuessAltsymDegree(PSL(5,5));
true Alternating 82

Run in calculatorCopy input