All group functions for groups described in chapter Group are also applicable to permutation groups. This section describes which functions are implemented specially for permutation groups. Functions not mentioned here are handled by the default methods described in the respective sections.
G ^ p
ConjugateSubgroup( G, p )
Returns the conjugate permutation group of G with the permutation p. p must be an element of the parent group of G. If a stabilizer chain for G is already known, it is also conjugated.
Centralizer( G, U )
Centralizer( G, g )
Normalizer( G, U )
These functions first compute a stabilizer chain for G. If a stabilizer chain is already known a basechange may be performed to obtain a base that is better suited for the problem. These functions then enumerate the elements of G with a backtrack algorithm, eliminating whole cosets of stabilizers in the stabilizer chain if possible (see PermGroupOps.SubgroupProperty). They build a stabilizer chain for the resulting subgroup.
SylowSubgroup( G, p )
If G is not transitive, its p-Sylow subgroup is computed by starting
with P:=G
, and for each transitive constituent homomorphism hom
iterating
P := PreImage( SylowSubgroup( Image( hom, P ), p ) )
.
If G is transitive but not primitive, its p-Sylow subgroup is
computed as
SylowSubgroup( PreImage( SylowSubgroup(Image(hom,G),p) ), p )
.
If G is primitive, SylowSubgroup
takes random elements in G, until
it finds a p-element g, whose centralizer in G contains the whole
p-Sylow subgroup. Such an element must exist, because a p-group has
a nontrivial centre. Then the p-Sylow subgroup of the centralizer is
computed and returned. Note that the centralizer must be a proper
subgroup of G, because it operates imprimitively on the cycles of g.
Coset( U, g )
Returns the coset U*g
. The representative chosen is the
lexicographically smallest element of that coset. It is computed with an
algorithm that is very similar to the backtrack algorithm.
gap> s4 := Group( (1,2,3,4), (1,2) );; s4.name := "s4";; gap> u := Subgroup( s4, [(1,2,3)] );; gap> Coset( u, (1,3,2) ); (Subgroup( s4, [ (1,2,3) ] )*()) gap> Coset( u, (3,2) ); (Subgroup( s4, [ (1,2,3) ] )*(2,3))
Cosets( G, U )
Returns the cosets of U in G. Cosets
first computes stabilizer
chains for G and U with a common base. If either subgroup already
has a stabilizer chain, a basechange is performed (see MakeStabChain).
A transversal is computed recursively using the fact that if S is a
transversal of U^{(2)} = Stab_U(b_1) in G^{(2)} = Stab_G(b_1), and
R^{(1)} is a transversal of G^{(2)} in G, then a transversal of U
in G is a subset of S * R^{(1)}.
gap> Cosets( s4, u ); [ (Subgroup( s4, [ (1,2,3) ] )*()), (Subgroup( s4, [ (1,2,3) ] )*(3,4)), (Subgroup( s4, [ (1,2,3) ] )*(2,3)), (Subgroup( s4, [ (1,2,3) ] )*(2,3,4)), (Subgroup( s4, [ (1,2,3) ] )*(2,4,3)), (Subgroup( s4, [ (1,2,3) ] )*(2,4)), (Subgroup( s4, [ (1,2,3) ] )*(1,2,3,4)), (Subgroup( s4, [ (1,2,3) ] )*(1,2,4)) ]
PermutationCharacter( P )
Computes the character of the natural permutation representation of P,
i.e. it does the same as PermutationCharacter( P, {rm Stab}_P(1) )
but works much faster.
gap> G := SymmetricPermGroup(5);; gap> PermutationCharacter(G); [ 5, 3, 1, 2, 0, 1, 0 ]
ElementaryAbelianSeries( G )
This function builds an elementary abelian series of G by iterated
construction of normal closures. If a partial elementary abelian series
reaches up to a subgroup U of G which does not yet contain the
generator s of G then the series is extended up to the normal closure
N of U and s. If the factor N/U
is not elementary abelian,
i.e., if some commutator of s with one of its conjugates under G does
not lie in U, intermediate subgroups are calculated recursively by
extending U with that commutator. If G is solvable this process must
come to an end since commutators of arbitrary depth cannot exist in
solvable groups.
Hence this method gives an elementary abelian series if G is solvable
and gives an infinite recursion if it is not. For permutation groups,
however, there is a bound on the derived length that depends only on the
degree d of the group. According to Dixon this is (5 log_3(d))/2. So
if the commutators get deeper than this bound the algorithm stops and
sets G.isSolvable
to false
, signalling an error. Otherwise
G.isSolvable
is set to true
and the elementary abelian series is
returned as a list of subgroups of G.
gap> S := Group( (1,2,3,4), (1,2) );; S.name := "s4";; gap> ElementaryAbelianSeries( S ); [ Subgroup( s4, [ (1,2), (1,3,2), (1,4)(2,3), (1,2)(3,4) ] ), Subgroup( s4, [ (1,3,2), (1,4)(2,3), (1,2)(3,4) ] ), Subgroup( s4, [ (1,4)(2,3), (1,2)(3,4) ] ), Subgroup( s4, [ ] ) ] gap> A := Group( (1,2,3), (3,4,5) );; gap> ElementaryAbelianSeries( A ); Error, <G> must be solvable
IsSolvable( G )
Solvability of a permutation group G is tested by trying to construct
an elementary abelian series as described above. After this has been
done the flag G.isSolvable
is set correctly, so its value is
returned.
gap> S := Group( (1,2,3,4), (1,2) );; gap> IsSolvable( S ); true gap> A := Group( (1,2,3), (3,4,5) );; gap> IsSolvable( A ); false
CompositionSeries( G )
A composition series for the solvable group G is calculated either from
a given subnormal series, which must be bound to G.subnormalSeries
,
in which case G.bssgs
must hold the corresponding base-strong
subnormal generating system, or from an elementary abelian series (as
computed by ElementaryAbelianSeries( G )
above) by inserting
intermediate subgroups (i.e. powers of the polycyclic generators or
composition series along bases of the vector spaces in the elementary
abelian series). In either case, after execution of this function,
G.bssgs
holds a base-strong pag system corresponding to the
composition series calculated.
gap> S := Group( (1,2,3,4), (1,2) );; S.name := "s4";; gap> CompositionSeries( S ); [ Subgroup( s4, [ (1,2), (1,3,2), (1,4)(2,3), (1,2)(3,4) ] ), Subgroup( s4, [ (1,3,2), (1,4)(2,3), (1,2)(3,4) ] ), Subgroup( s4, [ (1,4)(2,3), (1,2)(3,4) ] ), Subgroup( s4, [ (1,2)(3,4) ] ), Subgroup( s4, [ ] ) ]
If G is not solvable then a composition series cs is computed with an
algorithm by A. Seress and R. Beals. In this case the factor group of
each element cs[i]
in the composition series modulo the next one
cs[i+1]
are represented as primitive permutation groups. One
should call cs[i].operations.FactorGroup( cs[i], cs[i+1] )
directly to avoid the check in FactorGroup
that cs[i+1]
is normal
in cs[i]
. The natural homomorphism of cs[i]
onto this factor
group will be given as a GroupHomomorphismByImages
(see
GroupHomomorphismByImages).
gap> pyl29 := Group( (1,2,3)(4,5,6)(7,8,9), (2,6,4,9,3,8,7,5), > (4,7)(5,8)(6,9), (1,10)(4,7)(5,6)(8,9) );; gap> pyl29.name := "pyl29";; gap> cs := CompositionSeries( pyl29 ); [ Subgroup( pyl29, [ (1,9,5)(2,7,6)(3,8,4), (2,7,3,4)(5,8,9,6), ( 1, 2,10)( 4, 9, 5)( 6, 8, 7), (2,6,4,9,3,8,7,5), (4,7)(5,8)(6,9) ] ), Subgroup( pyl29, [ (1,9,5)(2,7,6)(3,8,4), (2,7,3,4)(5,8,9,6), ( 1, 2,10)( 4, 9, 5)( 6, 8, 7), (2,6,4,9,3,8,7,5) ] ), Subgroup( pyl29, [ (1,9,5)(2,7,6)(3,8,4), (2,7,3,4)(5,8,9,6), ( 1, 2,10)( 4, 9, 5)( 6, 8, 7) ] ), Subgroup( pyl29, [ ] ) ] gap> List( [1..3], i->cs[i].operations.FactorGroup(cs[i],cs[i+1]) ); [ Group( (1,2) ), Group( (1,2) ), Group( (1,9,5)(2,7,6)(3,8,4), (2,7,3,4)(5,8,9,6), ( 1, 2,10) ( 4, 9, 5)( 6, 8, 7) ) ] gap> List( last, Size ); [ 2, 2, 360 ]
ExponentsPermSolvablePermGroup( G, perm [, start ] )
ExponentsPermSolvablePermGroup
returns a list e, such that perm =
G.bssgs[1]^e[1] * G.bssgs[2]^e[2] * ... *
G.bssgs[n]^e[n]
, where G.bssgs
must be a prime-step
base-strong subnormal generating system as calculated by
ElementaryAbelianSeries
(see ElementaryAbelianSeries and above). If
the optional third argument start is given, the list entries
exps[1], ..., exps[start-1]
are left unbound and the element
perm is decomposed as product of the remaining pag generators
G.bssgs[start], ..., G.bssgs[n]
.
gap> S := Group( (1,2,3,4), (1,2) );; S.name := "s4";; gap> ElementaryAbelianSeries( S );; gap> S.bssgs; [ (1,2), (1,3,2), (1,4)(2,3), (1,2)(3,4) ] gap> ExponentsPermSolvablePermGroup( S, (1,2,3) ); [ 0, 2, 0, 0 ]
AgGroup( G )
This function converts a solvable permutation group into an ag group. It
calculates an elementary abelian series and a prime-step bssgs for G
(see ElementaryAbelianSeries
above) and then finds the relators
belonging to this prime-step bssgs using the function
ExponentsPermSolvablePermGroup
(see above). An isomorphism from the ag
group to the permutation group is bound to AgGroup( G ).bijection
.
gap> G := WreathProduct( SymmetricGroup( 4 ), CyclicGroup( 3 ) );; gap> A := AgGroup( G ); Group( g1, g2, g3, g4, g5, g6, g7, g8, g9, g10, g11, g12, g13 ) gap> (A.1*A.3)^A.bijection; ( 1, 6,10, 2, 5, 9)( 3, 7,11)( 4, 8,12)
DirectProduct( G, H )
If G and H are both permutation groups, DirectProduct
constructs the
direct product of G and H as an intransitive permutation group. There are
special routines for Centre
, Centralizer
and SylowSubgroup
for such
groups that will work faster than the standard permutation group functions.
These functions are DirectProductPermGroupCentre
,
DirectProductPermGroupCentralizer
and DirectProductPermGroupSylowSubgroup
.
You can enforce that these routines will be always used for direct products
of permutation groups by issuing the following three commands (They are not
performed by standard as the code has not been well-tested).
gap> DirectProductPermGroupOps.Centre:=DirectProductPermGroupCentre;; gap> DirectProductPermGroupOps.Centralizer:= > DirectProductPermGroupCentralizer;; gap> DirectProductPermGroupOps.SylowSubgroup:= > DirectProductPermGroupSylowSubgroup;;
GAP 3.4.4