  
  [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 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  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 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
  
  
  [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
  
