home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / anupq.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  12.7 KB  |  325 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  anupq.tex                GAP documentation                 Eamonn O'Brien
  4. %A                                                             & Frank Celler
  5. %A                                                           & Benedikt Rothe
  6. %%
  7. %A  @(#)$Id: anupq.tex,v 3.7 1993/02/18 12:42:41 felsch Exp $
  8. %%
  9. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  10. %%
  11. %H  $Log: anupq.tex,v $
  12. %H  Revision 3.7  1993/02/18  12:42:41  felsch
  13. %H  bug eliminated (reported by E. O'Brien)
  14. %H
  15. %H  Revision 3.6  1993/02/15  15:15:16  felsch
  16. %H  examples fixed
  17. %H
  18. %H  Revision 3.5  1993/02/01  11:40:52  fceller
  19. %H  fixed an example
  20. %H
  21. %H  Revision 3.4  1993/01/05  11:40:05  fceller
  22. %H  some more fixes, changed "SetupFile" to return 'true'
  23. %H  
  24. %H  Revision 3.3  1993/01/04  11:01:01  fceller
  25. %H  fixed some misspellings
  26. %H
  27. %H  Revision 3.2  1992/12/29  15:57:49  fceller
  28. %H  Initial GAP 3.2 revision
  29. %H  
  30. %%
  31. \Chapter{ANU Pq}
  32.  
  33. The ANU $p$-quotient program  (pq) may be called from {\GAP}.  Using this
  34. program, {\GAP}  provides access to both  the $p$-quotient  and $p$-group
  35. generation algorithms.
  36.  
  37. The  following section describes the function 'Pq', which gives access to
  38. the $p$-quotient algorithm.
  39.  
  40. The next section  describes  the  function 'PqDescendants',  which  gives
  41. access to the $p$-group generation algorithm.
  42.  
  43. The next sections describe  functions for  saving  results  to  file (see
  44. "PqList" and "SavePqList").
  45.  
  46. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  47. \Section{Pq}
  48.  
  49. 'Pq( <F>, ... )'
  50.  
  51. Let <F> be a  finitely presented  group.  Then  'Pq' returns  the desired
  52. $p$-quotient of <F> as an ag group.
  53.  
  54. The following parameters or parameter pairs are supported.
  55.  
  56. \"Prime\", <p>: \\
  57.     Compute the $p$-quotient for the prime <p>.
  58.  
  59. \"ClassBound\", <n>: \\
  60.     The $p$-quotient computed has lower exponent-$p$ class at most <n>.
  61.  
  62. \"Exponent\", <n>: \\
  63.     The $p$-quotient computed has exponent <n>.
  64.     By default, no exponent law is enforced.
  65.  
  66. \"Verbose\": \\
  67.     The runtime-information generated  by  the ANU  pq is  displayed.  By
  68.     default, pq works silently.
  69.  
  70. \"OutputLevel\", <n>: \\
  71.     The runtime-information  generated by the  ANU  pq  is  displayed  at
  72.     output  level  <n>,  which  must  be a  integer from  0 to  3.   This
  73.     parameter implies \"Verbose\".
  74.  
  75. \"SetupFile\", <name>: \\
  76.     Do not run the ANU pq, just  construct the input file and store it in
  77.     the file <name>. In this case 'true' is returned.
  78.  
  79. Alternatively, you can pass 'Pq' a record as a parameter, which  contains
  80. as entries some (or all)  of the above mentioned.  Those parameters which
  81. do not occur in the record are set to their default values.
  82.  
  83. |    gap> RequirePackage( "anupq" );
  84.     gap> F := FreeGroup(2);
  85.     Group( f.1, f.2 )
  86.     gap> Pq( F, rec( Prime := 2, ClassBound := 3 ) );        
  87.     Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7, G.8, G.9, G.10 )
  88.     gap> F.relators := [ F.1^4, F.2^4 ];;
  89.     gap> Pq( F, rec( Prime := 2, ClassBound := 3 ) );
  90.     Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7, G.8 )
  91.     gap> Pq( F, "Prime", 2, "ClassBound", 3, "Exponent", 4 );
  92.     Group( G.1, G.2, G.3, G.4, G.5, G.6, G.7 ) |
  93.  
  94. This function requires the package \"anupq\"\ (see "RequirePackage").
  95.  
  96. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  97. \Section{PqDescendants}
  98.  
  99. 'PqDescendants( <G>, ... )'
  100.  
  101. Let  <G>  be  an  ag  group  of  prime  power  order  with  a  consistent
  102. power-commutator   presentation   (see   "IsConsistent").   A   list   of
  103. automorphisms   of  <G>   must   be  bound  to   the   record   component
  104. '<G>.automorphisms' such that '<G>.automorphisms' together with the inner
  105. automorphisms   of  <G>   generate  the   automorphism   group  of   <G>.
  106. 'PqDescendants' returns a list of descendants of <G>.
  107.  
  108. The following optional parameters or parameter pairs are supported.
  109.  
  110. \"ClassBound\", <n>: \\
  111.     'PqDescendants' generates  only  descendants  with lower exponent-$p$
  112.     class  at most  <n>.  The default value is  the exponent-$p$ class of
  113.     <G> plus one.
  114.  
  115. \"OrderBound\", <n>: \\
  116.     'PqDescendants' generates only descendants of  size at  most $p^<n>$.
  117.     Note that you cannot set both \"OrderBound\"\ and \"StepSize\".
  118.  
  119. \"StepSize\", <n>: \\
  120.     Let <n> be a  positive integer.  'PqDescendants' generates only those
  121.     immediate  descendants  which are $p^<n>$  bigger  than  their parent
  122.     group.
  123.  
  124. \"StepSize\", <l>: \\
  125.     Let <l> be a  list of  positive  integers such that  the  sum  of the
  126.     length of <l> and the exponent-$p$ class of <G> is equal to the class
  127.     bound \"ClassBound\".  Then  <l> describes  the  step size  for  each
  128.     additional class.
  129.  
  130. \"AgAutomorphisms\": \\
  131.     The automorphisms stored in '<G>.automorphisms' are  a PAG-generating
  132.     sequence for  the  automorphism group  of  <G> supplied in  *reverse*
  133.     order.
  134.  
  135. \"RankInitialSegmentSubgroups\", <n>: \\
  136.     Set the rank  of the  initial  segment  subgroup chosen to  be <n>.  
  137.     By default, this has value 0.
  138.  
  139. \"SpaceEfficient\": \\
  140.     The ANU  pq performs  calculations  more slowly but with 
  141.     greater space efficiency. 
  142.     This  flag is  frequently  necessary  for  groups of  large  Frattini
  143.     quotient rank.  The space  saving occurs because only one permutation
  144.     is  stored at  any  one  time.   This option  is  only  available  in
  145.     conjunction with the \"AgAutomorphisms\"\ flag.
  146.  
  147. \"AllDescendants\": \\
  148.     By default, only capable descendants are constructed. If this flag
  149.     is set, compute all descendants. 
  150.  
  151. \"Exponent\", <n>: \\
  152.     Construct only descendants with exponent <n>.  Default is no exponent
  153.     law.
  154.  
  155. \"Metabelian\": \\
  156.     Construct only metabelian descendants.
  157.  
  158. \"Verbose\": \\
  159.     The runtime-information  generated by  the  ANU pq is  displayed.  By
  160.     default, pq works silently.
  161.  
  162. \"SetupFile\", <name>: \\
  163.     Do not run the ANU pq, just construct  the input file and store it in
  164.     the file <name>. In this case 'true' is returned.
  165.  
  166. \"TmpDir\", <dir>: \\
  167.     'PqDescendants' stores intermediate results  in temporary  files; the
  168.     location  of  these  files  is  determined  by the value  selected by
  169.     'TmpName'.  If your default temporary directory does not  have enough
  170.     free disk space,  you can supply an alternative path  <dir>.  In this
  171.     case 'PqDescendants' stores its intermediate results  in  a temporary
  172.     subdirectory of <dir>.
  173.     Alternatively, you can globally set  the  variable 'ANUPQtmpDir', for
  174.     instance in your \".gaprc\"\ file, to point to a suitable location.
  175.  
  176. Alternatively,  you can pass 'PqDescendants'  a record  as  a  parameter,
  177. which  contains  as  entries some (or all) of the above mentioned.  Those
  178. parameters  which do not occur  in  the record are  set  to their default
  179. values.
  180.  
  181. Note that you cannot set both \"OrderBound\"\ and \"StepSize\".
  182.  
  183. In the first example  we  compute all descendants of the Klein four group
  184. which have exponent-2 class at most 5 and order at most $2^6$.
  185.  
  186. |    gap> F := FreeGroup( 2 );
  187.     Group( f.1, f.2 )
  188.     gap> F.relators := [ F.1^2, F.2^2, Comm(F.2, F.1) ];;
  189.     gap> G := AgGroupFpGroup( F );
  190.     Group( f.1, f.2 )
  191.     gap> G.name := "G";;
  192.     gap> G.automorphisms := [];;
  193.     gap> GroupHomomorphismByImages( G, G, [G.1, G.2], [G.2, G.1 * G.2] );
  194.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.2, f.1*f.2 ] )
  195.     gap> Add( G.automorphisms, last );
  196.     gap> GroupHomomorphismByImages( G, G, [G.1, G.2], [G.2, G.1] );      
  197.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.2, f.1 ] )
  198.     gap> Add( G.automorphisms, last );
  199.     gap> L := PqDescendants( G, "OrderBound", 6, "ClassBound", 5,     
  200.     >                        "AllDescendants", "AgAutomorphisms" );;
  201.     gap> Length(L);
  202.     83
  203.     gap> Number( L, x -> x.isCapable );
  204.     47
  205.     gap> List( L, x -> Size(x) );
  206.     [ 8, 8, 8, 16, 16, 16, 32, 16, 16, 16, 16, 16, 32, 32, 64, 64, 32, 
  207.       32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
  208.       32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 32, 32,
  209.       32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
  210.       64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64 ]
  211.     gap> List( L, x -> Length( PCentralSeries( x, 2 ) ) - 1 );
  212.     [ 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
  213.       3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
  214.       3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
  215.       4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5 ] |
  216.  
  217. In the second example we compute all  capable descendants of order  27 of
  218. the elementary abelian group of order 9.
  219.  
  220. |    gap> F := FreeGroup(2); 
  221.     Group( f.1, f.2 )
  222.     gap> F.relators := [ F.1^3, F.2^3, Comm(F.1, F.2) ];;
  223.     gap> G := AgGroupFpGroup( F );
  224.     Group( f.1, f.2 )
  225.     gap> G.name := "G";;
  226.     gap> G.automorphisms := [];;
  227.     gap> GroupHomomorphismByImages( G, G, [G.1, G.2], [G.1^2, G.2^2] );
  228.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.1^2, f.2^2 ] )
  229.     gap> Add( G.automorphisms, last );
  230.     gap> GroupHomomorphismByImages( G, G, [G.1, G.2], [G.2^2, G.1] );
  231.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.2^2, f.1 ] )
  232.     gap> Add( G.automorphisms, last );
  233.     gap> GroupHomomorphismByImages(G,G,[G.1,G.2],[G.1*G.2^2,G.1^2*G.2^2]);
  234.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], 
  235.     [ f.1*f.2^2, f.1^2*f.2^2 ] )
  236.     gap> Add( G.automorphisms, last );
  237.     gap> GroupHomomorphismByImages( G, G, [G.1,G.2], [G.1,G.1^2*G.2] );  
  238.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.1, f.1^2*f.2 ] )
  239.     gap> Add( G.automorphisms, last );
  240.     gap> GroupHomomorphismByImages( G, G, [G.1, G.2], [G.1^2, G.2] );
  241.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.1^2, f.2 ] )
  242.     gap> Add( G.automorphisms, last );
  243.     gap> L := PqDescendants( G, "OrderBound", 3,                   
  244.     >                           "ClassBound", 2, 
  245.     >                           "AgAutomorphisms" );;
  246.     gap> Length(L);
  247.     2
  248.     gap> List( L, x -> Size(x) );
  249.     [ 27, 27 ]
  250.     gap> List( L, x -> Length( PCentralSeries( x, 3 ) ) - 1 );
  251.     [ 2, 2 ] |
  252.  
  253. In  the  third  example,  we  compute  all  capable  descendants  of  the
  254. elementary abelian group of order  $5^2$ which have exponent-$5$ class at
  255. most $3$, exponent $5$, and are metabelian.
  256.  
  257. |    gap> F := FreeGroup(2);
  258.     Group( f.1, f.2 )
  259.     gap> F.relators := [F.1^5, F.2^5, Comm(F.2,F.1)];
  260.     [ f.1^5, f.2^5, f.2^-1*f.1^-1*f.2*f.1 ]
  261.     gap> G := AgGroupFpGroup(F); 
  262.     Group( f.1, f.2 )
  263.     gap> G.name := "G";;
  264.     gap> a1 := GroupHomomorphismByImages( G, G, [G.1, G.2], [G.1^2, G.2] );
  265.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.1^2, f.2 ] )
  266.     gap> a2 := GroupHomomorphismByImages(G,G,[G.1,G.2],[G.1^4*G.2,G.1^4]);
  267.     GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.1^4*f.2, f.1^4 ] )
  268.     gap> G.automorphisms := [ a1, a2 ];
  269.     [ GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.1^2, f.2 ] ), 
  270.       GroupHomomorphismByImages( G, G, [ f.1, f.2 ], [ f.1^4*f.2, f.1^4
  271.          ] ) ]
  272.     gap> L := PqDescendants(G,"Metabelian","ClassBound",3,"Exponent",5);
  273.     [ Group( G.1, G.2, G.3 ), Group( G.1, G.2, G.3, G.4 ), 
  274.       Group( G.1, G.2, G.3, G.4, G.5 ) ]
  275.     gap> List( L, x -> Length( PCentralSeries( x, 5 ) ) - 1 ); 
  276.     [ 2, 3, 3 ]
  277.     gap> List( L, x -> Length( DerivedSeries( x ) ) );           
  278.     [ 3, 3, 3 ]
  279.     gap> List( L, x -> Maximum( List( Elements(x), y -> Order(x,y) ) ) );
  280.     [ 5, 5, 5 ] |
  281.  
  282. This function requires the package \"anupq\"\ (see "RequirePackage").
  283.  
  284. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  285. \Section{PqList}
  286.  
  287. 'PqList( <file> )' \\
  288. 'PqList( <file>, <sub> )' \\
  289. 'PqList( <file>, <n> )'
  290.  
  291. The function 'PqList' reads a file  <file> and returns the list $L$ of ag
  292. groups defined in this file.
  293.  
  294. If list <sub> is  supplied as a parameter, the function returns 'Sublist(
  295. $L$, <sub> )'.  If an integer <n> is supplied, 'PqList' returns $L[<n>]$.
  296.  
  297. This  function  and  'SavePqList'  (see  "SavePqList")  can  be  used  to
  298. save and restore a list of descendants (see "PqDescendants").
  299.  
  300. This function requires the package \"anupq\"\ (see "RequirePackage").
  301.  
  302. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  303. \Section{SavePqList}
  304.  
  305. 'SavePqList( <name>, <list> )'
  306.  
  307. The function 'SavePqList' writes a list of  descendants  <list> to a file
  308. <name>.
  309.  
  310. This function and 'PqList' (see "PqList") can be used to save and restore
  311. results of 'PqDescendants' (see "PqDescendants").
  312.  
  313. This function requires the package \"anupq\"\ (see "RequirePackage").
  314.  
  315. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  316. %E  Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables
  317. %%
  318. %%  Local Variables:
  319. %%  mode:               outline
  320. %%  outline-regexp:     "\\\\Chapter\\|\\\\Section\\|%E"
  321. %%  fill-column:        73
  322. %%  eval:               (hide-body)
  323. %%  End:
  324. %%
  325.