%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  anupq.tex                GAP documentation                 Eamonn O'Brien
%A                                                             & Frank Celler
%A                                                           & Benedikt Rothe
%%
%A  @(#)$Id: anupq.tex,v 3.12 1994/06/10 02:39:12 vfelsch Rel $
%%
%Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
%%
%H  $Log: anupq.tex,v $
%H  Revision 3.12  1994/06/10  02:39:12  vfelsch
%H  updated examples
%H
%H  Revision 3.11  1994/05/19  13:47:15  sam
%H  fixed 'StandardPresentation'
%H
%H  Revision 3.10  1994/04/27  09:01:08  fceller
%H  added 'PqHomomorphism'
%H  added new parameter "SubList"
%H
%H  Revision 3.9  1993/07/27  11:32:31  fceller
%H  changed examples to new free group / relators style
%H
%H  Revision 3.8  1993/06/28  10:01:52  fceller
%H  new ANU pq version
%H
%H  Revision 3.6  1993/02/15  15:15:16  felsch
%H  examples fixed
%H
%H  Revision 3.5  1993/02/01  11:40:52  fceller
%H  fixed an example
%H
%H  Revision 3.4  1993/01/05  11:40:05  fceller
%H  some more fixes, changed "SetupFile" to return 'true'
%H  
%H  Revision 3.3  1993/01/04  11:01:01  fceller
%H  fixed some misspellings
%H
%H  Revision 3.2  1992/12/29  15:57:49  fceller
%H  Initial GAP 3.2 revision
%H  
%%
\Chapter{ANU Pq}

The ANU $p$-quotient program (pq) may  be called from {\GAP}.  Using this
program,  {\GAP}  provides access to   the  following\:\ the $p$-quotient
algorithm;  the $p$-group  generation algorithm; a  standard presentation
algorithm; an algorithm to compute the automorphism group of a $p$-group.

The  following section describes the function 'Pq', which gives access to
the $p$-quotient algorithm.

The next section  describes  the  function 'PqDescendants',  which  gives
access to the $p$-group generation algorithm.

The next sections describe  functions for  saving  results  to  file (see
"PqList" and "SavePqList").

The  next  section describes  the  function 'StandardPresentation'  which
gives access to the standard presentation algorithm and to the  algorithm
used to compute the automorphism group of a $p$-group.

The  last sections  describes  the  function  'IsIsomorphicPGroup'  which
implements  an  isomorphism  test  for  $p$-groups  using  the   standard
presentation algorithm.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Pq}

'Pq( <F>, ... )'

Let <F> be a  finitely presented  group.  Then  'Pq' returns  the desired
$p$-quotient of <F> as an ag group.

The following parameters or parameter pairs are supported.

\"Prime\", <p>: \\
    Compute the $p$-quotient for the prime <p>.

\"ClassBound\", <n>: \\
    The $p$-quotient computed has lower exponent-$p$ class at most <n>.

\"Exponent\", <n>: \\
    The $p$-quotient computed has exponent <n>.
    By default, no exponent law is enforced.

\"Metabelian\": \\
    The largest metabelian $p$-quotient is constructed. 

\"Verbose\": \\
    The runtime-information generated  by  the ANU  pq is  displayed.  By
    default, pq works silently.

\"OutputLevel\", <n>: \\
    The runtime-information  generated by the  ANU  pq  is  displayed  at
    output  level  <n>,  which  must  be a  integer from  0 to  3.   This
    parameter implies \"Verbose\".

\"SetupFile\", <name>: \\
    Do not run the ANU pq, just  construct the input file and store it in
    the file <name>. In this case 'true' is returned.

Alternatively, you can pass 'Pq' a record as a parameter, which  contains
as entries some (or all)  of the above mentioned.  Those parameters which
do not occur in the record are set to their default values.

See also "PqHomomorphism".

|    gap> RequirePackage("anupq");
    gap> f2 := FreeGroup( 2, "f2" );                          
    Group( f2.1, f2.2 )
    gap> Pq( f2, rec( Prime := 2,  ClassBound := 3 ) );
    Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7, G.8, G.9, G.10 )
    gap> g := f2 / [ f2.1^4, f2.2^4 ];;
    gap> Pq( g, rec( Prime := 2, ClassBound := 3 ) );
    Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7, G.8 )
    gap> Pq( g, "Prime", 2, "ClassBound", 3, "Exponent", 4 );
    Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7 )
    gap> g := f2 / [ f2.1^25, Comm(Comm(f2.2,f2.1),f2.1), f2.2^5 ];;
    gap> Pq( g, "Prime", 5, "Metabelian", "ClassBound", 5 ); 
    Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7 ) |

