home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / pq.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  47.4 KB  |  1,340 lines
  1. #############################################################################
  2. ##
  3. #A  pq.g                        GAP library                     Werner Nickel
  4. #A                                                           & Alice Niemeyer
  5. ##
  6. #A  @(#)$Id: pq.g,v 3.10 1992/08/19 11:24:41 fceller Rel $
  7. ##
  8. #Y  Copyright 1991,  Mathematics Research Section,  ANU,  Canberra, Australia
  9. ##
  10. ##   This file contains an  implementation of  the  $p$-quotient algorithm as
  11. ##  specified by  Havas and  Newman  ("Application  of computers to questions
  12. ##  like  those  of  Burnside"  in Lecture Notes in Mathematics 806, Springer
  13. ##  1980).  Many tricks and techniques  used in  this  implementation are not
  14. ##  published  and  we learnt  them in many discussions from  Mike Newman. He
  15. ##  also explained and  pointed out to us  important sections of  the FORTRAN
  16. ##  code  of the Canberra   Nilpotent  Quotient  Program, which  is  the only
  17. ##  (written)  source of information  on  the  implementation  and  the  fine
  18. ##  details of the $p$-Quotient Algorithm.
  19. ##
  20. ##   This  implementation is written for GAP 3.1 and Frank Celler's extension
  21. ##  of the Pc-Module which makes it possible to handle central extensions  of
  22. ##  $p$-groups  more efficiently  than  this  was  possible in  GAP 2.6.  The
  23. ##  current internal code supporting the needs for the $p$-quotient algorithm
  24. ##  was written by  Frank Celler according  to  the observations made in many
  25. ##  experimental  versions  of the  $p$-Quotient Algorithm.  At  the  time of
  26. ##  writing  the  current  implementation  runs within a factor of two of the 
  27. ##  FORTRAN standalone.
  28. ##
  29. ##  THE PQ-DATA-STRUCTURE RECORD:
  30. ##
  31. ##   The   $p$-Quotient  Algorithm   deals  with  finite   presentations  for
  32. ##  $p$-quotients of groups. In the implementation, we store a finite presen-
  33. ##  tation  of a $p$-quotient $Q$  of a group in a record which we will  call
  34. ##  the PQp record. It contains the following record fields :
  35. ##
  36. ##   .generators               A list of abstract generators which generate Q
  37. ##   .pcp                      An internal pcp-description for Q
  38. ##   .identity                 The identity element of the group Q
  39. ##   .dimensions               A  list, where dimensions[i] is the  dimension
  40. ##                             of the $i$-th factor in the lower exponent-$p$
  41. ##                             central series calculated by the  $p$-Quotient 
  42. ##                             Algorithm
  43. ##   .prime                    An integer, which is the prime $p$
  44. ##   .one                      A finite field element, the unit of  $GF(p)$
  45. ##   .maxgennr                 An integer used to create names for generators
  46. ##   .nrgens                   An integer, the  number  of  generators of the
  47. ##                             previously computed quotient, used to identify
  48. ##                             the last element in .generators which does not 
  49. ##                             lie in the $p$-multiplicator
  50. ##   .nrnewgens                An integer specifying  how many new generators
  51. ##                             are still  alive.  It  is  used  to  determine 
  52. ##                             quickly, whether the $p$-quotient is completed
  53. ##   .defining                 A list of two sets :
  54. ##          .defining[1]         -  contains  the  triangle-indices  of those
  55. ##                                  commutators that  define  a new  ( or, in
  56. ##                                  the  process  of  the $p$-cover algorithm
  57. ##                                  also, pseudo ) generator
  58. ##          .defining[2]         -  contains  the indices of those generators
  59. ##                                  whose $p$-th  powers  define  a  new ( or 
  60. ##                                  pseudo ) generator
  61. ##   .definedby                A list which contains the  definition  of  the 
  62. ##                             $k$-th generator  in  the  $k$-th place. There 
  63. ##                             are  three  different types of entries, namely
  64. ##                             lists, positive and negative integers :
  65. ##          [ j, i ]             -  the generator is defined as commutator of
  66. ##                                  the  $j$-th  and  the  $i$-th  element in 
  67. ##                                  .generators
  68. ##            i                  -  the generator is defined as $p$-th  power
  69. ##                                  of the $i$-th element in .generators
  70. ##           -i                  -  the generator is  defined  as an image of
  71. ##                                  the $i$-th generator  in the presentation
  72. ##                                  for  $G$,  consequently  it  must  be  of
  73. ##                                  weight 1
  74. ##   .isdefinition             A list of two boolean lists
  75. ##          .isdefinition[1]     -  the $(j-2)d+i$-th entry  is  true  if the
  76. ##                                  commutator of the $j$-th and  the  $i$-th
  77. ##                                  generator  is a  definition,  else  false 
  78. ##                                  ($d$=.dimensions[1])
  79. ##          .isdefinition[2]     -  the  $i$-th  entry  is true if the $p$-th
  80. ##                                  power  of  the  $i$-th  generator   is  a
  81. ##                                  definition, else false
  82. ##   .epimorphism              A  list  containing  an  image in $Q$ for each
  83. ##                             generator of  $G$.  The  image  is  one of the 
  84. ##                             following:
  85. ##                i              - the image is the $i$-th element of 
  86. ##                                 .generators
  87. ##                word           - the image is word,  which is a word in the 
  88. ##                                 generators of $Q$
  89. ##   .pInverse                 A list containing the inverse of $i$ in  GF(p)
  90. ##                             at position $i$.
  91. ##
  92. #H  $Log: pq.g,v $
  93. #H  Revision 3.10  1992/08/19  11:24:41  fceller
  94. #H  'exponents' is now added in 'FirstClassPQp'
  95. #H
  96. #H  Revision 3.9  1992/08/19  10:00:48  fceller
  97. #H  changed 'SavePQp' to 'Save'
  98. #H
  99. #H  Revision 3.8  1992/08/10  12:21:05  fceller
  100. #H  added 'FpGroup' support
  101. #H
  102. #H  Revision 3.7  1992/06/29  14:00:06  fceller
  103. #H  cleand up a few names
  104. #H
  105. #H  Revision 3.6  1992/06/04  07:04:20  fceller
  106. #H  added 'AgGroup' for PqPresentation
  107. #H
  108. #H  Revision 3.5  1992/04/03  18:22:09  martin
  109. #H  changed the author line
  110. #H
  111. #H  Revision 3.4  1992/02/20  16:41:58  fceller
  112. #H  '.relations' renamed to '.relators'.
  113. #H
  114. #H  Revision 3.3  1991/09/30  10:55:44  fceller
  115. #H  Long lines removed, they cause problems with mailer.
  116. #H
  117. #H  Revision 3.2  1991/09/24  15:50:10  fceller
  118. #H  Removed unnecessery error message.
  119. #H
  120. #H  Revision 3.1  1991/09/13  09:12:00  fceller
  121. #H  Inital Release under RCS
  122. #H
  123. ##
  124. ##
  125.  
  126.  
  127. #############################################################################
  128. ##
  129. #F  InfoPQ1( <arg> )  . . . . . . . . . . . . . . . . . . package information
  130. #F  InfoPQ2( <arg> )  . . . . . . . . . . . . . . . package debug information
  131. ##
  132. if not IsBound( InfoPQ1 )  then InfoPQ1 := Print;  fi;
  133. if not IsBound( InfoPQ2 )  then InfoPQ2 := Ignore;  fi;
  134.  
  135.  
  136. #############################################################################
  137. ##
  138.  
  139. #F  PQpOps  . . . .  . . . . . . . . . . . . . . . .  presentation operations
  140. ##
  141. PQpOps := rec();
  142.  
  143.  
  144. #############################################################################
  145. ##
  146. #F  PQpOps.Print( <P> ) . . . . . . . . . . . . . . . . .  print a PQp record
  147. ##
  148. PQpOps.Print := function( P )
  149.  
  150.     local   i,  j,  com,  lst;
  151.  
  152.     Print("PQp( rec( \n");
  153.     Print("   generators  := ", P.generators,",\n"  );
  154.     Print("   definedby   := ", P.definedby, ",\n"  );
  155.     Print("   prime       := ", P.prime, ",\n"      );
  156.     Print("   dimensions  := ", P.dimensions, ",\n" );
  157.     Print("   epimorphism := ", P.epimorphism, ",\n");
  158.  
  159.     Print("   powerRelators := [ " );
  160.     for i  in [1 .. Length(P.generators)]  do
  161.         if PowerPcp(P.pcp, i) = IdWord  then
  162.             Print(P.generators[i],"^",P.prime);
  163.         else
  164.             Print(P.generators[i],"^",P.prime,"/(",PowerPcp(P.pcp,i),")");
  165.         fi;
  166.         if i < Length(P.generators) then
  167.             Print(", ");
  168.         else
  169.             Print(" ],\n");
  170.         fi;
  171.     od;
  172.  
  173.     com := false;
  174.     lst := [];
  175.     Print( "   commutatorRelators := [ " );
  176.     for i  in [2 .. Length(P.generators)]  do
  177.         for j in  [1 .. i-1]  do
  178.             if CommPcp(P.pcp, i, j) <> IdWord  then
  179.                 if com  then
  180.                     Print(", ");
  181.                 else
  182.                     com := true;
  183.                 fi;
  184.                 Print("Comm(",P.generators[i],",",P.generators[j],
  185.                       ")/(",CommPcp(P.pcp, i, j),")");
  186.                 Add(lst, [i,j]);
  187.             fi;
  188.         od;
  189.     od;
  190.     Print(" ],\n   definingCommutators := ", lst, " ) )" );
  191.  
  192. end;
  193.  
  194.  
  195.  
  196. #############################################################################
  197. ##
  198. #F  PQpOps.AgGroup  . . . . . . . . . . . . . . . .  convert into an ag group
  199. ##
  200. PQpOps.AgGroup := function( P )
  201.     return AgGroupPcp(P.pcp);
  202. end;
  203.  
  204.  
  205. #############################################################################
  206. ##
  207. #F  PQpOps.FpGroup  . . . . . . . . . . . . . . . .  convert into an fp group
  208. ##
  209. PQpOps.FpGroup := function( P )
  210.     return FpGroup(AgGroupPcp(P.pcp));
  211. end;
  212.  
  213.  
  214. #############################################################################
  215. ##
  216. #F  PQp( <R> )  . . . . . . . . . . . . . . . . . . . .  restore a PQp record
  217. ##
  218. ##  'PQp' takes as argument a GAP record containing all information necessary
  219. ##  to  restore the internal pcp-description, such as the GAP  record created
  220. ##  by the function 'Print'.
  221. ##
  222. PQp := function(G)
  223.  
  224.     local       P, i, j, cw, ii, r, rr, k, w;
  225.  
  226.     P := Pcp("a", Length(G.generators), G.prime, "combinatorial");
  227.     P := rec( generators       := GeneratorsPcp(P),
  228.               pcp              := P,
  229.               prime            := G.prime,
  230.               one              := Z(G.prime)^0,
  231.               nrgens           := Length(G.generators),
  232.               maxgennr         := Length(G.generators)+1,
  233.               nrnewgens        := Length(G.generators),
  234.               defining         := [[],[]],
  235.               definedby        := Copy(G.definedby),
  236.               isdefinition     := [ BlistList([],[]),
  237.                                     BlistList([],[]) ],
  238.               dimensions       := Copy(G.dimensions),
  239.               epimorphism      := Copy(G.epimorphism),
  240.               isPQp            := true,
  241.               operations       := PQpOps
  242.          );
  243.  
  244.     for i  in [ 1 .. Length(G.generators) ]  do
  245.         Add(P.isdefinition[2], false);
  246.     od;
  247.     for i  in [ 1 .. Length(P.generators)*P.dimensions[1]]  do
  248.         Add(P.isdefinition[1], false);
  249.     od;
  250.     for k in [ 1 .. Length(P.definedby)] do
  251.         if IsList(P.definedby[k]) then
  252.             j := P.definedby[k][1];
  253.             i := P.definedby[k][2];
  254.             P.isdefinition[1][(j-2)*P.dimensions[1]+i] := true;
  255.             AddSet(P.defining[1], TriangleIndex(j,i));
  256.         elif P.definedby[k] > 0 then
  257.             P.isdefinition[2][P.definedby[k]] := true;
  258.             AddSet(P.defining[2], P.definedby[k]);
  259.         fi;
  260.     od;
  261.  
  262.     P.identity := P.generators[1]^0;
  263.  
  264.     # compute inverses of 1 .. p-1 in GF(p) as suggested by M. Sch"onert
  265.     r := PrimitiveRootMod( P.prime );  rr := r;
  266.     i := 1/r mod P.prime;              ii := i;
  267.     P.pInverse := [1];
  268.     while rr <> 1  do
  269.         P.pInverse[rr] := ii;
  270.         rr := rr * r mod P.prime;
  271.         ii := ii * i mod P.prime;
  272.     od;
  273.         
  274.     cw := [];
  275.     for i  in [ 1 .. Length(G.dimensions) ]  do
  276.         for j  in [ 1 .. G.dimensions[i] ]  do
  277.             cw[Length(cw)+1] := i;
  278.         od;
  279.     od;
  280.     DefineCentralWeightsPcp(P.pcp, cw);
  281.  
  282.     for i  in [ 1 .. Length(G.generators) ]  do
  283.         w := G.powerRelators[i]^-1 * G.generators[i]^G.prime;
  284.         DefinePowerPcp(P.pcp, i, MappedWord(w,G.generators,P.generators));
  285.     od;
  286.  
  287.     for i  in [ 1 .. Length(G.commutatorRelators) ]  do
  288.         w := G.commutatorRelators[i]^-1
  289.              * Comm(G.generators[G.definingCommutators[i][1]],
  290.                     G.generators[G.definingCommutators[i][2]]);
  291.         DefineCommPcp(P.pcp,
  292.                       G.definingCommutators[i][1],
  293.                       G.definingCommutators[i][2],
  294.                       MappedWord(w, G.generators, P.generators));
  295.     od;
  296.  
  297.     for i  in [ 1 .. Length(P.epimorphism) ]  do
  298.         if not IsInt(P.epimorphism[i])  then
  299.             P.epimorphism[i] :=
  300.                 MappedWord(G.epimorphism[i],G.generators,P.generators);
  301.         fi;
  302.     od;
  303.     return P;
  304.  
  305. end;
  306.  
  307. #############################################################################
  308. ##
  309. #F  SavePQp( <file>, <P>, <N> ) . . . . . . . . . . . . . . saves <P> to file
  310. ##
  311. ##  'SavePQp' prints the PQp record <P> to the file <file> with name <N>.
  312. ##
  313. PQpOps.Save := function( file, P, N )
  314.  
  315.     local       i;
  316.  
  317.     PrintTo(file, "");
  318.     for i  in [ 1 .. Length(P.generators) ]  do
  319.         AppendTo(file, P.generators[i], " := AbstractGenerator(\"",
  320.                  P.generators[i],"\");\n");
  321.     od;
  322.     AppendTo(file, N, " := ", P, ";");
  323.  
  324. end;
  325. SavePQp := PQpOps.Save;
  326.  
  327.  
  328. #############################################################################
  329. ##
  330.  
  331.  
  332. #F  InitPQp( <rank>, <prime> )  . . . . . . . . . .  initializes a PQp record
  333. ##  
  334. ##  'InitPQp' creates a  PQp record for an  elementary abelian  group of rank
  335. ##  <rank> and order <prime>^<rank>.
  336. ##
  337. InitPQp := function( rank, prime )
  338.  
  339.     local   i, ii, r, rr, P;
  340.  
  341.  
  342.     P := rec();
  343.     if rank > 0 then
  344.         P.pcp          := Pcp( "g", rank, prime, "combinatorial" );
  345.         P.generators   := GeneratorsPcp( P.pcp );
  346.         P.identity     := P.generators[1]^0;
  347.     else
  348.         P.generators := [];
  349.     fi;
  350.     P.dimensions   := [];
  351.     P.prime        := prime;
  352.     P.maxgennr     := Length(P.generators)+1;
  353.     P.nrgens       := 0;
  354.     P.nrnewgens    := 0;
  355.     P.one          := Z(P.prime)^0;
  356.     P.defining     := [ [], [] ];
  357.     P.definedby    := [];
  358.     P.isdefinition := [ BlistList( [], [] ), BlistList( [], [] ) ];
  359.     P.epimorphism  := [];
  360.     P.pInverse     := [1];
  361.     P.unused       := 0;
  362.     P.isPQp        := true;
  363.     P.operations   := PQpOps;
  364.  
  365.     # initialise the .definedby entries for the first <rank> generators
  366.     for i  in [ 1 .. Length(P.generators)]  do
  367.         P.definedby[i] := -i;
  368.     od;
  369.  
  370.     # compute inverses of 1 .. p-1 in GF(p) as suggested by M. Sch"onert
  371.     r := PrimitiveRootMod( P.prime );  rr := r;
  372.     i := 1/r mod P.prime;              ii := i;
  373.     while rr <> 1  do
  374.         P.pInverse[rr] := ii;
  375.         rr := rr * r mod P.prime;
  376.         ii := ii * i mod P.prime;
  377.     od;
  378.  
  379.     # initialise .epimorphism
  380.     for i  in [1 .. rank] do  P.epimorphism[i] := i;  od;
  381.     return P;
  382.  
  383. end;
  384.  
  385.  
  386. #############################################################################
  387. ##
  388. #F  AddGeneratorsPQp( <P>, <cl> ) . . . . . . . .  adds new/pseudo generators
  389. ##  
  390. ##  This function  adds the  new and pseudo generators to the PQp record  <P>
  391. ##  corresponding to  weight <cl>. Call a generator  $g$  a new generator  if
  392. ##  <cl> is the  maximal  class  of the $p$-quotient  and  call  it a  pseudo
  393. ##  generator otherwise.  Whether <cl> is  the maximal class is tested in the
  394. ##  code by comparing <cl> to the length of '<P>.dimensions'.
  395. ##
  396. ##  The rule for adding new/pseudo generators of weight <cl> is :
  397. ##  1) for a relation $[ b, a ] = w$ add a new/pseudo generator $g$ such that
  398. ##     the relation  becomes $[ b,  a  ] =   wg$, if  the relation is   not a
  399. ##     definition and $wt(a) =  1$  and $wt(b)  =  <cl>-1$.   Call   this the
  400. ##     definition of the new/pseudo generator $g$.
  401. ##  2) for a relation $a^p =  w$ add a new/pseudo generator $g$ such that the
  402. ##     $wt(a) = 1$ or $a$ is defined as a $p$-th  power and $wt(a) = <cl>-1$.
  403. ##     Call this the definition of $g$.
  404. ##
  405. AddGeneratorsPQp := function( P, cl )
  406.  
  407.     local   i, j, x, k, l;
  408.  
  409.  
  410.     # set l to the number of generators of weight less or equal cl
  411.     l := 0;
  412.     for i  in [1 .. cl]  do l := l + P.dimensions[i];  od;
  413.         
  414.     # Add new/pseudo generators to the commutators
  415.     k  := Length(P.definedby) + 1;
  416.     for  j  in [ l-P.dimensions[cl]+1 .. l]  do
  417.  
  418.         # define pseudo generators for commutator relations
  419.         for  i in [1 .. Minimum(P.dimensions[1],j-1)]  do
  420.  
  421.             # add new/pseudo generators to all  rhs of  relations,  which are
  422.             # not definitions
  423.             x := TriangleIndex(j,i);
  424.             if  cl = Length(P.dimensions)  then
  425.                 AddSet( P.defining[1], x );
  426.                 P.definedby[k] := [ j, i ];
  427.                 DefineCommPcp( P.pcp, j, i, P.generators[k] );
  428.                 k := k + 1;
  429.             elif  not x in P.defining[1] then
  430.                 AddSet( P.defining[1], x );
  431.                 P.definedby[k] := [ j, i ];
  432.                 AddCommPcp( P.pcp, j, i, P.generators[k] );
  433.                 k := k + 1;
  434.             fi;
  435.         od;
  436.     od;
  437.  
  438.     # add new/pseudo generators to the $p^{th}$-powers
  439.     for  i  in [l-P.dimensions[cl]+1 .. l]  do
  440.  
  441.         # Add  a new/pseudo  generator for each  generator  $a_i$, for  which
  442.         # $a_i$ is not a definition and $a_i$ is defined as $p$-th power
  443.         if  IsInt( P.definedby[i] ) then
  444.             if  cl = Length(P.dimensions)  then
  445.                 AddSet( P.defining[2], i );
  446.                 P.definedby[k] := i;
  447.                 DefinePowerPcp( P.pcp, i, P.generators[k] );
  448.                 k := k + 1;
  449.             elif not i in P.defining[2] then
  450.                 AddSet( P.defining[2], i );
  451.                 P.definedby[k] := i;
  452.                 AddPowerPcp( P.pcp, i, P.generators[k] );
  453.                 k := k + 1;
  454.             fi;
  455.         fi;
  456.     od;
  457.  
  458. end;
  459.  
  460.  
  461. #############################################################################
  462. ##
  463. #F  DefineGeneratorsPQp( <P> )  . . . . . . . . defines new/pseudo generators
  464. ##
  465. ##  DefineGeneratorsPQp() creates the new and pseudo generators necessary for
  466. ##  the computation of  the $p$-cover  of the group defined by the PQp record
  467. ##  <P> and adds them to the internal power commutator presentation '<P>.pcp'
  468. ##  of the PQp record by the function 'ExtendCentralPcp'.
  469. ##
  470. DefineGeneratorsPQp := function( P )
  471.  
  472.     local   l,  i,  nr_newgens, newgens, cl;
  473.  
  474.     # l will be the number of generators of weight less or equal <cl>
  475.     l := Sum( P.dimensions );
  476.     newgens := [];
  477.     for  cl in  Reversed( [1 .. Length(P.dimensions)] )  do
  478.         nr_newgens := 0;
  479.  
  480.         # The following  for-loop can  be avoided  by storing  the  number of
  481.         # generators per  class  defined  by  $p^{th}$-powers  in  the  group
  482.         # record.   But that should  not have  a  significant impact  on  the
  483.         # performance of the PQ.
  484.         for  i in [ l-P.dimensions[cl]+1 .. l]  do
  485.  
  486.             # Test if $a_i$ was defined as a $p$-th power
  487.             if  IsInt(P.definedby[i]) then
  488.                 nr_newgens := nr_newgens + 1;
  489.             fi;
  490.         od;
  491.  
  492.         # Compute the number of  commutators of the form [ cl, 1 ].  Note the
  493.         # different handling in case cl = 1.  If cl is the maximal class this
  494.         # gives us the number of new generators.
  495.         if cl = 1 then
  496.             nr_newgens := nr_newgens + P.dimensions[1]*(P.dimensions[1]-1)/2;
  497.         else
  498.             nr_newgens := nr_newgens + P.dimensions[1]*P.dimensions[cl];
  499.         fi;
  500.  
  501.         # Subtract from the  number of  generators  those that have survived.
  502.         # This is the number of pseudo generators.
  503.         if cl < Length(P.dimensions) then
  504.             nr_newgens := nr_newgens - P.dimensions[cl+1];
  505.         fi;
  506.  
  507.         if cl = Length(P.dimensions) then 
  508.             P.nrnewgens := P.nrgens + nr_newgens; 
  509.             P.nrnewgensleft := nr_newgens;
  510.         fi;
  511.  
  512.         # Create the new/pseudo generators.
  513.         if cl < Length(P.dimensions) then
  514.             for i in [ 1 .. nr_newgens ] do     # "p" as in "p"seudo
  515.                 Add( newgens, "p" );
  516.             od;
  517.         else
  518.             for i in [ 1 .. nr_newgens ] do
  519.                 Add(newgens,ConcatenationString("a",StringInt(P.maxgennr)));
  520.                 P.maxgennr := P.maxgennr + 1;
  521.             od;
  522.         fi;
  523.         l := l - P.dimensions[cl];
  524.     od;
  525.  
  526.     # define some pseudo generators to lift the epimorphism
  527.     for i in [ 1 .. Length(P.epimorphism) ] do
  528.         if not IsInt( P.epimorphism[i] ) then
  529.            Add( newgens, "e" ); # "e" as in epimorphism
  530.         fi;
  531.     od;
  532.     ExtendCentralPcp( P.pcp, newgens, P.prime );
  533.     P.generators := GeneratorsPcp( P.pcp );
  534.  
  535.     return P;
  536.  
  537. end;
  538.  
  539. #############################################################################
  540. ##
  541. #F  TailsPQp( <P> ) . . . . . . . .  computes a covering presentation for <P>
  542. ##
  543. ##  'TailsPQp' computes a not  necessarily consistent, covering  presentation
  544. ##  for <P>.  For  each class cl computed so far 'AddGeneratorsPQp' is called
  545. ##  to   add   the   new/pseudo    generators   created    by   a   call   to
  546. ##  'DefineGeneratorsPQp' for this class.
  547. ##
  548. ##  'AddGeneratorsPQp' modifies the relations of the form
  549. ##  1) $[ b, a ] = w$ with $wt(b) = cl$ and $wt(a) = 1$
  550. ##  2) $c^p      = v$  with $wt(c) = cl$ and $c$ is  either defined as $p$-th
  551. ##                                          power or $wt(c) = 1 (=cl)$.
  552. ##
  553. ##  A theoretical argument shows that for all other relations the word in the
  554. ##  new/pseudo generators with  which  to modify  each  relation (called  the
  555. ##  `tail' of the relation) can be computed.  This  is done  in this function
  556. ##  and the relations are modified accordingly.
  557. ##
  558. TailsPQp := function( P )
  559.  
  560.     local     i, j, k, clnrgen, cl, g, x, y, z, endcl, enddim, Q;
  561.  
  562.     Q := P.pcp;
  563.     clnrgen := Length(P.generators);
  564.  
  565.     P := DefineGeneratorsPQp(P);
  566.     for  cl in  Reversed( [1 .. Length(P.dimensions)] )  do
  567.  
  568.         # add new/pseudo generators
  569.         AddGeneratorsPQp(P, cl);
  570.  
  571.         # Compute the tails of the new/pseudo generators.  First the tails of
  572.         # the $p^{th}$-powers are computed
  573.         for  i in  Reversed([clnrgen-P.dimensions[cl]+1 .. clnrgen])  do
  574.  
  575.             # compute tails  for $p^{th}$-powers  $a_i^p$ for which $a_i$  is
  576.             # defined as a commutator
  577.             if IsList(P.definedby[i])  then
  578.                 g := P.definedby[i][1];
  579.                 y := P.generators[ g ];
  580.                 z := P.generators[ P.definedby[i][2] ];
  581.  
  582.                 #    (y^p*z) / (y^(p-1) * (y*z))
  583.                 x := DifferencePcp( Q,
  584.                          ProductPcp( Q, PowerPcp( Q, g ), z),
  585.                          ProductPcp( Q,
  586.                                      PowerPcp( Q, y, P.prime-1 ),
  587.                                      ProductPcp( Q, y, z ) ) );
  588.                 if x <> P.identity  then AddPowerPcp( Q, i, x );  fi;
  589.             fi;
  590.         od;
  591.         clnrgen := clnrgen - P.dimensions[cl];
  592.  
  593.         # Next compute the tails of the commutators
  594.         endcl  := P.nrgens;
  595.         for k  in [ cl .. Length(P.dimensions) ]  do
  596.             endcl := endcl - P.dimensions[k];
  597.         od;
  598.  
  599.         enddim := P.dimensions[1]+1;
  600.         k := 1;
  601.         while  cl-k >= k+1  do
  602.             for  i in  [enddim ..  enddim+P.dimensions[k+1]]  do
  603.                 if  IsList(P.definedby[i])  then
  604.                     # the second generator is defined as commutator
  605.                     y := P.generators[ P.definedby[i][1] ];
  606.                     z := P.generators[ P.definedby[i][2] ];
  607.                     g := ProductPcp( Q, y, z );
  608.                     j := endcl;
  609.                     while  j > i and j > endcl - P.dimensions[cl-k]  do
  610.                         x := P.generators[j];
  611.                         #  ((x*y)*z) / (x*(y*z))
  612.                         x := DifferencePcp( Q, 
  613.                                  ProductPcp( P.pcp,
  614.                                  ProductPcp(Q,x,y), z),
  615.                                      ProductPcp(Q,x,g) );
  616.                         if x <> P.identity then
  617.                            AddCommPcp( Q, j, i, x );
  618.                         fi;
  619.                          j := j - 1;
  620.                     od;
  621.                 elif  P.definedby[i] > 0  then
  622.  
  623.                     # The second generator is defined as $p$-th power
  624.                     # and is not one of the first generators (which are
  625.                     # defined by the epimorphism).
  626.                     z := P.definedby[i];
  627.                     y := P.generators[z];
  628.                     g := PowerPcp( Q, z );
  629.                     z := PowerPcp( Q,y,P.prime-1);
  630.                     j := endcl;
  631.                     while  j > i and j > endcl - P.dimensions[cl-k]  do
  632.                         x := P.generators[j];
  633.                         #  ((x*y) * y^(p-1)) / (x*y^p)
  634.                         x := DifferencePcp( Q,
  635.                                 ProductPcp( Q,
  636.                                     ProductPcp(Q,x,y), z),
  637.                                     ProductPcp(Q,x,g) );
  638.                         if x <> P.identity then
  639.                             AddCommPcp( Q, j, i, x );
  640.                         fi;
  641.                         j := j - 1;
  642.                     od;
  643.                 fi;
  644.             od;
  645.             endcl  := endcl  - P.dimensions[cl-k];
  646.             enddim := enddim + P.dimensions[k+1];
  647.             k      := k + 1;
  648.         od;
  649.     od;
  650.  
  651.     return P;
  652. end;
  653.  
  654. #############################################################################
  655. ##
  656. #F  EchelonizePQp( <P>, <sys>, <w> )  . . . . . .  echelonize <w> along <sys>
  657. ##
  658. ##  'EchelonizePQp'  takes the word  <w> in the  generators of <P> of highest
  659. ##  weight and views  it as a linear equation over $GF(p)$. This is possible,
  660. ##  because  the generators of highest  weight  are central and of order $p$.
  661. ##  Furthermore, <sys>  is a  system  of words in  the  generators  of <P> of
  662. ##  highest weight, also  regarded  as linear  equations and in reduced form.
  663. ##  'EchelonizePQp' reduces <w>  along the system of linear  equations <sys>.
  664. ##  If <w> is not the identity after the echelonisation,  it is added  to the
  665. ##  system of equations.
  666. ##
  667. EchelonizePQp := function( P, sys, w )
  668.  
  669.     local  wd, t, i;
  670.  
  671.     w := TailReducedPcp( P.pcp, sys.ls, w );
  672.  
  673.     if w = P.identity  then return 1; fi;
  674.  
  675.     wd := TailDepthPcp( P.pcp, w );
  676.     w := PowerPcp( P.pcp, w, P.pInverse[ ExponentPcp(P.pcp,w,wd) ] );
  677.  
  678.     sys.ls[ wd ] := w;
  679.     for i  in sys.del  do
  680.         t := ExponentPcp( P.pcp, sys.ls[i], wd );
  681.         if t <> 0  then
  682.             sys.ls[i] := DifferencePcp(P.pcp,sys.ls[i],PowerPcp(P.pcp,w,t));
  683.         fi;
  684.     od;
  685.     Add( sys.del, wd );
  686.     if wd <= P.nrnewgens then
  687.         P.nrnewgensleft := P.nrnewgensleft - 1;
  688.         if P.nrnewgensleft = 0 then return 0; fi;
  689.     fi;
  690.  
  691.     return 1;
  692.  
  693. end;
  694.  
  695. #############################################################################
  696. ##
  697. #F  ConsistencyPQp( <P> ) . . . . . . . . . . . . . determine inconsistencies
  698. ##
  699. ##  'ConsistencyPQp'  evaluates all the  relations of  the consistency  test.
  700. ##  Each relation which is not satisfied yields a linear equation. The set of
  701. ##  linear  equations is returned. In  the  case that  <P>  is  a  consistent
  702. ##  presentation the set of linear equations is empty. (cf. M.R. Vaughan-Lee:
  703. ##  "An Aspect of the Nilpotent Quotient Algorithm",  in Computational Group
  704. ##  Theory, edited by Michael D. Atkinson)
  705. ##
  706. ConsistencyPQp := function( P )
  707.  
  708.     local i, j, k, a, b, c,d,  wtb, nrwt, linsys, wt, ai, ap;
  709.  
  710.     linsys := rec( ls := [], del := [] );
  711.  
  712.     # store in nrwt[i] the number of generators of weight less than i
  713.     nrwt := [0];
  714.     for i in [2 .. Length(P.dimensions)+1 ] do
  715.         nrwt[i] := nrwt[i-1] + P.dimensions[i-1];
  716.     od;
  717.  
  718.     # Loop through all possible weights a consistency relation can have.
  719.     for wt in Reversed( [ 3 .. Length(P.dimensions)+1 ] ) do
  720.         InfoPQ2( "#I  ConsistencyPQp: (a^p) * a = a * (a^p)\n" );
  721.  
  722.         # Check the relations $a^p*a = a*a^p$
  723.         if wt mod 2 = 1 then
  724.             # run through all $a$ with $2*wt(a) + 1 = wt$
  725.             for i in [nrwt[(wt-1)/2]+1 .. nrwt[(wt-1)/2+1] ] do
  726.                 a  := P.generators[i];
  727.                 ap := PowerPcp( P.pcp, i );
  728.                 a  := DifferencePcp( P.pcp, 
  729.                          ProductPcp( P.pcp, ap, a ),
  730.                          ProductPcp( P.pcp, a, ap ));
  731.                 if a <> P.identity then
  732.                     if EchelonizePQp( P, linsys, a ) = 0 then
  733.                         return 0;
  734.                     fi;
  735.                 fi;
  736.             od;
  737.         fi;
  738.         InfoPQ2( "#I  ConsistencyPQp:  b*(a^p) = (b*a)*a^(p-1)\n" );
  739.  
  740.         # Check the consistency relation $b*(a^p) = b*a*(a^{(p-1)})$
  741.         # for b > a.
  742.         # wt = wt( b * a^p ) = wt(a) + wt(b) + 1 = wt
  743.         # Loop through possible weights for a, namely wt(a) = i
  744.         for i in [1 .. wt-2] do
  745.             for k in [nrwt[i]+1 .. nrwt[i+1]] do
  746.                 a  := P.generators[k];
  747.                 ap := PowerPcp( P.pcp, k );
  748.                 ai := PowerPcp( P.pcp,a,P.prime-1);
  749.                 d := nrwt[wt-i];
  750.                 # wt(b) = wt-i-1, thus d-1 is the last choice for b
  751.                 if P.isdefinition[2][k] then
  752.                     # b > ap was done in TailsPQp, here we do b <= ap
  753.                     d := Minimum(Position(P.generators,ap),d);
  754.                 fi;
  755.                 # run through $b$ with $d>=b>a$ and $wt(b) = wt-i-1$
  756.                 for j in [Maximum(k+1,nrwt[wt-i-1]+1) .. d] do
  757.                     b := P.generators[j];
  758.                     b := DifferencePcp( P.pcp,
  759.                              ProductPcp( P.pcp, b, ap ),
  760.                              ProductPcp( P.pcp,
  761.                                   ProductPcp(P.pcp,b,a), ai ));
  762.                     if b <> P.identity  then
  763.                        if EchelonizePQp( P, linsys, b ) = 0 then
  764.                             return 0;
  765.                         fi;
  766.                     fi;
  767.                 od;
  768.             od;
  769.         od;
  770.         InfoPQ2( "#I  ConsistencyPQp: (b^p)*a  =  b^(p-1)*b*a\n" );
  771.  
  772.         # Check the consistency relations $(b^p)*a = (b^{(p-1)})*b*a$
  773.         # wt = wt(b^p*a) = wt(a) + wt(b) + 1 = wt(b) + 2
  774.         # for b > a and wt(a) = 1
  775.         # Loop through the generators of weight 1
  776.         for  i in [1 .. P.dimensions[1]]  do
  777.             a := P.generators[i];
  778.             # run through all $b$ with $wt(b) = wt - 2$
  779.             for  j in [Maximum(i+1,nrwt[wt-2]+1) .. nrwt[wt-1]]  do
  780.                 if  not P.isdefinition[1][(j-2)*P.dimensions[1]+i]  then
  781.                     # if [b,a] is a definition of x, say then
  782.                     # b^p*a was used to compute the tail of x^p
  783.                     b := P.generators[j];
  784.                     b := DifferencePcp( P.pcp,
  785.                              ProductPcp( P.pcp, PowerPcp( P.pcp, j ), a),
  786.                              ProductPcp( P.pcp,
  787.                                  PowerPcp( P.pcp,b,P.prime-1),
  788.                                  ProductPcp(P.pcp,b,a)));
  789.                     if b <> P.identity  then
  790.                         if EchelonizePQp( P, linsys, b ) = 0 then
  791.                                 return 0;
  792.                         fi;
  793.                     fi;
  794.                 fi;
  795.             od;
  796.         od;
  797.         InfoPQ2( "#I  ConsistencyPQp: (c*b)*a  =  c*(b*a)\n" );
  798.  
  799.         # and  relations $(c*b)*a = c*(b*a)$
  800.         for i in [1 .. P.dimensions[1]] do 
  801.             a := P.generators[i];
  802.             # run through all $b$ with $wt(b) >= 1$ and
  803.             # $wt(b) <= wt(c) = wt - wt(b) - wt(a) = wt - wt(b) - 1$,
  804.             # which is  the condition $2 * wt(b) <= wt - 1$
  805.             wtb := 1;
  806.             while 2 * wtb <= wt - 1 do
  807.                 for j in [Maximum(i+1,nrwt[wtb]+1) .. nrwt[wtb+1]] do
  808.                     b := P.generators[j];
  809.                     ap := ProductPcp(P.pcp,b,a);
  810.                     d := nrwt[wt-wtb];
  811.                     if  P.isdefinition[1][(j-2)*P.dimensions[1]+i]  then
  812.                         d := Minimum(d,
  813.                             Position(P.generators,CommPcp(P.pcp,j,i)));
  814.                     fi;
  815.                     # wt(c) = wt - wt(b) - 1
  816.                     for k in [Maximum(j+1,nrwt[wt-wtb-1]+1) .. d] do
  817.                         c := P.generators[k];
  818.                         c := DifferencePcp( P.pcp,
  819.                                  ProductPcp(P.pcp,
  820.                                      ProductPcp(P.pcp,c,b),a),
  821.                                  ProductPcp(P.pcp, c, ap ) );
  822.                         if c <> P.identity  then
  823.                             if EchelonizePQp( P, linsys, c ) = 0 then
  824.                                 return 0;
  825.                             fi;
  826.                         fi;
  827.                     od;
  828.                 od;
  829.                 wtb := wtb + 1;
  830.             od;
  831.         od;
  832.     od;
  833.  
  834.     return linsys;
  835.  
  836. end;
  837.  
  838.  
  839. #############################################################################
  840. ##
  841. #F  ElimTailsPQp( <P>, <sys> )  . . . . . .  eliminate superfluous generators
  842. ##
  843. ##  'ElimTailsPQp'  takes  two parameters <P> and <sys>.  <sys> is a list  of
  844. ##  words in the generators of <P> of highest weight.  Each  word specifies a
  845. ##  relation between a superfluous generator  and other generators of highest
  846. ##  weight,  by which  the superfluous one is to be replaced.  'ElimTailsPQp' 
  847. ##  eliminates all occurrences of superfluous generators.
  848. ##
  849. ElimTailsPQp := function( P, sys )
  850.  
  851.     local       words, del, wasDefComm, wasDefPow, defby,
  852.                 i, j, k, r, Q, tmp;
  853.  
  854.     if sys.ls <> [] then
  855.         del := sys.del;
  856.         words := sys.ls;
  857.     fi;
  858.  
  859.     if sys.ls = [] or del = [] then
  860.         P.unused := 0;
  861.         Add( P.dimensions, Length( P.generators ) - P.nrgens );
  862.         P.nrgens := Length( P.generators );
  863.         i := P.dimensions[1];
  864.         j := P.dimensions[Length(P.dimensions)]; 
  865.  
  866.         # Enlarge the boolean list .isdefinition[1] and .isdefinition[2]
  867.         for k in [1..j] do Add( P.isdefinition[2], false ); od;
  868.         for k in [ 1..j*i ] do Add(P.isdefinition[1], false); od;
  869.  
  870.         # Update the entries in the boolean list .isdefinition[1]
  871.         # and .isdefinition[2]
  872.         for k in [P.nrgens-j+1 .. P.nrgens] do
  873.             if IsList(P.definedby[k]) then
  874.                  P.isdefinition[1][(P.definedby[k][1]-2)*i+P.definedby[k][2]] 
  875.                  := true;
  876.             elif P.definedby[k] > 0  then
  877.                  P.isdefinition[2][P.definedby[k]] := true;
  878.             fi;
  879.         od;
  880.         
  881.         return P;
  882.     fi;
  883.  
  884.     if Length( del ) = Length( P.generators )  then
  885.         P := InitPQp( 0, P.prime );
  886.         return( P );
  887.     fi;
  888.     Q := P.pcp;
  889.  
  890.     # At  first  run  through the  sequence  of  tails  and  delete  all  the
  891.     # definitions of new/pseudo generators
  892.     wasDefComm := [];
  893.     wasDefPow  := [];
  894.     for i in del  do
  895.         defby := P.definedby[ i ];
  896.         if IsList(defby) then
  897.  
  898.             # Use 'SubtractCommPcp', since del[i] is a tail generator
  899.             SubtractCommPcp( Q, defby[1], defby[2], words[i] );
  900.             AddSet( wasDefComm, TriangleIndex(defby[1],defby[2]));
  901.         elif defby > 0 then
  902.             SubtractPowerPcp( Q, defby, words[i] );
  903.             AddSet( wasDefPow, defby );
  904.         else
  905.             defby := -defby;
  906.             if IsInt( P.epimorphism[ defby ] ) then
  907.                 P.epimorphism[defby] :=
  908.                     DifferencePcp( P.pcp, P.generators[i],words[i]);
  909.             else
  910.                 P.epimorphism[defby] :=
  911.                     DifferencePcp( P.pcp, P.epimorphism[defby],words[i]);
  912.             fi;
  913.         fi;
  914.     od;
  915.  
  916.     # In this loop we check all the commutator relations and loop through all
  917.     # generators of the previous step
  918.     for i in [1 .. P.nrgens] do
  919.         # loop through all generators such that the
  920.         # Triangle Index is defined
  921.         for j  in [ 1 .. i - 1 ]  do
  922.             if not TriangleIndex(i,j) in P.defining[1] then
  923.  
  924.                 # The commutator  does not  define  a new  generator thus all
  925.                 # occurrences  of generators to  be  eliminated on the  right
  926.                 # hand side  of this commutator relation have to be  replaced
  927.                 # by corresponding words in the remaining generators.
  928.                 tmp := CommPcp( Q, i, j );
  929.                 if tmp <> P.identity  then
  930.                     r := TailReducedPcp( Q, words, tmp );
  931.                     DefineCommPcp( Q, i, j, r );
  932.                 fi;
  933.             fi;
  934.         od;
  935.     od;
  936.  
  937.     P.defining[1] := Difference( P.defining[1], wasDefComm );
  938.  
  939.     # In this loop we check all the  power relations and loop through all the
  940.     # generators
  941.     for i in [1 .. P.nrgens] do
  942.  
  943.         # Does the power define a generator ?
  944.         if not i in P.defining[2] then
  945.  
  946.             # The power does not define  a new generator thus all occurrences
  947.             # of generators to be eliminated  on the  right hand side of this
  948.             # power relation  have to be  replaced by corresponding words  in
  949.             # the remaining generators.
  950.             tmp := PowerPcp( Q, i );
  951.             if tmp <> P.identity then
  952.                  r := TailReducedPcp( Q, words, tmp );
  953.                  DefinePowerPcp( Q, i, r );
  954.             fi;
  955.         fi;
  956.     od;
  957.  
  958.     P.defining[2] := Difference( P.defining[2], wasDefPow );
  959.  
  960.     defby := [];
  961.     k := 1;
  962.     for i in [ 1 .. Length(P.definedby) ] do
  963.         if not i in del then
  964.             defby[k]   := P.definedby[i];
  965.             k := k + 1;
  966.         fi;
  967.     od;
  968.     P.definedby := defby;
  969.  
  970.     P.unused := Length( del );
  971.     Add( P.dimensions, Length( P.generators ) - P.nrgens - P.unused );
  972.     P.nrgens := Length( P.generators ) - Length( del );
  973.  
  974.     ShrinkPcp( Q, del );
  975.     P.generators := GeneratorsPcp(Q);
  976.  
  977.     i := P.dimensions[1];
  978.     j := P.dimensions[Length(P.dimensions)]; 
  979.  
  980.     # Enlarge the boolean list .isdefinition[1] and .isdefinition[2]
  981.     for k in [1..j] do Add( P.isdefinition[2], false ); od;
  982.     for k in [ 1..j*i ] do Add(P.isdefinition[1], false); od;
  983.  
  984.     # Update  the  entries   in  the  boolean  lists <P>.isdefinition[1]  and
  985.     # <P>.isdefinition[2]
  986.     for k in [P.nrgens-j+1 .. P.nrgens] do
  987.         if IsList(P.definedby[k]) then
  988.             P.isdefinition[1][(P.definedby[k][1]-2)*i+P.definedby[k][2]] 
  989.             := true;
  990.         elif P.definedby[k] > 0 then
  991.             P.isdefinition[2][P.definedby[k]] := true;
  992.         fi;
  993.     od;
  994.  
  995.     for k  in [ 1 .. Length(P.epimorphism) ]  do
  996.         if not IsInt( P.epimorphism[k] )  then
  997.  
  998.             # Convert the data structure
  999.             P.epimorphism[k] := SumPcp( Q, P.epimorphism[k], P.identity );
  1000.         else
  1001.             i := 0;
  1002.             for  j in [ 1 .. P.epimorphism[k] ]  do
  1003.                 if  not j in del  then
  1004.                     i := i + 1;
  1005.                 fi;
  1006.             od;
  1007.             P.epimorphism[k] := i;
  1008.         fi;
  1009.     od;
  1010.     return P;
  1011.  
  1012. end;
  1013.  
  1014.  
  1015. #############################################################################
  1016. ##
  1017. #F  LiftHomomorphismPQp( <G>, <P>, <linsys> ) .  lift homomorphism to p-cover
  1018. ##
  1019. ##  'LiftHomomorphismPQp' attempts to  lift the  homomorphism  from the given
  1020. ##  finitely presented group <G> onto the p-cover of a  previously calculated
  1021. ##  $p$-quotient. In doing so it obtains relations  between the generators of
  1022. ##  the $p$-multiplier in  order  to satisfy  the relations of  the  finitely
  1023. ##  presented group.  It uses these  relations to eliminate some (or possibly
  1024. ##  all) of the generators of the $p$-multiplier.
  1025. ##
  1026. LiftHomomorphismPQp := function( G, P, linsys )
  1027.  
  1028.     local   i, s, images, k, x;
  1029.  
  1030.     # determine the number of pseudo generators needed here
  1031.     k := 0;
  1032.     for i in [ 1 .. Length(P.epimorphism) ] do
  1033.         if not IsInt( P.epimorphism[i] ) then
  1034.             k := k+1;
  1035.         fi;
  1036.     od;
  1037.  
  1038.     k := Length(P.generators) - k + 1;
  1039.  
  1040.     # add pseudo generators to the images of the homomorphism
  1041.     for i in [ 1 .. Length(P.epimorphism) ] do
  1042.         if not IsInt( P.epimorphism[i] ) then
  1043.             P.epimorphism[i] :=
  1044.                 SumPcp( P.pcp, P.epimorphism[i],P.generators[k]);
  1045.             P.definedby[k] := -i;
  1046.             k := k+1;
  1047.         fi;
  1048.     od;
  1049.  
  1050.     # temporarily write all images as group elements
  1051.     images := Copy( P.epimorphism );
  1052.     for i in [ 1 .. Length(images) ] do
  1053.         if IsInt(images[i]) then
  1054.             images[i] := P.generators[images[i]];
  1055.         fi;
  1056.     od;
  1057.  
  1058.     # compute the images of the relations of P under
  1059.     # the epimorphism
  1060.     for i in [ 1 .. Length(G.relators) ] do
  1061.         s   := MappedWord( G.relators[i], G.generators,images );
  1062.         s   := NormalWordPcp( P.pcp, s );
  1063.         s   := PowerPcp( P.pcp, s, G.exponents[i] );
  1064.         EchelonizePQp( P, linsys, s );
  1065.     od;
  1066.  
  1067.     return [linsys,P];
  1068.  
  1069. end;
  1070.  
  1071.  
  1072.  
  1073. #############################################################################
  1074. ##
  1075. #F  CleanUpPQp( <P> ) . . . . . . . . . . . . . . . . . . . . .  clean up <P>
  1076. ##
  1077. CleanUpPQp := function( P )
  1078.  
  1079.     local i, defby;
  1080.  
  1081.     # Delete all the new and pseudo generators introduced
  1082.     for i in [ P.nrgens+1 .. Length(P.definedby) ] do
  1083.         defby := P.definedby[i];
  1084.         if IsList(defby) then
  1085.             RemoveSet( P.defining[1],TriangleIndex(defby[1],defby[2]) );
  1086.             P.isdefinition[1][(defby[1]-2)*P.dimensions[1]+defby[2]] 
  1087.                 := false;
  1088.         else
  1089.             if defby < 0 then defby := -defby; fi;
  1090.             RemoveSet( P.defining[2], defby );
  1091.             P.isdefinition[2][defby] := false;
  1092.         fi;
  1093.     od;
  1094.     P.definedby   := Sublist( P.definedby, [ 1 .. P.nrgens ] );
  1095.     ShrinkPcp( P.pcp, [P.nrgens+1 .. Length(P.generators)] );
  1096.     P.generators := GeneratorsPcp(P.pcp);
  1097.     P.nrgens     := Length(P.generators);
  1098.     P.nrnewgens  := 0;
  1099.  
  1100. end;
  1101.  
  1102. #############################################################################
  1103. ##
  1104. #F  FirstClassPQp( <G>, <p> ) . . . . . . . . computes the p-abelian quotient
  1105. ##
  1106. ##  'FirstClassPQp'  returns  a  PQp  record  for  the  exponent-$p$-class  1
  1107. ##  quotient of <G>.
  1108. ##
  1109. FirstClassPQp := function( G, p )
  1110.  
  1111.     local       erg, P;
  1112.  
  1113.     # add '<G>.exponents' and 'G.relators' if missing
  1114.     if not IsBound(G.relators)  then
  1115.         G.relators := [];
  1116.     fi;
  1117.     if not IsBound(G.exponents) then
  1118.         G.exponents := List(G.relators, x -> 1);
  1119.     fi;
  1120.  
  1121.     P := InitPQp(Length(G.generators), p);
  1122.     erg := ConsistencyPQp(P);
  1123.     if erg = 0 then
  1124.         CleanUpPQp(P);
  1125.         return P;
  1126.     fi;
  1127.     erg := LiftHomomorphismPQp(G, P, erg);
  1128.     P   := ElimTailsPQp( erg[2], erg[1] );
  1129.     return P;
  1130.  
  1131. end;
  1132.  
  1133.  
  1134.  
  1135. #############################################################################
  1136. ##
  1137. #F  PQuotient( <G>, <p>, <cl> ) . . . . . . .  computes a $p$-quotient of <G>
  1138. ##
  1139. ##  'PQuotient' computes the class <cl> $p$-quotient of the group  <G>  given
  1140. ##  by generators and relations. If <cl> is 0 it either computes the  largest
  1141. ##  $p$-quotient, if there is a largest, or  runs forever or until one of the
  1142. ##  following is satisfied:
  1143. ##
  1144. ##                a) GAP runs into a segmentation fault
  1145. ##                b) GAP runs into a bus error
  1146. ##                c) GAP runs out of memory
  1147. ##                d) K. Lux is using the program (will result in an error)
  1148. ##                e) GAP is killed by an annoyed user
  1149. ##                f) The machine crashes
  1150. ##                g) The machine is rebooted
  1151. ##                h) The sky falls down
  1152. ##
  1153. PQuotient := function(G, p, cl)
  1154.  
  1155.     local   i, forever, P, erg, t;
  1156.  
  1157.     # Check the arguments
  1158.     if not IsPrime(p) then
  1159.         Error("<p> must be a prime");
  1160.     fi;
  1161.     if not IsInt( cl ) or cl < 0 then
  1162.         Error("<cl> must be a non-negative integer");
  1163.     fi;
  1164.  
  1165.     # add '<G>.exponents' and 'G.relators' if missing
  1166.     if not IsBound(G.relators)  then
  1167.         G.relators := [];
  1168.     fi;
  1169.     if not IsBound(G.exponents) then
  1170.         G.exponents := List(G.relators, x -> 1);
  1171.     fi;
  1172.  
  1173.     # Who wants to run forever?
  1174.     forever := false;
  1175.     if cl = 0  then forever := true;  fi;
  1176.  
  1177.     # initialise <P>
  1178.     P := FirstClassPQp( G, p );
  1179.     erg := rec( ls := [], del := [] );
  1180.     if Length(P.generators) = 0 then return P; fi;
  1181.     t := Runtime();
  1182.     InfoPQ1( "#I  PQuotient: class 1 : ", P.dimensions[1], "\n" );
  1183.  
  1184.     # main loop
  1185.     i := 2;
  1186.     while i <= cl or forever do
  1187.        InfoPQ1( "#I  PQuotient: Runtime : ", Runtime()-t, "\n" );
  1188.        P   := TailsPQp(P);
  1189.        erg := ConsistencyPQp(P);
  1190.        if erg = 0 then 
  1191.           CleanUpPQp(P); 
  1192.           InfoPQ1( "#I  PQuotient: <G> has exponent-p-class :",
  1193.                    Length(P.dimensions), "\n",
  1194.                   "Runtime : ", Runtime()-t, "\n" );
  1195.           return P; 
  1196.        fi;
  1197.        erg := LiftHomomorphismPQp(G, P, erg);
  1198.        P   := ElimTailsPQp( erg[2], erg[1] );
  1199.  
  1200.        if P.dimensions[ Length( P.dimensions ) ] = 0  then
  1201.           P.dimensions := Sublist(P.dimensions, [1..Length(P.dimensions)-1]);
  1202.           P.nrnewgens := 0;
  1203.           InfoPQ1( "#I  PQuotient: <G> has exponent-p-class :",
  1204.                    Length(P.dimensions), "\n", "Runtime : ",
  1205.                    Runtime()-t, "\n" );
  1206.           return P;
  1207.        fi;
  1208.  
  1209.        InfoPQ1( "#I  PQuotient: class ", i, " : ",
  1210.                 P.dimensions[Length(P.dimensions)], "\n" );
  1211.        i := i+1;
  1212.     od;
  1213.     InfoPQ1( "#I  PQuotient: Runtime : ", Runtime()-t, "\n" );
  1214.     return P;
  1215.  
  1216. end;
  1217.  
  1218. pQuotient     := PQuotient;
  1219. PrimeQuotient := PQuotient;
  1220.  
  1221.  
  1222. #############################################################################
  1223. ##
  1224. #F  NextClassPQp( <G>, <P> )  . . . . . . . . . . . .  compute the next class
  1225. ##
  1226. ##  Let <P> be a PQp record for the class $c$-quotient of <G>. 'NextClassPQp'
  1227. ##  returns a PQp  record for the class  $c+1$ quotient  of <G>, if it exists
  1228. ##  and <P> otherwise.
  1229. ## 
  1230. NextClassPQp := function( G, P )
  1231.  
  1232.     local   P, erg;
  1233.  
  1234.     P   := TailsPQp(P);
  1235.     erg := ConsistencyPQp(P);
  1236.     if erg = 0 then
  1237.         InfoPQ1("#I  NextClassPQp: <G> has no larger p-quotient\n");
  1238.         CleanUpPQp(P);
  1239.         return P;
  1240.     fi;
  1241.     erg := LiftHomomorphismPQp(G, P, erg);
  1242.     P   := ElimTailsPQp( erg[2], erg[1] );
  1243.  
  1244.     if P.dimensions[ Length( P.dimensions ) ] = 0  then
  1245.         P.dimensions := Sublist( P.dimensions, [1..Length(P.dimensions)-1]);
  1246.         P.nrnewgens  := 0;
  1247.     fi;
  1248.     return P;
  1249.  
  1250. end;
  1251.  
  1252.  
  1253. #############################################################################
  1254. ##
  1255. #F  Weight( <P>, <w> )  . . . . . . . . . .  compute the weight of <w> in <P>
  1256. ##
  1257. ##  Let <P> be a PQp record and <w> a word in the generators of <P>. 'Weight'
  1258. ##  returns the weight of <w>.
  1259. ##
  1260. Weight := function( P, w )
  1261.     return P.operations.Weight(P, w);
  1262. end;
  1263.  
  1264. PQpOps.Weight := function (P, w )
  1265.  
  1266.     local   i, d, wt;
  1267.  
  1268.     d  := DepthPcp(P.pcp, w);
  1269.     i  := 1;
  1270.     wt := 1;
  1271.     while i < d do
  1272.         i  := i + P.dimensions[wt];
  1273.         wt := wt + 1;
  1274.     od;
  1275.     return wt-1;
  1276.  
  1277. end;
  1278.  
  1279. #############################################################################
  1280. ##
  1281. #F  PQpOps.Factorization( <P>, <w> )  . .  express w in the generators of <P>
  1282. ##
  1283. ##  Let <P> be a  PQp  record  and  <w>  a word  in  the generators  of  <P>.
  1284. ##  'PQpOps.Factorization' returns  a  word expressing  <w> in the  weight  1
  1285. ##  generators.
  1286. ##
  1287. PQpOps.Factorization := function( P, w )
  1288.  
  1289.     local    i, gens, wt;
  1290.  
  1291.     # check '<P>.abstractGenerators'
  1292.     if IsBound(P.abstractGenerators)  then
  1293.         if Length(P.abstractGenerators) <> Length(P.generators)  then
  1294.                Error("not enough abstract generators");
  1295.         fi;
  1296.     else
  1297.         P.abstractGenerators := P.generators;
  1298.     fi;
  1299.  
  1300.     # Build a list gens which contains  the  word defining generator i in the
  1301.     # i-th position. Note that we use the  operators * and ^, since we do not
  1302.     # want to collect the word in the group <P>.
  1303.     gens := [];
  1304.     for i in [1 .. Length(P.generators) ] do
  1305.         if IsInt( P.definedby[i] ) then
  1306.             if P.definedby[i] < 0 then
  1307.                 gens[i] := P.generators[i];
  1308.             else
  1309.                 gens[i] := P.generators[P.definedby[i]]^P.prime;
  1310.             fi;
  1311.         else
  1312.             gens[i] := P.generators[P.definedby[i][1]]^-1
  1313.                        * P.generators[P.definedby[i][2]]^-1
  1314.                        * P.generators[P.definedby[i][1]]
  1315.                        * P.generators[P.definedby[i][2]];
  1316.         fi;
  1317.     od;
  1318.  
  1319.     wt := TailDepthPcp( P.pcp,w );
  1320.     while wt > 1 do
  1321.         w  := MappedWord( w, P.abstractGenerators, gens );
  1322.         wt := wt - 1;
  1323.     od;
  1324.  
  1325.     return w;
  1326.  
  1327. end;
  1328.  
  1329. #############################################################################
  1330. ##
  1331.  
  1332. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1333. ##
  1334. ## Local Variables:
  1335. ## mode:           outline
  1336. ## outline-regexp: "#F\\|#V\\|#E"
  1337. ## eval:           (hide-body)
  1338. ## End:
  1339. ##
  1340.