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)
GAP 3.4.4