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: 0
Proof: BoolElt Default: true
The 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.
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
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.
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
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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|