home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / permhomo.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  35.9 KB  |  1,092 lines
  1. #############################################################################
  2. ##
  3. #A  permhomo.g                  GAP library                  Martin Schoenert
  4. #A                                                                & Udo Polis
  5. ##
  6. #A  @(#)$Id: permhomo.g,v 3.10 1992/06/23 12:08:47 martin Rel $
  7. ##
  8. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  9. ##
  10. ##  This file contains functions that implement homomorphisms for permgroups.
  11. ##
  12. #H  $Log: permhomo.g,v $
  13. #H  Revision 3.10  1992/06/23  12:08:47  martin
  14. #H  fixed 'PGHBIO.CoKernel' to take the normal closure
  15. #H
  16. #H  Revision 3.9  1992/06/04  12:50:57  martin
  17. #H  changed 'GroupHomomorphismsByImages' to accept empty lists
  18. #H
  19. #H  Revision 3.8  1992/06/03  17:26:20  martin
  20. #H  improved 'GroupHomomorphismByImages'
  21. #H
  22. #H  Revision 3.7  1992/03/27  11:14:51  martin
  23. #H  changed mapping to general mapping and function to mapping
  24. #H
  25. #H  Revision 3.6  1992/02/20  19:31:34  martin
  26. #H  fixed a bug in 'BlocksHomOps.PreImagesSetStab', kernel may be trivial
  27. #H
  28. #H  Revision 3.5  1992/02/20  15:58:50  martin
  29. #H  added Udo to the list of authors
  30. #H
  31. #H  Revision 3.4  1992/02/19  19:39:21  martin
  32. #H  fixed 'TransConstHomOps.PreImagesSet', the generators of the preimage
  33. #H  must contain the generators of the kernel
  34. #H
  35. #H  Revision 3.3  1992/02/19  13:02:30  martin
  36. #H  added 'TransConstHomomorphism' and 'BlocksHomomorphism'
  37. #H
  38. #H  Revision 3.2  1992/02/10  15:14:35  martin
  39. #H  added the domain 'Mappings'
  40. #H
  41. #H  Revision 3.1  1992/01/20  15:54:47  martin
  42. #H  initial revision under RCS
  43. #H
  44. ##
  45.  
  46.  
  47. #############################################################################
  48. ##
  49. #F  PermGroupOps.GroupHomomormphismByImages(<G>,<H>,<gens>,<imgs>)  .  create
  50. #F      a permutation group homomorphism by the images of a generating system
  51. ##
  52. PermGroupOps.GroupHomomorphismByImages := function ( G, H, gens, imgs )
  53.     local   hom;        # homomorphism from <G> to <H>, result
  54.  
  55.     # make the homomorphism
  56.     hom := rec( );
  57.     hom.isGeneralMapping := true;
  58.     hom.domain          := Mappings;
  59.  
  60.     # enter the identifying information
  61.     hom.source          := G;
  62.     hom.range           := H;
  63.     hom.generators      := gens;
  64.     hom.genimages       := imgs;
  65.  
  66.     # enter usefull information (precious little)
  67.     if IsEqualSet( gens, G.generators )  then
  68.         hom.preimage    := G;
  69.     else
  70.         hom.preimage    := Parent(G).operations.Subgroup( Parent(G), gens );
  71.     fi;
  72.     if IsEqualSet( imgs, H.generators )  then
  73.         hom.image       := H;
  74.     else
  75.         hom.image       := Parent(H).operations.Subgroup( Parent(H), imgs );
  76.     fi;
  77.  
  78.     # enter the operations record
  79.     hom.operations      := PermGroupHomomorphismByImagesOps;
  80.  
  81.     # return the homomorphism
  82.     return hom;
  83. end;
  84.  
  85. PermGroupHomomorphismByImagesOps := Copy( GroupHomomorphismByImagesOps );
  86.  
  87. PermGroupHomomorphismByImagesOps.MakeMapping := function ( hom )
  88.     local   rnd,        # list of random elements of '<hom>.source'
  89.             rne,        # list of the images of the elements in <rnd>
  90.             rni,        # index of the next random element to consider
  91.             elm,        # one element in '<hom>.source'
  92.             img,        # its image
  93.             size,       # size of the stabilizer chain constructed so far
  94.             stb,        # stabilizer in '<hom>.source'
  95.             orb,        # orbit
  96.             len,        # length of the orbit before extension
  97.             bpt,        # base point
  98.             i,  j;      # loop variables
  99.  
  100.     # handle trivial case
  101.     if hom.generators = []  then
  102.         return;
  103.     fi;
  104.  
  105.     # start with the generators as random elements
  106.     rnd := ShallowCopy( hom.generators );
  107.     for i  in [Length(rnd)..16]  do
  108.         Add( rnd, hom.source.identity );
  109.     od;
  110.     rne := ShallowCopy( hom.genimages );
  111.     for i  in [Length(rne)..16]  do
  112.         Add( rne, hom.range.identity );
  113.     od;
  114.     rni := 1;
  115.  
  116.     # initialize the top level
  117.     bpt := 0;
  118.     for elm  in hom.generators  do
  119.         if elm <> elm^0
  120.           and (bpt = 0  or SmallestMovedPointPerm( elm ) < bpt)
  121.         then
  122.             bpt := SmallestMovedPointPerm( elm );
  123.         fi;
  124.     od;
  125.     if bpt = 0  then bpt := 1;  fi;
  126.     hom.orbit                   := [ bpt ];
  127.     hom.transversal             := [];
  128.     hom.transversal[ bpt ]      := hom.source.identity;
  129.     hom.transimages             := [];
  130.     hom.transimages[ bpt ]      := hom.range.identity;
  131.     hom.stabilizer              := rec();
  132.     hom.stabilizer.identity     := hom.source.identity;
  133.     hom.stabilizer.generators   := [];
  134.     hom.stabilizer.genimages    := [];
  135.  
  136.     # extend orbit and transversal
  137.     orb := hom.orbit;
  138.     i := 1;
  139.     while i <= Length(orb)  do
  140.         for j  in [1..Length(hom.generators)]  do
  141.             elm := hom.generators[j];
  142.             img := hom.genimages[j];
  143.             if not IsBound(hom.transversal[orb[i]/elm])  then
  144.                 hom.transversal[orb[i]/elm] := elm;
  145.                 hom.transimages[orb[i]/elm] := img;
  146.                 Add( orb, orb[i]/elm );
  147.             fi;
  148.         od;
  149.         i := i + 1;
  150.     od;
  151.  
  152.     # get the size of the stabilizer chain
  153.     size := Length( hom.orbit );
  154.  
  155.     # create new elements until we have reached the size
  156.     while size <> Size( hom.preimage )  do
  157.  
  158.         # make a new element from the generators
  159.         elm := rnd[rni];
  160.         img := rne[rni];
  161.         i := RandomList( [ 1 .. Length( hom.generators ) ] );
  162.         rnd[rni] := rnd[rni] * hom.generators[i];
  163.         rne[rni] := rne[rni] * hom.genimages[i];
  164.         rni := rni mod 16 + 1;
  165.  
  166.         # divide the element through the stabilizer chain
  167.         stb := hom;
  168.         while stb.generators <> []
  169.           and IsBound(stb.transversal[stb.orbit[1]^elm])  do
  170.             bpt := stb.orbit[1];
  171.             while bpt ^ elm <> bpt  do
  172.                 img := img * stb.transimages[bpt^elm];
  173.                 elm := elm * stb.transversal[bpt^elm];
  174.             od;
  175.             stb := stb.stabilizer;
  176.         od;
  177.  
  178.         # if the element was not in the stabilizer chain
  179.         if elm <> hom.source.identity  then
  180.  
  181.             # if this stabilizer is trivial add an initial orbit
  182.             if stb.generators = []  then
  183.                 bpt := SmallestMovedPointPerm( elm );
  184.                 stb.orbit                   := [ bpt ];
  185.                 stb.transversal             := [];
  186.                 stb.transversal[ bpt ]      := hom.source.identity;
  187.                 stb.transimages             := [];
  188.                 stb.transimages[ bpt ]      := hom.range.identity;
  189.                 stb.stabilizer              := rec();
  190.                 stb.stabilizer.identity     := hom.source.identity;
  191.                 stb.stabilizer.generators   := [];
  192.                 stb.stabilizer.genimages    := [];
  193.             fi;
  194.  
  195.             # divide the size of stabilizer chain by the old orbit length
  196.             size := size / Length( stb.orbit );
  197.  
  198.             # add the element to the generators
  199.             Add( stb.generators, elm );
  200.             Add( stb.genimages,  img );
  201.  
  202.             # extend orbit and transversal
  203.             orb := stb.orbit;
  204.             len := Length(orb);
  205.             i := 1;
  206.             while i <= len  do
  207.                 if not IsBound(stb.transversal[orb[i]/elm])  then
  208.                     stb.transversal[orb[i]/elm] := elm;
  209.                     stb.transimages[orb[i]/elm] := img;
  210.                     Add( orb, orb[i]/elm );
  211.                 fi;
  212.                 i := i + 1;
  213.             od;
  214.             while i <= Length(orb)  do
  215.                 for j  in [1..Length(stb.generators)]  do
  216.                     elm := stb.generators[j];
  217.                     img := stb.genimages[j];
  218.                     if not IsBound(stb.transversal[orb[i]/elm])  then
  219.                         stb.transversal[orb[i]/elm] := elm;
  220.                         stb.transimages[orb[i]/elm] := img;
  221.                         Add( orb, orb[i]/elm );
  222.                     fi;
  223.                 od;
  224.                 i := i + 1;
  225.             od;
  226.  
  227.             # multiply the size of stabilizer chain by the new orbit length
  228.             size := size * Length( stb.orbit );
  229.  
  230.         fi;
  231.  
  232.     od;
  233.  
  234. end;
  235.  
  236. PermGroupHomomorphismByImagesOps.CoKernel := function ( hom )
  237.     local   C,          # cokernel of <hom>, result
  238.             stb,        # stabilizer in the chain of <hom>
  239.             bpt,        # basepoint of stabilizer
  240.             elm,        # one schreier generator
  241.             img,        # image of <elm> under <hom>
  242.             i, k;       # loop variables
  243.  
  244.     # handle special case
  245.     if IsBound( hom.isMapping )  and hom.isMapping  then
  246.         return TrivialSubgroup( hom.range );
  247.     fi;
  248.  
  249.     # make sure we have a stabilizer chain for <hom>
  250.     if not IsBound( hom.stabilizer )  then
  251.         hom.operations.MakeMapping( hom );
  252.     fi;
  253.  
  254.     # loop over the stabilizer chain
  255.     C := TrivialSubgroup( hom.range );
  256.     while hom.generators <> []  do
  257.  
  258.         # for all orbit points
  259.         for i  in hom.orbit  do
  260.  
  261.             # and all generators
  262.             for k  in [ 1 .. Length(hom.generators) ]  do
  263.  
  264.                 # make the schreier generator and its image
  265.                 elm := hom.transversal[i] * hom.generators[k];
  266.                 img := hom.transimages[i] * hom.genimages[k];
  267.  
  268.                 # divde the schreier generator through the stabilizer chain
  269.                 stb := hom;
  270.                 while stb.generators <> []
  271.                   and IsBound(stb.transversal[stb.orbit[1]^elm])  do
  272.                     bpt := stb.orbit[1];
  273.                     while bpt ^ elm <> bpt  do
  274.                         img := img * stb.transimages[bpt^elm];
  275.                         elm := elm * stb.transversal[bpt^elm];
  276.                     od;
  277.                     stb := stb.stabilizer;
  278.                 od;
  279.  
  280.                 # if the image is not trivial add it to the cokernel
  281.                 if not img in C  then
  282.                     C := Closure( C, img );
  283.                 fi;
  284.  
  285.             od;
  286.  
  287.         od;
  288.  
  289.         # go down to the next stabilizer
  290.         hom := hom.stabilizer;
  291.  
  292.     od;
  293.  
  294.     # return the cokernel
  295.     return NormalClosure( Parent( C ), C );
  296. end;
  297.  
  298. PermGroupHomomorphismByImagesOps.ImageElm := function ( hom, elm )
  299.     if not IsMapping( hom )  then
  300.         Error("<hom> must be a single valued mapping");
  301.     fi;
  302.     return hom.operations.ImagesRepresentative( hom, elm );
  303. end;
  304.  
  305. PermGroupHomomorphismByImagesOps.ImagesElm := function ( hom, elm )
  306.     local   img,        # image of <elm>, result
  307.             stb,        # stabilizer of <G>
  308.             bpt;        # basepoint of <stb>
  309.  
  310.     # make sure we have a stabilizer chain and the co kernel
  311.     if not IsBound( hom.stabilizer )  then
  312.         hom.operations.MakeMapping( hom );
  313.     fi;
  314.     if not IsBound( hom.coKernel )  then
  315.         hom.coKernel := hom.operations.CoKernel( hom );
  316.     fi;
  317.  
  318.     # go down the stabchain and reduce the permutation
  319.     stb := hom;
  320.     img := hom.range.identity;
  321.     while stb.generators <> []  do
  322.         bpt := stb.orbit[1];
  323.  
  324.         # if '<bpt>^<elm>' is not in the orbit then <elm> is not in <source>
  325.         if not IsBound(stb.transversal[bpt^elm])  then
  326.             return [];
  327.         fi;
  328.  
  329.         # reduce <elm> into the stabilizer
  330.         while bpt ^ elm <> bpt  do
  331.             img := img * stb.transimages[bpt^elm];
  332.             elm := elm * stb.transversal[bpt^elm];
  333.         od;
  334.  
  335.         # and test if the reduced <g> lies in the stabilizer
  336.         stb := stb.stabilizer;
  337.     od;
  338.  
  339.     # if <elm> is not the identity it did not lie in <source>
  340.     if elm <> hom.source.identity  then
  341.         return [];
  342.     fi;
  343.  
  344.     # return the image
  345.     return hom.coKernel * img^-1;
  346. end;
  347.  
  348. PermGroupHomomorphismByImagesOps.ImagesSet := function ( hom, elms )
  349.     if IsGroup( elms )  and IsSubset( hom.source, elms )  then
  350.         if hom.preimage <> hom.source  then
  351.             elms := Intersection( hom.preimage, elms );
  352.         fi;
  353.         if not IsBound( hom.coKernel )  then
  354.             hom.coKernel := hom.operations.CoKernel( hom );
  355.         fi;
  356.         return Closure( hom.coKernel,
  357.                         Parent( hom.range ).operations.Subgroup(
  358.                                 Parent( hom.range ),
  359.                                 List( elms.generators,
  360.                                       gen -> ImagesRepresentative( hom,
  361.                                                                    gen ) )));
  362.     else
  363.         return GroupHomomorphismOps.ImagesSet( hom, elms );
  364.     fi;
  365. end;
  366.  
  367. PermGroupHomomorphismByImagesOps.ImagesRepresentative := function (hom,elm)
  368.     local   img,        # image of <elm>, result
  369.             stb,        # stabilizer of <G>
  370.             bpt;        # basepoint of <stb>
  371.  
  372.     # make sure we have a stabilizer chain
  373.     if not IsBound( hom.stabilizer )  then
  374.         hom.operations.MakeMapping( hom );
  375.     fi;
  376.  
  377.     # go down the stabchain and reduce the permutation
  378.     stb := hom;
  379.     img := hom.range.identity;
  380.     while stb.generators <> []  do
  381.         bpt := stb.orbit[1];
  382.  
  383.         # if '<bpt>^<elm>' is not in the orbit then <elm> is not in <source>
  384.         if not IsBound(stb.transversal[bpt^elm])  then
  385.             Error("<elm> must lie in the preimage of <hom>");
  386.         fi;
  387.  
  388.         # reduce <elm> into the stabilizer
  389.         while bpt ^ elm <> bpt  do
  390.             img := img * stb.transimages[bpt^elm];
  391.             elm := elm * stb.transversal[bpt^elm];
  392.         od;
  393.  
  394.         # and test if the reduced <g> lies in the stabilizer
  395.         stb := stb.stabilizer;
  396.     od;
  397.  
  398.     # if <elm> is not the identity it did not lie in <source>
  399.     if elm <> hom.source.identity  then
  400.         Error("<elm> must lie in the preimage of <hom>");
  401.     fi;
  402.  
  403.     # return the image
  404.     return img^-1;
  405. end;
  406.  
  407. PermGroupHomomorphismByImagesOps.CompositionMapping := function (hom1,hom2)
  408.     local   prd,        # product of <hom1> and <hom2>, result
  409.             stb,        # stabilizer in the chain of <prd>
  410.             gens,       # strong generators of '<hom1>.source'
  411.             imgs,       # their images under <prd>
  412.             i, k;       # loop variables
  413.  
  414.     # product of a homomorphism by generator images
  415.     if IsHomomorphism( hom2 )  and IsBound( hom2.genimages )  then
  416.  
  417.         # with another homomorphism
  418.         if IsHomomorphism( hom1 )  then
  419.  
  420.             # make sure we have a stabilizer chain for the left homomorphism
  421.             if not IsBound( hom2.stabilizer )  then
  422.                 hom1.operations.MakeMapping( hom2 );
  423.             fi;
  424.  
  425.             # make the homomorphism
  426.             prd := rec( );
  427.             prd.isGeneralMapping := true;
  428.             prd.domain          := Mappings;
  429.  
  430.             # enter the identifying information
  431.             prd.source          := hom2.source;
  432.             prd.range           := hom1.range;
  433.  
  434.             # enter usefull information
  435.             prd.isMapping       := true;
  436.             prd.isHomomorphism  := true;
  437.             prd.preimage        := hom2.source;
  438.  
  439.             # copy the stabilizer chain and update the images of the sgs
  440.             gens := [ prd.source.identity ];
  441.             imgs := [ prd.range.identity ];
  442.             stb := prd;
  443.             stb.identity        := hom2.source.identity;
  444.             stb.generators      := [];
  445.             stb.genimages       := [];
  446.             while hom2.generators <> []  do
  447.  
  448.                 # copy the generators and their images
  449.                 for i  in [ 1 .. Length( hom2.generators ) ]  do
  450.                     if not hom2.generators[i]  in gens  then
  451.                         Add( gens, hom2.generators[i] );
  452.                         Add( imgs, ImagesRepresentative( hom1,
  453.                                                       hom2.genimages[i] ) );
  454.                     fi;
  455.                     stb.generators[i] := hom2.generators[i];
  456.                     stb.genimages[i] := imgs[ Position( gens,
  457.                                                       hom2.generators[i] ) ];
  458.                 od;
  459.  
  460.                 # copy the orbit and transversal
  461.                 stb.orbit := [];
  462.                 stb.transversal := [];
  463.                 stb.transimages := [];
  464.                 for i  in [ 1 .. Length( hom2.orbit ) ]  do
  465.                     k := hom2.orbit[i];
  466.                     stb.orbit[i] := k;
  467.                     stb.transversal[k] := hom2.transversal[k];
  468.                     stb.transimages[k] := imgs[ Position( gens,
  469.                                                      hom2.transversal[k] ) ];
  470.                 od;
  471.  
  472.                 # on to the next stabilizer
  473.                 stb.stabilizer := rec();
  474.                 stb.stabilizer.identity   := stb.identity;
  475.                 stb.stabilizer.generators := [];
  476.                 stb.stabilizer.genimages  := [];
  477.                 stb := stb.stabilizer;
  478.                 hom2 := hom2.stabilizer;
  479.  
  480.             od;
  481.  
  482.             # enter the operations record
  483.             prd.operations      := PermGroupHomomorphismByImagesOps;
  484.  
  485.         # with another mapping
  486.         else
  487.  
  488.             prd := MappingOps.CompositionMapping( hom1, hom2 );
  489.  
  490.         fi;
  491.  
  492.     # of something else
  493.     else
  494.         prd := MappingOps.CompositionMapping( hom1, hom2 );
  495.     fi;
  496.  
  497.     # return the product
  498.     return prd;
  499. end;
  500.  
  501.  
  502. #############################################################################
  503. ##
  504. #F  PermGroupOps.OperationHomomorphism(<G>,<P>) . . .  operation homomorphism
  505. #F                                                           for a perm group
  506. ##
  507. PermGroupOps.OperationHomomorphism := function ( G, P )
  508.     local   hom;        # operation homomorphism from <G> into <P>, result
  509.  
  510.     # special case for transitive constituent homomorphism
  511.     if      P.operationOperation = OnPoints
  512.         and ForAll( P.operationDomain, IsInt )
  513.     then
  514.         hom := PermGroupOps.TransConstHomomorphism( G, P );
  515.  
  516.     # special case for blocks homomorphism
  517.     elif    P.operationOperation = OnSets
  518.         and ForAll( P.operationDomain, IsSet )
  519.         and Size( Union(P.operationDomain) ) = Sum( P.operationDomain, Size )
  520.     then
  521.         hom := PermGroupOps.BlocksHomomorphism( G, P );
  522.  
  523.     # delegate other cases
  524.     else
  525.         hom := GroupOps.OperationHomomorphism( G, P );
  526.  
  527.     fi;
  528.  
  529.     # return the homomorphism
  530.     return hom;
  531. end;
  532.  
  533.  
  534. #############################################################################
  535. ##
  536. #F  PermGroupOps.TransConstHomomorphism(<G>,<P>) . . . transitive constituent
  537. #F                                               homomorphism of <G> into <P>
  538. ##
  539. ##  The  reason  that we  specialize 'OperationHomomorphism'  for   this case
  540. ##  is that we can map  stabilizer chains when  we take  images of  preimages
  541. ##  of subgroups.   Also taking images of  elements  can be  made a litte bit
  542. ##  faster.
  543. ##
  544. PermGroupOps.TransConstHomomorphism := function ( G, P )
  545.     local   hom;        # homomorphism, result
  546.  
  547.     # make the homomorphism
  548.     hom := rec(
  549.  
  550.         # tags
  551.         isGeneralMapping    := true,
  552.         domain              := Mappings,
  553.  
  554.         # source and range
  555.         source              := G,
  556.         range               := P,
  557.  
  558.         # permutation mapping <D> to the moved points of <P>
  559.         conperm             := MappingPermListList( P.operationDomain,
  560.                                      [ 1 .. Length( P.operationDomain ) ] ),
  561.  
  562.         # usefull information
  563.         isMapping           := true,
  564.         isHomomorphism      := true,
  565.         isGroupHomomorphism := true,
  566.         isTransConstHom     := true,
  567.  
  568.         # operations record
  569.         operations          := TransConstHomomorphismOps );
  570.  
  571.     # return the homomorphism
  572.     return hom;
  573. end;
  574.  
  575. TransConstHomomorphismOps := Copy( OperationHomomorphismOps );
  576.  
  577. TransConstHomomorphismOps.ImageElm := function ( hom, elm )
  578.     return RestrictedPerm(elm,hom.range.operationDomain) ^ hom.conperm;
  579. end;
  580.  
  581. TransConstHomomorphismOps.ImagesElm := function ( hom, elm )
  582.     return [ hom.operations.ImageElm( hom, elm ) ];
  583. end;
  584.  
  585. TransConstHomomorphismOps.ImagesRepresentative
  586.         := TransConstHomomorphismOps.ImageElm;
  587.  
  588. TransConstHomomorphismOps.ImagesSet := function ( hom, H )
  589.     local   I,          # image of <H>, result
  590.             S,          # stabilizer in <H>
  591.             T,          # corresponding stabilizer in <I>
  592.             gens,       # strong generators of <H>
  593.             imgs,       # their images in <I>
  594.             top,        # is 'true' if <T> is <I>
  595.             gen,        # one generator from <gens>
  596.             pnt,        # one point in the orbit <S>
  597.             img;        # the image of <pnt> in the orbit of <T>
  598.  
  599.     # handle special case that <H> is a subgroup of '<hom>.source'
  600.     if IsDomain( H )  then
  601.  
  602.         # adapt the base of <H> to the subset of <D> that is in the base
  603.         MakeStabChain( H, hom.range.operationDomain );
  604.         Size( H );
  605.         InfoPermGroup1("#I  TransConstHomOps.ImagesSet called for ",
  606.                         GroupString(H,"H"),"\n");
  607.  
  608.         # initialize a list of strong gens of <H> and their images in <I>
  609.         gens := [];
  610.         imgs := [];
  611.         for gen  in H.generators  do
  612.             Add( gens, gen );
  613.             Add( imgs, Image( hom, gen ) );
  614.         od;
  615.  
  616.         # create the image group
  617.         I := Subgroup( Parent( hom.range ), imgs );
  618.         if IsBound( I.orbit )  then return I;  fi;
  619.  
  620.         # loop over the points in the subset of <G> that is in the base
  621.         S := H;
  622.         T := I;
  623.         top := true;
  624.         while   IsBound( S.orbit )
  625.             and S.orbit[1] in hom.range.operationDomain
  626.         do
  627.  
  628.             # make the generators for <T>
  629.             if not top  then
  630.                 T.generators := [];
  631.                 for gen  in S.generators  do
  632.                     if not gen in gens  then
  633.                         Add( gens, gen );
  634.                         Add( imgs, Image( hom, gen ) );
  635.                     fi;
  636.                     if imgs[ Position( gens, gen ) ] <> T.identity  then
  637.                        Add( T.generators, imgs[ Position( gens, gen ) ] );
  638.                    fi;
  639.                 od;
  640.             fi;
  641.  
  642.             # make the orbit and the transversal for <T>
  643.             T.orbit := [];
  644.             T.transversal := [];
  645.             for pnt  in S.orbit  do
  646.                 img := pnt ^ hom.conperm;
  647.                 Add( T.orbit, img );
  648.                 if pnt <> S.orbit[1]  then
  649.                     gen := S.transversal[ pnt ];
  650.                     T.transversal[ img ] := imgs[ Position( gens, gen ) ];
  651.                 else
  652.                     T.transversal[ img ] := T.identity;
  653.                 fi;
  654.             od;
  655.  
  656.             # add a trivial stabilizer
  657.             T.stabilizer := rec(
  658.                 generators := [],
  659.                 identity   := T.identity );
  660.  
  661.             # go down to the next step
  662.             S := S.stabilizer;
  663.             T := T.stabilizer;
  664.             top := false;
  665.  
  666.         od;
  667.  
  668.         # give some information
  669.         Size( I );
  670.         InfoPermGroup1("#I  TransConstHomOps.ImagesSet returns ",
  671.                         GroupString(I,"I"),"\n");
  672.  
  673.     # delegate set case
  674.     else
  675.         I := OperationHomomorphismOps.ImagesSet( hom, H );
  676.  
  677.     fi;
  678.  
  679.     # return the image
  680.     return I;
  681. end;
  682.  
  683. TransConstHomomorphismOps.PreImagesSet := function ( hom, I )
  684.     local   H,          # preimage of <I>, result
  685.             S,          # stabilizer in <H>
  686.             T,          # corresponding stabilizer in <I>
  687.             K,          # kernel of <hom>
  688.             gens,       # strong generators of <I>
  689.             pres,       # their preimages in <H>
  690.             top,        # is 'true' if <S> is <H>
  691.             gen,        # one generator from <gens>
  692.             pnt,        # one point in the orbit <T>
  693.             img;        # the preimage of <pnt> in the orbit of <S>
  694.  
  695.     #N  18-Feb-92 <I> need not be a subset of 'Image( <hom> )'
  696.  
  697.     # handle special case that <I> is a subgroup of '<hom>.range'
  698.     if IsDomain( I )  then
  699.  
  700.         # compute a stabilizer chain for <I>
  701.         MakeStabChain( I );
  702.         Size( I );
  703.         InfoPermGroup1("#I  TransConstHomOps.PreImagsSet called for ",
  704.                         GroupString(I,"I"),"\n");
  705.  
  706.         # initialize a list of strong gens of <I> and their preimages in <H>
  707.         gens := [];
  708.         pres := [];
  709.         for gen  in I.generators  do
  710.             Add( gens, gen );
  711.             Add( pres, PreImagesRepresentative( hom, gen ) );
  712.         od;
  713.  
  714.         # compute the kernel of <hom>
  715.         K := Kernel( hom );
  716.  
  717.         # create the preimage group
  718.         H := Subgroup(Parent(hom.source),Concatenation(pres,K.generators));
  719.         if IsBound( H.orbit )  then return H;  fi;
  720.  
  721.         # loop over the basepoints of <I>
  722.         S := H;
  723.         T := I;
  724.         top := true;
  725.         while IsBound( T.orbit )  do
  726.  
  727.             # make the generators for <S>
  728.             if not top  then
  729.                 S.generators := ShallowCopy( K.generators );
  730.                 for gen  in T.generators  do
  731.                     if not gen in gens  then
  732.                         Add( gens, gen );
  733.                         Add( pres, PreImagesRepresentative( hom, gen ) );
  734.                     fi;
  735.                     Add( S.generators, pres[ Position( gens, gen ) ] );
  736.                 od;
  737.             fi;
  738.  
  739.             # make the orbit and the transversal for <S>
  740.             S.orbit := [];
  741.             S.transversal := [];
  742.             for pnt  in T.orbit  do
  743.                 img := pnt / hom.conperm;
  744.                 Add( S.orbit, img );
  745.                 if pnt <> T.orbit[1]  then
  746.                     gen := T.transversal[ pnt ];
  747.                     S.transversal[ img ] := pres[ Position( gens, gen ) ];
  748.                 else
  749.                     S.transversal[ img ] := S.identity;
  750.                 fi;
  751.             od;
  752.  
  753.             # add a trivial stabilizer
  754.             S.stabilizer := rec(
  755.                 generators := [],
  756.                 identity   := S.identity );
  757.  
  758.             # go down to the next step
  759.             S := S.stabilizer;
  760.             T := T.stabilizer;
  761.             top := false;
  762.  
  763.         od;
  764.  
  765.         # append the kernel to the stabilizer chain of <H>
  766.         #N  18-Feb-92 martin 'Copy' and 'ShallowCopy' should go away
  767.         S.generators := ShallowCopy( K.generators );
  768.         if IsBound( K.orbit )  then
  769.             S.orbit       := ShallowCopy( K.orbit );
  770.             S.transversal := ShallowCopy( K.transversal );
  771.             S.stabilizer  := Copy( K.stabilizer );
  772.         fi;
  773.  
  774.         # give some information
  775.         Size( H );
  776.         InfoPermGroup1("#I  TransConstHomOps.PreImagesSet returns ",
  777.                         GroupString(H,"H"),"\n");
  778.  
  779.     # delegate set case
  780.     else
  781.         H := OperationHomomorphismOps.PreImagesSet( hom, I );
  782.  
  783.     fi;
  784.  
  785.     # return the preimage
  786.     return H;
  787. end;
  788.  
  789.  
  790. #############################################################################
  791. ##
  792. #F  PermGroupOps.BlocksHomomorphism(<G>,<P>)   homomorphism for the operation
  793. #F                                   of a permutation group on a block system
  794. ##
  795. PermGroupOps.BlocksHomomorphism := function ( G, P )
  796.     local   hom,        # homomorphism, result
  797.             i, k;       # loop variables
  798.  
  799.     # make the homomorphism
  800.     hom := rec(
  801.  
  802.         # tags
  803.         isGeneralMapping    := true,
  804.         domain              := Mappings,
  805.  
  806.         # source and range
  807.         source              := G,
  808.         range               := P,
  809.  
  810.         # get the blocks
  811.         blocks              := P.operationDomain,
  812.  
  813.         # usefull information
  814.         isMapping           := true,
  815.         isHomomorphism      := true,
  816.         isGroupHomomorphism := true,
  817.         isBlocksHomomorphism := true,
  818.  
  819.         # operations record
  820.         operations          := BlocksHomomorphismOps );
  821.  
  822.     # add also a list that says for each element which block it lies in
  823.     hom.reps := [];
  824.     for i  in [ 1 .. Length( hom.blocks ) ]  do
  825.         for k  in hom.blocks[i]  do
  826.             hom.reps[k] := i;
  827.         od;
  828.     od;
  829.  
  830.     # return the homomorphism
  831.     return hom;
  832. end;
  833.  
  834. BlocksHomomorphismOps := Copy( OperationHomomorphismOps );
  835.  
  836. BlocksHomomorphismOps.ImageElm := function ( hom, elm )
  837.     local    img,       # image of <elm> under <hom>, result
  838.              i;         # loop variable
  839.  
  840.     # make the image permutation as a list
  841.     img := [];
  842.     for i  in [ 1 .. Length( hom.blocks ) ]  do
  843.         img[i] := hom.reps[ hom.blocks[i][1] ^ elm ];
  844.     od;
  845.  
  846.     # return the image as a permutation
  847.     return PermList( img );
  848. end;
  849.  
  850. BlocksHomomorphismOps.ImagesElm := function ( hom, elm )
  851.     return [ hom.operations.ImageElm( hom, elm ) ];
  852. end;
  853.  
  854. BlocksHomomorphismOps.ImagesRepresentative
  855.         := BlocksHomomorphismOps.ImageElm;
  856.  
  857. BlocksHomomorphismOps.ImagesSet := function ( hom, H )
  858.     local   I,          # image of <H>, result
  859.             S,          # block stabilizer in <H>
  860.             T,          # corresponding stabilizer in <I>
  861.             R,          # temporary stabilizer
  862.             gens,       # strong generators of <H>
  863.             imgs,       # their images in <I>
  864.             top,        # 'true' if <T> is <I>
  865.             gen,        # one generator from <gens>
  866.             pnt,        # one point in the orbit <S>
  867.             img,        # the image of <pnt> in the orbit of <T>
  868.             blockStabsOrbit,        # orbit of the block stabilizers
  869.             blockStabsTransversal,  # transversals of the block stabilizers
  870.             i;          # loop variable
  871.  
  872.     # handle the special case that <H> is a subgroup of '<hom>.source'
  873.     if IsDomain( H )  then
  874.  
  875.         # compute the generators for the image
  876.         gens := [];
  877.         imgs := [];
  878.         for gen  in H.generators  do
  879.             Add( gens, gen );
  880.             Add( imgs, Image( hom, gen ) );
  881.         od;
  882.  
  883.         # initialize the image group
  884.         I := Subgroup( Parent( hom.range ), imgs );
  885.  
  886.         blockStabsOrbit := [];
  887.         blockStabsTransversal := [];
  888.  
  889.         # start with the group
  890.         S := H;
  891.         T := I;
  892.         top := true;
  893.  
  894.         # loop over the blocks
  895.         for i  in [ 1 .. Length( hom.blocks ) ]  do
  896.  
  897.             # make sure that <S> has the rep. of the block as basepoint
  898.             MakeStabChain( S, [ hom.blocks[i][1] ] );
  899.  
  900.             # if <S> does not already stabilize this block
  901.             if      IsBound( S.orbit )
  902.                 and S.orbit[1] = hom.blocks[i][1]
  903.                 and not IsSubsetSet( hom.blocks[i], S.orbit )
  904.             then
  905.  
  906.                 # add orbit and transversal to the representative lists
  907.                 Add( blockStabsOrbit, S.orbit );
  908.                 Add( blockStabsTransversal, S.transversal );
  909.  
  910.                 # make the generators for <T>
  911.                 if not top  then
  912.                     T.generators := [];
  913.                     for gen  in S.generators  do
  914.                         if not gen in gens  then
  915.                             Add( gens, gen );
  916.                             Add( imgs, Image( hom, gen ) );
  917.                         fi;
  918.                         if imgs[ Position( gens, gen ) ] <> T.identity  then
  919.                             Add( T.generators, imgs[ Position(gens,gen) ] );
  920.                         fi;
  921.                     od;
  922.                 fi;
  923.  
  924.                 # make the orbit and the transversal of <T>
  925.                 T.orbit       := [ i ];
  926.                 T.transversal := [];
  927.                 T.transversal[i] := ();
  928.                 for pnt  in S.orbit  do
  929.                     img := hom.reps[ pnt ];
  930.                     if not img in T.orbit  then
  931.                         Add( T.orbit, img );
  932.                         gen := S.transversal[ pnt ];
  933.                         T.transversal[ img ] := imgs[ Position(gens,gen) ];
  934.                     fi;
  935.                 od;
  936.  
  937.                 # add a trivial stabilizer to <T>
  938.                 T.stabilizer := rec(
  939.                     identity    := T.identity,
  940.                     generators  := [] );
  941.  
  942.                 # make <R> the stabilizer of the block in <S>
  943.                 #N  18-Feb-91 martin 'Copy' and 'ShallowCopy' should go away
  944.                 R := ShallowCopy( Subgroup( Parent( S ), [] ) );
  945.                 R.generators := ShallowCopy( S.stabilizer.generators );
  946.                 R.orbit := [ S.orbit[1] ];
  947.                 R.transversal := [];
  948.                 R.transversal[ R.orbit[1] ] := R.identity;
  949.                 for pnt  in S.orbit  do
  950.                     if pnt in hom.blocks[i]  and not pnt in R.orbit  then
  951.                         gen := R.identity;
  952.                         while R.orbit[1] ^ gen <> pnt  do
  953.                             gen := LeftQuotient(S.transversal[pnt/gen],gen);
  954.                         od;
  955.                         PermGroupOps.AddGensExtOrb( R, [gen] );
  956.                     fi;
  957.                 od;
  958.                 R.stabilizer := Copy( S.stabilizer );
  959.  
  960.                 # prepare for the next step
  961.                 S := R;
  962.                 T := T.stabilizer;
  963.                 top := false;
  964.  
  965.             fi;
  966.  
  967.         od;
  968.  
  969.         # if <H> is the full group this also gives us the kernel
  970.         if H = hom.source  and not IsBound( hom.kernel )  then
  971.             hom.kernel := S;
  972.             hom.blockStabsOrbit := blockStabsOrbit;
  973.             hom.blockStabsTransversal := blockStabsTransversal;
  974.         fi;
  975.  
  976.     # delegate the set case
  977.     else
  978.         I := OperationHomomorphismOps.ImagesSet( hom, H );
  979.  
  980.     fi;
  981.  
  982.     # return the images
  983.     return I;
  984. end;
  985.  
  986. BlocksHomomorphismOps.PreImagesRepresentative := function ( hom, elm )
  987.     local   pre,        # preimage of <elm>, result
  988.             pnt,        # one point of a set stabilizer
  989.             i;          # loop variable
  990.  
  991.     # make sure that we know the iterated set stabilizers
  992.     if not IsBound( hom.blockStabsOrbit )  then
  993.         Image( hom );
  994.     fi;
  995.  
  996.     # start with the identity as preimage
  997.     pre := hom.source.identity;
  998.  
  999.     # loop over the blocks and their interated set stabilizers
  1000.     for i  in [ 1 .. Length( hom.blockStabsOrbit ) ]  do
  1001.  
  1002.         # find a rep. mapping 'blocks[<i>]' to 'blocks[<i>^<elm>]^(<pre>^-1)'
  1003.         pnt := First( hom.blocks[ hom.reps[hom.blockStabsOrbit[i][1]]^elm ],
  1004.                       pnt -> pnt / pre in hom.blockStabsOrbit[i] );
  1005.         while hom.blockStabsOrbit[i][1] ^ pre <> pnt  do
  1006.             pre := LeftQuotient(hom.blockStabsTransversal[i][pnt/pre],pre);
  1007.         od;
  1008.  
  1009.     od;
  1010.  
  1011.     # return the preimage
  1012.     return pre;
  1013. end;
  1014.  
  1015. BlocksHomomorphismOps.PreImagesSet := function ( hom, I )
  1016.     local   H;          # preimage of <I> under <hom>, result
  1017.  
  1018.     # make sure we know a stabilizer chain for <I>
  1019.     MakeStabChain( I );
  1020.  
  1021.     # now compute the preimage by iterating
  1022.     H := BlocksHomomorphismOps.PreImagesSetStab( hom, I );
  1023.  
  1024.     # return the preimage
  1025.     return H;
  1026. end;
  1027.  
  1028. BlocksHomomorphismOps.PreImagesSetStab := function ( hom, I )
  1029.     local   H,          # preimage of <I> under <hom>, result
  1030.             pnt,        # rep. of the block that is the basepoint <I>
  1031.             gen,        # one generator of <I>
  1032.             pre;        # a representative of its preimages
  1033.  
  1034.     # if <I> is trivial is preimage is the kernel of <hom>
  1035.     if I.generators = []  then
  1036.         H := ShallowCopy( Kernel( hom ) );
  1037.         H.generators  := ShallowCopy( H.generators );
  1038.         if IsBound( H.orbit )  then
  1039.             H.orbit       := ShallowCopy( H.orbit );
  1040.             H.transversal := ShallowCopy( H.transversal );
  1041.             H.stabilizer  := Copy( H.stabilizer );
  1042.         fi;
  1043.  
  1044.     # else begin with the preimage $H_{block[i]}$ of the stabilizer  $I_{i}$,
  1045.     # adding preimages of the generators of  $I$  to those of  $H_{block[i]}$
  1046.     # gives us generators for $H$. Because $H_{block[i][1]} \<= H_{block[i]}$
  1047.     # the stabilizer chain below $H_{block[i][1]}$ is already complete, so we
  1048.     # only have to care about the top level with the basepoint $block[i][1]$.
  1049.     else
  1050.         H := BlocksHomomorphismOps.PreImagesSetStab( hom, I.stabilizer );
  1051.         pnt := hom.blocks[ I.orbit[1] ][1];
  1052.         MakeStabChain(   H, [ pnt ] );
  1053.         ExtendStabChain( H, [ pnt ] );
  1054.         for gen  in I.generators  do
  1055.             pre := PreImagesRepresentative( hom, gen );
  1056.             if not IsBound( H.transversal[ pnt ^ pre ] )  then
  1057.                 PermGroupOps.AddGensExtOrb( H, [ pre ] );
  1058.             fi;
  1059.         od;
  1060.  
  1061.     fi;
  1062.  
  1063.     # return the preimage
  1064.     return H;
  1065. end;
  1066.  
  1067. BlocksHomomorphismOps.KernelGroupHomomorphism := function ( hom )
  1068.  
  1069.     # when we compute the image we will also get the kernel
  1070.     Image( hom );
  1071.  
  1072.     # return the kernel
  1073.     return hom.kernel;
  1074. end;
  1075.  
  1076.  
  1077. #############################################################################
  1078. ##
  1079. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1080. ##
  1081. ##  Local Variables:
  1082. ##  mode:               outline
  1083. ##  outline-regexp:     "#F\\|#V\\|#E\\|#R"
  1084. ##  fill-column:        73
  1085. ##  fill-prefix:        "##  "
  1086. ##  eval:               (hide-body)
  1087. ##  End:
  1088. ##
  1089.  
  1090.  
  1091.  
  1092.