|
There are three aspects of the conjugacy problem for elements: determining
whether two elements are conjugate in a group G, determining a set of
representatives for the conjugacy classes of elements of G, and listing
all the elements in a particular class of G. The algorithms used depend on
the category of G. If G is in category GrpPerm or GrpMat,
conjugacy is determined by means of a backtrack search over base-images.
If G is in category GrpPC, testing conjugacy is performed
by transforming each element into a standard representative of its conjugacy
class by an orbit-stabilizer process that works down a sequence of
increasing quotients of G. Conjugacy testing for a group G in category
GrpGPC is only possible if G is nilpotent. In this case, an algorithm
by E. Lo [Lo98] is used.
Some functions described in this section may not exist or may have restrictions
for some categories of groups. Details can be found in the chapters on the
individual categories.
Conjugates(H, x) : GrpFin, GrpFinElt -> { GrpFinElt }
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.
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 G is a permutation group, the construction may be controlled
using the parameters Orbits, WeakLimit and StrongLimit.
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).
Classes(G: parameters) : GrpFin -> [ <RngIntElt, RngIntElt, GrpFinElt> ]
WeakLimit: RngIntElt Default: 200
StrongLimit: RngIntElt Default: 500
Reps: [ GrpFinElt ] Default:
Al: MonStg Default:
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 when G is a permutation or matrix
group.
Reps := Q: Create the classes of G by assuming that Q is
a sequence of class representatives for G. The orders and lengths of
the classes will be computed and checked for consistency.
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 or matrix 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. In matrix groups, the primary invariant
factors are used where possible, or the characteristic or minimal
polynomials otherwise. 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 := "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 maximal 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. A
representation of G/R is computed using an algorithm of Derek Holt
and its classes computed and represented as elements of G. To extend
to the next larger quotient, a group is computed from each class which
acts on the transversal. Each distinct orbit in that action gives rise
to a new class.
To compute the classes of G/R, the default algorithm (excluding the
extension method) is used. The same set of parameters is passed on, so
you can control limits in the random classes method if it is chosen.
The limitations of the algorithm are that R may be trivial, in which
case nothing is done except to call a different algorithm, or one or
more of the sections may be so large as to prohibit computing the
action on the transversal.
This algorithm is currently only available for permutation groups.
Return the sequence of pairs giving element orders and class lengths of the
group G. This uses the same algorithms as the Classes function, with
the same parameters, to compute the classes and their representatives, but only
returns the basic data of orders and lengths. The class representatives are
stored within the group structure, just as with the Classes function.
Given a group G for which the conjugacy classes are known and
an element x of G, return the designated representative for
the conjugacy class of G containing x.
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.
Given a group G and subgroups H and K belonging to G,
return the value true if G and H are conjugate in G. The
function returns a second value if the subgroups
are conjugate: an element z which conjugates H into K.
The exponent of the group G.
Nclasses(G) : GrpFin -> 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 }.
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.
The conjugacy classes of the Mathieu group M 11 can be
constructed as follows:
> 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)
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|