21.16 PermGroupOps.ElementProperty

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

PermGroupOps.ElementProperty returns an element g in the permutation group 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. If G has no such element, false is returned.

    gap> V4 := Group((1,2),(3,4));;
    gap> PermGroupOps.ElementProperty( V4, g -> (1,2)^g = (3,4) );
    false 

PermGroupOps.ElementProperty first computes a stabilizer chain for G, if necessary. Then it performs a backtrack search through G for an element satisfying prop, i.e., enumerates all elements of G as described in section Stabilizer Chains, and applies prop to each until one element g is found for which prop(g) is true. This algorithm is described in detail in But82.

    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> U := V ^ (1,2,3,4)(5,6,7,8);;
    gap> PermGroupOps.ElementProperty( S8, g -> U ^ g = V );
    (1,4,2)(5,6)    # another permutation conjugating <U> to <V> 

This search will of course take quite a while if G is large, especially if no element of G satisfies prop, and therefore all elements of G must be tried.

To speed up the computation you may pass a subgroup K of G as optional third argument. This subgroup must preserve prop in the sense that either all elements of a left coset g*K satisfy prop or no element of g*K does.

In our example above such a subgroup is the normalizer N_G(V) because h in g N_G(V) takes U to V if and only if g does. Of course every subgroup of N_G(V) has this property too. Below we use the subgroup V itself. In this example this speeds up the computation by a factor of 4.

    gap> K := Subgroup( S8, V.generators );;
    gap> PermGroupOps.ElementProperty( S8, g -> U ^ g = V, K );
    (1,4,2)(5,6) 

In the following example, we use the same subgroup, but with a larger generating system. This speeds up the computation by another factor of 3. Something like this may happen frequently. The reason is too complicated to be explained here.

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

Passing the full normalizer speeds up the computation in this example by another factor of 2. Beware though that in other examples the computation of the normalizer alone may take longer than calling PermGroupOps.ElementProperty with only the subgroup itself as argument.

    gap> N := Normalizer( S8, V );
    Subgroup( S8, [ (1,2), (1,2,3), (6,7), (6,7,8), (2,3), (7,8),
      (1,6)(2,7)(3,8), (4,5) ] )
    gap> Size( N );
    144
    gap> PermGroupOps.ElementProperty( S8, g -> U ^ g = V, N );
    (1,4)(5,6) 

Previous Up Top Next
Index

GAP 3.4.4
April 1997