21.17 PermGroupOps.SubgroupProperty

PermGroupOps.SubgroupProperty( G, prop )
PermGroupOps.SubgroupProperty( G, prop, K )

PermGroupOps.SubgroupProperty returns the subgroup U of the permutation group G of all elements in G that satisfy prop, i.e., the subgroup of all elements g in G such that prop(g) is true. prop must be a function of one argument that returns either true or false when applied to an element of G. Of course the elements that satisfy prop must form a subgroup of G. PermGroupOps.SubgroupProperty builds a stabilizer chain for U.

    gap> S8 := Group( (1,2), (1,2,3,4,5,6,7,8) );;  S8.name := "S8";;
    gap> Size(S8);
    40320
    gap> V := Subgroup( S8, [(1,2),(1,2,3),(6,7),(6,7,8)] );;
    gap> Size(V);
    36
    gap> PermGroupOps.SubgroupProperty( S8, g -> V ^ g = V );
    Subgroup( S8, [ (7,8), (6,7), (4,5), (2,3)(4,5)(6,8,7), (1,2),
      (1,6,3,8)(2,7) ] )
    # the normalizer of 'V' in 'S8' 

PermGroupOps.SubgroupProperty first computes a stabilizer chain for G, if necessary. Then it performs a backtrack search through G for the elements satisfying prop, i.e., enumerates all elements of G as described in section Stabilizer Chains, and applies prop to each, adding elements for which prop(g) is true to the subgroup U. Once U has become non-trivial, it is used to eliminate whole cosets of stabilizers in the stabilizer chain of G if they cannot contain elements with the property prop that are not already in U. This algorithm is described in detail in But82.

This search will of course take quite a while if G is large. To speed up the computation you may pass a subgroup K of U as optional third argument.

Passing the subgroup V itself, speeds up the computation in this example by a factor of 2.

    gap> K := Subgroup( S8, V.generators );;
    gap> PermGroupOps.SubgroupProperty( S8, g -> V ^ g = V, K );
    Subgroup( S8, [ (1,2), (1,2,3), (6,7), (6,7,8), (2,3), (7,8), (4,5),
      (1,6,3,8)(2,7) ] ) 

Previous Up Top Next
Index

GAP 3.4.4
April 1997