home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / aghomomo.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  33.6 KB  |  1,097 lines
  1. #############################################################################
  2. ##
  3. #A  aghomomo.g                  GAP library                      Frank Celler
  4. ##
  5. #A  @(#)$Id: aghomomo.g,v 3.30 1992/08/11 14:25:51 fceller Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains functions for homomorphisms of aggroups.
  10. ##
  11. #H  $Log: aghomomo.g,v $
  12. #H  Revision 3.30  1992/08/11  14:25:51  fceller
  13. #H  'Subgroup' is broken for mat groups, so do not use it
  14. #H  in 'GroupHomomorphismByImages'
  15. #H
  16. #H  Revision 3.29  1992/06/02  12:08:26  beick
  17. #H  added a missing argument in 'AGHBIO.ImagesSet'
  18. #H
  19. #H  Revision 3.28  1992/05/27  10:15:24  fceller
  20. #H  added missing 'Reversed' in 'HomomorphicIgs'
  21. #H
  22. #H  Revision 3.27  1992/04/07  12:53:37  fceller
  23. #H  changed comparison with '0'
  24. #H
  25. #H  Revision 3.26  1992/03/30  07:47:09  fceller
  26. #H  changed 'Exponents' slightly.
  27. #H
  28. #H  Revision 3.25  1992/03/27  15:19:38  fceller
  29. #H  fixed a bug in 'CompositionFactorGroup'
  30. #H
  31. #H  Revision 3.24  1992/03/27  11:14:51  martin
  32. #H  changed mapping to general mapping and function to mapping
  33. #H
  34. #H  Revision 3.23  1992/03/17  12:31:20  jmnich
  35. #H  fixed bug in CompositionMapping
  36. #H
  37. #H  Revision 3.22  1992/03/01  10:56:21  fceller
  38. #H  Fixed a bug in 'AbstractIgs'.
  39. #H
  40. #H  Revision 3.21  1992/02/21  16:50:57  hbesche
  41. #H  renamed 'Word' to 'AbstractGenerator'
  42. #H
  43. #H  Revision 3.20  1992/02/21  14:02:02  fceller
  44. #H  'Subgroup' must be called with a parent group.
  45. #H
  46. #H  Revision 3.19  1992/02/07  18:11:40  fceller
  47. #H  Initial GAP 3.1 release.
  48. #H
  49. #H  Revision 3.1  1991/06/16  12:29:36  fceller
  50. #H  Initial revision under RCS.
  51. ##
  52.  
  53.  
  54. #############################################################################
  55. ##
  56. #F  InfoAgGroup1( <arg> ) . . . . . . . . . . . . . . . . package information
  57. #F  InfoAgGroup2( <arg> ) . . . . . . . . . . . . . package debug information
  58. ##
  59. if not IsBound( InfoAgGroup1 )  then InfoAgGroup1 := Ignore;  fi;
  60. if not IsBound( InfoAgGroup2 )  then InfoAgGroup2 := Ignore;  fi;
  61.  
  62.  
  63. #############################################################################
  64. ##
  65.  
  66. #F  AbstractIgs( <U>, <gens>, <words> ) . . . . . . . . . . .  igs with words
  67. ##
  68. ##  Generate the generators of <U> with <gens> takeing <words> along the way.
  69. ##
  70. AbstractIgs := function( U, gens, words )
  71.  
  72.     local   G, len, p,              # Supergroup, composotion length, primes
  73.             igs, new,
  74.             pag,
  75.             needed, found,          # generators needed / found
  76.             idWord, id,             # identities of <U> and <words>
  77.             isLess,
  78.             dmap, chain,            # subgroup depth map, depth chain
  79.             k, i, j,
  80.             u, uw, ua,
  81.             n,
  82.             e1, e2, e3,
  83.             x, z;
  84.  
  85.     # Typecheck arguments.
  86.     if Length( gens ) <> Length( words )  then
  87.         Error(Length(words), "<words> given, ", Length(gens), " needed\n");
  88.     fi;
  89.  
  90.     igs := Igs( U );
  91.     if igs = []  then
  92.         return rec( igs := [], abstractIgs := [] );
  93.     fi;
  94.  
  95.     G   := Parent( U );
  96.     len := Length( G.cgs );
  97.     p   := List( G.cgs, RelativeOrderAgWord );
  98.     id  := G.identity;
  99.  
  100.     # Make  a  list  which will hold the induced generating system. Enter the
  101.     # generators  of <igs> in a list <new> such that the are sorted according
  102.     # to their depths with the highest depth first.
  103.     needed := Length( igs );
  104.     new    := List( [ 1 .. Length( gens ) ], x -> [ gens[x], words[x] ] );
  105.     idWord := words[1] ^ 0;
  106.     isLess := function( x, y )
  107.         return DepthAgWord( x[ 1 ] ) > DepthAgWord( y[ 1 ] );
  108.     end;
  109.     Sort( new, isLess );
  110.  
  111.     # Make a list of subgroup depths in order to detect a chain.
  112.     dmap := [];
  113.     for i  in [ 1 .. needed ]  do
  114.         dmap[ DepthAgWord( igs[ i ] ) ] := i;
  115.     od;
  116.     chain := needed + 1;
  117.  
  118.     # Add  new  generators  until  we  reach the needed number of generators.
  119.     # They  new  generators  are obtained by powers and conjugated of the old
  120.     # ones.
  121.     pag   := List( [ 1 .. len ], x -> [ id, idWord ] );
  122.     k     := 1;
  123.     found := 0;
  124.     while k <= Length( new ) and needed <> found  do
  125.         u  := new[ k ][ 1 ];
  126.         uw := DepthAgWord( u );
  127.         ua := new[ k ][ 2 ];
  128.  
  129.         # Shift  the  elements  through the <pag> until we reach the identity
  130.         # or cannot shift anymore.
  131.         while u <> id and dmap[ uw ] < chain and pag[ uw ][ 1 ] <> id  do
  132.             x  := LeadingExponentAgWord( u )
  133.                    /  LeadingExponentAgWord( pag[ uw ][ 1 ] )
  134.                   mod p[ uw ];
  135.             u  := LeftQuotient( pag[ uw ][ 1 ] ^ x, u );
  136.             ua := LeftQuotient( pag[ uw ][ 2 ] ^ x, ua );
  137.             uw := DepthAgWord( u );
  138.         od;
  139.  
  140.         # Remove this element as we want to sort <new> at the end.
  141.         new[ k ] := [ id, idWord ];
  142.         if u <> id and dmap[ uw ] < chain  then
  143.  
  144.             # Can we update <chain> ?
  145.             if dmap[ uw ] = chain - 1  then
  146.                 chain := chain - 1;
  147.                 while chain > 1 and pag[DepthAgWord(igs[chain-1])][1]<>id  do
  148.                     chain := chain - 1;
  149.                 od;
  150.             fi;
  151.  
  152.             # The  element  is  not  in  the  <pag>.  Add  the  power and all
  153.             # conjugated to the new generators.
  154.             if dmap[ uw ] + 1 < chain  then
  155.                 z := u ^ RelativeOrderAgWord( u );
  156.                 if z <> id  then
  157.                     Add( new, [ z, ua ^ RelativeOrderAgWord( u ) ] );
  158.                 fi;
  159.             fi;
  160.             for x  in pag  do
  161.                 if x[ 1 ] <> id  then
  162.                    if dmap[Minimum(uw,DepthAgWord(x[1]))] + 1 < chain  then
  163.                        z := u ^ x[ 1 ];
  164.                        if z <> u  then
  165.                            Add( new, [ z, ua ^ x[ 2 ] ] );
  166.                        fi;
  167.                    fi;
  168.                 fi;
  169.             od;
  170.             pag[ uw ] := [ u, ua ];
  171.             found := found + 1;
  172.         InfoAgGroup2( "#I  AbstractIgs:", found," found, ",
  173.               needed, " needed\n" );
  174.         fi;
  175.         k := k + 1;
  176.     od;
  177.  
  178.     # We must now adjust the generators ( if we found enough ).
  179.     if needed <> found  then
  180.         Error( "elements <gens> do not generate group <U>" );
  181.     fi;
  182.     for i  in [ 1 .. Length( igs ) ]  do
  183.         u  := igs[ i ];
  184.         uw := DepthAgWord( u );
  185.         e1 := LeadingExponentAgWord( u );
  186.         e2 := LeadingExponentAgWord( pag[ uw ][ 1 ] );
  187.         if e1 <> e2  then
  188.             x := e1 / e2 mod p[ uw ];
  189.             pag[ uw ][ 1 ] := pag[ uw ][ 1 ] ^ x;
  190.             pag[ uw ][ 2 ] := pag[ uw ][ 2 ] ^ x;
  191.         fi;
  192.         if u <> pag[ uw ]  then
  193.             for j  in [ uw + 1 .. len ]  do
  194.                 e1 := ExponentAgWord( u, j );
  195.                 e2 := ExponentAgWord( pag[ uw ][ 1 ], j );
  196.                 if e1 <> e2  then
  197.                     e3 := LeadingExponentAgWord( pag[ j ][ 1 ] );
  198.                     x  := ( e1-e2 ) / e3 mod p[ j ];
  199.                     pag[ uw ][ 1 ] := pag[ uw ][ 1 ] * pag[ j ][ 1 ] ^ x;
  200.                     pag[ uw ][ 2 ] := pag[ uw ][ 2 ] * pag[ j ][ 2 ] ^ x;
  201.                 fi;
  202.             od;
  203.         fi;
  204.     od;
  205.  
  206.     # Now we can return.
  207.     pag := Filtered( pag, x -> x[ 1 ] <> id );
  208.     return rec( igs := List( pag, x -> x[ 1 ] ),
  209.                 abstractIgs := List( pag, x -> x[ 2 ] ) );
  210.  
  211. end;
  212.  
  213.  
  214. #############################################################################
  215. ##
  216. #F  HomomorphicIgs( <imgs> )  . . . . . . . . . .  Igs of a homomorphic image
  217. ##
  218. ##  It  is important that  <imgs>  are the images of  in  induced  generating
  219. ##  system  in their natural order, ie.  they must not be sorted according to
  220. ##  their  depths in the new group,  they must be  sorted according to  their
  221. ##  depths in the old group.
  222. ##
  223. HomomorphicIgs := function( arg )
  224.   
  225.     local   imgs,   # images
  226.              h,        # conjugating element / homomorphism
  227.              pag,    # induced generating system
  228.             g,      # one element of <imgs>
  229.               dg,     # depth of <g>
  230.             id;     # identity
  231.   
  232.     imgs := arg[1];
  233.     if imgs = []  then
  234.     return imgs;
  235.     fi;
  236.     id := imgs[1] ^ 0;
  237.   
  238.     if Length( arg ) = 1  then
  239.         pag := [];
  240.          for g  in Reversed( imgs )  do
  241.               dg := DepthAgWord( g );
  242.             while g <> id and IsBound( pag[ dg ] )  do
  243.               g := ReducedAgWord( g, pag[ dg ] );
  244.                  dg := DepthAgWord( g );
  245.             od;
  246.             if g <> id  then
  247.                pag[ dg ] := g;
  248.             fi;
  249.          od;
  250.     else
  251.          h := arg[2];
  252.         pag := [];
  253.          for g  in Reversed( imgs )  do
  254.              g  := g ^ h;
  255.              dg := DepthAgWord( g );
  256.              while g <> id and IsBound( pag[ dg ] )  do
  257.                  g := ReducedAgWord( g, pag[ dg ] );
  258.                  dg := DepthAgWord( g );
  259.              od;
  260.              if g <> id  then
  261.                  pag[ dg ] := g;
  262.              fi;
  263.         od;
  264.     fi;
  265.  
  266.     # Filter unbound entries from <pag>.
  267.     imgs :=[];
  268.     for g  in pag  do
  269.         Add( imgs, g );
  270.     od;
  271.     return imgs;
  272.   
  273. end;
  274.  
  275. #############################################################################
  276. ##
  277. #F  AgGroupOps.Factorization( <G>, <g> )  . . . . factorization of <g> in <G>
  278. ##
  279. AgGroupOps.Factorization := function( G, g )
  280.     local   v, w, i;
  281.  
  282.     if not IsBound( G.factorInfo )  then
  283.         G.factorInfo := Normalized( G );
  284.         if not IsBound( G.abstractGenerators )  then
  285.             G.abstractGenerators := List( [ 1 .. Length( G.generators ) ],
  286.                                     x -> AbstractGenerator( String( x ) ) );
  287.         fi;
  288.         G.factorInfo.abstractCgs := AbstractIgs( G.factorInfo, G.generators,
  289.                                       G.abstractGenerators ).abstractIgs;
  290.     fi;
  291.  
  292.     v := G.operations.Exponents( G.factorInfo, g, Integers );
  293.     w := IdWord;
  294.     for i  in [ 1 .. Length(v) ]  do
  295.         if v[i] <> 0  then
  296.             w := w * G.factorInfo.abstractCgs[i] ^ v[i];
  297.         fi;
  298.     od;
  299.  
  300.     return w;
  301.  
  302. end;
  303.  
  304.  
  305. #############################################################################
  306. ##
  307.  
  308. #F  KernelHomomorphismAgGroupPermGroup( <a> ) . . . .  kernel of homomorphism
  309. ##
  310. ##
  311. ##  'KernelHomomorphismAgGroupPermGroup'   determines   the   kernel   of   a
  312. ##  homomorphism mapping a   soluble  Group given   by  pc-presentation to  a
  313. ##  permutation   group. The  homomorphism  must    be   given by  a   normal
  314. ##  homomorphism record to which the entries 'image' and 'kernel' are added.
  315. ##
  316. KernelHomomorphismAgGroupPermGroup := function( hom )
  317.     local ggens, m, sk, im, gexps, x, y, i, j, k, l;
  318.  
  319.     ggens   := Cgs( hom.source );
  320.     gexps   := List( ggens, RelativeOrderAgWord );
  321.     m       := Length( ggens );
  322.     sk      := List( [1..m], x -> hom.source.identity );
  323.     im      := [];
  324.     im[m+1] := TrivialSubgroup( hom.range );
  325.  
  326.     for j in Reversed( [1..m] ) do
  327.         if Image( hom, ggens[j] ) in im[j+1]  then
  328.             y := ggens[j];
  329.             for k in [j+1..m] do
  330.                 if sk[k] = hom.source.identity then
  331.                     if gexps[k] <> gexps[j] then
  332.                         y := y ^ gexps[k];
  333.                     else
  334.                         l := 0;
  335.                         while l < gexps[k] do
  336.                             x := y * (ggens[k] ^ l);
  337.                             if Image( hom, x ) in im[k+1]  then
  338.                                 y := x;
  339.                                 l := gexps[k];
  340.                             else
  341.                                 l := l + 1;
  342.                             fi;
  343.                         od;
  344.                     fi;
  345.                 fi;
  346.             od;
  347.             sk[j] := y;
  348.             im[j] := im[j+1];
  349.         else
  350.             im[j] := Closure( im[j+1], Image( hom, ggens[j] ) );
  351.         fi;
  352.     od;
  353.     hom.kernel := Subgroup( Parent( hom.source ), sk );
  354.     hom.image  := im[1];
  355.     return hom.kernel;
  356.  
  357. end;
  358.  
  359.  
  360. #############################################################################
  361. ##
  362. #F  KernelHomomorphismAgGroupAgGroup( <a> ) . . . .  kernel of a homomorphism
  363. ##
  364. KernelHomomorphismAgGroupAgGroup := function( a )
  365.  
  366.     local   gensInv,
  367.             imgsInv,
  368.             gensKer,
  369.             u, v,
  370.             uw, vw,
  371.             gens, imgs,
  372.             idR, idD,
  373.             tmp,
  374.             i, j;
  375.  
  376.     idR := a.range.identity;
  377.     idD := a.source.identity;
  378.  
  379.     # Compute kernel and image, this is a Zassenhaus-algorithm.
  380.     gensInv := [];
  381.     imgsInv := [];
  382.     gensKer := [];
  383.     gens := a.generators;
  384.     imgs := a.genimages;
  385.     for i  in Reversed( [ 1 .. Length( imgs ) ] )  do
  386.         u  := imgs[ i ];
  387.         v  := gens[ i ];
  388.         uw := DepthAgWord( u );
  389.         while u <> idR and IsBound( gensInv[ uw ] )  do
  390.             tmp := LeadingExponentAgWord( u )
  391.                     /  LeadingExponentAgWord( gensInv[ uw ] )
  392.                    mod RelativeOrderAgWord( u );
  393.             u := gensInv[ uw ] ^ -tmp * u;
  394.             v := imgsInv[ uw ] ^ -tmp * v;
  395.             uw := DepthAgWord( u );
  396.         od;
  397.         if u = idR  then
  398.             vw := DepthAgWord( v );
  399.             while v <> idD and IsBound( gensKer[ vw ] )  do
  400.                 v  := ReducedAgWord( v, gensKer[ vw ] );
  401.                 vw := DepthAgWord( v );
  402.             od;
  403.             if v <> idD  then
  404.                 gensKer[ vw ] := v;
  405.             fi;
  406.         else
  407.             gensInv[ uw ] := u;
  408.             imgsInv[ uw ] := v;
  409.         fi;
  410.     od;
  411.  
  412.     # Now  we  have  image  and  kernel.  Add them to the <a>.
  413.     gensInv := Filtered( gensInv, IsBound );
  414.     gensKer := Filtered( gensKer, IsBound );
  415.     imgsInv := Filtered( imgsInv, IsBound );
  416.     for i  in [ 1 .. Length( gensInv ) ]  do
  417.         tmp :=  1 / LeadingExponentAgWord( gensInv[ i ] )
  418.                 mod RelativeOrderAgWord( gensInv[ i ] );
  419.         gensInv[ i ] := gensInv[ i ] ^ tmp;
  420.         imgsInv[ i ] := imgsInv[ i ] ^ tmp;
  421.     od;
  422.     for i  in [ 1 .. Length( gensInv ) - 1 ]  do
  423.         for j  in [ i + 1 .. Length( gensInv ) ]  do
  424.             uw := DepthAgWord( gensInv[ j ] );
  425.             tmp := ExponentAgWord( gensInv[ i ], uw );
  426.             if tmp <> 0  then
  427.                 gensInv[i] := gensInv[i] / gensInv[j] ^ tmp;
  428.                 imgsInv[i] := imgsInv[i] / imgsInv[j] ^ tmp;
  429.             fi;
  430.         od;
  431.     od;
  432.     a.image   := AgSubgroup( a.range, gensInv, false );
  433.     a.kernel  := AgSubgroup( a.source, gensKer, false );
  434.     a.gensInv := gensInv;
  435.     a.imgsInv := imgsInv;
  436.  
  437.     # is <a>.range = <a>.image
  438.     if a.range = a.image  then
  439.         a.image := a.range;
  440.     fi;
  441.  
  442.     # Return.
  443.     return a.kernel;
  444.  
  445. end;
  446.  
  447.  
  448. #############################################################################
  449. ##
  450.  
  451. #V  AgGroupHomomorphismOps  . . . . . . . . . . . . . . ag group homomorphism
  452. ##
  453. AgGroupHomomorphismOps := ShallowCopy( GroupHomomorphismOps );
  454.  
  455.  
  456. #############################################################################
  457. ##
  458.  
  459. #V  AgGroupHomomorphismByImagesOps  . . . . . . . . .  ag group hom by images
  460. ##
  461. AgGroupHomomorphismByImagesOps := Copy( GroupHomomorphismByImagesOps );
  462.  
  463.  
  464. #############################################################################
  465. ##
  466. #F  AgGroupHomomorphismByImagesOps.CoKernel( <fun> )  . . . . . . . co-kernel
  467. ##
  468. AgGroupHomomorphismByImagesOps.CoKernel := function ( hom )
  469.     local   C,          # co kernel of <hom>, result
  470.             gen,        # one generator of <C>
  471.             e,          # element of <hom>.source
  472.             k;          # loop variable
  473.  
  474.     # start with the trivial co kernel
  475.     C := TrivialSubgroup( Parent( hom.range ) );
  476.  
  477.     # check if <fun> is a function
  478.     if not IsMapping( hom )  then
  479.  
  480.         # for each element of the source and each generator of the source
  481.         for e  in Elements( hom.source )  do
  482.             for k  in [ 1 .. Length( hom.generators ) ]  do
  483.  
  484.                 # the co kernel must contain the corresponding Schreier gen
  485.                 gen := Image( hom, e ) * hom.genimages[k]
  486.                        / Image( hom, e * hom.generators[k] );
  487.                 C := Closure( C, gen );
  488.  
  489.             od;
  490.         od;
  491.     fi;
  492.  
  493.     # return the co kernel
  494.     return C;
  495. end;
  496.  
  497.  
  498. #############################################################################
  499. ##
  500. #F  AgGroupHomomorphismByImagesOps.IsMapping( <a> ) . . . .  is it a function
  501. ##
  502. AgGroupHomomorphismByImagesOps.IsMapping := function( a )
  503.  
  504.     local   gens,   # generators
  505.             imgs,   # images of generators
  506.             map,    # mapping
  507.             i, j;   # loops
  508.  
  509.     # We must check if the <imgs> fulfill the presenation of the domain.
  510.     gens := a.generators;
  511.     imgs := a.genimages;
  512.     map  := a.operations.ImageElm;
  513.  
  514.     # The power-part of the presenation.
  515.     for i  in [ 1 .. Length( gens ) ]  do
  516.         if imgs[ i ] ^ RelativeOrderAgWord( gens[ i ] )
  517.        <>
  518.        map( a, gens[ i ] ^ RelativeOrderAgWord( gens[ i ] ) )
  519.         then
  520.             return false;
  521.         fi;
  522.     od;
  523.  
  524.     # The commutator-part of the presenation.
  525.     for i  in [ 1 .. Length( gens ) ]  do
  526.         for j  in [ i + 1 .. Length( gens ) ]  do
  527.             if Comm( imgs[ j ], imgs[ i ] )
  528.            <>
  529.                map( a, Comm( gens[ j ], gens[ i ] ) )
  530.             then
  531.                 return false;
  532.             fi;
  533.         od;
  534.     od;
  535.  
  536.     # So the funtion <img> fulfill the relations, it a homomorphism.
  537.     return true;
  538.  
  539. end;
  540.  
  541.  
  542. #############################################################################
  543. ##
  544. #F  AgGroupHomomorphismByImagesOps.IsGroupHomomorphism( <map> ) . is function
  545. ##
  546. AgGroupHomomorphismByImagesOps.IsGroupHomomorphism := function ( hom )
  547.     return IsMapping( hom );
  548. end;
  549.  
  550.  
  551. #############################################################################
  552. ##
  553. #F  AgGroupHomomorphismByImagesOps.ImageElm( <h>, <u> ) . . .  image of <elm>
  554. ##
  555. AgGroupHomomorphismByImagesOps.ImageElm := function ( h, u )
  556.     local exv, img, j;
  557.  
  558.     img := h.range.identity;
  559.     exv := h.source.operations.Exponents( h.source, u, Integers );
  560.     for j  in [ 1 .. Length(exv) ]  do
  561.         if exv[j] <> 0  then
  562.             img := img * h.genimages[j] ^ exv[j];
  563.         fi;
  564.     od;
  565.     return img;
  566. end;
  567.  
  568.  
  569. #############################################################################
  570. ##
  571. #F  AgGroupHomomorphismByImagesOps.ImagesElm( <a>, <e> )  . . . . . .  images
  572. ##
  573. AgGroupHomomorphismByImagesOps.ImagesElm := function ( a, e )
  574.     if not IsBound( a.coKernel )  then
  575.         a.coKernel := a.operations.CoKernel( a );
  576.     fi;
  577.     return a.coKernel * Image( a, e );
  578. end;
  579.  
  580.  
  581. #############################################################################
  582. ##
  583. #F  AgGroupHomomorphismByImagesOps.ImagesRepresentative( <a>, <e> ) . . . rep
  584. ##
  585. AgGroupHomomorphismByImagesOps.ImagesRepresentative := function ( a, e )
  586.     return a.operations.ImageElem( a, e );
  587. end;
  588.  
  589.  
  590. #############################################################################
  591. ##
  592. #F  AgGroupHomomorphismByImagesOps.ImagesSet( <a>, <D> )  . . .  image of <D>
  593. ##
  594. AgGroupHomomorphismByImagesOps.ImagesSet := function( a, D )
  595.     local   imgs;
  596.  
  597.     if not IsHomomorphism( a ) or not IsGroup( D )  then
  598.         imgs := MappingOps.ImagesSet( a, D );
  599.     elif IsAgGroup( a.range )  then
  600.         imgs := AgSubgroup( a.range, HomomorphicIgs( List( Igs( D ), x ->
  601.                             a.operations.ImageElm( a, x ) ) ), false );
  602.     else
  603.         imgs := List( D.generators, x -> a.operations.ImageElm( a, x ) );
  604.         if Set( imgs ) = Set( a.range.generators )  then
  605.             imgs := a.range;
  606.         else
  607.             imgs := Subgroup( Parent( a.range ), imgs );
  608.         fi;
  609.     fi;
  610.     return imgs;
  611.  
  612. end;
  613.  
  614.  
  615. #############################################################################
  616. ##
  617. #F  AgGroupHomomorphismByImagesOps.KernelGroupHomomorphism( <a> ) . .  kernel
  618. ##
  619. AgGroupHomomorphismByImagesOps.KernelGroupHomomorphism := function ( a )
  620.     local   krn;        # kernel of <a>, result
  621.  
  622.     if not IsMapping( a )  then
  623.         krn := GroupHomomorphismByImagesOps.KernelGroupHomomorphism( a );
  624.     elif IsAgGroup( a.range )  then
  625.         krn := KernelHomomorphismAgGroupAgGroup( a );
  626.     elif IsPermGroup( a.range )  then
  627.         krn := KernelHomomorphismAgGroupPermGroup( a );
  628.     else
  629.         krn := GroupHomomorphismOps.KernelGroupHomomorphism( a );
  630.     fi;
  631.     return krn;
  632. end;
  633.  
  634.  
  635. #############################################################################
  636. ##
  637. #F  AgGroupHomomorphismByImagesOps.CompositionMapping( <a>, <b> ) . . .  comp
  638. ##
  639. AgGroupHomomorphismByImagesOps.CompositionMapping := function ( a, b )
  640.     local   prd,  gens,  imgs;
  641.  
  642.     if IsHomomorphism( a ) and IsHomomorphism( b )  then
  643.         gens := b.source.generators;
  644.         imgs := List( gens, x -> Image( a, Image( b, x ) ) );
  645.         prd  := GroupHomomorphismByImages( b.source, a.range, gens, imgs );
  646.      prd.isMapping      := true;
  647.         prd.isHomomorphism := true;
  648.         prd.preimage       := b.source;
  649.     else
  650.         prd := MappingOps.CompositionMapping( a, b );
  651.     fi;
  652.     return prd;
  653. end;
  654.  
  655.  
  656. #############################################################################
  657. ##
  658. #F  AgGroupHomomorphismByImagesOps.PowerMapping( <map>, <n> ) . . . . . power
  659. ##
  660. AgGroupHomomorphismByImagesOps.PowerMapping := function ( map, n )
  661.     local   pow,  id,  i;
  662.  
  663.     # catch trivial case
  664.     if n = 0  then
  665.         pow := GroupHomomorphismByImages( map.source, map.range,
  666.                       map.source.generators,
  667.                       map.source.generators );
  668.  
  669.     # compute the power using repeated squaring
  670.     else
  671.         pow := IdentityMapping( map.source );
  672.         id  := pow;
  673.         i := 2 ^ (LogInt( n, 2 ) + 1);
  674.         while 1 < i  do
  675.             if pow <> id  then
  676.                 pow := pow.operations.CompositionMapping( pow, pow );
  677.         fi;
  678.             i := QuoInt( i, 2 );
  679.             if i <= n  then
  680.                 if pow <> id  then
  681.                     pow := map.operations.CompositionMapping( pow, map );
  682.                 else
  683.                     pow := map;
  684.                 fi;
  685.                 n := n - i;
  686.             fi;
  687.         od;
  688.     fi;
  689.  
  690.     # return the power
  691.     return pow;
  692. end;
  693.  
  694.  
  695. #############################################################################
  696. ##
  697. #F  AgGroupHomomorphismByImagesOps.InverseMapping( <a> )  . . . . . . inverse
  698. ##
  699. AgGroupHomomorphismByImagesOps.InverseMapping := function( a )
  700.     local   inv;
  701.  
  702.     if    not IsMapping( a )
  703.        or not IsBijection( a ) 
  704.        or not IsAgGroup( a.range )  
  705.     then
  706.         return GroupHomomorphismByImagesOps.InverseMapping( a );
  707.     else
  708.         if not IsBound( a.gensInv )  then
  709.         AgGroupHomomorphismByImagesOps.KernelGroupHomomorphism( a );
  710.         fi;
  711.     inv := GroupHomomorphismByImages( a.range,   a.source,
  712.                       a.gensInv, a.imgsInv );
  713.     inv.kernelGroupHomomorphism := TrivialSubgroup( a.range );
  714.     inv.inverseMapping          := a;
  715.         inv.image                   := a.source;
  716.     inv.isMapping               := true;
  717.     inv.isBijection             := true;
  718.     return inv;
  719.     fi;
  720.  
  721. end;
  722.  
  723.  
  724. #############################################################################
  725. ##
  726. #F  AgGroupHomomorphismByImagesOps.PreImagesSet( <a>, <D> ) . . . .  preimage
  727. ##
  728. AgGroupHomomorphismByImagesOps.PreImagesSet := function( a, D )
  729.  
  730.     if IsAgGroup( D ) and IsSubset( a.range, D )  then
  731.     return MergedIgs( a.source, Kernel( a ), List( Igs( D ), 
  732.             x -> a.operations.PreImagesRepresentative( a,x ) ), false );
  733.     else
  734.         return GroupHomomorphismByImagesOps.PreImagesSet( a, D );
  735.     fi;
  736. end;
  737.  
  738.  
  739. #############################################################################
  740. ##
  741. #F  AgGroupHomomorphismByImagesOps.PreImagesRepresentative( <a>, <e> )     .  pi
  742. ##
  743. AgGroupHomomorphismByImagesOps.PreImagesRepresentative := function( a, e )
  744.     local   pre,  exv,  i;
  745.  
  746.     if not IsAgGroup( a.range )  then
  747.     pre := GroupHomomorphismByImagesOps.PreImagesRepresentative( a, e );
  748.  
  749.     else
  750.  
  751.         # Use 'Kernel' in order to bind 'imgsInv'
  752.     if not IsBound( a.gensInv )  then
  753.         AgGroupHomomorphismByImagesOps.KernelGroupHomomorphism( a );
  754.     fi;
  755.  
  756.     # Check that <e> lies in the image of <a>
  757.     if not e in a.image  then
  758.         Error( "<e> must have at least one preimage" );
  759.     fi;
  760.  
  761.     # Construct a preimage.
  762.         pre := a.source.identity;
  763.         exv := a.image.operations.Exponents( a.image, e, Integers );
  764.         for i  in [ 1 .. Length(exv) ]  do
  765.             if exv[i] <> 0  then
  766.                 pre := pre * a.imgsInv[i] ^ exv[i];
  767.             fi;
  768.         od;
  769.     fi;
  770.     return pre;
  771.  
  772. end;
  773.  
  774.  
  775. #############################################################################
  776. ##
  777. #F  AgGroupOps.GroupHomomorphismByImages( <U>, <R>, <g>, <i> ) . . create hom
  778. ##
  779. AgGroupOps.GroupHomomorphismByImages := function( D, R, gens, imgs )
  780.  
  781.     local   h,      # homomorphism
  782.             tmp;    # temporary
  783.  
  784.     # Normalize <gens> and unbind possible '<D>.field'.
  785.     D := Normalized( D );
  786.     Unbind( D.field );
  787.     if Cgs( D ) <> gens  then
  788.         tmp  := AbstractIgs( D, gens, imgs );
  789.         gens := tmp.igs;
  790.         imgs := tmp.abstractIgs;
  791.     fi;
  792.  
  793.     # If range <R> is just 'rec()', try to construct the image.
  794.     if not IsBound( R.generators )  then
  795.         if imgs = []  then
  796.             Error( "needs either range or at least one image" );
  797.         fi;
  798.         R := Group( imgs, imgs[1]^0 );
  799.     fi;
  800.  
  801.     # Construct the homorphism record.
  802.     h := rec( source           := D,
  803.               range            := R,
  804.               domain           := Mappings,
  805.               generators       := gens,
  806.               genimages        := imgs,
  807.               preimage         := D,
  808.               image            := R.operations.Subgroup( Parent(R), imgs ),
  809.               isGeneralMapping := true,
  810.               operations       := AgGroupHomomorphismByImagesOps );
  811.     return h;
  812.  
  813. end;
  814.  
  815.  
  816. #############################################################################
  817. ##
  818.  
  819. #F  CompositionHomomorphismOps    . . . . . . . . . .  natural homomorphism ops
  820. ##
  821. CompositionHomomorphismOps := Copy( AgGroupHomomorphismByImagesOps );
  822.  
  823.  
  824. #############################################################################
  825. ##
  826. #F  CompositionHomomorphismOps.ImageElm( <a>, <e> ) . . . . . .  image of <e>
  827. ##
  828. CompositionHomomorphismOps.ImageElm := function( a, e )
  829.     return FactorAgWord( e, a.range.identity );
  830. end;
  831.  
  832.  
  833. #############################################################################
  834. ##
  835. #F  CompositionHomomorphismOps.PreImagesRepresentative( <a>, <e> )  . . . rep
  836. ##
  837. CompositionHomomorphismOps.PreImagesRepresentative := function( a, e )
  838.     return FactorAgWord( e, a.source.identity );
  839. end;
  840.  
  841.  
  842. #############################################################################
  843. ##
  844. #F  CompositionHomomorphismOps.Print( <a> ) . . . . . . . . . . . . . . print
  845. ##
  846. CompositionHomomorphismOps.Print := function( a )
  847.     Print( "NaturalHomomorphism( ", a.source, ", ", a.image, " )" );
  848. end;
  849.  
  850.  
  851. #############################################################################
  852. ##
  853. #F  CompositionFactorGroup( <G>, <N> )    . . . . . . . . . . . . . . . . local
  854. ##
  855. CompositionFactorGroup := function( G, N )
  856.     local   a,  l,  H;
  857.  
  858.     # Check arguments.
  859.     if not Index( Parent(G), G ) = 1 or not IsElementAgSeries( N )  then
  860.         Error( "<G> must be a parent group and <N> a compositionsubgroup" );
  861.     fi;
  862.     InfoAgGroup2( "#I  FactorGroup: uses composition factor group\n" );
  863.  
  864.     # Get the depths where the words must be cut of.
  865.     l := DepthAgWord( Igs( N )[ 1 ] );
  866.  
  867.     # Construct factorgroup, this must be done by hand as in 'AgGroupFpGroup'
  868.     H := FactorAgGroup( G.generators[ 1 ], l - 1 );
  869.     H.isDomain   := true;
  870.     H.isGroup    := true;
  871.     H.isAgGroup  := true;
  872.     H.cgs        := H.generators;
  873.     H.operations := AgGroupOps;
  874.  
  875.     # Now construct the mapping. This is a homomorphism with kernel <N>.
  876.     a := GroupHomomorphismByImages( G, H, Cgs( G ), List( Cgs( G ),
  877.                     x -> FactorAgWord( x, H.identity ) ) );
  878.     a.isMapping  := true;
  879.     a.kernel     := N;
  880.     a.image      := H;
  881.     a.imgsInv    := FactorArg( Normalized( G ), N ).generators;
  882.     a.gensInv    := H.cgs;
  883.     a.operations := CompositionHomomorphismOps;
  884.  
  885.     # Bind result to <H>.naturalHomomorphism
  886.     H.naturalHomomorphism := a;
  887.  
  888.     # Return the factor group.
  889.     return H;
  890.  
  891. end;
  892.  
  893.  
  894. #############################################################################
  895. ##
  896. #F  AgGroupOps.FactorGroup( <G>, <N> )    . . . . . . . . . . .  <G> -> <G>/<N>
  897. ##
  898. AgGroupOps.FactorGroup := function( U, N )
  899.     local   F,  a;
  900.  
  901.     # Catch two trivial cases.
  902.     if U = N  then
  903.         InfoAgGroup2( "#I  FactorGroup: <U>/<N> is trivial\n" );
  904.         F := AgGroupFpGroup( rec( generators := [], relators := [] ) );
  905.         a := GroupHomomorphismByImages( U, F, Cgs(U),
  906.                     List( Cgs(U), x -> F.identity ) );
  907.     a.isMapping := true;
  908.         Kernel( a );
  909.     F.naturalHomomorphism := a;
  910.     return F;
  911.     fi;
  912.  
  913.     # Dispatch if possible.
  914.     if     Index( Parent( U ), U ) = 1
  915.        and IsNormalized( U )
  916.        and N.generators <> []
  917.        and IsElementAgSeries( N )
  918.     then
  919.         return CompositionFactorGroup( U, N );
  920.     else
  921.         F := AgGroupFpGroup( U.operations.FpGroup( 
  922.                  CollectorlessFactorGroup( U, N ), "g" ) );
  923.     a := GroupHomomorphismByImages(
  924.             U,
  925.             F,
  926.         Concatenation( FactorArg(U,N).generators, Igs(N) ),
  927.         Concatenation( F.cgs, List(Igs(N),x->F.identity) ) );
  928.         a.isMapping := true;
  929.         Kernel( a );
  930.         F.naturalHomomorphism := a;
  931.     return F;
  932.     fi;
  933.  
  934. end;
  935.  
  936.  
  937. #############################################################################
  938. ##
  939. #F  AgGroupOps.NaturalHomomorphism( <G>, <F> )    . . . . . .  nat homomorphism
  940. ##
  941. AgGroupOps.NaturalHomomorphism :=  function( G, F )
  942.     local   f;
  943.  
  944.     if G = F.factorNum  then
  945.         f := F.naturalHomomorphism;
  946.     else
  947.         f := GroupHomomorphismByImages( G, F, Cgs( G ), List( Cgs( G ),
  948.              x -> Image( F.naturalHomomorphism, x ) ) );
  949.         f.isMapping := true;
  950.     fi;
  951.     return f;
  952.  
  953. end;
  954.  
  955.  
  956. #############################################################################
  957. ##
  958.  
  959. #F  HomomorphismsSeries( <G>, <list> )    . . . . . . . . .  factor homs of <G>
  960. ##
  961. HomomorphismsSeries := function( G, list )
  962.     local   homs,  H,  N,  fac,  f,  fast,  i,  j;
  963.  
  964.     # Check the arguments.
  965.     if    not IsAgGroup( G )
  966.        or not IsList( list )
  967.        or Length( list ) < 2
  968.        or not IsAgGroup( list[ 1 ] )
  969.        or list[ Length( list ) ].generators <> []
  970.     then
  971.         Error( "usage: HomomorphismsSeries( <G>, <list> )" );
  972.     fi;
  973.  
  974.     # Dirty hack.
  975.     fast := IsParent( G ) and ForAll( list, IsElementAgSeries );
  976.  
  977.     # Construct the homs using 'NaturalHomomorphism'.
  978.     fac  := G / list[ 1 ];
  979.     homs := [ NaturalHomomorphism( G, fac ) ];
  980.     fac  := G / list[ Length( list ) - 1 ];
  981.     homs[ Length( list ) ] := NaturalHomomorphism( G, fac );
  982.     for i  in Reversed( [ 2 .. Length( list ) - 1 ] )  do
  983.         H := homs[ i + 1 ].range;
  984.         N := list[ i - 1 ];
  985.  
  986.     # Dirty hack!
  987.         if fast  then
  988.             N := homs[i+1].operations.ImagesSet( homs[ i + 1 ], N );
  989.         else
  990.             for j  in Reversed( [ i + 1 .. Length( list ) ] )  do
  991.                 N := homs[j].operations.ImagesSet( homs[ j ], N );
  992.             od;
  993.         fi;
  994.     fac := H / N;
  995.     homs[ i ] := NaturalHomomorphism( H, fac );
  996.     od;
  997.     if Length( homs ) > 1  then
  998.     f := GroupHomomorphismByImages(
  999.                        homs[2].range, homs[1].range,
  1000.                 homs[2].range.generators,
  1001.                homs[1].range.generators );
  1002.         homs[2] := GroupHomomorphismByImages(
  1003.                        homs[2].source, homs[1].range,
  1004.                        homs[2].source.generators,
  1005.                        List( homs[2].source.generators, x ->
  1006.                              Image( f, Image( homs[2], x ) ) ) );
  1007.     fi;
  1008.     return homs;
  1009.  
  1010. end;
  1011.  
  1012.  
  1013. #############################################################################
  1014. ##
  1015. #F  IsomorphismAgGroup( <list> )  . . . . . . . . . . . .  isomorphic AgGroup
  1016. ##
  1017. ##  'IsomorphismAgGroup' constructs  an   ag-group H from   a   given list of
  1018. ##  subgroups which  has  to be a  series  of some other ag-group   G, i.e. a
  1019. ##  series for the first group in  this list.  The constructed ag-group G has
  1020. ##  the property, that it is isomorphic to G and that under the corresponding
  1021. ##  isomorphism the given  list of ag-groups  will map onto a sublist  of the
  1022. ##  composition series of H.  This function may be used  to  redefine a known
  1023. ##  group  so that there   exists an  elementary  abelian  series through the
  1024. ##  group's composition  series. This is required  for  some algorithms.  The
  1025. ##  isomorphism G <-> H is returned by 'IsomorphismAgGroup'.
  1026. ##
  1027. ##  returns:    <aghom>
  1028. ##
  1029. IsomorphismAgGroup := function( series )
  1030.     local   fpword, gens, rels, aggens, group, comm, facs, facgens, faclen,
  1031.             len, steps, p, i, j;
  1032.  
  1033.     fpword := function ( elem )
  1034.         local list, word, i, j, k;
  1035.  
  1036.         k    := 1;
  1037.         word := IdWord;
  1038.         for i in [1..steps] do
  1039.             list := facs[i].operations.Exponents( facs[i], elem, Integers );
  1040.             for j in [ 1 .. faclen[i] ] do
  1041.                 if list[j] <> 0 then
  1042.                     elem := facgens[i][j] ^ list[j] * elem;
  1043.                     word := word * gens[k] ^ list[j];
  1044.                 fi;
  1045.                 k := k + 1;
  1046.             od;
  1047.         od;
  1048.         return word;
  1049.     end;
  1050.  
  1051.     facs    := [];
  1052.     facgens := [];
  1053.     faclen  := [];
  1054.     aggens  := [];
  1055.     steps   := Length( series ) - 1;
  1056.     for i in [1..steps] do
  1057.         Add( facs, series[i] mod series[i+1] );
  1058.         Add( facgens, ShallowCopy( facs[i].generators ) );
  1059.         Add( faclen, Length( facgens[i] ) );
  1060.         Append( aggens, facgens[i] );
  1061.         Apply( facgens[i], x -> x ^ -1 );
  1062.     od;
  1063.     len  := Length( aggens );
  1064.     gens := List( Sublist( InformationAgWord( series[1].identity ).names,
  1065.                            List( aggens, DepthAgWord ) ), AbstractGenerator );
  1066.     rels := [];
  1067.     for i in [1..len] do
  1068.         p := RelativeOrderAgWord( aggens[i] );
  1069.         Add( rels, gens[i] ^ p / fpword( aggens[i] ^ p ) );
  1070.     od;
  1071.     for i in [1..len-1] do
  1072.         for j in [i+1..len] do
  1073.             comm := fpword( Comm( aggens[j], aggens[i] ) );
  1074.             if comm <> IdWord then
  1075.                 Add( rels, Comm( gens[j], gens[i] ) / comm );
  1076.             fi;
  1077.         od;
  1078.     od;
  1079.     group := AgGroupFpGroup( rec( generators := gens, relators := rels ) );
  1080.     return GroupHomomorphismByImages( series[1], group, 
  1081.                       aggens, group.generators );
  1082.  
  1083. end;
  1084.  
  1085.  
  1086. #############################################################################
  1087. ##
  1088.  
  1089. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1090. ##
  1091. ## Local Variables:
  1092. ## mode:           outline
  1093. ## outline-regexp: "#F\\|#V\\|#E"
  1094. ## eval:           (hide-body)
  1095. ## End:
  1096. ##
  1097.