home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / group.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  92.0 KB  |  3,253 lines
  1. #############################################################################
  2. ##
  3. #A  group.g                     GAP library                      Frank Celler
  4. ##
  5. #A  @(#)$Id: group.g,v 3.63 1993/02/11 17:50:25 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains dispatcher and default functions for  group functions.
  10. ##
  11. ##  Namely it  contains   the functions that   construct groups and  subgroup
  12. ##  (e.g.   'Group'  and  'Subgroup'), the  functions  that implement  domain
  13. ##  functions  (e.g.  'GroupOp.Element'), the  functions   that  test  if   a
  14. ##  group has  a  certain property  (e.g.   'IsPerfect'), the  functions that
  15. ##  test  properties  for subgroups (e.g.   'IsNormal'),  the  functions that
  16. ##  compute  important  subgroups (e.g.    'SylowSubgroup'),  the   functions
  17. ##  that  compute  series   (e.g.  'LowerCentralSeries'), and   the functions
  18. ##  that compute other information for subgroups (e.g. 'Index').
  19. ##
  20. ##  Further functions  that can be   applied to groups  are  in 'grpcoset.g',
  21. ##  'grphomom.g', 'grpprods.g' and 'operatio.g'.
  22. ##
  23. #H  $Log: group.g,v $
  24. #H  Revision 3.63  1993/02/11  17:50:25  martin
  25. #H  the code to compute the radical was incorrect
  26. #H
  27. #H  Revision 3.62  1993/02/10  10:11:14  martin
  28. #H  added 'PCore' and 'Radical'
  29. #H
  30. #H  Revision 3.61  1993/01/18  18:54:52  martin
  31. #H  added character table computation
  32. #H
  33. #H  Revision 3.60  1993/01/04  11:16:53  fceller
  34. #H  added 'Exponent'
  35. #H
  36. #H  Revision 3.59  1992/12/16  19:47:27  martin
  37. #H  replaced quoted record names with escaped ones
  38. #H
  39. #H  Revision 3.58  1992/12/02  08:08:42  fceller
  40. #H  moved 'CompositionSeries' and 'PCentralSeries' to "group.tex"
  41. #H
  42. #H  Revision 3.57  1992/11/30  18:35:28  fceller
  43. #H  added 'ElementaryAbelianSeries' and 'CompositionSeries'
  44. #H
  45. #H  Revision 3.56  92/08/10  12:21:05  fceller
  46. #H  fixed 'AgGroup' problem for PQp
  47. #H  
  48. #H  Revision 3.55  1992/06/23  08:56:49  fceller
  49. #H  'Factorization' should work not only for groups but for all
  50. #H  structures with generators.
  51. #H
  52. #H  Revision 3.54  1992/06/04  07:04:20  fceller
  53. #H  added 'AgGroup' for PqPresentation
  54. #H
  55. #H  Revision 3.53  1992/06/01  11:14:12  martin
  56. #H  changed 'Subgroup' to really ignore identities in the generators list
  57. #H
  58. #H  Revision 3.52  1992/03/27  11:14:51  martin
  59. #H  changed mapping to general mapping and function to mapping
  60. #H
  61. #H  Revision 3.51  1992/03/12  20:27:10  fceller
  62. #H  fixed a minor bug.
  63. #H
  64. #H  Revision 3.50  1992/02/12  15:44:23  martin
  65. #H  added the lattice package
  66. #H
  67. #H  Revision 3.49  1992/02/11  12:44:04  martin
  68. #H  added 'SmallestGenerators'
  69. #H
  70. #H  Revision 3.48  1992/02/11  12:39:49  martin
  71. #H  improved 'GroupOps.IsSubset' for common cases
  72. #H
  73. #H  Revision 3.47  1992/02/07  13:36:09  fceller
  74. #H  Initial GAP 3.1 release.
  75. #H
  76. #H  Revision 3.1  1991/05/06  11:23:50  fceller
  77. #H  Initial revision under RCS.
  78. ##
  79.  
  80.  
  81. #############################################################################
  82. ##
  83. #F  InfoGroup?( ... ) . . . . . .  information function for the group package
  84. ##
  85. if not IsBound( InfoGroup1 )  then InfoGroup1 := Ignore;  fi;
  86. if not IsBound( InfoGroup2 )  then InfoGroup2 := Ignore;  fi;
  87.  
  88.  
  89. #############################################################################
  90. ##
  91. #F  GroupString(<G>,<name>) . . . . . . . . . . . .  group information string
  92. ##
  93. GroupString := function ( G, name )
  94.     if IsBound( G.name )  then
  95.         if IsBound( G.size )  then
  96.             return ConcatenationString(
  97.                         G.name, " ",
  98.                         "(size ", StringInt(G.size), ")"
  99.                    );
  100.         else
  101.             return G.name;
  102.         fi;
  103.     else
  104.         if IsBound( G.size )  then
  105.             return ConcatenationString(
  106.                         "<", name, "> ",
  107.                         "(", StringInt(Length(G.generators)), " gens, ",
  108.                         "size ", StringInt(G.size), ")"
  109.                    );
  110.         else
  111.             return ConcatenationString(
  112.                         "<", name, "> ",
  113.                         "(", StringInt(Length(G.generators)), " gens)"
  114.                    );
  115.         fi;
  116.     fi;
  117. end;
  118.  
  119.  
  120. #############################################################################
  121. ##
  122.  
  123. #V  GroupOps  . . . . . . . . . . . . . . . . .  operations record for groups
  124. ##
  125. ##  'GroupOps' is the operations record for groups.  This is initially a copy
  126. ##  of 'DomainOps'.  This way all the default methods for domains are
  127. ##  inherited.
  128. ##
  129. ##  The operations records for special groups are created by making a copy of
  130. ##  this record and overlaying some functions.  This way those groups inherit
  131. ##  the default methods.
  132. ##
  133. GroupOps := Copy( DomainOps );
  134.  
  135.  
  136. #############################################################################
  137. ##
  138.  
  139. #F  Group(<gen>,...) or Group(<gens>,<id>) or Group(<D>)  . .  create a group
  140. ##
  141. Group := function ( arg )
  142.     local   G,          # group containing the elements of <arg>, result
  143.             D,          # domain containing the elements of <arg>
  144.             gens,       # elements of <arg> as a flat list
  145.             id,         # identity element
  146.             i;          # loop variable
  147.  
  148.     # if called with one domain argument look in the operations record
  149.     if Length( arg ) = 1 and IsDomain( arg[1] )  then
  150.         G := arg[1].operations.Group( arg[1] );
  151.  
  152.     # special case for matrices, because they look like lists
  153.     elif Length( arg ) = 2 and IsMat( arg[1] )  then
  154.         gens := arg;
  155.         id   := arg[1]^0;
  156.         D    := Domain( gens );
  157.         G    := D.operations.Group( D, gens, id );
  158.  
  159.     # list of generators plus identity
  160.     elif Length( arg ) = 2 and IsList( arg[1] )  then
  161.         gens := arg[1];
  162.         id   := arg[2];
  163.         D    := Domain( Concatenation( gens, [ id ] ) );
  164.         G    := D.operations.Group( D, gens, id );
  165.  
  166.     # generators
  167.     elif 0 < Length( arg )  then
  168.         gens := arg;
  169.         id   := arg[1]^0;
  170.         D    := Domain( gens );
  171.         G    := D.operations.Group( D, gens, id );
  172.  
  173.     # no argument given, error
  174.     else
  175.         Error("usage: Group(<gen>,...) or Group(<gens>,<id>) or Group(<D>)");
  176.     fi;
  177.  
  178.     # return the group
  179.     for i  in [ 1 .. Length(G.generators) ]  do
  180.         G.(i) := G.generators[i];
  181.     od;
  182.     return G;
  183.  
  184. end;
  185.  
  186. GroupElementsOps.Group := function ( GroupElements, gens, id )
  187.     local   G;          # group containing <gens>, result
  188.  
  189.     # make the domain
  190.     G            := rec();
  191.     G.isDomain   := true;
  192.     G.isGroup    := true;
  193.  
  194.     # enter identification
  195.     G.identity   := id;
  196.     if id in gens  then
  197.         G.generators := Filtered( gens, gen -> gen <> id );
  198.     else
  199.         G.generators := ShallowCopy( gens );
  200.     fi;
  201.  
  202.     # enter operations record
  203.     G.operations := GroupOps;
  204.  
  205.     # return the group
  206.     return G;
  207.  
  208. end;
  209.  
  210.  
  211. #############################################################################
  212. ##
  213. #F  AsGroup( <D> )  . . . . . . . . . . . . . . . .  view a domain as a group
  214. ##
  215. AsGroup := function ( D )
  216.     local   G;
  217.  
  218.     # check that the argument is a domain or a list
  219.     if not IsDomain( D )  and not IsList( D )  then
  220.         Error( "<D> must be a list or a domain" );
  221.     fi;
  222.  
  223.     # convert a domain into a group
  224.     if IsDomain( D )  then
  225.         G := D.operations.AsGroup( D );
  226.  
  227.     # convert a list into a group
  228.     else
  229.         G := Domain( D ).operations.AsGroup( D );
  230.     fi;
  231.  
  232.     # return the group
  233.     return G;
  234.  
  235. end;
  236.  
  237. GroupElementsOps.AsGroup := function ( D )
  238.     local   G,  L;
  239.  
  240.     # handle trivial case
  241.     if IsGroup( D )  then
  242.         G := ShallowCopy( D );
  243.  
  244.     # otherwise take elements from the domain
  245.     else
  246.         D := Set( D );
  247.         L := ShallowCopy( D );
  248.         G := TrivialSubgroup( Group( D, D[1]^0 ) );
  249.         SubtractSet( L, Elements( G ) );
  250.         while L <> []  do
  251.             G := Closure( G, L[1] );
  252.             SubtractSet( L, Elements( G ) );
  253.         od;
  254.         if Length( Elements( G ) ) <> Length( D )  then
  255.             Error( "the elements of <D> must form a group" );
  256.         fi;
  257.         G := Group( G.generators, D[1]^0 );
  258.         G.elements := D;
  259.         G.isFinite := true;
  260.         G.size     := Length( D );
  261.     fi;
  262.  
  263.     # return the group
  264.     return G;
  265.  
  266. end;
  267.  
  268. GroupOps.AsGroup := function( G )
  269.     return ShallowCopy( G );
  270. end;
  271.  
  272.  
  273. #############################################################################
  274. ##
  275. #F  IsGroup( <obj> )  . . . . . . . . . . . . .  test if an object is a group
  276. ##
  277. IsGroup := function ( obj )
  278.     return     IsRec( obj )
  279.            and IsBound( obj.isGroup )
  280.            and obj.isGroup;
  281. end;
  282.  
  283.  
  284. #############################################################################
  285. ##
  286. #F  IsParent( <G> ) . . . . . . . . . . . . test if a group is a parent group
  287. ##
  288. IsParent := function ( G )
  289.     return G.operations.IsParent( G );
  290. end;
  291.  
  292. GroupOps.IsParent := function ( G )
  293.     return not IsBound( G.parent );
  294. end;
  295.  
  296.  
  297. #############################################################################
  298. ##
  299. #F  Parent( <G>, ... )  . . . . . . . . . . . . . . . . . common parent group
  300. ##
  301. Parent := function ( arg )
  302.     local   G;
  303.  
  304.     # check the number of arguments
  305.     if Length( arg ) = 0  then
  306.         Error( "usage: Parent( <G>, ... )" );
  307.     fi;
  308.  
  309.     # compute the parent group
  310.     G := arg[1].operations.Parent( arg );
  311.  
  312.     # return the parent group
  313.     return G;
  314.  
  315. end;
  316.  
  317. GroupOps.Parent := function ( L )
  318.     local   G,          # parent of first group, result
  319.             H;          # loop variable
  320.  
  321.     # get the parent of the first group
  322.     if IsBound( L[1].parent )  then
  323.         G := L[1].parent;
  324.     else
  325.         G := L[1];
  326.     fi;
  327.  
  328.     # check that all other groups have the same parent
  329.     for H  in L  do
  330.         if IsBound( H.parent )  and H.parent <> G  then
  331.             Error( "<G> and <H> must have the same parent group" );
  332.         elif not IsBound( H.parent ) and H <> G  then
  333.             Error( "<G> and <H> must have the same parent group" );
  334.         fi;
  335.     od;
  336.  
  337.     # return the parent
  338.     return G;
  339.  
  340. end;
  341.  
  342.  
  343. #############################################################################
  344. ##
  345. #V  MaintainedGroupInfo . . . . . . . . . . . . . . .  maintained info fields
  346. ##
  347. MaintainedGroupInfo := [
  348.     "isCyclic", "isElementaryAbelian", "isAbelian", "isSolvable",
  349.     "isNilpotent", "isPerfect", "isSimple", "isFinite", "size"
  350. ];
  351.  
  352.  
  353. #############################################################################
  354. ##
  355.  
  356. #F  GroupOps.Group( <D> ) . . . . . . . . . . convert a subgroup into a group
  357. ##
  358. GroupOps.Group := function ( D )
  359.     local   G,          # group for the domain <D>, result
  360.             name;       # component name in the group record
  361.  
  362.     # make the group
  363.     G := Group( D.generators, D.identity );
  364.  
  365.     # copy information
  366.     for name  in Intersection( RecFields( D ), MaintainedGroupInfo ) do
  367.         G.(name) := D.(name);
  368.     od;
  369.  
  370.     # return the group
  371.     return G;
  372.  
  373. end;
  374.  
  375.  
  376. #############################################################################
  377. ##
  378. #F  GroupOps.Elements( <G> )  . . . . . . . .  set of the elements of a group
  379. ##
  380. GroupOps.Elements := function ( G )
  381.     local   H,          # subgroup of the first generators of <G>
  382.             gen;        # generator of <G>
  383.  
  384.     # start with the trivial group and its element list
  385.     H := TrivialSubgroup( G );
  386.     H.elements := [ H.identity ];
  387.  
  388.     # add the generators one after the other
  389.     for gen  in G.generators  do
  390.         H := GroupOps.Closure( H, gen );
  391.     od;
  392.  
  393.     # return the list of elements
  394.     return H.elements;
  395.  
  396. end;
  397.  
  398.  
  399. #############################################################################
  400. ##
  401. #F  GroupOps.\=( <G>, <H> )  . . . . . . . . .  test if two groups are equal
  402. ##
  403. GroupOps.\= := function ( G, H )
  404.     local   isEql;
  405.  
  406.     if IsGroup( G ) and IsFinite( G )  then
  407.         if IsGroup( H ) and IsFinite( H )  then
  408.             isEql :=    G.generators = H.generators
  409.                      or IsEqualSet( G.generators, H.generators )
  410.                      or (    Size( G ) = Size( H )
  411.                          and ForAll( G.generators, gen -> gen in H )
  412.                          and ForAll( H.generators, gen -> gen in G ));
  413.         elif IsGroup( H )  then
  414.             isEql := false;
  415.         elif IsCoset( H ) and IsFinite( H )  then
  416.             if G <> H.group  then
  417.                 isEql := false;
  418.             else
  419.                 isEql := H.representative in H.group;
  420.             fi;
  421.         elif IsCoset( H )  then
  422.             isEql := false;
  423.         else
  424.             isEql := DomainOps.\=( G, H );
  425.         fi;
  426.     elif IsGroup( G )  then
  427.         if IsGroup( H )  and IsFinite( H )  then
  428.             isEql := false;
  429.         elif IsGroup( H )  then
  430.             isEql :=    G.generators = H.generators
  431.                      or IsEqualSet( G.generators, H.generators )
  432.                      or (    ForAll( G.generators, gen -> gen in H )
  433.                          and ForAll( H.generators, gen -> gen in G ));
  434.         elif IsCoset( H ) and IsFinite( H )  then
  435.             isEql := false;
  436.         elif IsCoset( H )  then
  437.             if G <> H.group  then
  438.                 isEql := false;
  439.             else
  440.                 isEql := H.representative in H.group;
  441.             fi;
  442.         else
  443.             isEql := DomainOps.\=( G, H );
  444.         fi;
  445.     elif IsCoset( G ) and IsFinite( G )  then
  446.         if IsGroup( H ) and IsFinite( H )  then
  447.             if G.group <> H  then
  448.                 isEql := false;
  449.             else
  450.                 isEql := G.representative in G.group;
  451.             fi;
  452.         elif IsGroup( H )  then
  453.             isEql := false;
  454.         else
  455.             isEql := DomainOps.\=( G, H );
  456.         fi;
  457.     elif IsCoset( G )  then
  458.         if IsGroup( H ) and IsFinite( H )  then
  459.             isEql := false;
  460.         elif IsGroup( H )  then
  461.             if G.group <> H  then
  462.                 isEql := false;
  463.             else
  464.                 isEql := G.representative in G.group;
  465.             fi;
  466.         else
  467.             isEql := DomainOps.\=( G, H );
  468.         fi;
  469.     else
  470.         isEql := DomainOps.\=( G, H );
  471.     fi;
  472.     return isEql;
  473.  
  474. end;
  475.  
  476.  
  477. #############################################################################
  478. ##
  479. #F  GroupOps.IsSubset( <G>, <H> ) . . . . . . . . . test for subset of groups
  480. ##
  481. GroupOps.IsSubset := function ( G, H )
  482.     local   isSub;
  483.  
  484.     if IsGroup( G ) and IsFinite( G )  then
  485.         if IsGroup( H ) and IsFinite( H )  then
  486.             isSub :=    G.generators = H.generators
  487.                      or IsSubsetSet( G.generators, H.generators )
  488.                      or (IsBound( H.parent ) and G = H.parent)
  489.                      or (    Size( G ) >= Size( H )
  490.                          and ForAll( H.generators, gen -> gen in G ));
  491.         elif IsGroup( H )  then
  492.             isSub := false;
  493.         elif IsCoset( H ) and IsFinite( H )  then
  494.             isSub := IsSubset( G, H.group )
  495.                  and H.representative in G;
  496.         elif IsCoset( H )  then
  497.             isSub := false;
  498.         else
  499.             isSub := DomainOps.IsSubset( G, H );
  500.         fi;
  501.     elif IsGroup( G )  then
  502.         if IsGroup( H )  and IsFinite( H )  then
  503.             isSub :=    G.generators = H.generators
  504.                      or IsSubsetSet( G.generators, H.generators )
  505.                      or (IsBound( H.parent ) and G = H.parent)
  506.                      or ForAll( H.generators, gen -> gen in G );
  507.         elif IsGroup( H )  then
  508.             isSub :=    G.generators = H.generators
  509.                      or IsSubsetSet( G.generators, H.generators )
  510.                      or (IsBound( H.parent ) and G = H.parent)
  511.                      or ForAll( H.generators, gen -> gen in G );
  512.         elif IsCoset( H ) and IsFinite( H )  then
  513.             isSub := IsSubset( G, H.group )
  514.                  and H.representative in G;
  515.         elif IsCoset( H )  then
  516.             isSub := IsSubset( G, H.group )
  517.                  and H.representative in G;
  518.         else
  519.             isSub := DomainOps.IsSubset( G, H );
  520.         fi;
  521.     elif IsCoset( G ) and IsFinite( G )  then
  522.         if IsGroup( H ) and IsFinite( H )  then
  523.             isSub := G.identity in G.group
  524.                  and ForAll( H.generators, gen -> gen in G );
  525.         elif IsGroup( H )  then
  526.             isSub := false;
  527.         else
  528.             isSub := DomainOps.IsSubset( G, H );
  529.         fi;
  530.     elif IsCoset( G )  then
  531.         if IsGroup( H ) and IsFinite( H )  then
  532.             isSub := G.identity in G.group
  533.                  and ForAll( H.generators, gen -> gen in G );
  534.         elif IsGroup( H )  then
  535.             isSub := G.identity in G.group
  536.                  and ForAll( H.generators, gen -> gen in G );
  537.         else
  538.             isSub := DomainOps.IsSubset( G, H );
  539.         fi;
  540.     else
  541.         isSub := DomainOps.IsSubset( G, H );
  542.     fi;
  543.     return isSub;
  544.  
  545. end;
  546.  
  547.  
  548. #############################################################################
  549. ##
  550. #F  GroupOps.Intersection( <G>, <H> ) . . . . . . . .  intersection of groups
  551. ##
  552. GroupOps.Intersection := function ( G, H )
  553.  
  554.     # if one argument is a list, filter this list
  555.     if IsList( G )  then
  556.         return Filtered( G, g -> g in H );
  557.     elif IsList( H )  then
  558.         return Filtered( H, g -> g in G );
  559.     fi;
  560.  
  561.     # if the groups have different parents, use the domain method
  562.     if IsBound( G.parent )  then
  563.         if IsBound( H.parent )  then
  564.             if G.parent <> H.parent  then
  565.                 return DomainOps.Intersection( G, H );
  566.             fi;
  567.         elif H <> G.parent  then
  568.             return DomainOps.Intersection( G, H );
  569.         fi;
  570.     else
  571.         if IsBound( H.parent )  then
  572.             if G <> H.parent  then
  573.                 return DomainOps.Intersection( G, H );
  574.             fi;
  575.         elif G <> H  then
  576.             return DomainOps.Intersection( G, H );
  577.         fi;
  578.     fi;
  579.  
  580.     # construct this group of stabilizer of a right coset
  581.     if not IsFinite( G )  then
  582.         return Stabilizer( H, Coset( G ), OnRight );
  583.     elif not IsFinite( H )  then
  584.         return Stabilizer( G, Coset( H ), OnRight );
  585.     elif Size( G ) < Size( H )  then
  586.         return Stabilizer( G, Coset( H ), OnRight );
  587.     else
  588.         return Stabilizer( H, Coset( G ), OnRight );
  589.     fi;
  590.  
  591. end;
  592.  
  593.  
  594. #############################################################################
  595. ##
  596. #F  GroupOps.Print( <G> ) . . . . . . . . . . . . . . .  pretty print a group
  597. ##
  598. GroupOps.Print := function ( G )
  599.     local   i;
  600.  
  601.     # if the group has a name we use this
  602.     if IsBound( G.name )  then
  603.         Print( G.name );
  604.  
  605.     # if the group is a parent print it as 'Group(...)'
  606.     elif not IsBound( G.parent )  then
  607.  
  608.         # if the group is not trivial the identity need not be printed
  609.         if G.generators <> []  then
  610.             Print( "Group( ");
  611.             for i  in [ 1 .. Length(G.generators)-1 ]  do
  612.                 Print( G.generators[i], ", " );
  613.             od;
  614.             Print( G.generators[Length(G.generators)], " )" );
  615.  
  616.         # if the group is trivial print it as 'Group( <id> )'
  617.         else
  618.             Print( "Group( ", G.identity, " )" );
  619.         fi;
  620.  
  621.     # if the group is a subgroup print it as 'Subgroup(...)'
  622.     else
  623.         Print( "Subgroup( ", G.parent, ", ", G.generators, " )" );
  624.     fi;
  625.  
  626. end;
  627.  
  628.  
  629. #############################################################################
  630. ##
  631.  
  632. #F  Subgroup( <G>, <gens> ) . . . . . . . . . . . . . . . . create a subgroup
  633. ##
  634. Subgroup := function ( G, gens )
  635.     local   U,          # subgroup of <G> with generators <gens>, result
  636.             i;          # loop variable
  637.  
  638.     # check the arguments
  639.     if not IsGroup( G )  or not IsParent( G )  then
  640.         Error( "<G> must be a parent group" );
  641.     fi;
  642.     if not ForAll( gens, gen -> gen in G )  then
  643.         Error( "the generators <gens> must lie in <G>" );
  644.     fi;
  645.  
  646.     # make the subgroup
  647.     U := G.operations.Subgroup( G, gens );
  648.     for i  in [ 1 .. Length( U.generators ) ]  do
  649.         U.(i) := U.generators[i];
  650.     od;
  651.  
  652.     # return the subgroup
  653.     return U;
  654.  
  655. end;
  656.  
  657. GroupOps.Subgroup := function ( G, gens )
  658.     local   U;          # subgroup of <G> generated by <gens>, result
  659.  
  660.     # remove the identity from the list of generators
  661.     if G.identity in gens  then
  662.         gens := Filtered( gens, gen -> gen <> G.identity );
  663.     else
  664.         gens := ShallowCopy( gens );
  665.     fi;
  666.  
  667.     # handle special case
  668.     if IsEqualSet( G.generators, gens )  then
  669.         U := G;
  670.  
  671.     # otherwise
  672.     else
  673.  
  674.         # make the subgroup
  675.         U            := rec();
  676.         U.isDomain   := true;
  677.         U.isGroup    := true;
  678.         U.parent     := G;
  679.  
  680.         # enter the identification
  681.         U.identity   := G.identity;
  682.         U.generators := gens;
  683.  
  684.         # enter the operations record
  685.         U.operations := GroupOps;
  686.  
  687.     fi;
  688.  
  689.     # return the subgroup
  690.     return U;
  691.  
  692. end;
  693.  
  694.  
  695. #############################################################################
  696. ##
  697. #F  AsSubgroup( <G>, <U> )  . . . . view a group as subgroup of another group
  698. ##
  699. AsSubgroup := function ( G, U )
  700.  
  701.     # check the arguments
  702.     if not IsGroup( G )  or not IsParent( G )  then
  703.         Error( "<G> must be a parent group" );
  704.     fi;
  705.     if not IsGroup( U )  then
  706.         Error( "<U> must be a group" );
  707.     fi;
  708.     if not ForAll( U.generators, gen -> gen in G )  then
  709.         Error( "the generators of <U> must lie in <G>" );
  710.     fi;
  711.  
  712.     # dispatch
  713.     return G.operations.AsSubgroup( G, U );
  714.  
  715. end;
  716.  
  717. GroupOps.AsSubgroup := function ( G, U )
  718.     return G.operations.Subgroup( G, U.generators );
  719. end;
  720.  
  721.  
  722. #############################################################################
  723. ##
  724. #F  Centralizer( <G>, <obj> ) . . . . centralizer of a subgroup or an element
  725. ##
  726. Centralizer := function ( G, obj )
  727.     local   C;          # centralizer of <obj> in <G>, result
  728.  
  729.     # check the arguments
  730.     if not IsGroup( G )  then
  731.         Error( "<G> must be a group" );
  732.     elif not IsGroup( obj ) and not obj in Parent( G )  then
  733.         Error( "<obj> must be an element of the parent of <G>" );
  734.     elif IsGroup( obj ) and Parent( obj ) <> Parent( G )  then
  735.         Error( "<obj> must be a subgroup of the parent of <G>" );
  736.     fi;
  737.     InfoGroup1( "#I  Centralizer: of <obj> in ", GroupString(G,"G"), "\n" );
  738.  
  739.     # compute the centralizer
  740.     if IsParent( G ) and IsGroup( obj )  then
  741.         if not IsBound( obj.centralizer )  then
  742.             obj.centralizer := G.operations.Centralizer( G, obj );
  743.         fi;
  744.         C := obj.centralizer;
  745.     else
  746.         C := G.operations.Centralizer( G, obj );
  747.     fi;
  748.  
  749.     # return the centralizer
  750.     InfoGroup1( "#I  Centralizer: returns ", GroupString(C,"C"), "\n" );
  751.     return C;
  752.  
  753. end;
  754.  
  755. GroupOps.Centralizer := function ( G, obj )
  756.     local   C,          # centralizer of <obj> in <G>, result
  757.             gen;        # one generator of subgroup <obj>
  758.  
  759.     # centralizer of a subgroup
  760.     if IsGroup( obj )  then
  761.         C := G;
  762.         for gen  in obj.generators  do
  763.             C := Stabilizer( C, gen );
  764.         od;
  765.  
  766.     # centralizer of an element in a subgroup
  767.     else
  768.         C := Stabilizer( G, obj );
  769.     fi;
  770.  
  771.     # return the centralizer
  772.     return C;
  773.  
  774. end;
  775.  
  776.  
  777. #############################################################################
  778. ##
  779. #F  Centre( <G> ) . . . . . . . . . . . . . . . . . . . . . centre of a group
  780. ##
  781. Centre := function ( G )
  782.  
  783.     # check that the argument is a group
  784.     if not IsGroup( G )  then
  785.         Error( "<G> must be a group" );
  786.     fi;
  787.     InfoGroup1( "#I  Centre: ", GroupString(G,"G"), "\n" );
  788.  
  789.     # compute the centre
  790.     if not IsBound( G.centre )  then
  791.         G.centre := G.operations.Centre( G );
  792.     fi;
  793.  
  794.     # return the centre
  795.     InfoGroup1("#I  Centre returns ", GroupString(G.centre,"C"), "\n" );
  796.     return G.centre;
  797.  
  798. end;
  799.  
  800. GroupOps.Centre := function ( G )
  801.     local   C;          # centre of <G>, result
  802.  
  803.     # if <G> is abelian it is its own centre
  804.     if IsBound( G.isAbelian )  and G.isAbelian  then
  805.         C := G;
  806.  
  807.     # otherwise compute the centralizer of <G> in <G>
  808.     else
  809.         C := Centralizer( G, G );
  810.     fi;
  811.  
  812.     # return the centre
  813.     return C;
  814.  
  815. end;
  816.  
  817.  
  818. #############################################################################
  819. ##
  820. #F  Closure(<G>,<obj>)  . closure of a group with another group or an element
  821. ##
  822. Closure := function ( G, obj )
  823.     local   C;          # closure of <G> with <obj>, result
  824.  
  825.     # check the arguments
  826.     if not IsGroup( G )  then
  827.         Error( "<G> must be a group" );
  828.     elif not IsGroup( obj ) and not obj in Parent( G )  then
  829.         Error( "<obj> must be an element of the parent of <G>" );
  830.     elif IsGroup( obj ) and Parent( G ) <> Parent( obj )  then
  831.         Error( "<obj> must be a subgroup of the parent of <G>" );
  832.     fi;
  833.     InfoGroup1( "#I  Closure: of ", GroupString(G,"G"), " and <obj>\n" );
  834.  
  835.     # compute the closure
  836.     C := G.operations.Closure( G, obj );
  837.  
  838.     # return the closure
  839.     InfoGroup1( "#I  Closure: returns ", GroupString(C,"C"), "\n" );
  840.     return C;
  841.  
  842. end;
  843.  
  844. GroupOps.Closure := function ( G, obj )
  845.     local   C,          # closure '\< <G>, <obj> \>', result
  846.             gen,        # generator of <G> or <C>
  847.             reps,       # representatives of cosets of <G> in <C>
  848.             rep;        # representative of coset of <G> in <C>
  849.  
  850.     # handle the closure of a group with a subgroup
  851.     if IsGroup( obj )  then
  852.         if IsParent( G )  then
  853.             C := G;
  854.         elif IsParent( obj )  then
  855.             C := obj;
  856.         else
  857.             C := G;
  858.             for gen in obj.generators  do
  859.                 C := G.operations.Closure( C, gen );
  860.             od;
  861.         fi;
  862.  
  863.     # closure of a group with a single element
  864.     else
  865.  
  866.         # try to avoid adding an element to a group that already contains it
  867.         if   IsParent( G )
  868.           or obj in G.generators
  869.           or obj^-1 in G.generators
  870.           or (IsBound( G.elements )  and obj in G.elements)
  871.           or obj = G.identity
  872.         then
  873.             return G;
  874.         fi;
  875.  
  876.         # make the closure group
  877.         C := G.operations.Subgroup( Parent(G),
  878.                                     Concatenation( G.generators, [obj] ) );
  879.  
  880.         # if <G> is nonabelian then so is <C>
  881.         if IsBound( G.isAbelian ) and not G.isAbelian  then
  882.             C.isAbelian := false;
  883.         elif IsBound( G.isAbelian )  then
  884.             C.isAbelian := ForAll( G.generators,
  885.                                    gen -> Comm(gen,obj)=G.identity );
  886.         fi;
  887.  
  888.         # if <G> is infinite then so is <C>
  889.         if IsBound( G.isFinite ) and not G.isFinite  then
  890.             C.isFinite := false;
  891.             C.size     := "infinity";
  892.         fi;
  893.  
  894.         # if the elements of <G> are known then extend this list
  895.         if IsBound( G.elements )  then
  896.  
  897.             # if <G>^<obj> = <G> then <C> = <G> * <obj>
  898.             if ForAll( G.generators, gen -> gen ^ obj in G.elements )  then
  899.                 InfoGroup2( "#I   new generator normalizes\n" );
  900.                 C.elements := ShallowCopy( G.elements );
  901.                 rep := obj;
  902.                 while not rep in G.elements  do
  903.                     Append( C.elements, G.elements * rep );
  904.                     rep := rep * obj;
  905.                 od;
  906.                 C.elements := Set( C.elements );
  907.                 C.isFinite := true;
  908.                 C.size     := Length( C.elements );
  909.  
  910.             # otherwise use a Dimino step
  911.             else
  912.                 InfoGroup2( "#I   new generator normalizes not\n" );
  913.                 C.elements := ShallowCopy( G.elements );
  914.                 reps := [ G.identity ];
  915.                 InfoGroup2( "\r#I   |<cosets>| = ",Length(reps), "\c" );
  916.                 for rep  in reps  do
  917.                     for gen  in C.generators  do
  918.                         if not rep * gen in C.elements  then
  919.                             Append( C.elements, G.elements * (rep * gen) );
  920.                             Add( reps, rep * gen );
  921.                             InfoGroup2( "\r#I   |<cosets>| = ",
  922.                                         Length(reps),"\c");
  923.                         fi;
  924.                     od;
  925.                 od;
  926.                 InfoGroup2( "\n" );
  927.                 C.elements := Set( C.elements );
  928.                 C.isFinite := true;
  929.                 C.size := Length( C.elements );
  930.  
  931.             fi;
  932.         fi;
  933.  
  934.     fi;
  935.  
  936.     # return the closure
  937.     return C;
  938.  
  939. end;
  940.  
  941.  
  942. #############################################################################
  943. ##
  944. #F  CommutatorFactorGroup( <G> )  . . . .  commutator factor group of a group
  945. ##
  946. CommutatorFactorGroup := function ( G )
  947.  
  948.     # check that the argument is a group
  949.     if not IsGroup( G )  then
  950.         Error( "<G> must be a group" );
  951.     fi;
  952.     InfoGroup1( "#I  CommutatorFactorGroup: ", GroupString(G,"G"), "\n" );
  953.  
  954.     # compute the commutator factor group
  955.     if not IsBound( G.commutatorFactorGroup )  then
  956.         G.commutatorFactorGroup := G.operations.CommutatorFactorGroup( G );
  957.     fi;
  958.  
  959.     # return the commutator factor group
  960.     InfoGroup1( "#I  CommutatorFactorGroup: ",
  961.                 GroupString(G.commutatorFactorGroup,"F"),"\n");
  962.     return G.commutatorFactorGroup;
  963.  
  964. end;
  965.  
  966. GroupOps.CommutatorFactorGroup := function ( G )
  967.     return FactorGroup( G, DerivedSubgroup( G ) );
  968. end;
  969.  
  970.  
  971. #############################################################################
  972. ##
  973. #F  CommutatorSubgroup( <U>, <V> )  . . . . commutator subgroup of two groups
  974. ##
  975. CommutatorSubgroup := function ( U, V )
  976.     local   C;
  977.  
  978.     # check that the arguments are groups with a common parent
  979.     if not IsGroup( U )  then
  980.         Error( "<U> must be a group" );
  981.     elif not IsGroup( V )  then
  982.         Error( "<V> must be a group" );
  983.     fi;
  984.  
  985.     # <U> and <V> must have a common parent
  986.     Parent( U, V );
  987.     InfoGroup1( "#I  CommutatorSubgroup: of <U> and <V>\n" );
  988.  
  989.     # compute the commutator subgroup
  990.     C := U.operations.CommutatorSubgroup( U, V );
  991.  
  992.     # return the commutator subgroup
  993.     InfoGroup1( "#I  CommutatorSubgroup: ", GroupString(C,"C"), "\n" );
  994.     return C;
  995.  
  996. end;
  997.  
  998. GroupOps.CommutatorSubgroup := function ( U, V )
  999.     local   C, u, v, c;
  1000.  
  1001.     # [ <U>, <V> ] = normal closure of < [ <u>, <v> ] >.
  1002.     C := TrivialSubgroup( U );
  1003.     for u  in U.generators  do
  1004.         for v  in V.generators  do
  1005.             c := Comm( u, v );
  1006.             if not c in C  then
  1007.                 C := Closure( C, c );
  1008.             fi;
  1009.         od;
  1010.     od;
  1011.     return NormalClosure( Closure( U, V ), C );
  1012.  
  1013. end;
  1014.  
  1015.  
  1016. #############################################################################
  1017. ##
  1018. #F  Core( <G>, <U> )  . . . . . . . . . . . . . core of a subgroup in a group
  1019. ##
  1020. Core := function ( G, U )
  1021.     local   C;          # core of <U> in <G>, result
  1022.  
  1023.     # check that the arguments are groups with a common parent
  1024.     if not IsGroup( G )  then
  1025.         Error( "<G> must be a group" );
  1026.     elif not IsGroup( U )  then
  1027.         Error( "<U> must be a group" );
  1028.     fi;
  1029.     Parent( G, U );
  1030.     InfoGroup1( "#I  Core: of ", GroupString(U,"U"), " in ",
  1031.                 GroupString(G,"G"), "\n");
  1032.  
  1033.     # compute the core
  1034.     if IsParent( G )  then
  1035.         if not IsBound( U.core )  then
  1036.             U.core := G.operations.Core( G, U );
  1037.         fi;
  1038.         C := U.core;
  1039.     else
  1040.         C := G.operations.Core( G, U );
  1041.     fi;
  1042.  
  1043.     # return the core
  1044.     InfoGroup1( "#I  Core: returns ", GroupString(C,"C"), "\n" );
  1045.     return C;
  1046.  
  1047. end;
  1048.  
  1049. GroupOps.Core := function ( G, U )
  1050.     local   C,          # core of <U> in <G>, result
  1051.             i;          # loop variable
  1052.  
  1053.     # start with the subgroup <U>
  1054.     C := U;
  1055.     InfoGroup2("#I  Core: approx. is ",GroupString(C,"C"),"\n");
  1056.  
  1057.     # loop until all generators normalize <C>
  1058.     i := 1;
  1059.     while i <= Length( G.generators )  do
  1060.  
  1061.         # if <C> is not normalized by this generator take the intersection
  1062.         # with the conjugate subgroup and start all over again
  1063.         if not ForAll( C.generators, gen -> gen ^ G.generators[i] in C ) then
  1064.             C := Intersection( C, C ^ G.generators[i] );
  1065.             InfoGroup2("#I  Core: approx. is ",GroupString(C,"C"),"\n");
  1066.             i := 1;
  1067.  
  1068.         # otherwise try the next generator
  1069.         else
  1070.             i := i + 1;
  1071.         fi;
  1072.  
  1073.     od;
  1074.  
  1075.     # return the core
  1076.     return C;
  1077.  
  1078. end;
  1079.  
  1080.  
  1081. #############################################################################
  1082. ##
  1083. #F  DerivedSubgroup( <G> )  . . . . . . . . . . . derived subgroup of a group
  1084. ##
  1085. DerivedSubgroup := function ( G )
  1086.  
  1087.     # check that the argument is a group
  1088.     if not IsGroup( G )  then
  1089.         Error( "<G> must be a group" );
  1090.     fi;
  1091.     InfoGroup1( "#I  DerivedSubgroup: ", GroupString(G,"G"), "\n" );
  1092.  
  1093.     # compute the derived subgroup
  1094.     if not IsBound( G.derivedSubgroup )  then
  1095.         G.derivedSubgroup := G.operations.DerivedSubgroup( G );
  1096.     fi;
  1097.  
  1098.     # return the derived subgroup
  1099.     InfoGroup1( "#I  DerivedSubgroup: ",
  1100.                 GroupString(G.derivedSubgroup,"D"), "\n");
  1101.     return G.derivedSubgroup;
  1102.  
  1103. end;
  1104.  
  1105. GroupOps.DerivedSubgroup := function ( G )
  1106.     local   D,          # derived subgroup of <G>, result
  1107.             i,  j,      # loops
  1108.             comm;       # commutator of two generators of <G>
  1109.  
  1110.     # find the subgroup generated by the commutators of the generators
  1111.     D := TrivialSubgroup( G );
  1112.     for i  in [ 2 .. Length( G.generators ) ]  do
  1113.         for j  in [ 1 .. i - 1 ]  do
  1114.             comm := Comm( G.generators[i], G.generators[j] );
  1115.             if not comm in D  then
  1116.                 D := Closure( D, comm );
  1117.             fi;
  1118.         od;
  1119.     od;
  1120.  
  1121.     # return the normal closure of <D> in <G>
  1122.     return NormalClosure( G, D );
  1123.  
  1124. end;
  1125.  
  1126.  
  1127. #############################################################################
  1128. ##
  1129. #F  FittingSubgroup( <G> )  . . . . . . . . . . . Fitting subgroup of a group
  1130. ##
  1131. FittingSubgroup := function ( G )
  1132.  
  1133.     # check that the argument is a group
  1134.     if not IsGroup( G )  then
  1135.         Error("<G> must be a group");
  1136.     fi;
  1137.     InfoGroup1( "#I  FittingSubgroup: ", GroupString(G,"G"), "\n" );
  1138.  
  1139.     # compute the Fitting subgroup
  1140.     if not IsBound( G.fittingSubgroup )  then
  1141.         G.fittingSubgroup := G.operations.FittingSubgroup( G );
  1142.     fi;
  1143.  
  1144.     # return the Fitting subgroup
  1145.     InfoGroup1( "#I  FittingSubgroup: ",
  1146.                 GroupString(G.fittingSubgroup, "F" ), "\n" );
  1147.     return G.fittingSubgroup;
  1148.  
  1149. end;
  1150.  
  1151. GroupOps.FittingSubgroup := function ( G )
  1152.     local   F;
  1153.  
  1154.     if G.generators = []  then
  1155.         F := G;
  1156.     else
  1157.         F := Subgroup( Parent( G ), Union( List( Set( Factors( Size( G ) ) ),
  1158.                          p -> Core( G, SylowSubgroup(G,p) ).generators ) ) );
  1159.     fi;
  1160.     return F;
  1161.  
  1162. end;
  1163.  
  1164.  
  1165. #############################################################################
  1166. ##
  1167. #F  FrattiniSubgroup( <G> ) . . . . . . . . . .  Frattini subgroup of a group
  1168. ##
  1169. FrattiniSubgroup := function ( G )
  1170.  
  1171.     # check that the argument is a group
  1172.     if not IsGroup( G )  then
  1173.         Error( "<G> must be a group" );
  1174.     fi;
  1175.     InfoGroup1( "#I  FrattiniSubgroup: ", GroupString(G,"G"), "\n" );
  1176.  
  1177.     # compute the Frattini subgroup
  1178.     if not IsBound( G.frattiniSubgroup )  then
  1179.         G.frattiniSubgroup := G.operations.FrattiniSubgroup( G );
  1180.     fi;
  1181.  
  1182.     # return the Frattini subgroup
  1183.     InfoGroup1( "#I  FrattiniSubgroup: ",
  1184.                 GroupString(G.frattiniSubgroup,"F"), "\n");
  1185.     return G.frattiniSubgroup;
  1186.  
  1187. end;
  1188.  
  1189. GroupOps.FrattiniSubgroup := function ( G )
  1190.     Error("sorry, can not compute the Frattini subgroup for <G>");
  1191. end;
  1192.  
  1193.  
  1194. #############################################################################
  1195. ##
  1196. #F  NormalClosure( <G>, <U> ) . . . . normal closure of a subgroup in a group
  1197. ##
  1198. NormalClosure := function ( G, U )
  1199.     local   N;          # normal closure of <U> in <G>, result
  1200.  
  1201.     # check that the arguments are groups with a common parent
  1202.     if not IsGroup( G )  then
  1203.         Error( "<G> must be a group" );
  1204.     elif not IsGroup( U )  then
  1205.         Error( "<U> must be a group" );
  1206.     fi;
  1207.  
  1208.     # <G> and <U> must have a common parent
  1209.     Parent( G, U );
  1210.     InfoGroup1( "#I  NormalClosure: of ", GroupString(U,"U"), " in ",
  1211.                 GroupString(G,"G"), "\n");
  1212.  
  1213.     # compute the normal closure
  1214.     if IsParent( G )  then
  1215.         if not IsBound( U.normalClosure )  then
  1216.             U.normalClosure := G.operations.NormalClosure( G, U );
  1217.         fi;
  1218.         N := U.normalClosure;
  1219.     else
  1220.         N := G.operations.NormalClosure( G, U );
  1221.     fi;
  1222.  
  1223.     # return the normal closure
  1224.     InfoGroup1( "#I  NormalClosure: returns ", GroupString(N,"N"), "\n" );
  1225.     return N;
  1226.  
  1227. end;
  1228.  
  1229. GroupOps.NormalClosure := function ( G, U )
  1230.     local   N,          # normal closure of <U> in <G>, result
  1231.             gensG,      # generators of the group <G>
  1232.             genG,       # one generator of the group <G>
  1233.             gensN,      # generators of the group <N>
  1234.             genN,       # one generator of the group <N>
  1235.             cnj;        # conjugated of a generator of <U>
  1236.  
  1237.     # get a set of generators of <G>
  1238.     if IsFinite( G )  then
  1239.         gensG := G.generators;
  1240.     else
  1241.         gensG := Concatenation(G.generators,List(G.generators,gen->gen^-1));
  1242.     fi;
  1243.  
  1244.     # make a copy of the group to be closed
  1245.     N := ShallowCopy( U );
  1246.     InfoGroup2("#I   |<gens>| = ",Length(N.generators),"\n");
  1247.  
  1248.     # loop over all generators of N
  1249.     gensN := ShallowCopy( N.generators );
  1250.     for genN  in gensN  do
  1251.  
  1252.         # loop over the generators of G
  1253.         for genG  in gensG  do
  1254.  
  1255.             # make sure that the conjugated element is in the closure
  1256.             cnj := genN ^ genG;
  1257.             if not cnj in N  then
  1258.                 InfoGroup2("#I   |<gens>| = ",Length(N.generators),"+1\n");
  1259.                 N := Closure( N, cnj );
  1260.                 Add( gensN, cnj );
  1261.             fi;
  1262.  
  1263.         od;
  1264.  
  1265.     od;
  1266.  
  1267.     # return the normal closure
  1268.     return N;
  1269.  
  1270. end;
  1271.  
  1272.  
  1273. #############################################################################
  1274. ##
  1275. #F  NormalIntersection( <N>, <U> )  . . . . . intersection with normal subgrp
  1276. ##
  1277. GroupOps.NormalIntersection := GroupOps.Intersection;
  1278.  
  1279. NormalIntersection := function( N, U )
  1280.     return N.operations.NormalIntersection( N, U );
  1281. end;
  1282.  
  1283.  
  1284. #############################################################################
  1285. ##
  1286. #F  Normalizer( <G>, <U> )  . . . . . . . . . . . .  normalizer of a subgroup
  1287. ##
  1288. Normalizer := function ( G, U )
  1289.     local   N;          # normalizer of <U> in <G>, result
  1290.  
  1291.     # check that the arguments are groups with a common parent
  1292.     if not IsGroup( G )  then
  1293.         Error( "<G> must be a group" );
  1294.     elif not IsGroup( U )  then
  1295.         Error("<U> must be a group");
  1296.     fi;
  1297.  
  1298.     # <G> and <U> must have a common parent
  1299.     Parent( G, U );
  1300.     InfoGroup1( "#I  Normalizer: of ", GroupString(U,"U"), " in ",
  1301.                 GroupString(G,"G"), "\n");
  1302.  
  1303.     # compute the normalizer
  1304.     if IsParent( G )  then
  1305.         if not IsBound( U.normalizer )  then
  1306.             U.normalizer := G.operations.Normalizer( G, U );
  1307.         fi;
  1308.         N := U.normalizer;
  1309.     else
  1310.         N := G.operations.Normalizer( G, U );
  1311.     fi;
  1312.  
  1313.     # return the normalizer
  1314.     InfoGroup1("#I  Normalizer: returns ",GroupString(N,"N"),"\n");
  1315.     return N;
  1316.  
  1317. end;
  1318.  
  1319. GroupOps.Normalizer := function ( G, U )
  1320.     return Stabilizer( G, U, G.operations.ConjugateSubgroup );
  1321. end;
  1322.  
  1323.  
  1324. #############################################################################
  1325. ##
  1326. #F  PCore( <G>, <p> ) . . . . . . . . . . . . . . . . . . . p-core of a group
  1327. ##
  1328. ##  'PCore' returns the <p>-core of the group <G>, i.e., the  largest  normal
  1329. ##  <p> subgroup of <G>.  This is the core of the <p> Sylow subgroups.
  1330. ##
  1331. PCore := function ( G, p )
  1332.  
  1333.     # check the arguments
  1334.     if not IsGroup( G )  then
  1335.         Error("<G> must be a group");
  1336.     fi;
  1337.     if not IsInt( p )  or p < 0  or not IsPrime( p )  then
  1338.         Error("<p> must be a prime");
  1339.     fi;
  1340.  
  1341.     # compute the <p>-core
  1342.     if not IsBound( G.pCores )  then
  1343.         G.pCores := [];
  1344.     fi;
  1345.     if not IsBound( G.pCores[p] )  then
  1346.         G.pCores[p] := G.operations.PCore( G, p );
  1347.     fi;
  1348.  
  1349.     # return the <p>-core
  1350.     return G.pCores[p];
  1351. end;
  1352.  
  1353. GroupOps.PCore := function ( G, p )
  1354.     return Core( G, SylowSubgroup( G, p ) );
  1355. end;
  1356.  
  1357.  
  1358. #############################################################################
  1359. ##
  1360. #F  Radical( <G> )  . . . . . . . . . . . . . . . . . . .  radical of a group
  1361. ##
  1362. ##  'Radical' returns the radical of <G>, i.e., the largest  normal  solvable
  1363. ##  subgroup of <G>.
  1364. ##
  1365. Radical := function ( G )
  1366.  
  1367.     # check the argument
  1368.     if not IsGroup( G )  then
  1369.         Error("<G> must be a group");
  1370.     fi;
  1371.  
  1372.     # compute the radical
  1373.     if not IsBound( G.radical )  then
  1374.         G.radical := G.operations.Radical( G );
  1375.     fi;
  1376.  
  1377.     # return the radical
  1378.     return G.radical;
  1379. end;
  1380.  
  1381. GroupOps.Radical := function ( G )
  1382.     local   R,  p;
  1383.     if IsSolvable( G )  then
  1384.         R := G;
  1385.     else
  1386.         Error("sorry, cannot compute the radical of <G>");
  1387.     fi;
  1388.     return R;
  1389. end;
  1390.  
  1391.  
  1392. #############################################################################
  1393. ##
  1394. #F  SylowSubgroup( <G>, <p> ) . . . . . . . . . . .  Sylowsubgroup of a group
  1395. ##
  1396. SylowSubgroup := function ( G, p )
  1397.  
  1398.     # check the arguments
  1399.     if not IsGroup( G )  then
  1400.         Error( "<G> must be a group" );
  1401.     elif not IsFinite( G )  then
  1402.         Error( "<G> must be a finite group" );
  1403.     elif not IsInt( p ) or p < 2 or not IsPrime( p )  then
  1404.         Error( "<p> must be a positive prime" );
  1405.     fi;
  1406.     InfoGroup1( "#I  SylowSubgroup: ",GroupString(G,"G"),", <p> = ",p,"\n" );
  1407.  
  1408.     # compute the Sylow subgroup
  1409.     if not IsBound( G.sylowSubgroups )  then
  1410.         G.sylowSubgroups := [];
  1411.     fi;
  1412.     if not IsBound( G.sylowSubgroups[p] )  then
  1413.         G.sylowSubgroups[p] := G.operations.SylowSubgroup( G, p );
  1414.     fi;
  1415.  
  1416.     # return the Sylow subgroup
  1417.     InfoGroup1("#I  SylowSubgroup: ",
  1418.                GroupString(G.sylowSubgroups[p],"S"),"\n");
  1419.     return G.sylowSubgroups[p];
  1420.  
  1421. end;
  1422.  
  1423. GroupOps.SylowSubgroup := function ( G, p )
  1424.     local   S,          # <p>-Sylow subgroup of <G>, result
  1425.             r;          # random element of <G>
  1426.  
  1427.     # repeat until <S> is the full <p>-Sylow subgroup
  1428.     S := TrivialSubgroup( G );
  1429.     while Size( G ) / Size( S ) mod p = 0  do
  1430.  
  1431.         # find an element of order <p> that normalizes <S>
  1432.         repeat
  1433.             repeat
  1434.                 r := Random( G );
  1435.             until Order( G, r ) mod p = 0;
  1436.             r := r ^ (Order( G, r ) / p);
  1437.         until not r in S  and ForAll( S.generators, g -> g ^ r in S );
  1438.  
  1439.         # add it to <S>
  1440.         S := Closure( S, r );
  1441.  
  1442.     od;
  1443.  
  1444.     # return the <p>-Sylow subgroup
  1445.     return S;       
  1446. end;
  1447.  
  1448.  
  1449. #############################################################################
  1450. ##
  1451. #F  TrivialSubgroup( <G> )  . . . . . . . . . . . trivial subgroup of a group
  1452. ##
  1453. TrivialSubgroup := function ( G )
  1454.  
  1455.     # check that the argument is a group
  1456.     if not IsGroup( G )  then
  1457.         Error( "<G> must be a group" );
  1458.     fi;
  1459.  
  1460.     # return the trivial subgroup
  1461.     if not IsBound( G.trivialSubgroup )  then
  1462.         G.trivialSubgroup := G.operations.TrivialSubgroup( G );
  1463.     fi;
  1464.     return G.trivialSubgroup;
  1465.  
  1466. end;
  1467.  
  1468. GroupOps.TrivialSubgroup := function ( G )
  1469.     local   T;
  1470.  
  1471.     # check if <G> is a parent group
  1472.     if IsBound( G.parent )  then
  1473.         T := Subgroup( G.parent, [] );
  1474.     else
  1475.         T := Subgroup( G, [] );
  1476.     fi;
  1477.  
  1478.     # add the set of elements
  1479.     T.elements := [ T.identity ];
  1480.     return T;
  1481.  
  1482. end;
  1483.  
  1484.  
  1485. #############################################################################
  1486. ##
  1487.  
  1488. #F  DerivedSeries( <G> )  . . . . . . . . . . . . . derived series of a group
  1489. ##
  1490. DerivedSeries := function ( G )
  1491.  
  1492.     # check that the argument is a group
  1493.     if not IsGroup( G )  then
  1494.         Error( "<G> must be a group" );
  1495.     fi;
  1496.     InfoGroup1( "#I  DerivedSeries: ", GroupString(G,"G"), "\n" );
  1497.  
  1498.     # compute the derived series
  1499.     if not IsBound( G.derivedSeries )  then
  1500.         G.derivedSeries := G.operations.DerivedSeries( G );
  1501.     fi;
  1502.  
  1503.     # return the derived series
  1504.     InfoGroup1( "#I  DerivedSeries returns series of length ",
  1505.                 Length(G.derivedSeries),"\n");
  1506.     return G.derivedSeries;
  1507.  
  1508. end;
  1509.  
  1510. GroupOps.DerivedSeries := function ( G )
  1511.     local   S,          # derived series of <G>, result
  1512.             D;          # derived subgroups
  1513.  
  1514.     # print out a warning for infinite groups
  1515.     if not IsFinite( G )  then
  1516.         Print("#W  DerivedSeries: may not stop for infinite group <G>\n");
  1517.     fi;
  1518.  
  1519.     # compute the series by repeated calling of 'DerivedSubgroup'
  1520.     S := [ G ];
  1521.     InfoGroup2( "#I  DerivedSeries: step ", Length(S), "\n" );
  1522.     D := DerivedSubgroup( G );
  1523.     while D <> S[ Length(S) ]  do
  1524.         Add( S, D );
  1525.         InfoGroup2( "#I  DerivedSeries: step ", Length(S), "\n" );
  1526.         D := DerivedSubgroup( D );
  1527.     od;
  1528.  
  1529.     # return the series when it becomes stable
  1530.     return S;
  1531.  
  1532. end;
  1533.  
  1534.  
  1535. #############################################################################
  1536. ##
  1537. #F  ElementaryAbelianSeries( <G> )  . .  elementary abelian series of a group
  1538. ##
  1539. ElementaryAbelianSeries := function( G )
  1540.     local   L,  i;
  1541.  
  1542.     # if <G> is a list compute a elementary series through a given normal one
  1543.     if IsList( G )  then
  1544.         if not IsSolvable( G[1] )  then
  1545.             Error( "<G> must be solvable" );
  1546.         fi;
  1547.         for i  in [ 1 .. Length(G)-1 ]  do
  1548.           if not IsNormal(G[1],G[i+1]) or not IsSubgroup(G[i],G[i+1])  then
  1549.               Error( "<G> must be normal series" );
  1550.           fi;
  1551.         od;
  1552.         L := G[1].operations.ElementaryAbelianSeries( G );
  1553.  
  1554.     # otherwise compute a elementary series if it is not known
  1555.     else
  1556.         if not IsSolvable( G )  then
  1557.             Error( "<G> must be solvable" );
  1558.         fi;
  1559.         if not IsBound( G.elementaryAbelianSeries )  then
  1560.             L := G.operations.ElementaryAbelianSeries( G );
  1561.             G.elementaryAbelianSeries := L;
  1562.         else
  1563.             L := G.elementaryAbelianSeries;
  1564.         fi;
  1565.     fi;
  1566.     return L;
  1567.  
  1568. end;
  1569.  
  1570. GroupOps.ElementaryAbelianSeries := function( G )
  1571.     local   A,  f,  L;
  1572.  
  1573.     # if <G> is a list convert all groups in that list
  1574.     if IsList( G )  then
  1575.         A := AgGroup( G[1] );
  1576.         f := A.bijection^-1;
  1577.         L := A.operations.ElementaryAbelianSeries(List(G,x->Image(f,x)));
  1578.         f := A.bijection;
  1579.  
  1580.     # convert <G> into an ag group
  1581.     else
  1582.         A := AgGroup( G );
  1583.         f := A.bijection;
  1584.         L := A.operations.ElementaryAbelianSeries( Image( f^-1, G ) );
  1585.     fi;
  1586.  
  1587.     # convert back into <G>
  1588.     return List( L, x -> Image( f, x ) );
  1589.  
  1590. end;
  1591.  
  1592.  
  1593. #############################################################################
  1594. ##
  1595. #F  CompositionSeries( <G> )  . . . . . . . . . composition series of a group
  1596. ##
  1597. CompositionSeries := function ( G )
  1598.  
  1599.     if not IsBound( G.compositionSeries )  then
  1600.         G.compositionSeries := G.operations.CompositionSeries(G);
  1601.     fi;
  1602.     return G.compositionSeries;
  1603.  
  1604. end;
  1605.  
  1606. GroupOps.CompositionSeries := function( G )
  1607.     Error( "cannot compute the composition series of <G>" );
  1608. end;
  1609.  
  1610.  
  1611. #############################################################################
  1612. ##
  1613. #F  LowerCentralSeries( <G> ) . . . . . . . . lower central series of a group
  1614. ##
  1615. LowerCentralSeries := function ( G )
  1616.  
  1617.     # check that the argument is a group
  1618.     if not IsGroup( G )  then
  1619.         Error( "<G> must be a group" );
  1620.     fi;
  1621.     InfoGroup1( "#I  LowerCentralSeries: ", GroupString(G,"G"), "\n" );
  1622.  
  1623.     # compute the lower central series
  1624.     if not IsBound( G.lowerCentralSeries )  then
  1625.         G.lowerCentralSeries := G.operations.LowerCentralSeries( G );
  1626.     fi;
  1627.  
  1628.     # return the lower central series
  1629.     InfoGroup1( "#I  LowerCentralSeries: returns series of length ",
  1630.                 Length(G.lowerCentralSeries), "\n" );
  1631.     return G.lowerCentralSeries;
  1632.  
  1633. end;
  1634.  
  1635. GroupOps.LowerCentralSeries := function ( G )
  1636.     local   S,          # lower central series of <G>, result
  1637.             C;          # commutator subgroups
  1638.  
  1639.     # print out a warning for infinite groups
  1640.     if not IsFinite( G )  then
  1641.       Print("#W  LowerCentralSeries: may not stop for infinite group <G>\n");
  1642.     fi;
  1643.  
  1644.     # compute the series by repeated calling of 'CommutatorSubgroup'
  1645.     S := [ G ];
  1646.     InfoGroup2( "#I  LowerCentralSeries: step ", Length(S), "\n" );
  1647.     C := DerivedSubgroup( G );
  1648.     while C <> S[ Length(S) ]  do
  1649.         Add( S, C );
  1650.         InfoGroup2( "#I  LowerCentralSeries: step ", Length(S), "\n" );
  1651.         C := CommutatorSubgroup( G, C );
  1652.     od;
  1653.  
  1654.     # return the series when it becomes stable
  1655.     return S;
  1656.  
  1657. end;
  1658.  
  1659.  
  1660. #############################################################################
  1661. ##
  1662. #F  NormalSubgroups( <G> )  . . . . . . . . . . . normal subgroups of a group
  1663. ##
  1664. NormalSubgroups := function ( G )
  1665.  
  1666.     # check that the argument is a group
  1667.     if not IsGroup( G )  then
  1668.         Error( "<G> must be a group" );
  1669.     fi;
  1670.     InfoGroup1( "#I  NormalSubgroups: ", GroupString(G,"G"), "\n" );
  1671.  
  1672.     # compute the normal subgroups
  1673.     if not IsBound( G.normalSubgroups )  then
  1674.         G.normalSubgroups := G.operations.NormalSubgroups( G );
  1675.     fi;
  1676.  
  1677.     # return the normal subgroups
  1678.     InfoGroup1("#I  NormalSubgroups: returns ",
  1679.                 Length(G.normalSubgroups)," subgroups\n");
  1680.     return G.normalSubgroups;
  1681.  
  1682. end;
  1683.  
  1684. GroupOps.NormalSubgroups := function ( G )
  1685.     local   nrm;        # normal subgroups of <G>, result
  1686.  
  1687.     # compute the normal subgroup lattice above the trivial subgroup
  1688.     nrm := G.operations.NormalSubgroupsAbove(G,Subgroup(Parent(G),[]),[]);
  1689.  
  1690.     # sort the normal subgroups according to their size
  1691.     Sort( nrm, function( a, b ) return Size( a ) < Size( b ); end );
  1692.  
  1693.     # and return it
  1694.     return nrm;
  1695.  
  1696. end;
  1697.  
  1698. GroupOps.NormalSubgroupsAbove := function ( G, N, avoid )
  1699.     local   R,          # normal subgroups above <N>, result
  1700.             C,          # one conjugacy class of <G>
  1701.             g,          # representative of a conjugacy class of <G>
  1702.             M;          # normal closure of <N> and <g>
  1703.  
  1704.     # initialize the list of normal subgroups
  1705.     InfoGroup1("#I    normal subgroup of order ",Size(N),"\n");
  1706.     R := [ N ];
  1707.  
  1708.     # make a shallow copy of avoid, because we are going to change it
  1709.     avoid := ShallowCopy( avoid );
  1710.  
  1711.     # for all representative that need not be avoided and do not ly in <N>
  1712.     for C  in ConjugacyClasses( G )  do
  1713.         g := Representative( C );
  1714.  
  1715.         if not g in avoid  and not g in N  then
  1716.  
  1717.             # compute the normal closure of <N> and <g> in <G>
  1718.             M := NormalClosure( G, Closure( N, g ) );
  1719.             if ForAll( avoid, rep -> not rep in M )  then
  1720.                 Append( R, G.operations.NormalSubgroupsAbove(G,M,avoid) );
  1721.             fi;
  1722.  
  1723.             # from now on avoid this representative
  1724.             Add( avoid, g );
  1725.         fi;
  1726.     od;
  1727.  
  1728.     # return the list of normal subgroups
  1729.     return R;
  1730.  
  1731. end;
  1732.  
  1733.  
  1734. #############################################################################
  1735. ##
  1736. #F  PCentralSeries( <G>, <p> )  . . . . . .  . . . . . . . <p>-central series
  1737. ##
  1738. PCentralSeries := function ( G, p )
  1739.  
  1740.     # <p> must be a prime
  1741.     if not IsPrimeInt( p )  then
  1742.         Error( "<p> must be a prime" );
  1743.     fi;
  1744.  
  1745.     # check if already know this p-central series
  1746.     if not IsBound( G.pCentralSeries )  then
  1747.         G.pCentralSeries := [];
  1748.     fi;
  1749.     if not IsBound( G.pCentralSeries[p] )  then
  1750.         G.pCentralSeries[p] := G.operations.PCentralSeries( G, p );
  1751.     fi;
  1752.     return G.pCentralSeries[p];
  1753.  
  1754. end;
  1755.  
  1756. GroupOps.PCentralSeries := function( G, p )
  1757.     local   i,  L,  C,  S,  N,  P;
  1758.  
  1759.     # Start with <G>.
  1760.     L := [];
  1761.     N := G;
  1762.     repeat
  1763.         Add( L, N );
  1764.         S := N;
  1765.         C := CommutatorSubgroup( G, S );
  1766.         P := Subgroup( Parent(G), List( S.generators, x -> x ^ p ) );
  1767.         N := Closure( C, P );
  1768.     until N = S;
  1769.     return L;
  1770.  
  1771. end;
  1772.  
  1773.  
  1774. #############################################################################
  1775. ##
  1776. #F  SubnormalSeries( <G>, <U> ) . subnormal series from a group to a subgroup
  1777. ##
  1778. SubnormalSeries := function ( G, U )
  1779.     local   S;          # subnormal series of <U> in <G>, result
  1780.  
  1781.     # check thet the arguments are groups with a common parent
  1782.     if not IsGroup( G )  then
  1783.         Error( "<G> must be a group" );
  1784.     elif not IsGroup( U )  then
  1785.         Error( "<U> must be a group" );
  1786.     fi;
  1787.  
  1788.     # <G> and <U> must have a common parent
  1789.     Parent( G, U );
  1790.     InfoGroup1( "#I  SubnormalSeries: of ", GroupString(U,"U"), " in ",
  1791.                 GroupString(G,"G"), "\n");
  1792.  
  1793.     # compute the subnormal series
  1794.     if IsParent( G )  then
  1795.         if not IsBound( U.subnormalSeries )  then
  1796.             U.subnormalSeries := G.operations.SubnormalSeries( G, U );
  1797.         fi;
  1798.         S := U.subnormalSeries;
  1799.     else
  1800.         #N 9-Dec-91 fceller: we could use a subnormal series of the parent
  1801.         S := G.operations.SubnormalSeries( G, U );
  1802.     fi;
  1803.  
  1804.     # return the result
  1805.     InfoGroup1( "#I  SubnormalSeries: returns series of length ",
  1806.                 Length( S ),"\n");
  1807.     return S;
  1808.  
  1809. end;
  1810.  
  1811. GroupOps.SubnormalSeries := function ( G, U )
  1812.     local   S,          # subnormal series of <U> in <G>, result
  1813.             C;          # normal closure of <U> in <G> resp. <C>
  1814.  
  1815.     # compute the subnormal series by repeated calling of 'NormalClosure'
  1816.     S := [ G ];
  1817.     InfoGroup2( "#I  SubnormalSeries: step ", Length(S), "\n" );
  1818.     C := NormalClosure( G, U );
  1819.     while C <> S[ Length( S ) ]  do
  1820.         Add( S, C );
  1821.         InfoGroup2( "#I  SubnormalSeries: step ", Length(S), "\n" );
  1822.         C := NormalClosure( C, U );
  1823.     od;
  1824.  
  1825.     # return the series
  1826.     return S;
  1827.  
  1828. end;
  1829.  
  1830.  
  1831. #############################################################################
  1832. ##
  1833. #F  UpperCentralSeries( <G> ) . . . . . . . . upper central series of a group
  1834. ##
  1835. UpperCentralSeries := function ( G )
  1836.  
  1837.     # check that the argument is a group
  1838.     if not IsGroup( G )  then
  1839.         Error( "<G> must be a group" );
  1840.     fi;
  1841.     InfoGroup1( "#I  UpperCentralSeries: ", GroupString(G,"G"), "\n" );
  1842.  
  1843.     # compute the upper central series
  1844.     if not IsBound( G.upperCentralSeries )  then
  1845.         G.upperCentralSeries := G.operations.UpperCentralSeries( G );
  1846.     fi;
  1847.  
  1848.     # return the upper central series
  1849.     InfoGroup1( "#I  UpperCentralSeries: returns series of length ",
  1850.                 Length(G.upperCentralSeries), "\n" );
  1851.     return G.upperCentralSeries;
  1852.  
  1853. end;
  1854.  
  1855. GroupOps.UpperCentralSeries := function ( G )
  1856.     local   S,          # upper central series of <G>, result
  1857.             C,          # centre
  1858.             hom;        # homomorphisms of <G> to '<G>/<C>'
  1859.  
  1860.     # print out a warning for infinite groups
  1861.     if not IsFinite( G )  then
  1862.       Print("#W  UpperCentralSeries: may not stop for infinite group <G>\n");
  1863.     fi;
  1864.  
  1865.     # compute the series by repeated calling of 'CommutatorSubgroup'
  1866.     S := [ TrivialSubgroup( G ) ];
  1867.     InfoGroup2( "#I  UpperCentralSeries: step ", Length(S), "\n" );
  1868.     C := Centre( G );
  1869.     while C <> S[ Length(S) ]  do
  1870.         Add( S, C );
  1871.         InfoGroup2( "#I  UpperCentralSeries: step ", Length(S), "\n" );
  1872.         hom := NaturalHomomorphism( G, G / C );
  1873.         C := PreImage( hom, Centre( hom.range ) );
  1874.     od;
  1875.  
  1876.     # return the series when it becomes stable
  1877.     return Reversed( S );
  1878.  
  1879. end;
  1880.  
  1881.  
  1882. #############################################################################
  1883. ##
  1884.  
  1885. #F  IsAbelian( <G> )  . . . . . . . . . . . . . .  test if a group is abelian
  1886. ##
  1887. IsAbelian := function ( G )
  1888.  
  1889.     # check that the argument is a group
  1890.     if not IsGroup( G )  then
  1891.         Error( "<G> must be a group" );
  1892.     fi;
  1893.     InfoGroup1( "#I  IsAbelian: ", GroupString(G,"G"), "\n" );
  1894.  
  1895.     # test if the group is abelian
  1896.     if not IsBound( G.isAbelian )  then
  1897.         G.isAbelian := G.operations.IsAbelian( G );
  1898.     fi;
  1899.  
  1900.     # return the result
  1901.     InfoGroup1( "#I  IsAbelian: returns ", G.isAbelian, "\n" );
  1902.     return G.isAbelian;
  1903.  
  1904. end;
  1905.  
  1906. GroupOps.IsAbelian := function ( G )
  1907.     local   i, j;       # loop variables
  1908.  
  1909.     # test if every generator commutes with all the others
  1910.     for i  in [ 2 .. Length(G.generators) ]  do
  1911.         for j  in [ 1 .. i-1 ]  do
  1912.             if Comm( G.generators[i], G.generators[j] ) <> G.identity  then
  1913.                 return false;
  1914.             fi;
  1915.         od;
  1916.     od;
  1917.  
  1918.     # all generators commute, return 'true'
  1919.     return true;
  1920.  
  1921. end;
  1922.  
  1923.  
  1924. #############################################################################
  1925. ##
  1926. #F  IsCentral( <G>, <U> ) . . . . . test if a group is centralizer by another
  1927. ##
  1928. IsCentral := function ( G, U )
  1929.     local   isCen;      # 'true' if <U> is central in <G>, result
  1930.  
  1931.     # check that the arguments are groups with a common parent
  1932.     if not IsGroup( G )  then
  1933.         Error( "<G> must be a group" );
  1934.     elif not IsGroup( U )  then
  1935.         Error( "<U> must be a group" );
  1936.     fi;
  1937.  
  1938.     # <U> and <G> must have a common parent
  1939.     Parent( G, U );
  1940.     InfoGroup1( "#I  IsCentral: is ", GroupString(U,"U"),
  1941.                 " central in ", GroupString(G,"G"), "\n");
  1942.  
  1943.     # if <G> is the parent, use the entry '<U>.isCentral'
  1944.     if IsParent( G )  then
  1945.         if not IsBound( U.isCentral )  then
  1946.             U.isCentral := G.operations.IsCentral( G, U );
  1947.         fi;
  1948.         isCen := U.isCentral;
  1949.  
  1950.     # otherwise
  1951.     else
  1952.         if IsBound( U.isCentral ) and U.isCentral  then
  1953.             isCen := true;
  1954.         else
  1955.             isCen := G.operations.IsCentral( G, U );
  1956.         fi;
  1957.     fi;
  1958.  
  1959.     # return the result
  1960.     InfoGroup1( "#I  IsCentral: returns ", isCen, "\n" );
  1961.     return isCen;
  1962.  
  1963. end;
  1964.  
  1965. GroupOps.IsCentral := function ( G, U )
  1966.     local   g,          # one generator of <G>
  1967.             u;          # one generator of <U>
  1968.  
  1969.     # test if all generators of <U> are fixed by the generators of <G>
  1970.     for u  in U.generators  do
  1971.         for g  in G.generators  do
  1972.             if Comm( u, g ) <> U.identity  then
  1973.                 return false;
  1974.             fi;
  1975.         od;
  1976.     od;
  1977.  
  1978.     # all generators of <U> are fixed, return 'true'
  1979.     return true;
  1980.  
  1981. end;
  1982.  
  1983.  
  1984. #############################################################################
  1985. ##
  1986. #F  IsConjugate(<G>,<x>,<y>)  . test if two objects are conjugated in a group
  1987. ##
  1988. IsConjugate := function ( G, x, y )
  1989.     local   isConj;     # 'true' if <x> and <y> are conjugated, result
  1990.  
  1991.     # check the arguments
  1992.     if not IsGroup( G )  then
  1993.         Error( "<G> must be a group" );
  1994.     fi;
  1995.     if IsGroup( x )  then
  1996.         Parent( G, x, y );
  1997.     else
  1998.         if not x in Parent(G)  or not y in Parent(G)  then
  1999.             Error( "<x> and <y> must lie in the parent group of <G>" );
  2000.         fi;
  2001.     fi;
  2002.     InfoGroup1( "#I  IsConjugate: is <x> conjugated to <y> in ",
  2003.                 GroupString(G,"G"), "\n");
  2004.  
  2005.     # test if <x> and <y> are conjugated in <G>
  2006.     isConj := G.operations.IsConjugate( G, x, y );
  2007.  
  2008.     # return the result
  2009.     InfoGroup1( "#I  IsConjugate: returns ",isConj,"\n" );
  2010.     return isConj;
  2011.  
  2012. end;
  2013.  
  2014. GroupOps.IsConjugate := function ( G, x, y )
  2015.     return RepresentativeOperation( G, x, y ) <> false;
  2016. end;
  2017.  
  2018.  
  2019. #############################################################################
  2020. ##
  2021. #F  IsCyclic( <G> ) . . . . . . . . . . . . . . . . test if a group is cyclic
  2022. ##
  2023. IsCyclic := function ( G )
  2024.  
  2025.     # check that the argument is a group
  2026.     if not IsGroup( G )  then
  2027.         Error( "<G> must be a group" );
  2028.     fi;
  2029.     InfoGroup1( "#I  IsCyclic: ", GroupString(G,"G"), "\n" );
  2030.  
  2031.     # test if <G> is cyclic
  2032.     if not IsBound( G.isCyclic )  then
  2033.         G.isCyclic := G.operations.IsCyclic( G );
  2034.     fi;
  2035.  
  2036.     # return the result
  2037.     InfoGroup1( "#I  IsCyclic: returns ", G.isCyclic, "\n" );
  2038.     return G.isCyclic;
  2039.  
  2040. end;
  2041.  
  2042. GroupOps.IsCyclic := function ( G )
  2043.     local   isCyclic;   # 'true' if <G> is cyclic, result
  2044.  
  2045.     # if <G> is not abelian it is certainly not cyclic
  2046.     if not IsAbelian( G )  then
  2047.         isCyclic := false;
  2048.  
  2049.     # if <G> has only one generator it is certainly cyclic
  2050.     elif Length( G.generators ) <= 1  then
  2051.         isCyclic := true;
  2052.  
  2053.     # if <G> is finite, test if the <p>-th powers of the generators
  2054.     # generate a subgroup of index <p> for all prime divisors <p>
  2055.     elif IsFinite( G )  then
  2056.         isCyclic := ForAll( Set( Factors( Size( G ) ) ),
  2057.                 p -> Index( G, Subgroup( Parent( G ),
  2058.                                          List(G.generators,g->g^p)) ) = p );
  2059.  
  2060.     # otherwise test if the abelian invariants are that of $Z$
  2061.     else
  2062.         isCyclic := AbelianInvariants( G ) = [ 0 ];
  2063.     fi;
  2064.  
  2065.     # return the result
  2066.     return isCyclic;
  2067.  
  2068. end;
  2069.  
  2070.  
  2071. #############################################################################
  2072. ##
  2073. #F  IsElementaryAbelian( <G> )  . . . . test if a group is elementary abelian
  2074. ##
  2075. IsElementaryAbelian := function ( G )
  2076.  
  2077.     # check that the argument is a group
  2078.     if not IsGroup( G )  then
  2079.         Error( "<G> must be a group" );
  2080.     fi;
  2081.     InfoGroup1( "#I  IsElementaryAbelian: ", GroupString(G,"G"), "\n" );
  2082.  
  2083.     # test if the group is elementary abelian
  2084.     if not IsBound( G.isElementaryAbelian )  then
  2085.         G.isElementaryAbelian := G.operations.IsElementaryAbelian( G );
  2086.     fi;
  2087.  
  2088.     # return the result
  2089.     InfoGroup1( "#I  ",
  2090.                 "IsElementaryAbelian: returns ",G.isElementaryAbelian,"\n" );
  2091.     return G.isElementaryAbelian;
  2092.  
  2093. end;
  2094.  
  2095. GroupOps.IsElementaryAbelian := function ( G )
  2096.     local   isEla,      # 'true' if <G> is elementary abelian, result
  2097.             p;          # order of one generator of <G>
  2098.  
  2099.     # if <G> is not abelian it is certainly not elementary abelian
  2100.     if not IsAbelian( G )  then
  2101.         isEla := false;
  2102.  
  2103.     # if <G> is trivial it is certainly elementary abelian
  2104.     elif IsTrivial( G )  then
  2105.         isEla := true;
  2106.  
  2107.     # if <G> is infinite it is certainly not elementary abelian
  2108.     elif IsBound( G.isFinite ) and not G.isFinite  then
  2109.         isEla := false;
  2110.  
  2111.     # otherwise compute the order of the first generator
  2112.     else
  2113.         p := Order( G, G.generators[1] );
  2114.  
  2115.         # if the order is not a prime <G> is certainly not elementary abelian
  2116.         if not IsPrime( p )  then
  2117.             isEla := false;
  2118.  
  2119.         # otherwise test that all other generators have order <p>
  2120.         else
  2121.             isEla := ForAll( G.generators, gen -> gen^p = G.identity );
  2122.         fi;
  2123.  
  2124.     fi;
  2125.  
  2126.     # return the result
  2127.     return isEla;
  2128.  
  2129. end;
  2130.  
  2131.  
  2132. #############################################################################
  2133. ##
  2134. #F  IsNilpotent( <G> )  . . . . . . . . . . . .  test if a group is nilpotent
  2135. ##
  2136. IsNilpotent := function ( G )
  2137.  
  2138.     # check that the argument is a group
  2139.     if not IsGroup( G )  then
  2140.         Error( "<G> must be a group" );
  2141.     fi;
  2142.     InfoGroup1( "#I  IsNilpotent: ", GroupString(G,"G"), "\n" );
  2143.  
  2144.     # test if <G> is nilpotent
  2145.     if not IsBound( G.isNilpotent )  then
  2146.         G.isNilpotent := G.operations.IsNilpotent( G );
  2147.     fi;
  2148.  
  2149.     # return the result
  2150.     InfoGroup1( "#I  IsNilpotent: returns ", G.isNilpotent, "\n" );
  2151.     return G.isNilpotent;
  2152.  
  2153. end;
  2154.  
  2155. GroupOps.IsNilpotent := function ( G )
  2156.     local   S;          # lower central series of <G>
  2157.  
  2158.     # give a warning if the group is infinite
  2159.     if not IsFinite( G )  then
  2160.         Print( "#W  IsNilpotent: may not stop for infinite group <G>" );
  2161.     fi;
  2162.  
  2163.     # compute the lower central series
  2164.     S := LowerCentralSeries( G );
  2165.  
  2166.     # <G> is nilpotent if the lower central series reaches the trivial group
  2167.     return IsTrivial( S[ Length( S ) ] );
  2168.  
  2169. end;
  2170.  
  2171.  
  2172. #############################################################################
  2173. ##
  2174. #F  IsNormal( <G>, <U> )  . . . . .  test if a group is normalizer by another
  2175. ##
  2176. IsNormal := function ( G, U )
  2177.     local   isNor;      # 'true' if <U> is normal in <G>, result
  2178.  
  2179.     # check that the arguments are groups with a common parent
  2180.     if not IsGroup( G )  then
  2181.         Error( "<G> must be a group" );
  2182.     elif not IsGroup( U )  then
  2183.         Error("<U> must be a group");
  2184.     fi;
  2185.  
  2186.     # <U> and <G> must have a common parent
  2187.     Parent( G, U );
  2188.     InfoGroup1( "#I  IsNormal: is ", GroupString(U,"U"),
  2189.                 " normal in ", GroupString(G,"G"), "\n" );
  2190.  
  2191.     # if <G> is the parent, use the entry '<U>.isNormal'
  2192.     if IsParent( G )  then
  2193.         if not IsBound( U.isNormal )  then
  2194.             U.isNormal := G.operations.IsNormal( G, U );
  2195.         fi;
  2196.         isNor := U.isNormal;
  2197.  
  2198.     # otherwise
  2199.     else
  2200.         if IsBound( U.isNormal )  and U.isNormal  then
  2201.             isNor := true;
  2202.         else
  2203.             isNor := G.operations.IsNormal( G, U );
  2204.         fi;
  2205.     fi;
  2206.  
  2207.     # return the result
  2208.     InfoGroup1( "#I  IsNormal: returns ", isNor, "\n" );
  2209.     return isNor;
  2210.  
  2211. end;
  2212.  
  2213. GroupOps.IsNormal := function ( G, U )
  2214.     local   gens,       # generators of <G>
  2215.             gen,        # one generator of <G>
  2216.             u;          # one generator of <U>
  2217.  
  2218.     # get a generating system of <G>
  2219.     if IsFinite( G )  then
  2220.         gens := Set( G.generators );
  2221.     else
  2222.         gens := ShallowCopy( G.generators );
  2223.         Append( gens, List( G.generators, gen -> gen ^ -1 ) );
  2224.     fi;
  2225.  
  2226.     # test if all generators of <U> are left in <U>
  2227.     for u  in U.generators  do
  2228.         for gen  in gens  do
  2229.             if not u^gen in U  then
  2230.                 return false;
  2231.             fi;
  2232.         od;
  2233.     od;
  2234.  
  2235.     # all generators of <U> are left in <U>, return 'true'
  2236.     return true;
  2237.  
  2238. end;
  2239.  
  2240.  
  2241. #############################################################################
  2242. ##
  2243. #F  IsPerfect( <G> )  . . . . . . . . . . . . . .  test if a group is perfect
  2244. ##
  2245. IsPerfect := function ( G )
  2246.  
  2247.     # check that the argument is a group
  2248.     if not IsGroup( G )  then
  2249.         Error( "<G> must be a group" );
  2250.     fi;
  2251.     InfoGroup1( "#I  IsPerfect: ", GroupString(G,"G"), "\n" );
  2252.  
  2253.     # test if <G> is perfect
  2254.     if not IsBound( G.isPerfect )  then
  2255.         G.isPerfect := G.operations.IsPerfect( G );
  2256.     fi;
  2257.  
  2258.     # return the result
  2259.     InfoGroup1( "#I  IsPerfect: returns ", G.isPerfect, "\n" );
  2260.     return G.isPerfect;
  2261.  
  2262. end;
  2263.  
  2264. GroupOps.IsPerfect := function ( G )
  2265.     local   isPerfect;  # 'true' if <G> is perfect, result
  2266.  
  2267.     # if the group is finite test the index of the derived subgroup
  2268.     if IsFinite( G )  then
  2269.         isPerfect := Index( G, DerivedSubgroup( G ) ) = 1;
  2270.  
  2271.     # otherwise test the abelian invariants of the commutator factor group
  2272.     else
  2273.         isPerfect := AbelianInvariants( CommutatorFactorGroup( G ) ) = [];
  2274.     fi;
  2275.  
  2276.     # return the result
  2277.     return isPerfect;
  2278.  
  2279. end;
  2280.  
  2281.  
  2282. #############################################################################
  2283. ##
  2284. #F  IsSimple( <G> ) . . . . . . . . . . . . . . . . test if a group is simple
  2285. ##
  2286. IsSimple := function ( G )
  2287.  
  2288.     # check that the argument is a group
  2289.     if not IsGroup( G )  then
  2290.         Error( "<G> must be a group" );
  2291.     fi;
  2292.     InfoGroup1( "#I  IsSimple: ", GroupString(G,"G"), "\n" );
  2293.  
  2294.     # test if <G> is simple
  2295.     if not IsBound( G.isSimple )  then
  2296.         G.isSimple := G.operations.IsSimple( G );
  2297.     fi;
  2298.  
  2299.     # return the result
  2300.     InfoGroup1( "#I  IsSimple: returns ", G.isSimple, "\n" );
  2301.     return G.isSimple;
  2302.  
  2303. end;
  2304.  
  2305. GroupOps.IsSimple := function ( G )
  2306.     local   C,          # one conjugacy class of <G>
  2307.             g;          # representative of <C>
  2308.  
  2309.     # loop over the conjugacy classes
  2310.     for C  in ConjugacyClasses( G )  do
  2311.         g := Representative( C );
  2312.         if g <> G.identity
  2313.             and NormalClosure( G, Subgroup( Parent(G), [ g ] ) ) <> G
  2314.         then
  2315.             return false;
  2316.         fi;
  2317.     od;
  2318.  
  2319.     # all classes generate the full group
  2320.     return true;
  2321. end;
  2322.  
  2323.  
  2324. #############################################################################
  2325. ##
  2326. #F  IsSolvable( <G> ) . . . . . . . . . . . . . . test if a group is solvable
  2327. ##
  2328. IsSolvable := function ( G )
  2329.  
  2330.     # check that the argument is a group
  2331.     if not IsGroup( G )  then
  2332.         Error( "<G> must be a group" );
  2333.     fi;
  2334.     InfoGroup1( "#I  IsSolvable: ", GroupString(G,"G"), "\n" );
  2335.  
  2336.     # test if <G> is solvable
  2337.     if not IsBound( G.isSolvable )  then
  2338.         if IsBound( G.isNilpotent ) and G.isNilpotent  then
  2339.             G.isSolvable := true;
  2340.         elif IsBound( G.isAbelian ) and G.isAbelian  then
  2341.             G.isSolvable := true;
  2342.         else
  2343.             G.isSolvable := G.operations.IsSolvable( G );
  2344.         fi;
  2345.     fi;
  2346.  
  2347.     # return the result
  2348.     InfoGroup1( "#I  IsSolvable: returns ", G.isSolvable, "\n" );
  2349.     return G.isSolvable;
  2350.  
  2351. end;
  2352.  
  2353. GroupOps.IsSolvable := function ( G )
  2354.     local   S;          # derived series of <G>
  2355.  
  2356.     # give a warning for infinite groups, where this may run forever
  2357.     if not IsFinite( G )  then
  2358.         Print( "#W  IsSolvable: may not stop for infinite group <G>" );
  2359.     fi;
  2360.  
  2361.     # compute the derived series of <G>
  2362.     S := DerivedSeries( G );
  2363.  
  2364.     # the group is solvable if the derived series reaches the trivial group
  2365.     return IsTrivial( S[ Length( S ) ] );
  2366.  
  2367. end;
  2368.  
  2369.  
  2370. #############################################################################
  2371. ##
  2372. #F  IsSubgroup( <G>, <U> )  . . . .  test if a group is a subgroup of another
  2373. ##
  2374. IsSubgroup := function ( G, U )
  2375.     local   isSub;
  2376.  
  2377.     # check that the arguments are groups with a common parent
  2378.     if not IsGroup( G )  then
  2379.         Error( "<G> must be a group" );
  2380.     elif not IsGroup( U )  then
  2381.         Error( "<U> must be a group" );
  2382.     fi;
  2383.     Parent( G, U );
  2384.     InfoGroup1( "#I  IsSubgroup: is ", GroupString(U,"U"),
  2385.                 " a subgroup of ", GroupString(G,"G"), "\n");
  2386.  
  2387.     # test if <U> is a subgroup of <G>
  2388.     if IsParent( G )  then
  2389.         isSub := true;
  2390.     else
  2391.         isSub := G.operations.IsSubgroup( G, U );
  2392.     fi;
  2393.  
  2394.     # return the result
  2395.     InfoGroup1( "#I  IsSubgroup: returns ", isSub, "\n" );
  2396.     return isSub;
  2397.  
  2398. end;
  2399.  
  2400. GroupOps.IsSubgroup := function ( G, U )
  2401.     local   isSub;      # 'true' if <U> is a subgroup of <G>, result
  2402.  
  2403.     # if the elements of <G> are known use then
  2404.     if IsBound( G.elements )  then
  2405.         isSub := IsSubsetSet( G.elements, Set( U.generators ) );
  2406.  
  2407.     # otherwise test if the generators lie in <G>
  2408.     else
  2409.         isSub := ForAll( U.generators, gen -> gen in G );
  2410.     fi;
  2411.  
  2412.     # return the result
  2413.     return isSub;
  2414.  
  2415. end;
  2416.  
  2417.  
  2418. #############################################################################
  2419. ##
  2420. #F  IsSubnormal( <G>, <U> ) . . . . . test if a group is subnormal in another
  2421. ##
  2422. IsSubnormal := function ( G, U )
  2423.     local   isSub;
  2424.  
  2425.     # check that the arguments are groups with a common parent
  2426.     if not IsGroup( G )  then
  2427.         Error( "<G> must be a group" );
  2428.     elif not IsSubgroup( G, U )  then
  2429.         Error( "<U> must be a subgroup of <G>" );
  2430.     fi;
  2431.  
  2432.     # <U> and <G> must have a common parent
  2433.     Parent( G, U );
  2434.     InfoGroup1( "#I  IsSubnormal: is ", GroupString(U,"U"),
  2435.                 " subnormal in ", GroupString(G,"G"), "\n" );
  2436.  
  2437.     # if <G> is the parent, use the entry '<U>.isSubnormal'
  2438.     if IsParent( G )  then
  2439.         if not IsBound( U.isSubnormal )  then
  2440.             U.isSubnormal := G.operations.IsSubnormal( G, U );
  2441.         fi;
  2442.         isSub := U.isSubnormal;
  2443.  
  2444.     # otherwise
  2445.     else
  2446.         if IsBound( U.isSubnormal ) and U.isSubnormal  then
  2447.             isSub := true;
  2448.         else
  2449.             isSub := G.operations.IsSubnormal( G, U );
  2450.         fi;
  2451.     fi;
  2452.  
  2453.     # return the result
  2454.     InfoGroup1( "#I  IsSubnormal: returns ", isSub, "\n" );
  2455.     return isSub;
  2456.  
  2457. end;
  2458.  
  2459. GroupOps.IsSubnormal := function ( G, U )
  2460.     local   S;          # subnormal series of <U> in <G>
  2461.  
  2462.     # compute the subnormal series of <U> in <G>
  2463.     S := SubnormalSeries( G, U );
  2464.  
  2465.     # <U> is subnormal if the series reaches <U>
  2466.     return S[ Length(S) ] = U;
  2467.  
  2468. end;
  2469.  
  2470.  
  2471. #############################################################################
  2472. ##
  2473. #F  IsTrivial( <G> )  . . . . . . . . . . . . . .  test if a group is trivial
  2474. ##
  2475. IsTrivial := function ( G )
  2476.     return G.operations.IsTrivial( G );
  2477. end;
  2478.  
  2479. GroupOps.IsTrivial := function ( G )
  2480.     return G.generators = [];
  2481. end;
  2482.  
  2483.  
  2484. #############################################################################
  2485. ##
  2486.  
  2487. #F  AbelianInvariants( <G> )  . . . . . . . . . abelian invariants of a group
  2488. ##
  2489. AbelianInvariants := function ( G )
  2490.  
  2491.     # check that the argument is a group
  2492.     if not IsGroup( G ) or not IsAbelian( G )  then
  2493.         Error("<G> must be an abelian group");
  2494.     fi;
  2495.     InfoGroup1("#I  AbelianInvariants: ",GroupString(G,"G"),"\n");
  2496.  
  2497.     # compute the abelian invariants
  2498.     if not IsBound( G.abelianInvariants )  then
  2499.         G.abelianInvariants := G.operations.AbelianInvariants( G );
  2500.     fi;
  2501.  
  2502.     # return the abelian invariants
  2503.     InfoGroup1( "#I  AbelianInvariants: ", G.abelianInvariants, "\n" );
  2504.     return G.abelianInvariants;
  2505.  
  2506. end;
  2507.  
  2508. GroupOps.AbelianInvariants := function ( G )
  2509.     local   G,  H,  p,  l,  r,  i,  j,  gns,  inv,  ranks, g;
  2510.  
  2511.     if not IsFinite( G )  then
  2512.         Error( "<G> must be a finite group" );
  2513.     elif G.generators = []  then
  2514.         return [];
  2515.     fi;
  2516.  
  2517.     gns := G.generators;
  2518.     inv := [];
  2519.     for p  in Set( Factors( Size( G ) ) )  do
  2520.         ranks := [];
  2521.         repeat
  2522.             H := TrivialSubgroup( G );
  2523.             for g  in gns  do
  2524.                 H := Closure( H, g ^ p );
  2525.             od;
  2526.             r := Size( G ) / Size( H );
  2527.             InfoGroup2( "#I  AbelianInvariants: |<G>| = ", Size( G ),
  2528.                         ", |<H>| = ", Size( H ), "\n" );
  2529.             G   := H;
  2530.             gns := G.generators;
  2531.             if r <> 1  then  Add( ranks, Length( Factors( r ) ) );  fi;
  2532.         until r = 1;
  2533.         InfoGroup2( "#I  AbelianInvariants: <ranks> = ", ranks, "\n" );
  2534.         l := List( [ 1 .. ranks[1] ], x -> 1 );
  2535.         for i  in ranks  do
  2536.             for j  in [ 1 .. i ]  do
  2537.                 l[ j ] := l[ j ] * p;
  2538.             od;
  2539.         od;
  2540.         Append( inv, l );
  2541.     od;
  2542.  
  2543.     Sort( inv );
  2544.     return inv;
  2545.  
  2546. end;
  2547.  
  2548.  
  2549. #############################################################################
  2550. ##
  2551. #F  Exponent( <G> ) . . . . . . . . . . . . . . . . . . . . . exponent of <G>
  2552. ##
  2553. Exponent := function( G )
  2554.  
  2555.     # check the argument
  2556.     if not IsGroup(G)  then
  2557.     Error( "<G> must be a group" );
  2558.     fi;
  2559.  
  2560.     # compute the exponent
  2561.     if not IsBound(G.exponent)  then
  2562.     G.exponent := G.operations.Exponent(G);
  2563.     fi;
  2564.     return G.exponent;
  2565.  
  2566. end;
  2567.  
  2568. #N 'ConjugacyClasses' will not work with 'FpGroup' so we use 'Elements'
  2569. GroupOps.Exponent := function( G )
  2570.     return Lcm( List( Elements(G), x -> Order( G, x ) ) );
  2571. end;
  2572.  
  2573.  
  2574. #############################################################################
  2575. ##
  2576. #F  Index( <G>, <U> ) . . . . . . . . . . . .  index of a subgroup in a group
  2577. ##
  2578. Index := function ( G, U )
  2579.     local   index;      # index of <U> in <G>, result
  2580.  
  2581.     # check that the arguments are groups with a common parent
  2582.     if not IsGroup( G )  then
  2583.         Error( "<G> must be a group" );
  2584.     elif not IsGroup( U )  then
  2585.         Error( "<U> must be a group" );
  2586.     fi;
  2587.  
  2588.     # <G> and <U> must have a common parent
  2589.     Parent( G, U );
  2590.     InfoGroup1("#I  Index: of ", GroupString(U,"U"), " in ",
  2591.                 GroupString(G,"G"), "\n");
  2592.  
  2593.     # compute the index
  2594.     if IsParent( G )  then
  2595.         if not IsBound( U.index )  then
  2596.             U.index := G.operations.Index( G, U );
  2597.         fi;
  2598.         index := U.index;
  2599.     else
  2600.         index := G.operations.Index( G, U );
  2601.     fi;
  2602.  
  2603.     # return the index
  2604.     InfoGroup1("#I  Index: returns ",index,"\n");
  2605.     return index;
  2606.  
  2607. end;
  2608.  
  2609. GroupOps.Index := function ( G, U )
  2610.     return Size( G ) / Size( U );
  2611. end;
  2612.  
  2613.  
  2614. #############################################################################
  2615. ##
  2616. #F  SmallestGenerators(<G>) . . . . . . smallest generating system of a group
  2617. ##
  2618. SmallestGenerators := function ( G )
  2619.  
  2620.     # check the argument
  2621.     if not IsGroup( G )  then
  2622.         Error("<G> must be a group");
  2623.     fi;
  2624.  
  2625.     # compute the smallest generating system
  2626.     if not IsBound( G.smallestGenerators )  then
  2627.         G.smallestGenerators := G.operations.SmallestGenerators( G );
  2628.     fi;
  2629.  
  2630.     # return the smallest generating system
  2631.     return G.smallestGenerators;
  2632. end;
  2633.  
  2634. GroupOps.SmallestGenerators := function ( G )
  2635.     local   gens,       # smallest generating system of <G>, result
  2636.             gen,        # one generator of <gens>
  2637.             H;          # subgroup generated by <gens> so far
  2638.  
  2639.     # start with the empty generating system and the trivial subgroup
  2640.     gens := [];
  2641.     H := TrivialSubgroup( G );
  2642.  
  2643.     # loop over the elements of <G> in their order
  2644.     for gen  in Elements( G )  do
  2645.  
  2646.         # add the element not lying in the subgroup generated by the previous
  2647.         if not gen in H  then
  2648.             Add( gens, gen );
  2649.             H := Closure( H, gen );
  2650.  
  2651.             # it is important to know when to stop
  2652.             if Size( H ) = Size( G )  then
  2653.                 return gens;
  2654.             fi;
  2655.  
  2656.         fi;
  2657.  
  2658.     od;
  2659.  
  2660.     # well we should never come here
  2661.     Error("panic, <G> not generated by its elements");
  2662. end;
  2663.  
  2664.  
  2665. #############################################################################
  2666. ##
  2667.  
  2668. #F  IsConjugacyClass( <C> ) . . test if an object is a conjugacy class record
  2669. ##
  2670. IsConjugacyClass := function ( C )
  2671.     return     IsRec( C )
  2672.            and IsBound( C.isConjugacyClass )
  2673.            and C.isConjugacyClass;
  2674. end;
  2675.  
  2676.  
  2677. #############################################################################
  2678. ##
  2679. #F  ConjugacyClass(<G>,<g>) . . . .  conjugacy class of an element in a group
  2680. #V  ConjugacyClassGroupOps  . . . . . operations record for conjugacy classes
  2681. ##
  2682. ConjugacyClass := function ( G, g )
  2683.     return G.operations.ConjugacyClass( G, g );
  2684. end;
  2685.  
  2686. GroupOps.ConjugacyClass := function ( G, g )
  2687.     local   C;
  2688.  
  2689.     # make the domain
  2690.     C := rec( );
  2691.     C.isDomain          := true;
  2692.     C.isConjugacyClass  := true;
  2693.  
  2694.     # enter the identifying information
  2695.     C.group             := G;
  2696.     C.representative    := g;
  2697.  
  2698.     # enter the operations record
  2699.     C.operations        := ConjugacyClassGroupOps;
  2700.  
  2701.     # return the conjugacy class
  2702.     return C;
  2703.  
  2704. end;
  2705.  
  2706. ConjugacyClassGroupOps := Copy( DomainOps );
  2707.  
  2708. ConjugacyClassGroupOps.Elements := function ( C )
  2709.     return Set( Orbit( C.group, C.representative ) );
  2710. end;
  2711.  
  2712. ConjugacyClassGroupOps.Size := function ( C )
  2713.     if not IsBound( C.centralizer )  then
  2714.         C.centralizer := Centralizer( C.group, C.representative );
  2715.     fi;
  2716.     return Index( C.group, C.centralizer );
  2717. end;
  2718.  
  2719. ConjugacyClassGroupOps.\= := function ( C, D )
  2720.     local    isEql;
  2721.  
  2722.     if    IsRec( C )  and IsBound( C.isConjugacyClass )
  2723.       and IsRec( D )  and IsBound( D.isConjugacyClass )
  2724.       and C.group = D.group
  2725.     then
  2726.         isEql := C.size = D.size
  2727.              and Order( C.group, C.representative )
  2728.                = Order( D.group, D.representative )
  2729.              and RepresentativeOperation(
  2730.                                 C.group,
  2731.                                 D.representative,
  2732.                                 C.representative ) <> false;
  2733.     else
  2734.         isEql := DomainOps.\=( C, D );
  2735.     fi;
  2736.     return isEql;
  2737.  
  2738. end;
  2739.  
  2740. ConjugacyClassGroupOps.\in := function ( g, C )
  2741.     return     g in C.group
  2742.            and Order( C.group, g ) = Order( C.group, C.representative )
  2743.            and RepresentativeOperation( C.group,
  2744.                                         g,
  2745.                                         C.representative ) <> false;
  2746. end;
  2747.  
  2748. ConjugacyClassGroupOps.Random := function ( C )
  2749.     return C.representative ^ Random( C.group );
  2750. end;
  2751.  
  2752. ConjugacyClassGroupOps.\* := function ( C, D )
  2753.     if IsConjugacyClass( C )  then
  2754.         return Elements( C ) * D;
  2755.     elif IsConjugacyClass( D )  then
  2756.         return C * Elements( D );
  2757.     else
  2758.         Error( "panic, neither <C> nor <D> is a conjugacy class" );
  2759.     fi;
  2760. end;
  2761.  
  2762. ConjugacyClassGroupOps.Print := function ( C )
  2763.     Print( "ConjugacyClass( ", C.group, ", ", C.representative, " )" );
  2764. end;
  2765.  
  2766.  
  2767. #############################################################################
  2768. ##
  2769. #F  ConjugacyClasses( <G> )  . . . . . . . . . . conjugacy classes of a group
  2770. ##
  2771. ConjugacyClasses := function ( G )
  2772.  
  2773.     # check that the argument is a group
  2774.     if not IsGroup( G )  then
  2775.         Error("<G> must be a group");
  2776.     fi;
  2777.     InfoGroup1("#I  ConjugacyClasses: ",GroupString(G,"G"),"\n");
  2778.  
  2779.     # compute the conjugacy classes
  2780.     if not IsBound( G.conjugacyClasses )  then
  2781.         G.conjugacyClasses := G.operations.ConjugacyClasses( G );
  2782.     fi;
  2783.  
  2784.     # return the classes
  2785.     InfoGroup1( "#I  ConjugacyClasses: returns ",
  2786.                 Length(G.conjugacyClasses), " classes\n" );
  2787.     return G.conjugacyClasses;
  2788.  
  2789. end;
  2790.  
  2791. GroupOps.ConjugacyClasses := function ( G )
  2792.     local   classes,    # conjugacy classes of <G>, result
  2793.             class,      # one class of <G>
  2794.             elms;       # elements of <G>
  2795.  
  2796.     # initialize the conjugacy class list
  2797.     classes := [ ConjugacyClass( G, G.identity ) ];
  2798.     InfoGroup1( "#I    1. class of order 1 and length 1 ",
  2799.                 "(1 of ",Size(G)," elements)\n" );
  2800.  
  2801.     # if the group is small, or if its elements are known do it the hard way
  2802.     if Size( G ) <= 1000 or IsBound( G.elements )  then
  2803.  
  2804.         # get the elements
  2805.         elms := Difference( Elements( G ), [ G.identity ] );
  2806.  
  2807.         # while we have not found all conjugacy classes
  2808.         while elms <> []  do
  2809.  
  2810.             # add the class of the first element
  2811.             class := ConjugacyClass( G, elms[1] );
  2812.             Add( classes, class );
  2813.             InfoGroup1( "#I    ", Length(classes),
  2814.                         ". class of order ", Order(G,elms[1]),
  2815.                         " and length ", Size(class),
  2816.                         " (", Sum(List(classes,Size)), " elements)\n" );
  2817.  
  2818.             # remove the elements of this class
  2819.             SubtractSet( elms, Elements( class ) );
  2820.  
  2821.         od;
  2822.  
  2823.     # otherwise use probabilistic algorithm
  2824.     else
  2825.  
  2826.         # while we have not found all conjugacy classes
  2827.         while Sum( List( classes, Size ) ) <> Size( G )  do
  2828.  
  2829.             # try random elements
  2830.             G.operations.ConjugacyClassesTry( G, classes, Random(G), 0, 1 );
  2831.  
  2832.         od;
  2833.  
  2834.     fi;
  2835.  
  2836.     # return the conjugacy classes
  2837.     return classes;
  2838.  
  2839. end;
  2840.  
  2841. GroupOps.ConjugacyClassesTry := function ( G, classes, elm, length, fixes )
  2842.     local   C,          # new class
  2843.             D,          # another new class
  2844.             new,        # new classes
  2845.             i;          # loop variable
  2846.  
  2847.     # if the element is not in one of the known classes add a new class
  2848.     if ForAll( classes, D -> length mod Size(D) <> 0 or not elm in D )  then
  2849.         C := ConjugacyClass( G, elm );
  2850.         Add( classes, C );
  2851.         new := [ C ];
  2852.         if length = 0  then
  2853.             InfoGroup1("#I    ",Length(classes),
  2854.                        ". class of order ",Order(G,elm),
  2855.                        " and length ",Size(C),
  2856.                        " (",Sum(List(classes,Size))," elements)\n");
  2857.         else
  2858.             InfoGroup1("#I    ",Length(classes),
  2859.                        ". class of power order ",Order(G,elm),
  2860.                        " and length ",Size(C),
  2861.                        " (",Sum(List(classes,Size))," elements)\n");
  2862.         fi;
  2863.  
  2864.         # try powers that keep the order, compare only with new classes
  2865.         for i  in [2..Order(G,elm)-1]  do
  2866.             if GcdInt( i, Order(G,elm) * fixes ) = 1  then
  2867.                 if not elm^i in C  then
  2868.                     if ForAll( new, D -> not elm^i in D )  then
  2869.                         D := ConjugacyClass( G, elm^i );
  2870.                         Add( classes, D );
  2871.                         Add( new, D );
  2872.                         InfoGroup1("#I    ",Length(classes),
  2873.                                    ". class of same order",
  2874.                                    " and same length ",
  2875.                                    " (",Sum(List(classes,Size)),
  2876.                                    " elements)\n");
  2877.                     fi;
  2878.                 elif IsPrime(i)  then
  2879.                     fixes := fixes * i;
  2880.                 fi;
  2881.             fi;
  2882.         od;
  2883.  
  2884.         # try also the powers of this element that reduce the order
  2885.         for i  in Set( FactorsInt( Order( G, elm ) ) )  do
  2886.             G.operations.ConjugacyClassesTry(G,classes,elm^i,Size(C),fixes);
  2887.         od;
  2888.  
  2889.     fi;
  2890.  
  2891. end;
  2892.  
  2893.  
  2894. #############################################################################
  2895. ##
  2896. #F  ConjugateSubgroup( <G>, <obj> ) . . . . . . . . . .  conjugate of a group
  2897. ##
  2898. ConjugateSubgroup := function ( G, g )
  2899.  
  2900.     # check the arguments
  2901.     if not IsGroup( G )  then
  2902.         Error( "<G> must be a group" );
  2903.     elif not g in Parent( G )  then
  2904.         Error( "<g> must be an element of the parent group of <G>" );
  2905.     fi;
  2906.  
  2907.     # dispatch
  2908.     return G.operations.ConjugateSubgroup( G, g );
  2909.  
  2910. end;
  2911.  
  2912. GroupOps.ConjugateSubgroup := function ( G, g )
  2913.     local   H,          # conjugated subgroup of <G>, result
  2914.             name;       # component name in the group record
  2915.  
  2916.     # special case if <g> is in <G>
  2917.     if IsBound( G.elements )  and g in G.elements  or g in G.generators  then
  2918.         return G;
  2919.     fi;
  2920.  
  2921.     # create the domain
  2922.     H := Subgroup( Parent( G ), OnTuples( G.generators, g ) );
  2923.  
  2924.     # copy usefull information
  2925.     for name  in Intersection( RecFields( G ), MaintainedGroupInfo )  do
  2926.         H.(name) := G.(name);
  2927.     od;
  2928.  
  2929.     # copy the list of elements if present
  2930.     if IsBound( G.elements )  then
  2931.         H.elements := OnSets( G.elements, g );
  2932.     fi;
  2933.  
  2934.     # return the conjugated subgroup
  2935.     return H;
  2936.  
  2937. end;
  2938.  
  2939. GroupOps.\^ := ConjugateSubgroup;
  2940.  
  2941.  
  2942. #############################################################################
  2943. ##
  2944. #F  ConjugateSubgroups( <G>, <U> )  . . .  conjugated subgroups of a subgroup
  2945. ##
  2946. ConjugateSubgroups := function ( G, U )
  2947.  
  2948.     # check that the arguments are groups with a common parent
  2949.     if not IsGroup( G )  then
  2950.         Error("<G> must be a group");
  2951.     elif not IsGroup( U )  then
  2952.         Error("<U> must be a group");
  2953.     fi;
  2954.     Parent( G, U );
  2955.  
  2956.     # dispatch
  2957.     return G.operations.ConjugateSubgroups( G, U );
  2958.  
  2959. end;
  2960.  
  2961. GroupOps.ConjugateSubgroups := function ( G, U )
  2962.     return Orbit( G, U );
  2963. end;
  2964.  
  2965.  
  2966. #############################################################################
  2967. ##
  2968. #F  AbstractElementsGroup( <group> )  . . . . elements in abstract generators
  2969. ##
  2970. AbstractElementsGroup := function ( G )
  2971.     local   elms, e, reps, aReps, aElms, i, k, j;
  2972.  
  2973.     InfoGroup1( "#I  AbstractElementsGroup: ", GroupString( G, "G" ), "\n" );
  2974.  
  2975.     # start with the identity subgroup
  2976.     G.elements := [ G.identity ];
  2977.     G.abstractElements := [ IdWord ];
  2978.  
  2979.     # run over the subgroups <1> <= <G.1> <= <G.1,G.2> <= <G.1,G.2,G.3> ..
  2980.     for i  in [ 1 .. Length( G.generators ) ]  do
  2981.  
  2982.         # start with the trivial transversal of the previous subgroup
  2983.         reps  := [ G.identity ];
  2984.         aReps := [ IdWord ];
  2985.         elms  := ShallowCopy( G.elements );
  2986.         aElms := ShallowCopy( G.abstractElements );
  2987.  
  2988.         # perform an orbit algorithm for the representatives
  2989.         j := 1;
  2990.         while j <= Length( reps )  do
  2991.             for k  in [ 1 .. i ]  do
  2992.  
  2993.                 # if new, add e to representatives and the coset to elements
  2994.                 e := reps[ j ] * G.generators[ k ];
  2995.                 if not e in elms  then
  2996.                     Add( reps, e );
  2997.                     Append( elms, G.elements * e );
  2998.                     e := aReps[ j ] * G.abstractGenerators[ k ];
  2999.                     Add( aReps, e );
  3000.                     Append( aElms, G.abstractElements * e );
  3001.                 fi;
  3002.  
  3003.             od;
  3004.             j := j + 1;
  3005.         od;
  3006.  
  3007.         # on to the next subgroup
  3008.         G.elements := elms;
  3009.         G.abstractElements := aElms;
  3010.         InfoGroup2( "#I  AbstractElementsGroup: |<G.elements>| = ",
  3011.                     Length( G.elements ), ", ", i, ".th generator\r" );
  3012.     od;
  3013.  
  3014.     # We must sort by hand
  3015.     InfoGroup2( "#I  AbstractElementsGroup: sorting",
  3016.                 "                                \r" );
  3017.     e := [ 1 .. Length( G.elements ) ];
  3018.     k := function ( a, b )  return G.elements[ a ] < G.elements[ b ];  end;
  3019.     Sort( e, k );
  3020.     G.elements := Sublist( G.elements, e );
  3021.     G.abstractElements := Sublist( G.abstractElements, e );
  3022.  
  3023.     InfoGroup1( "#I  AbstractElementsGroup: |<G>.elements| = ",
  3024.                 Length( G.elements ), "\n" );
  3025.  
  3026.     # return the list of elements and abstract elements
  3027.     return G;
  3028.  
  3029. end;
  3030.  
  3031.  
  3032. #############################################################################
  3033. ##
  3034. #F  Factorization( <G>, <g> ) . . . factorize a group element into generators
  3035. ##
  3036. Factorization := function ( G, g )
  3037.     local   F;
  3038.  
  3039.     # compute the factorization
  3040.     F := G.operations.Factorization( G, g );
  3041.  
  3042.     # return the factorization
  3043.     return F;
  3044.  
  3045. end;
  3046.  
  3047. GroupOps.Factorization := function ( G, g )
  3048.     local   p;
  3049.  
  3050.     # abort if group is infinite
  3051.     if not IsFinite( G )  then
  3052.         Error( "sorry, cannot factor <g> in the infinite group <G>" );
  3053.     fi;
  3054.  
  3055.     # we need a list of abstract elements
  3056.     if not IsBound( G.abstractElements )  then
  3057.         if not IsBound( G.abstractGenerators )  then
  3058.             G.abstractGenerators := WordList( Length(G.generators), "x" );
  3059.         fi;
  3060.         AbstractElementsGroup( G );
  3061.     fi;
  3062.  
  3063.     # is <g> an element of <G> ?
  3064.     p := Position( G.elements, g );
  3065.     if p = false  then
  3066.         Error("<g> must be an element of <G>");
  3067.     fi;
  3068.     return G.abstractElements[ p ];
  3069.  
  3070. end;
  3071.  
  3072.  
  3073. #############################################################################
  3074. ##
  3075. #F  AgGroup( <G> )  . . . . . . . . . . . . . . . view a group as an ag group
  3076. ##
  3077. AgGroup := function ( G )
  3078.     local   H;
  3079.  
  3080.     if IsBound(G.isPQp) and G.isPQp  then
  3081.         H := G.operations.AgGroup(G);
  3082.     elif not IsGroup(G)  then
  3083.         Error("<G> must be a group");
  3084.     elif not IsFinite(G)  then
  3085.         Error("<G> must be finite group");
  3086.     elif not IsSolvable(G)  then
  3087.         Error("<G> must be finite solvable group");
  3088.     elif IsBound(G.operations.AgGroup)  then
  3089.         H := G.operations.AgGroup(G);
  3090.     else
  3091.         Error("sorry, cannot convert <G> into an ag group");
  3092.     fi;
  3093.     return H;
  3094.  
  3095. end;
  3096.  
  3097. GroupOps.AgGroup := function ( G )
  3098.  
  3099.     local   D,      # derived series of <G>
  3100.             B,      # ag-system
  3101.             BP,     # relative order of <B>[i]
  3102.             L,      # generators of factor groups
  3103.                     # abstract generators in second part
  3104.             M,      # <D>[ i+1 ]
  3105.             N,      # subgroup of <D>[ i ] / M
  3106.             Q,      # <p>-agemo of <N>
  3107.                     # composition list in second part
  3108.             R,      # relators
  3109.             p,      # one primefactor of |<D>[i] / <D>[i+1]|
  3110.             P,
  3111.             S,
  3112.             i,  j;
  3113.  
  3114.     # Compute the derived series, step down the agemos.
  3115.     S  := Parent( G );
  3116.     D  := DerivedSeries( G );
  3117.     B  := [];
  3118.     BP := [];
  3119.     for i  in [ 1 .. Length( D ) - 1 ]  do
  3120.         InfoGroup2( "#I  AgGroup: derived step ", i, "\n" );
  3121.         L := D[ i ].generators;
  3122.         M := D[ i + 1 ];
  3123.         for p  in Set( Factors( Index( D[ i ], M ) ) )  do
  3124.             InfoGroup2( "#I  AgGroup: prime ", p, "\n" );
  3125.             N := Closure( M, Subgroup( S, L ) );
  3126.             L := Set( List( L, x -> x ^ p ) );
  3127.             Q := Closure( M, Subgroup( S, L ) );
  3128.             while N <> Q  do
  3129.                 P := Q;
  3130.                 j := 1;
  3131.                 while N <> P  do
  3132.                     while N.generators[ j ] in P  do
  3133.                         j := j + 1;
  3134.                     od;
  3135.                     Add( B, N.generators[ j ] );
  3136.                     Add( BP, p );
  3137.                     P := Closure( P, N.generators[ j ] );
  3138.                 od;
  3139.                 L := Set( List( L, x -> x ^ p ) );
  3140.                 N := Q;
  3141.                 Q := Closure( M, Subgroup( S, L ) );
  3142.             od;
  3143.         od;
  3144.     od;
  3145.  
  3146.     # Now compute a presentation for the ag system <B>
  3147.     L := WordList( Length( B ), "g" );
  3148.     Q := [];
  3149.     j := Length( B );
  3150.     for i  in [ 2 .. j + 1 ]  do
  3151.         Q[ i ] := Subgroup( S, Sublist( B, [ i .. j ] ) );
  3152.         Q[ i ].abstractGenerators := Sublist( L, [ i .. j ] );
  3153.     od;
  3154.     R := [];
  3155.     for i  in [ 1 .. Length( B ) ]  do
  3156.         Add( R, L[i]^BP[i] / Factorization( Q[ i+1 ], B[i]^BP[i] ) );
  3157.     od;
  3158.     for i  in [ 1 .. Length( B ) - 1 ]  do
  3159.         for j  in [ i + 1 .. Length( B ) ]  do
  3160.             Add( R, Comm(L[j],L[i])/Factorization(Q[i+1],Comm(B[j],B[i])) );
  3161.         od;
  3162.     od;
  3163.     Q := AgGroupFpGroup( rec( generators := L, relators := R ) );
  3164.     Q.bijection := GroupHomomorphismByImages( Q, G, Q.generators, B );
  3165.     Q.bijection.isMapping           := true;
  3166.     Q.bijection.isHomomorphism      := true;
  3167.     Q.bijection.isIsomorphism       := true;
  3168.     Q.bijection.isGroupHomomorphism := true;
  3169.     Q.bijection.isInjective         := true;
  3170.     Q.bijection.isSurjective        := true;
  3171.     Q.bijection.isBijection         := true;
  3172.     return Q;
  3173.  
  3174. end;
  3175.  
  3176.  
  3177. #############################################################################
  3178. ##
  3179. #F  PermGroup( <G> )  . . . . . . . . . . . . .  view a group as a perm group
  3180. ##
  3181. PermGroup := function ( G )
  3182.  
  3183.     # check that the argument is a finite group
  3184.     if not IsGroup( G ) or not IsFinite( G )  then
  3185.         Error("<G> must be a finite group");
  3186.     fi;
  3187.  
  3188.     # find a permutation group
  3189.     if not IsBound( G.permGroup )  then
  3190.         G.permGroup := G.operations.PermGroup( G );
  3191.     fi;
  3192.  
  3193.     # return the permutation group
  3194.     InfoGroup1("#I  PermGroup: returns ",GroupString(G.permGroup,"P"),"\n");
  3195.     return G.permGroup;
  3196.  
  3197. end;
  3198.  
  3199. GroupOps.PermGroup := function ( G )
  3200.     local   P;          # permutation group isomorphic to <G>, result
  3201.  
  3202.     # make the permutation group
  3203.     P := Operation( G, Elements( G ), OnRight );
  3204.  
  3205.     # make the bijection from <P> to <G>
  3206.     P.bijection := InverseMapping( OperationHomomorphism( G, P ) );
  3207.     P.bijection.isMapping       := true;
  3208.     P.bijection.isInjective     := true;
  3209.     P.bijection.isSurjective    := true;
  3210.     P.bijection.isBijection     := true;
  3211.     P.bijection.isHomomorphism  := true;
  3212.     P.bijection.isMonomorphism  := true;
  3213.     P.bijection.isEpimorphism   := true;
  3214.     P.bijection.isIsomorphism   := true;
  3215.     P.bijection.image           := G;
  3216.     P.bijection.preimage        := P;
  3217.     P.bijection.kernel          := TrivialSubgroup( P );
  3218.  
  3219.     # return the permutation group
  3220.     return P;
  3221.  
  3222. end;
  3223.  
  3224.  
  3225. #############################################################################
  3226. ##
  3227.  
  3228. #R  Read  . . . . . . . . . . . . .  read other function from the other files
  3229. ##
  3230. ReadLib( "grphomom" );
  3231. ReadLib( "operatio" );
  3232. ReadLib( "grpcoset" );
  3233. ReadLib( "grpprods" );
  3234. ReadLib( "grpctbl"  );
  3235. ReadLib( "lattgrp"  );
  3236.  
  3237.  
  3238. #############################################################################
  3239. ##
  3240. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  3241. ##
  3242. ##  Local Variables:
  3243. ##  mode:               outline
  3244. ##  outline-regexp:     "#F\\|#V\\|#E\\|#R"
  3245. ##  fill-column:        73
  3246. ##  fill-prefix:        "##  "
  3247. ##  eval:               (hide-body)
  3248. ##  End:
  3249. ##
  3250.  
  3251.  
  3252.  
  3253.