home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / permgrp.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  59.5 KB  |  1,823 lines
  1. #############################################################################
  2. ##
  3. #A  permgrp.g                   GAP library                         Udo Polis
  4. #A                                                         & Martin Schoenert
  5. ##
  6. #A  @(#)$Id: permgrp.g,v 3.43 1993/02/10 10:11:14 martin Rel $
  7. ##
  8. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  9. ##
  10. ##  This file contains the basic functions that work with permutation groups.
  11. ##  There  are  functions to compute   a stabilizer chain  for  a permutation
  12. ##  group, to change to a stabilizer chain for  a  different base, and simple
  13. ##  functions that use stabilizer chain, e.g., 'Size' and 'in'.
  14. ##
  15. #H  $Log: permgrp.g,v $
  16. #H  Revision 3.43  1993/02/10  10:11:14  martin
  17. #H  added "permcser"
  18. #H
  19. #H  Revision 3.42  1993/01/18  18:55:16  martin
  20. #H  added character table computation
  21. #H
  22. #H  Revision 3.41  1993/01/18  17:40:29  martin
  23. #H  moved coset functions to 'permcose.g'
  24. #H
  25. #H  Revision 3.40  1993/01/15  14:43:03  martin
  26. #H  added 'MakeStabChainRandom'
  27. #H
  28. #H  Revision 3.39  1993/01/08  13:46:51  fceller
  29. #H  changed '.size' into 'Size' call in 'ConjugacyClassOps.\='
  30. #H
  31. #H  Revision 3.38  1993/01/04  11:16:53  fceller
  32. #H  added 'Exponent'
  33. #H
  34. #H  Revision 3.37  1992/12/16  19:47:27  martin
  35. #H  replaced quoted record names with escaped ones
  36. #H
  37. #H  Revision 3.36  1992/12/02  08:09:50  fceller
  38. #H  added "permag.g"
  39. #H
  40. #H  Revision 3.35  1992/07/14  13:13:34  martin
  41. #H  added package "permprod"
  42. #H
  43. #H  Revision 3.34  1992/06/03  09:18:00  martin
  44. #H  added 'PermGroupOps.IsSimple'
  45. #H
  46. #H  Revision 3.33  1992/05/14  10:43:50  martin
  47. #H  fixed 'SylowSubgroups', groups with known size need not have a stabchain
  48. #H
  49. #H  Revision 3.32  1992/03/13  13:47:16  martin
  50. #H  fixed 'PermGroupOps.Subgroup' from overwriting the or of parent groups
  51. #H
  52. #H  Revision 3.31  1992/02/19  13:07:04  martin
  53. #H  added the new Sylow subgroup algorithm
  54. #H
  55. #H  Revision 3.30  1992/02/12  15:44:23  martin
  56. #H  added the lattice package
  57. #H
  58. #H  Revision 3.29  1992/02/11  12:44:04  martin
  59. #H  added 'SmallestGenerators'
  60. #H
  61. #H  Revision 3.28  1992/01/29  09:09:38  martin
  62. #H  changed 'Order' to take two arguments, group and element
  63. #H
  64. #H  Revision 3.27  1992/01/27  11:22:41  martin
  65. #H  fixed another bug in 'Closure' (hopefully the last)
  66. #H
  67. #H  Revision 3.26  1992/01/20  15:58:36  martin
  68. #H  added permgroup homomorphisms
  69. #H
  70. #H  Revision 3.25  1992/01/20  15:40:31  martin
  71. #H  changed 'Closure' to avoid calling 'GroupOps.Closure'
  72. #H
  73. #H  Revision 3.24  1992/01/16  12:30:33  martin
  74. #H  added 'MakeStabChainStrongGenerators'
  75. #H
  76. #H  Revision 3.23  1992/01/14  16:42:29  martin
  77. #H  fixed yet another bug in 'Closure'
  78. #H
  79. #H  Revision 3.22  1992/01/07  14:44:34  martin
  80. #H  added 'PermGroupOps.Normalizer' (in 'permnorm.g')
  81. #H
  82. #H  Revision 3.21  1992/01/07  13:59:28  martin
  83. #H  changed 'Closure' to ignore element lists
  84. #H
  85. #H  Revision 3.20  1991/12/05  11:23:33  martin
  86. #H  removed incorrect redefinition of 'GroupOps.^'
  87. #H
  88. #H  Revision 3.19  1991/11/28  16:04:07  martin
  89. #H  added permgroups conjugacy classes
  90. #H
  91. #H  Revision 3.18  1991/11/28  15:52:32  martin
  92. #H  added permgroup cosets
  93. #H
  94. #H  Revision 3.17  1991/11/28  14:36:55  martin
  95. #H  changed the order of the functions in the file
  96. #H
  97. #H  Revision 3.16  1991/11/28  14:28:55  martin
  98. #H  fixed 'ConjugateSubgroup', 'GroupOps.CS' may return identical subgroup
  99. #H
  100. #H  Revision 3.15  1991/11/28  14:07:49  martin
  101. #H  moved 'PermutationsOps.Group' from 'permutat.g' to 'permgrp.g'
  102. #H
  103. #H  Revision 3.14  1991/11/28  14:06:34  martin
  104. #H  changed 'Subgroup', now delegates to 'GroupOps.Subgroup'
  105. #H
  106. #H  Revision 3.13  1991/11/28  11:31:18  martin
  107. #H  removed 'Print', inherit from 'GroupOps'
  108. #H
  109. #H  Revision 3.12  1991/11/28  11:18:11  martin
  110. #H  changed 'ChangeStabChain' to leave the generators on the top level
  111. #H
  112. #H  Revision 3.11  1991/11/21  15:27:58  martin
  113. #H  added code to update base entry in permgroups
  114. #H
  115. #H  Revision 3.10  1991/10/15  11:13:32  martin
  116. #H  fixed 'Closure' from incorrect 'MakeStabStrong' call
  117. #H
  118. #H  Revision 3.9  1991/10/14  11:35:29  martin
  119. #H  changed 'Print' to honor '<G>.name'
  120. #H
  121. #H  Revision 3.8  1991/10/11  10:52:06  martin
  122. #H  moved 'MakeStabChain', etc into the 'PermGroupOps' record
  123. #H
  124. #H  Revision 3.7  1991/10/08  16:07:23  martin
  125. #H  fixed 'Elements' from the idea that stabilizers are subgroups
  126. #H
  127. #H  Revision 3.6  1991/10/07  15:34:51  martin
  128. #H  fixed another nasty bug in 'Closure'
  129. #H
  130. #H  Revision 3.5  1991/10/04  15:37:16  martin
  131. #H  fixed a minor problem in 'ListStabChain'
  132. #H
  133. #H  Revision 3.4  1991/10/02  14:18:29  martin
  134. #H  fixed a nasty bug in 'Closure'
  135. #H
  136. #H  Revision 3.3  1991/10/01  14:59:23  martin
  137. #H  changed stabchain, stabilizer are no subgroups
  138. #H
  139. #H  Revision 3.2  1991/09/30  13:02:08  martin
  140. #H  fixed 'MakeStabChain' for the trivial group
  141. #H
  142. #H  Revision 3.1  1991/09/30  12:49:09  martin
  143. #H  'Subgroup' binds the generators to '<S>.<i>'
  144. #H
  145. #H  Revision 3.0  1991/09/30  11:39:21  martin
  146. #H  initial revision under RCS
  147. #H
  148. ##
  149.  
  150.  
  151. #############################################################################
  152. ##
  153. #F  InfoPermGroup1( ... ) . .  information function for the permgroup package
  154. #F  InfoPermGroup2( ... ) . .  information function for the permgroup package
  155. ##
  156. if not IsBound( InfoPermGroup1 )  then InfoPermGroup1 := Ignore;  fi;
  157. if not IsBound( InfoPermGroup2 )  then InfoPermGroup2 := Ignore;  fi;
  158.  
  159.  
  160. #############################################################################
  161. ##
  162. #F  IsPermGroup(<D>)  . . . . . . . . . . . . is a domain a permutation group
  163. ##
  164. IsPermGroup := function ( D )
  165.     return IsRec( D )
  166.        and IsBound( D.isPermGroup )  and D.isPermGroup;
  167. end;
  168.  
  169.  
  170. #############################################################################
  171. ##
  172. #F  PermutationsOps.Group(<D>,<gens>,<id>)  . . .  create a permutation group
  173. ##
  174. PermutationsOps.Group := function ( Permutations, gens, id )
  175.     local   G;          # permutation group <G>, result
  176.  
  177.     # let the default function do the main work
  178.     G := GroupElementsOps.Group( Permutations, gens, id );
  179.  
  180.     # add the permutation group tag
  181.     G.isPermGroup       := true;
  182.  
  183.     # add known information
  184.     G.isFinite          := true;
  185.  
  186.     # add the operations record
  187.     G.operations        := PermGroupOps;
  188.  
  189.     # return the permuation group
  190.     return G;
  191. end;
  192.  
  193.  
  194. #############################################################################
  195. ##
  196. #V  PermGroupOps  . . . . . . operation record for permutation group category
  197. ##
  198. ##  'PermGroupOps'  is  the  operation  record for   permutation  groups.  It
  199. ##  contains   the  function  for   domain  operation,    e.g.,    'Size' and
  200. ##  'Intersection' as well  as  the functions  for group    operations, e.g.,
  201. ##  'Centralizer' and 'Orbit'.
  202. ##
  203. ##  'PermGroupOps' is initially a copy of 'GroupOps', thus permutation groups
  204. ##  inherit the default group functions, e.g., 'DerivedSubgroup' and 'Index'.
  205. ##  However  'PermGroupOps'   overlays  some of  those    functions with more
  206. ##  efficient ones, e.g., 'Elements' and 'Size'.
  207. ##
  208. PermGroupOps := Copy( GroupOps );
  209.  
  210.  
  211. #############################################################################
  212. ##
  213. #F  PermGroupOps.Subgroup(<G>,<gens>) . . . . . . make a permutation subgroup
  214. ##
  215. PermGroupOps.Subgroup := function ( G, gens )
  216.     local   S;          # subgroup, result
  217.  
  218.     # let the default function do the main work
  219.     S := GroupOps.Subgroup( G, gens );
  220.  
  221.     # add permgroup tag and permgroup operations record
  222.     if IsBound( S.parent )  then
  223.         S.isPermGroup       := true;
  224.         S.operations        := PermGroupOps;
  225.     fi;
  226.  
  227.     # return the subgroup
  228.     return S;
  229. end;
  230.  
  231.  
  232. #############################################################################
  233. ##
  234. #F  PermGroupOps.Closure(<G>,<obj>) . . . . . . . . . .  closure < <G>, <g> >
  235. ##
  236. PermGroupOps.Closure := function ( G, obj )
  237.     local   C,          # closure of < <G>, <obj> >, result
  238.             gens;       # generators of <obj> that are not in <G>
  239.  
  240.     # get the elements that must be added to <G>
  241.     if IsGroup( obj )  then
  242.         gens := obj.generators;
  243.     else
  244.         gens := [ obj ];
  245.     fi;
  246.  
  247.     # handle a closure in the parent
  248.     if IsParent( G )  then
  249.         C := G;
  250.  
  251.     # handle the closure with a group that has a stabilizer chain
  252.     elif IsBound( G.orbit )  then
  253.  
  254.         # if all generators are in <G>, <G> is the closure
  255.         gens := Filtered( gens, gen -> not G.operations.\in( gen, G ) );
  256.         if gens = []  then
  257.             C := G;
  258.  
  259.         # otherwise make the closure and copy the stabilizer chain
  260.         else
  261.             C := Subgroup( Parent( G ), G.generators );
  262.             C.orbit       := ShallowCopy( G.orbit );
  263.             C.transversal := ShallowCopy( G.transversal );
  264.             C.stabilizer  := Copy( G.stabilizer );
  265.             C.operations.MakeStabStrong( C, gens, C.operations.Base( C ) );
  266.  
  267.         fi;
  268.  
  269.     # handle the closure with a group that has no stabilizer chain
  270.     else
  271.  
  272.         # if all generators are in <G>, <G> is the closure
  273.         gens := Filtered( gens, gen ->     not gen    in G.generators
  274.                                        and not gen^-1 in G.generators
  275.                                        and not (IsBound( G.elements )
  276.                                                 and gen in G.elements) );
  277.         if gens = []  then
  278.             C := G;
  279.  
  280.         # otherwise make the closure group
  281.         else
  282.             C := G.operations.Subgroup( Parent( G ),
  283.                                        Concatenation( G.generators, gens ) );
  284.  
  285.         fi;
  286.  
  287.     fi;
  288.  
  289.     # return the closure
  290.     return C;
  291. end;
  292.  
  293.  
  294. #############################################################################
  295. ##
  296. ##  A stabilizer chain of a permutation group  is a chain  of subgroups, each
  297. ##  of which is a stabilizer of a point in the previous subgroup.
  298. ##
  299. ##  Each stabilizer <S> is represented by a record with the following  fields
  300. ##
  301. ##      '<S>.identity':     identity of <S>.
  302. ##
  303. ##      '<S>.generators':   system of generators for the <S>.
  304. ##
  305. ##      '<S>.orbit':        orbit of  the  point  '<S>.orbit[1]'  under  <S>.
  306. ##                          '<S>.orbit[1]' is called the basepoint of <S>.
  307. ##
  308. ##      '<S>.transversal':  transversal    corresponding    to   '<S>.orbit'.
  309. ##                          For each  point  <p>  in  the  orbit  '<S>.orbit'
  310. ##                          '<S>.transversal[<p>]'  is  a  permutation   that
  311. ##                          takes <p> to  a  point  earlier  in  '<S>.orbit'.
  312. ##                          This is usually called a Schreier vector of  <S>,
  313. ##                          however 'factoredInverseTransversal' would  be  a
  314. ##                          more appropriate name.
  315. ##
  316. ##      '<S>.stabilizer':   stabilizer of the point 'orbit[1]' in <S>.
  317. ##
  318. ##  The chain begins with the group <G> itself and is terminated by a trivial
  319. ##  stabilizer, i.e., 'rec( identity := (), generators := [] )'.
  320. ##
  321. SC_level := 0;          # only for information
  322.  
  323.  
  324. #############################################################################
  325. ##
  326. #F  PermGroupOps.AddGensExtOrb(<S>,<new>) . . . . . add generators and extend
  327. #F                                                      orbit and transversal
  328. ##
  329. PermGroupOps.AddGensExtOrb := function ( S, new )
  330.     local   gens,       # generators of <S> or <new>
  331.             gen,        # one generator in <gens>
  332.             orb,        # orbit of <S>
  333.             len,        # length of the orbit
  334.             i;          # loop variable
  335.  
  336.     # add the new generators to the generator list
  337.     for gen  in new  do
  338.         if not gen in S.generators  then
  339.             Add( S.generators, gen );
  340.         fi;
  341.     od;
  342.  
  343.     # extend the orbit and the transversal with the new generators
  344.     orb := S.orbit;
  345.     len := Length(orb);
  346.     i := 1;
  347.     while i <= Length(orb)  do
  348.         if i <= len  then gens := new;  else gens := S.generators;  fi;
  349.         for gen  in gens  do
  350.             if not IsBound(S.transversal[orb[i]/gen])  then
  351.                 S.transversal[orb[i]/gen] := gen;
  352.                 Add( orb, orb[i]/gen );
  353.             fi;
  354.         od;
  355.         i := i + 1;
  356.     od;
  357.  
  358. end;
  359.  
  360.  
  361. #############################################################################
  362. ##
  363. #F  PermGroupOps.MakeStabStrong(<S>,<new>,<base>) .  make a stabilizer strong
  364. ##
  365. PermGroupOps.MakeStabStrong := function ( S, new, base )
  366.     local   gens,       # generators of <S>
  367.             gen,        # one generator of <S>
  368.             orb,        # orbit of <S>, same as '<S>.orbit'
  369.             len,        # initial length of <orb>
  370.             rep,        # representative of point in <orb>
  371.             sch,        # schreier generator of '<S>.stabilizer'
  372.             stb,        # stabilizer beneath <S>
  373.             bpt,        # basepoint of <stb>, same as '<stb>.orbit[1]'
  374.             i,  j;      # loop variables
  375.  
  376.     # find the index of the first point moved by <new> in '<base>+[1..]'
  377.     i := 1;
  378.     while i <= Length(base)
  379.       and ForAll( new, gen -> base[i]^gen = base[i] )  do
  380.         i := i + 1;
  381.     od;
  382.     if Length(base) < i  then
  383.         while ForAll( new, gen -> (i-Length(base))^gen = i-Length(base) )  do
  384.             i := i + 1;
  385.         od;
  386.     fi;
  387.  
  388.     # if necessary add a new stabilizer to the stabchain
  389.     if not IsBound(S.stabilizer)  then
  390.         if i <= Length(base)  then
  391.             S.orbit               := [ base[i] ];
  392.         else
  393.             S.orbit               := [ i-Length(base) ];
  394.         fi;
  395.         S.transversal             := [];
  396.         S.transversal[S.orbit[1]] := S.identity;
  397.         S.stabilizer              := rec();
  398.         S.stabilizer.identity     := S.identity;
  399.         S.stabilizer.generators   := [];
  400.     fi;
  401.  
  402.     # find the index of the basepoint in '<base>+[1..]'
  403.     j := Position( base, S.orbit[1] );
  404.     if j = false  then
  405.         j := S.orbit[1] + Length(base);
  406.     fi;
  407.  
  408.     # if the new generators move an earlier point insert a new stabilizer
  409.     if i < j  then
  410.         S.stabilizer              := ShallowCopy( S );
  411.         S.stabilizer.generators   := ShallowCopy( S.generators );
  412.         if i <= Length(base)  then
  413.             S.orbit               := [ base[i] ];
  414.         else
  415.             S.orbit               := [ i-Length(base) ];
  416.         fi;
  417.         S.transversal             := [];
  418.         S.transversal[S.orbit[1]] := S.identity;
  419.     fi;
  420.  
  421.     # add the new generators to <S> and extend the orbit and transversal
  422.     orb := S.orbit;
  423.     len := Length(orb);
  424.     PermGroupOps.AddGensExtOrb( S, new );
  425.  
  426.     # force all the new generators that fix the basepoint into the stabilizer
  427.     for gen  in new  do
  428.         if orb[1]^gen = orb[1]  then
  429.             PermGroupOps.MakeStabStrong( S.stabilizer, [ gen ], base );
  430.         fi;
  431.     od;
  432.  
  433.     # compute the Schreier generators (seems to work better backwards)
  434.     for i  in Reversed([1..Length(orb)])  do
  435.  
  436.         # compute an inverse representant '<orb>[1]^(<rep>^-1) = <orb>[i]'
  437.         rep := S.transversal[orb[i]];
  438.         while orb[i] ^ rep <> orb[1]  do
  439.             rep := rep * S.transversal[ orb[i]^rep ];
  440.         od;
  441.  
  442.         # take only the new generators for old, all generators for new points
  443.         if i <= len  then gens := new;  else gens := S.generators;  fi;
  444.         for gen  in gens  do
  445.  
  446.             # avoid to compute schreier generators that will turn out trivial
  447.             if gen <> S.transversal[ orb[i] / gen ]  then
  448.  
  449.                 # divide (gen * rep)^-1 by the representantives
  450.                 sch := (gen * rep)^-1;
  451.                 stb := S;
  452.                 while stb.generators <> []
  453.                   and IsBound(stb.transversal[stb.orbit[1]^sch])  do
  454.                     bpt := stb.orbit[1];
  455.                     while bpt ^ sch <> bpt  do
  456.                         sch := sch * stb.transversal[bpt^sch];
  457.                     od;
  458.                     stb := stb.stabilizer;
  459.                 od;
  460.  
  461.                 # force nontrivial reduced Schreier generator into the stab.
  462.                 if sch <> S.identity  then
  463.                     PermGroupOps.MakeStabStrong( S.stabilizer, [sch], base );
  464.                 fi;
  465.  
  466.             fi;
  467.         od;
  468.  
  469.     od;
  470.  
  471. end;
  472.  
  473.  
  474. #############################################################################
  475. ##
  476. #F  PermGroupOps.MakeStabStrongRandom(<S>,<new>,<base>) . make a stab. strong
  477. ##
  478. ##  Does almost the same, except that only  a  few  Schreier  generators  are
  479. ##  tried on each level.
  480. ##
  481. PermGroupOps.MakeStabStrongRandom := function ( S, new, base )
  482.     local   gens,       # generators of <S>
  483.             gen,        # one generator of <S>
  484.             orb,        # orbit of <S>, same as '<S>.orbit'
  485.             len,        # initial length of <orb>
  486.             rep,        # representative of point in <orb>
  487.             sch,        # schreier generator of '<S>.stabilizer'
  488.             stb,        # stabilizer beneath <S>
  489.             bpt,        # basepoint of <stb>, same as '<stb>.orbit[1]'
  490.             rind,       # random indices no tried so far
  491.             rlen,       # length of <rind>
  492.             rlog,       # 'Length(<orb>) / 2^ <nr of indices tried so far>'
  493.             i,  j;      # loop variables
  494.  
  495.     # find the index of the first point moved by <new> in '<base>+[1..]'
  496.     i := 1;
  497.     while i <= Length(base)
  498.       and ForAll( new, gen -> base[i]^gen = base[i] )  do
  499.         i := i + 1;
  500.     od;
  501.     if Length(base) < i  then
  502.         while ForAll( new, gen -> (i-Length(base))^gen = i-Length(base) )  do
  503.             i := i + 1;
  504.         od;
  505.     fi;
  506.  
  507.     # if necessary add a new stabilizer to the stabchain
  508.     if not IsBound(S.stabilizer)  then
  509.         if i <= Length(base)  then
  510.             S.orbit               := [ base[i] ];
  511.         else
  512.             S.orbit               := [ i-Length(base) ];
  513.         fi;
  514.         S.transversal             := [];
  515.         S.transversal[S.orbit[1]] := S.identity;
  516.         S.stabilizer              := rec();
  517.         S.stabilizer.identity     := S.identity;
  518.         S.stabilizer.generators   := [];
  519.     fi;
  520.  
  521.     # find the index of the basepoint in '<base>+[1..]'
  522.     j := Position( base, S.orbit[1] );
  523.     if j = false  then
  524.         j := S.orbit[1] + Length(base);
  525.     fi;
  526.  
  527.     # if the new generators move an earlier point insert a new stabilizer
  528.     if i < j  then
  529.         S.stabilizer              := ShallowCopy( S );
  530.         S.stabilizer.generators   := ShallowCopy( S.generators );
  531.         if i <= Length(base)  then
  532.             S.orbit               := [ base[i] ];
  533.         else
  534.             S.orbit               := [ i-Length(base) ];
  535.         fi;
  536.         S.transversal             := [];
  537.         S.transversal[S.orbit[1]] := S.identity;
  538.     fi;
  539.  
  540.     # add the new generators to <S> and extend the orbit and transversal
  541.     orb := S.orbit;
  542.     len := Length(orb);
  543.     PermGroupOps.AddGensExtOrb( S, new );
  544.  
  545.     # force all the new generators that fix the basepoint into the stabilizer
  546.     for gen  in new  do
  547.         if orb[1]^gen = orb[1]  then
  548.             PermGroupOps.MakeStabStrongRandom( S.stabilizer, [ gen ], base );
  549.         fi;
  550.     od;
  551.  
  552.     # compute the Schreier generators (seems to work better backwards)
  553.     rind := [1..Length(orb)];
  554.     rlen := Length( orb );
  555.     rlog := Length( orb );
  556.     while 0 < rlen  and 0 < rlog  do
  557.         j := Random( [1..rlen] );
  558.         i := rind[j];
  559.         rind[j] := rind[rlen];
  560.         rlen := rlen - 1;
  561.         rlog := QuoInt( rlog, 2 );
  562.  
  563.         # compute an inverse representant '<orb>[1]^(<rep>^-1) = <orb>[i]'
  564.         rep := S.transversal[orb[i]];
  565.         while orb[i] ^ rep <> orb[1]  do
  566.             rep := rep * S.transversal[ orb[i]^rep ];
  567.         od;
  568.  
  569.         # take only the new generators for old, all generators for new points
  570.         if i <= len  then gens := new;  else gens := S.generators;  fi;
  571.         for gen  in gens  do
  572.  
  573.             # avoid to compute schreier generators that will turn out trivial
  574.             if gen <> S.transversal[ orb[i] / gen ]  then
  575.  
  576.                 # divide (gen * rep)^-1 by the representantives
  577.                 sch := (gen * rep)^-1;
  578.                 stb := S;
  579.                 while stb.generators <> []
  580.                   and IsBound(stb.transversal[stb.orbit[1]^sch])  do
  581.                     bpt := stb.orbit[1];
  582.                     while bpt ^ sch <> bpt  do
  583.                         sch := sch * stb.transversal[bpt^sch];
  584.                     od;
  585.                     stb := stb.stabilizer;
  586.                 od;
  587.  
  588.                 # force nontrivial reduced Schreier generator into the stab.
  589.                 if sch <> S.identity  then
  590.                     rlog := Length( orb );
  591.                     PermGroupOps.MakeStabStrongRandom( S.stabilizer,
  592.                                                        [sch],
  593.                                                        base );
  594.                 fi;
  595.  
  596.             fi;
  597.         od;
  598.  
  599.     od;
  600.  
  601. end;
  602.  
  603.  
  604. #############################################################################
  605. ##
  606. #F  PermGroupOps.SwapStabChain(<S>) . . . . . . . . . exchange two basepoints
  607. ##
  608. PermGroupOps.SwapStabChain := function ( S )
  609.     local   a,  b,      # basepoints that are to be switched
  610.             T,          # copy of $S$ with $T.stabilizer$ becomes $S_b$
  611.             pnt,        # one point from $a^S$ not yet in $a^{T_b}$
  612.             ind,        # index of <pnt> in $S.orbit$
  613.             img,        # image $b^{Rep(S,pnt)^-}$
  614.             gen,        # new generator of $T_b$
  615.             i;          # loop variable
  616.  
  617.     # get the two basepoints $a$ and $b$ that we have to switch
  618.     a := S.orbit[1];
  619.     b := S.stabilizer.orbit[1];
  620.     InfoPermGroup2("#I      swap ",b," with ",a," on level ",SC_level,"\n");
  621.  
  622.     # set $T = S$ and compute $T.orbit = b^T$ and a transversal $T/T_b$
  623.     T := rec();
  624.     T.identity       := S.identity;
  625.     T.generators     := [];
  626.     T.orbit          := [ b ];
  627.     T.transversal    := [];
  628.     T.transversal[b] := S.identity;
  629.     PermGroupOps.AddGensExtOrb( T, S.generators );
  630.  
  631.     # initialize $T.stabilizer$, which will become $T_b$
  632.     T.stabilizer := rec();
  633.     T.stabilizer.identity       := T.identity;
  634.     T.stabilizer.generators:=ShallowCopy(S.stabilizer.stabilizer.generators);
  635.     T.stabilizer.orbit          := [ a ];
  636.     T.stabilizer.transversal    := [];
  637.     T.stabilizer.transversal[a] := T.identity;
  638.  
  639.     # in the end $|b^T||a^{T_b}| = [T:T_{ab}] = [S:S_{ab}] = |a^S||b^{S_a}|$
  640.     ind := 1;
  641.     while Length(T.orbit) * Length(T.stabilizer.orbit)
  642.         < Length(S.orbit) * Length(S.stabilizer.orbit)  do
  643.  
  644.         # choose a point $pnt \in a^S \ a^{T_b}$ with representative $s$
  645.         repeat ind := ind + 1;  until not S.orbit[ind] in T.stabilizer.orbit;
  646.         pnt := S.orbit[ind];
  647.  
  648.         # find out what $s^-$ does with $b$ (without computing $s$!)
  649.         img := b;
  650.         i := pnt;
  651.         while i <> a  do
  652.             img := img ^ S.transversal[i];
  653.             i   := i   ^ S.transversal[i];
  654.         od;
  655.  
  656.         # if $b^{s^-}} \in b^{S_a}$ with representative $r \in S_a$
  657.         if IsBound(S.stabilizer.transversal[img])  then
  658.  
  659.             # with $gen = s^- r^-$ we have
  660.             # $b^gen = {b^{s^-}}^{r^-} = img^{r-} = b$, so $gen \in S_b$
  661.             # and $pnt^gen = {pnt^{s^-}}^{r^-} = a^{r-} = a$, so $gen$ is new
  662.             gen := S.transversal[pnt];
  663.             while pnt ^ gen <> a  do
  664.                 gen := gen * S.transversal[pnt^gen];
  665.             od;
  666.             while b ^ gen <> b  do
  667.                 gen := gen * S.stabilizer.transversal[b^gen];
  668.             od;
  669.  
  670.             # add the new generator to $T_b$ and extend orbit and transversal
  671.             PermGroupOps.AddGensExtOrb( T.stabilizer, [ gen ] );
  672.  
  673.         fi;
  674.  
  675.     od;
  676.  
  677.     # copy everything back into the stabchain
  678.     S.generators                 := T.generators;
  679.     S.orbit                      := T.orbit;
  680.     S.transversal                := T.transversal;
  681.     if Length(T.stabilizer.orbit) = 1  then
  682.         S.stabilizer             := S.stabilizer.stabilizer;
  683.     else
  684.         S.stabilizer.generators  := T.stabilizer.generators;
  685.         S.stabilizer.orbit       := T.stabilizer.orbit;
  686.         S.stabilizer.transversal := T.stabilizer.transversal;
  687.     fi;
  688.  
  689. end;
  690.  
  691.  
  692. #############################################################################
  693. ##
  694. #F  PermGroupOps.ForcePointStabChain(<S>,<pnt>) .  force a point in the orbit
  695. ##
  696. PermGroupOps.ForcePointStabChain := function ( S, pnt )
  697.  
  698.     # do nothing if <pnt> is already in the orbit of <S>
  699.     if not IsBound(S.orbit)  or not pnt in S.orbit  then
  700.  
  701.         # if all generators of <S> fix <pnt> insert a trivial stabilizer
  702.         if ForAll( S.generators, gen -> pnt ^ gen = pnt )  then
  703.  
  704.             InfoPermGroup2("#I      inserting trivial stabilizer for ",
  705.                            pnt," on level ",SC_level,"\n");
  706.  
  707.             S.stabilizer              := ShallowCopy( S );
  708.             S.stabilizer.generators   := ShallowCopy( S.generators );
  709.             S.orbit                   := [ pnt ];
  710.             S.transversal             := [];
  711.             S.transversal[pnt]        := S.identity;
  712.  
  713.         # otherwise
  714.         else
  715.  
  716.             # get <pnt> in the orbit of the stabilizer
  717.             SC_level := SC_level + 1;
  718.             PermGroupOps.ForcePointStabChain( S.stabilizer, pnt );
  719.             SC_level := SC_level - 1;
  720.  
  721.             # and swap the two stabilizers
  722.             PermGroupOps.SwapStabChain( S );
  723.  
  724.         fi;
  725.  
  726.     else
  727.         InfoPermGroup2("#I      found ",pnt," on level ",SC_level,"\n");
  728.     fi;
  729.  
  730. end;
  731.  
  732.  
  733. #############################################################################
  734. ##
  735. #F  PermGroupOps.ConjugateStabChain(<G>,<g>)  . . . . . conjugate a stabchain
  736. ##
  737. PermGroupOps.ConjugateStabChain := function ( G, g )
  738.     local    S,         # stabilizer in stabchain
  739.              str,       # strong generating system
  740.              cnj,       # conjugated strong generating system
  741.              old,       # old generators of a stabilizer
  742.              orb,       # old orbit of a stabilizer
  743.              trn,       # old transversal of a stabilizer
  744.              i;         # loop variable
  745.  
  746.     # initialize the strong generators and their conjugates
  747.     str := [ G.identity ];
  748.     cnj := [ G.identity ];
  749.  
  750.     # go down the stabchain to conjugate every stabilizer
  751.     S := G;
  752.     while S.generators <> []  do
  753.  
  754.         # conjugate the generators of this stabilizer
  755.         old := S.generators;
  756.         S.generators := [];
  757.         for i  in [1..Length(old)]  do
  758.             if not old[i] in str  then
  759.                 Add( str, old[i] );
  760.                 Add( cnj, old[i] ^ g );
  761.             fi;
  762.             S.generators[i] := cnj[ Position(str,old[i]) ];
  763.         od;
  764.  
  765.         # conjugate the orbit and the transversal of this stabilizer
  766.         orb           := S.orbit;
  767.         trn           := S.transversal;
  768.         S.orbit       := [];
  769.         S.transversal := [];
  770.         for i  in [1..Length(orb)]  do
  771.             S.orbit[i]                := orb[i] ^ g;
  772.             S.transversal[S.orbit[i]] := cnj[ Position(str,trn[orb[i]]) ];
  773.         od;
  774.  
  775.         # on to the next stabilizer
  776.         S := S.stabilizer;
  777.  
  778.     od;
  779.  
  780. end;
  781.  
  782.  
  783. #############################################################################
  784. ##
  785. #F  PermGroupOps.ChangeStabChain(<G>,<base>)  . . . . . .  change a stabchain
  786. #F                                                       for a different base
  787. ##
  788. PermGroupOps.ChangeStabChain := function ( G, base )
  789.     local   S,          # stabilizer in the stabchain
  790.             cnj,        # conjugating permutation
  791.             i;          # loop variable
  792.  
  793.     # give some information
  794.     SC_level := 1;
  795.     InfoPermGroup1("#I  ChangeStabChain called\n");
  796.  
  797.     # intialize the conjugating permutation
  798.     cnj := G.identity;
  799.  
  800.     # go down the stabchain
  801.     S := G;
  802.     i := 1;
  803.     while i <= Length(base)  and IsBound(S.stabilizer)  do
  804.  
  805.         # do not insert trivial stabilizers
  806.         if ForAny( S.generators, gen->(base[i]^cnj)^gen<>base[i]^cnj )  then
  807.  
  808.             # get the <i>th point of the base into the orbit of $H$
  809.             InfoPermGroup2("#I    force ",base[i]^cnj," (=",base[i],"^cnj) ",
  810.                            "to level ",SC_level,"\n");
  811.             PermGroupOps.ForcePointStabChain( S, base[i]^cnj );
  812.  
  813.             # extend the conjugating permutation
  814.             while base[i]^cnj <> S.orbit[1]  do
  815.                 cnj := cnj * S.transversal[base[i]^cnj];
  816.             od;
  817.  
  818.             # on to the next stabilizer
  819.             S := S.stabilizer;
  820.             SC_level := SC_level + 1;
  821.  
  822.         else
  823.             InfoPermGroup2("#I    skip ",base[i]^cnj," (=",base[i],"^cnj) ",
  824.                            "on level ",SC_level,"\n");
  825.         fi;
  826.  
  827.         # on to the next basepoint
  828.         i := i + 1;
  829.  
  830.     od;
  831.  
  832.     # conjugate <G> to move all the points to the beginning of their orbits
  833.     if cnj <> G.identity  then
  834.         InfoPermGroup2("#I    conjugating\n");
  835.  
  836.         # do not conjugate on the top level where we want to keep the gens
  837.         G.orbit                   := [ G.orbit[1] ^ (cnj^-1) ];
  838.         G.transversal             := [];
  839.         G.transversal[G.orbit[1]] := G.identity;
  840.         G.operations.AddGensExtOrb( G, G.generators );
  841.  
  842.         # conjugate on the other levels
  843.         PermGroupOps.ConjugateStabChain( G.stabilizer, cnj^-1 );
  844.     fi;
  845.  
  846.     # unbind the, now probably incorrect, base component
  847.     Unbind( G.base );
  848.     InfoPermGroup1("#I  ChangeStabChain done\n");
  849. end;
  850.  
  851.  
  852. #############################################################################
  853. ##
  854. #F  ReduceStabChain(<G>)  . . . . remove trivial stabilizers from a stabchain
  855. ##
  856. ##  We say that a  stabilizer chain is  reduced if it contains no stabilizers
  857. ##  <S> that are equal to '<S>.stabilizer',  i.e., for which  '<S>.orbit' has
  858. ##  length 1.  Usually it is  better to work  with reduced stabilizer chains,
  859. ##  however sometimes one wants to have a stabilizer chain corresponding to a
  860. ##  specific choice of basepoints (see "IntersectionPermGroup").
  861. ##
  862. ReduceStabChain := function ( G )
  863.     G.operations.ReduceStabChain( G );
  864. end;
  865.  
  866. PermGroupOps.ReduceStabChain := function ( G )
  867.     local   S;          # stabilizer in the stabchain
  868.  
  869.     # go down the stabchain and remove trivial stabilizers
  870.     S := G;
  871.     while S.generators <> []  do
  872.  
  873.         # if this stabilizer is trivial copy the entries from the next level
  874.         if Length(S.orbit) = 1  then
  875.             S.identity    := S.stabilizer.identity;
  876.             S.generators  := S.stabilizer.generators;
  877.             S.orbit       := S.stabilizer.orbit;
  878.             S.transversal := S.stabilizer.transversal;
  879.             S.stabilizer  := S.stabilizer.stabilizer;
  880.  
  881.         # otherwise go on with the next level
  882.         else
  883.             S := S.stabilizer;
  884.  
  885.         fi;
  886.  
  887.     od;
  888.  
  889.     # remove trivial stabilizers at the end of the stabchain
  890.     Unbind( S.orbit       );
  891.     Unbind( S.transversal );
  892.     Unbind( S.stabilizer  );
  893.  
  894.     # unbind the, now probably incorrect, base component
  895.     Unbind( G.base );
  896. end;
  897.  
  898.  
  899. #############################################################################
  900. ##
  901. #F  ExtendStabChain(<G>,<base>) . . insert trivial stabilizers in a stabchain
  902. ##
  903. ExtendStabChain := function ( G, base )
  904.     G.operations.ExtendStabChain( G, base );
  905. end;
  906.  
  907. PermGroupOps.ExtendStabChain := function ( G, base )
  908.     local   S,          # stabilizer of <G>
  909.             i;          # loop variable
  910.  
  911.     # go down the stabchain and insert trivial stabilizers
  912.     S := G;
  913.     i := 1;
  914.     while i <= Length(base)  do
  915.  
  916.         # if necessary append a trivial stabilizer
  917.         if S.generators = []  then
  918.  
  919.             S.orbit                   := [ base[i] ];
  920.             S.transversal             := [];
  921.             S.transversal[base[i]]    := S.identity;
  922.             S.stabilizer              := rec();
  923.             S.stabilizer.identity     := S.identity;
  924.             S.stabilizer.generators   := [];
  925.  
  926.         # if necessary insert a trivial stabilizer
  927.         elif base[i] <> S.orbit[1]  then
  928.  
  929.             # test that the new base is really an extension of the current
  930.             if ForAny( S.generators, gen -> base[i]^gen <> base[i] )  then
  931.                 Error("<base> must reduce to base of <G>");
  932.             fi;
  933.  
  934.             S.stabilizer              := ShallowCopy(S);
  935.             S.stabilizer.generators   := ShallowCopy( S.generators );
  936.             S.orbit                   := [ base[i] ];
  937.             S.transversal             := [];
  938.             S.transversal[base[i]]    := S.identity;
  939.             
  940.         fi;
  941.  
  942.         # on to the next basepoint and the next stabilizer
  943.         S := S.stabilizer;
  944.         i := i + 1;
  945.  
  946.     od;
  947.  
  948.     # unbind the, now probably incorrect, base component
  949.     Unbind( G.base );
  950. end;
  951.  
  952.  
  953. #############################################################################
  954. ##
  955. #F  MakeStabChain(<G>[,<base>]) . . . . . . . . .  compute a stabilizer chain
  956. #F                                                    for a permutation group
  957. ##
  958. MakeStabChain := function ( arg )
  959.     if Length(arg) = 1  then
  960.         arg[1].operations.MakeStabChain( arg[1], [] );
  961.     elif Length(arg) = 2  then
  962.         arg[1].operations.MakeStabChain( arg[1], arg[2] );
  963.     else
  964.         Error("usage: MakeStabChain( <G> [, <base>] )");
  965.     fi;
  966. end;
  967.  
  968. PermGroupOps.MakeStabChain := function ( G, base )
  969.     if G.generators <> []  and not IsBound(G.stabilizer)  then
  970.         PermGroupOps.MakeStabStrong( G, G.generators, base );
  971.     else
  972.         ReduceStabChain( G );
  973.         PermGroupOps.ChangeStabChain( G, base );
  974.     fi;
  975. end;
  976.  
  977.  
  978. #############################################################################
  979. ##
  980. #F  MakeStabChainStrongGenerators(<G>,<base>,<stronggens>)  . . . construct a
  981. #F              reduced stabilizer chain for a given strong generating system
  982. ##
  983. MakeStabChainStrongGenerators := function ( G, base, stronggens )
  984.  
  985.     # check the arguments
  986.     if    not IsPermGroup( G )  then
  987.         Error("<G> must be a permutation group");
  988.     elif  not IsList( stronggens )  then
  989.         Error("<stronggens> must be a list of permutations");
  990.     elif  not IsList( base )  then
  991.         Error("<base> must be a list of points");
  992.     fi;
  993.  
  994.     # dispatch (very likely to 'PermGroupOps.MakeStabChainStrongGenerators')
  995.     G.operations.MakeStabChainStrongGenerators( G, base, stronggens );
  996. end;
  997.  
  998. PermGroupOps.MakeStabChainStrongGenerators := function ( G, base, sgs )
  999.     local   S,          # stabilizer of <G>
  1000.             ssgs,       # subset of strong generators
  1001.             bpt;        # base point
  1002.  
  1003.     # forget old stabilizer chain (if any)
  1004.     Unbind( G.orbit );
  1005.     Unbind( G.transversal );
  1006.     Unbind( G.stabilizer );
  1007.  
  1008.     # build up the stabilizer chain
  1009.     S    := G;
  1010.     ssgs := sgs;
  1011.     for bpt  in base  do
  1012.  
  1013.         # if this step is not trivial
  1014.         if not ForAll( ssgs, gen -> bpt ^ gen = bpt )  then
  1015.  
  1016.             # enter the new generators, but not on the top level
  1017.             if ssgs <> sgs  then
  1018.                 S.generators := ssgs;
  1019.             fi;
  1020.  
  1021.             # calculate orbit and transversal on this level
  1022.             S.orbit       := [ bpt ];
  1023.             S.transversal := [];
  1024.             S.transversal[ bpt ] := S.identity;
  1025.             G.operations.AddGensExtOrb( S, S.generators );
  1026.  
  1027.             # initialize next stabilizer and compute its generators
  1028.             S.stabilizer := rec( generators := [],
  1029.                                  identity   := G.identity );
  1030.             ssgs := Filtered( ssgs, gen -> bpt ^ gen = bpt );
  1031.  
  1032.             # and go down to the next level
  1033.             S := S.stabilizer;
  1034.  
  1035.         fi;
  1036.  
  1037.     od;
  1038.  
  1039. end;
  1040.  
  1041.  
  1042. #############################################################################
  1043. ##
  1044. #F  MakeStabChainRandom(<G>[,<base>]) . . . . . .  compute a stabilizer chain
  1045. #F                                                    for a permutation group
  1046. ##
  1047. MakeStabChainRandom := function ( arg )
  1048.     if Length(arg) = 1  then
  1049.         arg[1].operations.MakeStabChainRandom( arg[1], [] );
  1050.     elif Length(arg) = 2  then
  1051.         arg[1].operations.MakeStabChainRandom( arg[1], arg[2] );
  1052.     else
  1053.         Error("usage: MakeStabChainRandom( <G> [, <base>] )");
  1054.     fi;
  1055. end;
  1056.  
  1057. PermGroupOps.MakeStabChainRandom := function ( G, base )
  1058.     if G.generators <> []  and not IsBound(G.stabilizer)  then
  1059.         PermGroupOps.MakeStabStrongRandom( G, G.generators, base );
  1060.     else
  1061.         ReduceStabChain( G );
  1062.         PermGroupOps.ChangeStabChain( G, base );
  1063.     fi;
  1064. end;
  1065.  
  1066.  
  1067. #############################################################################
  1068. ##
  1069. #F  ListStabChain(<G>)  . . stabilizer chain of a permutation group as a list
  1070. ##
  1071. ListStabChain := function ( G )
  1072.     local   S,          # stabilizer of <G>
  1073.             lst;        # stabchain, result
  1074.  
  1075.     # make sure that <G> has a stabchain
  1076.     if not IsBound(G.stabilizer)  then MakeStabChain( G );  fi;
  1077.  
  1078.     # go down the stabchain and collect the stabilizers
  1079.     lst := [];
  1080.     S := G;
  1081.     while IsBound(S.stabilizer)  do
  1082.         Add( lst, S );
  1083.         S := S.stabilizer;
  1084.     od;
  1085.     Add( lst, S );
  1086.  
  1087.     # return the stabchain
  1088.     return lst;
  1089. end;
  1090.  
  1091.  
  1092. #############################################################################
  1093. ##
  1094. #F  PermGroupOps.Elements(<G>)  . . . . . . . elements of a permutation group
  1095. ##
  1096. PermGroupOps.Elements := function ( G )
  1097.     local   elms;               # element set, result
  1098.  
  1099.     # make sure that <G> has a stabchain
  1100.     if not IsBound(G.stabilizer)  then MakeStabChain(G); fi;
  1101.  
  1102.     # compute the elements of <G>
  1103.     elms := PermGroupOps.ElementsStab( G );
  1104.  
  1105.     # return the elements
  1106.     return elms;
  1107. end;
  1108.  
  1109. PermGroupOps.ElementsStab := function ( G )
  1110.     local   elms,               # element list, result
  1111.             stb,                # elements of the stabilizer
  1112.             pnt,                # point in the orbit of <G>
  1113.             rep;                # inverse representative for that point
  1114.  
  1115.     # if <G> is trivial then it is easy
  1116.     if G.generators = []  then
  1117.         elms := [ G.identity ];
  1118.  
  1119.     # otherwise
  1120.     else
  1121.  
  1122.         # start with the empty list
  1123.         elms := [];
  1124.  
  1125.         # compute the elements of the stabilizer
  1126.         stb := PermGroupOps.ElementsStab( G.stabilizer );
  1127.  
  1128.         # loop over all points in the orbit
  1129.         for pnt  in G.orbit  do
  1130.  
  1131.            # add the corresponding coset to the set of elements
  1132.            rep := G.identity;
  1133.            while G.orbit[1] ^ rep <> pnt  do
  1134.                 rep := LeftQuotient( G.transversal[pnt/rep], rep );
  1135.            od;
  1136.            UniteSet( elms, stb * rep );
  1137.  
  1138.         od;
  1139.  
  1140.    fi;
  1141.  
  1142.    # return the result
  1143.    return elms;
  1144. end;
  1145.  
  1146.  
  1147. #############################################################################
  1148. ##
  1149. #F  PermGroupOps.IsFinite(<P>)  . . . . test if a permutation group is finite
  1150. ##
  1151. PermGroupOps.IsFinite := function ( G )
  1152.     return true;
  1153. end;
  1154.  
  1155.  
  1156. #############################################################################
  1157. ##
  1158. #F  PermGroupOps.Size(<G>)  . . . . . . . . . . . size of a permutation group
  1159. ##
  1160. PermGroupOps.Size := function ( G )
  1161.     local   S,          # stabilizer of <G>
  1162.             size;       # size of <G>, result
  1163.  
  1164.     # make sure that <G> has a stabchain
  1165.     if not IsBound(G.stabilizer)  then MakeStabChain( G );  fi;
  1166.  
  1167.     # go down the stabchain and multiply the orbitlengths
  1168.     size := 1;
  1169.     S := G;
  1170.     while S.generators <> []  do
  1171.         size := size * Length( S.orbit );
  1172.         S := S.stabilizer;
  1173.     od;
  1174.  
  1175.     # return the size
  1176.     return size;
  1177. end;
  1178.  
  1179.  
  1180. #############################################################################
  1181. ##
  1182. #F  PermGroupOps.\in(<g>,<G>)  . . . . membership test for permutation group
  1183. ##
  1184. PermGroupOps.\in := function ( g, G )
  1185.     local   S,          # stabilizer of <G>
  1186.             bpt;        # basepoint of <S>
  1187.  
  1188.     # make sure that we can proceed with the rest
  1189.     if     (   IsPerm( g ) = false
  1190.             or IsPerm( G.identity ) = false)
  1191.        and (   IsRec( g ) = false
  1192.             or IsBound( g.operations ) = false
  1193.             or IsRec( G.identity ) = false
  1194.             or IsBound( G.identity.operations ) = false
  1195.             or g.operations <> G.identity.operations)
  1196.     then
  1197.         return GroupOps.\in( g, G );
  1198.     fi;
  1199.  
  1200.     # handle special case
  1201.     if g in G.generators  then
  1202.         return true;
  1203.     fi;
  1204.  
  1205.     # make sure that <G> has a stabchain
  1206.     if not IsBound(G.stabilizer)  then MakeStabChain( G );  fi;
  1207.  
  1208.     # go down the stabchain and reduce the permutation
  1209.     S := G;
  1210.     while S.generators <> []  do
  1211.         bpt := S.orbit[1];
  1212.  
  1213.         # if '<bpt>^<g>' is not in the orbit then <g> is not in <G>
  1214.         if not IsBound(S.transversal[bpt^g])  then
  1215.             return false;
  1216.         fi;
  1217.  
  1218.         # reduce <g> into the stabilizer
  1219.         while bpt ^ g <> bpt  do
  1220.             g := g * S.transversal[bpt^g];
  1221.         od;
  1222.  
  1223.         # and test if the reduced <g> lies in the stabilizer
  1224.         S := S.stabilizer;
  1225.     od;
  1226.  
  1227.     # <g> is in the trivial iff <g> is the identity
  1228.     return g = G.identity;
  1229. end;
  1230.  
  1231.  
  1232. #############################################################################
  1233. ##
  1234. #F  PermGroupOps.Random(<G>)  . . . . . random element of a permutation group
  1235. ##
  1236. PermGroupOps.Random := function ( G )
  1237.     local   S,          # stabilizer of <G>
  1238.             rnd,        # random element of <G>, result
  1239.             pnt;        # random point in <S>.orbit
  1240.  
  1241.     # make sure that <G> has a stabchain
  1242.     if not IsBound(G.stabilizer)  then MakeStabChain( G );  fi;
  1243.  
  1244.     # go down the stabchain and multiply random representatives
  1245.     rnd := G.identity;
  1246.     S := G;
  1247.     while S.generators <> []  do
  1248.         pnt := RandomList(S.orbit) ^ rnd;
  1249.         while S.orbit[1]^rnd <> pnt  do
  1250.             rnd := LeftQuotient( S.transversal[pnt/rnd], rnd );
  1251.         od;
  1252.         S := S.stabilizer;
  1253.     od;
  1254.  
  1255.     # return the random element
  1256.     return rnd;
  1257. end;
  1258.  
  1259.  
  1260. #############################################################################
  1261. ##
  1262. #F  PermGroupOps.Order(<G>,<g>) . . . . . . . . . . .  order of a permutation
  1263. ##
  1264. PermGroupOps.Order := function ( G, g )
  1265.     return OrderPerm( g );
  1266. end;
  1267.  
  1268.  
  1269. #############################################################################
  1270. ##
  1271. #F  PermGroupOps.ConjugacyClass(<G>,<g>)  . . . conjugacy class of an element
  1272. #F                                                     in a permutation group
  1273. #V  ConjugacyClassPermGroupOps  . . .  operation record for conjugacy classes
  1274. #V                                                     in a permutation group
  1275. ##
  1276. ##  Conjugacy  classes in  permutation  groups  are   almost like   conjugacy
  1277. ##  classes  in  generic groups,  except that  'Representative'   accepts the
  1278. ##  centralizer of the second element as optional parameter.
  1279. ##
  1280. PermGroupOps.ConjugacyClass := function ( G, g )
  1281.     local   C;
  1282.  
  1283.     # make the domain
  1284.     C := GroupOps.ConjugacyClass( G, g );
  1285.  
  1286.     # enter the operations record
  1287.     C.operations := ConjugacyClassPermGroupOps;
  1288.  
  1289.     # return the conjugacy class
  1290.     return C;
  1291. end;
  1292.  
  1293. ConjugacyClassPermGroupOps := Copy( ConjugacyClassGroupOps );
  1294.  
  1295. ConjugacyClassPermGroupOps.\= := function ( C, D )
  1296.     local    isEql;
  1297.     if    IsRec( C )  and IsBound( C.isConjugacyClass )
  1298.       and IsRec( D )  and IsBound( D.isConjugacyClass )
  1299.       and C.group = D.group
  1300.     then
  1301.         if not IsBound( C.centralizer )  then
  1302.             C.centralizer := Centralizer( C.group, C.representative );
  1303.         fi;
  1304.         isEql := Size(C) = Size(D)
  1305.              and Order( C.group, C.representative )
  1306.                = Order( D.group, D.representative )
  1307.              and C.group.operations.RepresentativeConjugationElements(
  1308.                         C.group,
  1309.                         D.representative,
  1310.                         C.representative,
  1311.                         C.centralizer ) <> false;
  1312.     else
  1313.         isEql := DomainOps.\=( C, D );
  1314.     fi;
  1315.     return isEql;
  1316. end;
  1317.  
  1318. ConjugacyClassPermGroupOps.\in := function ( g, C )
  1319.     if not IsBound( C.centralizer )  then
  1320.         C.centralizer := Centralizer( C.group, C.representative );
  1321.     fi;
  1322.     return g in C.group
  1323.        and Order( C.group, g ) = Order( C.group, C.representative )
  1324.        and C.group.operations.RepresentativeConjugationElements(
  1325.                 C.group,
  1326.                 g,
  1327.                 C.representative,
  1328.                 C.centralizer ) <> false;
  1329. end;
  1330.  
  1331.  
  1332. #############################################################################
  1333. ##
  1334. #F  PermGroupOps.ConjugateSubgroup(<G>,<g>)  conjugate of a permutation group
  1335. ##
  1336. PermGroupOps.ConjugateSubgroup := function ( G, g )
  1337.     local   H,          # conjugated subgroup, result
  1338.             S,          # stabilizer of <G>
  1339.             T,          # stabilizer of <H>
  1340.             str,        # strong generators of <G>
  1341.             cnj,        # conjugated generators
  1342.             i;          # loop variable
  1343.  
  1344.     # first conjugate the generators (and the element list if present)
  1345.     H := GroupOps.ConjugateSubgroup( G, g );
  1346.  
  1347.     # now conjugate the stabchain if present
  1348.     if IsBound( G.stabilizer )  and not IsBound( H.stabilizer )  then
  1349.  
  1350.         str := Concatenation( [ G.identity ], G.generators );
  1351.         cnj := Concatenation( [ H.identity ], H.generators );
  1352.  
  1353.         # go down the stabchain and conjugate every stabilizer
  1354.         S := G;
  1355.         T := H;
  1356.         while S.generators <> []  do
  1357.  
  1358.             # conjugate the generators of this stabilizer
  1359.             T.generators := [];
  1360.             for i  in [1..Length(S.generators)]  do
  1361.                 if not S.generators[i] in str  then
  1362.                     Add( str, S.generators[i] );
  1363.                     Add( cnj, S.generators[i] ^ g );
  1364.                 fi;
  1365.                 T.generators[i]:=cnj[Position(str,S.generators[i])];
  1366.             od;
  1367.  
  1368.             # conjugate the orbit and the transversal of this stabilizer
  1369.             T.orbit       := [];
  1370.             T.transversal := [];
  1371.             for i  in [1..Length(S.orbit)]  do
  1372.                 T.orbit[i]                := S.orbit[i] ^ g;
  1373.                 T.transversal[T.orbit[i]] :=
  1374.                         cnj[ Position(str,S.transversal[S.orbit[i]]) ];
  1375.             od;
  1376.  
  1377.             # make a new stabilizer
  1378.             T.stabilizer := Group( [], T.identity );
  1379.  
  1380.             # on to the next stabilizer
  1381.             S := S.stabilizer;
  1382.             T := T.stabilizer;
  1383.         od;
  1384.  
  1385.     fi;
  1386.  
  1387.     # return the conjugated subgroup
  1388.     return H;
  1389. end;
  1390.  
  1391.  
  1392. #############################################################################
  1393. ##
  1394. #F  PermGroupOps.IsSimple(<G>)  . . . . test if a permutation group is simple
  1395. ##
  1396. ##  This  is  a most interesting function.   It  tests whether  a permutation
  1397. ##  group is  simple  by testing whether the group is  perfect and then  only
  1398. ##  looking at the size of the group and the degree of a primitive operation.
  1399. ##  Basically  it uses  the O'Nan--Scott theorem, which gives  a pretty clear
  1400. ##  description of perfect primitive groups.  This algorithm is described  in
  1401. ##  William M. Kantor,
  1402. ##  Finding Composition Factors of Permutation Groups of Degree $n\leq 10^6$,
  1403. ##  J. Symbolic Computation, 12:517--526, 1991.
  1404. ##
  1405. PermGroupOps.IsSimple := function ( G )
  1406.     local   D,          # operation domain of <G>
  1407.             hom,        # transitive constituent or blocks homomorphism
  1408.             d,          # degree of <G>
  1409.             n, m,       # $d = n^m$
  1410.             simple,     # list of orders of simple groups
  1411.             transperf,  # list of orders of transitive perfect groups
  1412.             s, t;       # loop variables
  1413.  
  1414.     # if <G> is the trivial group, it is simple
  1415.     if Size( G ) = 1  then
  1416.         return true;
  1417.     fi;
  1418.  
  1419.     # first find a transitive representation for <G>
  1420.     D := Orbit( G, PermGroupOps.SmallestMovedPoint( G ) );
  1421.     if not IsEqualSet( PermGroupOps.MovedPoints( G ), D )  then
  1422.         hom := OperationHomomorphism( G, Operation( G, D ) );
  1423.         if Size( G ) <> Size( Image( hom ) )  then
  1424.             return false;
  1425.         fi;
  1426.         G := Image( hom );
  1427.     fi;
  1428.  
  1429.     # next find a primitive representation for <G>
  1430.     D := Blocks( G, PermGroupOps.MovedPoints( G ) );
  1431.     while Length( D ) <> 1  do
  1432.         hom := OperationHomomorphism( G, Operation( G, D, OnSets ) );
  1433.         if Size( G ) <> Size( Image( hom ) )  then
  1434.             return false;
  1435.         fi;
  1436.         G := Image( hom );
  1437.         D := Blocks( G, PermGroupOps.MovedPoints( G ) );
  1438.     od;
  1439.  
  1440.     # compute the degree $d$ and express it as $d = n^m$
  1441.     D := PermGroupOps.MovedPoints( G );
  1442.     d := Length( D );
  1443.     n := SmallestRootInt( Length( D ) );
  1444.     m := LogInt( Length( D ), n );
  1445.     if 10^6 < d  then
  1446.         Error("cannot decide whether <G> is simple or not");
  1447.     fi;
  1448.  
  1449.     # if $G = C_p$, it is simple
  1450.     if    IsPrime( Size( G ) )  then
  1451.         return true;
  1452.  
  1453.     # if $G = A_d$, it is simple (unless $d < 5$)
  1454.     elif  Size( G ) = Factorial( d ) / 2  then
  1455.         return 5 <= d;
  1456.  
  1457.     # if $G = S_d$, it is not simple (except $S_2$)
  1458.     elif  Size( G ) = Factorial( d )  then
  1459.         return 2 = d;
  1460.  
  1461.     # if $G$ is not perfect, it is not simple (unless $G = C_p$, see above)
  1462.     elif  Size( DerivedSubgroup( G ) ) < Size( G )  then
  1463.         return false;
  1464.  
  1465.     # if $\|G\| = d^2$, it is not simple (Kantor's Lemma 4)
  1466.     elif  Size( G ) = d ^ 2  then
  1467.         return false;
  1468.  
  1469.     # if $d$ is a prime, <G> is simple
  1470.     elif  IsPrime( d )  then
  1471.         return true;
  1472.  
  1473.     # if $G = U(4,2)$, it is simple (operation on 27 points)
  1474.     elif  d = 27 and Size( G ) = 25920  then
  1475.         return true;
  1476.  
  1477.     # if $G = PSL(n,q)$, it is simple (operations on prime power points)
  1478.     elif  (  (d =      8 and Size(G) = (7^3-7)/2          )  # PSL(2,7)
  1479.           or (d =      9 and Size(G) = (8^3-8)            )  # PSL(2,8)
  1480.           or (d =     32 and Size(G) = (31^3-31)/2        )  # PSL(2,31)
  1481.           or (d =    121 and Size(G) =        237783237120)  # PSL(5,3)
  1482.           or (d =    128 and Size(G) = (127^3-127)/2      )  # PSL(2,127)
  1483.           or (d =   8192 and Size(G) = (8191^3-8191)/2    )  # PSL(2,8191)
  1484.           or (d = 131072 and Size(G) = (131071^3-131071)/2)  # PSL(2,131071)
  1485.           or (d = 524288 and Size(G) = (524287^3-524287)/2)) # PSL(2,524287)
  1486.       and IsTransitive( Stabilizer( G, D[1] ), Difference( D, [ D[1] ] ) )
  1487.     then
  1488.         return true;
  1489.  
  1490.     # if $d$ is a prime power, <G> is not simple (except the cases above)
  1491.     elif  IsPrimePowerInt( d )  then
  1492.         return false;
  1493.  
  1494.     # if we don't have at least an $A_5$ acting on the top, <G> is simple
  1495.     elif  m < 5  then
  1496.         return true;
  1497.  
  1498.     # otherwise we must check for some special cases
  1499.     else
  1500.  
  1501.         # orders of simple subgroups of $S_n$ with primitive normalizer
  1502.         simple := [ ,,,,,
  1503.           [60,360],,,,                  #  5: A(5), A(6)
  1504.           [60,360,1814400],,            # 10: A(5), A(6), A(10)
  1505.           [660,7920,95040,239500800],,  # 12: PSL(2,11), M(11), M(12), A(12)
  1506.           [1092,43589145600],           # 14: PSL(2,13), A(14)
  1507.           [360,2520,20160,653837184000] # 15: A(6), A(7), A(8), A(15)
  1508.         ];
  1509.  
  1510.         # orders of transitive perfect subgroups of $S_m$
  1511.         transperf := [ ,,,,
  1512.           [60],                         # 5: A(5)
  1513.           [60,360],                     # 6: A(5), A(6)
  1514.           [168,2520],                   # 7: PSL(3,2), A(7)
  1515.           [168,8168,20160]              # 8: PSL(3,2), AGL(3,2), A(8)
  1516.         ];
  1517.  
  1518.         # test the special cases (Kantor's Lemma 3)
  1519.         for s  in simple[n]  do
  1520.             for t  in transperf[m]  do
  1521.                 if    Size( G ) mod (t * s^m) = 0
  1522.                   and (((t * (2*s)^m) mod Size( G ) = 0 and s <> 360)
  1523.                     or ((t * (4*s)^m) mod Size( G ) = 0 and s =  360))
  1524.                 then
  1525.                     return false;
  1526.                 fi;
  1527.             od;
  1528.         od;
  1529.  
  1530.         # otherwise <G> is simple
  1531.         return true;
  1532.  
  1533.     fi;
  1534.  
  1535. end;
  1536.  
  1537.  
  1538. #############################################################################
  1539. ##
  1540. #F  PermGroupOps.Base(<G>)  . . . . . . . . . .  base for a permutation group
  1541. ##
  1542. PermGroupOps.Base := function ( G )
  1543.     local   S,          # stabilizer of <G>
  1544.             base;       # base <base>, result
  1545.  
  1546.     # make sure there is a stabchain
  1547.     if not IsBound(G.stabilizer)  then MakeStabChain(G);  fi;
  1548.  
  1549.     # go down the stabchain and collect the basepoints
  1550.     base := [];
  1551.     S := G;
  1552.     while IsBound(S.stabilizer)  do
  1553.         Add( base, S.orbit[1] );
  1554.         S := S.stabilizer;
  1555.     od;
  1556.  
  1557.     # return the base
  1558.     return base;
  1559. end;
  1560.  
  1561.  
  1562. #############################################################################
  1563. ##
  1564. #F  PermGroupOps.StrongGenerators(<G>)  . . . . . .  strong generating system
  1565. #F                                                     of a permutation group
  1566. ##
  1567. PermGroupOps.StrongGenerators := function ( G )
  1568.     local   S,          # stabilizer of <G>
  1569.             gens;       # strong generators, result
  1570.  
  1571.     # make sure that <G> has a stabchain
  1572.     if not IsBound(G.stabilizer)  then MakeStabChain( G );  fi;
  1573.  
  1574.     # go down the stabchain and collect the strong generators
  1575.     gens := [];
  1576.     S := G;
  1577.     while S.generators <> []  do
  1578.         UniteSet( gens, S.generators );
  1579.         S := S.stabilizer;
  1580.     od;
  1581.  
  1582.     # return the strong generators
  1583.     return gens;
  1584. end;
  1585.  
  1586.  
  1587. #############################################################################
  1588. ##
  1589. #F  PermGroupOps.Indices(<G>) . . . . . . . . . . indices of stabilizer chain
  1590. #F                                                     of a permutation group
  1591. ##
  1592. PermGroupOps.Indices := function ( G )
  1593.     local   S,          # stabilizer of <G>
  1594.             inds;       # indices, result
  1595.  
  1596.     # make sure that <G> has a stabchain
  1597.     if not IsBound(G.stabilizer)  then MakeStabChain( G );  fi;
  1598.  
  1599.     # go down the stabchain and collect the indices
  1600.     inds := [];
  1601.     S := G;
  1602.     while IsBound(S.stabilizer)  do
  1603.         Add( inds, Length( S.orbit ) );
  1604.         S := S.stabilizer;
  1605.     od;
  1606.  
  1607.     # return the indices
  1608.     return inds;
  1609. end;
  1610.  
  1611.  
  1612. #############################################################################
  1613. ##
  1614. #F  PermGroupOps.SmallestGenerators(<G>)  . . . .  smallest generating system
  1615. #F                                                     of a permutation group
  1616. ##
  1617. PermGroupOps.SmallestGenerators := function ( G )
  1618.  
  1619.     # first we need a stabilizer chain with respect to the smallest base
  1620.     MakeStabChain( G, G.operations.MovedPoints( G ) );
  1621.  
  1622.     # call the recursive function to do the work
  1623.     return G.operations.SmallestGeneratorsStab( G );
  1624. end;
  1625.  
  1626. PermGroupOps.SmallestGeneratorsStab := function ( S )
  1627.     local   gens,       # smallest generating system of <S>, result
  1628.             gen,        # one generator in <gens>
  1629.             orb,        # basic orbit of <S>
  1630.             pnt,        # one point in <orb>
  1631.             T;          # stabilizer in <S>
  1632.  
  1633.     # handle the anchor case
  1634.     if S.generators = []  then
  1635.         return [];
  1636.     fi;
  1637.  
  1638.     # now get the smallest generating system of the stabilizer
  1639.     gens := PermGroupOps.SmallestGeneratorsStab( S.stabilizer );
  1640.  
  1641.     # get the sorted orbit (the basepoint will be the first point)
  1642.     orb := Set( S.orbit );
  1643.     SubtractSet( orb, [S.orbit[1]] );
  1644.  
  1645.     # handle the other points in the orbit
  1646.     while orb <> []  do
  1647.  
  1648.         # take the smallest point (coset) and one representative
  1649.         pnt := orb[1];
  1650.         gen := S.identity;
  1651.         while S.orbit[1] ^ gen <> pnt  do
  1652.            gen := LeftQuotient( S.transversal[ pnt / gen ], gen );
  1653.         od;
  1654.  
  1655.         # the next generator is the smallest element in this coset
  1656.         T := S.stabilizer;
  1657.         while T.generators <> []  do
  1658.             pnt := Minimum( OnTuples( T.orbit, gen ) );
  1659.             while T.orbit[1] ^ gen <> pnt  do
  1660.                 gen := LeftQuotient( T.transversal[ pnt / gen ], gen );
  1661.             od;
  1662.             T := T.stabilizer;
  1663.         od;
  1664.  
  1665.         # add this generator to the generators list and reduce orbit
  1666.         Add( gens, gen );
  1667.         SubtractSet( orb, Orbit( Group( gens, () ), S.orbit[1] ) );
  1668.  
  1669.     od;
  1670.  
  1671.     # return the smallest generating system
  1672.     return gens;
  1673. end;
  1674.  
  1675.  
  1676. #############################################################################
  1677. ##
  1678. #F  PermGroupOps.SylowSubgroup(<G>,<p>) . . . . . . . . . . .  Sylow subgroup
  1679. #F                                                     of a permutation group
  1680. ##
  1681. PermGroupOps.SylowSubgroup := function ( G, p )
  1682.     local   S,          # <p>-Sylow subgroup of <G>, result
  1683.             q,          # largest power of <p> dividing the size of <G>
  1684.             D,          # domain of operation of <G>
  1685.             O,          # one orbit of <G> in this domain
  1686.             B,          # blocks of the operation of <G> on <D>
  1687.             f,          # operation homomorphism of <G> on <O> or <B>
  1688.             T,          # <p>-Sylow subgroup in the image of <f>
  1689.             g, g2,      # one <p> element of <G>
  1690.             C, C2;      # centralizer of <g> in <G>
  1691.  
  1692.     # get the size of the <p>-Sylow subgroup
  1693.     q := 1;  while Size( G ) mod (q * p) = 0  do q := q * p;  od;
  1694.     InfoGroup1("#I  ",p,"-SylowSubgroup in ",GroupString(G,"G"),"\n");
  1695.  
  1696.     # handle trivial subgroup
  1697.     if   q = 1  then
  1698.         InfoGroup1("#I  ",p,"-SylowSubgroup returns trivial subgroup\n");
  1699.         return TrivialSubgroup( G );
  1700.     fi;
  1701.  
  1702.     # go down in stabilizers as long as possible
  1703.     if not IsBound( G.orbit )  then MakeStabChain( G );  fi;
  1704.     while Length( G.orbit ) mod p <> 0  do
  1705.         InfoGroup2("#I    go down to stabilizer\n");
  1706.         G := Stabilizer( G, G.orbit[1] );
  1707.     od;
  1708.  
  1709.     # handle full group
  1710.     if q = Size( G )  then
  1711.         InfoGroup2("#I  ",p,"-SylowSubgroup returns full group\n");
  1712.         return G;
  1713.     fi;
  1714.  
  1715.     # handle <p>-Sylow subgroups of size <p>
  1716.     if q = p  then
  1717.         InfoGroup2("#I  ",p,"-SylowSubgroup returns cyclic group\n");
  1718.         repeat g := Random( G );  until Order( G, g ) mod p = 0;
  1719.         g := g ^ (Order( G, g ) / p);
  1720.         return Subgroup( Parent(G), [ g ] );
  1721.     fi;
  1722.  
  1723.     # if the group is not transitive work with the transive constituents
  1724.     D := PermGroupOps.MovedPoints( G );
  1725.     if not IsTransitive( G, D )  then
  1726.         S := G;
  1727.         while q < Size( S )  do
  1728.             InfoGroup2("#I    approximation is ",GroupString(S,"S"),"\n");
  1729.             O := Orbit( S, D[1] );
  1730.             f := OperationHomomorphism( S, Operation( S, O ) );
  1731.             T := PermGroupOps.SylowSubgroup( Image( f ), p );
  1732.             S := PreImage( f, T );
  1733.             SubtractSet( D, O );
  1734.         od;
  1735.         InfoGroup1("#I  ",p,"-SylowSubgroup returns ",
  1736.                    GroupString(S,"S"),"\n");
  1737.         return S;
  1738.     fi;
  1739.  
  1740.     # if the group is not primitive work in the image first
  1741.     B := Blocks( G, D );
  1742.     if Length( B ) <> 1  then
  1743.         f := OperationHomomorphism( G, Operation( G, B, OnSets ) );
  1744.         T := PermGroupOps.SylowSubgroup( Image( f ), p );
  1745.         if Size( T ) < Size( Image( f ) )  then
  1746.             S := PermGroupOps.SylowSubgroup( PreImage( f, T ), p );
  1747.             InfoGroup1("#I  ",p,"-Sylow subgroup returns ",
  1748.                         GroupString(S,"S"),"\n");
  1749.             return S;
  1750.         fi;
  1751.     fi;
  1752.  
  1753.     # find a <p> element whose centralizer contains a full <p>-Sylow subgroup
  1754.     repeat g := Random( G );  until Order( G, g ) mod p = 0;
  1755.     g := g ^ (Order( G, g ) / p);
  1756.     C := Centralizer( G, g );
  1757.     Size( C );
  1758.     InfoGroup2("#I  ","  ",p,"-element centralizer is ",
  1759.                 GroupString(C,"C"),"\n");
  1760.     while GcdInt( q, Size( C ) ) < q  do
  1761.         repeat g2 := Random( C );  until Order( G, g2 ) mod p = 0;
  1762.         g2 := g2 ^ (Order( G, g2 ) / p);
  1763.         C2 := Centralizer( G, g2 );
  1764.         if GcdInt( q, Size( C ) ) < GcdInt( q, Size( C2 ) )  then
  1765.             C := C2;  g := g2;
  1766.             InfoGroup2("#I  ","  ",p,"-element centralizer is ",
  1767.                        GroupString(C,"C"),"\n");
  1768.         fi;
  1769.     od;
  1770.  
  1771.     # the centralizer operates on the cycles of the <p> element
  1772.     B := List( Cycles( g, D ), Set );
  1773.     f := OperationHomomorphism( C, Operation( C, B, OnSets ) );
  1774.     T := PermGroupOps.SylowSubgroup( Image( f ), p );
  1775.     S := PreImage( f, T );
  1776.     InfoGroup1("#I  ",p,"-SylowSubgroup returns ",GroupString(S,"S"),"\n");
  1777.     return S;
  1778.  
  1779. end;
  1780.  
  1781.  
  1782. #############################################################################
  1783. ##
  1784. #F  PermGroupOps.Exponent( <G> )  . . . . . . . . . . . . . . exponent of <G>
  1785. ##
  1786. PermGroupOps.Exponent := function( G )
  1787.     return Lcm( Set( List( ConjugacyClasses(G),
  1788.             x -> Order( G, Representative(x) ) ) ) );
  1789. end;
  1790.  
  1791.  
  1792. #############################################################################
  1793. ##
  1794. #R  Read  . . . . . . . . . . . . .  read other function from the other files
  1795. ##
  1796. ReadLib( "permoper" );
  1797. ReadLib( "permbckt" );
  1798. ReadLib( "permnorm" );
  1799. ReadLib( "permcose" );
  1800. ReadLib( "permhomo" );
  1801. ReadLib( "permprod" );
  1802. ReadLib( "permcser" );
  1803. ReadLib( "permag"   );
  1804. ReadLib( "permctbl" );
  1805. ReadLib( "lattperm" );
  1806.  
  1807.  
  1808. #############################################################################
  1809. ##
  1810. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1811. ##
  1812. ##  Local Variables:
  1813. ##  mode:               outline
  1814. ##  outline-regexp:     "#F\\|#V\\|#E\\|#R"
  1815. ##  fill-column:        73
  1816. ##  fill-prefix:        "##  "
  1817. ##  eval:               (hide-body)
  1818. ##  End:
  1819. ##
  1820.  
  1821.  
  1822.  
  1823.