  
  [1X4 [33X[0;0YInfluencing the algorithm[133X[101X
  
  [33X[0;0YA  number of choices can be made by the user to influence the performance of
  [10XAutomorphismGroupPGroup[110X.  Below  we identify these choices and their default
  values  used in [2XAutomorphismGroup[102X ([14X2.1-1[114X). We use the optional argument [3Xflag[103X
  of  [10XAutomorphismGroupPGroup[110X  to  invoke  user-defined  choices. The possible
  values for [3Xflag[103X are[133X
  
  [8X[10X[3Xflag[103X[8X[10X = false[110X[8X [108X
        [33X[0;6Ythe user-defined defaults are employed in the algorithm. See below for
        a list of possibilities.[133X
  
  [8X[10X[3Xflag[103X[8X[10X = true[110X[8X [108X
        [33X[0;6Yinvokes  the  interactive  version  of  the  algorithm as described in
        Section [14X4.5[114X.[133X
  
  [33X[0;0YIn  the  next  section  we  give  a  brief outline of the algorithm which is
  necessary  to understand the possible choices. Then we introduce the choices
  the later sections of this chapter.[133X
  
  
  [1X4.1 [33X[0;0YOutline of the algorithm[133X[101X
  
  [33X[0;0YThe  algorithm  and  its  refinements  are  described  in [ELO02]; the basic
  algorithm goes back to [O'B95]. Here we give a brief outline.[133X
  
  [33X[0;0YThe basic algorithm proceeds by induction down the lower [22Xp[122X-central series of
  a  given  [22Xp[122X-group  [22XG[122X;  that  is,  it  successively computes [22XAut(G_i)[122X for the
  quotients  [22XG_i  = G / P_i(G)[122X of the descending sequence of subgroups defined
  by  [22XP_1(G)  =  G[122X  and  [22XP_i+1(G)=[P_i(G),G]  P_i(G)^p[122X for [22Xi≥ 1[122X. Hence, in the
  initial step of the algorithm, [22XAut(G_2) = GL(d,p)[122X where [22Xd[122X is the rank of the
  elementary abelian group [22XG_2[122X. In the inductive step it determines [22XAut(G_i+1)[122X
  from  [22XAut(G_i)[122X.  For  this  purpose  we introduce an action of [22XAut(G_i)[122X on a
  certain  elementary abelian [22Xp[122X-group [22XM[122X (the [13X[22Xp[122X-multiplicator[113X of [22XG_i[122X). The main
  computation  of the inductive step is the determination of the stabiliser in
  [22XAut(G_i)[122X  of  a  subgroup  [22XU[122X  of  [22XM[122X (the [13Xallowable subgroup[113X for [22XG_i+1[122X). This
  stabiliser calculation is the bottle-neck of the algorithm.[133X
  
  [33X[0;0YOur  package  incorporates a number of refinements designed to simplify this
  stabiliser  computation. Some of these refinements incur overheads and hence
  they  are  not always invoked. The features outlined below allow the user to
  select them.[133X
  
  [33X[0;0YObserve  that  the initial step of the algorithm returns [22XGL(d,p)[122X. But [22XAut(G)[122X
  may  induce  on  [22XG_2[122X  a proper subgroup, say [22XK[122X, of [22XGL(d,p)[122X. Any intermediate
  subgroup  of  [22XGL(d,p)[122X  which  contains  [22XK[122X  suffices for the algorithm and we
  supply   two   methods   to   construct   a  suitable  subgroup:  these  use
  characteristic  subgroups  or  invariants  of  normal  subgroups  of [22XG[122X. (See
  Section [14X4.2[114X.)[133X
  
  [33X[0;0YIn the inductive step an action of [22XAut(G_i)[122X on an elementary abelian group [22XM[122X
  is  used.  This  action is computed as a matrix action on a vector space. To
  simplify  the  orbit-stabiliser  computation  of the subspace [22XU[122X of [22XM[122X, we can
  construct   the   stabiliser   of   [22XU[122X   by  iteration  over  a  sequence  of
  [22XAut(G_i)[122X-invariant subspaces of [22XM[122X. (See Section [14X4.3[114X.)[133X
  
  [33X[0;0YOrbit-stabiliser   computations   in  finite  solvable  groups  given  by  a
  polycyclic  generating sequence [LNS84] are much more efficient than generic
  computations  of this type. Thus our algorithm makes use of a large solvable
  normal  subgroup  [22XS[122X of [22XAut(G_i)[122X. Further, it is useful if the generating set
  of  [22XAut(G_i)[122X outside [22XS[122X is as small as possible. To achieve this we determine
  a permutation representation of [22XAut(G_i)/S[122X and use this to reduce the number
  of generators if possible. (See Section [14X4.4[114X.)[133X
  
  
  [1X4.2 [33X[0;0YThe initialisation step[133X[101X
  
  [33X[0;0YAssume  we  seek  to  compute  the  automorphism group of a [22Xp[122X-group [22XG[122X having
  Frattini rank [22Xd[122X. We first determine as small as possible a subgroup of [22XGL(d,
  p)[122X whose extension can act on [22XG[122X.[133X
  
  [33X[0;0YThe  user can choose the initialisation routine by assigning [10XInitAutGroup[110X to
  any one of the following:[133X
  
  [8X[10XInitAutomorphismGroupOver[110X[8X [108X
        [33X[0;6Yto use the minimal overgroups: We determine the minimal over-groups of
        the  Frattini subgroup of [22XG[122X and compute invariants of these which must
        be  respected by the automorphism group of [22XG[122X. We partition the minimal
        overgroups and compute the stabiliser in [22XGL(d, p)[122X of this partition.[133X
  
        [33X[0;6YThe partition of the minimal overgroups is computed using the function
        [10XPGFingerprint(  G,  U  )[110X.  This  is  the  time-consuming  part of this
        initialisation   method.   The   user   can   overwrite  the  function
        [10XPGFingerprint[110X.[133X
  
  [8X[10XInitAutomorphismGroupChar[110X[8X [108X
        [33X[0;6Yto  use the characteristic subgroups: Compute a generating set for the
        stabiliser  in  [22XGL (d, p)[122X of a chain of characteristic subgroups of [22XG[122X.
        In practice, we construct a characteristic chain by determining 2-step
        centralisers  and  omega  subgroups  of factors of the lower [22Xp[122X-central
        series.[133X
  
        [33X[0;6YHowever,  there are often other characteristic subgroups which are not
        found  by  these  approaches.  The  user  can  overwrite  the function
        [10XPGCharSubgroups( G )[110X to supply a set of characteristic subgroups.[133X
  
  [8X[10XInitAutomorphismGroupFull[110X[8X [108X
        [33X[0;6Yto use the full [22XGL(d,p)[122X.[133X
  
  [33X[0;0YIn  the  method  for [2XAutomorphismGroup[102X ([14X2.1-1[114X) we use a default strategy: if
  the  value [22Xfracp^d-1p-1[122X is less than 1000, then we use the minimal overgroup
  approach,  otherwise the characteristic subgroups are employed. An exception
  is  made  for  homogeneous  abelian groups where we initialise the algorithm
  with the full group [22XGL(d,p)[122X.[133X
  
  
  [1X4.3 [33X[0;0YStabilisers in matrix groups[133X[101X
  
  [33X[0;0YConsider  the [22Xi[122Xth inductive step of the algorithm. Here [22XA ≤ Aut(G_i)[122X acts as
  matrix  group  on  the elementary abelian [22Xp[122X-group [22XM[122X and we want to determine
  the stabiliser of a subgroup [22XU ≤ M[122X.[133X
  
  [33X[0;0YWe  use  the  MeatAxe  [HR94]  to  compute a series of [22XA[122X-invariant subspaces
  through  [22XM[122X  such  that each factor in the series is irreducible as [22XA[122X-module.
  Then  we  use this series to break the computation of [22XStab_A(U)[122X into several
  smaller orbit-stabiliser calculations.[133X
  
  [33X[0;0YNote that a theoretic argument yields an [22XA[122X-invariant subspace of [22XM[122X a priori:
  the  nucleus [22XN[122X. This is always used to split the computation up. However, it
  may happen that [22XN = M[122X and hence results in no improvement.[133X
  
  [1X4.3-1 CHOP_MULT[101X
  
  [33X[1;0Y[29X[2XCHOP_MULT[102X [32X global variable[133X
  
  [33X[0;0YThe  invariant  series through [22XM[122X is computed and used if the global variable
  [10XCHOP_MULT[110X  is  set  to  [9Xtrue[109X.  Otherwise,  the  algorithm tries to determine
  [22XStab_A(U)[122X in one step. By default, [10XCHOP_MULT[110X is [9Xtrue[109X.[133X
  
  [33X[0;0YEach  orbit-stabiliser  calculation enumerates the orbit of a subspace under
  the  generators  of  [22XA[122X outside [22XS[122X. When the stabiliser is small this orbit is
  long,  up  to  [22X|A/S|[122X, and the enumeration is hopeless. Hence, once the orbit
  exceeds  a  few  thousand  points,  the  stabiliser  is also sought as a set
  stabiliser,  by  the  partition  backtrack  of  [5XGAP[105X  ([2XStabilizer[102X ([14XReference:
  Stabilizer[114X) with [10XOnSets[110X), in a permutation representation of [22XA[122X on the points
  of [22XA/S[122X and the lines of the module section in the orbits of the lines of the
  subspace.  This  needs  the  permutation  representation  of  [22XA/S[122X  which the
  initialisation   by   [10XInitAutomorphismGroupOver[110X  provides.  The  enumeration
  continues  in  rounds  of  growing  length,  and  after  each  round the set
  stabiliser  is  tried  again,  allowed to spend on its permutation domain at
  most  as  much  work  as the enumeration has done so far, so that a group on
  which it cannot help costs at most twice its enumeration.[133X
  
  [1X4.3-2 PERM_STAB[101X
  
  [33X[1;0Y[29X[2XPERM_STAB[102X [32X global variable[133X
  
  [33X[0;0YThe  set stabiliser method is used if the global variable [10XPERM_STAB[110X is [9Xtrue[109X,
  the default. Setting it to [9Xfalse[109X forces orbit enumeration.[133X
  
  
  [1X4.3-3 [33X[0;0YThe option OrbitLimit[133X[101X
  
  [33X[0;0Y[10XAutomorphismGroupPGroup(  G  :  OrbitLimit := n )[110X returns [9Xfail[109X as soon as an
  orbit-stabiliser  calculation would enumerate more than [3Xn[103X points and the set
  stabiliser  method  cannot be used. This lets a computation over many groups
  set aside the expensive ones instead of losing the whole job. The method for
  [10XAutomorphismGroup[110X  signals  an error in this case, since an attribute cannot
  be [9Xfail[109X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := PcGroupCode( 103045690560068391423508120999240094531550914947096312619671359, 512 );;[127X[104X
    [4X[25Xgap>[125X [27XSetInfoLevel( InfoAutGrp, 0 );[127X[104X
    [4X[25Xgap>[125X [27XPERM_STAB := false;;[127X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroupPGroup( G : OrbitLimit := 1000 );[127X[104X
    [4X[28Xfail[128X[104X
    [4X[25Xgap>[125X [27XPERM_STAB := true;;[127X[104X
    [4X[25Xgap>[125X [27XA := AutomorphismGroupPGroup( G : OrbitLimit := 1000 );;[127X[104X
    [4X[25Xgap>[125X [27XA.size;[127X[104X
    [4X[28X262144[128X[104X
  [4X[32X[104X
  
  
  [1X4.4 [33X[0;0YSearching for a small generating set[133X[101X
  
  [33X[0;0YAfter each step of the computation, we attempt to find a nice generating set
  for the automorphism group of the current factor.[133X
  
  [33X[0;0YIf  the automorphism group is soluble, we store a polycyclic generating set;
  otherwise,  we  store  such  a  generating  set  for  a large soluble normal
  subgroup  [22XS[122X  of  the  automorphism group [22XA[122X, and as few generators outside as
  possible.  If  [22XS  =  A[122X  and a polycyclic generating set for [22XS[122X is known, many
  steps of the algorithm proceed more rapidly.[133X
  
  [1X4.4-1 NICE_STAB[101X
  
  [33X[1;0Y[29X[2XNICE_STAB[102X [32X global variable[133X
  
  [33X[0;0YIt  may  be  both  time-consuming  and  difficult  to  reduce  the number of
  generators for [22XA[122X outside [22XS[122X. Note that if the initialisation of the algorithm
  is   by   [10XInitAutomorphismGroupOver[110X,  then  we  always  know  a  permutation
  representation  for  [22XA/S[122X. Occasionally the search for a small generating set
  is expensive. If this is observed, one could set the flag [10XNICE_STAB[110X to [9Xfalse[109X
  and the algorithm no longer invokes this search.[133X
  
  
  [1X4.5 [33X[0;0YAn interactive version of the algorithm[133X[101X
  
  [33X[0;0YThe   choice   of   initialisation   and  the  choice  of  chopping  of  the
  [22Xp[122X-multiplicator  can  also  be  driven  by  an  interactive  version  of the
  algorithm. We give an example.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := PcGroupCode(2504972218445939562621471375, 256);;  # SmallGroup( 2^8, 1000 );[127X[104X
    [4X[25Xgap>[125X [27XSetInfoLevel( InfoAutGrp, 3 );[127X[104X
    [4X[28X[128X[104X
    [4X[25Xgap>[125X [27XAutomorphismGroupPGroup( G, true );[127X[104X
    [4X[28X#I  step 1: 2^3 -- init automorphisms[128X[104X
    [4X[28X[128X[104X
    [4X[28Xchoose initialisation (Over/Char/Full):     # we choose Full[128X[104X
    [4X[28X#I    init automorphism group : Full[128X[104X
    [4X[28X#I  step 2: 2^3 -- aut grp has size 168[128X[104X
    [4X[28X#I    computing cover[128X[104X
    [4X[28X#I    computing matrix action[128X[104X
    [4X[28X#I    computing stabilizer of U[128X[104X
    [4X[28X#I    dim U = 3  dim N = 6  dim M = 6[128X[104X
    [4X[28X[128X[104X
    [4X[28Xchop M/N and N: (y/n):                      # we choose n[128X[104X
    [4X[28X#I    induce autos and add central autos[128X[104X
    [4X[28X#I  step 3: 2^2 -- aut grp has size 12288[128X[104X
    [4X[28X#I    computing cover[128X[104X
    [4X[28X#I    computing matrix action[128X[104X
    [4X[28X#I    computing stabilizer of U[128X[104X
    [4X[28X#I    dim U = 6  dim N = 5  dim M = 8[128X[104X
    [4X[28X[128X[104X
    [4X[28Xchop M/N and N: (y/n):                      # we choose y[128X[104X
    [4X[28X#I    induce autos and add central autos[128X[104X
    [4X[28X#I  final step: convert[128X[104X
    [4X[28Xrec([128X[104X
    [4X[28X  glAutos := [ Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) -> [ f1, f2*f3, f3,[128X[104X
    [4X[28X          f4, f5, f6*f7, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1*f3*f5*f6, f2*f3, f3, f4, f5*f8, f6*f7, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1*f3, f2*f4, f3, f4*f7, f5*f7, f6*f7*f8, f7, f8 ] ], glOrder := 4,[128X[104X
    [4X[28X  agAutos :=[128X[104X
    [4X[28X    [ Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) -> [ f1*f4, f2, f3, f4*f8, f5,[128X[104X
    [4X[28X          f6, f7, f8 ], Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1, f2*f4, f3, f4*f7, f5, f6*f7*f8, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1*f5, f2, f3, f4, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1, f2*f5, f3, f4, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1, f2, f3*f5, f4, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1*f6, f2, f3, f4, f5*f7*f8, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1, f2*f6, f3, f4*f7*f8, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1*f8, f2, f3, f4, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1, f2*f8, f3, f4, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1, f2, f3*f8, f4, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1*f7, f2, f3, f4, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1, f2*f7, f3, f4, f5, f6, f7, f8 ],[128X[104X
    [4X[28X      Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8 ]) ->[128X[104X
    [4X[28X        [ f1, f2, f3*f7, f4, f5, f6, f7, f8 ] ],[128X[104X
    [4X[28X  agOrder := [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ],[128X[104X
    [4X[28X  one := IdentityMapping( <pc group of size 256 with 8 generators> ),[128X[104X
    [4X[28X  group := <pc group of size 256 with 8 generators>, size := 32768 )[128X[104X
  [4X[32X[104X
  
  [33X[0;0YTwo  points  are  worthy  of  comment. First, the interactive version of the
  algorithm  permits  the  user  to make a suitable choice in each step of the
  algorithm  instead  of  making  one  choice  at the beginning. Secondly, the
  output  of  the  [10XInfo[110X  function  shows  the ranks of the [22Xp[122X-multiplicator and
  allowable  subgroup,  and  thus  allow  the  user  to  observe  the scale of
  difficulty of the computation.[133X
  
