Group Recognition#

Constructive Recognition of Alternating Groups#

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-98afe7)#

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

Group Recognition#

Constructive Recognition of Alternating Groups#

Determining the Type of a Finite Group of Lie Type#

Classical Forms#

Recognizing Classical Groups in their Natural Representation#

Constructive Recognition of Linear Groups#

Constructive Recognition of Symplectic Groups#

Constructive Recognition of Unitary Groups#

Recognition Of Classical Groups in Low Degree#

Constructive Recognition of Suzuki Groups#

Introduction#

Recognition Functions#

Constructive Recognition of Small Ree Groups#

Introduction#

Recognition Functions#

Constructive Recognition of Large Ree Groups#

Introduction#

Recognition Functions#