home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / aggroup.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  54.5 KB  |  1,717 lines
  1. #############################################################################
  2. ##
  3. #A  aggroup.g                   GAP library                      Frank Celler
  4. ##
  5. #A  @(#)$Id: aggroup.g,v 3.41 1993/01/18 18:44:40 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This  file  contains  all  functions  for  creating aggroups and changing
  10. ##  collectors. It also contains the functions for  converting  aggroups into
  11. ##  PermGroups and MatGroups.
  12. ##
  13. #H  $Log: aggroup.g,v $
  14. #H  Revision 3.41  1993/01/18  18:44:40  martin
  15. #H  added character table computation
  16. #H
  17. #H  Revision 3.40  1992/12/16  19:47:27  martin
  18. #H  replaced quoted record names with escaped ones
  19. #H
  20. #H  Revision 3.39  1992/10/13  15:18:10  martin
  21. #H  fixed 'AgGroupOps.SemidirectProduct', the images of <G> operate with '^'
  22. #H
  23. #H  Revision 3.38  1992/08/03  12:32:23  fceller
  24. #H  'RefinedAgSeries' now returns always a new group
  25. #H
  26. #H  Revision 3.37  1992/05/29  10:06:13  fceller
  27. #H  fixed bug in 'PermGroupAgGroup'
  28. #H
  29. #H  Revision 3.36  1992/04/07  12:53:37  fceller
  30. #H  changed comparison with '0'
  31. #H
  32. #H  Revision 3.35  1992/04/03  13:10:09  fceller
  33. #H  changed 'Shifted...' into 'Sifted...'
  34. #H
  35. #H  Revision 3.34  1992/03/30  07:47:09  fceller
  36. #H  changed 'Exponents' slightly.
  37. #H
  38. #H  Revision 3.33  1992/03/27  11:14:51  martin
  39. #H  changed mapping to general mapping and function to mapping
  40. #H
  41. #H  Revision 3.32  1992/03/26  15:14:33  martin
  42. #H  changed 'SemiDirectProduct' to 'SemidirectProduct'
  43. #H
  44. #H  Revision 3.31  1992/02/29  15:00:57  fceller
  45. #H  use 'MakeVecFFE'
  46. #H
  47. #H  Revision 3.30  1992/02/21  16:47:27  hbesche
  48. #H  renamed 'Word' to 'AbstractGenerator'
  49. #H
  50. #H  Revision 3.29  1992/02/21  14:02:02  fceller
  51. #H  'i' was undeclared in 'CollectorlessFactorGroup'.
  52. #H
  53. #H  Revision 3.28  1992/02/07  18:11:40  fceller
  54. #H  Initial GAP 3.1 release.
  55. #H
  56. #H  Revision 3.1  1991/05/06  21:26:46  fceller
  57. #H  Initial revision
  58. ##
  59.  
  60.  
  61. #############################################################################
  62. ##
  63. #F  InfoAgGroup1( <arg> ) . . . . . . . . . . . . . . . . package information
  64. #F  InfoAgGroup2( <arg> ) . . . . . . . . . . . . . package debug information
  65. ##
  66. if not IsBound( InfoAgGroup1 )  then InfoAgGroup1 := Ignore;  fi;
  67. if not IsBound( InfoAgGroup2 )  then InfoAgGroup2 := Ignore;  fi;
  68.  
  69.  
  70. #############################################################################
  71. ##
  72.  
  73. #V  AgGroupOps  . . . . . . . . . . . . . . . . . . aggroup operations record
  74. ##
  75. AgGroupOps := ShallowCopy( GroupOps );
  76.  
  77.  
  78. #############################################################################
  79. ##
  80. #F  AgGroupOps.\=  . . . . . . . . . . . . . . . . . . . . . . equality test
  81. ##
  82. AgGroupOps.\= := function( G, H )
  83.     local   isEql;
  84.     if     IsRec( G ) 
  85.        and IsRec( H )
  86.        and IsBound( G.isAgGroup )
  87.        and IsBound( H.isAgGroup )
  88.        and G.isAgGroup
  89.        and H.isAgGroup
  90.     then
  91.         if IsCompatibleAgWord( G.identity, H.identity )  then
  92.             isEql := Cgs( G ) = Cgs( H );
  93.         else
  94.             isEql := false;
  95.         fi;
  96.     else
  97.     isEql := GroupOps.\=( G, H );
  98.     fi;
  99.     return isEql;
  100. end;
  101.  
  102.  
  103. #############################################################################
  104. ##
  105. #F  AgGroupOps.\<  . . . . . . . . . . . . . . . . . . . . . . .  comparison
  106. ##
  107. AgGroupOps.\< := function( G, H )
  108.     local   isLess;
  109.     if IsAgGroup( G ) and IsAgGroup( H )  then
  110.         if IsCompatibleAgWord( G.identity, H.identity )  then
  111.            isLess := Reversed( Cgs(G) ) < Reversed( Cgs(H) );
  112.         else
  113.             isLess := G.identity < H.identity;
  114.         fi;
  115.     else
  116.     isLess := GroupOps.\<( G, H );
  117.     fi;
  118.     return isLess;
  119. end;
  120.  
  121.  
  122. #############################################################################
  123. ##
  124. #F  AgGroupOps.\/  . . . . . . . . . . . . . . . . . . . . . .  factor group
  125. ##
  126. AgGroupOps.\/ := function( G, N )
  127.  
  128.     if IsInt( N )  then
  129.         N := CompositionSubgroup( G, N );
  130.     fi;
  131.     return FactorGroup( G, N );
  132.  
  133. end;
  134.  
  135.  
  136. #############################################################################
  137. ##
  138. #F  AgGroupOps.\in . . . . . . . . . . . . . . . . . . . . . membership test
  139. ##
  140. ##  We use 'SiftedAgWord' in order to decide membership.
  141. ##
  142. AgGroupOps.\in := function( g, G )
  143.     return     IsCompatibleAgWord( G.identity, g )
  144.            and SiftedAgWord( G, g ) = G.identity;
  145. end;
  146.  
  147.  
  148. #############################################################################
  149. ##
  150. #F  AgGroupOps.Group( <U> ) . . . . . . . . . . . . . . create a parent group
  151. ##
  152. AgGroupOps.Group := function( U )
  153.     local   G;
  154.  
  155.     if Index( Parent( U ), U ) = 1  then
  156.         G := CopyAgGroup( Parent( U ) );
  157.         G.bijection := GroupHomomorphismByImages(G,U,G.cgs,Parent(U).cgs);
  158.         G.bijection.range := U;
  159.     else
  160.         G := U / TrivialSubgroup( U );
  161.         G.bijection := NaturalHomomorphism( U, G ) ^ -1;
  162.     fi;
  163.     return G;
  164.  
  165. end;
  166.  
  167.  
  168. #############################################################################
  169. ##
  170. #F  AgGroupOps.Subgroup( <G>, <gens> )  . . . .  construct ag subgroup record
  171. ##
  172. AgGroupOps.Subgroup := function( G, gens )
  173.     local   id;
  174.  
  175.     id := G.identity;
  176.     if IsBound( G.parent )  then
  177.         return rec( generators := Filtered( gens, x -> x<>id ),
  178.                     identity   := id,
  179.                    isDomain   := true,
  180.                     isGroup    := true,
  181.                     isAgGroup  := true,
  182.                     parent     := G.parent,
  183.                     operations := G.operations );
  184.     else
  185.         return rec( generators := Filtered( gens, x -> x<>id ),
  186.                     identity   := id,
  187.                     isDomain   := true,
  188.                     isGroup    := true,
  189.                     isAgGroup  := true,
  190.                     parent     := G,
  191.                     operations := G.operations );
  192.     fi;
  193.  
  194. end;
  195.  
  196.  
  197. #############################################################################
  198. ##
  199. #F  AgGroupOps.FpGroup( <U> ) . . . . . . . . . . presentation of an ag group
  200. ##
  201. AgGroupOps.FpGroup := function( arg )
  202.     local   U,  gens,  u,  F,  i,  j,  k,  v,  names,  l,  r;
  203.  
  204.     # Check trivial case.
  205.     U := arg[ 1 ];
  206.     if U.generators = []  then
  207.         F := Group( [], IdWord );
  208.         F.relators := [];
  209.         return F;
  210.     fi;
  211.  
  212.     # Get generators.
  213.     gens := Igs( U );
  214.  
  215.     # Try to find suitable names for this generators.
  216.     if Length( arg ) = 2 then
  217.         names := WordList( Length( gens ), arg[2] );
  218.     else
  219.         names := List( Sublist( InformationAgWord( gens[ 1 ] ).names,
  220.                        List( gens, DepthAgWord ) ), AbstractGenerator );
  221.     fi;
  222.  
  223.     # The presenation is a power/commutator presentation.
  224.     F := Group( names, IdWord );
  225.     F.relators := [];
  226.  
  227.     # At first the power-part of the presentation.
  228.     for i  in [ 1 .. Length( gens ) ]  do
  229.         l := F.generators[ i ] ^ RelativeOrderAgWord( gens[ i ] );
  230.         u := gens[ i ] ^ RelativeOrderAgWord( gens[ i ] );
  231.         v := U.operations.Exponents( U, u, Integers );
  232.         r := IdWord;
  233.         for k  in [ 1 .. Length(v) ]  do
  234.             if v[k] <> 0  then
  235.                 r := r * F.generators[k] ^ v[k];
  236.             fi;
  237.         od;
  238.         Add( F.relators, l / r );
  239.     od;
  240.  
  241.     # Now the commutator-part of the presenation.
  242.     for i  in [ 1 .. Length( gens ) ]  do
  243.         for j  in [ i + 1 .. Length( gens ) ]  do
  244.             l := Comm( F.generators[ j ], F.generators[ i ] );
  245.             u := Comm( gens[ j ], gens[ i ] );
  246.             v := U.operations.Exponents( U, u, Integers );
  247.             r := IdWord;
  248.             for k  in [ 1 .. Length(v) ]  do
  249.                 if v[k] <> 0  then
  250.                     r := r * F.generators[k] ^v[k];
  251.                 fi;
  252.             od;
  253.             Add( F.relators, l / r );
  254.         od;
  255.     od;
  256.  
  257.     # Return the presenation.
  258.     return F;
  259.  
  260. end;
  261.  
  262.  
  263. #############################################################################
  264. ##
  265. #F  AgGroupOps.Order( <D>, <g> )  . . . . . . . . . . . . . . .  order of <g>
  266. ##
  267. AgGroupOps.Order := function( D, g )
  268.     local   ord, id;
  269.  
  270.     # Raise <g> to n.th power, where n is the relative order of <g>.
  271.     ord := 1;
  272.     id  := D.identity;
  273.     while g <> id  do
  274.         ord := ord * RelativeOrderAgWord( g );
  275.         g   := g ^ RelativeOrderAgWord( g );
  276.     od;
  277.  
  278.     return ord;
  279.  
  280. end;
  281.  
  282.  
  283. #############################################################################
  284. ##
  285.  
  286. #F  AgSubgroup( <G>, <gens>, <flag> )    . . . . . . . . . . . . . ag subgroup
  287. ##
  288. AgSubgroup := function( G, gens, flag )
  289.  
  290.     if flag  then
  291.         if IsBound( G.cgs ) and not IsBound( G.igs ) and G.cgs = gens  then
  292.             return G;
  293.         fi;
  294.     else
  295.         if IsBound( G.igs ) and G.igs = gens  then
  296.             return G;
  297.         fi;
  298.     fi;
  299.     if IsBound( G.parent )  then
  300.         if flag  then
  301.             return rec( generators := gens,
  302.                         identity   := G.identity,
  303.                         cgs        := gens,
  304.                        isDomain   := true,
  305.                         isGroup    := true,
  306.                         isAgGroup  := true,
  307.                         parent     := G.parent,
  308.                         operations := G.operations );
  309.         else
  310.             return rec( generators := gens,
  311.                         identity   := G.identity,
  312.                         igs        := gens,
  313.                         isDomain   := true,
  314.                         isGroup    := true,
  315.                         isAgGroup  := true,
  316.                         parent     := G.parent,
  317.                         operations := G.operations );
  318.         fi;
  319.     else
  320.         if Length( gens ) = Length( G.cgs )  then
  321.             if flag  then
  322.                 return rec( generators := gens,
  323.                             identity   := G.identity,
  324.                             cgs        := gens,
  325.                            isDomain   := true,
  326.                             isGroup    := true,
  327.                             isAgGroup  := true,
  328.                             operations := G.operations );
  329.             else
  330.                 return rec( generators := gens,
  331.                             identity   := G.identity,
  332.                             cgs        := G.cgs,
  333.                             igs        := gens,
  334.                             isDomain   := true,
  335.                             isGroup    := true,
  336.                             isAgGroup  := true,
  337.                             operations := G.operations );
  338.             fi;
  339.         else
  340.             if flag  then
  341.                 return rec( generators := gens,
  342.                             identity   := G.identity,
  343.                             cgs        := gens,
  344.                             isDomain   := true,
  345.                             isGroup    := true,
  346.                             isAgGroup  := true,
  347.                             parent     := G,
  348.                             operations := G.operations );
  349.             else
  350.                 return rec( generators := gens,
  351.                             identity   := G.identity,
  352.                             igs        := gens,
  353.                             isDomain   := true,
  354.                             isGroup    := true,
  355.                             isAgGroup  := true,
  356.                             parent     := G,
  357.                             operations := G.operations );
  358.             fi;
  359.         fi;
  360.     fi;
  361.  
  362. end;
  363.  
  364.  
  365. #############################################################################
  366. ##
  367. #F  ChangeCollector( <G>, <name> )  . . . . . . . change collector of aggroup
  368. ##
  369. ChangeCollector := function( arg )
  370.     local   G;
  371.  
  372.     # Check the arguments.
  373.     if    Length( arg ) < 2
  374.        or Length( arg ) > 3
  375.        or not IsAgGroup( arg[ 1 ] )
  376.        or not IsString( arg[ 2 ] )
  377.        or ( Length( arg ) = 3 and not IsInt( arg[ 3 ] ) )
  378.     then
  379.         Error( "usage: ChangeCollector( <G>, <collector>, [<n>] )" );
  380.     fi;
  381.     G := arg[ 1 ];
  382.     if not IsParent( G )  then
  383.         Error( "<G> must be a parent group" );
  384.     fi;
  385.  
  386.     # Change collector using 'SetCollectorAgWord'.
  387.     if Length( arg ) = 2  then
  388.        SetCollectorAgWord( G.identity, arg[ 2 ] );
  389.     else
  390.        SetCollectorAgWord( G.identity, arg[ 2 ], arg[ 3 ] );
  391.     fi;
  392.  
  393. end;
  394.  
  395.  
  396. #############################################################################
  397. ##
  398. #F  RefinedAgSeries( <G> )  . . . . . . . . . . . . . aggroup with PAG-system
  399. ##
  400. RefinedAgSeries := function( G )
  401.     local   F, idx, gens, new, names, facs, prods, len, wrds, coeffs, map,
  402.             i, j;
  403.  
  404.     # Check the arguments.
  405.     if not IsAgGroup( G )  then
  406.         Error( "usage: RefinedAgSeries( <G> )" );
  407.     elif not IsParent( G )  then
  408.         Error( "<G> must be the parent group" );
  409.     elif G.generators = []  then  
  410.         return G;
  411.     fi;
  412.  
  413.     # Get  the  generators  of <G> and names of those generators. Make a list
  414.     # of  lists  of  the factors of the indices. Concatenate this list to get
  415.     # the new indices.
  416.     gens  := G.generators;
  417.     names := InformationAgWord( gens[ 1 ] ).names;
  418.     idx   := List( gens, RelativeOrderAgWord );
  419.     facs  := List( idx, Factors );
  420.     idx   := Concatenation( facs );
  421.  
  422.     # If there are no composite numbers, return <G>.
  423.     # if Length( Filtered( facs, x -> Length( x ) > 1 ) ) = 0  then
  424.     #     return G;
  425.     # fi;
  426.  
  427.     # Construct the generators  If the relative  order of  a generator  is  a
  428.     # prime, do not change the name.   Otherwise add "_i"  to the name, for i
  429.     # from 1 upto the number of factors.
  430.     wrds := [];
  431.     for i  in [ 1 .. Length( facs ) ]  do
  432.         if Length( facs[ i ] ) = 1  then
  433.             Add( wrds, AbstractGenerator( names[ i ] ) );
  434.         else
  435.             Append( wrds, WordList( Length( facs[i] ), names[i] ) );
  436.         fi;
  437.     od;
  438.  
  439.     # Make the products  of  the factors  of   <facs> and  a list  of the new
  440.     # generators (that are the powers of those products).
  441.     prods := List( facs, x -> List( [ 1 .. Length( x ) ], y ->
  442.                    Product( Sublist( x, [ 1 .. y-1 ] ) ) ) );
  443.     new := [];
  444.     for i  in [ 1 .. Length( prods ) ]  do
  445.         Append( new, List( prods[ i ], x -> gens[ i ] ^ x ) );
  446.     od;
  447.     len := Length( new );
  448.  
  449.     # 'coeffs' takes the products and a number and returns the coeffs need to
  450.     # express this number in the product.
  451.     coeffs := function( ps, n )
  452.         local     c,  x;
  453.         c := [];
  454.         for x  in Reversed( ps )  do
  455.             Add( c, QuoInt( n, x ) );
  456.             n := n mod x;
  457.         od;
  458.         return Reversed( c );
  459.     end;
  460.  
  461.     # 'map' takes an agwords an expresses its in the new words of <wrds>.
  462.     map := function( a )
  463.         local     L;
  464.         L := ExponentsAgWord( a );
  465.         L := List( [ 1 .. Length( L ) ], x -> coeffs( prods[ x ], L[ x ] ) );
  466.         L := Concatenation( L );
  467.         return Product( [ 1 .. len ], x -> wrds[ x ] ^ L[ x ] );
  468.     end;
  469.  
  470.     # Now we can construct the new power/commutator presentation.
  471.     F := rec( generators := wrds,  relators := [] );
  472.     for i  in [ 1 .. len ]  do
  473.         Add( F.relators, wrds[i]^idx[i] / map( new[i]^idx[i] ) );
  474.     od;
  475.     for i  in [ 1 .. len - 1 ]  do
  476.         for j  in [ i + 1 .. len ]  do
  477.             Add(F.relators, Comm(wrds[j],wrds[i])/map(Comm(new[j],new[i])));
  478.         od;
  479.     od;
  480.     return AgGroupFpGroup( F );
  481.  
  482. end;
  483.  
  484.  
  485. #############################################################################
  486. ##
  487. #F  SiftedAgWord( <U>, <g> )  . . . . . remainder of shifting <g> through <U>
  488. ##
  489. SiftedAgWord := function( U, g )
  490.  
  491.     # Make sure that <U> has 'shiftInfo'.
  492.     if  not IsBound( U.shiftInfo )  then
  493.         U.operations.AddShiftInfo( U );
  494.     fi;
  495.  
  496.     # Use the suggested method in order to shift <g> through <U>.
  497.     if U.shiftInfo.method = 7  then
  498.  
  499.         # <U> is a trivial factorgroup or subgroup.
  500.         if IsBound( U.isFactorArg ) and U.isfactorArg  then
  501.             return SiftedAgWord( U.factorDen, g );
  502.         else
  503.             return g;
  504.         fi;
  505.     elif U.shiftInfo.method = 4  then
  506.  
  507.         # <U> is the supergroup.
  508.         return U.identity;
  509.     elif U.shiftInfo.method = 5  or U.shiftInfo.method = 1  then
  510.  
  511.         # <U> is a composition subgroup.
  512.         if DepthAgWord( g ) < U.shiftInfo.first  then
  513.             return g;
  514.         else
  515.             return U.identity;
  516.         fi;
  517.     elif U.shiftInfo.method = 6  then
  518.  
  519.         # <U> is no composition subgroup.
  520.         while g <> U.identity  do
  521.             if IsBound( U.shiftInfo.depths[ DepthAgWord( g ) ] )  then
  522.                 g := ReducedAgWord( g, U.shiftInfo.gens[ U.shiftInfo.depths[
  523.                                     DepthAgWord( g ) ] ] );
  524.             else
  525.                 return g;
  526.             fi;
  527.         od;
  528.         return g;
  529.     elif U.shiftInfo.method = 2 or U.shiftInfo.method = 3  then
  530.  
  531.         # <U> is a factorgroup.
  532.         while g <> U.identity  do
  533.             if not IsBound( U.shiftInfo.depths[ DepthAgWord( g ) ] )  then
  534.                 return g;
  535.             elif U.shiftInfo.depths[ DepthAgWord( g ) ] < 0  then
  536.                 g := ReducedAgWord( g, U.shiftInfo.subs[ -U.shiftInfo.depths[
  537.                                     DepthAgWord( g ) ] ] );
  538.             else
  539.                 g := ReducedAgWord( g, U.shiftInfo.gens[ U.shiftInfo.depths[
  540.                                     DepthAgWord( g ) ] ] );
  541.             fi;
  542.         od;
  543.         return g;
  544.     else
  545.  
  546.        # Something is wrong.
  547.        Error( "ShiftAgWord: unkown method ", U.shiftInfo.method,
  548.               " (internal error)" );
  549.     fi;
  550.  
  551. end;
  552.  
  553.  
  554. #############################################################################
  555. ##
  556. #F  Exponents( <U>, <u> ) . . . . . . . . . . . exponent vector of <u> in <U>
  557. ##
  558. Exponents := function( arg )
  559.     if Length(arg) = 2  then
  560.         return arg[1].operations.Exponents( arg[1], arg[2], Integers );
  561.     else
  562.         return arg[1].operations.Exponents( arg[1], arg[2], arg[3] );
  563.     fi;
  564. end;
  565.  
  566. AgGroupOps.Exponents := function( U, u, F )
  567.     local   exps, tmp, dep;
  568.  
  569.     # Make sure that <U> has 'shiftInfo'.
  570.     if  not IsBound( U.shiftInfo )  then
  571.         U.operations.AddShiftInfo( U );
  572.     fi;
  573.  
  574.     # Use the suggested method in order to compute the exponent vector.
  575.     if u = U.identity  then
  576.         exps := ShallowCopy( U.shiftInfo.list );
  577.     elif U.shiftInfo.method = 7  then
  578.         return [];
  579.     elif U.shiftInfo.method = 4
  580.         or U.shiftInfo.method = 5
  581.         or U.shiftInfo.method = 1
  582.     then
  583.         if IsFFE( F.one )  then
  584.             return ExponentsAgWord( u,
  585.                                     U.shiftInfo.first,
  586.                                     U.shiftInfo.last,
  587.                                     F.root );
  588.         elif F.one = 1  then
  589.             return ExponentsAgWord( u,
  590.                                     U.shiftInfo.first,
  591.                                     U.shiftInfo.last );
  592.         else
  593.             return ExponentsAgWord( u,
  594.                                     U.shiftInfo.first,
  595.                                     U.shiftInfo.last ) * F.one;
  596.         fi;
  597.     elif U.shiftInfo.method = 6  then
  598.         exps := ShallowCopy( U.shiftInfo.list );
  599.         while u <> U.identity  do
  600.             dep := U.shiftInfo.depths[ DepthAgWord( u ) ];
  601.             tmp := LeadingExponentAgWord( u )
  602.                      / LeadingExponentAgWord( U.shiftInfo.gens[ dep ] )
  603.                    mod RelativeOrderAgWord( u );
  604.             exps[ dep ] := tmp;
  605.             u := U.shiftInfo.gens[ dep ] ^ tmp mod u;
  606.         od;
  607.     elif U.shiftInfo.method = 3  then
  608.         exps := ShallowCopy( U.shiftInfo.list );
  609.         while u <> U.identity  do
  610.             dep := U.shiftInfo.depths[ DepthAgWord( u ) ];
  611.             if dep < 0  then
  612.                 u := ReducedAgWord( u, U.shiftInfo.subs[ -dep ] );
  613.             else
  614.                 tmp := LeadingExponentAgWord( u )
  615.                          / LeadingExponentAgWord( U.shiftInfo.gens[ dep ] )
  616.                        mod RelativeOrderAgWord( u );
  617.                 exps[ U.shiftInfo.factorDepths[ DepthAgWord( u ) ] ] := tmp;
  618.                 u := U.shiftInfo.gens[ dep ] ^ tmp mod u;
  619.             fi;
  620.         od;
  621.     elif U.shiftInfo.method = 2  then
  622.         exps := ShallowCopy( U.shiftInfo.list );
  623.         while u <> U.identity and DepthAgWord( u ) <= U.shiftInfo.last  do
  624.             dep := U.shiftInfo.depths[ DepthAgWord( u ) ];
  625.             tmp := LeadingExponentAgWord( u )
  626.                      / LeadingExponentAgWord( U.shiftInfo.gens[ dep ] )
  627.                    mod RelativeOrderAgWord( u );
  628.             exps[ dep ] := tmp;
  629.             u := U.shiftInfo.gens[ dep ] ^ tmp mod u;
  630.         od;
  631.     else
  632.         Error( "Exponents: unkown method ", U.shiftInfo.method );
  633.     fi;
  634.  
  635.     # If the <U> is elementary abelian group with a field, make a vector.
  636.     if IsFFE( F.one )  then
  637.         return MakeVecFFE( exps, F.one );
  638.     elif F.one = 1  then
  639.         return exps;
  640.     else
  641.         return exps * F.one;
  642.     fi;
  643.  
  644. end;
  645.  
  646.  
  647. #############################################################################
  648. ##
  649. #F  FactorArg( <U>, <N> ) . . . . . . . . . . . . . .  factor argument record
  650. #V  FactorArgOps  . . . . . . . . . . . . . . . . . . . . factor argument ops
  651. ##
  652. FactorArgOps := rec();
  653.  
  654. FactorArg := function( U, N )
  655.     local   G, depths;
  656.  
  657.     if not IsBound( FactorArgOps.Parent )  then
  658.         FactorArgOps.Parent       := AgGroupOps.Parent;
  659.         FactorArgOps.IsParent     := AgGroupOps.IsParent;
  660.         FactorArgOps.AddShiftInfo := AgGroupOps.AddShiftInfo;
  661.         FactorArgOps.Exponents    := AgGroupOps.Exponents;
  662.     fi;
  663.     G := rec( factorNum   := U,
  664.               factorDen   := N,
  665.               identity    := U.identity,
  666.               isFactorArg := true,
  667.               operations  := FactorArgOps );
  668.     depths := Set( List( Igs( N ), DepthAgWord ) );
  669.     G.generators := Filtered(Igs(U), x->not DepthAgWord(x) in depths);
  670.  
  671.     return G;
  672.  
  673. end;
  674.  
  675. AgGroupOps.\mod := FactorArg;
  676.  
  677.  
  678. #############################################################################
  679. ##
  680.  
  681. #F  AgGroupPcp( <P> ) . . . . . . . . . . . . . . convert a pcp into ag group
  682. ##
  683. AgGroupPcp := function( P )
  684.     local   G;
  685.  
  686.     G := AgPcp( P );
  687.     return Group( G.generators, G.identity );
  688. end;
  689.  
  690.  
  691. #############################################################################
  692. ##
  693. #F  MatGroupAgGroup( <G>, <M> ) . . . . . . . . . . . . . . . .  matrix group
  694. ##
  695. MatGroupAgGroup := function( G, M )
  696.     local   V,  base,  p;
  697.  
  698.     # Typecheck arguments
  699.     if not IsAgGroup( G ) or not IsAgGroup( M )  then
  700.         Error( "usage: MatGroupAgGroup( <G>, <M> )" );
  701.     elif M.generators = []  then
  702.         Error( "<M> must not be trivial" );
  703.     elif not IsElementaryAbelian( M )  then
  704.         Error( "<M> must be elementary abelian" );
  705.     elif not IsNormal( G, M )  then
  706.         Error( "<G> must normalize <M>" );
  707.     fi;
  708.  
  709.     # Get the prime, construct the matrices.
  710.     base := Igs( M );
  711.     p := RelativeOrderAgWord( base[ 1 ] );
  712.     M := ShallowCopy( M );
  713.     M.field := GF( p );
  714.     V := rec( isDomain := true, base := base, field := M.field );
  715.     return LinearOperation( G, V, function( x, a ) return
  716.                                    M.operations.Exponents( M, x^a, M.field );
  717.                                   end );
  718.  
  719. end;
  720.  
  721.  
  722. #############################################################################
  723. ##
  724. #F  PermGroupAgGroup( <G>, <U> )  . . . . . . . . . . . . . permutation group
  725. ##
  726. PermGroupAgGroup := function( G, U )
  727.     local   C;
  728.  
  729.     # Typecheck arguments
  730.     if not IsAgGroup( G ) or not IsAgGroup( U )  then
  731.         Error( "usage: PermGroupAgGroup( <G>, <U> )" );
  732.     elif not IsSubgroup( G, U )  then
  733.         Error( "<U> must be a subgroup of <G>" );
  734.     fi;
  735.  
  736.     # Construct cosets.
  737.     C := G.operations.Cosets( G, U );
  738.  
  739.     # Return permutation group.
  740.     return Group( List( Igs( G ), x -> PermList( List(
  741.                         C, p -> Position( C, p*x ) ) ) ), () );
  742. end;
  743.  
  744.  
  745. #############################################################################
  746. ##
  747. #F  AgGroupFpGroup( <P> ) . . . . . . . . . . . . . . . . . create an aggroup
  748. ##
  749. AgGroupFpGroup := function( P )
  750.     local   G,  i;
  751.  
  752.     # Initialize  the  aggroup using the internal function 'AgFpGroup'. If an
  753.     # error  is  detected  in  the  argument <P>, this function will raise an
  754.     # error.
  755.     G := AgFpGroup( P );
  756.     G.isDomain  := true;
  757.     G.isGroup   := true;
  758.     G.isAgGroup := true;
  759.  
  760.     # This  group  contains  a  canonical generating system, so it is already
  761.     # normalized.
  762.     G.cgs := G.generators;
  763.  
  764.     # Add the operations record for an aggroup.
  765.     G.operations := AgGroupOps;
  766.  
  767.     # Check if the indices are primes.
  768.     if ForAny( G.generators, x->not IsPrimeInt(RelativeOrderAgWord(x)))  then
  769.        Print("#W  AgGroupFpGroup: composite index, use 'RefinedAgSeries'\n");
  770.     fi;
  771.  
  772.     # Add <G>.n
  773.     for i  in [ 1 .. Length( G.generators ) ]  do
  774.         G.( String( i ) ) := G.generators[ i ];
  775.     od;
  776.  
  777.     # That's it.
  778.     return G;
  779.  
  780. end;
  781.  
  782.  
  783. #############################################################################
  784. ##
  785.  
  786. #F  DirectProductAgGroupOps . . . . . . . .  ops for embedding and projection
  787. ##
  788. DirectProductAgGroupOps := rec(); # <AgGroupOps>
  789.  
  790.  
  791. #############################################################################
  792. ##
  793. #F  DirectProductAgGroupOps.Embedding( <G>, <D>, <i> )    . . . . . . embedding
  794. ##
  795. DirectProductAgGroupOps.Embedding := function( arg )
  796.     local   G,  D,  C,  i,  k,  emb;
  797.  
  798.     # get arguments
  799.     G := arg[1];
  800.     D := arg[2];
  801.     if Length( arg ) = 2  then
  802.         i := 0;
  803.         for k  in [ 1 .. Length( D.groups ) ]  do
  804.         C := D.groups[k];
  805.         if Parent( C ) = Parent( G ) and IsSubgroup( C, G )  then
  806.         if i <> 0  then
  807.             Error( "<G> appears in several components of <D>" );
  808.         fi;
  809.         i := k;
  810.         fi;
  811.     od;
  812.     if i = 0  then
  813.         Error( "<G> is no component of <D>" );
  814.     fi;
  815.     else
  816.     i := arg[3];
  817.     fi;
  818.  
  819.     # either <G> is an element of <D>.groups or we must restrict
  820.     emb := D.embeddings[i];
  821.     if G <> D.groups[i]  then
  822.     emb := GroupHomomorphismByImages( G, D, Cgs( G ), List( Cgs( G ),
  823.                                       x -> Image( emb, x ) ) );
  824.     emb.isMapping := true;
  825.     fi;
  826.     return emb;
  827.  
  828. end;
  829.  
  830. #############################################################################
  831. ##
  832. #F  DirectProductAgGroupOps.Projection( <G>, <D>, <i> )    . . . . .  projection
  833. ##
  834. DirectProductAgGroupOps.Projection := function( arg )
  835.     local   G,  D,  i,  k;
  836.  
  837.     # get arguments
  838.     D := arg[1];
  839.     G := arg[2];
  840.     if Length( arg ) = 2  then
  841.         i := 0;
  842.         for k  in [ 1 .. Length( D.groups ) ]  do
  843.         if G = D.groups[k]  then
  844.         if i <> 0  then
  845.             Error( "<G> appears in several components of <D>" );
  846.         fi;
  847.         i := k;
  848.         fi;
  849.     od;
  850.     if i = 0  then
  851.         Error( "<G> is no component of <D>" );
  852.     fi;
  853.     else
  854.     i := arg[3];
  855.     fi;
  856.  
  857.     # return projection
  858.     return D.projections[i];
  859.  
  860. end;
  861.  
  862.  
  863. #############################################################################
  864. ##
  865. #F  AgGroupOps.DirectProduct( <L> )   . . . . . . . . . . . .  direct product
  866. ##
  867. AgGroupOps.DirectProduct := function( L )
  868.     local   x,  F,  gens,  rels,  D,  k,  l,  r,  i;
  869.  
  870.     # All groups must be ag groups.
  871.     if not ForAll( L, z -> IsList( z ) or IsAgGroup( z ) ) then
  872.         return GroupOps.DirectProduct( L );
  873.     fi;
  874.  
  875.     # Use 'FpGroup' to get the presentation.
  876.     D := [];
  877.     r := [];
  878.     i := 1;
  879.     gens := [];
  880.     rels := [];
  881.     for x  in L  do
  882.         if IsList( x )  then
  883.             F := x[ 1 ].operations.FpGroup( x[ 1 ], x[ 2 ] );
  884.             Add( D, CopyAgGroup( x[ 1 ] ) );
  885.         else
  886.             F := FpGroup( x );
  887.             Add( D, CopyAgGroup( x ) );
  888.         fi;
  889.         Append( gens, F.generators );
  890.         Append( rels, F.relators );
  891.         Add( r, i );
  892.         i := i + Length( F.generators );
  893.     od;
  894.     Add( r, i );
  895.  
  896.     # Construct the ag group.
  897.     F := AgGroupFpGroup( rec( generators := gens, relators := rels ) );
  898.     F.groups := D;
  899.     F.operations := DirectProductAgGroupOps;
  900.  
  901.     # Construct the embeddings.
  902.     F.embeddings := [];
  903.     for k  in [ 1 .. Length( D ) ]  do
  904.     F.embeddings[k] := GroupHomomorphismByImages( D[k], F, Igs(D[k]),
  905.                    Sublist(F.generators, [r[k] .. r[k+1]-1]) );
  906.     od;
  907.  
  908.     # Construct the projections.
  909.     F.projections := [];
  910.     for k  in [ 1 .. Length( D ) ]  do
  911.     gens := [];
  912.     for l  in [ 1 .. Length( D ) ]  do
  913.         if l = k  then
  914.         Append( gens, Igs( D[l] ) );
  915.         else
  916.         Append( gens, List( Igs( D[l] ), x -> D[k].identity ) );
  917.         fi;
  918.     od;
  919.     F.projections[k] := GroupHomomorphismByImages(F, D[k], Cgs(F), gens);
  920.     od;
  921.  
  922.     # Return the direct product.
  923.     return F;
  924.  
  925. end;
  926.  
  927.  
  928. #############################################################################
  929. ##
  930.  
  931. #F  SemidirectProduct( <G>, <a>, <H> )    . . . . . . . . .  semidirect product
  932. ##
  933. AgGroupOps.SemidirectProduct := function( G, a, H )
  934.     local   F, FG, FH, gensG, gensH, abstG, abstH, lenH, m, v, r, l, i, j, k;
  935.  
  936.     # Both <G> and <H> must be ag groups.
  937.     if not IsAgGroup( H ) or not IsAgGroup( G )  then
  938.         return GroupOps.SemidirectProduct( G, a, H );
  939.     fi;
  940.         
  941.     # Normalize and copy <G> and <H>.
  942.     G := Normalized( G );
  943.     H := Normalized( H );
  944.     Unbind( G.field );
  945.     Unbind( H.field );
  946.     FG := G.operations.FpGroup( G, "g" );
  947.     FH := H.operations.FpGroup( H, "h" );
  948.  
  949.     # Construct the free direct product.
  950.     F  := rec( generators := Concatenation( FG.generators, FH.generators ),
  951.                relators   := Concatenation( FG.relators,   FH.relators ) );
  952.  
  953.     # Add the operation of <G> on <H> using <a>.
  954.     gensG := Igs( G );
  955.     abstG := FG.generators;
  956.     gensH := Igs( H );
  957.     abstH := FH.generators;
  958.     lenH  := Length( gensH );
  959.     for i  in [ 1 .. Length( gensG ) ]  do
  960.         for j  in [ 1 .. lenH ]  do
  961.             l := abstH[ j ] ^ abstG[ i ];
  962.             m := gensH[j] ^ Image( a, gensG[i] );
  963.             v := H.operations.Exponents( H, m, Integers );
  964.             r := IdWord;
  965.             for k  in [ 1 .. lenH ]  do
  966.                 if v[k] <> 0  then
  967.                     r := r * abstH[k] ^ v[k];
  968.                 fi;
  969.             od;
  970.             Add( F.relators, l / r );
  971.         od;
  972.     od;
  973.  
  974.     # Construct the ag group and the embeddings and projections.
  975.     F := AgGroupFpGroup( F );
  976.     F.embeddings := [];
  977.     l := Sublist( F.generators, [ 1 .. Length(Igs(G)) ] );
  978.     F.embeddings[1] := GroupHomomorphismByImages( G, F, Igs( G ), l );
  979.     l := Sublist( F.generators, [ Length(Igs(G))+1 .. Length(Igs(F)) ] );
  980.     F.embeddings[2] := GroupHomomorphismByImages( H, F, Igs( H ), l );
  981.     F.projections := [];
  982.     l := Concatenation( Igs(G), List( Igs(H), x -> G.identity ) );
  983.     F.projections[1] := GroupHomomorphismByImages( F, G, Igs(F), l );
  984.     l := Concatenation( List( Igs(G), x -> H.identity ), Igs(H) );
  985.     F.projections[2] := GroupHomomorphismByImages( F, H, Igs(F), l );
  986.     return F;
  987.  
  988. end;
  989.  
  990.  
  991. #############################################################################
  992. ##
  993. #F  SemidirectMatProduct( <G>, <a> )  . . . semi direct product with matrices
  994. ##
  995. SemidirectMatProduct := function( G, a )
  996.     local   FG, dim, p, abstM, F, gensG, abstG, i, j, k, l, r, mat, R;
  997.  
  998.     # Normalize and copy <G>.
  999.     G := Normalized( G );
  1000.     Unbind( G.field );
  1001.     FG := G.operations.FpGroup( G, "g" );
  1002.  
  1003.     # <a>  is  homomorphism  into a  matrix  group. Get   the  dimension  of
  1004.     # the underlying vectorspace.
  1005.     R     := a.range;
  1006.     dim   := Length( R.identity[ 1 ] );
  1007.     p     := CharFFE( R.generators[1][1][1] );
  1008.     abstM := WordList( dim, "h" );
  1009.  
  1010.     # Construct the free direct product.
  1011.     F := rec( generators := Concatenation( FG.generators, abstM ),
  1012.               relators   := Concatenation( FG.relators,
  1013.                                            List( abstM, x -> x ^ p ) ) );
  1014.  
  1015.     # Add the operation of <G> on the vectorspace.
  1016.     gensG := Igs( G );
  1017.     abstG := FG.generators;
  1018.     for i  in [ 1 .. Length( gensG ) ]  do
  1019.         mat := Image( a, gensG[ i ] );
  1020.         for j  in [ 1 .. Length( mat ) ]  do
  1021.             l := abstM[ j ] ^ abstG[ i ];
  1022.             r := IdWord;
  1023.             for k  in [ 1 .. Length( mat[ j ] ) ]  do
  1024.                 if LogVecFFE( mat[j], k ) <> false  then
  1025.                     r := r * abstM[k] ^ Int(mat[j][k]);
  1026.                 fi;
  1027.             od;
  1028.             Add( F.relators, l / r );
  1029.         od;
  1030.     od;
  1031.     return AgGroupFpGroup( F );
  1032.  
  1033. end;
  1034.  
  1035.  
  1036. #############################################################################
  1037. ##
  1038.  
  1039. #F  WreathProduct( <G>, <H>, <f> )  . . . . . . . . . . . . .  wreath product
  1040. ##
  1041. AgGroupOps.WreathProduct := function( G, H, f )
  1042.     local   i, j, k, lenG, lenH, FG, FH, deg, gens, rels, E, b, bi, a, aij;
  1043.  
  1044.     # Both <H> and <G> must be ag groups.
  1045.     if not IsAgGroup( H ) or not IsAgGroup( G )  then
  1046.         return GroupOps.WreathProduct( G, H, f );
  1047.     fi;
  1048.     G := Normalized( G );
  1049.     H := Normalized( H );
  1050.     Unbind( G.field );
  1051.     Unbind( H.field );
  1052.  
  1053.     # Get degree of range of <f>.
  1054.     deg := PermGroupOps.LargestMovedPoint( Image( f, H ) );
  1055.  
  1056.     # Construct enough generators for the wreath product.
  1057.     lenG := Length( Igs( G ) );
  1058.     lenH := Length( Igs( H ) );
  1059.  
  1060.     # Get the presentation for both groups.
  1061.     FG := G.operations.FpGroup( G, "x" );
  1062.     FH := G.operations.FpGroup( H, "h" );
  1063.  
  1064.     # <bi> are the abstract generators for the complement isomorph <H>.
  1065.     bi := FH.generators;
  1066.     b  := Igs( H );
  1067.  
  1068.     # <aij> are the abstract gens for the <deg> subgroups ismorph to <G>.
  1069.     a   := FG.generators;
  1070.     aij := List( [ 1 .. deg ], y -> List( [ 1 .. lenG ], x -> AbstractGenerator(
  1071.            ConcatenationString( "n", String( y ), "_", String( x ) ) ) ) );
  1072.  
  1073.     # Make a list of all generators.
  1074.     gens := Concatenation( bi, Iterated( aij, Concatenation ) );
  1075.  
  1076.     # Start with the relators for <H>.
  1077.     rels := FH.relators;
  1078.  
  1079.     # Add the relators of <G> <deg> times.
  1080.     for i  in [ 1 .. deg ]  do
  1081.         Append( rels, List( FG.relators, x -> MappedWord( x, a, aij[i]) ) );
  1082.     od;
  1083.  
  1084.     # At last the operation of <H> on the <deg> <G>s.
  1085.     for i  in [ 1 .. lenH ]  do
  1086.         for j  in [ 1 .. deg ]  do
  1087.             for k  in [ 1 .. lenG ]  do
  1088.                 Add( rels, aij[j][k] ^ bi[i]/aij[j^(Image(f,b[i]))][k] );
  1089.             od;
  1090.         od;
  1091.     od;
  1092.  
  1093.     # Return an ag group.
  1094.     return AgGroupFpGroup( rec( generators := gens, relators := rels ) );
  1095.  
  1096. end;
  1097.  
  1098.  
  1099. #############################################################################
  1100. ##
  1101.  
  1102. #F  CollectorlessFactorGroup( <U>, <N> )  . . . . . . . . . . new factorgroup
  1103. ##
  1104. CollectorlessFactorGroup := function( U, N )
  1105.     local   G,  i;
  1106.  
  1107.     G := U.operations.CollectorlessFactorGroup( U, N );
  1108.  
  1109.     # Add generators and <U> and <N>.
  1110.     G.factorNum := U;
  1111.     G.factorDen := N;
  1112.     for i  in [ 1 .. Length( G.generators ) ]  do
  1113.         G.( i ) := G.generators[ i ];
  1114.     od;
  1115.  
  1116.     # return the group
  1117.     return G;
  1118.  
  1119. end;
  1120.  
  1121. CanonicalAgWord7 := function( I, g )
  1122.     return rec( representative       := g,
  1123.                 info                 := I,
  1124.                 operations           := FactorGroupAgWordOps,
  1125.                 isFactorGroupElement := true );
  1126.  
  1127. end;
  1128.  
  1129. CanonicalAgWord4 := function( I, g )
  1130.     return rec( representative       := I.kernel.identity,
  1131.                 info                 := I,
  1132.                 operations           := FactorGroupAgWordOps,
  1133.                 isFactorGroupElement := true );
  1134. end;
  1135.  
  1136. CanonicalAgWord5 := function( I, g )
  1137.     local   x, y, i, first;
  1138.     first := I.kernel.shiftInfo.first;
  1139.     if TailDepthAgWord( g ) < first  then
  1140.         return rec( representative       := g,
  1141.                     info                 := I,
  1142.                     operations           := FactorGroupAgWordOps,
  1143.                     isFactorGroupElement := true );
  1144.     else
  1145.         x := ExponentsAgWord( g, 1, first - 1 );
  1146.         y := I.kernel.parent.cgs;
  1147.         g := I.kernel.identity;
  1148.         for i  in [ 1 .. Length(x) ]  do
  1149.             if x[i] > 0  then
  1150.                 g := g * y[i] ^ x[i];
  1151.             fi;
  1152.         od;
  1153.         return rec( representative       := g,
  1154.                     info                 := I,
  1155.                     operations           := FactorGroupAgWordOps,
  1156.                     isFactorGroupElement := true );
  1157.     fi;
  1158. end;
  1159.  
  1160. CanonicalAgWord6a := function( I, g )
  1161.     local   y, x, d, e;
  1162.     y := I.kernel.cgs;
  1163.     for x  in y  do
  1164.         d := DepthAgWord( x );
  1165.         e := ExponentAgWord( g, d );
  1166.         if e > 0  then
  1167.             g := g / x ^ e;
  1168.         fi;
  1169.     od;
  1170.     return rec( representative       := g,
  1171.                 info                 := I,
  1172.                 operations           := FactorGroupAgWordOps,
  1173.                 isFactorGroupElement := true );
  1174. end;
  1175.  
  1176. CanonicalAgWord6b := function( I, g )
  1177.     local   y, x, d, e;
  1178.     y := I.kernel.igs;
  1179.     for x  in y  do
  1180.         d := DepthAgWord( x );
  1181.         e := ExponentAgWord( g, d );
  1182.         if e > 0  then
  1183.             e := LeadingExponentAgWord( x ) / e mod RelativeOrderAgWord( x );
  1184.             g := g / x ^ e;
  1185.         fi;
  1186.     od;
  1187.     return rec( representative       := g,
  1188.                 info                 := I,
  1189.                 operations           := FactorGroupAgWordOps,
  1190.                 isFactorGroupElement := true );
  1191. end;
  1192.  
  1193. AgGroupOps.CollectorlessFactorGroup := function( U, N )
  1194.     local   G,  factor,  depths,  info,  i,  gens,  id;
  1195.  
  1196.     N := CopyAgGroup( N );
  1197.     U := CopyAgGroup( U );
  1198.     factor := FactorArg( U, N );
  1199.     depths := List( factor.generators, DepthAgWord );
  1200.  
  1201.     # Setup the agword infomation record.
  1202.     info := rec();
  1203.     info.kernel := N;
  1204.     info.group  := U;
  1205.     info.factor := factor;
  1206.     info.depths := [];
  1207.     for i  in [ 1 .. Length( depths ) ]  do
  1208.         info.depths[ depths[ i ] ] := i;
  1209.     od;
  1210.  
  1211.     # Select a function in order to compute a canonical rep.
  1212.     if not IsBound( info.kernel.shiftInfo )  then
  1213.         info.kernel.operations.AddShiftInfo( info.kernel );
  1214.     fi;
  1215.  
  1216.     if info.kernel.shiftInfo.method = 1  then
  1217.         Error( "factor arguments are not allowed" );
  1218.     elif info.kernel.shiftInfo.method = 2  then
  1219.         Error( "factor arguments are not allowed" );
  1220.     elif info.kernel.shiftInfo.method = 3  then
  1221.         Error( "factor arguments are not allowed" );
  1222.     elif info.kernel.shiftInfo.method = 4  then
  1223.         info.canonical := CanonicalAgWord4;
  1224.     elif info.kernel.shiftInfo.method = 5  then
  1225.         info.canonical := CanonicalAgWord5;
  1226.     elif info.kernel.shiftInfo.method = 6  then
  1227.         if IsBound( info.kernel.igs )  then
  1228.             info.canonical := CanonicalAgWord6b;
  1229.         else
  1230.             info.canonical := CanonicalAgWord6a;
  1231.         fi;
  1232.     elif info.kernel.shiftInfo.method = 7  then
  1233.         info.canonical := CanonicalAgWord7;
  1234.     else
  1235.         Error( "unkown method ", info.kernel.shiftInfo.method );
  1236.     fi;
  1237.  
  1238.     # Construct the new ag words.
  1239.     gens := List( factor.generators, x -> info.canonical( info, x ) );
  1240.     id   := info.canonical( info, N.identity );
  1241.  
  1242.     # Construct new ag group.
  1243.     G := rec();
  1244.     G.isDomain   := true;
  1245.     G.isGroup    := true;
  1246.     G.isAgGroup  := true;
  1247.     G.generators := gens;
  1248.     G.identity   := id;
  1249.     G.cgs        := G.generators;
  1250.     G.operations := AgGroupOps;
  1251.     return G;
  1252.  
  1253. end;
  1254.  
  1255.  
  1256. #############################################################################
  1257. ##
  1258.  
  1259. #F  CayleyInputAgGroup( <U>, <name> )   . . . . . . . . . cayley input string
  1260. ##
  1261. ##  Compute  the  pc-presentation  for a  finite polycyclic  group  as cayley
  1262. ##  input.  Return  this  input  as string.  The group will be named "G", the
  1263. ##  generators  "G.i".  The  workspace for this group in cayley will be saved
  1264. ##  under <name>.
  1265. ##
  1266. CayleyInputAgGroup := function( U, name )
  1267.  
  1268.     local   gens,
  1269.             word,
  1270.             wordString,
  1271.             lines,
  1272.             newLines,
  1273.             i, j;
  1274.  
  1275.  
  1276.     # <lines>  will  hold the various lines of the input for cayley,they will
  1277.     # be concatenated later.
  1278.     lines := [];
  1279.  
  1280.     # Get the generators for the group  <U>.
  1281.     gens := Igs( U );
  1282.  
  1283.     # Make the preamble for Cayley. Initialize the group and generators.
  1284.     Add( lines, "PRINT 'A group of order "                          );
  1285.     Add( lines, String( Size( U ) )                                 );
  1286.     Add( lines, " will be defined.';\n"                             );
  1287.     Add( lines, "\" This presentation was computed by GAP \";\n"    );
  1288.     Add( lines, "G = FGRANK( "                                      );
  1289.     Add( lines, String( Length( gens ) )                            );
  1290.     Add( lines, " );\n"                                             );
  1291.     Add( lines, "G.PCRELATIONS :\n"                                 );
  1292.  
  1293.     # A function will yield the string for a word.
  1294.     wordString := function( a )
  1295.         local k, l, list, str, count;
  1296.         list := U.operations.Exponents( U, a, Integers );
  1297.         k := 1;
  1298.         while k <= Length( list ) and list[k] = 0  do k := k + 1;  od;
  1299.         if k > Length( list )  then return "IDENTITY";  fi;
  1300.         if list[ k ] <> 1  then
  1301.             str := ConcatenationString(
  1302.                 "G.", String( k ), "^", String( list[ k ] ) );
  1303.         else
  1304.             str := ConcatenationString( "G.", String( k ) );
  1305.         fi;
  1306.         count := LengthString( str );
  1307.         for l  in [ k + 1 .. Length( list ) ]  do
  1308.             if count > 60  then
  1309.                 str   := ConcatenationString( str, "\n    " );
  1310.                 count := 4;
  1311.             fi;
  1312.             count := count - LengthString( str );
  1313.             if list[ l ] > 1  then
  1314.                 str := ConcatenationString(
  1315.                     str, "*G.", String( l ), "^", String( list[ l ] ) );
  1316.             elif list[ l ] = 1  then
  1317.                 str := ConcatenationString( str, "*G.", String( l ) );
  1318.             fi;
  1319.             count := count + LengthString( str );
  1320.         od;
  1321.         return str;
  1322.     end;
  1323.  
  1324.     # Add the power presentation part.
  1325.     for i  in [ 1 .. Length( gens ) ]  do
  1326.         Add( lines, "G."                                                 );
  1327.         Add( lines, String( i )                                          );
  1328.         Add( lines, "^"                                                  );
  1329.         Add( lines, String( RelativeOrderAgWord( gens[ i ] ) )           );
  1330.         Add( lines, " =\n    "                                           );
  1331.         Add( lines, wordString( gens[i]^RelativeOrderAgWord( gens[i] ) ) );
  1332.         Add( lines, ",\n"                                                );
  1333.     od;
  1334.  
  1335.     # Add the commutator presentation part.
  1336.     for i  in [ 1 .. Length( gens ) - 1 ]  do
  1337.         for j  in [ i + 1 .. Length( gens ) ]  do
  1338.             if i <> Length( gens ) - 1 or j <> i + 1  then
  1339.                 Add( lines, "(G."                                       );
  1340.                 Add( lines, String( j )                                 );
  1341.                 Add( lines, ",G."                                       );
  1342.                 Add( lines, String( i )                                 );
  1343.                 Add( lines, ") =\n    "                                 );
  1344.                 Add( lines, wordString( Comm( gens[ j ], gens[ i ] ) )  );
  1345.                 Add( lines, ",\n"                                       );
  1346.             else
  1347.                 Add( lines, "(G."                                       );
  1348.                 Add( lines, String( j )                                 );
  1349.                 Add( lines, ",G."                                       );
  1350.                 Add( lines, String( i )                                 );
  1351.                 Add( lines, ") =\n    "                                 );
  1352.                 Add( lines, wordString( Comm( gens[ j ], gens[ i ] ) )  );
  1353.                 Add( lines, ";\n"                                       );
  1354.             fi;
  1355.        od;
  1356.     od;
  1357.  
  1358.     # Add a postambel.
  1359.     Add( lines, "PRINT 'A group of order ',ORDER( G ),' is defined.';\n"   );
  1360.     Add( lines, "PRINT 'It will be saved under "                           );
  1361.     Add( lines, name                                                       );
  1362.     Add( lines, ".cws and is called G.';\n"                                );
  1363.     Add( lines, "save '"                                                   );
  1364.     Add( lines, name                                                       );
  1365.     Add( lines, ".cws';\nbye;\n"                                           );
  1366.  
  1367.     # Concatenate all lines and return.
  1368.     while Length( lines ) > 1  do
  1369.         if Length( lines ) mod 2 = 1  then
  1370.             Add( lines, "" );
  1371.         fi;
  1372.         newLines := [];
  1373.         for i  in [ 1 .. Length( lines ) / 2 ]  do
  1374.             newLines[ i ] := ConcatenationString( lines[2*i-1], lines[2*i] );
  1375.         od;
  1376.         lines := newLines;
  1377.     od;
  1378.     return lines[ 1 ];
  1379.  
  1380. end;
  1381.  
  1382.  
  1383. #############################################################################
  1384. ##
  1385. #F  GapInputAgGroup( <U>, <name> )  . . . . . . . . . . . .  gap input string
  1386. ##
  1387. ##  Compute  the  pc-presentation for a finite polycyclic group as gap input.
  1388. ##  Return  this  input  as  string.  The group  will  be  named  <name>, the
  1389. ##  generators "g<i>".
  1390. ##
  1391. GapInputAgGroup := function( U, name )
  1392.  
  1393.     local   gens,
  1394.             word,
  1395.             wordString,
  1396.             newLines,
  1397.             lines,
  1398.             i, j;
  1399.  
  1400.  
  1401.     # <lines>  will  hold  the  various  lines of the input for gap, they are
  1402.     # concatenated later.
  1403.     lines := [];
  1404.  
  1405.     # Get the generators for the group <U>.
  1406.     gens := Igs( U );
  1407.  
  1408.     # Make the preamble for GAP. Initialize the group and the generators.
  1409.     Add( lines, "##\n"                                                  );
  1410.     Add( lines, "## The presentation has been computed by GAP\n"        );
  1411.     Add( lines, "##\n"                                                  );
  1412.     Add( lines, "Print( \"A group of order "                            );
  1413.     Add( lines, String( Size( U ) )                                     );
  1414.     Add( lines, " will be defined.\\n\" );\n"                           );
  1415.     for i  in [ 1 .. Length( gens ) ]  do
  1416.         Add( lines, "g"             );
  1417.         Add( lines, String( i )     );
  1418.         Add( lines, " := AbstractGenerator( \"g" );
  1419.         Add( lines, String( i )     );
  1420.         Add( lines, "\" );\n"       );
  1421.     od;
  1422.     Add( lines, "GROUP := rec( generators := [\n"   );
  1423.     for i  in [ 1 .. Length( gens ) - 1 ]  do
  1424.         Add( lines, "g"         );
  1425.         Add( lines, String( i ) );
  1426.         Add( lines, ",\n"       );
  1427.     od;
  1428.     Add( lines, "g"                         );
  1429.     Add( lines, String( Length( gens ) )    );
  1430.     Add( lines, "],\n"                      );
  1431.     Add( lines, "relators := [\n"           );
  1432.  
  1433.     # A function will yield the string for a word.
  1434.     wordString := function( a )
  1435.         local k, l, list, str, count;
  1436.         list := U.operations.Exponents( U, a, Integers );
  1437.         k := 1;
  1438.         while k <= Length( list ) and list[k] = 0  do k := k + 1;  od;
  1439.         if k > Length( list )  then return "IdWord";  fi;
  1440.         if list[ k ] <> 1  then
  1441.             str := ConcatenationString( "g", String( k ), "^",
  1442.                 String( list[ k ] ) );
  1443.         else
  1444.             str := ConcatenationString( "g", String( k ) );
  1445.         fi;
  1446.         count := LengthString( str ) + 15;
  1447.         for l  in [ k + 1 .. Length( list ) ]  do
  1448.             if count > 60  then
  1449.                 str   := ConcatenationString( str, "\n    " );
  1450.                 count := 4;
  1451.             fi;
  1452.             count := count - LengthString( str );
  1453.             if list[ l ] > 1  then
  1454.                 str := ConcatenationString( str, "*g", String( l ), "^",
  1455.                     String( list[ l ] ) );
  1456.             elif list[ l ] = 1  then
  1457.                 str := ConcatenationString( str, "*g", String( l ) );
  1458.             fi;
  1459.             count := count + LengthString( str );
  1460.         od;
  1461.         return str;
  1462.     end;
  1463.  
  1464.     # Add the power presentation part.
  1465.     for i  in [ 1 .. Length( gens ) ]  do
  1466.         Add( lines, ConcatenationString( "g", String( i ), "^",
  1467.             String( RelativeOrderAgWord( gens[ i ] ) ), " / ( ",
  1468.             wordString( gens[ i ] ^ RelativeOrderAgWord( gens[ i ] ) ),
  1469.         " ),\n" ) );
  1470.     od;
  1471.  
  1472.     # Add the commutator presentation part.
  1473.     for i  in [ 1 .. Length( gens ) - 1 ]  do
  1474.         for j  in [ i + 1 .. Length( gens ) ]  do
  1475.             if i <> Length( gens ) - 1 or j <> i + 1  then
  1476.                 Add( lines, ConcatenationString( "Comm( g", String( j ),
  1477.                     ", g",  String( i ), " ) / ( ",
  1478.                     wordString( Comm( gens[ j ], gens[ i ] ) ), " ),\n" ) );
  1479.             else
  1480.                 Add( lines, ConcatenationString( "Comm( g", String( j ),
  1481.                     ", g", String( i ), " ) / ( ",
  1482.                     wordString( Comm( gens[ j ], gens[ i ] ) ), " )\n" ) );
  1483.             fi;
  1484.        od;
  1485.     od;
  1486.     Add( lines, "] );\n" );
  1487.  
  1488.     # Postamble.
  1489.     Add( lines, name                                );
  1490.     Add( lines, " := AgGroupFpGroup( GROUP );\n"    );
  1491.     for i  in [ 1 .. Length( gens ) ]  do
  1492.         Add( lines, "g"                 );
  1493.         Add( lines, String( i )         );
  1494.         Add( lines, " := "              );
  1495.         Add( lines, name                );
  1496.         Add( lines, ".generators[ "     );
  1497.         Add( lines, String( i )         );
  1498.         Add( lines, " ];\n"             );
  1499.     od;
  1500.     Add( lines, "Print(\"A group of order \", Size("         );
  1501.     Add( lines, name                                         );
  1502.     Add( lines, "), \" has been defined.\\n\");\n"           );
  1503.     Add( lines, "Print(\"It is called "                      );
  1504.     Add( lines, name                                         );
  1505.     Add( lines, "\\n\");\n"                                  );
  1506.  
  1507.     # Concatenate all lines and return.
  1508.     while Length( lines ) > 1  do
  1509.         if Length( lines ) mod 2 = 1  then
  1510.             Add( lines, "" );
  1511.         fi;
  1512.         newLines := [];
  1513.         for i  in [ 1 .. Length( lines ) / 2 ]  do
  1514.             newLines[ i ] := ConcatenationString( lines[2*i-1], lines[2*i] );
  1515.         od;
  1516.         lines := newLines;
  1517.     od;
  1518.     return lines[ 1 ];
  1519.  
  1520. end;
  1521.  
  1522.  
  1523. #############################################################################
  1524. ##
  1525. #F  SogosInputAgGroup( <U>, <name> )  . . . . . . . . . .  sogos input string
  1526. ##
  1527. ##  Compute  the  pc-presentation  for  a  finite polycyclic  group as  sogos
  1528. ##  input.  Return  this input as string. The group will be named <name>, the
  1529. ##  generators "gi".
  1530. ##
  1531. SogosInputAgGroup := function( U, name )
  1532.  
  1533.     local   gens,
  1534.             word,
  1535.             wordString,
  1536.             shift,
  1537.             newLines,
  1538.             lines,
  1539.             i, j;
  1540.  
  1541.  
  1542.     # <lines>  will  hold the various lines of the input for sogos, they will
  1543.     # be concatenated later.
  1544.     lines := [];
  1545.  
  1546.     # Get the generators for the group <U>.
  1547.     gens := Igs( U );
  1548.  
  1549.     #  Make the preamble for Sogos. Initialize the group and the generators.
  1550.     Add( lines, "\" A group of order "                                  );
  1551.     Add( lines, String( Size( U ) )                                     );
  1552.     Add( lines, " will be defined. \"\n"                                );
  1553.     Add( lines, "\" The presentation has been computed by GAP \";\n"    );
  1554.     Add( lines, "group: "                                               );
  1555.     Add( lines, name                                                    );
  1556.     Add( lines, ";\n"                                                   );
  1557.     Add( lines, "generators:\n"                                         );
  1558.     for i  in [ 1 .. Length( gens ) - 1 ]  do
  1559.         Add( lines, "g"         );
  1560.         Add( lines, String( i ) );
  1561.         Add( lines, ",\n"       );
  1562.     od;
  1563.     Add( lines, "g"                         );
  1564.     Add( lines, String( Length( gens ) )    );
  1565.     Add( lines, ";\n"                       );
  1566.     Add( lines, "pc relations:\n"           );
  1567.  
  1568.     # A function will will yield the string for a word.
  1569.     wordString := function( a )
  1570.         local k, l, list, str, count;
  1571.         list := U.operations.Exponents( U, a, Integers );
  1572.         k := 1;
  1573.         while k <= Length( list ) and list[k] = 0  do k := k + 1;  od;
  1574.         if k > Length( list )  then return "1";  fi;
  1575.         if list[ k ] <> 1  then
  1576.             str := ConcatenationString( "g", String( k ), "^",
  1577.                 String( list[ k ] ) );
  1578.         else
  1579.             str := ConcatenationString( "g", String( k ) );
  1580.         fi;
  1581.         count := LengthString( str ) + 15;
  1582.         for l  in [ k + 1 .. Length( list ) ]  do
  1583.             if count > 60  then
  1584.                 str   := ConcatenationString( str, "\n    " );
  1585.                 count := 4;
  1586.             fi;
  1587.             count := count - LengthString( str );
  1588.             if list[ l ] > 1  then
  1589.                 str := ConcatenationString( str, "*g", String( l ), "^",
  1590.                     String( list[ l ] ) );
  1591.             elif list[ l ] = 1  then
  1592.                 str := ConcatenationString( str, "*g", String( l ) );
  1593.             fi;
  1594.             count := count + LengthString( str );
  1595.         od;
  1596.         return str;
  1597.     end;
  1598.  
  1599.     # Add the power presentation part.
  1600.     for i  in [ 1 .. Length( gens ) ]  do
  1601.         Add( lines, ConcatenationString( "g", String( i ), "^",
  1602.             String( RelativeOrderAgWord( gens[ i ] ) ), " = ",
  1603.             wordString( gens[ i ] ^ RelativeOrderAgWord( gens[ i ] ) ),
  1604.         ",\n" ) );
  1605.     od;
  1606.  
  1607.     # Add the commutator presentation part.
  1608.     for i  in [ 1 .. Length( gens ) - 1 ]  do
  1609.         for j  in [ i + 1 .. Length( gens ) ]  do
  1610.             if i <> Length( gens ) - 1 or j <> i + 1  then
  1611.                 Add( lines, ConcatenationString( "[g", String( j ), ",g",
  1612.                     String( i ), "] = ", wordString( Comm( gens[ j ],
  1613.                     gens[ i ] ) ), ",\n" ) );
  1614.             else
  1615.                 Add( lines, ConcatenationString( "[g", String( j ), ",g",
  1616.                     String( i ), "] = ", wordString( Comm( gens[ j ],
  1617.                     gens[ i ] ) ), ";\n" ) );
  1618.             fi;
  1619.        od;
  1620.     od;
  1621.  
  1622.     # Postamble.
  1623.     Add( lines, "order;\n" );
  1624.     Add( lines, "elementary abelian series;\n" );
  1625.     Add( lines, "save workspace, file = '" );
  1626.     Add( lines, name );
  1627.     Add( lines, ".sws';\n" );
  1628.     Add( lines, "input;\n" );
  1629.  
  1630.     # Concatenate all lines and return.
  1631.     while Length( lines ) > 1  do
  1632.         if Length( lines ) mod 2 = 1  then
  1633.             Add( lines, "" );
  1634.         fi;
  1635.         newLines := [];
  1636.         for i  in [ 1 .. Length( lines ) / 2 ]  do
  1637.             newLines[ i ] := ConcatenationString( lines[2*i-1], lines[2*i] );
  1638.         od;
  1639.         lines := newLines;
  1640.     od;
  1641.     return lines[ 1 ];
  1642.  
  1643. end;
  1644.  
  1645.  
  1646. #############################################################################
  1647. ##
  1648. #F  CGSInputAgGroup( <U>, <name> )  . . . . . . . . . .  generate input files
  1649. ##
  1650. CGSInputAgGroup := function( U, name )
  1651.  
  1652.     local   gapFile,
  1653.             sogosFile,
  1654.             cayleyFile;
  1655.  
  1656.     gapFile    := ConcatenationString( name, ".gap" );
  1657.     sogosFile  := ConcatenationString( name, ".sog" );
  1658.     cayleyFile := ConcatenationString( name, ".cay" );
  1659.  
  1660.     PrintTo( gapFile,    GapInputAgGroup   ( U, name ) );
  1661.     PrintTo( sogosFile,  SogosInputAgGroup ( U, name ) );
  1662.     PrintTo( cayleyFile, CayleyInputAgGroup( U, name ) );
  1663.  
  1664. end;
  1665.  
  1666.  
  1667. #############################################################################
  1668. ##
  1669.  
  1670. #F  Read .  . . . . . . . . . . . . . . . . . . . . load other group packages
  1671. ##
  1672. ReadLib( "agprops"  );
  1673. ReadLib( "agsubgrp" );
  1674. ReadLib( "aghomomo" );
  1675. ReadLib( "agcoset"  );
  1676. ReadLib( "agnorm"   );
  1677. ReadLib( "aghall"   );
  1678. ReadLib( "aginters" );
  1679. ReadLib( "agcomple" );
  1680. ReadLib( "agclass"  );
  1681. ReadLib( "agcent"   );
  1682. ReadLib( "agctbl"   );
  1683. ReadLib( "lattag"   );
  1684. ReadLib( "onecohom" );
  1685.  
  1686.  
  1687. #############################################################################
  1688. ##
  1689. #F  MergeOperationsEntries( <src>, <dst> )  . . . . . . . . . fix ops entries
  1690. ##
  1691. MergeOperationsEntries := function( src, dst )
  1692.     local   sen,  den,  cpy,  nam;
  1693.  
  1694.     sen := Set( RecFields( src ) );
  1695.     den := Set( RecFields( dst ) );
  1696.     cpy := Difference( sen, den );
  1697.     for nam  in cpy  do
  1698.     dst.( nam ) := src.( nam );
  1699.     od;
  1700.  
  1701. end;
  1702.  
  1703. MergeOperationsEntries( AgGroupOps, DirectProductAgGroupOps );
  1704.  
  1705.  
  1706. #############################################################################
  1707. ##
  1708.  
  1709. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1710. ##
  1711. ## Local Variables:
  1712. ## mode:           outline
  1713. ## outline-regexp: "#F\\|#V\\|#E"
  1714. ## eval:           (hide-body)
  1715. ## End:
  1716. ##
  1717.