home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / operatio.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  68.6 KB  |  2,216 lines
  1. #############################################################################
  2. ##
  3. #A  operatio.g                  GAP library                  Martin Schoenert
  4. ##
  5. #A  @(#)$Id: operatio.g,v 3.27 1993/02/09 14:38:21 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains those  functions  that  deal  with  group  operations.
  10. ##
  11. #H  $Log: operatio.g,v $
  12. #H  Revision 3.27  1993/02/09  14:38:21  martin
  13. #H  changed 'Position' to 'PositionSorted' in 'Operation' etc.
  14. #H
  15. #H  Revision 3.26  1993/01/26  14:51:11  martin
  16. #H  fixed a typo in 'GroupElementsOps.CycleLenght'
  17. #H
  18. #H  Revision 3.25  1992/10/13  16:02:44  martin
  19. #H  added '<G>.operationImages'
  20. #H
  21. #H  Revision 3.24  1992/06/27  08:07:03  martin
  22. #H  moved 'OnTuples', 'OnSets', etc. into the kernel
  23. #H
  24. #H  Revision 3.23  1992/06/03  16:29:42  martin
  25. #H  added 'MaximalBlocks'
  26. #H
  27. #H  Revision 3.22  1992/05/04  19:02:18  martin
  28. #H  fixed 'OperationHomomorphism' from incorrect dispatching
  29. #H
  30. #H  Revision 3.21  1992/03/27  11:14:51  martin
  31. #H  changed mapping to general mapping and function to mapping
  32. #H
  33. #H  Revision 3.20  1992/03/11  15:30:04  martin
  34. #H  fixed a very minor bug in 'IsFixpoint'
  35. #H
  36. #H  Revision 3.19  1992/03/10  11:36:16  martin
  37. #H  added 'IsRegular' and 'IsSemiRegular'
  38. #H
  39. #H  Revision 3.18  1992/02/10  15:14:35  martin
  40. #H  added the domain 'Mappings'
  41. #H
  42. #H  Revision 3.17  1992/01/31  14:30:15  martin
  43. #H  added 'IsEquivalentOperation'
  44. #H
  45. #H  Revision 3.16  1992/01/27  14:00:23  martin
  46. #H  improved 'OperationHomomorphismOps.Kernel'
  47. #H
  48. #H  Revision 3.15  1992/01/24  14:48:16  martin
  49. #H  renamed 'Representative' to 'RepresentativeOperation'
  50. #H
  51. #H  Revision 3.14  1992/01/07  15:37:54  martin
  52. #H  added 'DegreeOperation'
  53. #H
  54. #H  Revision 3.13  1991/12/18  14:38:38  martin
  55. #H  fixed a minor bug in 'OperationHomomorphism'
  56. #H
  57. #H  Revision 3.12  1991/12/12  11:14:45  martin
  58. #H  added 'Transitivity'
  59. #H
  60. #H  Revision 3.11  1991/12/12  09:19:59  martin
  61. #H  changed 'ONPOINTS' to 'OnPoints', etc
  62. #H
  63. #H  Revision 3.10  1991/12/06  16:41:51  martin
  64. #H  added 'OperationHomomorphism'
  65. #H
  66. #H  Revision 3.9  1991/12/06  15:37:09  martin
  67. #H  changed 'Cycle' to default to 'GroupElementsOps.Cycle' etc.
  68. #H
  69. #H  Revision 3.8  1991/12/06  13:43:11  martin
  70. #H  changed 'Permutation' and 'Operation' to use 'SortParallel'
  71. #H
  72. #H  Revision 3.7  1991/11/21  13:29:39  martin
  73. #H  fixed a minor bug in 'GroupOps.IsPrimitive'
  74. #H
  75. #H  Revision 3.6  1991/11/08  14:12:33  martin
  76. #H  changed 'GroupDomain' to 'Domain'
  77. #H
  78. #H  Revision 3.5  1991/10/08  10:59:56  martin
  79. #H  fixed 'Stabilizer' from incorrect 'Closure' call
  80. #H
  81. #H  Revision 3.4  1991/09/28  12:15:55  martin
  82. #H  fixed some minor problems
  83. #H
  84. #H  Revision 3.3  1991/09/27  13:31:52  martin
  85. #H  changed to use 'GroupOps' and to call ops functions always with operation
  86. #H
  87. #H  Revision 3.2  1991/09/27  10:44:49  martin
  88. #H  'Representative' now may return 'false'
  89. #H
  90. #H  Revision 3.1  1991/09/27  10:37:36  martin
  91. #H  changed 'Stabilizer' to use 'Subgroup' and 'Closure'
  92. #H
  93. #H  Revision 3.0  1991/08/08  15:31:51  martin
  94. #H  initial revision under RCS
  95. #H
  96. ##
  97.  
  98.  
  99. #############################################################################
  100. ##
  101. #F  InfoOperation?(...) . . .  information function for the operation package
  102. ##
  103. if not IsBound(InfoOperation1)  then InfoOperation1 := Ignore;  fi;
  104. if not IsBound(InfoOperation2)  then InfoOperation2 := Ignore;  fi;
  105.  
  106.  
  107. #############################################################################
  108. ##
  109. #F  OnRightCosets( <set>, <g> ) . operation of group elements on right cosets
  110. #F  OnLeftCosets( <set>, <g> )  .  operation of group elements on left cosets
  111. OnRightCosets := function ( set, g )
  112.     local   img,  e;
  113.     img := [];
  114.     for e  in set  do
  115.         AddSet( img, e * g );
  116.     od;
  117.     return img;
  118. end;
  119.  
  120. OnLeftCosets := function ( set, g )
  121.     local   img,  e;
  122.     img := [];
  123.     for e  in set  do
  124.         AddSet( img, g * e );
  125.     od;
  126.     return img;
  127. end;
  128.  
  129.  
  130. #############################################################################
  131. ##
  132. #F  OnLines( <line>, <g> )  operation of group elements on subspaces of dim 1
  133. #F  OnSubspaces( <space>, <g> ) . .  operation of group elements on subspaces
  134. ##
  135. #N  10-Mar-92 martin still to add 'OnSubspaces'
  136. ##
  137. OnLines := function ( vec, g )
  138.     local   line, c;
  139.     line := vec * g;
  140.     for c  in line  do
  141.         if c <> c * 0  then
  142.             line := (1/c) * line;
  143.             return line;
  144.         fi;
  145.     od;
  146.     return line;
  147. end;
  148.  
  149.  
  150. #############################################################################
  151. ##
  152. #F  Cycle( <g>, <d> ) . . . . . . . .  orbit of a point under a group element
  153. ##
  154. Cycle := function ( arg )
  155.     local   cyc,  D;
  156.  
  157.     # dispatch to the appropriate function
  158.     if Length(arg) = 2  then
  159.         D := Domain( [ arg[1] ] );
  160.         cyc := D.operations.Cycle( arg[1], arg[2], OnPoints );
  161.     elif Length(arg) = 3  then
  162.         D := Domain( [ arg[1] ] );
  163.         cyc := D.operations.Cycle( arg[1], arg[2], arg[3] );
  164.     else
  165.         Error("usage: Cycle( <g>, <d> [, <operation>]");
  166.     fi;
  167.  
  168.     # return the cycle <cyc>
  169.     return cyc;
  170. end;
  171.  
  172. GroupElementsOps.Cycle := function ( g, d, opr )
  173.     local   cyc,        # cycle, result
  174.             img;        # image running through the cycle
  175.  
  176.     # standard operation
  177.     if   opr = OnPoints  then
  178.         InfoOperation1("#I  Cycle |<d>^<g>|=\c");
  179.         cyc := [ d ];
  180.         img := d ^ g;
  181.         while img <> d  do
  182.             Add( cyc, img );
  183.             img := img ^ g;
  184.         od;
  185.         InfoOperation1("\r#I  Cycle |<d>^<g>|=",Length(cyc),"\n");
  186.  
  187.     # special case for operation on pairs
  188.     elif opr = OnPairs  then
  189.         InfoOperation1("#I  Cycle |<pair>^<g>|=\c");
  190.         cyc := [ d ];
  191.         img := [ d[1]^g, d[2]^g ];
  192.         while img <> d  do
  193.             Add( cyc, img );
  194.             img := [ img[1]^g, img[2]^g ];
  195.         od;
  196.         InfoOperation1("\r#I  Cycle |<pair>^<g>|=",Length(cyc),"\n");
  197.  
  198.     # other operation
  199.     else
  200.         InfoOperation1("#I  Cycle |opr(<d>,<g>)|=\c");
  201.         cyc := [ d ];
  202.         img := opr( d, g );
  203.         while img <> d  do
  204.             Add( cyc, img );
  205.             img := opr( img, g );
  206.         od;
  207.         InfoOperation1("#I  Cycle |opr(<d>,<g>)|=",Length(cyc),"\n");
  208.  
  209.     fi;
  210.  
  211.     # return the cycle <cyc>
  212.     return cyc;
  213. end;
  214.  
  215.  
  216. #############################################################################
  217. ##
  218. #F  CycleLength( <g>, <d> ) . length of the orbit of a point under an element
  219. ##
  220. CycleLength := function ( arg )
  221.     local   len,  D;
  222.  
  223.     # dispatch to the appropriate function
  224.     if Length(arg) = 2  then
  225.         D := Domain( [ arg[1] ] );
  226.         len := D.operations.CycleLength( arg[1], arg[2], OnPoints );
  227.     elif Length(arg) = 3  then
  228.         D := Domain( [ arg[1] ] );
  229.         len := D.operations.CycleLength( arg[1], arg[2], arg[3] );
  230.     else
  231.         Error("usage: CycleLength( <g>, <d> [, <operation>]");
  232.     fi;
  233.  
  234.     # return the length <len>
  235.     return len;
  236. end;
  237.  
  238. GroupElementsOps.CycleLength := function ( g, d, opr )
  239.     local   len,        # cycle length, result
  240.             d1,         # point in a tuple
  241.             len1,       # cycle length of a point in a tuple
  242.             img;        # image running through the cycle
  243.  
  244.     # standard operation
  245.     if   opr = OnPoints  then
  246.         InfoOperation1("#I  CycleLength |<d>^<g>|=\c");
  247.         len := 1;
  248.         img := d ^ g;
  249.         while img <> d  do
  250.             len := len + 1;
  251.             img := img ^ g;
  252.         od;
  253.         InfoOperation1("\r#I  CycleLength |<d>^<g>|=",len,"\n");
  254.  
  255.     # special case for operation on pairs and tuples
  256.     elif opr = OnPairs  or opr = OnTuples then
  257.         InfoOperation1("#I  CycleLength |<pair>^<g>|=\c");
  258.         len := 1;
  259.         for d1  in d  do
  260.             len1 := 1;
  261.             img := d1 ^ g;
  262.             while img <> d1  do
  263.                 len1 := len1 + 1;
  264.                 img := img ^ g;
  265.             od;
  266.             len := LcmInt( len, len1 );
  267.         od;
  268.         InfoOperation1("\r#I  CycleLength |<pair>^<g>|=",len,"\n");
  269.  
  270.     # other operation
  271.     else
  272.         InfoOperation1("#I  CycleLength |opr(<d>,<g>)|=\c");
  273.         len := 1;
  274.         img := opr( d, g );
  275.         while img <> d  do
  276.             len := len + 1;
  277.             img := opr( img, g );
  278.         od;
  279.         InfoOperation1("#I  CycleLength |opr(<d>,<g>)|=",len,"\n");
  280.  
  281.     fi;
  282.  
  283.     # return the cycle length <len>
  284.     return len;
  285. end;
  286.  
  287.  
  288. #############################################################################
  289. ##
  290. #F  Cycles( <g>, <D> )  . . . . . . . . . cycles of a domain under an element
  291. ##
  292. Cycles := function ( arg )
  293.     local   cycs,  D;
  294.  
  295.     # dispatch to the appropriate function
  296.     if Length(arg) = 2  then
  297.         D := Domain( [ arg[1] ] );
  298.         cycs := D.operations.Cycles( arg[1], arg[2], OnPoints );
  299.     elif Length(arg) = 3  then
  300.         D := Domain( [ arg[1] ] );
  301.         cycs := D.operations.Cycles( arg[1], arg[2], arg[3] );
  302.     else
  303.         Error("usage: Cycles( <g>, <d> [, <operation>]");
  304.     fi;
  305.  
  306.     # return the cycles <cycs>
  307.     return cycs;
  308. end;
  309.  
  310. GroupElementsOps.Cycles := function ( g, D, opr )
  311.     local   cycs,       # cycles, result
  312.             cyc,        # cycle
  313.             img;        # image running through the cycle
  314.  
  315.     # standard operation
  316.     if   opr = OnPoints  then
  317.         InfoOperation1("#I  Cycles |cycs|=\c");
  318.         D := Set( D );
  319.         cycs := [];
  320.         while D <> []  do
  321.             cyc := [ D[1] ];
  322.             img := D[1] ^ g;
  323.             while img <> D[1]  do
  324.                 Add( cyc, img );
  325.                 img := img ^ g;
  326.             od;
  327.             Add( cycs, cyc );
  328.             SubtractSet( D, cyc );
  329.             InfoOperation2("\r#I  Cycles |cycs|=",Length(cycs),"\c");
  330.         od;
  331.         InfoOperation2("\r#I  Cycles |cycs|=",Length(cycs),"\n");
  332.  
  333.     # special case for operation on pairs
  334.     elif opr = OnPairs  then
  335.         InfoOperation1("#I  Cycles |cycs|=\c");
  336.         D := Set( D );
  337.         cycs := [];
  338.         while D <> []  do
  339.             cyc := [ D[1] ];
  340.             img := [ D[1][1]^g, D[1][2]^g ];
  341.             while img <> D[1]  do
  342.                 Add( cyc, img );
  343.                 img := [ img[1]^g, img[2]^g ];
  344.             od;
  345.             Add( cycs, cyc );
  346.             SubtractSet( D, cyc );
  347.             InfoOperation2("\r#I  Cycles |cycs|=",Length(cycs),"\c");
  348.         od;
  349.         InfoOperation2("\r#I  Cycles |cycs|=",Length(cycs),"\n");
  350.  
  351.     # other operation
  352.     else
  353.         InfoOperation1("#I  Cycles |cycs|=\c");
  354.         D := Set( D );
  355.         cycs := [];
  356.         while D <> []  do
  357.             cyc := [ D[1] ];
  358.             img := opr( D[1], g );
  359.             while img <> D[1]  do
  360.                 Add( cyc, img );
  361.                 img := opr( D[1], g );
  362.             od;
  363.             Add( cycs, cyc );
  364.             SubtractSet( D, cyc );
  365.             InfoOperation2("\r#I  Cycles |cycs|=",Length(cycs),"\c");
  366.         od;
  367.         InfoOperation2("\r#I  Cycles |cycs|=",Length(cycs),"\n");
  368.  
  369.     fi;
  370.  
  371.     # return the cycles <cycs>
  372.     return cycs;
  373. end;
  374.  
  375.  
  376. #############################################################################
  377. ##
  378. #F  CycleLengths( <g>, <D> )  . . . . . . lengths of the cycles of an element
  379. ##
  380. CycleLengths := function ( arg )
  381.     local   lens,  D;
  382.  
  383.     # dispatch to the appropriate function
  384.     if Length(arg) = 2  then
  385.         D := Domain( [ arg[1] ] );
  386.         lens := D.operations.CycleLengths( arg[1], arg[2], OnPoints );
  387.     elif Length(arg) = 3  then
  388.         D := Domain( [ arg[1] ] );
  389.         lens := D.operations.CycleLengths( arg[1], arg[2], arg[3] );
  390.     else
  391.         Error("usage: CycleLengths( <g>, <d> [, <operation>]");
  392.     fi;
  393.  
  394.     # return the lengths <lens>
  395.     return lens;
  396. end;
  397.  
  398. GroupElementsOps.CycleLengths := function ( g, D, opr )
  399.     local   lens,       # cycle lengths, result
  400.             cyc,        # cycle
  401.             img;        # image running through the cycle
  402.  
  403.     # standard operation
  404.     if   opr = OnPoints  then
  405.         InfoOperation1("#I  CycleLengths |cycs|=\c");
  406.         D := Set( D );
  407.         lens := [];
  408.         while D <> []  do
  409.             cyc := [ D[1] ];
  410.             img := D[1] ^ g;
  411.             while img <> D[1]  do
  412.                 Add( cyc, img );
  413.                 img := img ^ g;
  414.             od;
  415.             Add( lens, Length( cyc ) );
  416.             SubtractSet( D, cyc );
  417.             InfoOperation2("\r#I  CycleLengths |lens|=",
  418.                            Length(lens),"\c");
  419.         od;
  420.         InfoOperation2("\r#I  CycleLengths |lens|=",
  421.                        Length(lens),"\n");
  422.  
  423.     # special case for operation on pairs
  424.     elif opr = OnPairs  then
  425.         InfoOperation1("#I  CycleLengths |lens|=\c");
  426.         D := Set( D );
  427.         lens := [];
  428.         while D <> []  do
  429.             cyc := [ D[1] ];
  430.             img := [ D[1][1]^g, D[1][2]^g ];
  431.             while img <> D[1]  do
  432.                 Add( cyc, img );
  433.                 img := [ img[1]^g, img[2]^g ];
  434.             od;
  435.             Add( lens, Length( cyc ) );
  436.             SubtractSet( D, cyc );
  437.             InfoOperation2("\r#I  CycleLengths |lens|=",
  438.                            Length(lens),"\c");
  439.         od;
  440.         InfoOperation2("\r#I  CycleLengths |lens|=",
  441.                        Length(lens),"\n");
  442.  
  443.     # other operation
  444.     else
  445.         InfoOperation1("#I  CycleLengths |lens|=\c");
  446.         D := Set( D );
  447.         lens := [];
  448.         while D <> []  do
  449.             cyc := [ D[1] ];
  450.             img := opr( D[1], g );
  451.             while img <> D[1]  do
  452.                 Add( cyc, img );
  453.                 img := opr( D[1], g );
  454.             od;
  455.             Add( lens, Length( cyc ) );
  456.             SubtractSet( D, cyc );
  457.             InfoOperation2("\r#I  CycleLengths |lens|=",
  458.                            Length(lens),"\c");
  459.         od;
  460.         InfoOperation2("\r#I  CycleLengths |lens|=",
  461.                        Length(lens),"\n");
  462.  
  463.     fi;
  464.  
  465.     # return the cycle lengths <lens>
  466.     return lens;
  467. end;
  468.  
  469.  
  470. #############################################################################
  471. ##
  472. #F  Permutation( <g>, <D> ) . . .  permutation of a group element on a domain
  473. ##
  474. Permutation := function ( arg )
  475.     local   prm,  D;
  476.  
  477.     # dispatch to the appropriate function
  478.     if Length(arg) = 2  then
  479.         D := Domain( [ arg[1] ] );
  480.         prm := D.operations.Permutation( arg[1], arg[2], OnPoints );
  481.     elif Length(arg) = 3  then
  482.         D := Domain( [ arg[1] ] );
  483.         prm := D.operations.Permutation( arg[1], arg[2], arg[3] );
  484.     else
  485.         Error("usage: Permutation( <g>, <d> [, <operation>]");
  486.     fi;
  487.  
  488.     # return the permutation <prm>
  489.     return prm;
  490. end;
  491.  
  492. GroupElementsOps.Permutation := function ( g, D, opr )
  493.     local   prm,        # permutation, result
  494.             set,        # domain <D> as set for faster Position
  495.             pos,        # Position(<D>,<x>) = <pos>[ Position(<set>,<x>) ]
  496.             i;          # loop variable
  497.  
  498.     # standard operation
  499.     if   opr = OnPoints  then
  500.         InfoOperation1("#I  Permutation(<g>,<D>)              \c");
  501.  
  502.         # make a sorted copy <set> of the domain <D> and remember <pos>
  503.         InfoOperation2("\r#I  Permutation(<g>,<D>) sorting <D>\c");
  504.         set := ShallowCopy(D);
  505.         pos := [1..Length(D)];
  506.         SortParallel( set, pos );
  507.  
  508.         # check the domain <D> and give a hint that <set> is a set
  509.         if not IsSet( set )  then
  510.             Error("<D> must not contain an element twice");
  511.         fi;
  512.  
  513.         # make the permutation <prm>
  514.         InfoOperation2("\r#I  Permutation(<g>,<D>) make perm \c");
  515.         prm := [];
  516.         for i  in [1..Length(D)]  do
  517.             prm[i] := pos[ PositionSorted( set, D[i]^g ) ];
  518.         od;
  519.         prm := PermList( prm );
  520.         InfoOperation1("\r#I  Permutation(<g>,<D>) returns   \n");
  521.  
  522.     # special case for operation on pairs
  523.     elif opr = OnPairs  then
  524.         InfoOperation1("#I  Permutation(<g>,<D>)              \c");
  525.  
  526.         # make a sorted copy <set> of the domain <D> and remember <pos>
  527.         InfoOperation2("\r#I  Permutation(<g>,<D>) sorting <D>\c");
  528.         set := ShallowCopy(D);
  529.         pos := [1..Length(D)];
  530.         SortParallel( set, pos );
  531.  
  532.         # check the domain <D> and give a hint that <set> is a set
  533.         if not IsSet( set )  then
  534.             Error("<D> must not contain an element twice");
  535.         fi;
  536.  
  537.         # make the permutation <prm>
  538.         InfoOperation2("\r#I  Permutation(<g>,<D>) make perm \c");
  539.         prm := [];
  540.         for i  in [1..Length(D)]  do
  541.             prm[i] := pos[ PositionSorted( set, [ D[i][1]^g, D[i][2]^g ] ) ];
  542.         od;
  543.         prm := PermList( prm );
  544.         InfoOperation1("\r#I  Permutation(<g>,<D>) returns   \n");
  545.  
  546.     # other operation
  547.     else
  548.         InfoOperation1("#I  Permutation(<g>,<D>)              \c");
  549.  
  550.         # make a sorted copy <set> of the domain <D> and remember <pos>
  551.         InfoOperation2("\r#I  Permutation(<g>,<D>) sorting <D>\c");
  552.         set := ShallowCopy(D);
  553.         pos := [1..Length(D)];
  554.         SortParallel( set, pos );
  555.  
  556.         # check the domain <D> and give a hint that <set> is a set
  557.         if not IsSet( set )  then
  558.             Error("<D> must not contain an element twice");
  559.         fi;
  560.  
  561.         # make the permutation <prm>
  562.         InfoOperation2("\r#I  Permutation(<g>,<D>) make perm \c");
  563.         prm := [];
  564.         for i  in [1..Length(D)]  do
  565.             prm[i] := pos[ PositionSorted( set, opr( D[i], g ) ) ];
  566.         od;
  567.         prm := PermList( prm );
  568.         InfoOperation1("\r#I  Permutation(<g>,<D>) returns   \n");
  569.  
  570.     fi;
  571.  
  572.     # return the permutation <prm>
  573.     return prm;
  574. end;
  575.  
  576.  
  577. #############################################################################
  578. ##
  579. #F  IsFixpoint( <G>, <d> )  . . test if a group operates trivially on a point
  580. ##
  581. IsFixpoint := function ( arg )
  582.     local   G,          # group, first argument or alternatively
  583.             g,          # group element, first argument
  584.             d,          # point, second argument
  585.             opr,        # operation, optional third argument
  586.             isFix;      # is the point <d> a fixpoint, result
  587.  
  588.     # standard operation of a group element
  589.     if Length(arg) = 2  and not IsGroup(arg[1])  then
  590.         g := arg[1];  d := arg[2];
  591.         isFix := (d^g = d);
  592.  
  593.     # special case for operation on pairs of a group element
  594.     elif Length(arg) = 3  and arg[3] = OnPairs  and not IsGroup(arg[1])  then
  595.         g := arg[1];  d := arg[2];
  596.         isFix := (d[1]^g = d[1] and d[2]^g = d[2]);
  597.  
  598.     # other operation of a group element
  599.     elif Length(arg) = 3  and not IsGroup(arg[1])  then
  600.         g := arg[1];  d := arg[2];
  601.         opr := arg[3];
  602.         isFix := (opr(d,g) = d);
  603.  
  604.     # standard operation of a group
  605.     elif Length(arg) = 2  then
  606.         G := arg[1];  d := arg[2];
  607.         isFix := true;
  608.         for g  in G.generators  do
  609.             isFix := isFix and (d^g = d);
  610.         od;
  611.  
  612.     # special case for operation on pairs of a group
  613.     elif Length(arg) = 3  and arg[3] = OnPairs  then
  614.         G := arg[1];  d := arg[2];
  615.         isFix := true;
  616.         for g  in G.generators  do
  617.             isFix := isFix and (d[1]^g = d[1] and d[2]^g = d[2]);
  618.         od;
  619.  
  620.     # other operation of a group
  621.     elif Length(arg) = 3  then
  622.         G := arg[1];  d := Set( arg[2] );
  623.         opr := arg[3];
  624.         isFix := true;
  625.         for g  in G.generators  do
  626.             isFix := isFix and (opr(d,g) = d);
  627.         od;
  628.  
  629.     else
  630.         Error("usage: IsFixpoint( <G>, <d> [, <operation>] )");
  631.     fi;
  632.  
  633.     # return the result
  634.     return isFix;
  635. end;
  636.  
  637.  
  638. #############################################################################
  639. ##
  640. #F  IsFixpointFree( <G>, <D> )  . . .  test if a group operates fixpoint free
  641. ##
  642. IsFixpointFree := function ( arg )
  643.     local   isFree, D;
  644.  
  645.     # special case for group element
  646.     if not IsGroup(arg[1])  then
  647.         if Length(arg) = 2  then
  648.             D := Domain( [ arg[1] ] );
  649.             isFree := D.operations.IsFixpointFree(arg[1],arg[2],OnPoints);
  650.         elif Length(arg) = 3  then
  651.             D := Domain( [ arg[1] ] );
  652.             isFree := D.operations.IsFixpointFree(arg[1],arg[2],arg[3]);
  653.         else
  654.             Error("usage: IsFixpointFree( <g>, <D> [, <operation>] )");
  655.         fi;
  656.  
  657.     # for a group use the operations function
  658.     else
  659.         if Length(arg) = 2  then
  660.             isFree:=arg[1].operations.IsFixpointFree(arg[1],arg[2],OnPoints);
  661.         elif Length(arg) = 3  then
  662.             isFree:=arg[1].operations.IsFixpointFree(arg[1],arg[2],arg[3]);
  663.         else
  664.             Error("usage: IsFixpointFree( <G>, <d> [, <operation>]");
  665.         fi;
  666.  
  667.     fi;
  668.  
  669.     # return the result
  670.     return isFree;
  671. end;
  672.  
  673. GroupElementsOps.IsFixpointFree := function ( g, D, opr )
  674.     local   isFree,     # has the domain <D> no fixpoint, result
  675.             pnt;        # point of the domain <D>
  676.  
  677.     # standard operation
  678.     if   opr = OnPoints  then
  679.         isFree := true;
  680.         for pnt  in D  do
  681.             isFree := isFree and (pnt^g <> pnt);
  682.         od;
  683.  
  684.     # special case for the operation on pairs
  685.     elif opr = OnPairs  then
  686.         isFree := true;
  687.         for pnt  in D  do
  688.             isFree := isFree and (pnt[1]^g <> pnt[1] or pnt[2]^g <> pnt[2]);
  689.         od;
  690.  
  691.     # other operation
  692.     else
  693.         isFree := true;
  694.         for pnt  in D  do
  695.             isFree := isFree and (opr(pnt,g) <> pnt);
  696.         od;
  697.  
  698.     fi;
  699.  
  700.     # return the result
  701.     return isFree;
  702. end;
  703.  
  704. GroupOps.IsFixpointFree := function ( G, D, opr )
  705.     local   isFree,     # has the domain <D> no fixpoint, result
  706.             gen,        # generator of the group <G>
  707.             pnt;        # point of the domain <D>
  708.  
  709.     # standard operation
  710.     if   opr = OnPoints  then
  711.         isFree := true;
  712.         for pnt  in D  do
  713.             if isFree  then
  714.                 isFree := false;
  715.                 for gen  in G.generators  do
  716.                     isFree := isFree or (pnt^gen <> pnt);
  717.                 od;
  718.             fi;
  719.         od;
  720.  
  721.     # special case for operation on pairs of a group
  722.     elif opr = OnPairs  then
  723.         isFree := true;
  724.         for pnt  in D  do
  725.             if isFree  then
  726.                 isFree := false;
  727.                 for gen  in G.generators  do
  728.                     isFree := isFree
  729.                            or (pnt[1]^gen <> pnt[1] or pnt[2]^gen <> pnt[2]);
  730.                 od;
  731.             fi;
  732.         od;
  733.  
  734.     # other operation of a group
  735.     else
  736.         isFree := true;
  737.         for pnt  in D  do
  738.             if isFree  then
  739.                 isFree := false;
  740.                 for gen  in G.generators  do
  741.                     isFree := isFree or (opr(pnt,gen) <> pnt);
  742.                 od;
  743.             fi;
  744.         od;
  745.  
  746.     fi;
  747.  
  748.     # return the result
  749.     return isFree;
  750. end;
  751.  
  752.  
  753. #############################################################################
  754. ##
  755. #F  DegreeOperation( <G>, <D> ) . . . . . . . . . . .  degree of an operation
  756. ##
  757. DegreeOperation := function ( arg )
  758.     local   deg;        # degree of <G> on <D>, result
  759.  
  760.     # dispatch to the appropriate function
  761.     if Length(arg) = 2  then
  762.         deg := arg[1].operations.DegreeOperation(arg[1],arg[2],OnPoints);
  763.     elif Length(arg) = 3  then
  764.         deg := arg[1].operations.DegreeOperation(arg[1],arg[2],arg[3]);
  765.     else
  766.         Error("usage: DegreeOperation( <G>, <D> [, <operation>]");
  767.     fi;
  768.  
  769.     # return the degree
  770.     return deg;
  771. end;
  772.  
  773. GroupOps.DegreeOperation := function ( G, D, opr )
  774.     local   deg,        # degree of <G> on <D>, result
  775.             gen,        # generator of the group <G>
  776.             pnt,        # point of the domain <D>
  777.             isFree;     # 'true' if <pnt> is moved by at least one <gen>
  778.  
  779.     # standard operation
  780.     if   opr = OnPoints  then
  781.         deg := 0;
  782.         for pnt  in D  do
  783.             isFree := false;
  784.             for gen  in G.generators  do
  785.                 isFree := isFree or (pnt^gen <> pnt);
  786.             od;
  787.             if isFree  then
  788.                 deg := deg + 1;
  789.             fi;
  790.         od;
  791.  
  792.     # special case for operation on pairs of a group
  793.     elif opr = OnPairs  then
  794.         deg := 0;
  795.         for pnt  in D  do
  796.             isFree := false;
  797.             for gen  in G.generators  do
  798.                 isFree := isFree
  799.                        or (pnt[1]^gen <> pnt[1] or pnt[2]^gen <> pnt[2]);
  800.             od;
  801.             if isFree  then
  802.                 deg := deg + 1;
  803.             fi;
  804.         od;
  805.  
  806.     # other operation of a group
  807.     else
  808.         deg := 0;
  809.         for pnt  in D  do
  810.             isFree := false;
  811.             for gen  in G.generators  do
  812.                 isFree := isFree or (opr(pnt,gen) <> pnt);
  813.             od;
  814.             if isFree  then
  815.                 deg := deg + 1;
  816.             fi;
  817.         od;
  818.  
  819.     fi;
  820.  
  821.     # return the degree
  822.     return deg;
  823. end;
  824.  
  825.  
  826. #############################################################################
  827. ##
  828. #F  IsTransitive( <G>, <D> )  test if a group operates transitive on a domain
  829. ##
  830. IsTransitive := function ( arg )
  831.     local   isTrans;
  832.  
  833.     # dispatch to the appropriate function
  834.     if Length(arg) = 2  then
  835.         isTrans := arg[1].operations.IsTransitive(arg[1],arg[2],OnPoints);
  836.     elif Length(arg) = 3  then
  837.         isTrans := arg[1].operations.IsTransitive(arg[1],arg[2],arg[3]);
  838.     else
  839.         Error("usage: IsTransitive( <G>, <D> [, <operation>]");
  840.     fi;
  841.  
  842.     # return the result
  843.     return isTrans;
  844. end;
  845.  
  846. GroupOps.IsTransitive := function ( G, D, opr )
  847.     local   isTrans;
  848.  
  849.     # test whether the domain is a subset of a single orbit
  850.     if D = []  then
  851.         isTrans := true;
  852.     else
  853.         isTrans := IsSubsetSet( G.operations.Orbit( G, D[1], opr ), D );
  854.     fi;
  855.  
  856.     # return the result
  857.     return isTrans;
  858. end;
  859.  
  860.  
  861. #############################################################################
  862. ##
  863. #F  Transitivity( <G>, <D> )  . . . . . . . . .  transitivity of an operation
  864. ##
  865. Transitivity := function ( arg )
  866.     local   trans;      # transitivity of <G> on <D>, result
  867.  
  868.     # dispatch to the appropriate function
  869.     if Length(arg) = 2  then
  870.         trans := arg[1].operations.Transitivity(arg[1],arg[2],OnPoints);
  871.     elif Length(arg) = 3  then
  872.         trans := arg[1].operations.Transitivity(arg[1],arg[2],arg[3]);
  873.     else
  874.         Error("usage: Transitivity( <G>, <D> [, <operation>]");
  875.     fi;
  876.  
  877.     # return the transitivity
  878.     return trans;
  879. end;
  880.  
  881. GroupOps.Transitivity := function ( G, D, opr )
  882.     if D = []  or not G.operations.IsTransitive( G, D, opr )  then
  883.         return 0;
  884.     else
  885.         return 1 + Transitivity( Stabilizer( G, D[1], opr ),
  886.                                  Difference( D, [ D[1] ] ),
  887.                                  opr );
  888.     fi;
  889. end;
  890.  
  891.  
  892. #############################################################################
  893. ##
  894. #F  IsRegular( <G>, <D> ) . . . . . . . . .  test if a group operates regular
  895. ##
  896. IsRegular := function ( arg )
  897.     local   isReg, D;
  898.  
  899.     # dispatch to the appropriate function
  900.     if Length(arg) = 2  then
  901.         isReg := arg[1].operations.IsRegular( arg[1], arg[2], OnPoints );
  902.     elif Length(arg) = 3  then
  903.         isReg := arg[1].operations.IsRegular( arg[1], arg[2], arg[3] );
  904.     else
  905.         Error("usage: IsRegular( <G>, <d> [, <operation>]");
  906.     fi;
  907.  
  908.     # return the result
  909.     return isReg;
  910. end;
  911.  
  912. GroupOps.IsRegular := function ( G, D, opr )
  913.     return     IsTransitive(  G, D, opr )
  914.            and IsSemiRegular( G, D, opr );
  915. end;
  916.  
  917.  
  918. #############################################################################
  919. ##
  920. #F  IsSemiRegular( <G>, <D> )  . . . . . test if a group operates semiregular
  921. ##
  922. IsSemiRegular := function ( arg )
  923.     local   isReg, D;
  924.  
  925.     # dispatch to the appropriate function
  926.     if Length(arg) = 2  then
  927.         isReg := arg[1].operations.IsSemiRegular( arg[1], arg[2], OnPoints );
  928.     elif Length(arg) = 3  then
  929.         isReg := arg[1].operations.IsSemiRegular( arg[1], arg[2], arg[3] );
  930.     else
  931.         Error("usage: IsSemiRegular( <G>, <d> [, <operation>]");
  932.     fi;
  933.  
  934.     # return the result
  935.     return isReg;
  936. end;
  937.  
  938. GroupOps.IsSemiRegular := function ( G, D, opr )
  939.     return IsSemiRegular( Operation(G,D,opr), [1..Length(D)] );
  940. end;
  941.  
  942.  
  943. #############################################################################
  944. ##
  945. #F  Orbit( <G>, <d> ) . . . . . . . . . . . .  orbit of a point under a group
  946. ##
  947. Orbit := function ( arg )
  948.     local   orb;
  949.  
  950.     # dispatch to the appropriate function
  951.     if Length(arg) = 2  then
  952.         orb := arg[1].operations.Orbit( arg[1], arg[2], OnPoints );
  953.     elif Length(arg) = 3  then
  954.         orb := arg[1].operations.Orbit( arg[1], arg[2], arg[3] );
  955.     else
  956.         Error("usage: Orbit( <G>, <d> [, <operation>]");
  957.     fi;
  958.  
  959.     # return the orbit <orb>
  960.     return orb;
  961. end;
  962.  
  963. GroupOps.Orbit := function ( G, d, opr )
  964.     local   orb,        # orbit, result
  965.             set,        # orbit <orb> as set for faster membership test
  966.             gen,        # generator of the group <G>
  967.             pnt,        # point in the orbit <orb>
  968.             img;        # image of the point <pnt> under the generator <gen>
  969.  
  970.     # standard operation
  971.     if   opr = OnPoints  then
  972.         InfoOperation1("#I  Orbit |<d>^<G>|=\c");
  973.         orb := [ d ];
  974.         set := [ d ];
  975.         for pnt  in orb  do
  976.             for gen  in G.generators  do
  977.                 img := pnt ^ gen;
  978.                 if not img in set  then
  979.                     Add( orb, img );
  980.                     AddSet( set, img );
  981.                 fi;
  982.             od;
  983.         od;
  984.         InfoOperation1("\r#I  Orbit |<d>^<G>|=",Length(orb),"\n");
  985.  
  986.     # special case for operation on pairs
  987.     elif opr = OnPairs  then
  988.         InfoOperation1("#I  Orbit |<pair>^<G>|=\c");
  989.         orb := [ d ];
  990.         set := [ d ];
  991.         for pnt  in orb  do
  992.             for gen  in G.generators  do
  993.                 img := [ pnt[1]^gen, pnt[2]^gen ];
  994.                 if not img in set  then
  995.                     Add( orb, img );
  996.                     AddSet( set, img );
  997.                 fi;
  998.             od;
  999.         od;
  1000.         InfoOperation1("\r#I  Orbit |<pair>^<G>|=",Length(orb),"\n");
  1001.  
  1002.     # other operation
  1003.     else
  1004.         InfoOperation1("#I  Orbit |opr(<d>,<G>)|=\c");
  1005.         orb := [ d ];
  1006.         set := [ d ];
  1007.         for pnt  in orb  do
  1008.             for gen  in G.generators  do
  1009.                 img := opr( pnt, gen );
  1010.                 if not img in set  then
  1011.                     Add( orb, img );
  1012.                     AddSet( set, img );
  1013.                 fi;
  1014.             od;
  1015.         od;
  1016.         InfoOperation1("\r#I  Orbit |opr(<d>,<G>)|=",Length(orb),"\n");
  1017.  
  1018.     fi;
  1019.  
  1020.     # return the orbit <orb>
  1021.     return orb;
  1022. end;
  1023.  
  1024.  
  1025. #############################################################################
  1026. ##
  1027. #F  OrbitLength( <G>, <d> ) . .  length of the orbit of a point under a group
  1028. ##
  1029. OrbitLength := function ( arg )
  1030.     local   len;
  1031.  
  1032.     # dispatch to the appropriate function
  1033.     if Length(arg) = 2  then
  1034.         len := arg[1].operations.OrbitLength( arg[1], arg[2], OnPoints );
  1035.     elif Length(arg) = 3  then
  1036.         len := arg[1].operations.OrbitLength( arg[1], arg[2], arg[3] );
  1037.     else
  1038.         Error("usage: OrbitLength( <G>, <d> [, <operation>]");
  1039.     fi;
  1040.  
  1041.     # return the length <len>
  1042.     return len;
  1043. end;
  1044.  
  1045. GroupOps.OrbitLength := function ( G, d, opr )
  1046.     local   len;
  1047.  
  1048.     # compute the length
  1049.     len := Length( G.operations.Orbit( G, d, opr ) );
  1050.  
  1051.     # return the length <len>
  1052.     return len;
  1053. end;
  1054.  
  1055.  
  1056. #############################################################################
  1057. ##
  1058. #F  Orbits( <G>, <D> )  . . . . . . . . . .  orbits of a domain under a group
  1059. ##
  1060. Orbits := function ( arg )
  1061.     local   orbs;
  1062.  
  1063.     # dispatch to the appropriate function
  1064.     if Length(arg) = 2  then
  1065.         orbs := arg[1].operations.Orbits( arg[1], arg[2], OnPoints );
  1066.     elif Length(arg) = 3  then
  1067.         orbs := arg[1].operations.Orbits( arg[1], arg[2], arg[3] );
  1068.     else
  1069.         Error("usage: Orbits( <G>, <D> [, <operation>]");
  1070.     fi;
  1071.  
  1072.     # return the orbits <orbs>
  1073.     return orbs;
  1074. end;
  1075.  
  1076. GroupOps.Orbits := function ( G, D, opr )
  1077.     local   orbs,       # orbits, result
  1078.             orb,        # orbit
  1079.             set,        # orbit <orb> as set for faster membership test
  1080.             gen,        # generator of the group <G>
  1081.             pnt,        # point in the orbit <orb>
  1082.             img;        # image of the point <pnt> under the generator <gen>
  1083.  
  1084.     # standard operation
  1085.     if   opr = OnPoints  then
  1086.         InfoOperation1("#I  Orbits |orbs|=\c");
  1087.         D := Set( D );
  1088.         orbs := [];
  1089.         while D <> []  do
  1090.             orb := [ D[1] ];
  1091.             set := [ D[1] ];
  1092.             for pnt  in orb  do
  1093.                 for gen  in G.generators  do
  1094.                     img := pnt ^ gen;
  1095.                     if not img in set  then
  1096.                         Add( orb, img );
  1097.                         AddSet( set, img );
  1098.                     fi;
  1099.                 od;
  1100.             od;
  1101.             Add( orbs, orb );
  1102.             SubtractSet( D, orb );
  1103.             InfoOperation2("\r#I  Orbits |orbs|=",Length(orbs),"\c");
  1104.         od;
  1105.         InfoOperation1("\r#I  Orbits |orbs|=",Length(orbs),"\n");
  1106.  
  1107.     # special case for operation on pairs
  1108.     elif opr = OnPairs  then
  1109.         InfoOperation1("#I  Orbits |orbs|=\c");
  1110.         D := Set( D );
  1111.         orbs := [];
  1112.         while D <> []  do
  1113.             orb := [ D[1] ];
  1114.             set := [ D[1] ];
  1115.             for pnt  in orb  do
  1116.                 for gen  in G.generators  do
  1117.                     img := [ pnt[1]^gen, pnt[2]^gen ];
  1118.                     if not img in set  then
  1119.                         Add( orb, img );
  1120.                         AddSet( set, img );
  1121.                     fi;
  1122.                 od;
  1123.             od;
  1124.             Add( orbs, orb );
  1125.             SubtractSet( D, orb );
  1126.             InfoOperation2("\r#I  Orbits |orbs|=",Length(orbs),"\c");
  1127.         od;
  1128.         InfoOperation1("\r#I  Orbits |orbs|=",Length(orbs),"\n");
  1129.  
  1130.     # other operation
  1131.     else
  1132.         InfoOperation1("#I  Orbits |orbs|=\c");
  1133.         D := Set( D );
  1134.         orbs := [];
  1135.         while D <> []  do
  1136.             orb := [ D[1] ];
  1137.             set := [ D[1] ];
  1138.             for pnt  in orb  do
  1139.                 for gen  in G.generators  do
  1140.                     img := opr( pnt, gen );
  1141.                     if not img in set  then
  1142.                         Add( orb, img );
  1143.                         AddSet( set, img );
  1144.                     fi;
  1145.                 od;
  1146.             od;
  1147.             Add( orbs, orb );
  1148.             SubtractSet( D, orb );
  1149.             InfoOperation2("\r#I  Orbits |orbs|=",Length(orbs),"\c");
  1150.         od;
  1151.         InfoOperation1("\r#I  Orbits |orbs|=",Length(orbs),"\n");
  1152.  
  1153.     fi;
  1154.  
  1155.     # return the orbits <orbs>
  1156.     return orbs;
  1157. end;
  1158.  
  1159.  
  1160. #############################################################################
  1161. ##
  1162. #F  OrbitLengths( <G>, <D> )  . . . . . . .  lengths of the orbits of a group
  1163. ##
  1164. OrbitLengths := function ( arg )
  1165.     local   lens;
  1166.  
  1167.     # dispatch to the appropriate function
  1168.     if Length(arg) = 2  then
  1169.         lens := arg[1].operations.OrbitLengths( arg[1], arg[2], OnPoints );
  1170.     elif Length(arg) = 3  then
  1171.         lens := arg[1].operations.OrbitLengths( arg[1], arg[2], arg[3] );
  1172.     else
  1173.         Error("usage: OrbitLengths( <G>, <D> [, <operation>]");
  1174.     fi;
  1175.  
  1176.     # return the orbit lengths <lens>
  1177.     return lens;
  1178. end;
  1179.  
  1180. GroupOps.OrbitLengths := function ( G, D, opr )
  1181.     local   lens,       # orbit lengths, result
  1182.             orb,        # orbit
  1183.             set,        # orbit <orb> as set for faster membership test
  1184.             gen,        # generator of the group <G>
  1185.             pnt,        # point in the orbit <orb>
  1186.             img;        # image of the point <pnt> under the generator <gen>
  1187.  
  1188.     # standard operation
  1189.     if   opr = OnPoints  then
  1190.         InfoOperation1("#I  OrbitLengths |orbs|=\c");
  1191.         D := Set( D );
  1192.         lens := [];
  1193.         while D <> []  do
  1194.             orb := [ D[1] ];
  1195.             set := [ D[1] ];
  1196.             for pnt  in orb  do
  1197.                 for gen  in G.generators  do
  1198.                     img := pnt ^ gen;
  1199.                     if not img in set  then
  1200.                         Add( orb, img );
  1201.                         AddSet( set, img );
  1202.                     fi;
  1203.                 od;
  1204.             od;
  1205.             Add( lens, Length(orb) );
  1206.             SubtractSet( D, orb );
  1207.             InfoOperation2("\r#I  OrbitLengths |orbs|=",
  1208.                            Length(lens),"\c");
  1209.         od;
  1210.         InfoOperation1("\r#I  OrbitLengths |orbs|=",
  1211.                        Length(lens),"\n");
  1212.  
  1213.     # special case for operation on pairs
  1214.     elif opr = OnPairs  then
  1215.         InfoOperation1("#I  OrbitLengths |orbs|=\c");
  1216.         D := Set( D );
  1217.         lens := [];
  1218.         while D <> []  do
  1219.             orb := [ D[1] ];
  1220.             set := [ D[1] ];
  1221.             for pnt  in orb  do
  1222.                 for gen  in G.generators  do
  1223.                     img := [ pnt[1]^gen, pnt[2]^gen ];
  1224.                     if not img in set  then
  1225.                         Add( orb, img );
  1226.                         AddSet( set, img );
  1227.                     fi;
  1228.                 od;
  1229.             od;
  1230.             Add( lens, Length(orb) );
  1231.             SubtractSet( D, orb );
  1232.             InfoOperation2("\r#I  OrbitLengths |orbs|=",
  1233.                            Length(lens),"\c");
  1234.         od;
  1235.         InfoOperation1("\r#I  OrbitLengths |orbs|=",
  1236.                        Length(lens),"\n");
  1237.  
  1238.     # other operation
  1239.     else
  1240.         InfoOperation1("#I  OrbitLengths |orbs|=\c");
  1241.         D := Set( D );
  1242.         lens := [];
  1243.         while D <> []  do
  1244.             orb := [ D[1] ];
  1245.             set := [ D[1] ];
  1246.             for pnt  in orb  do
  1247.                 for gen  in G.generators  do
  1248.                     img := opr( pnt, gen );
  1249.                     if not img in set  then
  1250.                         Add( orb, img );
  1251.                         AddSet( set, img );
  1252.                     fi;
  1253.                 od;
  1254.             od;
  1255.             Add( lens, Length(orb) );
  1256.             SubtractSet( D, orb );
  1257.             InfoOperation2("\r#I  OrbitLengths |orbs|=",
  1258.                            Length(lens),"\c");
  1259.         od;
  1260.         InfoOperation1("\r#I  OrbitLengths |orbs|=",
  1261.                        Length(lens),"\n");
  1262.  
  1263.     fi;
  1264.  
  1265.     # return the orbit lengths <lens>
  1266.     return lens;
  1267. end;
  1268.  
  1269.  
  1270. #############################################################################
  1271. ##
  1272. #F  Operation( <G>, <D> ) . . . . . . . . .  operation of a group on a domain
  1273. ##
  1274. Operation := function ( arg )
  1275.     local   grp;
  1276.  
  1277.     # dispatch to the appropriate function
  1278.     if Length(arg) = 2  then
  1279.         grp := arg[1].operations.Operation( arg[1], arg[2], OnPoints );
  1280.         grp.operationGroup     := arg[1];
  1281.         grp.operationDomain    := arg[2];
  1282.         grp.operationOperation := OnPoints;
  1283.     elif Length(arg) = 3  then
  1284.         grp := arg[1].operations.Operation( arg[1], arg[2], arg[3] );
  1285.         grp.operationGroup     := arg[1];
  1286.         grp.operationDomain    := arg[2];
  1287.         grp.operationOperation := arg[3];
  1288.     else
  1289.         Error("usage: Operation( <G>, <D> [, <operation>]");
  1290.     fi;
  1291.  
  1292.     # return the operation group <grp>
  1293.     return grp;
  1294. end;
  1295.  
  1296. GroupOps.Operation := function ( G, D, opr )
  1297.     local   grp,        # operation group, result
  1298.             prms,       # generators of the operation group <grp>
  1299.             prm,        # generator of the operation group <grp>
  1300.             gen,        # generator of the group <G>
  1301.             set,        # domain <D> as set for faster Position
  1302.             pos,        # Position(<D>,<x>) = <pos>[ Position(<set>,<x>) ]
  1303.             i;          # loop variable
  1304.  
  1305.     # standard operation
  1306.     if   opr = OnPoints  then
  1307.         InfoOperation1("#I  Operation(<G>,<D>)              \c");
  1308.  
  1309.         # make a sorted copy <set> of the domain <D> and remember <pos>
  1310.         InfoOperation2("\r#I  Operation(<G>,<D>) sorting <D>\c");
  1311.         set := ShallowCopy(D);
  1312.         pos := [1..Length(D)];
  1313.         SortParallel( set, pos );
  1314.  
  1315.         # check the domain <D> and give a hint that <set> is a set
  1316.         if not IsSet( set )  then
  1317.             Error("<D> must not contain an element twice");
  1318.         fi;
  1319.  
  1320.         # make the permutations <prms> and the operation group <grp>
  1321.         prms := [];
  1322.         for gen  in G.generators  do
  1323.             InfoOperation2("\r#I  Operation(<G>,<D>) make perm ",
  1324.                            Position( G.generators, gen ), "\c");
  1325.             prm := [];
  1326.             for i  in [1..Length(D)]  do
  1327.                 prm[i] := pos[ PositionSorted( set, D[i]^gen ) ];
  1328.             od;
  1329.             Add( prms, PermList( prm ) );
  1330.         od;
  1331.         grp := Group( prms, () );
  1332.         grp.operationImages := prms;
  1333.         InfoOperation1("\r#I  Operation(<G>,<D>) returns       \n");
  1334.  
  1335.     # special case for operation on pairs
  1336.     elif opr = OnPairs  then
  1337.         InfoOperation1("#I  Operation(<G>,<D>)              \c");
  1338.  
  1339.         # make a sorted copy <set> of the domain <D> and remember <pos>
  1340.         InfoOperation2("\r#I  Operation(<G>,<D>) sorting <D>\c");
  1341.         set := ShallowCopy(D);
  1342.         pos := [1..Length(D)];
  1343.         SortParallel( set, pos );
  1344.  
  1345.         # check the domain <D> and give a hint that <set> is a set
  1346.         if not IsSet( set )  then
  1347.             Error("<D> must not contain an element twice");
  1348.         fi;
  1349.  
  1350.         # make the permutations <prms> and the operation group <grp>
  1351.         prms := [];
  1352.         for gen  in G.generators  do
  1353.             InfoOperation2("\r#I  Operation(<G>,<D>) make perm ",
  1354.                            Position( G.generators, gen ), "\c");
  1355.             prm := [];
  1356.             for i  in [1..Length(D)]  do
  1357.                 prm[i] := pos[PositionSorted(set,[D[i][1]^gen,D[i][2]^gen])];
  1358.             od;
  1359.             Add( prms, PermList( prm ) );
  1360.         od;
  1361.         grp := Group( prms, () );
  1362.         grp.operationImages := prms;
  1363.         InfoOperation1("\r#I  Operation(<G>,<D>) returns       \n");
  1364.  
  1365.     # other operation
  1366.     else
  1367.         InfoOperation1("#I  Operation(<G>,<D>)              \c");
  1368.  
  1369.         # make a sorted copy <set> of the domain <D> and remember <pos>
  1370.         InfoOperation2("\r#I  Operation(<G>,<D>) sorting <D>\c");
  1371.         set := ShallowCopy(D);
  1372.         pos := [1..Length(D)];
  1373.         SortParallel( set, pos );
  1374.  
  1375.         # check the domain <D> and give a hint that <set> is a set
  1376.         if not IsSet( set )  then
  1377.             Error("<D> must not contain an element twice");
  1378.         fi;
  1379.  
  1380.         # make the permutations <prms> and the operation group <grp>
  1381.         prms := [];
  1382.         for gen  in G.generators  do
  1383.             InfoOperation2("\r#I  Operation(<G>,<D>) make perm ",
  1384.                            Position( G.generators, gen ), "\c");
  1385.             prm := [];
  1386.             for i  in [1..Length(D)]  do
  1387.                 prm[i] := pos[ PositionSorted( set, opr( D[i], gen ) ) ];
  1388.             od;
  1389.             Add( prms, PermList( prm ) );
  1390.         od;
  1391.         grp := Group( prms, () );
  1392.         grp.operationImages := prms;
  1393.         InfoOperation1("\r#I  Operation(<G>,<D>) returns       \n");
  1394.  
  1395.     fi;
  1396.  
  1397.     # return the permutation group <grp>
  1398.     return grp;
  1399. end;
  1400.  
  1401.  
  1402. #############################################################################
  1403. ##
  1404. #F  OperationHomomorphism(<G>,<P>)  . . . . . homomorphism of a group into an
  1405. #F                                              operation group of this group
  1406. ##
  1407. OperationHomomorphism := function ( G, P )
  1408.     local   hom;        # homomorphism from <G> to <P>, result
  1409.  
  1410.     # check the arguments
  1411.     if not IsGroup( P )  or not IsBound( P.operationGroup )  then
  1412.         Error("<P> must be an operation group");
  1413.     fi;
  1414.     if not IsGroup( G )  or not IsSubset( P.operationGroup, G )  then
  1415.         Error("<G> must be a group");
  1416.     fi;
  1417.  
  1418.     # make the operation homomorphism
  1419.     if G = P.operationGroup  then
  1420.         if not IsBound( P.operationHomomorphism )  then
  1421.             P.operationHomomorphism :=
  1422.                 G.operations.OperationHomomorphism( G, P );
  1423.         fi;
  1424.         hom := P.operationHomomorphism;
  1425.     else
  1426.         hom := G.operations.OperationHomomorphism( G, P );
  1427.     fi;
  1428.  
  1429.     # return the homomorphism
  1430.     return hom;
  1431. end;
  1432.  
  1433. GroupOps.OperationHomomorphism := function ( G, P )
  1434.     local   hom;        # operation homomorphism of <G> into <P>, result
  1435.  
  1436.     # make the homomorphism
  1437.     hom := rec( );
  1438.     hom.isGeneralMapping := true;
  1439.     hom.domain          := Mappings;
  1440.  
  1441.     # enter the identifying stuff
  1442.     hom.source          := G;
  1443.     hom.range           := P;
  1444.  
  1445.     # enter information
  1446.     hom.isMapping       := true;
  1447.     hom.isHomomorphism  := true;
  1448.     hom.preImage        := G;
  1449.     if G = P.operationGroup  then
  1450.         hom.image       := P;
  1451.     fi;
  1452.  
  1453.     # enter the operations record
  1454.     hom.operations      := OperationHomomorphismOps;
  1455.  
  1456.     # return the homomorphism
  1457.     return hom;
  1458. end;
  1459.  
  1460. OperationHomomorphismOps := Copy( GroupHomomorphismOps );
  1461.  
  1462. OperationHomomorphismOps.ImageElm := function ( hom, elm )
  1463.     return Permutation( elm,
  1464.                         hom.range.operationDomain,
  1465.                         hom.range.operationOperation );
  1466. end;
  1467.  
  1468. OperationHomomorphismOps.ImagesElm := function ( hom, elm )
  1469.     return [ Permutation( elm,
  1470.                           hom.range.operationDomain,
  1471.                           hom.range.operationOperation ) ];
  1472. end;
  1473.  
  1474. OperationHomomorphismOps.ImagesRepresentative := function ( hom, elm )
  1475.     return Permutation( elm,
  1476.                         hom.range.operationDomain,
  1477.                         hom.range.operationOperation );
  1478. end;
  1479.  
  1480. OperationHomomorphismOps.PreImagesRepresentative := function ( hom, elm )
  1481.     local   rep,                # representative, result
  1482.             S,                  # stabilizer of '<hom>.source'
  1483.             rep2,               # representative in <S>
  1484.             i;                  # loop variable
  1485.  
  1486.     # delegate easy cases to the source
  1487.     if hom.range.operationOperation = OnPoints  then
  1488.         rep := RepresentativeOperation(
  1489.                                hom.source,
  1490.                                hom.range.operationDomain,
  1491.                                Permuted( hom.range.operationDomain, elm^-1 ),
  1492.                                OnTuples );
  1493.  
  1494.     # handle other operations because 'Representative' would not be able to
  1495.     # recognize special cases after composing the operation with 'OnTuples'
  1496.     else
  1497.         rep := hom.source.identity;
  1498.         S   := hom.source;
  1499.         i   := 1;
  1500.         while i <= Length(hom.range.operationDomain)  and rep <> false  do
  1501.             rep2 := RepresentativeOperation(
  1502.                                    S,
  1503.                                    hom.range.operationDomain[i],
  1504.                                    hom.range.operationOperation(
  1505.                                        hom.range.operationDomain[i^elm],
  1506.                                        rep^-1 ),
  1507.                                    hom.range.operationOperation );
  1508.             if rep2 <> false  then
  1509.                 rep := rep2 * rep;
  1510.                 S   := Stabilizer( S,
  1511.                                    hom.range.operationDomain[i],
  1512.                                    hom.range.operationOperation );
  1513.             else
  1514.                 rep := false;
  1515.             fi;
  1516.             i := i + 1;
  1517.         od;
  1518.     fi;
  1519.  
  1520.     # return the representative
  1521.     return rep;
  1522. end;
  1523.  
  1524. OperationHomomorphismOps.KernelGroupHomomorphism := function ( hom )
  1525.     if hom.range.operationOperation = OnPoints  then
  1526.         return Intersection(
  1527.                     List( Orbits( hom.source,
  1528.                                   hom.range.operationDomain,
  1529.                                   OnPoints ),
  1530.                           orb -> Stabilizer( hom.source,
  1531.                                              orb,
  1532.                                              OnTuples )
  1533.                     )
  1534.                );
  1535.     else
  1536.         return Intersection(
  1537.                     List( Orbits( hom.source,
  1538.                                   hom.range.operationDomain,
  1539.                                   hom.range.operationOperation ),
  1540.                           orb -> Core( hom.source,
  1541.                                        Stabilizer( hom.source,
  1542.                                              orb[1],
  1543.                                              hom.range.operationOperation ) )
  1544.                     )
  1545.                );
  1546.     fi;
  1547. end;
  1548.  
  1549. OperationHomomorphismOps.Print := function ( hom )
  1550.     Print( "OperationHomomorphism( ", hom.source, ", ", hom.range, " )" );
  1551. end;
  1552.  
  1553.  
  1554. #############################################################################
  1555. ##
  1556. #F  Blocks(<G>,<D>[,<seed>][,<operation>])  .  blocks of operation of a group
  1557. ##
  1558. Blocks := function ( arg )
  1559.     local   blks;
  1560.  
  1561.     # dispatch to the appropriate function
  1562.     if Length(arg) = 2  then
  1563.         blks := arg[1].operations.Blocks( arg[1], arg[2], [], OnPoints );
  1564.     elif Length(arg) = 3  and IsList(arg[3])  then
  1565.         blks := arg[1].operations.Blocks( arg[1], arg[2], arg[3], OnPoints );
  1566.     elif Length(arg) = 3  and IsFunc(arg[3])  then
  1567.         blks := arg[1].operations.Blocks( arg[1], arg[2], [], arg[3] );
  1568.     elif Length(arg) = 4  then
  1569.         blks := arg[1].operations.Blocks( arg[1], arg[2], arg[3], arg[4] );
  1570.     else
  1571.         Error("usage: Blocks( <G>, <D> [, <seed>] [, <operation>]");
  1572.     fi;
  1573.  
  1574.     # return the blocks <blks>
  1575.     return blks;
  1576. end;
  1577.  
  1578. GroupOps.Blocks := function ( G, D, seed, opr )
  1579.     local   G2,         # group <G> operating on [1..Length(<D>)]
  1580.             D2,         # domain <D> as [1..Length(<D>)]
  1581.             seed2,      # seed <seed> as subset of <D2>
  1582.             blks,       # blocks, result
  1583.             blk,        # one block
  1584.             blks2,      # blocks when operationg on [1..Length(<D>)]
  1585.             blk2,       # one block when operating on [1..Length(<D>)]
  1586.             i;          # loop variable
  1587.  
  1588.     # convert domain to [1..Length(<D>)], group and seed correspondingly
  1589.     InfoOperation1("#I  BlocksGroup called\n");
  1590.     if not IsPermGroup(G) or not ForAll( D, IsInt ) or opr <> OnPoints  then
  1591.         G2 := G.operations.Operation( G, D, opr );
  1592.         D2 := [1..Length(D)];
  1593.         seed2 := List( seed, s -> Position( D, s ) );
  1594.     else
  1595.         G2 := G;
  1596.         D2 := D;
  1597.         seed2 := seed;
  1598.     fi;
  1599.  
  1600.     # compute the blocks
  1601.     blks2 := G2.operations.Blocks( G2, D2, seed2, OnPoints );
  1602.  
  1603.     # convert the blocks of [1..Length(<D>)] back into blocks of <D>
  1604.     if D <> D2  then
  1605.         blks := [];
  1606.         for blk2 in blks2  do
  1607.             blk := [];
  1608.             for i  in blk2  do
  1609.                 AddSet( blk, D[i] );
  1610.             od;
  1611.             AddSet( blks, blk );
  1612.         od;
  1613.     else
  1614.         blks := blks2;
  1615.     fi;
  1616.  
  1617.     # return the blocks <blks>
  1618.     InfoOperation1("#I  BlocksGroup |<blocks>|=",Length(blks),"\n");
  1619.     return blks;
  1620. end;
  1621.  
  1622.  
  1623. #############################################################################
  1624. ##
  1625. #F  MaximalBlocks(<G>,<D>[,<seed>][,<operation>]) . . . . . maximal blocks of
  1626. #F                                                       operation of a group
  1627. ##
  1628. MaximalBlocks := function ( arg )
  1629.     local   blks;
  1630.  
  1631.     # dispatch to the appropriate function
  1632.     if Length(arg) = 2  then
  1633.         blks := arg[1].operations.MaximalBlocks(arg[1],arg[2],[],OnPoints);
  1634.     elif Length(arg) = 3  and IsList(arg[3])  then
  1635.         blks := arg[1].operations.MaximalBlocks(arg[1],arg[2],arg[3],
  1636.                                                 OnPoints);
  1637.     elif Length(arg) = 3  and IsFunc(arg[3])  then
  1638.         blks := arg[1].operations.MaximalBlocks(arg[1],arg[2],[],arg[3]);
  1639.     elif Length(arg) = 4  then
  1640.         blks := arg[1].operations.MaximalBlocks(arg[1],arg[2],arg[3],arg[4]);
  1641.     else
  1642.         Error("usage: MaximalBlocks( <G>, <D> [, <seed>] [, <operation>]");
  1643.     fi;
  1644.  
  1645.     # return the blocks <blks>
  1646.     return blks;
  1647. end;
  1648.  
  1649. GroupOps.MaximalBlocks := function ( G, D, seed, opr )
  1650.     local   G2,         # group <G> operating on [1..Length(<D>)]
  1651.             D2,         # domain <D> as [1..Length(<D>)]
  1652.             seed2,      # seed <seed> as subset of <D2>
  1653.             blks,       # blocks, result
  1654.             blk,        # one block
  1655.             blks2,      # blocks when operationg on [1..Length(<D>)]
  1656.             blk2,       # one block when operating on [1..Length(<D>)]
  1657.             i;          # loop variable
  1658.  
  1659.     # convert domain to [1..Length(<D>)], group and seed correspondingly
  1660.     InfoOperation1("#I  MaximalBlocksGroup called\n");
  1661.     if not IsPermGroup(G) or not ForAll( D, IsInt ) or opr <> OnPoints  then
  1662.         G2 := G.operations.Operation( G, D, opr );
  1663.         D2 := [1..Length(D)];
  1664.         seed2 := List( seed, s -> Position( D, s ) );
  1665.     else
  1666.         G2 := G;
  1667.         D2 := D;
  1668.         seed2 := seed;
  1669.     fi;
  1670.  
  1671.     # compute the blocks
  1672.     blks2 := G2.operations.MaximalBlocks( G2, D2, seed2, OnPoints );
  1673.  
  1674.     # convert the blocks of [1..Length(<D>)] back into blocks of <D>
  1675.     if D <> D2  then
  1676.         blks := [];
  1677.         for blk2 in blks2  do
  1678.             blk := [];
  1679.             for i  in blk2  do
  1680.                 AddSet( blk, D[i] );
  1681.             od;
  1682.             AddSet( blks, blk );
  1683.         od;
  1684.     else
  1685.         blks := blks2;
  1686.     fi;
  1687.  
  1688.     # return the blocks <blks>
  1689.     InfoOperation1("#I  MaximalBlocksGroup |<blocks>|=",Length(blks),"\n");
  1690.     return blks;
  1691. end;
  1692.  
  1693.  
  1694. #############################################################################
  1695. ##
  1696. #F  IsPrimitive( <G>, <D> ) .  test if a group operates primitive on a domain
  1697. ##
  1698. IsPrimitive := function ( arg )
  1699.     local   isPrim;
  1700.  
  1701.     # dispatch to the appropriate function
  1702.     if Length(arg) = 2  then
  1703.         isPrim := arg[1].operations.IsPrimitive( arg[1], arg[2], OnPoints );
  1704.     elif Length(arg) = 3  then
  1705.         isPrim := arg[1].operations.IsPrimitive( arg[1], arg[2], arg[3] );
  1706.     else
  1707.         Error("usage: IsPrimitive( <G>, <D> [, <operation>]");
  1708.     fi;
  1709.  
  1710.     # return the result
  1711.     return isPrim;
  1712. end;
  1713.  
  1714. GroupOps.IsPrimitive := function ( G, D, opr )
  1715.     local   isPrim;
  1716.  
  1717.     isPrim := G.operations.IsTransitive( G, D, opr )
  1718.           and Length( G.operations.Blocks( G, D, [], opr ) ) = 1;
  1719.  
  1720.     # return the result
  1721.     return isPrim;
  1722. end;
  1723.  
  1724.  
  1725. #############################################################################
  1726. ##
  1727. #F  Stabilizer( <G>, <d> )  . . . . . . . stabilizer of a point under a group
  1728. ##
  1729. Stabilizer := function ( arg )
  1730.     local   stb;
  1731.  
  1732.     # dispatch to the appropriate function
  1733.     if Length(arg) = 2  then
  1734.         stb := arg[1].operations.Stabilizer( arg[1], arg[2], OnPoints );
  1735.     elif Length(arg) = 3  then
  1736.         stb := arg[1].operations.Stabilizer( arg[1], arg[2], arg[3] );
  1737.     else
  1738.         Error("usage: Stabilizer( <G>, <D> [, <operation>]");
  1739.     fi;
  1740.  
  1741.     # return the stabilizer <stb>
  1742.     return stb;
  1743. end;
  1744.  
  1745. GroupOps.Stabilizer := function ( G, d, opr )
  1746.     local   stb,        # stabilizer, result
  1747.             orb,        # orbit
  1748.             rep,        # representatives for the points in the orbit <orb>
  1749.             set,        # orbit <orb> as set for faster membership test
  1750.             gen,        # generator of the group <G>
  1751.             pnt,        # point in the orbit <orb>
  1752.             img,        # image of the point <pnt> under the generator <gen>
  1753.             sch;        # schreier generator of the stabilizer
  1754.  
  1755.     # standard operation
  1756.     if   opr = OnPoints  then
  1757.         InfoOperation1("#I  Stabilizer |<gens>|=0\c");
  1758.         orb := [ d ];
  1759.         set := [ d ];
  1760.         rep := [ G.identity ];
  1761.         stb := Subgroup( Parent( G ), [] );
  1762.         for pnt  in orb  do
  1763.             for gen  in G.generators  do
  1764.                 img := pnt ^ gen;
  1765.                 if not img in set  then
  1766.                     Add( orb, img );
  1767.                     AddSet( set, img );
  1768.                     Add( rep, rep[Position(orb,pnt)]*gen );
  1769.                 else
  1770.                     sch := rep[Position(orb,pnt)]*gen
  1771.                            / rep[Position(orb,img)];
  1772.                     if not sch in stb  then
  1773.                         stb := Closure( stb, sch );
  1774.                         InfoOperation2("\r#I  Stabilizer |<gens>|=",
  1775.                                        Length(stb.generators), "\c" );
  1776.                     fi;
  1777.                 fi;
  1778.             od;
  1779.         od;
  1780.         InfoOperation1("\r#I  Stabilizer |<gens>|=",
  1781.                        Length(stb.generators),"\n");
  1782.  
  1783.     # compute iterated stabilizers for the operation on pairs or on tuples
  1784.     elif opr = OnPairs  or opr = OnTuples  then
  1785.         InfoOperation1("#I  Stabilizer |<fixed points>|=0\n");
  1786.         stb := G;
  1787.         for pnt in d  do
  1788.             stb := stb.operations.Stabilizer( stb, pnt, OnPoints );
  1789.             InfoOperation2("#I  Stabilizer |<fixed points>|=",
  1790.                            Position( d, pnt ), "\n" );
  1791.         od;
  1792.         InfoOperation1("#I  Stabilizer |<fixed points>|=",
  1793.                        Length(d),"\n");
  1794.  
  1795.     # other operation
  1796.     else
  1797.         InfoOperation1("#I  Stabilizer |<gens>|=0\c");
  1798.         orb := [ d ];
  1799.         set := [ d ];
  1800.         rep := [ G.identity ];
  1801.         stb := Subgroup( Parent(G), [] );
  1802.         for pnt  in orb  do
  1803.             for gen  in G.generators  do
  1804.                 img := opr( pnt, gen );
  1805.                 if not img in set  then
  1806.                     Add( orb, img );
  1807.                     AddSet( set, img );
  1808.                     Add( rep, rep[Position(orb,pnt)]*gen );
  1809.                 else
  1810.                     sch := rep[Position(orb,pnt)]*gen
  1811.                            / rep[Position(orb,img)];
  1812.                     if not sch in stb  then
  1813.                         stb := Closure( stb, sch );
  1814.                         InfoOperation2("\r#I  Stabilizer |<gens>|=",
  1815.                                        Length(stb.generators), "\c" );
  1816.                     fi;
  1817.                 fi;
  1818.             od;
  1819.         od;
  1820.         InfoOperation1("\r#I  Stabilizer |<gens>|=",
  1821.                        Length(stb.generators),"\n");
  1822.  
  1823.     fi;
  1824.  
  1825.     # return the stabilizer <stb>
  1826.     return stb;
  1827. end;
  1828.  
  1829.  
  1830. #############################################################################
  1831. ##
  1832. #F  RepresentativeOperation(<G>,<d>,<e>)  . . . . . representative of a point
  1833. ##
  1834. RepresentativeOperation := function ( arg )
  1835.     local   rep;
  1836.  
  1837.     # dispatch to the appropriate function
  1838.     if Length(arg) = 3  then
  1839.         rep := arg[1].operations.RepresentativeOperation(
  1840.                                           arg[1], arg[2], arg[3], OnPoints );
  1841.     elif Length(arg) = 4  then
  1842.         rep := arg[1].operations.RepresentativeOperation(
  1843.                                           arg[1], arg[2], arg[3], arg[4] );
  1844.     else
  1845.       Error("usage: RepresentativeOperation( <G>, <d>, <e> [, <operation>]");
  1846.     fi;
  1847.  
  1848.     # return the representative <rep>
  1849.     return rep;
  1850. end;
  1851.  
  1852. GroupOps.RepresentativeOperation := function ( G, d, e, opr )
  1853.     local   rep,        # representative, result
  1854.             orb,        # orbit
  1855.             set,        # orbit <orb> as set for faster membership test
  1856.             gen,        # generator of the group <G>
  1857.             pnt,        # point in the orbit <orb>
  1858.             img,        # image of the point <pnt> under the generator <gen>
  1859.             by,         # <by>[<pnt>] is a gen taking <frm>[<pnt>] to <pnt>
  1860.             frm;        # where <frm>[<pnt>] lies earlier in <orb> than <pnt>
  1861.  
  1862.     # standard operation
  1863.     if   opr = OnPoints  then
  1864.         InfoOperation1("#I  RepresentativeOperation |<d>^<G>|=\c");
  1865.         if d = e  then return G.identity;  fi;
  1866.         orb := [ d ];
  1867.         set := [ d ];
  1868.         by  := [ G.identity ];
  1869.         frm := [ 1 ];
  1870.         for pnt  in orb  do
  1871.             for gen  in G.generators  do
  1872.                 img := pnt ^ gen;
  1873.                 if img = e  then
  1874.                     rep := gen;
  1875.                     while pnt <> d  do
  1876.                         rep := by[ Position(orb,pnt) ] * rep;
  1877.                         pnt := frm[ Position(orb,pnt) ];
  1878.                     od;
  1879.                     InfoOperation1("\r#I  RepresentativeOperation returns ",
  1880.                                    rep, "\n" );
  1881.                     return rep;
  1882.                 elif not img in set  then
  1883.                     Add( orb, img );
  1884.                     AddSet( set, img );
  1885.                     Add( frm, pnt );
  1886.                     Add( by,  gen );
  1887.                 fi;
  1888.             od;
  1889.         od;
  1890.         InfoOperation1("\r#I  RepresentativeOperation returns 'false'\n");
  1891.         return false;
  1892.  
  1893.     # special case for operation on pairs
  1894.     elif opr = OnPairs  then
  1895.         InfoOperation1("#I  RepresentativeOperation |<pair>^<G>|=\c");
  1896.         if d = e  then return G.identity;  fi;
  1897.         orb := [ d ];
  1898.         set := [ d ];
  1899.         by  := [ G.identity ];
  1900.         frm := [ 1 ];
  1901.         for pnt  in orb  do
  1902.             for gen  in G.generators  do
  1903.                 img := [ pnt[1]^gen, pnt[2]^gen ];
  1904.                 if img = e  then
  1905.                     rep := gen;
  1906.                     while pnt <> d  do
  1907.                         rep := by[ Position(orb,pnt) ] * rep;
  1908.                         pnt := frm[ Position(orb,pnt) ];
  1909.                     od;
  1910.                     InfoOperation1("\r#I  RepresentativeOperation returns ",
  1911.                                    rep, "\n" );
  1912.                     return rep;
  1913.                 elif not img in set  then
  1914.                     Add( orb, img );
  1915.                     AddSet( set, img );
  1916.                     Add( frm, pnt );
  1917.                     Add( by,  gen );
  1918.                 fi;
  1919.             od;
  1920.         od;
  1921.         InfoOperation1("\r#I  RepresentativeOperation returns 'false'\n");
  1922.         return false;
  1923.  
  1924.     # other operation
  1925.     else
  1926.         InfoOperation1("#I  RepresentativeOperation |opr(<d>,<G>)|=\c");
  1927.         if d = e  then return G.identity;  fi;
  1928.         orb := [ d ];
  1929.         set := [ d ];
  1930.         by  := [ G.identity ];
  1931.         frm := [ 1 ];
  1932.         for pnt  in orb  do
  1933.             for gen  in G.generators  do
  1934.                 img := opr( pnt, gen );
  1935.                 if img = e  then
  1936.                     rep := gen;
  1937.                     while pnt <> d  do
  1938.                         rep := by[ Position(orb,pnt) ] * rep;
  1939.                         pnt := frm[ Position(orb,pnt) ];
  1940.                     od;
  1941.                     InfoOperation1("\r#I  RepresentativeOperation returns ",
  1942.                                    rep, "\n" );
  1943.                     return rep;
  1944.                 elif not img in set  then
  1945.                     Add( orb, img );
  1946.                     AddSet( set, img );
  1947.                     Add( frm, pnt );
  1948.                     Add( by,  gen );
  1949.                 fi;
  1950.             od;
  1951.         od;
  1952.         InfoOperation1("\r#I  RepresentativeOperation returns 'false'\n");
  1953.         return false;
  1954.  
  1955.     fi;
  1956.  
  1957. end;
  1958.  
  1959.  
  1960. #############################################################################
  1961. ##
  1962. #F  RepresentativesOperation( <G>, <d> )  . . . . representatives of an orbit
  1963. ##
  1964. RepresentativesOperation := function ( arg )
  1965.     local   reps;
  1966.  
  1967.     # dispatch to the appropriate function
  1968.     if Length(arg) = 2  then
  1969.         reps := arg[1].operations.RepresentativesOperation(
  1970.                                                   arg[1], arg[2], OnPoints );
  1971.     elif Length(arg) = 3  then
  1972.         reps := arg[1].operations.RepresentativesOperation(
  1973.                                                   arg[1], arg[2], arg[3] );
  1974.     else
  1975.         Error("usage: RepresentativesOperation( <G>, <d> [, <operation>]");
  1976.     fi;
  1977.  
  1978.     # return the representatives <reps>
  1979.     return reps;
  1980. end;
  1981.  
  1982. GroupOps.RepresentativesOperation := function ( G, d, opr )
  1983.     local   reps,       # representatives for the points in the orbit, result
  1984.             orb,        # orbit
  1985.             set,        # orbit <orb> as set for faster membership test
  1986.             gen,        # generator of the group <G>
  1987.             pnt,        # point in the orbit <orb>
  1988.             img;        # image of the point <pnt> under the generator <gen>
  1989.  
  1990.     # standard operation
  1991.     if   opr = OnPoints  then
  1992.         InfoOperation1("#I  RepresentativesOperation |<orb>|=\c");
  1993.         orb := [ d ];
  1994.         set := [ d ];
  1995.         reps := [ G.identity ];
  1996.         for pnt  in orb  do
  1997.             for gen  in G.generators  do
  1998.                 img := pnt ^ gen;
  1999.                 if not img in set  then
  2000.                     Add( orb, img );
  2001.                     AddSet( set, img );
  2002.                     Add( reps, reps[Position(orb,pnt)]*gen );
  2003.                 fi;
  2004.             od;
  2005.         od;
  2006.         InfoOperation1("\r#I  RepresentativesOperation |<orb>|=",
  2007.                        Length(orb),"\n");
  2008.  
  2009.     # other operation
  2010.     else
  2011.         InfoOperation1("#I  RepresentativesOperation |<orb>|=0\c");
  2012.         orb := [ d ];
  2013.         set := [ d ];
  2014.         reps := [ G.identity ];
  2015.         for pnt  in orb  do
  2016.             for gen  in G.generators  do
  2017.                 img := opr( pnt, gen );
  2018.                 if not img in set  then
  2019.                     Add( orb, img );
  2020.                     AddSet( set, img );
  2021.                     Add( reps, reps[Position(orb,pnt)]*gen );
  2022.                 fi;
  2023.             od;
  2024.         od;
  2025.         InfoOperation1("\r#I  RepresentativesOperation |<orb>|=",
  2026.                        Length(orb),"\n");
  2027.  
  2028.     fi;
  2029.  
  2030.     # return the representatives <reps>
  2031.     return reps;
  2032. end;
  2033.  
  2034.  
  2035. #############################################################################
  2036. ##
  2037. #F  IsEqualOperation(<G>,<D>,<oprG>,<H>,<E>,<oprH>)  . test if two operations
  2038. #F                                                  of a group are equivalent
  2039. ##
  2040. IsEquivalentOperation := function ( arg )
  2041.     local   isEqv;      # is the operation equivalent, result
  2042.  
  2043.     # dispatch to the appropriate function
  2044.     if Length(arg) = 4  then
  2045.         isEqv := arg[1].operations.IsEquivalentOperation(
  2046.                         arg[1], arg[2], OnPoints,
  2047.                         arg[3], arg[4], OnPoints );
  2048.     elif Length( arg ) = 5  and IsGroup( arg[3] )  then
  2049.         isEqv := arg[1].operations.IsEquivalentOperation(
  2050.                         arg[1], arg[2], OnPoints,
  2051.                         arg[3], arg[4], arg[5] );
  2052.     elif Length( arg ) = 5  then
  2053.         isEqv := arg[1].operations.IsEquivalentOperation(
  2054.                         arg[1], arg[2], arg[3],
  2055.                         arg[4], arg[5], OnPoints );
  2056.     elif Length( arg ) = 6  then
  2057.         isEqv := arg[1].operations.IsEquivalentOperation(
  2058.                         arg[1], arg[2], arg[3],
  2059.                         arg[4], arg[5], arg[6] );
  2060.     else
  2061.         Error("usage: IsEquivalentOperation(<G>,<D>[,<operationG>],",
  2062.                                            "<H>,<E>[,<operationH>])");
  2063.     fi;
  2064.  
  2065.     # return the result
  2066.     return isEqv;
  2067.  
  2068. end;
  2069.  
  2070. GroupOps.IsEquivalentOperation := function ( G, D, oprG, H, E, oprH )
  2071.     local   isEqv,      # is the operation equivalent, result
  2072.             orbsG,      # orbits of <G>
  2073.             orbsH,      # orbits of <H>
  2074.             i,  k;      # loop variables
  2075.  
  2076.     # easy case first
  2077.     if DegreeOperation( G, D, oprG ) <> DegreeOperation( H, E, oprH )  then
  2078.         return false;
  2079.     fi;
  2080.  
  2081.     # compute the orbits
  2082.     orbsG := ShallowCopy( G.operations.Orbits( G, D, oprG ) );
  2083.     orbsH := ShallowCopy( H.operations.Orbits( H, E, oprH ) );
  2084.  
  2085.     # another simple test
  2086.     if Collected(List(orbsG,Length)) <> Collected(List(orbsH,Length))  then
  2087.         return false;
  2088.     fi;
  2089.  
  2090.     # loop over the orbits of <G>
  2091.     isEqv := true;
  2092.     i := 1;
  2093.     while i <= Length( orbsG )  and isEqv  do
  2094.  
  2095.         # try to match an orbit of <H>
  2096.         k := 1;
  2097.         while k <= Length( orbsH )
  2098.           and not GroupOps.IsEqvOprTrans(G,orbsG[i],oprG,H,orbsH[k],oprH)  do
  2099.             k := k + 1;
  2100.         od;
  2101.  
  2102.         # the matched orbit is no longer available in the future
  2103.         if k <= Length( orbsH )  then
  2104.             orbsH[k] := [];
  2105.         else
  2106.             isEqv := false;
  2107.         fi;
  2108.  
  2109.         i := i + 1;
  2110.     od;
  2111.  
  2112.     # return the result
  2113.     return isEqv;
  2114. end;
  2115.  
  2116. GroupOps.IsEqvOprTrans := function ( G, orbG, oprG, H, orbH, oprH )
  2117.     local   i;          # loop variable
  2118.  
  2119.     # easy case first
  2120.     if Length( orbG ) <> Length( orbH )  then
  2121.         return false;
  2122.     fi;
  2123.  
  2124.     # try all possible mappings
  2125.     for i  in [ 1 .. Length( orbH ) ]  do
  2126.         if GroupOps.IsEqvOprOrbit( G, orbG[1], oprG, H, orbH[i], oprH )  then
  2127.             return true;
  2128.         fi;
  2129.     od;
  2130.  
  2131.     # no possibility to map <orbG> onto <orbH>
  2132.     return false;
  2133. end;
  2134.  
  2135. GroupOps.IsEqvOprOrbit := function ( G, iniG, oprG, H, iniH, oprH )
  2136.     local    orbG,      # orbit of <iniG> under <G>
  2137.              orbH,      # orbit of <iniH> under <H>
  2138.              pntG,      # one point of <orbG>
  2139.              pntH,      # one point of <orbH>
  2140.              i,  k;     # loop variables
  2141.  
  2142.     # special case for standard operations
  2143.     if oprG = OnPoints  and oprH = OnPoints  then
  2144.  
  2145.         # make a parallel orbit algorithm
  2146.         orbG := [ iniG ];
  2147.         orbH := [ iniH ];
  2148.         i := 1;
  2149.         while i <= Length( orbG )  do
  2150.             for k  in [ 1 .. Length( G.generators ) ]  do
  2151.                 pntG := orbG[ i ] ^ G.generators[ k ];
  2152.                 pntH := orbH[ i ] ^ H.generators[ k ];
  2153.                 if not pntG in orbG  then
  2154.                     if pntH in orbH  then
  2155.                         return false;
  2156.                     fi;
  2157.                     Add( orbG, pntG );
  2158.                     Add( orbH, pntH );
  2159.                 else
  2160.                     if orbH[ Position( orbG, pntG ) ] <> pntH  then
  2161.                         return false;
  2162.                     fi;
  2163.                 fi;
  2164.             od;
  2165.             i := i + 1;
  2166.         od;
  2167.  
  2168.     # general case
  2169.     else
  2170.  
  2171.         # make a parallel orbit algorithm
  2172.         orbG := [ iniG ];
  2173.         orbH := [ iniH ];
  2174.         i := 1;
  2175.         while i <= Length( orbG )  do
  2176.             for k  in [ 1 .. Length( G.generators ) ]  do
  2177.                 pntG := oprG( orbG[ i ], G.generators[ k ] );
  2178.                 pntH := oprH( orbH[ i ], H.generators[ k ] );
  2179.                 if not pntG in orbG  then
  2180.                     if pntH in orbH  then
  2181.                         return false;
  2182.                     fi;
  2183.                     Add( orbG, pntG );
  2184.                     Add( orbH, pntH );
  2185.                 else
  2186.                     if orbH[ Position( orbG, pntG ) ] <> pntH  then
  2187.                         return false;
  2188.                     fi;
  2189.                 fi;
  2190.             od;
  2191.             i := i + 1;
  2192.         od;
  2193.  
  2194.     fi;
  2195.  
  2196.     # orbit computation complete, the orbits can be mapped
  2197.     return true;
  2198. end;
  2199.  
  2200.  
  2201. #############################################################################
  2202. ##
  2203. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  2204. ##
  2205. ##  Local Variables:
  2206. ##  mode:               outline
  2207. ##  outline-regexp:     "#F\\|#V\\|#E"
  2208. ##  fill-column:        73
  2209. ##  fill-prefix:        "##  "
  2210. ##  eval:               (hide-body)
  2211. ##  End:
  2212. ##
  2213.  
  2214.  
  2215.  
  2216.