21.21 Group Functions for Permutation Groups

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;;

Previous Up Top Next
Index

GAP 3.4.4
April 1997