7 Searching in groups and orbits
  
  
  7.1 Searching using orbit enumeration
  
  As described in Subsection 3.1-4 the standard orbit enumeration routines can
  perform  search operations during orbit enumeration. If one is looking for a
  shortest word in the generators of a group to express a group element with a
  certain  property,  then  this natural breadth-first search can be used, for
  example   by   letting  the  group  act  on  its  own  elements,  either  by
  multiplication or by conjugation.
  
  All technical instructions to do this are already given in Subsection 3.1-4,
  so  we  are  content to provide an example here. Assume you want to find the
  shortest  way  to  express  some  7-cycle in the symmetric group S_{10} as a
  product  of  generators  a  :=(1,2,3,4,5,6,7,8,9,10) and b :=(1,2). Then you
  could do this in the following way:
  
  ---------------------------  Example  ----------------------------
    gap> gens := [(1,2,3,4,5,6,7,8,9,10),(1,2)];
    [ (1,2,3,4,5,6,7,8,9,10), (1,2) ]
    gap> o := Orb(gens,(),OnRight,rec( report := 2000,
    > lookingfor := 
    > function(o,x) return NrMovedPoints(x) = 7 and Order(x)=7; end,
    > schreier := true ));
    <open orbit, 1 points with Schreier tree looking for sth.>
    gap> Enumerate(o);
    <open orbit, 614 points with Schreier tree looking for sth.>
    gap> w := TraceSchreierTreeForward(o,PositionOfFound(o));
    [ 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2 ]
    gap> ActWithWord(o!.gens,w,o!.op,o[1]);                  
    (1,10,9,8,7,6,5)
    gap> o[PositionOfFound(o)] = ActWithWord(o!.gens,w,o!.op,o[1]);
    true
    gap> EvaluateWord(o!.gens,w);
    (1,10,9,8,7,6,5)
  ------------------------------------------------------------------
  
  The  result shows that a^6 * (a* b)^3 is a 7-cycle and that there is no word
  in a and b with fewer than 12 letters expressing a 7-cycle.
  
  Note  that  we  can  go  on with the above orbit enumeration to find further
  words to express 7-cycles.
  
  
  7.2 Random searches in groups
  
  Another  possibility  to  look  for  elements  in a group satisfying certain
  properties  is to look at random elements, usually obtained by doing product
  replacement  (see  Section  6.2).  Although  this  can  lead  to  very  long
  expressions  as  words  in the generators, one can cope with this problem by
  using  the  maxdepth  option  of  the  product  replacer objects, which just
  reinitialises  the  product  replacement  table  after  a  certain number of
  product  replacements has been performed. To organise all this conveniently,
  there is the concept of "random searcher objects" described here.
  
  7.2-1 RandomSearcher
  
  > RandomSearcher( gens, testfunc[, opt] ) _________________________operation
  Returns:  a random searcher object
  
  gens  must  be  a  list  of  group generators, testfunc a function taking as
  argument  one  group element and returning true or false. opt is an optional
  options record. For possible options see below.
  
  At  first,  the  random  searcher  object  is just initialised but no random
  searching is performed. The actual search is triggered by the Search (7.2-2)
  operation (see below). The idea of random searcher objects is that a product
  replacer  object is created and during a search random elements are produced
  using  this product replacer object, and for each group element produced the
  function testfunc is called. If this function returns true, the search stops
  and the group element found is returned.
  
  The following options can be bound in the options record opt:
  
  exceptions
        This  component  can be a list to initialise the exception list in the
        random searcher object. Group elements in this list are not considered
        as  successful  searches.  This  list  is also used to continue search
        operations  to  found  more  suitable  group  elements  as every group
        element  considered "found" is added to that list before returning it.
        Thus every element will only be found once.
  
  maxdepth
        Sets  the maxdepth option of the created product replacer object. This
        limits  the  length  of the expression as product of the generators of
        the found group elements.
  
  addslots
        Sets the addslots option of the created product replacer object.
  
  scramble
        If  this  component is bound at all, then the created product replacer
        object is created with options scramble=100 and scramblefactor=10 (the
        default values), otherwise the options scramble=0 and scramblefactor=0
        are used, leading to no scrambling at all. See ProductReplacer (6.2-1)
        for details on the product replacement algorithm.
  
  Note  that  of  course  the generators in gens may have memory. However, the
  function testfunc is called with the group element with memory stripped off.
  
  7.2-2 Search
  
  > Search( rs ) ____________________________________________________operation
  Returns:  a group element
  
  Runs  the  search  with  the  random searcher object rs and returns with the
  first group element found.
  
  
  7.3 The dihedral trick and applications
  
  With  the "dihedral" trick we mean the following: Two involutions a and b in
  a  group  always  generate  a  dihedral group. Thus, to find a pseudo-random
  element  in  the  centraliser of an involution a, we can proceed as follows:
  Create  a  pseudo-random  element c, then b := a^c is another involution. If
  then  ab  has  order 2o, we can use (ab)^o. Otherwise, if the order of ab is
  2o-1, then (ab)^o * c^{-1} centralises a.
  
  This  trick  allows to efficiently produce elements in the centraliser of an
  involution  and  thus,  with  high  probability,  generators  for  the  full
  centraliser.
  
  There are the following functions:
  
  7.3-1 FindInvolution
  
  > FindInvolution( pr ) _____________________________________________function
  Returns:  an involution
  
  pr  must  be  a  product  replacer  object  (see  Section  6.2). Searches an
  involution  by  finding  a  random  element  of  even order and powering up.
  Returns the involution.
  
  7.3-2 FindCentralisingElementOfInvolution
  
  > FindCentralisingElementOfInvolution( pr, a ) _____________________function
  Returns:  a group element
  
  pr  must be a product replacer object (see Section 6.2). Produces one random
  element  and  builds  an  element the centralises the involution a using the
  dihedral trick described above.
  
  7.3-3 FindInvolutionCentralizer
  
  > FindInvolutionCentralizer( pr, a, nr ) ___________________________function
  Returns:  a list of nr group elements
  
  pr must be a product replacer object (see Section 6.2) and a and involution.
  This  function  uses FindCentralisingElementOfInvolution (7.3-2) nr times to
  produce  an  element  centralising  the involution a and returns the list of
  results.
  
  
  7.4 Orbit statistics on vector spaces
  
  The  following  two  functions  are  tools to get a rough and quick estimate
  about the average orbit length of a group acting on a vector space.
  
  7.4-1 OrbitStatisticOnVectorSpace
  
  > OrbitStatisticOnVectorSpace( gens, size, ti ) ____________________function
  Returns:  nothing
  
  gens  must  be  a list of matrix group generators and size an integer giving
  the  order  of  the group generated by gens. ti is an integer specifying the
  number  of seconds to run. This function enumerates orbits of random vectors
  in  the  natural  space  the group is acting on. The average length and some
  other information is printed on the screen.
  
  7.4-2 OrbitStatisticOnVectorSpaceLines
  
  > OrbitStatisticOnVectorSpaceLines( gens, size, ti ) _______________function
  Returns:  nothing
  
  gens  must  be  a list of matrix group generators and size an integer giving
  the  order  of  the group generated by gens. ti is an integer specifying the
  number  of  seconds  to  run.  This  function  enumerates  orbits  of random
  one-dimensional  subspaces  in the natural space the group is acting on. The
  average length and some other information is printed on the screen.
  
  
  7.5 Finding generating sets of subgroups
  
  The  following  function  can  be used to find generators of a subgroup of a
  group G, expressed as a straight line program in the generators of G.
  
  7.5-1 FindShortGeneratorsOfSubgroup
  
  > FindShortGeneratorsOfSubgroup( G, U, membershiptest ) ____________function
  Returns:  a record described below
  
  The  arguments  U and G must be GAP group objects with U being a subgroup of
  G.  The  argument  membershiptest  must  be a function taking two arguments,
  namely  a  group element and a group, that checks, whether the group element
  lies  in  the  group  or  not,  returning true or false accordingly. You can
  usually just use the function \in as third argument.
  
  This  function  does  a breadth-first search to find elements in U using the
  generators of G. It then uses calculates the size of the group generated and
  proceeds  in  this way, until a generating system for U is found in terms of
  the generators of G. Those generators are guaranteed to be shortest words in
  the generators of G lying in U.
  
  The  function  returns a record with two components bound: gens is a list of
  generators  for  U and slp is a GAP straight line program expressing exactly
  those generators in the generators of G.
  
  Note  that this function only performs satisfactorily when the index of U in
  G  is  not  to huge. It also helps if the groups come in a representation in
  which GAP can compute efficiently for example as permutation groups.