home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / agcomple.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  33.5 KB  |  1,028 lines
  1. #############################################################################
  2. ##
  3. #A  agcomple.g                  GAP library                      Frank Celler
  4. ##
  5. #A  @(#)$Id: agcomple.g,v 3.9 1992/10/27 14:41:29 fceller Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains all polymorph functions for groups.
  10. ##
  11. #H  $Log: agcomple.g,v $
  12. #H  Revision 3.9  1992/10/27  14:41:29  fceller
  13. #H  fixed a bug in 'Complements'
  14. #H
  15. #H  Revision 3.8  1992/05/25  07:57:59  fceller
  16. #H  added condition test, fixed one more bug
  17. #H
  18. #H  Revision 3.7  1992/05/22  07:16:11  fceller
  19. #H  fixed missing 'RowSpace' in call to 'Elements',
  20. #H  add missing conversion using 'logTable'
  21. #H
  22. #H  Revision 3.6  1992/04/07  14:28:07  fceller
  23. #H  fixed a few typos
  24. #H
  25. #H  Revision 3.5  1992/04/07  12:53:37  fceller
  26. #H  changed comparison with '0'
  27. #H
  28. #H  Revision 3.4  1992/02/07  18:11:40  fceller
  29. #H  Initial GAP 3.1 release.
  30. #H
  31. #H  Revision 3.1  1991/09/24  15:41:55  fceller
  32. #H  Initial Release under RCS
  33. ##
  34.  
  35.  
  36. #############################################################################
  37. ##
  38. #F  InfoAgCo1( <arg> ) . . . . . . . . . . . . . . . . .  package information
  39. #F  InfoAgCo2( <arg> )  . . . . . . . . . . . . . . package debug information
  40. ##
  41. if not IsBound( InfoAgCo1 )  then InfoAgCo1 := Ignore;  fi;
  42. if not IsBound( InfoAgCo2 )  then InfoAgCo2 := Ignore;  fi;
  43.  
  44.  
  45. #############################################################################
  46. ##
  47. #F  BaseSteinitz( <V>, <U> )  . . . . . . . . . . . . . . . base of <V> / <U>
  48. ##
  49. ##  Let <V> be a row space, <U> be a subspace. Then 'BaseSteinitz'  returns a
  50. ##  record  describing  a base  for the factorspace   and ways   to decompose
  51. ##  vectors:
  52. ##
  53. ##  zero:           zero of <V> and <U>
  54. ##  factorzero:        zero of <V> / <U>
  55. ##  field:          field of <V> and <U>
  56. ##  vectorspace:    base of <V>
  57. ##  subspace:        base of <U>
  58. ##  factorspace:    base of a complement of <U> in <V>
  59. ##  heads:          a list of integers i_j, such that  if i_j>0 then a vector
  60. ##                   with head j is at position i_j  in factorspace.  If i_j<0
  61. ##                  then the vector is in subspace.
  62. ##
  63. BaseSteinitz := function( V, U )
  64.     local   BV,  BU,  F,  i,  j;
  65.  
  66.     BV := Base( V );
  67.     BU := Base( U );
  68.     F  := rec( field := V.field, zero := V.zero, heads := [],
  69.                subspace := BU, vectorspace := BV, factorspace := []  );
  70.     for i  in [ 1 .. Length(BU) ]  do
  71.         j := 1;
  72.         while BU[i][j] = F.field.zero  do j := j+1;  od;
  73.         F.heads[j] := -i;
  74.     od;
  75.     for i  in [ 1 .. Length(BV) ]  do
  76.         j := 1;
  77.         while BV[i][j] = F.field.zero  do j := j+1;  od;
  78.         if not IsBound( F.heads[j] )  then
  79.             Add( F.factorspace, BV[i] );
  80.             F.heads[j] := Length(F.factorspace);
  81.         fi;
  82.     od;
  83.     F.factorzero := List( [ 1 .. Length(BV)-Length(BU) ], x->F.field.zero );
  84.     return F;
  85.  
  86. end;
  87.  
  88.  
  89. #############################################################################
  90. ##
  91. #F  AffineBlocksCO( <S>, <mats> ) . . . . . . . . . . . . . . . . . . . local
  92. ##
  93. ##  Divide the vectorspace  into blocks using  the  affine operations of  <S>
  94. ##  described by <mats>.  Return representative  for  these blocks and  their
  95. ##  normalizers in <S>.
  96. ##
  97. AffineBlocksCO := function( S, mats )
  98.     local   dim, p, nul, one, C, L, blt, B, O, Q, i, j, v, w, n, z;
  99.  
  100.     # The affine operation of <S> is described via <mats> as
  101.     #
  102.     #      ( lll 0 )
  103.     #      ( lll 0 )
  104.     #      ( ttt 1 )
  105.     #
  106.     # where l  describes  the   linear operation and  t  the  translation the
  107.     # dimension  of   the  vectorspace  is of   dimension  one less  than the
  108.     # matrices <mats>.
  109.     #
  110.     dim := Length(mats[1]) - 1;
  111.     one := mats[1][1][1]^0;
  112.     nul := 0 * one;
  113.     p := CharFFE( mats[ 1 ][ 1 ][ 1 ] );
  114.     C := List( [ 1 .. dim ], x -> p );
  115.     Q := List( [ 1 .. dim ], x -> p ^ ( dim - x ) );
  116.     L := [];
  117.     for i  in [ 1 .. p-1 ]  do
  118.         L[ LogFFE( one * i ) + 1 ] := i;
  119.     od;
  120.  
  121.     # Make a boolean list of length <p> ^ <dim>.
  122.     blt := BlistList( [ 1 .. p ^ dim ], [] );
  123.     InfoAgCo2( "#I  AffineBlocksCO: ", p^dim, " elements in H^1\n" );
  124.     i := Position( blt, false );
  125.     B := [];
  126.  
  127.     # Run through this boolean list.
  128.     while i <> false  do
  129.         v := CoefficientsInt( C, ( i - 1 ) ) * one;
  130.         w := ShallowCopy( v );
  131.         Add( v, one );
  132.         O := AgOrbitStabilizer( S, mats, v );
  133.         for v  in O.orbit  do
  134.             n := 1;
  135.             for j  in [ 1 .. dim ]  do
  136.                 z := v[j];
  137.                 if z <> nul  then
  138.                       n := n + Q[j] * L[ LogFFE( z ) + 1 ];
  139.                 fi;
  140.             od;
  141.             blt[ n ] := true;
  142.         od;
  143.         InfoAgCo2( "#I  AffineBlockCO: |block| = ", Length(O.orbit), "\n" );
  144.         Add( B, rec( vector := w, stabilizer := O.stabilizer ) );
  145.         i := Position( blt, false );
  146.     od;
  147.     InfoAgCo2( "#I  AffineBlockCO: ", Length( B ), " blocks found\n" );
  148.     return B;
  149.  
  150. end;
  151.  
  152.  
  153. #############################################################################
  154. ##
  155. #F  NextCentralizerCO( <ocr>, <S>, <H> )  . . . . . . . . . . . . . . . local
  156. ##
  157. ##  Correct the blockstabilizer and return the stabilizer of <H> in <S>
  158. ##
  159. NextCentralizerCO := function( ocr, S, H )
  160.     local   gens,  pnt,  i;
  161.  
  162.     # Get the generators of <S> and correct them.
  163.     InfoAgCo2( "#I  NextCentralizerCO: correcting blockstabilizer\n" );
  164.     gens := ShallowCopy( Igs( S ) );
  165.     pnt  := ocr.complementToCocycle( H );
  166.     for i  in [ 1 .. Length( gens ) ]  do
  167.         gens[ i ] := gens[ i ] *
  168.             ConjugatingWordOC( ocr,
  169.                                ocr.complementToCocycle( H ^ gens[ i ] ),
  170.                                pnt );
  171.     od;
  172.     InfoAgCo2( "#I  NextCentralizerCO: blockstabilizer corrected\n" );
  173.     return SumAgGroup( AgSubgroup( S, gens, false ), ocr.centralizer );
  174.  
  175. end;
  176.  
  177.  
  178. #############################################################################
  179. ##
  180. #F  NextCocyclesCO( <cor>, <ocr>, <S> )    . . . . . . . . . . . . . . . . local
  181. ##
  182. ##  Get the next conjugacy classes of  complements  under  operation  of  <S>
  183. ##  using affine operation on the onecohomologygroup of <K>  and  <N>,  where
  184. ##  <ocr> := rec( group := <K>, module := <N> ).
  185. ##
  186. ##  <ocr>  is a  record  as  described  in 'OneCocyclesOC'.  The classes  are
  187. ##  returned as list of records rec( complement, centralizer ).
  188. ##
  189. NextCocyclesCO := function( cor, ocr, S )
  190.     local   K, N, Z, SN, B, L, LL, tau, phi, mats, i;
  191.  
  192.     # Try to split <K> over <M>, if it does not split return.
  193.     InfoAgCo2( "#I  NextCocyclesCO: computing cocycles\n" );
  194.     K := ocr.group;
  195.     N := ocr.module;
  196.     Z := OneCocyclesOC( ocr, true );
  197.     if IsBool( Z )  then
  198.         if IsBound( ocr.normalIn )  then
  199.             InfoAgCo2( "#I  NextCocyclesCO: no normal complements\n" );
  200.         else
  201.             InfoAgCo2( "#I  NextCocyclesCO: no split extension\n" );
  202.         fi;
  203.         return [];
  204.     fi;
  205.  
  206.     # If there is only one complement this is normal.
  207.     if Base( Z ) = []  then
  208.         InfoAgCo2( "#I  NextCocyclesCO: group of cycles is trivial\n" );
  209.         K := ocr.complement;
  210.         if IsBound(cor.condition) and not cor.condition(cor, K)  then
  211.             return [];
  212.         else
  213.            return [ rec( complement := K, centralizer := S ) ];
  214.         fi;
  215.     fi;
  216.  
  217.     # If  the  one  cohomology  group  is trivial, there is only one class of
  218.     # complements.  Correct  the  blockstabilizer and return. If we only want
  219.     # normal complements, this case cannot happen, as cobounds are trivial.
  220.     SN := AgSubgroup( S, FactorArg( S, N ).generators, false );
  221.     if Length(Base(ocr.oneCoboundaries))=Length(Base(ocr.oneCocycles))  then
  222.         InfoAgCo2( "#I  NextCocyclesCO: H^1 is trivial\n" );
  223.         K := ocr.complement;
  224.         if IsBound(cor.condition) and not cor.condition(cor, K)  then
  225.             return [];
  226.         fi;
  227.         S := NextCentralizerCO( ocr, SN, ocr.complement );
  228.         return [ rec( complement := K, centralizer := S ) ];
  229.     fi;
  230.  
  231.     # If <S> = <N>, there are  no new blocks  under the operation  of <S>, so
  232.     # get  all elements of  the one cohomology  group and return. If  we only
  233.     # want normal complements,  there also are no  blocks under the operation
  234.     # of <S>.
  235.     B := BaseSteinitz( ocr.oneCocycles, ocr.oneCoboundaries );
  236.     if SN.generators = [] or IsBound(ocr.normalIn)  then
  237.         L := Elements(RowSpace(B.factorspace, B.field, B.zero));
  238.         InfoAgCo2("#I  NextCocyclesCO: ",Length(L)," complements found\n");
  239.         if IsBound(ocr.normalIn)  then
  240.             InfoAgCo2("#I  NextCocyclesCO: normal complements, using H^1\n");
  241.             LL := [];
  242.             if IsBound(cor.condition)  then
  243.                 for i  in L  do
  244.                     K := ocr.cocycleToComplement(i);
  245.                     if cor.condition(cor, K)  then    
  246.                         Add(LL, rec(complement := K, centralizer := S));
  247.                     fi;
  248.                 od;
  249.             else
  250.                 for i  in L  do
  251.                     K := ocr.cocycleToComplement(i);
  252.                     Add(LL, rec(complement := K, centralizer := S));
  253.                 od;
  254.             fi;
  255.             return LL;
  256.         else
  257.             InfoAgCo2("#I  NextCocyclesCO: S meets N, using H^1\n");
  258.             LL := [];
  259.             if IsBound(cor.condition)  then
  260.                 for i  in L  do
  261.                     K := ocr.cocycleToComplement(i);
  262.                     if cor.condition(cor, K)  then
  263.                         S := ocr.centralizer;
  264.                         Add(LL, rec(complement := K, centralizer := S));
  265.                     fi;
  266.                 od;
  267.             else
  268.                 for i  in L  do
  269.                     K := ocr.cocycleToComplement(i);
  270.                     S := ocr.centralizer;
  271.                     Add(LL, rec(complement := K, centralizer := S));
  272.                 od;
  273.             fi;
  274.             return LL;
  275.         fi;
  276.     fi;
  277.  
  278.     # The situation is as follows.
  279.     #
  280.     #  S                   As <N>  does act trivial  on  the  onecohomology
  281.     #   \   K              group,  compute first blocks of this group under
  282.     #    \ / \             the operation of  <S>/<N>. But  as <S>/<N>  acts
  283.     #     N   ?            affine,  this can be done using affine operation
  284.     #      \ /             (given as matrices).
  285.     #       1
  286.     # Get  the  matrices describing the affine operations. The linear  part
  287.     # of the  operation  is just conjugation of the entries of cocycle. The
  288.     # translation are  commuators  with the  generators.  So check if <ocr>
  289.     # has a small generating set. Use only these to form the commutators.
  290.  
  291.     # Translation: (.. h ..) -> (.. [h,c] ..)
  292.     if IsBound( ocr.smallGeneratingSet )  then
  293.         tau := function( c )
  294.             local   l,  i,  j,  z,  v;
  295.             l := [];
  296.             for i  in ocr.smallGeneratingSet  do
  297.                 Add( l, Comm( ocr.generators[i], c ) );
  298.             od;
  299.             l := ocr.listToCocycle( l );
  300.             v := ShallowCopy( B.factorzero );
  301.             for i  in [ 1 .. Length(l) ]  do
  302.                 if LogVecFFE(l, i) <> false  then
  303.                 z := l[i];
  304.                     j := B.heads[i];
  305.                     if j > 0  then
  306.                         l := l - z * B.factorspace[j];
  307.                         v[j] := z;
  308.                     else
  309.                         l := l - z * B.subspace[-j];
  310.                     fi;
  311.                 fi;
  312.             od;
  313.             IsVector( v );
  314.             return v;
  315.         end;
  316.     else
  317.         tau := function( c )
  318.             local   l,  i,  j,  z,  v;
  319.             l := [];
  320.             for i  in ocr.generators  do
  321.                 Add( l, Comm( i, c ) );
  322.             od;
  323.             l := ocr.listToCocycle( l );
  324.             v := ShallowCopy( B.factorzero );
  325.             for i  in [ 1 .. Length(l) ]  do
  326.                 if LogVecFFE(l, i) <> false  then
  327.                     z := l[i];
  328.                     j := B.heads[i];
  329.                     if j > 0  then
  330.                         l := l - z * B.factorspace[j];
  331.                         v[j] := z;
  332.                     else
  333.                         l := l - z * B.subspace[-j];
  334.                     fi;
  335.                 fi;
  336.             od;
  337.             IsVector( v );
  338.             return v;
  339.         end;
  340.     fi;
  341.  
  342.     # Linear Operation: (.. hm ..) -> (.. (hm)^c ..)
  343.     phi := function( z, c )
  344.         local   l,  i,  j,  z,  v;
  345.         l := ocr.listToCocycle( List( ocr.cocycleToList( z ), x -> x ^ c ) );
  346.         v := ShallowCopy( B.factorzero );
  347.         for i  in [ 1 .. Length( l ) ]  do
  348.             if LogVecFFE( l, i ) <> false  then
  349.                 z := l[i];
  350.                 j := B.heads[i];
  351.                 if j > 0  then
  352.                     l := l - z * B.factorspace[j];
  353.                     v[j] := z;
  354.                 else
  355.                     l := l - z * B.subspace[-j];
  356.                 fi;
  357.             fi;
  358.         od;
  359.         IsVector( v );
  360.         return v;
  361.     end;
  362.  
  363.     # Fake things, <SN> and '<B>.factorspace' are not empty.
  364.     L := rec( base := B.factorspace, isDomain := true );
  365.  
  366.     # Construct the affine operations and blocks under them.
  367.     mats := AffineOperation( SN, L, phi, tau ).images;
  368.     L    := AffineBlocksCO( SN, mats );
  369.     InfoAgCo2( "#I  NextCocyclesCO:", Length( L ), " complements found\n" );
  370.  
  371.     # choose a representative from each block and correct the blockstab
  372.     LL := [];
  373.     for i  in L  do
  374.         K := ocr.cocycleToComplement(i.vector*B.factorspace);
  375.         if not IsBound(cor.condition) or cor.condition(cor, K)  then
  376.             if Z = []  then
  377.                 S := SumAgGroup(i.stabilizer, ocr.centralizer);
  378.             else
  379.                 S := NextCentralizerCO(ocr, i.stabilizer, K);
  380.             fi;
  381.             Add(LL, rec(complement := K, centralizer := S));
  382.         fi;
  383.     od;
  384.     return LL;
  385.  
  386. end;
  387.  
  388.  
  389. #############################################################################
  390. ##
  391. #F  NextCentralCO( <cor>, <ocr>, <S> )     . . . . . . . . . . . . . . . . local
  392. ##
  393. ##  Get the conjugacy classes of complements in case <ocr.module> is central.
  394. ##
  395. NextCentralCO := function( cor, ocr, S )
  396.     local   z,K,N,Z,SN,B,L,tau,gens,imgs,A,T,heads,dim,s,v,j,i;
  397.  
  398.     # Try to split <ocr.group>
  399.     K := ocr.group;
  400.     N := ocr.module;
  401.  
  402.     # If  <K>  is no split extension of <N> return the trivial list, as there
  403.     # are  no  complements.  We  compute  the cocycles only if the extenstion
  404.     # splits.
  405.     Z := OneCocyclesOC( ocr, true );
  406.     if IsBool( Z )  then
  407.         if IsBound( ocr.normalIn )  then
  408.             InfoAgCo2( "#I  NextCentralCO: no normal complements\n" );
  409.         else
  410.             InfoAgCo2( "#I  NextCentralCO: no split extension\n" );
  411.         fi;
  412.         return [];
  413.     fi;
  414.  
  415.     # if there is only one complement it must be normal
  416.     if Base(Z) = []  then
  417.         InfoAgCo2("#I  NextCentralCO: Z^1 is trivial\n");
  418.         K := ocr.complement;
  419.         if IsBound(cor.condition) and not cor.condition(cor, K)  then
  420.             return [];
  421.         else
  422.             return [ rec(complement := K, centralizer := S) ];
  423.         fi;
  424.     fi;
  425.  
  426.     # If  the  one  cohomology  group  is trivial, there is only one class of
  427.     # complements.  Correct  the  blockstabilizer and return. If we only want
  428.     # normal complements, this cannot happen, as the cobounds are trivial.
  429.     SN := AgSubgroup(S, FactorArg(S, N).generators, false);
  430.     if Length(Base(ocr.oneCoboundaries))=Length(Base(ocr.oneCocycles))  then
  431.         InfoAgCo2( "#I  NextCocyclesCO: H^1 is trivial\n" );
  432.         K := ocr.complement;
  433.         if IsBound(cor.condition) and not cor.condition(cor, K)  then
  434.             return [];
  435.         else
  436.             S := NextCentralizerCO( ocr, SN, ocr.complement );
  437.             return [ rec(complement := K, centralizer := S) ];
  438.         fi;
  439.     fi;
  440.  
  441.     # If  <S>  =  <N>, there are no new blocks under the operation of <S>, so
  442.     # get  all elements of the onecohomologygroup and return. If we only want
  443.     # normal  complements,  there  also  are no blocks under the operation of
  444.     # <S>.
  445.     B := BaseSteinitz( ocr.oneCocycles, ocr.oneCoboundaries );
  446.     if SN.generators = [] or IsBound( ocr.normalIn )  then
  447.         if IsBound( ocr.normalIn )  then
  448.             InfoAgCo2("#I  NextCocyclesCO: normal complements, using H^1\n");
  449.         else
  450.             InfoAgCo2( "#I  NextCocyclesCO: S meets N, using H^1\n" );
  451.             S := ocr.centralizer;
  452.         fi;
  453.         L := Elements( RowSpace( B.factorspace, B.field, B.zero ) );
  454.         T := [];
  455.         for i  in L  do
  456.             K := ocr.cocycleToComplement(i);
  457.             if not IsBound(cor.condition) or cor.condition(cor, K)  then
  458.                 Add(T, rec(complement := K,  centralizer := S));
  459.             fi;
  460.         od;
  461.         InfoAgCo2( "#I  NextCocyclesCO: ",Length(T)," complements found\n" );
  462.         return T;
  463.     fi;
  464.  
  465.     # The  conjugacy  classes  of  complements  are cosets of the cocycles of
  466.     # 0^S. If 'smallGeneratingSet' is given, do not use this gens.
  467.  
  468.     # Translation: (.. h ..) -> (.. [h,c] ..)
  469.     if IsBound( ocr.smallGeneratingSet )  then
  470.         tau := function( c )
  471.             local   l;
  472.             l := [];
  473.             for i  in ocr.smallGeneratingSet  do
  474.                 Add( l, Comm( ocr.generators[ i ], c ) );
  475.             od;
  476.             return ocr.listToCocycle( l );
  477.         end;
  478.     else
  479.         tau := function( c )
  480.             local   l;
  481.             l := [];
  482.             for i  in ocr.generators  do
  483.                 Add( l, Comm( i, c ) );
  484.             od;
  485.             return ocr.listToCocycle( l );
  486.         end;
  487.     fi;
  488.     gens := Igs( SN );
  489.     imgs := List( gens, tau );
  490.  
  491.     # Now get a base for the subspace 0^S. For those zero  images which are
  492.     # not part of a base a generators of the stabilizer can be generated.
  493.     #     B   holds the base,
  494.     #     A   holds the correcting elements for the base vectors,
  495.     #     T   holds the stabilizer generators.
  496.     dim := Length( imgs[ 1 ] );
  497.     A := [];
  498.     B := [];
  499.     T := [];
  500.     heads := [ 1 .. dim ] * 0;
  501.  
  502.     # Get the base starting with the last one and go up.
  503.     for i  in Reversed( [ 1 .. Length(imgs) ] )  do
  504.         s := gens[i];
  505.         v := imgs[i];
  506.         j := 1;
  507.         while j <= dim and LogVecFFE( v, j ) = false  do
  508.             j := j + 1;
  509.         od;
  510.         while j <= dim and heads[j] <> 0  do
  511.             z := v[j] / B[heads[j]][j];
  512.             if z <> 0*z  then
  513.                 s := s / A[heads[j]] ^ ocr.logTable[LogFFE(z)+1];
  514.             fi;
  515.             v := v - v[j] / B[heads[j]][j] * B[heads[j]];
  516.             while j <= dim and LogVecFFE( v, j ) = false  do
  517.                 j := j + 1;
  518.             od;
  519.         od;
  520.         if j > dim  then
  521.             Add( T, s );
  522.         else
  523.             Add( B, v );
  524.             Add( A, s );
  525.             heads[ j ] := Length( B );
  526.         fi;
  527.     od;
  528.  
  529.     # So  <T>  now  holds a reversed list of generators for a stabilizer. <B>
  530.     # is  a  base for 0^<S> and <cocycles>/0^<S> are the conjugacy classes of
  531.     # complements.
  532.     S := SumAgGroup(N, AgSubgroup(S, Reversed(T), false));
  533.     if B = []  then
  534.         B := Elements(Z);
  535.     else
  536.         B := BaseSteinitz(Z, RowSpace(B, Z.field, Z.zero));
  537.         B := Elements(RowSpace(B.factorspace, B.field, B.zero));
  538.     fi;
  539.     L := [];
  540.     for i  in B  do
  541.         K := ocr.cocycleToComplement(i);
  542.         if not IsBound(cor.condition) or cor.condition(cor, K)  then
  543.             Add(L, rec(complement := K, centralizer := S));
  544.         fi;
  545.     od;
  546.     InfoAgCo2("#I  NextCentralCO: ", Length(L), " complements found\n");
  547.     return L;
  548.  
  549. end;
  550.  
  551.  
  552. #############################################################################
  553. ##
  554. #F  NextNormalCO( <cor>, <ocr>, <S>, <L> )  . . . . . . . . . . . . . . local
  555. ##
  556. ##  Compute  the  conjugacy  classes,  if  <L>  is  a  normal subgroup of the
  557. ##  intersection of all complements.
  558. ##
  559. NextNormalCO := function( cor, ocr, S, L )
  560.     local   K,  N,  T,  i,  new,  B;
  561.  
  562.     K := ocr.group;
  563.     N := ocr.module;
  564.  
  565.     # The situtation is as follows.
  566.     #
  567.     #   SL                We first compute the conjugacy  classes
  568.     #   / \               modulo <L>. Then the complements modulo
  569.     #  S   \              1 are the complete preimages.
  570.     #   \   A   K         The centralizer <B> is the intersection
  571.     #    \ / \ / \        of <S> and the stabilizer  <A>. As  <S>
  572.     #     B   NL  ?       is normal (S = C_M(K)) this is easy.
  573.     #      \ / \ /
  574.     #       N   L
  575.     #        \ /
  576.     #         1
  577.     #
  578.     new := rec();
  579.     new.group := AgSubgroup(K, FactorArg(K, L).generators, false);
  580.     new.module:= AgSubgroup(K,FactorArg(SumAgGroup(N,L),L).generators,false);
  581.     S := AgSubgroup(S, FactorArg(S, L).generators, false);
  582.  
  583.     # give some information about the new groups
  584.     InfoAgCo2("#I  NextNormalCO: old composition length: ",
  585.               Length(Igs(ocr.group)),", new: ",Length(Igs(new.group)),"\n");
  586.  
  587.     # The   information  of   <pPrimeSets>  or  <smallGeneratingSets>  cannot
  588.     # be mantained  without  much   effort.  So get  the   complements  using
  589.     # 'NextCocyclesCO'.
  590.     B := NextCocyclesCO(cor, new, S);
  591.     T := [];
  592.     InfoAgCo2( "#I  NextNormalCO: computing preimages and intersections\n" );
  593.     for i  in B  do
  594.         K := SumAgGroup(L, i.complement.group);
  595.         if not IsBound(cor.condition) or cor.condition(cor, K)  then
  596.             Add(T, rec(complement  := K,
  597.                        centralizer := NormalIntersection(S, i.centralizer)));
  598.         fi;
  599.     od;
  600.     return T;
  601.  
  602. end;
  603.  
  604.  
  605. #############################################################################
  606. ##
  607. #F  NextComplementsCO( <cor>, <S>, <K>, <M> ) . . . . . . . . . . . . . local
  608. ##
  609. NextComplementsCO := function( cor, S, K, M )
  610.     local   L,  p,  C,  ocr;
  611.  
  612.     if M.generators = []  then
  613.         if IsBound(cor.condition) and not cor.condition(cor, K)  then
  614.             return [];
  615.         else
  616.             return [ rec( complement := K, centralizer := S ) ];
  617.         fi;
  618.     elif IntersectionSet( FactorsAgGroup(M), FactorsAgGroup(K,M) ) = []  then
  619.  
  620.         # If <K> and <M> are coprime, <K> splits.
  621.         InfoAgCo2( "#I  NextComplementsCO: coprime case, <K> splits\n" );
  622.         ocr := rec( group := K, module := M );
  623.         if IsBound( cor.generators )  then
  624.             ocr.generators := cor.generators;
  625.         fi;
  626.         if IsBound( cor.smallGeneratingSet )  then
  627.             ocr.smallGeneratingSet := cor.smallGeneratingSet;
  628.             ocr.generatorsInSmall  := cor.generatorsInSmall;
  629.         elif IsBound( cor.primes )  then
  630.             p := RelativeOrderAgWord( M.generators[ 1 ] );
  631.             if p in cor.primes  then
  632.                 ocr.pPrimeSet := cor.pPrimeSets[ Position( cor.primes, p ) ];
  633.             fi;
  634.         fi;
  635.         if IsBound( cor.relators )  then
  636.             ocr.relators := cor.relators;
  637.         fi;
  638.         ocr.complement := CoprimeComplement( K, M );
  639.         OneCoboundariesOC( ocr );
  640.         if     IsBound( cor.normalComplements )
  641.            and cor.normalComplements
  642.            and Base( ocr.coboundaries ) <> []
  643.         then
  644.             return [];
  645.         else
  646.             K := ocr.complement;
  647.             if IsBound(cor.condition) and not cor.condition(cor, K)  then
  648.                 return [];
  649.             fi;
  650.             S := AgSubgroup( S, FactorArg( S, M ).generators, false );
  651.             S := NextCentralizerCO( ocr, S, K );
  652.             return [ rec( complement := K, centralizer := S ) ];
  653.         fi;
  654.     else
  655.  
  656.         # In the non-coprime case, we must construct cocycles.
  657.         ocr := rec( group := K, module := M );
  658.         if IsBound( cor.generators )  then
  659.             ocr.generators := cor.generators;
  660.         fi;
  661.         if IsBound( cor.normalComplement ) and cor.normalComplements  then
  662.             ocr.normalIn := S;
  663.         fi;
  664.         if IsBound( cor.normalSubgroup )  then
  665.             L := cor.normalSubgroup( S, K, M );
  666.             if L.generators = []  then
  667.                 return NextCocyclesCO(cor, ocr, S);
  668.             else
  669.                 return NextNormalCO(cor, ocr, S, L);
  670.             fi;
  671.         else
  672.             if IsBound( cor.smallGeneratingSet )  then
  673.                    ocr.smallGeneratingSet := cor.smallGeneratingSet;
  674.                 ocr.generatorsInSmall  := cor.generatorsInSmall;
  675.             elif IsBound( cor.primes )  then
  676.                 p := RelativeOrderAgWord( M.generators[ 1 ] );
  677.                 if p in cor.primes  then
  678.                     ocr.pPrimeSet := cor.pPrimeSets[Position(cor.primes,p)];
  679.         fi;
  680.             fi;
  681.             if IsBound( cor.relators )  then
  682.                 ocr.relators := cor.relators;
  683.             fi;
  684.             if    ( cor.useCentral and IsCentral( Parent(M), M ) )
  685.                  or ( cor.useCentralSK and IsCentral(S,M) and IsCentral(K,M) )
  686.             then
  687.                 return NextCentralCO(cor, ocr, S);
  688.             else
  689.                 return NextCocyclesCO(cor, ocr, S);
  690.             fi;
  691.         fi;
  692.     fi;
  693.  
  694. end;
  695.  
  696.  
  697. #############################################################################
  698. ##
  699. #F  ComplementsCO( <cor>, <G>, <n>, <all> ) . . . . . . . . . . . . . . local
  700. ##
  701. ##  Compute the complements in <G> of the  <n>.th elementary abelian subgroup
  702. ##  in  the elementary abelian  series of <G>.  If  <all>  is  true, find all
  703. ##  (conjugacy classes) of  complements.  Otherwise   try  to find  just  one
  704. ##  complement.
  705. ##
  706. ComplementsCO := function( cor, G, n, all )
  707.     local   time, E, C, r, a, a0, FG, FE, nextStep, found, i, j;
  708.  
  709.     # this function will only work for parent groups
  710.     if not IsParent( G )  then
  711.         Error( "<G> must be a parent group" );
  712.     fi;
  713.  
  714.     # give some information and start timing
  715.     InfoAgCo2( "#I  Complements: initialize factorgroups\n" );
  716.     time := Runtime();
  717.  
  718.     # compute the complement of <n>.th element of <E>
  719.     if not IsBound(cor.elementaryAbelianSeries)  then
  720.         cor.elementaryAbelianSeries := ElementaryAbelianSeries(G);
  721.     fi;
  722.     if not ForAll( cor.elementaryAbelianSeries, IsElementAgSeries ) then
  723.         Error( "the ag series must refine elementary abelian series" );
  724.     fi;
  725.  
  726.     # we only need the series beginning from position <n>
  727.     E := cor.elementaryAbelianSeries;
  728.     E := Sublist( E, [ n .. Length(E) ] );
  729.     r := Length(E);
  730.  
  731.     # Construct the homomorphisms <a>[i] = <G>/<E>[i+1] -> <G>/<E>[i].
  732.     a  := HomomorphismsSeries( G, E );
  733.     a0 := a[1];
  734.     a  := Sublist( a, [ 2 .. r ] );
  735.  
  736.     # <FG> contains the factorgroups <G>/<E>[1], ..., <G>/<E>[<r>].
  737.     FG := List( a, x -> x.range );
  738.     Add( FG, a[r-1].source );
  739.  
  740.     # <FE> contains the modules -, <E>[1]/<E>[2], ..., <E>[r-1]/<E>[r].
  741.     FE := [];
  742.     FE[r] := E[r-1];
  743.     for i  in [ 2 .. r-1 ]  do
  744.         FE[i] := E[i-1];
  745.         for j  in Reversed( [ i .. r-1 ] )  do
  746.             FE[i] := Image( a[j], FE[i] );
  747.         od;
  748.     od;
  749.  
  750.     # As all entries in <cor> are optional, initialize them if they are not
  751.     # present in <cor> with the following defaults.
  752.     #
  753.     #     'elementaryAbelianSeries' : standard elementary abelian series
  754.     #                                 (this happened already above)
  755.     #     'generators'              : standard generators
  756.     #     'relators'                : pc-relators
  757.     #     'useCentral'              : false
  758.     #     'useCentralSK'            : false
  759.     #     'normalComplements'       : false
  760.     #
  761.     if not IsBound( cor.useCentral )  then
  762.         cor.useCentral := false;
  763.     fi;
  764.     if not IsBound( cor.useCentralSK )  then
  765.         cor.useCentralSK := false;
  766.     fi;
  767.     if not IsBound( cor.normalComplements )  then
  768.         cor.normalComplements := false;
  769.     fi;
  770.     if IsBound( cor.generators )  then
  771.         cor.generators := List( cor.generators, x -> Image(a0, x) );
  772.     else
  773.         cor.generators := Cgs( FG[1] );
  774.     fi;
  775.     if not IsBound( cor.normalSubgroup )  then
  776.         cor.group  := FG[1];
  777.         cor.module := TrivialSubgroup( FG[1] );
  778.         OCAgGroupOps.AddRelations(cor);
  779.     fi;
  780.  
  781.     # The  following  function will be called recursively in order to descend
  782.     # the tree and reach a complement.  <nr> is the current level.
  783.     nextStep := function( S, K, nr )
  784.         local   M,  NC,  X;
  785.  
  786.         # give information about the level reached
  787.         InfoAgCo1( "#I  Complements: reached level ", nr, " of ", r, "\n" );
  788.  
  789.         # if this is the last level we have a complement, add it to <C>
  790.         if nr = r  then
  791.             Add( C, rec( complement := K, centralizer := S ) );
  792.             InfoAgCo1( "#I  Complements: next class found, ",
  793.                        "total ", Length(C), " complement(s), ",
  794.                        "time=", Runtime() - time, "\n" );
  795.             found := true;
  796.  
  797.         # otherwise try to split <K> over <M> = <FE>[<nr>+1]
  798.          else
  799.             S := PreImage( a[nr], S );
  800.             M := FE[nr+1];
  801.             cor.module := M;
  802.  
  803.             # we cannot take the 'PreImage' as this changes the gens
  804.             cor.generators := List( K.generators, x ->
  805.                                     PreImagesRepresentative(a[nr],x) );
  806.             K := Subgroup( FG[nr+1], cor.generators );
  807.  
  808.             # now 'NextComplementsCO' will try to find the complements
  809.             NC := NextComplementsCO( cor, S, K, M );
  810.  
  811.             # try to step down as fast as possible
  812.             for X  in NC  do
  813.                 nextStep( X.centralizer, X.complement, nr+1 );
  814.                 if found and not all  then
  815.                     return;
  816.                 fi;
  817.             od;
  818.         fi;
  819.     end;
  820.  
  821.     # in <C> we will collect the complements modulo <E>[r]
  822.     C := [];
  823.  
  824.     # ok, start 'nextStep'  with trivial module
  825.     InfoAgCo1("#I  Complements: starting search, time=",Runtime()-time,"\n");
  826.     found := false;
  827.     nextStep( AgSubgroup( FG[ 1 ], [], true ),
  828.               AgSubgroup( FG[ 1 ], cor.generators, false ),
  829.               1 );
  830.  
  831.     # some timings
  832.     InfoAgCo1( "#I  Complements: ",Length(C)," complement(s) found, ",
  833.                "time=", Runtime()-time, "\n" );
  834.  
  835.     # add the normalizer
  836.     InfoAgCo2( "#I  Complements: adding normalizers\n" );
  837.     for i  in [ 1 .. Length(C) ]  do
  838.         C[i].complement.normalizer := SumAgGroup( C[i].complement,
  839.                                                   C[i].centralizer );
  840.     od;
  841.     return C;
  842.  
  843. end;
  844.  
  845.  
  846. #############################################################################
  847. ##
  848. #F  ComplementsCO2( <G>, <N>, <all>, <fun> )  . . . . . . . . . . . . . local
  849. ##
  850. ##  Prepare arguments for 'ComplementCO'.
  851. ##
  852. ComplementsCO2 := function( G, N, all, fun )
  853.     local   E,  L,  cor,  a,  i,  l;
  854.  
  855.     # if <G>  is  not  a parent or  <N>  not  part  of  the  ag series
  856.     # construct   a   new  group  with   this   properties   and   use
  857.     # 'ComplementCO2' again.
  858.     if    not IsParent( G )
  859.        or not IsElementaryAbelianAgSeries( G )
  860.        or not IsElementAgSeries( N )
  861.     then
  862.         a := IsomorphismAgGroup( [ G, N, TrivialSubgroup(G) ] );
  863.         G := Image( a, G );
  864.         N := Image( a, N );
  865.         return List( ComplementsCO2( G, N, all, fun ), x -> rec(
  866.                 complement  := PreImage( a, x.complement ),
  867.                 centralizer := PreImage( a, x.centralizer ) ) );
  868.     fi;
  869.  
  870.     # Get the elementary abelian series through <N>.
  871.     E := ElementaryAbelianSeries( G );
  872.     if not N in E  then
  873.         L := [];
  874.         i := 1;
  875.         l := Length( E );
  876.         while i <= l and IsSubgroup( E[ i ], N )  do
  877.             Add( L, E[ i ] );
  878.             i := i + 1;
  879.         od;
  880.         Add( L, N );
  881.         Append( L, Sublist( E, [ i .. l ] ) );
  882.         E := L;
  883.     fi;
  884.  
  885.     # if <G> and <N> are coprime <G> splits over <N>
  886.     if IntersectionSet( FactorsAgGroup(N), FactorsAgGroup(G,N) ) = []  then
  887.         InfoAgCo2( "#I  Complements: coprime case, <G> splits\n" );
  888.         cor := rec();
  889.  
  890.     # otherwise we compute a hall system for <G>/<N>
  891.     else
  892.         InfoAgCo2( "#I  Complements: computing p prime sets\n" );
  893.         a   := NaturalHomomorphism( G, G / N );
  894.         cor := PPrimeSetsOC( Image( a ) );
  895.         cor.generators := List( cor.generators, x -> 
  896.                                 PreImagesRepresentative( a, x ) );
  897.         cor.useCentralSK := true;
  898.     fi;
  899.  
  900.     # we want our nice elementary abelian series
  901.     cor.elementaryAbelianSeries := E;
  902.  
  903.     # if a condition was given use it
  904.     if IsFunc(fun)  then cor.condition := fun;  fi;
  905.  
  906.     # 'ComplementsCO' will do most of the work
  907.     return ComplementsCO( cor, G, Position(E,N), all );
  908.  
  909. end;
  910.  
  911.  
  912. #############################################################################
  913. ##
  914. #F  Complementclasses( <G>, <N> ) . . . . . . . . . . . . find all complement
  915. ##
  916. AgGroupOps.Complementclasses := function( G, N )
  917.     local   C;
  918.  
  919.     # if <G> and <N> are equal the only complement is trivial
  920.     if G = N  then
  921.         C := [ TrivialSubgroup(G) ];
  922.  
  923.     # if <N> is trivial the only complement is <G>
  924.     elif N.generators = []  then
  925.         C := [ G ];
  926.  
  927.     # otherwise we have to work
  928.     else
  929.         C := List( ComplementsCO2(G, N, true, false), G -> G.complement );
  930.     fi;
  931.  
  932.     # return what we have found
  933.     return C;
  934.  
  935. end;
  936.  
  937. Complementclasses := function( G, N )
  938.     return G.operations.Complementclasses(G, N);
  939. end;
  940.  
  941.  
  942. #############################################################################
  943. ##
  944. #F  ComplementAgGroup( <G>, <N> ) . . . . . . . . . . . . find one complement
  945. ##
  946. AgGroupOps.Complement := function( G, N )
  947.     local   C;
  948.  
  949.     # if <G> and <N> are equal the only complement is trivial
  950.     if G = N  then
  951.         C := TrivialSubgroup(G);
  952.  
  953.     # if <N> is trivial the only complement is <G>
  954.     elif N.generators = []  then
  955.         C := G;
  956.  
  957.     # otherwise we have to work
  958.     else
  959.         C := ComplementsCO2( G, N, false, false );
  960.         if 0 < Length(C)  then
  961.             C := C[1].complement;
  962.         else
  963.             C := false;
  964.         fi;
  965.     fi;
  966.  
  967.     # return what we have found
  968.     return C;
  969.  
  970. end;
  971.  
  972. Complement := function( G, N )
  973.     return G.operations.Complement( G, N );
  974. end;
  975.  
  976.  
  977. #N  The  following worked in  GAP 2.4  but needs to be implemented in GAP 3.1
  978.  
  979.  
  980. #############################################################################
  981. ##
  982. #F  NormalSubgroup1CO( <S>, <K>, <M> )
  983. ##
  984. ##  Let C = C_K( M ), then the subgroup C^P[C,C] lies in every
  985. ##  complement.
  986. ##
  987. #X
  988. #XNormalSubgroup1CO := function( S, K, M )
  989. #X
  990. #X    local C, CK, cCK,
  991. #X          p,
  992. #X          i, j,
  993. #X          gens;
  994. #X
  995. #X    ## At first get the centralizer in the whole group. This is a normal
  996. #X    ## subgroup. So C_K(M) is the normal intersection.
  997. #X    C  := CentralizerAgGroup( M );
  998. #X    CK := NormalIntersectionAgGroup( C, K );
  999. #X
  1000. #X    ## Now add the p-power of the generators to the commutator subgroup.
  1001. #X    p    := IndexAgWord( GeneratorsAgGroup( M )[ 1 ] );
  1002. #X    cCK  := GeneratorsAgGroup( CK );
  1003. #X    gens := [];
  1004. #X    for i  from 1  to length( cCK ) - 1  do
  1005. #X        for j  from i + 1  to length( cCK )  do
  1006. #X            Add( gens, Comm( cCK[i], cCK[j] ) );
  1007. #X        od;
  1008. #X        Add( gens, cCK[ i ] ^ p );
  1009. #X    od;
  1010. #X
  1011. #X    #3 return( Cgs( K, Set( gens ) ) );
  1012. #X    return( Cgs( K, cras( gens ) ) );
  1013. #X
  1014. #Xend;
  1015.  
  1016.  
  1017. #############################################################################
  1018. ##
  1019.  
  1020. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1021. ##
  1022. ## Local Variables:
  1023. ## mode:           outline
  1024. ## outline-regexp: "#F\\|#V\\|#E\\|#N"
  1025. ## eval:           (hide-body)
  1026. ## End:
  1027. ##
  1028.