This function requires the package \"anupq\"\ (see "RequirePackage").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PqHomomorphism}

'PqHomomorphism( <G>, <images> )'

Let <G> be a $p$-quotient of $F$ computed  using  'Pq'. If <images>  is a
list  of  images  of  '$F$.generators'  under  an  automorphism  of  $F$,
'PqHomomorphism' will return the corresponding automorphism of <G>.

|    gap> F := FreeGroup (2, "F");
    Group( F.1, F.2 )
    gap> G := Pq (F, "Prime", 5, "Class", 2);
    Group( G.1, G.2, G.3, G.4, G.5 )
    gap> PqHomomorphism (G, [F.2, F.1]);
    GroupHomomorphismByImages( Group( G.1, G.2, G.3, G.4, G.5 ), Group(
    G.1, G.2, G.3, G.4, G.5 ), [ G.1, G.2, G.3, G.4, G.5 ], 
    [ G.2, G.1, G.3^4, G.5, G.4 ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PqDescendants}

'PqDescendants( <G>, ... )'

Let  <G>  be  an  ag  group  of  prime  power  order  with  a  consistent
power-commutator  presentation   (see  "IsConsistent").   'PqDescendants'
returns a list of descendants of <G>.

If <G>  does  *not* have p-class 1,  then a list of  automorphisms of <G>
must  be  bound  to the  record  component '<G>.automorphisms' such  that
'<G>.automorphisms' together with the inner automorphisms of <G> generate
the automorphism group of <G>.

One method  which  may be  used  to obtain such a generating set  for the
automorphism  group  is  to  call  'StandardPresentation'.   The record
returned has a generating set for the automorphism group of <G> stored as
a component (see "StandardPresentation").

The following optional parameters or parameter pairs are supported.

\"ClassBound\", <n>: \\
    'PqDescendants' generates  only  descendants  with lower exponent-$p$
    class  at most  <n>.  The default value is  the exponent-$p$ class of
    <G> plus one.

\"OrderBound\", <n>: \\
    'PqDescendants' generates only descendants of  size at  most $p^<n>$.
    Note that you cannot set both \"OrderBound\"\ and \"StepSize\".

\"StepSize\", <n>: \\
    Let <n> be a  positive integer.  'PqDescendants' generates only those
    immediate  descendants  which are $p^<n>$  bigger  than  their parent
    group.

\"StepSize\", <l>: \\
    Let <l> be a  list of  positive  integers such that  the  sum  of the
    length of <l> and the exponent-$p$ class of <G> is equal to the class
    bound \"ClassBound\".  Then  <l> describes  the  step size  for  each
    additional class.

\"AgAutomorphisms\": \\
    The automorphisms stored in '<G>.automorphisms' are  a PAG-generating
    sequence for  the  automorphism group  of  <G> supplied in  *reverse*
    order.

\"RankInitialSegmentSubgroups\", <n>: \\
    Set the rank  of the  initial  segment  subgroup chosen to  be <n>.  
    By default, this has value 0.

\"SpaceEfficient\": \\
    The ANU  pq performs  calculations  more slowly but with greater space 
    efficiency. 
    This  flag is  frequently  necessary  for  groups of  large  Frattini
    quotient rank.  The space  saving occurs because only one permutation
    is  stored at  any  one  time.   This option  is  only  available  in
    conjunction with the \"AgAutomorphisms\"\ flag.

\"AllDescendants\": \\
    By default, only capable descendants are constructed. If this flag
    is set, compute all descendants. 

\"Exponent\", <n>: \\
    Construct only descendants with exponent <n>.  Default is no exponent
    law.

\"Metabelian\": \\
    Construct only metabelian descendants.

\"SubList\", <sub>: \\
    Let $L$  be  the  list of  descendants  generated.  If  list <sub> is
    supplied,  'PqDescendants'  returns  'Sublist( $L$,<sub> )'.  If   an 
    integer <n> is supplied, 'PqDescendants' returns $L[<n>]$.

\"Verbose\": \\
    The runtime-information  generated by  the  ANU pq is  displayed.  By
    default, pq works silently.

\"SetupFile\", <name>: \\
    Do not run the ANU pq, just construct  the input file and store it in
    the file <name>. In this case 'true' is returned.

\"TmpDir\", <dir>: \\
    'PqDescendants' stores intermediate results  in temporary  files; the
    location  of  these  files  is  determined  by the value  selected by
    'TmpName'.  If your default temporary directory does not  have enough
    free disk space,  you can supply an alternative path  <dir>.  In this
    case 'PqDescendants' stores its intermediate results  in  a temporary
    subdirectory of <dir>.
    Alternatively, you can globally set  the  variable 'ANUPQtmpDir', for
    instance in your \".gaprc\"\ file, to point to a suitable location.

Alternatively,  you can pass 'PqDescendants'  a record  as  a  parameter,
which  contains  as  entries some (or all) of the above mentioned.  Those
parameters  which do not occur  in  the record are  set  to their default
values.

Note that you cannot set both \"OrderBound\"\ and \"StepSize\".

In the first example  we  compute all descendants of the Klein four group
which have exponent-2 class at most 5 and order at most $2^6$.

|    gap> f2 := FreeGroup( 2, "g" );;
    gap> g := AgGroupFpGroup(f2 / [f2.1^2, f2.2^2, Comm(f2.2,f2.1)]);
    Group( g.1, g.2 )
    gap> g.name := "g";;
    gap> l := PqDescendants( g, "OrderBound", 6, "ClassBound", 5,     
    >                        "AllDescendants" );;
    gap> Length(l);
    83
    gap> Number( l, x -> x.isCapable );
    47
    gap> List( l, x -> Size(x) );
    [ 8, 8, 8, 16, 16, 16, 32, 16, 16, 16, 16, 16, 32, 32, 64, 64, 32, 
      32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
      32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 32, 32,
      32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
      64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64 ]
    gap> List( l, x -> Length( PCentralSeries( x, 2 ) ) - 1 );
    [ 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
      3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
      3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
      4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5 ] |

In the second example we compute all  capable descendants of order  27 of
the  elementary abelian group of order 9.  Here, we supply  automorphisms
which form a  PAG-generating  sequence (in reverse order) for the class 1
group, since this  makes the computation more efficient.

|    gap> f2 := FreeGroup( 2, "g" );;
    gap> g := AgGroupFpGroup(f2 / [ f2.1^3, f2.2^3, Comm(f2.1,f2.2) ]);
    Group( g.1, g.2 )
    gap> g.name := "g";;
    gap> g.automorphisms := [];;
    gap> GroupHomomorphismByImages(g, g, [g.1, g.2], [g.1^2, g.2^2]);;
    gap> Add( g.automorphisms, last );
    gap> GroupHomomorphismByImages(g, g, [g.1, g.2], [g.2^2, g.1]);;
    gap> Add( g.automorphisms, last );
    gap> GroupHomomorphismByImages(g,g,[g.1,g.2],[g.1*g.2^2,g.1^2*g.2^2]);;
    gap> Add( g.automorphisms, last );
    gap> GroupHomomorphismByImages(g, g, [g.1,g.2], [g.1,g.1^2*g.2]);;  
    gap> Add( g.automorphisms, last );
    gap> GroupHomomorphismByImages(g, g, [g.1, g.2], [g.1^2, g.2]);;
    gap> Add( g.automorphisms, last );
    gap> l := PqDescendants( g, "OrderBound", 3,                   
    >                           "ClassBound", 2, 
    >                           "AgAutomorphisms" );;
    gap> Length(l);
    2
    gap> List( l, x -> Size(x) );
    [ 27, 27 ]
    gap> List( l, x -> Length( PCentralSeries( x, 3 ) ) - 1 );
    [ 2, 2 ] |

In  the  third  example,  we  compute  all  capable  descendants  of  the
elementary abelian group of order  $5^2$ which have exponent-$5$ class at
most $3$, exponent $5$, and are metabelian.

|    gap> f2 := FreeGroup( 2, "g" );;
    gap> g := AgGroupFpGroup( f2 / [f2.1^5, f2.2^5, Comm(f2.2,f2.1)] );
    Group( g.1, g.2 )
    gap> g.name := "g";;
    gap> l := PqDescendants(g,"Metabelian","ClassBound",3,"Exponent",5);;
    gap> List( l, x -> Length( PCentralSeries( x, 5 ) ) - 1 ); 
    [ 2, 3, 3 ]
    gap> List( l, x -> Length( DerivedSeries( x ) ) );           
    [ 3, 3, 3 ]
    gap> List( l, x -> Maximum( List( Elements(x), y -> Order(x,y) ) ) );
    [ 5, 5, 5 ] |

This function requires the package \"anupq\"\ (see "RequirePackage").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PqList}

'PqList( <file> )' \\
'PqList( <file>, <sub> )' \\
'PqList( <file>, <n> )'

The function 'PqList' reads a file  <file> and returns the list $L$ of ag
groups defined in this file.

If list <sub> is supplied as a parameter, the function  returns 'Sublist(
$L$, <sub> )'.  If an integer <n> is supplied, 'PqList' returns $L[<n>]$.

