|
Here we look at conjugacy classes of the group G. When the classes of G are
stored they will be ordered so that the element orders are increasing and,
second to this, by increasing class length. Apart from this the ordering is
random. If the user chooses to assert conjugacy classes the ordering must
agree with this ordering. Once the ordering of classes for a particular group
is set, it may not be changed.
Conjugates(H, x) : GrpPerm, GrpPermElt -> { GrpPermElt }
Given a group H and an element x belonging to a group K
such that H and K are subgroups of the same symmetric group,
this function returns the set of conjugates of x under the
action of H. If H = K, the function returns the conjugacy
class of x in H.
Classes(G: parameters) : GrpPerm -> [ <RngIntElt, RngIntElt, GrpPermElt> ]
Construct a set of representatives for the conjugacy classes of G.
The classes are returned as a sequence of triples containing the
element order, the class length and a representative element for the
class. The parameters Reps and Al enable the user to select
the algorithm that is to be used.
Reps: [ GrpPermElt ] Default:
Reps := Q: Create the classes of G by using the random algorithm
but using the group elements in Q as the "random" elements tried.
The element orders and lengths of the classes will be computed and checked
for consistency. Note that this function may re-order the given elements.
Reps: [ <GrpPermElt, RngIntElt> ] Default:
Reps := Q Create the classes of G assuming that the first
elements of the tuples in Q form a complete set
of conjugacy class representatives and the corresponding integer is the
size of the conjugacy class. The only check performed is that the class
sizes sum to the group order.
Al: MonStgElt Default: em "Default"
WeakLimit: RngIntElt Default: 500
StrongLimit: RngIntElt Default: 5000
Al := "Action": Create the classes of G by computing the orbits
of the set of elements of G under the action of conjugation. This option
is only feasible for small groups.
Al := "Random": Construct the conjugacy classes of elements for
a permutation group G using an algorithm that searches for
representatives of all conjugacy classes of G by examining a random
selection of group elements and their powers. The behaviour of this
algorithm is controlled by two associated optional parameters WeakLimit and StrongLimit, whose values are positive integers
n1 and n2, say. Before describing the effect of these
parameters, some definitions are needed: A mapping f: G -> I
is called a class invariant if f(g) = f(gh) for all g, h∈G.
For permutation groups, the cycle structure of g is a readily
computable class invariant. Two elements g and h are said to be
weakly conjugate with respect to the class invariant f if
f(g) = f(h). By definition, conjugacy implies weak conjugacy, but the
converse is false. The random algorithm first examines n1 random
elements and their powers, using a test for weak conjugacy. It then
proceeds to examine a further n2 random elements and their powers,
using a test for ordinary conjugacy. The idea behind this strategy is
that the algorithm should attempt to find as many classes as possible
using the very cheap test for weak conjugacy, before employing the more
expensive ordinary conjugacy test to recognize the remaining classes.
Al := "Inductive": Use G. Butler's inductive method to compute the
classes. See Butler [But94] for a description of the
algorithm. The action and random algorithms are used by this algorithm to
find the classes of any small groups it is called upon to deal with.
Al := "Extend": Construct the conjugacy classes of G by first
computing classes in a quotient G/N and then extending these classes
to successively larger quotients G/H until the classes for G/1 are
known. More precisely, a series of subgroups 1 = G0 < G1 < ... < Gr = R < G is computed such that R is the (solvable)
radical of G and Gi + 1/Gi is elementary abelian. The radical
quotient G/R is computed and its classes and centralizers of their
representatives found and pulled back to G.
The parameters TFAl and ASAl control the algorithm
used to compute the classes of G/R.
To extend from G/Gi + 1 to the next larger quotient G/Gi, an affine
action of each centralizer on a quotient of the elementary abelian layer
Gi + 1/Gi is computed. Each distinct orbit in that action gives rise
to a new class of the larger quotient
(see Mecky and Neubuser [MN89]).
Al := "Default": First some special cases are checked for:
If IsAltsym(G)
then the classes of G are computed from the partitions of Degree(G).
If G is solvable, an isomorphic representation of G as a pc-group is
computed and the classes computed in that representation.
In general, the action algorithm will be used if |G|≤5000,
otherwise the extension algorithm will be applied.
TFAl: MonStgElt Default: em "Default"
This parameter controls the algorithm used to compute the classes of
a group with trivial Fitting subgroup, such as the group G/R in the
description of the "Extend" method. The possible settings are the same
as for Al, except that "Extend" is not a valid choice.
The "Action", "Random" and "Inductive settings behave
as described above. The default algorithm is Derek Holt's generalisation
of the Cannon/Souvignier fusion method to all classes of the group.
The original fusion algorithm used fusion only on classes within a
direct product normal subgroup, see [CS97]. Holt has
extended the use of fusion to all conjugacy classes, avoiding the random
part of the Cannon/Souvignier method. This algorithm must use another algorithm
to find the classes of almost simple groups arising from the socle of the
TF-group. The algorithm used for this is controlled by the parameter ASAl.
ASAl: MonStgElt Default: em "Default"
This parameter controls the algorithm used to compute the classes of
an almost simple group from within the default TF-group algorithm.
The possibilities for this parameter are as for TFAl. The default
algorithm first determines if Altsym(G) is true. If so, classes
are deduced from the partitions of Degree(G). Next, if the order of G
is ≤5000 then the action algorithm is used. If the socle
of G has the correct order to be PSL(2, q), for some q, then
the random algorithm is used on G. Otherwise the inductive
algorithm is used.
Centralisers: BoolElt Default: false
A flag to force the storing of the centralisers of the class representatives
with the class table. This does not apply to the action algorithm.
In the case of the extension algorithm, this will do extra work to lift
the centralisers through the final elementary abelian layer.
PowerMap: BoolElt Default: false
A flag to force the storing of whatever power map information is produced
by the classes algorithm used. In the case of the extension algorithm, this
flag forces the computation of the full power map en-route, and may take
considerably longer than not doing so. However, it is overall faster
to set this flag true when the PowerMap is going to be computed
anyway.
ClassRepresentative(G, i) : GrpPerm, RngIntElt -> GrpPermElt
Given a group G for which the conjugacy classes are known,
return the stored representative for
the conjugacy class of G containing x or the stored
representative of conjugacy class i.
ClassCentralizer(G, i) : GrpPerm, RngIntElt -> GrpPerm
The centraliser of the representative element stored for conjugacy class
number i in group G. The group computed is stored with the class
table for reference by future calls to this function.
Given a group G, construct the conjugacy classes and the class map f
for G. For any element x of G, f(x) will be the index of the
conjugacy class of x in the sequence returned by the Classes function.
If the parameter Orbits
is set true, the classes are computed as orbits of elements under
conjugation
and the class map is stored as a list of images of the elements
of G (a list of length |G|). This option gives fast evaluation
of the class map but is practical only in the case of very small groups.
With Orbits := false, WeakLimit and StrongLimit are
used to control the random classes algorithm (see function Classes).
Given a group G and elements g and h belonging to G,
return the value true if g and h are conjugate in G. The
function returns a second value if the elements
are conjugate: an element k which conjugates g into h.
The method used is the backtrack search of Leon [Leo97].
This search may be speeded considerably by knowledge of (subgroups of) the
centralizers of g and h in G. The parameters relate to these subgroups.
Centralizer: MonStgElt Default: em "Default"
LeftSubgroup: GrpPerm Default: < g >
RightSubgroup: GrpPerm Default: < h >
The LeftSubgroup and RightSubgroup parameters
enable the user to supply
known subgroups of the centralizers of g and h respectively to the
algorithm. By default, the cyclic subgroups generated by g and h are
the known subgroups.
The Centralizer parameter controls whether the algorithm
starts by computing one or both centralizers in full before the conjugacy test.
The "Default" behaviour is to compute the left centralizer, i.e. CG(g),
unless either a left or right subgroup is specified, in which case no centralizer
calculation is done. Other possible values are the four possibilities
"Left" which forces computation of CG(g), "Right" which forces
CG(h) to be computed, "Both" which computes both centralizers, and
"None" which will compute no centralizers.
Given a group G and subgroups H and K of G,
return the value true if H and K are conjugate in G. The
function returns a second value if the subgroups
are conjugate: an element z which conjugates H into K.
The method used is the backtrack search of Leon [Leo97].
Compute: MonStgElt Default: em "Default"
This parameter may be set to any of "Both", "Default", "Left", "None", or
"Right". This controls which normalisers are computed before starting the
conjugacy test. The default strategy is currently "Left", which computes the
normalizer of H in G before starting the conjugacy test between H
and K. The greater the difference between H and K and their normalizers
in G, the more helpful to the search it is to compute their normalizers.
LeftSubgroup: GrpPerm Default: H
RightSubgroup: GrpPerm Default: K
Instead of having the IsConjugate function compute the normalizers
of H and K, the user may supply any known subgroup of G normalizing
H (as LeftSubgroup) or normalizing K (as RightSubgroup)
to be used as the normalizing groups to aid the search.
The exponent of the group G. This is computed as the product
of the exponents of the Sylow subgroups fo G.
Nclasses(G) : GrpPerm -> RngIntElt
The number of conjugacy classes of elements for the group G.
Given a group G, construct the power map for G. Suppose that the order
of G is m and that G has r conjugacy classes. When the classes
are determined by Magma, they are numbered from 1 to r. Let C be
the set of class indices { 1, ..., r } and let Z be the
set of integers. The power map f for G is the mapping
f : C x Z -> C
where the value of f(i, j) for i ∈C and j ∈Z
is the number of the class which contains xij,
where xi is a representative of the i-th conjugacy class.
An alternative form for setting this attribute is G`Classes := Q;.
Assert the class representatives of G.
If Q is a sequence of group elements then the action taken is identical to
using the ConjugacyClasses function described above, with the
parameter Reps set to Q.
If Q is a sequence of triples
< a, ell, x > then it is assumed to be the full class table,
each x has order a, and the class length of x in G is ell.
This assertion sets the class table with classes in the order as given by Q,
so this order must agree with the conventions of increasing element order
and then increasing class length.
The conjugacy classes of the Mathieu group M 11 can be
constructed as follows:
> SetSeed(2);
> M11 := sub<Sym(11) | (1,10)(2,8)(3,11)(5,7), (1,4,7,6)(2,11,10,9)>;
> Classes(M11);
Conjugacy Classes of group M11
------------------------------
[1] Order 1 Length 1
Rep Id(M11)
[2] Order 2 Length 165
Rep (3, 10)(4, 9)(5, 6)(8, 11)
[3] Order 3 Length 440
Rep (1, 2, 4)(3, 5, 10)(6, 8, 11)
[4] Order 4 Length 990
Rep (3, 6, 10, 5)(4, 8, 9, 11)
[5] Order 5 Length 1584
Rep (1, 3, 6, 2, 8)(4, 7, 10, 9, 11)
[6] Order 6 Length 1320
Rep (1, 11, 2, 6, 4, 8)(3, 10, 5)(7, 9)
[7] Order 8 Length 990
Rep (1, 4, 5, 6, 2, 7, 11, 10)(8, 9)
[8] Order 8 Length 990
Rep (1, 7, 5, 10, 2, 4, 11, 6)(8, 9)
[9] Order 11 Length 720
Rep (1, 11, 9, 10, 4, 3, 7, 2, 6, 5, 8)
[10] Order 11 Length 720
Rep (1, 9, 4, 7, 6, 8, 11, 10, 3, 2, 5)
The default values for the random class algorithm are
adequate for a large variety of groups. We look at what happens when we vary
the parameters in the case of the Higman-Sims simple group represented
on 100 letters. In this case the default strategy reduces to a random search.
The first choice of parameters does not look at enough
random elements. Increasing the limit on the number of random elements
examined will ensure the algorithm succeeds.
> G := sub<Sym(100) |
> (2,8,13,17,20,22,7)(3,9,14,18,21,6,12)(4,10,15,19,5,11,16)
> (24,77,99,72,64,82,40)(25,92,49,88,28,65,90)(26,41,70,98,91,38,75)
> (27,55,43,78,86,87,45)(29,69,59,79,76,35,67)(30,39,42,81,36,57,89)
> (31,93,62,44,73,71,50)(32,53,85,60,51,96,83)(33,37,58,46,84,100,56)
> (34,94,80,61,97,48,68)(47,95,66,74,52,54,63),
> (1,35)(3,81)(4,92)(6,60)(7,59)(8,46)(9,70)(10,91)(11,18)(12,66)(13,55)
> (14,85)(15,90)(17,53)(19,45)(20,68)(21,69)(23,84)(24,34)(25,31)(26,32)
> (37,39)(38,42)(40,41)(43,44)(49,64)(50,63)(51,52)(54,95)(56,96)(57,100)
> (58,97)(61,62)(65,82)(67,83)(71,98)(72,99)(74,77)(76,78)(87,89) >;
> K := Classes(G:WeakLimit := 20, StrongLimit := 50);
Runtime error in 'Classes': Random classes algorithm failed
> K := Classes(G: WeakLimit := 20, StrongLimit := 100);
> NumberOfClasses(G);
24
As the group has only 24 classes, the first random search could have
succeeded by looking at 50 elements. On this occasion it did not, but
looking at 100 elements did succeed.
We print the order, length and cycle structure for each conjugacy class.
> [ < k[1], k[2], CycleStructure(k[3]) > : k in K ];
[
<1, 1, [ <1, 100> ]>,
<2, 5775, [ <2, 40>, <1, 20> ]>,
<2, 15400, [ <2, 50> ]>,
<3, 123200, [ <3, 30>, <1, 10> ]>,
<4, 11550, [ <4, 20>, <2, 10> ]>,
<4, 173250, [ <4, 20>, <2, 6>, <1, 8> ]>,
<4, 693000, [ <4, 20>, <2, 8>, <1, 4> ]>,
<5, 88704, [ <5, 20> ]>,
<5, 147840, [ <5, 20> ]>,
<5, 1774080, [ <5, 19>, <1, 5> ]>,
<6, 1232000, [ <6, 15>, <2, 5> ]>,
<6, 1848000, [ <6, 12>, <3, 6>, <2, 4>, <1, 2> ]>,
<7, 6336000, [ <7, 14>, <1, 2> ]>,
<8, 2772000, [ <8, 10>, <4, 4>, <2, 2> ]>,
<8, 2772000, [ <8, 10>, <4, 3>, <2, 3>, <1, 2> ]>,
<8, 2772000, [ <8, 10>, <4, 4>, <2, 2> ]>,
<10, 2217600, [ <10, 8>, <5, 4> ]>,
<10, 2217600, [ <10, 10> ]>,
<11, 4032000, [ <11, 9>, <1, 1> ]>,
<11, 4032000, [ <11, 9>, <1, 1> ]>,
<12, 3696000, [ <12, 6>, <6, 3>, <4, 2>, <2, 1> ]>,
<15, 2956800, [ <15, 6>, <5, 2> ]>,
<20, 2217600, [ <20, 4>, <10, 2> ]>,
<20, 2217600, [ <20, 4>, <10, 2> ]>
]
We construct the power map and tabulate the second, third and fifth
powers of each class.
> p := PowerMap(G);
> [ < i, p(i, 2), p(i, 3), p(i, 5) > : i in [1 .. #K] ];
[
<1, 1, 1, 1>,
<2, 1, 2, 2>,
<3, 1, 3, 3>,
<4, 4, 1, 4>,
<5, 2, 5, 5>,
<6, 2, 6, 6>,
<7, 2, 7, 7>,
<8, 8, 8, 1>,
<9, 9, 9, 1>,
<10, 10, 10, 1>,
<11, 4, 3, 11>,
<12, 4, 2, 12>,
<13, 13, 13, 13>,
<14, 7, 14, 14>,
<15, 6, 15, 15>,
<16, 7, 16, 16>,
<17, 8, 17, 2>,
<18, 9, 18, 3>,
<19, 20, 19, 19>,
<20, 19, 20, 20>,
<21, 12, 5, 21>,
<22, 22, 9, 4>,
<23, 17, 23, 5>,
<24, 17, 24, 5>
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|