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.
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 [CB92].
Returns true if the permutation group G defined as acting on X is the alternating group Alt(X).
Returns true if the permutation group G defined as acting on X is the symmetric group Sym(X).
Returns true if the permutation group G defined as acting on X contains the alternating group Alt(X).Limit: RngIntElt Default: 0Proof: BoolElt Default: trueThe Limit argument controls the number of random elements of the group inspected in an attempt to show that the group does contain 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.
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 [CC91].
Given a permutation group G check if G is even, ie. contained in the alternating group.
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 ≥5. Note that G can be either a matrix or permutation representation of H.The algorithm used is that of [JLNP13]. 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 ≥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. [BLGN+03]. Otherwise, the algorithm employed for this map is that of [BP00], 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. [JLNP13]. The second part verifies that these elements generate G, and constructs isomorphisms between G and H, cf. [BLGN+03]. 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 ∈{5, ..., 10} and central extensions.
If g ∈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.
> 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
maxtries: RngIntElt Default: 100n + 5000
Extension: BoolElt Default: false
The group G should be known to be isomorphic to the symmetric group Sn for some n ≥8. The Bratus-Pak algorithm [BP00] (implemented by Derek Holt) is used to define an isomorphism between G and Sn. If successful, return true, homomorphism from G to Sn, homomorphism from Sn 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 Sn or to a perfect central extension 2.Sn. In that case, the first two maps returned will be a homomorphism from G to Sn and a map from Sn to G that induces a homomorphism onto G/Z(G). The sixth value returned will be true, if G isomorphic to 2.Sn and false, if G isomorphic to 2.An.
If unsuccessful, false is returned. This will always occur if the input group is not isomorphic to Sn (or 2.Sn when Extension is set) with n ≥8, and may occur occasionally even when G is isomorphic to Sn. The optional parameter maxtries (default 100n + 5000) can be used to control the number of random elements chosen before giving up.
If g is an element of G which has been constructively recognised to be isomorphic to Sn (or 2.Sn), then return true and element of word group for G which evaluates to g. Otherwise return false. This facilitates membership testing in G.
maxtries: RngIntElt Default: 100n + 5000
Extension: BoolElt Default: false
The group G should be known to be isomorphic to the alternating group An for some n ≥9. The Bratus-Pak algorithm [BP00] (implemented by Derek Holt) is used to define an isomorphism between G and An. If successful, return true, homomorphism from G to An, homomorphism from An 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 An or to a perfect central extension 2.An. In that case, the first two maps returned will be a homomorphism from G to An and a map from An to G that induces a homomorphism onto G/Z(G). The sixth value returned will be true, if G isomorphic to 2.An and false otherwise.
If unsuccessful, false is returned. This will always occur if the input group is not isomorphic to An (or 2.An when Extension is set) with n ≥9, and may occur occasionally even when G is isomorphic to An. The optional parameter maxtries (default 100n + 5000) can be used to control the number of random elements chosen before giving up.
If g is an element of G which has been constructively recognised to be isomorphic to An (or 2.An), then return true and element of word group for G which evaluates to g. Otherwise return false. This facilitates membership testing in G.
maxtries: RngIntElt Default: 5000
Extension: BoolElt Default: false
The group G should be believed to be isomorphic to Sn or An for some n > 6, or to 2.Sn or 2.An 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 Sn or An (or 2.Sn or 2.An 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 Sn or An with n > 6. This function was written by Derek Holt.
> 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.
> GuessAltsymDegree(Sym(50)); true Symmetric 50 > GuessAltsymDegree(Alt(73)); true Alternating 73 > GuessAltsymDegree(PSL(5,5)); true Alternating 82