This  function  and  'SavePqList'  (see  "SavePqList")  can  be  used  to
save and restore a list of descendants (see "PqDescendants").

This function requires the package \"anupq\"\ (see "RequirePackage").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SavePqList}

'SavePqList( <name>, <list> )'

The function 'SavePqList' writes a list of  descendants  <list> to a file
<name>.

This function and 'PqList' (see "PqList") can be used to save and restore
results of 'PqDescendants' (see "PqDescendants").

This function requires the package \"anupq\"\ (see "RequirePackage").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{StandardPresentation}
\index{automorphisms!of p groups}

'StandardPresentation( <F>, <p>, ...  )' \\
'StandardPresentation( <F>, <G>, ...  )'

Let  <F> be  a  finitely  presented group.   Then  'StandardPresentation'
returns the standard presentation for the  desired $p$-quotient of <F> as
an ag group.

Let <H> be the  $p$-quotient whose standard presentation is  computed.  A
generating set for a supplement to the inner automorphism group of <H> is
also  returned,   stored  as  the  component  '<H>.automorphisms'.   Each
generator is described by  its  action on  each of the generators  of the
standard presentation of <H>.

A  finitely-presented group <F> must be  supplied  as input. Usually, the
user will  also  supply a prime  <p> and  the  program will  compute  the
standard presentation for the desired $p$-quotient of <F>.

