home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / agsubgrp.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  40.2 KB  |  1,501 lines
  1. #############################################################################
  2. ##
  3. #A  agsubgrp.g                  GAP library                      Frank Celler
  4. ##
  5. #A  @(#)$Id: agsubgrp.g,v 3.25 1992/12/16 19:47:27 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file  contains   most functions  for named subgroups,  all functions
  10. ##  dealing with  or computing induced  or canonical  generating systems  for
  11. ##  aggroups and all functions for orbit-stabilizer calculation.
  12. ##
  13. #H  $Log: agsubgrp.g,v $
  14. #H  Revision 3.25  1992/12/16  19:47:27  martin
  15. #H  replaced quoted record names with escaped ones
  16. #H
  17. #H  Revision 3.24  1992/12/02  08:09:14  fceller
  18. #H  moved 'CompositionSeries' and 'PCentralSeries' to "group.tex"
  19. #H
  20. #H  Revision 3.23  1992/11/30  18:36:51  fceller
  21. #H  moved 'ElementaryAbelianSeries' and 'CompositionSeries' to "group.g"
  22. #H
  23. #H  Revision 3.22  1992/08/14  14:58:06  fceller
  24. #H  'ElementaryAbelianSeries' now stores its result in the group record
  25. #H  instead of just storing the factor groups.
  26. #H
  27. #H  Revision 3.21  1992/06/16  11:09:54  fceller
  28. #H  added 'FrattiniSubgroup' for p-groups
  29. #H
  30. #H  Revision 3.20  1992/04/03  13:10:09  fceller
  31. #H  changed 'Shifted...' into 'Sifted...'
  32. #H
  33. #H  Revision 3.19  1992/03/27  15:20:44  fceller
  34. #H  fixed a typo in 'PCentralSeries'
  35. #H
  36. #H  Revision 3.18  1992/02/07  18:11:40  fceller
  37. #H  Initial GAP 3.1 release.
  38. #H
  39. #H  Revision 3.1  1991/05/18  11:49:34  fceller
  40. #H  Initial revision
  41. ##
  42.  
  43.  
  44. #############################################################################
  45. ##
  46. #F  InfoAgGroup1( <arg> ) . . . . . . . . . . . . . . . . package information
  47. #F  InfoAgGroup2( <arg> ) . . . . . . . . . . . . . package debug information
  48. ##
  49. if not IsBound( InfoAgGroup1 )  then InfoAgGroup1 := Ignore;  fi;
  50. if not IsBound( InfoAgGroup2 )  then InfoAgGroup2 := Ignore;  fi;
  51.  
  52.  
  53. #############################################################################
  54. ##
  55.  
  56. #F  MergedIgs( <G>, <V>, <gens>, <normalize> )  . . . . . igs of <gens> & <V>
  57. ##
  58. AgGroupOps.MergedIgs := function( G, V, gens, normalize )
  59.  
  60.    local gensG, nrGensG,
  61.          gensNew, gensOld,
  62.          weightSeen, gensSeen,
  63.          chain,
  64.          subWeight,
  65.          pag, group,
  66.          i, j,
  67.          id,
  68.          cux, cuxw,
  69.          u, uw, uPowers,
  70.          v,
  71.          x;
  72.  
  73.    # Get the number of group <G> generators, this is the maximal depth.
  74.    gensG   := Igs( G );
  75.    nrGensG := Length( gensG );
  76.  
  77.    # Make  a  table to look up the weight corresponding to a subgroup, if the
  78.    # weight in the parent group is known.
  79.    subWeight := [];
  80.    for i  in [ 1 .. nrGensG ]  do
  81.       subWeight[ DepthAgWord( gensG[ i ] ) ] := i;
  82.    od;
  83.  
  84.    # At  first  we  have  not seen any weight or a pag-system. We make a list
  85.    # <id> for each weight and a list of 'false' for each seen weight.
  86.    id := G.identity;
  87.    weightSeen := List( [ 1 .. nrGensG ], x -> false );
  88.    pag        := List( [ 1 .. nrGensG ], x -> id    );
  89.  
  90.    # If a subgroup is known enter those generatos in the pag-system <pag>.
  91.    if IsBound( V.isAgGroup )  then
  92.       for v  in Igs( V )  do
  93.          weightSeen[ subWeight[ DepthAgWord( v ) ] ] := true;
  94.          pag       [ subWeight[ DepthAgWord( v ) ] ] := v;
  95.       od;
  96.    fi;
  97.  
  98.    # Maybe  we  have  trailing  'true'-s  at the end of <weightSeen>. In that
  99.    # case <chain> is the leftmost position of those 'true'-s.
  100.    chain := nrGensG + 1;
  101.    while chain > 1 and weightSeen[ chain - 1 ]  do
  102.       chain := chain - 1;
  103.    od;
  104.  
  105.    # We  only  loop  over the different generators of <gens>. <gensSeen> must
  106.    # contain at least <id>, while <gensNew> never contains it.
  107.    gensNew  := Difference( Set( gens ), [ id ] );
  108.    gensSeen := ShallowCopy( gensNew );
  109.    AddSet( gensSeen, id );
  110.  
  111.    # <gensNew>  will  hold  the  generators  which  must  still be entered in
  112.    # <pag>. If this is the empty list, we have entered all generators.
  113.    while gensNew <> []  do
  114.       gensOld := gensNew;
  115.       gensNew := Set( [] );
  116.       for u  in gensOld  do
  117.          uw := subWeight[ DepthAgWord( u ) ];
  118.  
  119.          # If  the subgroup weight of <u> has reached chain, nothing is to be
  120.          # done with this <u>, as it will reduce to <id>.
  121.          if uw < chain  then
  122.  
  123.             # Now repeat shifting <u> through the <pag> list, until we find a
  124.             # position  containing  <id>.  Not  only  <u>  but all powers are
  125.             # inserted.
  126.             uPowers := [];
  127.             repeat
  128.                if pag[ uw ] <> id  then
  129.                   if uw + 1 >= chain  then
  130.                      u := id;
  131.                   else
  132.                      u := u / pag[uw]^( LeadingExponentAgWord( u )
  133.                                           / LeadingExponentAgWord( pag[uw] )
  134.                                         mod RelativeOrderAgWord( u ) );
  135.                   fi;
  136.                else
  137.                   AddSet( gensSeen, u );
  138.                   weightSeen[ uw ] := true;
  139.                   Add( uPowers, u );
  140.                   if uw + 1 >= chain  then
  141.                      u := id;
  142.                   else
  143.                      u := u ^ RelativeOrderAgWord( u );
  144.                   fi;
  145.                fi;
  146.                if u <> id  then
  147.                   uw := subWeight[ DepthAgWord( u ) ];
  148.                fi;
  149.             until u = id or uw >= chain;
  150.  
  151.             # Add  the  commputators of the powers of <u> with <pag> words to
  152.             # the new generators.
  153.             if uPowers <> []  then
  154.                for u  in uPowers  do
  155.                   for x  in pag  do
  156.                      if x <> id
  157.                         and subWeight[ Minimum( DepthAgWord( x ),
  158.                                        DepthAgWord( u ) ) ] + 1 < chain
  159.                      then
  160.                         cux := Comm( u, x );
  161.                         if not cux in gensSeen  then
  162.                            cuxw := subWeight[ DepthAgWord( cux ) ];
  163.                            weightSeen[ cuxw ] := true;
  164.                            AddSet( gensNew, cux );
  165.                            AddSet( gensSeen, cux );
  166.                         fi;
  167.                      fi;
  168.                   od;
  169.                od;
  170.             fi;
  171.  
  172.             # Enter the generators <uPowers> in <pag>.
  173.             for x  in uPowers  do
  174.                pag[ subWeight[ DepthAgWord( x ) ] ] := x;
  175.             od;
  176.  
  177.             # Update <chain>.
  178.             while chain > 1 and weightSeen[ chain - 1 ]  do
  179.                chain := chain - 1;
  180.             od;
  181.             for i  in [ chain .. nrGensG ]  do
  182.                if pag[ i ] = id  then
  183.                   pag[ i ] := gensG[ i ];
  184.                   for j  in [ 1 .. chain - 1 ]  do
  185.                      cux := Comm( pag[ i ], pag[ j ] );
  186.                      if not cux in gensSeen  then
  187.                         AddSet( gensSeen, cux );
  188.                         AddSet( gensNew, cux );
  189.                         weightSeen[ subWeight[ DepthAgWord(cux) ] ] := true;
  190.                      fi;
  191.                   od;
  192.                fi;
  193.             od;
  194.          fi;
  195.       od;
  196.    od;
  197.  
  198.    # If <chain> has reached 1, we have generated the whole group <G>.
  199.    if chain = 1  then
  200.       if normalize  then
  201.          Cgs( G );
  202.       fi;
  203.       return G;
  204.    fi;
  205.  
  206.    # Remove <id> from <pag> and construct an aggroup record.
  207.    group := AgSubgroup( G, Filtered( pag, x -> x <> id ), false );
  208.  
  209.    # Normalize if necessary.
  210.    if normalize  then
  211.        Normalize( group );
  212.    fi;
  213.  
  214.    return group;
  215.  
  216. end;
  217.  
  218. MergedIgs := function( U, S, gens, normalize )
  219.     return U.operations.MergedIgs( U, S, gens, normalize );
  220. end;
  221.  
  222.  
  223. #############################################################################
  224. ##
  225. #F  MergedCgs( <G>, <objs> )  . . . . . . . . . . canonical generating system
  226. ##
  227. AgGroupOps.MergedCgs := function( U, objs )
  228.  
  229.     local   W,  V,
  230.             cW, cV,
  231.             gen,
  232.             N, Ns,      # normal subgroup(s)
  233.             gens,       # all other generators
  234.             G,          # Supergroup
  235.             T;          # <gen>
  236.  
  237.     # Get parent group and trivial subgroup of <U>.
  238.     G    := Parent( U );
  239.     W    := AgSubgroup( U, [], true );
  240.     cW   := [];
  241.     gens := [];
  242.     Ns   := [];
  243.  
  244.     # Sort  the  generators.  <gens>  holds  generating  elements, <Ns> holds
  245.     # generating  normal  subgroups.  <W> will hold the non-normal generating
  246.     # subgroup with longest composition length.
  247.     for gen  in objs  do
  248.         if IsAgWord( gen ) then
  249.             Add( gens, gen );
  250.         elif IsAgGroup( gen ) then
  251.             V  := gen;
  252.             cV := Igs( V );
  253.             G  := Parent( G, V );
  254.  
  255.             # See if <V> is a normal subgroup.
  256.             if IsBound( V.isNormal ) and V.isNormal  then
  257.                 Add( Ns, V );
  258.             elif Length( cW ) < Length( cV )  then
  259.                 Append( gens, cW );
  260.                 W  := V;
  261.                 cW := cV;
  262.             else
  263.                 Append( gens, cV );
  264.             fi;
  265.         else
  266.  
  267.             # Raise an error as we cannot use <gen>.
  268.             Error( "sorry, I cannot use ", gen, " as generator" );
  269.         fi;
  270.     od;
  271.  
  272.     # Now use 'MergedIgs' and 'Sum'
  273.     T := MergedIgs( U, W, gens, true );
  274.     for N  in Ns  do
  275.         T := SumAgGroup( N, T );
  276.     od;
  277.  
  278.     return T;
  279.  
  280. end;
  281.  
  282. MergedCgs := function( U, L )
  283.     return U.operations.MergedCgs( U, L );
  284. end;
  285.  
  286.  
  287. #############################################################################
  288. ##
  289. #F  Closure( <U>, <obj> ) . . . . . . . . . . . . .  closure of <U> and <obj>
  290. ##
  291. AgGroupOps.Closure := function( U, obj )
  292.     local   C,  S;
  293.  
  294.     if IsAgGroup( obj )  then
  295.         S := Parent( U, obj );
  296.         if Length( Igs( U ) ) < Length( Igs( obj ) )  then
  297.             C := MergedIgs( S, obj, Igs( U ), true );
  298.         else
  299.             C := MergedIgs( S, U, Igs( obj ), true );
  300.         fi;
  301.     else
  302.         C := MergedIgs( Parent( U ), U, [ obj ], false );
  303.     fi;
  304.     return C;
  305.  
  306. end;
  307.  
  308.  
  309. #############################################################################
  310. ##
  311. #F  Igs( <U> )  . . . . . . . . . . . . . . . . . . induced generating system
  312. ##
  313. AgGroupOps.Igs := function( U )
  314.     local   L;
  315.  
  316.     L := MergedIgs( Parent( U ), rec(), U.generators, false );
  317.     if IsBound( L.cgs )  then
  318.         return L.cgs;
  319.     else
  320.         return L.igs;
  321.     fi;
  322.  
  323. end;
  324.  
  325. Igs := function( U )
  326.     local   igs;
  327.  
  328.     if IsBound( U.igs )  then
  329.         igs := U.igs;
  330.     elif IsBound( U.cgs )  then
  331.         igs := U.cgs;
  332.     else
  333.         igs := U.operations.Igs( U );
  334.         if Length( igs ) = Length( U.parent.cgs )  then
  335.             U.cgs := U.parent.cgs;
  336.             igs   := U.cgs;
  337.         else
  338.               U.igs := igs;
  339.         fi;
  340.     fi;
  341.     return igs;
  342.  
  343. end;
  344.  
  345.  
  346. #############################################################################
  347. ##
  348. #F  Cgs( <U> )    . . . . . . . . . . . . . . . . . canonical generating system
  349. ##
  350. AgGroupOps.Cgs := function( U )
  351.     return MergedIgs( Parent( U ), rec(), U.generators, true ).cgs;
  352. end;
  353.     
  354. Cgs := function( U )
  355.     local   cgs;
  356.  
  357.     if IsBound( U.cgs )  then
  358.         cgs := U.cgs;
  359.     elif IsBound( U.igs )  then
  360.         cgs := ShallowCopy( U.igs );
  361.         NormalizeIgs( cgs );
  362.         U.cgs := cgs;
  363.     else
  364.         cgs := U.operations.Cgs( U );
  365.         U.cgs := cgs;
  366.     fi;
  367.     return cgs;
  368.  
  369. end;
  370.  
  371.  
  372. #############################################################################
  373. ##
  374.  
  375. #F  IsNormalized( <U> ) . . . . . . . . . . is induced system a canonical one
  376. ##
  377. AgGroupOps.IsNormalized := function( U )
  378.     local   gens, i, j, d, g;
  379.  
  380.     if not IsBound( U.igs )  then
  381.         Cgs( U );
  382.         return true;
  383.     elif IsBound( U.cgs )  then
  384.         if U.cgs = U.igs  then
  385.             Unbind( U.igs );
  386.             Unbind( U.shiftInfo );
  387.             Unbind( U.compositionSeries );
  388.             Unbind( U.elementaryAbelianFactors );
  389.             return true;
  390.         else
  391.             return false;
  392.         fi;
  393.     else
  394.         gens := U.igs;
  395.  
  396.         # Leading exponent equals one?
  397.         for g  in gens  do
  398.             if LeadingExponentAgWord( g ) <> 1  then
  399.                 return false;
  400.             fi;
  401.         od;
  402.  
  403.         # Zeros above diagonale?
  404.         for i  in [ 2 .. Length( gens ) ]  do
  405.             d := DepthAgWord( gens[ i ] );
  406.             for j  in [ 1 .. i - 1 ]  do
  407.                 if ExponentAgWord( gens[ j ], d ) <> 0  then
  408.                     return false;
  409.                 fi;
  410.             od;
  411.         od;
  412.  
  413.         # <gens> are normalized.
  414.         U.cgs := gens;
  415.         Unbind( U.igs );
  416.         Unbind( U.shiftInfo );
  417.         Unbind( U.compositionSeries );
  418.         Unbind( U.elementaryAbelianFactors );
  419.  
  420.         return true;
  421.     fi;
  422.  
  423. end;
  424.  
  425. IsNormalized := function( U )
  426.     return U.operations.IsNormalized( U );
  427. end;
  428.  
  429.  
  430. #############################################################################
  431. ##
  432. #F  Normalized( <U> ) . . . . . . . . . . . . . . . . . . . subgroup with cgs
  433. ##
  434. AgGroupOps.Normalized := function( U )
  435.     local   V;
  436.  
  437.     # Make a copy of the generators of <U>.
  438.     V := ShallowCopy( U );
  439.     V.generators := ShallowCopy( U.generators );
  440.     if IsBound( U.igs )  then
  441.         if U.igs = U.generators  then
  442.             V.igs := V.generators;
  443.         else
  444.             V.igs := ShallowCopy( U.igs );
  445.         fi;
  446.     fi;
  447.     if IsBound( U.cgs )  then
  448.         if U.cgs = U.generators  then
  449.             V.cgs := V.generators;
  450.         else
  451.             V.cgs := ShallowCopy( U.cgs );
  452.         fi;
  453.     fi;
  454.     V.operations.Normalize( V );
  455.     return V;
  456.  
  457. end;
  458.  
  459. Normalized := function( U )
  460.     return U.operations.Normalized( U );
  461. end;
  462.  
  463.  
  464. #############################################################################
  465. ##
  466. #F  Normalize( <U> )  . . . . . . . . . . . . . . . . . .  convert igs to cgs
  467. ##
  468. AgGroupOps.Normalize := function( U )
  469.     local   i, j, exp, gens;
  470.  
  471.     # If <U> is trivial or normalized return.
  472.     if not IsBound( U.igs )  then
  473.         U.generators := Cgs( U );
  474.         return;
  475.     elif IsBound( U.cgs )  then
  476.         Unbind( U.igs );
  477.         Unbind( U.shiftInfo );
  478.         Unbind( U.compositionSeries );
  479.         Unbind( U.elementaryAbelianFactors );
  480.         Unbind( U.abstractGenerators );
  481.         Unbind( U.factorInfo );
  482.         U.generators := U.cgs;
  483.         return;
  484.     fi;
  485.  
  486.     # Normalize igs.
  487.     gens := ShallowCopy( U.igs );
  488.     NormalizeIgs( gens );
  489.     Unbind( U.igs );
  490.     Unbind( U.shiftInfo );
  491.     Unbind( U.compositionSeries );
  492.     Unbind( U.elementaryAbelianFactors );
  493.     Unbind( U.abstractGenerators );
  494.     Unbind( U.factorInfo );
  495.     U.cgs := gens;
  496.     U.generators := gens;
  497.  
  498. end;
  499.  
  500. Normalize := function( U )
  501.     U.operations.Normalize( U );
  502. end;
  503.  
  504.  
  505. #############################################################################
  506. ##
  507. ##  CopyAgGroup( <G> )    . . . . . . . . . . . . . .  . . copy an ag group <G>
  508. ##
  509. CopyAgGroup := function( G )
  510.     local   H;
  511.  
  512.     H := ShallowCopy( G );
  513.     H.generators := ShallowCopy( G.generators );
  514.     if IsBound( G.igs )  then
  515.         if G.igs = G.generators  then
  516.             H.igs := H.generators;
  517.         else
  518.             H.igs := ShallowCopy( G.igs );
  519.         fi;
  520.     fi;
  521.     if IsBound( G.cgs )  then
  522.         if G.cgs = G.generators  then
  523.             H.cgs := H.generators;
  524.         elif IsBound( G.igs ) and G.cgs = G.igs  then
  525.             H.cgs := H.igs;
  526.         else
  527.             H.cgs := ShallowCopy( G.cgs );
  528.         fi;
  529.     fi;
  530.     return H;
  531.  
  532. end;
  533.  
  534.  
  535. #############################################################################
  536. ##
  537.  
  538. #F  AgGroupOps.ConjugateSubgroup( <U>, <g> )  . . . . . . . . . . . <U> ^ <g>
  539. ##
  540. AgGroupOps.ConjugateSubgroup := function( G, a )
  541.     local   H,  g,  id,  pag;
  542.  
  543.     # Shift <a> through <G>.
  544.     a := SiftedAgWord( G, a );
  545.     if a = G.identity  then
  546.         return G;
  547.     fi;
  548.  
  549.     # Conjugate all generators. Remove unbounds.
  550.     pag := [];
  551.     id  := G.identity;
  552.     for g  in Reversed( Igs( G ) )  do
  553.         g := g ^ a;
  554.         while g <> id and IsBound( pag[ DepthAgWord( g ) ] )  do
  555.             g := ReducedAgWord( g, pag[ DepthAgWord( g ) ] );
  556.         od;
  557.         if g <> id  then
  558.             pag[ DepthAgWord( g ) ] := g;
  559.         fi;
  560.     od;
  561.     pag := Filtered( pag, IsBound );
  562.  
  563.     # Don't normalize the group.
  564.     if IsBound( G.parent )  then
  565.         H := AgSubgroup( G.parent, pag, false );
  566.     else
  567.         H := AgSubgroup( G, pag, false );
  568.     fi;
  569.  
  570.     # copy usefull information
  571.     if IsBound( G.isCyclic )  then
  572.         H.isCyclic := G.isCyclic;
  573.     fi;
  574.     if IsBound( G.isElementaryAbelian )  then
  575.         H.isElementaryAbelian := G.isElementaryAbelian;
  576.     fi;
  577.     if IsBound( G.isAbelian )  then
  578.         H.isAbelian := G.isAbelian;
  579.     fi;
  580.     if IsBound( G.isNilpotent )  then
  581.         H.isNilpotent := G.isNilpotent;
  582.     fi;
  583.     return H;
  584.  
  585. end;
  586.  
  587. AgGroupOps.\^ := AgGroupOps.ConjugateSubgroup;
  588.  
  589.  
  590. #############################################################################
  591. ##
  592. #F  AgGroupOps.ConjugateSubgroups( <G>, <U> ) . .  conjugate subgroups of <U>
  593. ##
  594. AgGroupOps.ConjugateSubgroups := function( G, U )
  595.     local   L,  f,  d,  u,  S;
  596.  
  597.     L := Cgs( U );
  598.     f := function( c, g )
  599.              d := [];
  600.              for u  in c  do
  601.                  Add( d, u^g );
  602.              od;
  603.              d := HomomorphicIgs( d );
  604.              NormalizeIgs( d );
  605.              return d;
  606.          end;
  607.     S := Orbit( G, L, f );
  608.     return List( S, x -> AgSubgroup( G, x, true ) );
  609.  
  610. end;
  611.  
  612.  
  613. #############################################################################
  614. ##
  615. #F  AgGroupOps.NormalClosure( <G>, <U> )  . . . . . . . . . .  normal closure
  616. ##
  617. AgGroupOps.NormalClosure := function( arg )
  618.     local   U, V, M, G, K, gens, subg, tmp, id, g, u;
  619.  
  620.     # If only one group is given, take the supergroup  of  the first argument
  621.     # as default.
  622.     U := arg[ Length( arg ) ];
  623.     if Length( arg ) = 2  then
  624.         V := arg[ 1 ];
  625.     else
  626.         V := Parent( U );
  627.     fi;
  628.  
  629.     # If <U> or <V> is trivial, we can return.
  630.     if U.generators = [] or V.generators = []  then
  631.         return U;
  632.     fi;
  633.  
  634.     # Reduce  the  generators  of  <V>.  Conjugated <U> with those generators
  635.     # until we reach a fixpoint.
  636.     G    := Parent( U, V );
  637.     gens := Set( List( V.generators, x -> SiftedAgWord( U, x ) ) );
  638.     subg := U.generators;
  639.     K    := U;
  640.     id   := G.identity;
  641.     repeat
  642.         M := [];
  643.         for g  in gens  do
  644.             for u  in subg  do
  645.                 tmp := Comm( g, u );
  646.                 if tmp <> id  then
  647.                     AddSet( M, tmp );
  648.                 fi;
  649.             od;
  650.         od;
  651.  
  652.         # For  groups  with  more  generators,  it is better to normalized in
  653.         # order to reduce collecting costs.
  654.         tmp  := MergedIgs( G, K, M, true );
  655.         subg := FactorArg( tmp, K ).generators;
  656.         K    := tmp;
  657.     until subg = [];
  658.  
  659.     # Normalize the group. See above
  660.     return K;
  661.  
  662. end;
  663.  
  664.  
  665. #############################################################################
  666. ##
  667. #F  AgGroupOps.CommutatorSubgroup( <U>, <V> ) . . . . . . commutator subgroup
  668. ##
  669. AgGroupOps.CommutatorSubgroup := function( arg )
  670.     local   U, V, G, u, v, i, j, C;
  671.  
  672.     U := arg[ 1 ];
  673.     if Length( arg ) = 2  then
  674.         V := arg[ 2 ];
  675.     else
  676.         V := U;
  677.     fi;
  678.     G := Parent( U, V );
  679.     if U.generators = [] or V.generators = []  then
  680.         return AgSubgroup( G, [], true );
  681.     fi;
  682.  
  683.     # Construct cgs for <U> and <V>.
  684.     Cgs( U );
  685.     Cgs( V );
  686.  
  687.     # At  first compute all commutators [a,b] of generators a of <U> and b of
  688.     # <V>. If <U> = <V>, we need only compute those with a > b.
  689.     C := [];
  690.  
  691.     # Get the commutators of the generators;
  692.     if U = V  then
  693.         if IsBound( U.derivedSubgroup ) then
  694.             return U.derivedSubgroup;
  695.         fi;
  696.         for i  in [ 1 .. Length( U.cgs ) ]  do
  697.             for j  in [ i + 1 .. Length( V.cgs ) ]  do
  698.                 AddSet( C, Comm( V.cgs[ j ], U.cgs[ i ] ) );
  699.             od;
  700.         od;
  701.         C := MergedIgs( G, rec(), C, true );
  702.     else
  703.         for u  in U.cgs  do
  704.             for v  in V.cgs  do
  705.                 AddSet( C, Comm( v, u ) );
  706.             od;
  707.         od;
  708.         C := Subgroup( G, C );
  709.  
  710.         # In order to conjugate with fewer elements, compute <U,V>. If one is
  711.         # normal than we do not need the normal closure, see Glasby 1987.
  712.         if     not ( IsBound( U.isNormal ) and U.isNormal )
  713.            and not ( IsBound( V.isNormal ) and V.isNormal )
  714.         then
  715.             C := NormalClosure( Closure( U, V ), C );
  716.         fi;
  717.     fi;
  718.  
  719.     # That's it.
  720.     return C;
  721.  
  722. end;
  723.  
  724.  
  725. #############################################################################
  726. ##
  727. #F  AgGroupOps.DerivedSubgroup( <U> ) . . . . . . . . . . .  derived subgroup
  728. ##
  729. AgGroupOps.DerivedSubgroup := AgGroupOps.CommutatorSubgroup;
  730.  
  731.  
  732. #############################################################################
  733. ##
  734. #F  AgGroupOps.DerivedSeries( <U> ) . . . . . . . . . . . . .  derived series
  735. ##
  736. ##  Compute  the  derived  series  of  <U>.  Return a sequence of the derived
  737. ##  groups.  The group {1} is ( always ) part of this series.  This is nearly
  738. ##  the same as 'DerivedSeriesGroup'  but we will set 'isNormal' if <U>  is a
  739. ##  normal.
  740. ##
  741. AgGroupOps.DerivedSeries := function( U )
  742.     local   S, V;
  743.  
  744.     # Return if <U> = {1}.  Otherwise set 'isNormal' in <U>.
  745.     if U.generators = []  then
  746.         return [ U ];
  747.     else
  748.         IsNormal( Parent( U ), U );
  749.     fi;
  750.  
  751.     # Compute derived series by repeated calling of 'DerivedSubgroup'.
  752.     V := U;
  753.     S := [ U ];
  754.     repeat
  755.         V := DerivedSubgroup( V );
  756.         if U.isNormal  then V.isNormal := true;  fi;
  757.         Add( S, V );
  758.     until V.generators = [];
  759.     return S;
  760.  
  761. end;
  762.  
  763.  
  764. #############################################################################
  765. ##
  766. #F  AgGroupOps.LowerCentralSeries( <U> )  . . . . . . .  lower central series
  767. ##
  768. AgGroupOps.LowerCentralSeries := function( U )
  769.     local   S, v, u, C, V;
  770.  
  771.     # Test <U> = {1},  otherwise set 'isNormal' in <U>.
  772.     if U.generators = []  then
  773.         return [ U ];
  774.     else
  775.         IsNormal( Parent( U ), U );
  776.     fi;
  777.  
  778.     # Compute recursively Zi+1 := [G,Zi], Z0 := G.
  779.     V := U;
  780.     S := [];
  781.     repeat
  782.         Cgs( V );
  783.         if U.isNormal  then V.isNormal := true;  fi;
  784.         Add( S, V );
  785.  
  786.         # In  order to avoid the normal closure in case of a not normal group
  787.         # <U>, compute the commutator subgroup directly.
  788.         C := [];
  789.         for u  in U.cgs  do
  790.             for v  in V.cgs  do
  791.                 AddSet( C, Comm( v, u ) );
  792.             od;
  793.         od;
  794.         V := MergedIgs( V, rec(), C, true );
  795.     until V = S[ Length( S ) ];
  796.  
  797.     # If Zi+1 = Zi, return.
  798.     return S;
  799.  
  800. end;
  801.  
  802.  
  803. #############################################################################
  804. ##
  805. #F  AgGroupOps.Core( <G>, <U> ) . . . . . . . core of <U> under action of <G>
  806. ##
  807. AgGroupOps.Core := function( V, U )
  808.     local   N,  G,  v,  C;
  809.  
  810.     # Typecheck arguments and catch trivial cases.
  811.     G := Parent( U, V );
  812.     if IsSubgroup( U, V ) or U.generators = [] or V.generators = []  then
  813.         return U;
  814.     fi;
  815.  
  816.     # Start with <U>.
  817.     C := U;
  818.  
  819.     # Now  compute  intersection with all conjugate subgroups, conjugate with
  820.     # all generators of V and its powers
  821.     for v  in Reversed( Cgs( V ) )  do
  822.         repeat
  823.             N := ConjugateSubgroup( C, v );
  824.             if C <> N  then
  825.                 C := Intersection( C, N );
  826.             fi;
  827.         until C = N;
  828.         if C.generators = []  then
  829.             return C;
  830.         fi;
  831.     od;
  832.     return C;
  833.  
  834. end;
  835.  
  836.  
  837. #############################################################################
  838. ##
  839. #F  AgGroupOps.FrattiniSubgroup( <G> )  . . . . . .  frattini subgroup of <G>
  840. ##
  841. AgGroupOps.FrattiniSubgroup := function( G )
  842.     local   l,  k,  p,  i,  j,  F;
  843.  
  844.     # if <G> is trivial return
  845.     if G.generators = []  then
  846.         F := G;
  847.  
  848.     # <G> must be a p-group
  849.     elif 1 < Length(Set(Factors(Size(G))))  then
  850.         F := GroupOps.FrattiniSubgroup(G);
  851.  
  852.     # Frattini(<G>) = <G>^p * <G>'
  853.     else
  854.         p := RelativeOrderAgWord(G.generators[1]);
  855.         l := Igs(G);
  856.         k := [];
  857.         for i  in [ 2 .. Length(l) ]  do
  858.             for j  in [ 1 .. i-1 ]  do
  859.                 Add(k, Comm(l[i], l[j]));
  860.             od;
  861.             Add(k, l[i]^p);
  862.         od;
  863.         F := MergedIgs(G, rec(), k, false);
  864.     fi;
  865.  
  866.     # return the Frattini group
  867.     return F;
  868.  
  869. end;
  870.  
  871.  
  872. #############################################################################
  873. ##
  874. #F  AgGroupOps.CompositionSeries( <U> ) . . . . . . . . .  composition series
  875. ##
  876. AgGroupOps.CompositionSeries := function( U )
  877.     local   g,  l,  S;
  878.  
  879.     # compute an induced generating system of <U>
  880.     g := Igs( U );
  881.     l := Length( g );
  882.     S := List( [ 1 .. l + 1 ], x -> Sublist( g, [ x .. l ] ) );
  883.     if IsBound( U.igs )  then
  884.         S := List( S, x -> AgSubgroup( U, x, false ) );
  885.     else
  886.         S := List( S, x -> AgSubgroup( U, x, true ) );
  887.     fi;
  888.  
  889.     # make sure the first element of <S> is <U>
  890.     S[1] := U;
  891.  
  892.     # and return <S>
  893.     return S;
  894.  
  895. end;
  896.  
  897.  
  898. #############################################################################
  899. ##
  900. #F  AgGroupOps.PCentralSeries( <U>, <p> ) .  . . . . . . . <p>-central series
  901. ##
  902. AgGroupOps.PCentralSeries := function( U, p )
  903.     local   L,  C,  S,  N,  P;
  904.  
  905.     # Start with <U>.
  906.     L := [];
  907.     N := U;
  908.     repeat
  909.         Add( L, N );
  910.         S := N;
  911.         C := CommutatorSubgroup( U, S );
  912.         P := List( FactorArg( S, C ).generators, x -> x ^ p );
  913.         N := MergedIgs( S, C, P, true );
  914.     until N = S;
  915.     return L;
  916.  
  917. end;
  918.  
  919.  
  920. #############################################################################
  921. ##
  922.  
  923. #F  PRump( <U>, <p> ) . . . . . . . . . . . . . . . . . . . . . . .  <p>-rump
  924. ##
  925. PRump := function( U, p )
  926.     local   P;
  927.  
  928.     if not IsPrimeInt( p )  then
  929.         Error( "<p> must be a prime" );
  930.     else
  931.         P := U.operations.PRump( U, p );
  932.     fi;
  933.     return P;
  934.  
  935. end;
  936.  
  937. AgGroupOps.PRump := function( U, p )
  938.     local   i,  C,  P;
  939.  
  940.     # Start with the derived subgroup of <U> and add <p>-powers.
  941.     C := DerivedSubgroup( U );
  942.     P := List( FactorArg( U, C ).generators, x -> x ^ p );
  943.     return MergedIgs( U, C, P, true );
  944.  
  945. end;
  946.  
  947.  
  948. #############################################################################
  949. ##
  950. #F  CompositionSubgroup( <U>, <n> ) . . . . . . . . . .  composition subgroup
  951. ##
  952. CompositionSubgroup := function( U, n )
  953.     return U.operations.CompositionSubgroup( U, n );
  954. end;
  955.  
  956. AgGroupOps.CompositionSubgroup := function( U, n )
  957.     return CompositionSeries( U )[ n ];
  958. end;
  959.  
  960.  
  961. #############################################################################
  962. ##
  963.  
  964. #F  AddElementaryAbelianSeries( <U>, <S> )  . . . . . . . . . . . . . . local
  965. ##
  966. AddElementaryAbelianSeries := function( U, S )
  967.     local   i,  F;
  968.  
  969.     U.elementaryAbelianFactors := [];
  970.     for i  in [ 1 .. Length( S ) - 1 ]  do
  971.         F := CollectorlessFactorGroup( S[ i ], S[ i + 1 ] );
  972.         F.isAbelian := true;
  973.         F.isElementaryAbelian := true;
  974.         U.elementaryAbelianFactors[ i ] := F;
  975.     od;
  976.  
  977. end;
  978.  
  979.  
  980. #############################################################################
  981. ##
  982. #F  MeltElementaryAbelianSeriesAgGroup( <U> ) . . . . . .  melt series of <U>
  983. ##
  984. ##  Melt the elementary abelian series of <U>.
  985. ##
  986. MeltElementaryAbelianSeriesAgGroup := function( U )
  987.     local   P, S, L, i;
  988.  
  989.     L := ElementaryAbelianSeries( U );
  990.     P := AgSubgroup( U, [], true );
  991.     S := [ P ];
  992.     for i  in Reversed( [ 1 .. Length( L ) - 1 ] )  do
  993.         if not IsElementaryAbelian( L[ i ] / P )  then
  994.             P := L[ i + 1 ];
  995.             Add( S, P );
  996.         fi;
  997.     od;
  998.     Add( S, U );
  999.     AddElementaryAbelianSeries( U, Reversed( S ) );
  1000.  
  1001. end;
  1002.  
  1003.  
  1004. #############################################################################
  1005. ##
  1006. #F  ElementaryAbelianSeriesThrough( <list> )  . . . . . . . . . . . . . local
  1007. ##
  1008. ElementaryAbelianSeriesThrough := function( S )
  1009.     local   i,  N,  O,  I,  E,  L;
  1010.  
  1011.     # Typecheck arguments.
  1012.     if S[ Length( S ) ].generators <> []  then
  1013.         S := ShallowCopy( S );
  1014.         Add( S, AgSubgroup( S[1], [], true ) );
  1015.     fi;
  1016.  
  1017.     # Start with the elementay series of the first group of <S>.
  1018.     L := ElementaryAbelianSeries( S[ 1 ] );
  1019.     N := [ S[ 1 ] ];
  1020.     for i  in [ 2 .. Length( S ) - 1 ]  do
  1021.         O := L;
  1022.         L := [ S[ i ] ];
  1023.         for E  in O  do
  1024.             I := IntersectionSumAgGroup( E, S[ i ] );
  1025.             if not I.sum in N  then
  1026.                 Add( N, I.sum );
  1027.             fi;
  1028.             if not I.intersection in L  then
  1029.                 Add( L, I.intersection );
  1030.             fi;
  1031.         od;
  1032.     od;
  1033.     for E  in L  do
  1034.         if not E in N  then
  1035.             Add( N, E );
  1036.         fi;
  1037.     od;
  1038.  
  1039.     # return it.
  1040.     return N;
  1041.  
  1042. end;
  1043.  
  1044.  
  1045. #############################################################################
  1046. ##
  1047. #F  ElementaryAbelianSeries( <U> )  . . . . elementary abelian series as list
  1048. ##
  1049. AgGroupOps.ElementaryAbelianSeries := function( U )
  1050.  
  1051.     local   ds,             # derived subgroups
  1052.             series,         # Result
  1053.             new, cgrp, grp, # Sylow & agemo loop groups
  1054.             i, j,           # Loops
  1055.             g,
  1056.             tmp,
  1057.             diff,           # Reps of Comm factor group
  1058.             primes,         # Primes of factor group seen so far
  1059.             prime;          # Loop for primes
  1060.  
  1061.     # Check argument. Catch the trivial cases. Dispatch if <U> is a list.
  1062.     if IsList( U )  then
  1063.         return ElementaryAbelianSeriesThrough( U );
  1064.     elif U.generators = []  then
  1065.         return [ U ];
  1066.     fi;
  1067.  
  1068.     # If <U> has an entry <elementaryAbelianFactors> use it.
  1069.     if    IsBound( U.elementaryAbelianFactors )
  1070.        or ( IsParent( U ) and IsElementaryAbelianAgSeries( U ) )
  1071.     then
  1072.         series := [];
  1073.         for grp  in U.elementaryAbelianFactors  do
  1074.             Add( series, grp.factorNum );
  1075.         od;
  1076.         Add( series, grp.factorDen );
  1077.         return series;
  1078.     fi;
  1079.  
  1080.     # If  <U> is not the supergroup, get the elementary abelian series of its
  1081.     # supergroup and meet it with <U>.
  1082.     if not IsParent( U )  then
  1083.         series := ElementaryAbelianSeries( Parent( U ) );
  1084.         U := Normalized( U );
  1085.         new := [ U ];
  1086.         for i  in [ 2 .. Length( series ) ]  do
  1087.             tmp := new[ Length( new ) ];
  1088.             grp := NormalIntersection( series[ i ], tmp );
  1089.             if tmp <> grp  then
  1090.                 Add( new, grp );
  1091.             fi;
  1092.             if grp.generators = []  then
  1093.                 return new;
  1094.             fi;
  1095.         od;
  1096.         Error( "ElementaryAbelianSeries: inconsistent series" );
  1097.     fi;
  1098.  
  1099.     # Get  derived subgroups, we will chain down this series, and compute the
  1100.     # sylowsubgroups and the agemo's.
  1101.     ds     := DerivedSeries( U );
  1102.     series := [];
  1103.     for j  in [ 1 .. Length( ds ) - 1 ]  do
  1104.         new  := ds[ j ];
  1105.         cgrp := ds[ j+1 ];
  1106.         diff := FactorArg( new, cgrp ).generators;
  1107.  
  1108.         # Loop  over  all  primes,  if  P_1 ... P_n are the sylowgroups, this
  1109.         # will give P_i ... P_n + commutatorgroup
  1110.         primes := [];
  1111.         for g  in diff  do
  1112.             prime := RelativeOrderAgWord( g );
  1113.             if not ( prime in primes )  then Add( primes, prime );  fi;
  1114.         od;
  1115.         for prime  in primes  do
  1116.  
  1117.             # Agemo's
  1118.             repeat
  1119.                 grp  := new;
  1120.                 diff := List( diff, x -> x ^ prime );
  1121.                 new  := MergedIgs( U, cgrp, diff, true );
  1122.                 if new <> grp then
  1123.                     Add( series, grp );
  1124.                 fi;
  1125.             until new = grp;
  1126.         od;
  1127.     od;
  1128.  
  1129.     # Add trivial group
  1130.     Add( series, AgSubgroup( U, [], true ) );
  1131.  
  1132.     # This is an elementary abelian series
  1133.     AddElementaryAbelianSeries( U, series );
  1134.     return series;
  1135.  
  1136. end;
  1137.  
  1138.  
  1139. #############################################################################
  1140. ##
  1141. #F  RefinedSubnormalSeries( <L> ) . . . . . . . . . refine a subnormal series
  1142. ##
  1143. RefinedSubnormalSeries := function( L )
  1144.  
  1145.     local   N,            # New step in the new series
  1146.             S,          # Refined series
  1147.             ref,     # Flag
  1148.             D,            # generators
  1149.             z,       # Temporary
  1150.             i,  j;
  1151.  
  1152.     # Is series <L> already refined ?
  1153.     ref := true;
  1154.     for i  in [ 1 .. Length( L ) - 1 ]  do
  1155.         if Length( Igs(L[i]) ) <> Length( Igs(L[i+1]) )+1  then
  1156.             ref := false;
  1157.         fi;
  1158.     od;
  1159.     if ref  then
  1160.         return L;
  1161.     fi;
  1162.  
  1163.     # It is not refined, so refine it now.
  1164.     N := L[ Length( L ) ];
  1165.     S := [ N ];
  1166.     for i  in Reversed( [ 1 .. Length( L ) - 1 ] )  do
  1167.         D := FactorArg( L[ i ], N ).generators;
  1168.         for j  in Reversed( [ 2 .. Length( D ) ] )  do
  1169.             N := MergedIgs( L[i], N, [ D[j] ], true );
  1170.             Add( S, N );
  1171.         od;
  1172.         N := L[ i ];
  1173.         Add( S, N );
  1174.     od;
  1175.  
  1176.     # Reverse series and return.
  1177.     return Reversed( S );
  1178.  
  1179. end;
  1180.  
  1181.  
  1182. #############################################################################
  1183. ##
  1184.  
  1185. #F  AgOrbitStabilizer( <U>, <gens>, <p>, <op> ) . . . . . . . . . . . . orbit
  1186. ##
  1187. AgOrbitStabilizer := function( arg )
  1188.  
  1189.     local   O,          # complete Orbit
  1190.             prod,       # Auxiliary Variable to compute agword rep
  1191.             n,          # Auxiliary Variable to compute agword rep
  1192.             S,          # Agword stabilizer
  1193.             i, j, k,    # Loop
  1194.             G,
  1195.             len,
  1196.             l1, l2,
  1197.             V,          # Parameter <gens>
  1198.             U,          # Generating system of <U>
  1199.             p,          # Our start point
  1200.             o,          # relative order of next generators
  1201.             op,         # operation
  1202.             useOp,      # must we use a new operation (0=*, 1=^, 2=<op>)
  1203.             mi,
  1204.             np,         # New point
  1205.             r,          # Temp
  1206.             e;          # Temp
  1207.  
  1208.     InfoAgGroup1( "#I  OrbitStabilizer: ", "|<group>| = ",
  1209.                   StringPP( Size( arg[1] ) ), "\n" );
  1210.  
  1211.     # Catch trivial cases.
  1212.     if arg[ 1 ].generators = []  then
  1213.         InfoAgGroup1( "#I  OrbitStabilizer: returns ",
  1214.                   "|<orbit>| = 1, |<stab>| = 1 \n" );
  1215.         return rec( stabilizer := arg[ 1 ], orbit := [ arg[ 3 ] ] );
  1216.     fi;
  1217.  
  1218.     # Get generators.
  1219.     U := arg[ 1 ];
  1220.     G := Parent( U );
  1221.     U := Igs( U );
  1222.     V := arg[ 2 ];
  1223.     p := arg[ 3 ];
  1224.  
  1225.     # Get the operation, set flag <useOp> (0=*, 1=^, 2^<op>).
  1226.     if Length( arg ) = 4  then
  1227.         op := arg[ 4 ];
  1228.         if IsBool( op )  then
  1229.             if op  then
  1230.                 useOp := 0;
  1231.             else
  1232.                 useOp := 1;
  1233.             fi;
  1234.         elif op = OnRight  then
  1235.             useOp := 0;
  1236.         elif op = OnPoints then
  1237.             useOp := 1;
  1238.         else
  1239.             useOp := 2;
  1240.         fi;
  1241.     else
  1242.         useOp := 0;
  1243.     fi;
  1244.     if Length( U ) <> Length( V ) then
  1245.         Error( "not enough homomorphic generators for <U>" );
  1246.     fi;
  1247.  
  1248.     # Initialize all.
  1249.     O    := [ p ];
  1250.     prod := [ 1 ];
  1251.     n    := [ ];
  1252.     S    := [ ];
  1253.  
  1254.     # Start constructing orbit.
  1255.     for i  in Reversed( [ 1 .. Length( V ) ] )  do
  1256.         mi := V[ i ];
  1257.         if useOp = 0  then
  1258.             np := p * mi;
  1259.         elif useOp = 1  then
  1260.             np := p ^ mi;
  1261.         else
  1262.             np := op( p, mi );
  1263.         fi;
  1264.  
  1265.         # Is <np> really a new point or is it in <O>.
  1266.         j := Position( O, np );
  1267.  
  1268.         # Let's see if it is new (j = false).
  1269.         if j = false  then
  1270.             o := RelativeOrderAgWord( U[i] );
  1271.             Add( prod, prod[ Length( prod ) ] * o );
  1272.             Add( n, i );
  1273.             len := Length( O );
  1274.             if useOp = 0  then
  1275.                 l1 := 0;
  1276.                 O[ o * len ] := true;
  1277.                 for k  in [ 1 .. o - 1 ]  do
  1278.                     l2 := l1 + len;
  1279.                     for j  in [ 1 .. len ]  do
  1280.                         O[ j + l2 ] := O[ j + l1 ] * mi;
  1281.                     od;
  1282.                     l1 := l2;
  1283.                 od;
  1284.             elif useOp = 1  then
  1285.                 l1 := 0;
  1286.                 O[ o * len ] := true;
  1287.                 for k  in [ 1 .. o - 1 ]  do
  1288.                     l2 := l1 + len;
  1289.                     for j  in [ 1 .. len ]  do
  1290.                         O[ j + l2 ] := O[ j + l1 ] ^ mi;
  1291.                     od;
  1292.                     l1 := l2;
  1293.                 od;
  1294.             else
  1295.                 l1 := 0;
  1296.                 O[ o * len ] := true;
  1297.                 for k  in [ 1 .. o - 1 ]  do
  1298.                     l2 := l1 + len;
  1299.                     for j  in [ 1 .. len ]  do
  1300.                         O[ j + l2 ] := op( O[ j + l1 ], mi );
  1301.                     od;
  1302.                     l1 := l2;
  1303.                 od;
  1304.             fi;
  1305.         elif j = 1 then
  1306.             Add( S, U[i] );
  1307.         else
  1308.             r := G.identity;
  1309.             j := j - 1;
  1310.             len := Length( prod );
  1311.             for k  in [ 1 .. len - 1 ]  do
  1312.                 e := QuoInt( j, prod[ len - k ] );
  1313.                 r := U[ n[ len - k ] ] ^ e * r;
  1314.                 j := j mod prod[ len - k ];
  1315.             od;
  1316.             Add( S, U[i] * r ^ -1 );
  1317.         fi;
  1318.     od;
  1319.  
  1320.     # <S> is a reversed IGS.
  1321.     S := AgSubgroup( G, Reversed( S ), false );
  1322.  
  1323.     InfoAgGroup1( "#I  OrbitStabilizer: returns ", "|<orbit>| = ",
  1324.                   Length( O ), ", |<stab>| = ", StringPP(Size( S )), "\n" );
  1325.  
  1326.     return rec( stabilizer := S, orbit := O );
  1327.  
  1328. end;
  1329.  
  1330.  
  1331. #############################################################################
  1332. ##
  1333. #F  LinearOperation( <U>, <V>, <phi> )  . . . . . . . . . . lineare operation
  1334. ##
  1335. AgGroupOps.LinearOperation := function( U, V, phi )
  1336.     local   L,  B,  M;
  1337.  
  1338.     # Catch trivial cases.
  1339.     if U.generators = [] then
  1340.         return rec( images := [] );
  1341.     fi;
  1342.  
  1343.     # Ok, now compute matrix.
  1344.     B := Base( V );
  1345.     L := List( Igs( U ), x -> List( B, y -> phi( y, x ) ) );
  1346.     List( L, IsMat );
  1347.  
  1348.     M := Group( L, L[1]^0 );
  1349.     M.images := L;
  1350.     return M;
  1351.  
  1352. end;
  1353.  
  1354. LinearOperation := function( U, V, phi )
  1355.     return U.operations.LinearOperation( U, V, phi );
  1356. end;
  1357.  
  1358.  
  1359. #############################################################################
  1360. ##
  1361. #F  AffineOperationp( <G>, <V>, <phi>, <tau> )  . . . . . . . . . . affine op
  1362. ##
  1363. AgGroupOps.AffineOperation := function( U, V, phi, tau )
  1364.     local   i,  v,  m,  l,  one,  zero,  mats,  M,  B;
  1365.  
  1366.     # Catch trivial cases.
  1367.     U := Igs( U );
  1368.     if U = []  then
  1369.         return rec( images := [] );
  1370.     fi;
  1371.  
  1372.     B := Base( V );
  1373.     if B = []  then
  1374.         mats := List( U, x -> [ [ V.field.one ] ]);
  1375.     else
  1376.         one  := tau( U[ 1 ] )[ 1 ] ^ 0;
  1377.         zero := 0 * one;
  1378.  
  1379.         # First the linear operation.
  1380.         mats := List( U, x -> List( B, y -> phi( y, x ) ) );
  1381.         for m  in mats  do
  1382.             for l  in m  do
  1383.                 Add( l, zero );
  1384.             od;
  1385.         od;
  1386.         for i  in [ 1 .. Length( U ) ]  do
  1387.             v := tau( U[ i ] );
  1388.             Add( v, one );
  1389.             Add( mats[ i ], v );
  1390.         od;
  1391.         List( mats, IsMat );
  1392.     fi;
  1393.  
  1394.     M := Group( mats, mats[1]^0 );
  1395.     M.images := mats;
  1396.     return M;
  1397.  
  1398. end;
  1399.  
  1400. AffineOperation := function( U, V, phi, tau )
  1401.     return U.operations.AffineOperation( U, V, phi, tau );
  1402. end;
  1403.  
  1404.  
  1405. #############################################################################
  1406. ##
  1407. #F  Orbit( <U>, <pt>, <op> )  . . . . . . . . . . . . . . . orbit algorithmus
  1408. ##
  1409. AgGroupOps.Orbit := function( U, pt, op )
  1410.  
  1411.     # Catch trivial cases.
  1412.     if U.generators = []  then
  1413.         InfoAgGroup1( "#I  Orbit: |<group>| = 1\n#I  Orbit:",
  1414.                       " returns |<orbit>| = 1, |<stab>| = 1\n" );
  1415.         return [ pt ];
  1416.     fi;
  1417.  
  1418.     # Start algorithm using 'AgOrbitStabilizer'.
  1419.     return AgOrbitStabilizer( U, Igs( U ), pt, op ).orbit;
  1420.  
  1421. end;
  1422.  
  1423.  
  1424. #############################################################################
  1425. ##
  1426. #F  Stabilizer <U>, <pt>, <op> )  . . . .  . . . . . . stabilizer algorithmus
  1427. ##
  1428. AgGroupOps.Stabilizer := function( arg )
  1429.     local   U, pt, useOp, op, R, old, S, p, u, ui, i, j, k, l;
  1430.  
  1431.     U  := arg[ 1 ];
  1432.     pt := arg[ 2 ];
  1433.     op := arg[ 3 ];
  1434.     InfoAgGroup1("#I  Stabilizer: |<group>| = ",StringPP(Size(U)),"\n");
  1435.  
  1436.     # Catch trivial cases.
  1437.     if arg[ 1 ].generators = [] then
  1438.         InfoAgGroup1("#I  Stabilizer: returns |<orbit>|=1, |<stab>|=1\n");
  1439.         return arg[ 1 ];
  1440.     fi;
  1441.     useOp := op <> OnPoints;
  1442.  
  1443.     # Get setup.
  1444.     R := [ U.identity ];
  1445.     S := [];
  1446.  
  1447.     # Step up composition series.
  1448.     for u  in Reversed( Igs( U ) )  do
  1449.  
  1450.         # Let's see if we have a new rep.
  1451.         l  := Length( R );
  1452.         j  := 1;
  1453.         ui := u ^ -1;
  1454.         if useOp  then
  1455.             while j <= l and op( pt, ( R[ j ] * ui ) ) <> pt  do
  1456.                 j := j + 1;
  1457.             od;
  1458.         else
  1459.             while j <= l and pt ^ ( R[ j ] * ui ) <> pt  do
  1460.                 j := j + 1;
  1461.             od;
  1462.         fi;
  1463.  
  1464.         # If <j> > <l> then we have new rep.
  1465.         if j > l  then
  1466.             l   := Length( R );
  1467.             p   := RelativeOrderAgWord( u );
  1468.             old := ShallowCopy( R );
  1469.             for k  in [ 1 .. p - 1 ]  do
  1470.                 for i in [ 1 .. l ]  do
  1471.                     old[ i ] := u * old[ i ];
  1472.                 od;
  1473.                 Append( R, old );
  1474.             od;
  1475.         else
  1476.             Add( S, u * R[ j ] ^ -1 );
  1477.         fi;
  1478.     od;
  1479.  
  1480.     # Give some information.
  1481.     S := AgSubgroup( U,  Reversed( S ), false );
  1482.     InfoAgGroup1( "#I  Stabilizer: returns |<orbit>| = ",
  1483.                   Size( U ) / Size( S ), ", |<stab>| = ",
  1484.                   StringPP( Size( S ) ), "\n" );
  1485.     return S;
  1486.  
  1487. end;
  1488.  
  1489.  
  1490. #############################################################################
  1491. ##
  1492.  
  1493. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1494. ##
  1495. ## Local Variables:
  1496. ## mode:           outline
  1497. ## outline-regexp: "#F\\|#V\\|#E"
  1498. ## eval:           (hide-body)
  1499. ## End:
  1500. ##
  1501.