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.
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.
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: 500StrongLimit: RngIntElt Default: 5000Al := "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: falseA 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: falseA 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.
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.
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: HRightSubgroup: GrpPerm Default: KInstead 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.
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.
> 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>
]