Alternatively,  a  user may supply an ag group <G> which  is the class  1
$p$-quotient of <F>. If  this is  so, a list of automorphisms of <G> must
be   bound  to   the   record  component  '<G>.automorphisms'  such  that
'<G>.automorphisms' together with the inner automorphisms of <G> generate
the  automorphism  group  of  <G>.   The  presentation  for  <G>  can  be
constructed by an initial call to Pq (see "Pq").

Of  course, <G> need  not be the class  1 $p$-quotient of <F>.   However,
'<G>.automorphisms' must contain a description of the  automorphism group
of  <G>  and this is  most readily  available when  <G> is  an elementary
abelian  group.   Where the  necessary information  is  available  for  a
$p$-quotient of higher class,  one  can  apply  the standard presentation
algorithm from that class onwards.

The following parameters or parameter pairs are supported.

\"ClassBound\", <n>: \\
    The  standard presentation is  computed for  the largest $p$-quotient
    of <F> having lower exponent-$p$ class at most <n>.

\"Exponent\", <n>: \\
    The $p$-quotient computed has  exponent <n>.  By default, no exponent
    law is enforced.

\"Metabelian\": \\
    The $p$-quotient constructed is metabelian.

\"AgAutomorphisms\": \\
    The automorphisms stored in '<G>.automorphisms' are  a PAG-generating
    sequence  for the automorphism group  of  <G>  supplied  in *reverse*
    order.

\"Verbose\": \\
    The  runtime-information generated by  the  ANU  pq is displayed.  By
    default, pq works silently.

\"OutputLevel\", <n>: \\
    The  runtime-information generated  by  the  ANU pq is  displayed  at
    output level  <n>, which  must  be  a integer  from  0  to  3.   This
    parameter implies \"Verbose\".

\"SetupFile\", <name>: \\
    Do not run the ANU pq, just construct the input file and  store it in
    the file <name>. In this case 'true' is returned.

\"TmpDir\", <dir>: \\
    'StandardPresentation'  stores  intermediate  results  in   temporary
    files;  the location  of  these  files  is  determined by  the  value
    selected by 'TmpName'.  If your default  temporary directory does not
    have enough  free  disk  space,  you  can supply an  alternative path
    <dir>.  In this case  'StandardPresentation' stores its  intermediate
    results in a temporary subdirectory of <dir>.  Alternatively, you can
    globally  set  the  variable  'ANUPQtmpDir',  for  instance  in  your
    \".gaprc\"\ file, to point to a suitable location.

Alternatively,  you  can  pass   'StandardPresentation'  a  record  as  a
parameter,  which  contains  as  entries  some  (or  all)  of  the  above
mentioned.  Those parameters which do not occur in the record are set  to
their default values.

We illustrate the method with the following examples. 

|    gap> f2 := FreeGroup( "a", "b" );;
    gap> g := f2 / [f2.1^25, Comm(Comm(f2.2,f2.1), f2.1), f2.2^5];
    Group( a, b )
    gap> StandardPresentation( g, 5, "ClassBound", 10 );
    Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7, G.8, G.9, G.10, G.11, G.12,
    G.13, G.14, G.15, G.16, G.17, G.18, G.19, G.20, G.21, G.22, G.23,
    G.24, G.25, G.26 )

    gap> f2 := FreeGroup( "a", "b" );;
    gap> g := f2 / [ f2.1^625,
    >  Comm(Comm(Comm(Comm(f2.2,f2.1),f2.1),f2.1),f2.1)/Comm(f2.2,f2.1)^5,
    >  Comm(Comm(f2.2,f2.1),f2.2), f2.2^625 ];;
    gap> StandardPresentation( g, 5, "ClassBound", 15, "Metabelian" );
    Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7, G.8, G.9, G.10, G.11, G.12,
    G.13, G.14, G.15, G.16, G.17, G.18, G.19, G.20 )

    gap> f4 := FreeGroup( "a", "b", "c", "d" );;
    gap> g4 := f4 / [ f4.2^4, f4.2^2 / Comm(Comm (f4.2, f4.1), f4.1),
    >                f4.4^16, f4.1^16 / (f4.3 * f4.4), 
    >                f4.2^8 / (f4.4 * f4.3^4) ];
    Group( a, b, c, d )
    gap> g := Pq( g4, "Prime", 2, "ClassBound", 1 ); 
    Group( G.1, G.2 )
    gap> g.automorphisms := [];;
    gap> GroupHomomorphismByImages(g,g,[g.1,g.2],[g.2,g.1*g.2]);;        
    gap> Add( g.automorphisms, last );
    gap> GroupHomomorphismByImages(g,g,[g.1,g.2],[g.2,g.1]);;      
    gap> Add( g.automorphisms, last );
    gap> StandardPresentation(g4,g,"ClassBound",14,"AgAutomorphisms");
    Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7, G.8, G.9, G.10, G.11, G.12,
    G.13, G.14, G.15, G.16, G.17, G.18, G.19, G.20, G.21, G.22, G.23,
    G.24, G.25, G.26, G.27, G.28, G.29, G.30, G.31, G.32, G.33, G.34,
    G.35, G.36, G.37, G.38, G.39, G.40, G.41, G.42, G.43, G.44, G.45,
    G.46, G.47, G.48, G.49, G.50, G.51, G.52, G.53 ) |

This function requires the package \"anupq\"\ (see "RequirePackage").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsIsomorphicPGroup}

'IsIsomorphicPGroup( <G>, <H> )'

The functions returns true if <G> is isomorphic to <H>.  Both groups must
be ag groups of prime power order.

|    gap> p1 := Group( (1,2,3,4), (1,3) );
    Group( (1,2,3,4), (1,3) )
    gap> p2 := SolvableGroup( 8, 5 );
    Q8
    gap> p3 := SolvableGroup( 8, 4 );
    D8
    gap> IsIsomorphicPGroup( AgGroup(p1), p2 );
    false
    gap> IsIsomorphicPGroup( AgGroup(p1), p3 );
    true |

The function computes and compares the standard presentations for <G> and  
<H> (see "StandardPresentation").

