home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / ctmapcon.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  105.2 KB  |  2,902 lines
  1. #############################################################################
  2. ##
  3. #A  ctmapcon.g                  GAP library                     Thomas Breuer
  4. ##
  5. #A  @(#)$Id: ctmapcon.g,v 3.27 1992/04/30 12:28:34 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains  those  functions  that  are used to construct maps,
  10. ##  (mostly fusion maps and powermaps).
  11. ##
  12. #H  $Log: ctmapcon.g,v $
  13. #H  Revision 3.27  1992/04/30  12:28:34  martin
  14. #H  fixed bug in 'SubgroupFusions'
  15. #H
  16. #H  Revision 3.26  1992/03/06  13:20:48  sam
  17. #H  little improvement in 'SubgroupFusions', stylistic changes
  18. #H
  19. #H  Revision 3.25  1992/02/24  13:17:51  sam
  20. #H  removed minor bug in 'Powermap'
  21. #H
  22. #H  Revision 3.24  1992/02/04  15:40:45  sam
  23. #H  fixed bug in 'ConsiderSmallerPowermaps'
  24. #H
  25. #H  Revision 3.23  1992/01/21  16:38:36  sam
  26. #H  added 'CheckPermChar' (up to now a part of 'InitFusion') and
  27. #H  changed 'SubgroupFusions'
  28. #H
  29. #H  Revision 3.22  1992/01/13  16:02:30  sam
  30. #H  fixed little bug in 'ConsiderTableAutomorphisms',
  31. #H  adjusted 'SubgroupFusions'
  32. #H
  33. #H  Revision 3.21  1992/01/09  11:21:45  sam
  34. #H  added default initialisation for 'InfoPermGroup2'
  35. #H
  36. #H  Revision 3.20  1991/12/27  15:27:49  sam
  37. #H  renamed 'PowermapsAllowedBySymmetrizations' to
  38. #H  'PowermapsAllowedBySymmetrisations'
  39. #H
  40. #H  Revision 3.19  1991/12/20  10:13:58  sam
  41. #H  renamed 'Kernel' to 'KernelChar'
  42. #H
  43. #H  Revision 3.18  1991/12/20  09:18:54  sam
  44. #H  changed 'Consistency' to 'TestConsistencyMaps'
  45. #H
  46. #H  Revision 3.17  1991/12/20  08:22:26  sam
  47. #H  changed call of 'LargestMovedPointPerm' to call of 'LargestMovedPoint'
  48. #H
  49. #H  Revision 3.16  1991/12/19  13:02:20  martin
  50. #H  renamed 'SupportPerm' to 'LargestMovedPointPerm'
  51. #H
  52. #H  Revision 3.15  1991/12/17  08:28:27  sam
  53. #H  little bug in InitPowermap fixed
  54. #H
  55. #H  Revision 3.14  1991/12/16  12:36:25  sam
  56. #H  fixed little bug in 'RepresentativesFusions'
  57. #H
  58. #H  Revision 3.13  1991/12/13  13:15:11  sam
  59. #H  replaced 'IsPrime' by 'IsPrimeInt'
  60. #H
  61. #H  Revision 3.12  1991/12/12  09:14:36  martin
  62. #H  changed 'ONPOINTS' to 'OnPoints'
  63. #H
  64. #H  Revision 3.11  1991/12/04  17:49:26  sam
  65. #H  added 'CharString'
  66. #H
  67. #H  Revision 3.10  1991/12/03  17:07:46  sam
  68. #H  indented functions,
  69. #H  changed functions which use permutation groups
  70. #H
  71. #H  Revision 3.9  1991/10/18  16:09:02  sam
  72. #H  check of parameters in 'Powermap' changed
  73. #H
  74. #H  Revision 3.8  1991/10/09  18:13:19  sam
  75. #H  check of parameters in 'SubgroupFusions' changed
  76. #H
  77. #H  Revision 3.7  1991/10/09  14:36:16  sam
  78. #H  simplified use of "infinity"
  79. #H
  80. #H  Revision 3.6  1991/10/02  12:36:31  sam
  81. #H  corrections
  82. #H
  83. #H  Revision 3.5  1991/10/01  13:45:00  casper
  84. #H  changed 'E(3)' to '"infinity"',
  85. #H  some '()' deleted
  86. #H
  87. #H  Revision 3.4  1991/10/01  09:16:33  sam
  88. #H  changed 'VERBOSE' to 'InfoCharTable2'
  89. #H
  90. #H  Revision 3.3  1991/09/30  13:59:54  sam
  91. #H  changed 'Gcd' to 'GcdInt'
  92. #H
  93. #H  Revision 3.2  1991/09/05  15:35:48  sam
  94. #H  changed 'GcdList' to 'Gcd'
  95. #H
  96. #H  Revision 3.1  1991/09/03  15:09:33  goetz
  97. #H  changed 'reps' to 'orders'.
  98. #H
  99. #H  Revision 3.0  1991/09/03  14:18:50  goetz
  100. #H  Initial Revision.
  101. #H
  102. ##
  103.  
  104.  
  105. #############################################################################
  106. ##
  107. #F  InfoCharTable?( ... ) . . . info function for the character table package
  108. #F  InfoPermGroup2( ... ) . . . . . . info function for the permgroup package
  109. #F  CharString( <char>, <str> ) . . . . . . . .  character information string
  110. ##
  111.     if not IsBound( InfoCharTable1 )  then InfoCharTable1 := Ignore;  fi;
  112.     if not IsBound( InfoCharTable2 )  then InfoCharTable2 := Ignore;  fi;
  113.     if not IsBound( InfoPermGroup2 )  then InfoPermGroup2 := Ignore;  fi;
  114.  
  115. CharString := function( char, str )
  116.     return ConcatenationString( str, " of degree ", String( char[1] ) );
  117.     end;
  118.  
  119.  
  120. #############################################################################
  121. ##
  122. #F  UpdateMap( <char>, <paramap>, <indirected> )
  123. ##
  124. ##  improves <paramap> using that <indirected> is the indirection (possibly
  125. ##  parametrized) of <char> by <paramap>
  126. ##
  127. UpdateMap := function( char, paramap, indirected )
  128.     local i, j, value, fus;
  129.  
  130.     for i in [ 1 .. Length( paramap ) ] do
  131.       if IsInt( paramap[i] ) then
  132.         if indirected[i] <> char[ paramap[i] ] then
  133.           Print( "#E UpdateMap: inconsistency at class ", i, "\n" );
  134.           paramap[i]:= Unknown( );
  135.         fi;
  136.       else
  137.         value:= indirected[i];
  138.         if not IsList( value ) then value:= [ value ]; fi;
  139.         fus:= [];
  140.         for j in paramap[i] do
  141.           if char[j] in value then Add( fus, j ); fi;
  142.         od;
  143.         if fus = [] then
  144.           Print( "#E UpdateMap: inconsistency at class ", i, "\n" );
  145.           paramap[i]:= Unknown( );
  146.         else
  147.           if Length( fus ) = 1 then fus:= fus[1]; fi;
  148.           paramap[i]:= fus;
  149.         fi;
  150.       fi;
  151.     od;
  152.     end;
  153.  
  154.  
  155. #############################################################################
  156. ##
  157. #F  NonnegIntScalarProducts( <tbl>, <chars>, <candidate> )
  158. ##
  159. ##  returns 'true' if all scalar products of <candidate> with the characters
  160. ##  in the list <chars> are nonegative integers, 'false' otherwise.
  161. ##
  162. NonnegIntScalarProducts := function( tbl, chars, candidate )
  163.     local i, sc, classes, order, char, weighted;
  164.  
  165.     classes:= tbl.classes;
  166.     order:= tbl.order;
  167.     weighted:= [];
  168.     for char in chars do
  169.       for i in [ 1 .. Length( char ) ] do
  170.         weighted[i]:= classes[i] * char[i];
  171.       od;
  172.       sc:= weighted * candidate;
  173.       if not IsInt( sc / order ) or sc < 0 then return false; fi;
  174.     od;
  175.     return true;
  176.     end;
  177.  
  178.  
  179. #############################################################################
  180. ##
  181. #F  IntScalarProducts( <tbl>, <chars>, <candidate> )
  182. ##
  183. ##  returns 'true' if all scalar products of <candidate> with the characters
  184. ##  in the list <chars> are integers, 'false' otherwise.
  185. ##
  186. IntScalarProducts := function( tbl, chars, candidate )
  187.     local i, classes, order, char, weighted;
  188.  
  189.     classes:= tbl.classes;
  190.     order:= tbl.order;
  191.     weighted:= [];
  192.     for char in chars do
  193.       for i in [ 1 .. Length( char ) ] do
  194.         weighted[i]:= classes[i] * char[i];
  195.       od;
  196.       if not IsInt( weighted * candidate / order ) then return false; fi;
  197.     od;
  198.     return true;
  199.     end;
  200.  
  201.  
  202. #############################################################################
  203. ##
  204. #F  ContainedSpecialVectors( <tbl>, <chars>, <paracharacter>, <func> )
  205. ##
  206. ##  returns the list of all elements <vec> of <paracharacter> which have
  207. ##  integral norm and integral scalar product with the principal character
  208. ##  of <tbl> and which satisfy <func>( <tbl>, <chars>, <vec> )
  209. ##
  210. ContainedSpecialVectors := function( tbl, chars, paracharacter, func )
  211.     local i, j, x, classes, unknown, images, number, index, direction,
  212.           pos, oldvalue, newvalue, norm, sum, possibilities, order;
  213.  
  214.     paracharacter:= ShallowCopy( paracharacter );
  215.     classes:= tbl.classes;
  216.     order:= tbl.order;
  217.     unknown:= [];
  218.     images:= [];
  219.     number:= [];
  220.     index:= [];
  221.     direction:= [];
  222.     pos:= 1;
  223.     for i in [ 1 .. Length( paracharacter ) ] do
  224.       if IsList( paracharacter[i] ) then
  225.         unknown[pos]:= i;
  226.         images[pos]:= paracharacter[i];
  227.         number[pos]:= Length( paracharacter[i]);
  228.         index[pos]:= 1;
  229.         direction[pos]:= 1;               # 1 means up, -1 means down
  230.         paracharacter[i]:= paracharacter[i][1];
  231.         pos:= pos + 1;
  232.       fi;
  233.     od;
  234.     sum:= classes * paracharacter;
  235.     norm:= classes * List( paracharacter, x -> x * GaloisCyc( x, -1 ) );
  236.     possibilities:= [];
  237.     if IsInt( sum / order ) and IsInt( norm / order) 
  238.        and func( tbl, chars, paracharacter ) then
  239.       possibilities[1]:= Copy( paracharacter );
  240.     fi;
  241.     i:= 1;
  242.     while true do
  243.       i:= 1;
  244.       while i <= Length( unknown ) and 
  245.          ( ( index[i] = number[i] and direction[i] = 1 ) or
  246.               ( index[i] = 1 and direction[i] = -1 ) ) do
  247.         direction[i]:= - direction[i];
  248.         i:= i+1;
  249.       od;
  250.       if i > Length( unknown ) then             # we are through
  251.         return possibilities;
  252.       else                                      # update at position i
  253.         oldvalue:= images[i][ index[i] ];
  254.         index[i]:= index[i] + direction[i];
  255.         newvalue:= images[i][ index[i] ];
  256.         sum:= sum + classes[ unknown[i] ] * ( newvalue - oldvalue );
  257.         norm:= norm + classes[ unknown[i] ]
  258.                 * (   newvalue * GaloisCyc( newvalue, -1 )
  259.                     - oldvalue * GaloisCyc( oldvalue, -1 ) );
  260.         if IsInt( sum / order ) and IsInt( norm / order ) then
  261.           for j in [ 1 .. Length( unknown ) ] do
  262.             paracharacter[ unknown[j] ]:= images[j][ index[j] ];
  263.           od;
  264.           if func( tbl, chars, paracharacter ) then
  265.             Add( possibilities, Copy( paracharacter ) );
  266.           fi;
  267.         fi;
  268.       fi;
  269.     od;
  270.     end;
  271.  
  272.  
  273. #############################################################################
  274. ##
  275. #F  ContainedPossibleCharacters( <tbl>, <chars>, <paracharacter> )
  276. ##
  277. ##  returns the list of all elements <vec> of <paracharacter> which have
  278. ##  integral norm, integral scalar product with the principal character
  279. ##  of <tbl> and nonnegative integral scalar product with all elements
  280. ##  of <chars>
  281. ##
  282. ContainedPossibleCharacters := function(tbl, chars, paracharacter)
  283.     return ContainedSpecialVectors( tbl, chars, paracharacter,
  284.                                     NonnegIntScalarProducts );
  285.     end;
  286.  
  287.  
  288. #############################################################################
  289. ##
  290. #F  ContainedPossibleVirtualCharacters( <tbl>, <chars>, <paracharacter> )
  291. ##
  292. ##  returns the list of all elements <vec> of <paracharacter> which have
  293. ##  integral norm, integral scalar product with the principal character
  294. ##  of <tbl> and integral scalar product with all elements of <chars>
  295. ##
  296. ContainedPossibleVirtualCharacters :=function( tbl, chars, paracharacter )
  297.     return ContainedSpecialVectors( tbl, chars, paracharacter,
  298.                                     IntScalarProducts );
  299.     end;
  300.  
  301.  
  302. #############################################################################
  303. ##
  304. #F  InitFusion( <subtbl>, <tbl> )
  305. ##
  306. ##  returns the (probably parametrized) map of the subgroup fusion from
  307. ##  <subtbl> to <tbl> using the following properties:
  308. ##
  309. ##  For any class 'i' of <subtbl> the centralizer of the image must be
  310. ##  a multiple of the centralizer of 'i', and
  311. ##
  312. ##  the representative order of 'i' is equal to the representative order
  313. ##  of its image (only used if representative orders are stored).
  314. ##
  315. ##  If no fusion map is possible, 'false' is returned.
  316. ##
  317. InitFusion := function( subtbl, tbl )
  318.     local i, j, k, upper, subcentralizers, subclasses, centralizers,
  319.           initfusion, orders, subcentralizers, suborders, sameord, elm,
  320.           errors, choice;
  321.  
  322.     if not ( IsCharTable( subtbl ) and IsCharTable( tbl ) ) then
  323.       Error( "<subtbl>, <tbl> must be character tables" );
  324.     fi;
  325.  
  326.     subcentralizers:= subtbl.centralizers;
  327.     subclasses:= subtbl.classes;
  328.     centralizers:= tbl.centralizers;
  329.     initfusion:= [];
  330.     upper:= [ 1 ]; # upper[i]: upper bound for the number of elements
  331.                    # fusing in class i
  332.     for i in [ 2 .. Length( centralizers ) ] do
  333.       upper[i]:= Minimum( subtbl.order, tbl.classes[i] );
  334.     od;
  335.  
  336.     # if orders are known
  337.     if IsBound( subtbl.orders ) and IsBound( tbl.orders ) then
  338.       orders   := tbl.orders;
  339.       suborders:= subtbl.orders;
  340.       sameord:= [];
  341.       for i in [ 1 .. Length( orders ) ] do
  342.         if IsInt( orders[i] ) then
  343.           if IsBound( sameord[ orders[i] ] ) then
  344.             AddSet( sameord[ orders[i] ], i );
  345.           else
  346.             sameord[ orders[i] ]:= [ i ];
  347.           fi;
  348.         else                 # para-orders
  349.           for j in orders[i] do
  350.             if IsBound( sameord[j] ) then
  351.               AddSet( sameord[j], i );
  352.             else
  353.               sameord[j]:= [ i ];
  354.             fi;
  355.           od;
  356.         fi;
  357.       od;
  358.       for i in [ 1 .. Length( suborders) ] do
  359.         initfusion[i]:= [];
  360.         if IsInt( suborders[i] ) then
  361.           if not IsBound( sameord[ suborders[i] ] ) then
  362.             InfoCharTable2( "#E InitFusion: no fusion possible because of ",
  363.                             "representative orders\n" );
  364.             return false;
  365.           fi;
  366.           for j in sameord[ suborders[i] ] do
  367.             if centralizers[j] mod subcentralizers[i] = 0 and
  368.                                     upper[j] >= subclasses[i] then
  369.               AddSet( initfusion[i], j );
  370.             fi;
  371.           od;
  372.         else                 # para-orders
  373.           choice:= Filtered( suborders[i], x -> IsBound( sameord[x] ) );
  374.           if choice = [] then
  375.             InfoCharTable2( "#E InitFusion: no fusion possible because of ",
  376.                             "representative orders\n" );
  377.             return false;
  378.           fi;
  379.           for elm in choice do
  380.             for j in sameord[ elm ] do
  381.               if centralizers[j] mod subcentralizers[i] = 0 then
  382.                 AddSet( initfusion[i], j );
  383.               fi;
  384.             od;
  385.           od;
  386.         fi;
  387.       od;
  388.  
  389.     # just centralizers are known:
  390.     else
  391.       for i in [ 1 .. Length( subcentralizers ) ] do
  392.         initfusion[i]:= [];
  393.         for j in [ 1 .. Length( centralizers ) ] do
  394.           if centralizers[j] mod subcentralizers[i] = 0 and
  395.                                     upper[j] >= subclasses[i] then
  396.             AddSet( initfusion[i], j );
  397.           fi;
  398.         od;
  399.       od;
  400.     fi;
  401.  
  402.     # step 2: replace sets with exactly one element by that element
  403.     errors:= [];
  404.     for i in [ 1 .. Length( initfusion ) ] do
  405.       if Length( initfusion[i] ) = 1 then
  406.         initfusion[i]:= initfusion[i][1];
  407.       elif Length( initfusion[i] ) = 0 then
  408.         AddSet( errors, i );
  409.       fi;
  410.     od;
  411.     if errors <> [] then
  412.       InfoCharTable2( "#E InitFusion: no images for classes in ",
  413.                       errors, "\n" );
  414.       return false;
  415.     fi;
  416.     return initfusion;
  417.     end;
  418.  
  419.  
  420. #############################################################################
  421. ##
  422. #F  CheckPermChar( <subtbl>, <tbl>, <fusionmap>, <permchar> )
  423. ##
  424. ##  tries to improve the parametrized fusion <fusionmap> from the character
  425. ##  table <subtbl> into the character table <tbl> using the permutation
  426. ##  character <permchar> that belongs to the required fusion\:
  427. ##
  428. ##  An upper bound for the number of elements fusing into each class is
  429. ##  $'upper[i]'=
  430. ##           '<subtbl>.order' \* '<permchar>[i]' / '<tbl>.centralizers[i]'$.
  431. ##
  432. ##  We first subtract from that the number of all elements which {\em must}
  433. ##  fuse into that class:
  434. ##  $'upper[i]':= 'upper[i]' -
  435. ##                      \sum_{'fusionmap[i]'='i'} '<subtbl>.classes[i]'$.
  436. ##
  437. ##  After that, we delete all those possible images 'j' in 'initfusion[i]'
  438. ##  which do not satisfy $'<subtbl>.classes[i]' \leq 'upper[j]'$
  439. ##  (local function 'deletetoolarge').
  440. ##
  441. ##  At last, if there is a class 'j' with
  442. ##  $'upper[j]' = \sum_{'j' \in 'initfusion[i]'}' <subtbl>.classes[i]'$,
  443. ##  then 'j' must be the image for all 'i' with 'j' in 'initfusion[i]'
  444. ##  (local function 'takealliffits').
  445. ##
  446. ##  'CheckPermChar' returns 'true' if no inconsistency occured, and 'false'
  447. ##  otherwise.
  448. ##
  449. ##  ('CheckPermChar' is used as subroutine of 'SubgroupFusions'.)
  450. ##
  451. CheckPermChar := function( subtbl, tbl, fusionmap, permchar )
  452.     local i, upper, deletetoolarge, takealliffits, totest, improved;
  453.  
  454.     upper:= [];
  455.     if permchar = [] then
  456.  
  457.       # just check upper bounds
  458.       for i in [ 1 .. Length( tbl.centralizers ) ] do
  459.         upper[i]:= Minimum( subtbl.order, tbl.classes[i] );
  460.       od;
  461.     else
  462.  
  463.       # number of elements that fuse in each class
  464.       for i in [ 1 .. Length( tbl.centralizers ) ] do
  465.         upper[i]:= permchar[i] * subtbl.order / tbl.centralizers[i];
  466.       od;
  467.     fi;
  468.  
  469.     # subtract elements where the image is unique
  470.     for i in [ 1 .. Length( fusionmap ) ] do
  471.       if IsInt( fusionmap[i] ) then
  472.         upper[ fusionmap[i] ]:= upper[ fusionmap[i] ] - subtbl.classes[i];
  473.       fi;
  474.     od;
  475.     if Minimum( upper ) < 0 then
  476.       InfoCharTable2( "#E CheckPermChar: too many preimages for classes in ",
  477.                       Filtered( [ 1 .. Length( upper ) ],
  478.                                 x-> upper[x] < 0 ), "\n" );
  479.       return false;
  480.     fi;
  481.  
  482.     # Only those classes are allowed images which are not too big
  483.     # also after diminishing upper:
  484.     # 'deletetoolarge( <totest> )' excludes all those possible images 'x' in
  485.     # sets 'fusionmap[i]' which are contained in the list <totest> and
  486.     # which are larger than 'upper[x]'.
  487.     # (returns 'i' in case of an inconsistency at class 'i', otherwise the
  488.     # list of classes 'x' where 'upper[x]' was diminished)
  489.     #
  490.     deletetoolarge:= function( totest )
  491.       local i, improved, delete;
  492.  
  493.       if totest = [] then return []; fi; 
  494.       improved:= [];
  495.       for i in [ 1 .. Length( fusionmap ) ] do
  496.         if IsSet( fusionmap[i] )
  497.            and Intersection( fusionmap[i], totest ) <> [] then
  498.           fusionmap[i]:= Filtered( fusionmap[i],
  499.                                     x -> ( subtbl.classes[i] <= upper[x] ) );
  500.           if fusionmap[i] = [] then
  501.             return i;
  502.           elif Length( fusionmap[i] ) = 1 then
  503.             fusionmap[i]:= fusionmap[i][1];
  504.             AddSet( improved, fusionmap[i] );
  505.             upper[ fusionmap[i] ]:= upper[fusionmap[i]] - subtbl.classes[i];
  506.           fi;
  507.         fi;
  508.       od;
  509.       delete:= deletetoolarge( improved );
  510.       if IsInt( delete ) then
  511.         return delete;
  512.       else
  513.         return Union( improved, delete );
  514.       fi;
  515.     end;
  516.  
  517.     # Check if there are classes into which more elements must fuse
  518.     # than known up to now; if all possible preimages are
  519.     # necessary to satisfy the permutation character, improve 'fusionmap'.
  520.     # 'takealliffits( <totest> )' sets 'fusionmap[i]' to 'x' if 'x' is in
  521.     # the list 'totest' and if all possible preimages of 'x' are necessary
  522.     # to give 'upper[x]'.
  523.     # (returns 'i' in case of an inconsistency at class 'i', otherwise the
  524.     # list of classes 'x' where 'upper[x]' was diminished)
  525.     #
  526.     takealliffits:= function( totest )
  527.       local i, j, preimages, sum, improved, take;
  528.       if totest = [] then return []; fi;
  529.       improved:= [];
  530.       for i in Filtered( totest, x -> upper[x] > 0 ) do
  531.         preimages:= [];
  532.         for j in [ 1 .. Length( fusionmap ) ] do
  533.           if IsSet( fusionmap[j] ) and i in fusionmap[j] then
  534.             Add( preimages, j );
  535.           fi;
  536.         od;
  537.         sum:= Sum( List( preimages, x -> subtbl.classes[x] ) );
  538.         if sum = upper[i] then
  539.  
  540.           # take them all
  541.           for j in preimages do fusionmap[j]:= i; od;
  542.           upper[i]:= 0;
  543.           Add( improved, i );
  544.         elif sum < upper[i] then
  545.           return i;
  546.         fi;
  547.       od;
  548.       take:= takealliffits( improved );
  549.       if IsInt( take ) then
  550.         return take;
  551.       else
  552.         return Union( improved, take );
  553.       fi;
  554.     end;
  555.  
  556.     # Improve until no new improvement can be found!
  557.     totest:= [ 1 .. Length( permchar ) ];
  558.     while totest <> [] do
  559.       improved:= deletetoolarge( totest );
  560.       if IsInt( improved ) then
  561.         InfoCharTable2( "#E CheckPermChar: no image possible for class ",
  562.                         improved, "\n" );
  563.         return false;
  564.       fi;
  565.       totest:= takealliffits( Union( improved, totest ) );
  566.       if IsInt( totest ) then
  567.         InfoCharTable2( "#E CheckPermChar: not enough preimages for class ",
  568.                         totest, "\n" );
  569.         return false;
  570.       fi;
  571.     od;
  572.     return true;
  573.     end;
  574.  
  575.  
  576. #############################################################################
  577. ##
  578. #F  ImproveMaps( <map2>, <map1>, <composition>, <class> )
  579. ##
  580. ##  utility for 'CommutativeDiagram' and 'TestConsistencyMaps';
  581. ##  <composition> must be a set that is known to be an upper bound for the
  582. ##  composition $( <map2> \circ <map1> )[ <class> ]$;
  583. ##  if $'<map1>[ <class> ]' = x$ is unique then $<map2>[ x ]$ must be a set,
  584. ##  it will be replaced by its intersection with <composition>;
  585. ##  if <map1>[ <class> ] is a set then all elements 'x' with
  586. ##  'Intersection( <map2>[ x ], <composition> ) = []' are excluded.
  587. ##
  588. ##  'ImproveMaps' returns     0 if no improvement was found
  589. ##                           -1 if <map1>[ <class> ] was improved
  590. ##                          <x> if <map2>[ <x> ] was improved
  591. ##
  592. ImproveMaps := function( map2, map1, composition, class )
  593.     local j, map1_i, newvalue;
  594.  
  595.     map1_i:= map1[ class ];
  596.     if IsInt( map1_i ) then
  597.  
  598.       # case 1: map2[ map1_i ] must be a set,
  599.       #         try to improve map2 at that position
  600.       if composition <> map2[ map1_i ] then
  601.         if Length( composition ) = 1 then
  602.           map2[ map1_i ]:= composition[1];
  603.         else
  604.           map2[ map1_i ]:= composition;
  605.         fi;
  606.  
  607.         # map2[ map1_i ] was improved
  608.         return map1_i;
  609.       fi;
  610.     else
  611.  
  612.       # case 2: try to improve map1[ class ]
  613.       newvalue:= [];
  614.       for j in map1_i do
  615.         if ( IsInt(map2[j]) and map2[j] in composition ) or
  616.            ( IsSet(map2[j]) and Intersection(map2[j],composition)<>[] ) then
  617.           AddSet( newvalue, j );
  618.         fi;
  619.       od;
  620.       if newvalue <> map1_i then
  621.         if Length( newvalue ) = 1 then
  622.           map1[ class ]:= newvalue[1];
  623.         else
  624.           map1[ class ]:= newvalue;
  625.         fi;
  626.         return -1;                  # map1 was improved
  627.       fi;
  628.     fi;
  629.     return 0;                       # no improvement
  630.     end;
  631.  
  632.  
  633. #############################################################################
  634. ##
  635. #F  CommutativeDiagram( <paramap1>, <paramap2>, <paramap3>, <paramap4> )
  636. #F  CommutativeDiagram( <paramap1>, <paramap2>, <paramap3>, <paramap4>,
  637. #F                      <improvements> )
  638. ##
  639. ##  If 'CompositionMaps( <paramap2>, <paramap1> ) =
  640. ##      CompositionMaps( <paramap4>, <paramap3> )'
  641. ##  shall hold, the consistency is checked and the four maps
  642. ##  will be improved according to this condition.
  643. ##
  644. ##  If a record <improvements> with fields 'imp1', 'imp2', 'imp3', 'imp4' is
  645. ##  specified, only diagrams containing elements of 'imp<i>' as preimages of
  646. ##  <paramapi> are considered.
  647. ##
  648. ##  'CommutativeDiagram' returns 'false' if an inconsistency was found,
  649. ##  otherwise a record is returned that contains four lists 'imp1', \ldots,
  650. ##  'imp4':
  651. ##  'imp<i>' is the list of classes where <paramap_i> was improved.
  652. ##
  653. ##    i ---------> map1[i]
  654. ##    |              |
  655. ##    |              v
  656. ##    |          map2[ map1[i] ]
  657. ##    v
  658. ##  map3[i] ---> map4[ map3[i] ]
  659. ##
  660. CommutativeDiagram := function( arg )
  661.     local i, paramap1, paramap2, paramap3, paramap4, imp1, imp2, imp4,
  662.           globalimp1, globalimp2, globalimp3, globalimp4, newimp1, newimp2,
  663.           newimp4, map2_map1, map4_map3, composition, imp;
  664.  
  665.     if not ( Length(arg) in [ 4, 5 ] and IsList(arg[1]) and IsList(arg[2])
  666.              and IsList( arg[3] ) and IsList( arg[4] ) )
  667.        or ( Length( arg ) = 5 and not IsRec( arg[5] ) ) then
  668.       Error("usage: CommutativeDiagram(<pmap1>,<pmap2>,<pmap3>,<pmap4>)\n",
  669.           "resp. CommutativeDiagram(<pmap1>,<pmap2>,<pmap3>,<pmap4>,<imp>)");
  670.     fi;
  671.     paramap1:= arg[1];
  672.     paramap2:= arg[2];
  673.     paramap3:= arg[3];
  674.     paramap4:= arg[4];
  675.     if Length( arg ) = 5 then
  676.       imp1:= Union( arg[5].imp1, arg[5].imp3 );
  677.       imp2:= arg[5].imp2;
  678.       imp4:= arg[5].imp4;
  679.     else
  680.       imp1:= List( [ 1 .. Length( paramap1 ) ] );
  681.       imp2:= [];
  682.       imp4:= [];
  683.     fi;
  684.     globalimp1:= [];
  685.     globalimp2:= [];
  686.     globalimp3:= [];
  687.     globalimp4:= [];
  688.     while imp1 <> [] or imp2 <> [] or imp4 <> [] do
  689.       newimp1:= [];
  690.       newimp2:= [];
  691.       newimp4:= [];
  692.       for i in [ 1 .. Length( paramap1 ) ] do
  693.         if i in imp1
  694.            or ( IsSet(paramap1[i]) and Intersection(paramap1[i],imp2)<>[] )
  695.            or ( IsSet(paramap3[i]) and Intersection(paramap3[i],imp4)<>[] )
  696.            or ( IsInt( paramap1[i] ) and paramap1[i] in imp2 )
  697.            or ( IsInt( paramap3[i] ) and paramap3[i] in imp4 ) then
  698.           map2_map1:= CompositionMaps( paramap2, paramap1, i );
  699.           map4_map3:= CompositionMaps( paramap4, paramap3, i );
  700.           if IsInt( map2_map1 ) then map2_map1:= [ map2_map1 ]; fi;
  701.           if IsInt( map4_map3 ) then map4_map3:= [ map4_map3 ]; fi;
  702.           composition:= Intersection( map2_map1, map4_map3 );
  703.           if composition = [] then
  704.             InfoCharTable2( "#E CommutativeDiagram: inconsistency at class",
  705.                             i, "\n" );
  706.             return false;
  707.           fi;
  708.           if composition <> map2_map1 then
  709.             imp:= ImproveMaps( paramap2, paramap1, composition, i );
  710.             if imp = -1 then
  711.               AddSet( newimp1, i );
  712.               AddSet( globalimp1, i );
  713.             elif imp <> 0 then
  714.               AddSet( newimp2, imp );
  715.               AddSet( globalimp2, imp );
  716.             fi;
  717.           fi;
  718.           if composition <> map4_map3 then
  719.             imp:= ImproveMaps( paramap4, paramap3, composition, i );
  720.             if imp = -1 then
  721.               AddSet( newimp1, i );
  722.               AddSet( globalimp3, i );
  723.             elif imp <> 0 then
  724.               AddSet( newimp4, imp );
  725.               AddSet( globalimp4, imp );
  726.             fi;
  727.           fi;
  728.         fi;
  729.       od;
  730.       imp1:= newimp1;
  731.       imp2:= newimp2;
  732.       imp4:= newimp4;
  733.     od;
  734.     return rec( imp1:= globalimp1, imp2:= globalimp2,
  735.                 imp3:= globalimp3, imp4:= globalimp4 );
  736.     end;
  737.  
  738.  
  739. #############################################################################
  740. ##
  741. #F  CheckFixedPoints( <inside1>, <between>, <inside2> )
  742. ##
  743. ##  try to improve <between> using that <between> must map fixed points under
  744. ##  <inside1> to fixed points under <inside2> 
  745. ##
  746. ##  If an inconsistency occurs, return the list of classes where improvements
  747. ##  were found; otherwise return 'false'.
  748. ##
  749. CheckFixedPoints := function( inside1, between, inside2 )
  750.     local i, j, improvements, errors, image;
  751.  
  752.     improvements:= [];
  753.     errors:= [];
  754.     for i in [ 1 .. Length( inside1 ) ] do
  755.       if inside1[i] = i then             # for all fixed points of 'inside1'
  756.         if IsInt( between[i] ) then
  757.           if inside2[ between[i] ] <> between[i] then
  758.             if IsInt( inside2[ between[i] ] )
  759.                or not between[i] in inside2[ between[i] ] then
  760.               Add( errors, i );
  761.             else
  762.               inside2[ between[i] ]:= between[i];
  763.               Add( improvements, i );
  764.             fi;
  765.           fi;
  766.         else
  767.           image:= [];
  768.           for j in between[i] do
  769.             if inside2[j] = j
  770.                or ( IsSet( inside2[j] ) and j in inside2[j] ) then
  771.               Add( image, j );
  772.             fi;
  773.           od;
  774.           if image = [] then
  775.             AddSet( errors, i );
  776.           elif image <> between[i] then
  777.             between[i]:= image;
  778.             AddSet( improvements, i );
  779.           fi;
  780.         fi;
  781.       fi;
  782.     od;
  783.     if errors = [] then
  784.       if improvements <> [] then
  785.         InfoCharTable2( "#I CheckFixedPoints: improvements at classes ",
  786.                         improvements, "\n" );
  787.       fi;
  788.       return improvements;
  789.     else
  790.       InfoCharTable2( "#E CheckFixedPoints: no image possible for classes ",
  791.                       errors, "\n" );
  792.       return false;
  793.     fi;
  794.     end;
  795.    
  796.  
  797. #############################################################################
  798. ##
  799. #F  TransferDiagram( <inside1>, <between>, <inside2> )
  800. #F  TransferDiagram( <inside1>, <between>, <inside2>, <improvements> )
  801. ##
  802. ##  Like in 'CommutativeDiagram', it is checked that
  803. ##  'CompositionMaps( <between>, <inside1> ) =
  804. ##  CompositionMaps( <inside2>, <between> )', that means
  805. ##  <between> occurs twice in each commutative diagram
  806. ##
  807. ##     i   -----> between[i]
  808. ##     |            |
  809. ##     |            v
  810. ##     |         inside2[ between[i] ]
  811. ##     v
  812. ##  inside1[i] ----> between[ inside1[i] ]
  813. ##
  814. ##  If a record <improvements> with fields 'impinside1', 'impbetween' and
  815. ##  'impinside2' is specified, only those diagrams with elements of
  816. ##  'impinside1' as preimages of <inside1>, elements of 'impbetween' as
  817. ##  preimages of <between> or elements of 'impinside2' as preimages of
  818. ##  <inside2> are considered.
  819. ##
  820. ##  When an inconsistency occurs, the program immediately returns 'false';
  821. ##  else it returns a record with lists 'impinside1', 'impbetween' and
  822. ##  'impinside2' of found improvements.
  823. ##
  824. ##  (calls 'CheckFixedPoints')
  825. ##
  826. TransferDiagram := function( arg )
  827.     local i, inside1, between, inside2, imp1, impb, imp2, globalimp1,
  828.           globalimpb, globalimp2, newimp1, newimpb, newimp2, bet_ins1,
  829.           ins2_bet, composition, imp, check;
  830.  
  831.     if not ( Length(arg) in [ 3, 4 ] and IsList(arg[1]) and IsList(arg[2])
  832.              and IsList( arg[3] ) )
  833.        or ( Length( arg ) = 4 and not IsRec( arg[4] ) ) then
  834.       Error("usage: TransferDiagram(<inside1>,<between>,<inside2>) resp.\n",
  835.             "       TransferDiagram(<inside1>,<between>,<inside2>,<imp> )" );
  836.     fi;
  837.     inside1:= arg[1];
  838.     between:= arg[2];
  839.     inside2:= arg[3];
  840.     if Length( arg ) = 4 then
  841.       imp1:= arg[4].impinside1;
  842.       impb:= arg[4].impbetween;
  843.       imp2:= arg[4].impinside2;
  844.     else
  845.       imp1:= List( [ 1 .. Length( inside1 ) ] );
  846.       impb:= [];
  847.       imp2:= [];
  848.     fi;
  849.     globalimp1:= [];
  850.     globalimpb:= [];
  851.     globalimp2:= [];
  852.     while imp1 <> [] or impb <> [] or imp2 <> [] do
  853.       newimp1:= [];
  854.       newimpb:= [];
  855.       newimp2:= [];
  856.       for i in [ 1 .. Length( inside1 ) ] do
  857.         if i in imp1 or i in impb
  858.            or ( IsSet( inside1[i] ) and Intersection(inside1[i],impb)<>[] )
  859.            or ( IsSet( between[i] ) and Intersection(between[i],imp2)<>[] )
  860.            or ( IsInt( inside1[i] ) and inside1[i] in impb )
  861.            or ( IsInt( between[i] ) and between[i] in imp2 ) then
  862.           bet_ins1:= CompositionMaps( between, inside1, i );
  863.           ins2_bet:= CompositionMaps( inside2, between, i );
  864.           if IsInt( bet_ins1 ) then bet_ins1:= [ bet_ins1 ]; fi;
  865.           if IsInt( ins2_bet ) then ins2_bet:= [ ins2_bet ]; fi;
  866.           composition:= Intersection( bet_ins1, ins2_bet );
  867.           if composition = [] then
  868.             InfoCharTable2( "#I TransferDiagram: inconsistency at class ",
  869.                             i, "\n" );
  870.             return false;
  871.           fi;
  872.           if composition <> bet_ins1 then
  873.             imp:= ImproveMaps( between, inside1, composition, i );
  874.             if imp = -1 then
  875.               AddSet( newimp1, i );
  876.               AddSet( globalimp1, i );
  877.             elif imp <> 0 then
  878.               AddSet( newimpb, imp );
  879.               AddSet( globalimpb, imp );
  880.             fi;
  881.           fi;
  882.           if composition <> ins2_bet then
  883.             imp:= ImproveMaps( inside2, between, composition, i );
  884.             if imp = -1 then
  885.               AddSet( newimpb, i );
  886.               AddSet( globalimpb, i );
  887.             elif imp <> 0 then
  888.               AddSet( newimp2, imp );
  889.               AddSet( globalimp2, imp );
  890.             fi;
  891.           fi;
  892.         fi;
  893.       od;
  894.       imp1:= newimp1;
  895.       impb:= newimpb;
  896.       imp2:= newimp2;
  897.     od;
  898.     check:= CheckFixedPoints( inside1, between, inside2 );
  899.     if check = false then
  900.       return false;
  901.     elif check <> [] then
  902.       check:= TransferDiagram( inside1, between, inside2,
  903.                                rec( impinside1:= [], impbetween:= check,
  904.                                     impinside2:= [] ) );
  905.       return rec( impinside1:= Union( check.impinside1, globalimp1 ),
  906.                   impbetween:= Union( check.impbetween, globalimpb ),
  907.                   impinside2:= Union( check.impinside2, globalimp2 ) );
  908.     else
  909.       return rec( impinside1:= globalimp1, impbetween:= globalimpb,
  910.                   impinside2:= globalimp2 );
  911.     fi;
  912.     end;
  913.  
  914.  
  915. #############################################################################
  916. ##
  917. #F  TestConsistencyMaps( <powermap1>, <fusionmap>, <powermap2> )
  918. #F  TestConsistencyMaps( <powermap1>, <fusionmap>, <powermap2>, <fus_imp> )
  919. ##
  920. ##  Like in 'TransferDiagram', it is checked that maps are commutative:
  921. ##  For all positions 'i' where both '<powermap1>[i]' and '<powermap2>[i]'
  922. ##  are bound, it must hold 'CompositionMaps( <fusionmap>, <powermap1>[i] ) =
  923. ##  CompositionMaps( <powermap2>[i], <fusionmap> )', that means
  924. ##  1. <fusionmap> occurs twice in each commutative diagram and
  925. ##  2. <fusionmap> is common for all considered elements of <powermap1> resp.
  926. ##     <powermap2>.
  927. ##
  928. ##  If a list <fus_imp> is specified, only those diagrams with
  929. ##  elements of <fus_imp> as preimaes of <fusionmap> are considered.
  930. ##
  931. ##  When an inconsistency occurs, the program immediately returns 'false';
  932. ##  otherwise 'true' is returned.
  933. ##
  934. TestConsistencyMaps := function( arg )
  935.     local i, j, x, powermap1, powermap2, pos, fusionmap, imp,
  936.           fus_improvements, tr;
  937.  
  938.     if not ( Length(arg) in [ 3, 4 ] and IsList(arg[1]) and IsList(arg[2])
  939.              and IsList( arg[3] ) )
  940.        or ( Length( arg ) = 4 and not IsList( arg[4] ) ) then
  941.       Error("usage: TestConsistencyMaps(<powmap1>,<fusmap>,<powmap2>)",
  942.             " resp.\n    ",
  943.             "TestConsistencyMaps(<powmap1>,<fusmap>,<powmap2>,<fus_imp>)");
  944.     fi;
  945.     powermap1:= [];
  946.     powermap2:= [];
  947.     pos:= [];
  948.     for i in [ 1 .. Length( arg[1] ) ] do
  949.       if IsBound( arg[1][i] ) and IsBound( arg[3][i] ) then
  950.         Add( powermap1, arg[1][i] );
  951.         Add( powermap2, arg[3][i] );
  952.         Add( pos, i );
  953.       fi;
  954.     od;
  955.     fusionmap:= arg[2];
  956.     if Length( arg ) = 4 then
  957.       imp:= arg[4];
  958.     else
  959.       imp:= [ 1 .. Length( fusionmap ) ];
  960.     fi;
  961.     fus_improvements:= List( [ 1 .. Length( powermap1 ) ], x -> imp );
  962.     if fus_improvements = [] then return true; fi;     # no common powermaps
  963.     i:= 1;
  964.     while fus_improvements[i] <> [] do
  965.       tr:= TransferDiagram( powermap1[i], fusionmap, powermap2[i],
  966.                      rec( impinside1:= [],
  967.                           impbetween:= fus_improvements[i],
  968.                           impinside2:= [] ) );
  969.       # (We are only interested in improvements of the fusionmap which may
  970.       #  have occurred.)
  971.  
  972.       if tr = false then
  973.         InfoCharTable2( "#I TestConsistencyMaps: inconsistency in powermap ",
  974.                         pos[i], "\n" );
  975.         return false;
  976.       fi;
  977.       for j in [ 1 .. Length( fus_improvements ) ] do
  978.         fus_improvements[j]:= Union( fus_improvements[j], tr.impbetween );
  979.       od;
  980.       fus_improvements[i]:= [];
  981.       i:= ( i mod Length( fus_improvements ) ) + 1;
  982.     od;
  983.     return true;
  984.     end;
  985.  
  986.  
  987. #############################################################################
  988. ##
  989. #F  InitPowermap( <tbl>, <prime> )
  990. ##
  991. ##  returns a (parametrized) map that is a first approximation of the <prime>-th
  992. ##  powermap of <tbl>. The following properties are used:
  993. ##
  994. ##  1. For each class 'i', the centralizer order of the <prime>-th power must
  995. ##     be a multiple of the centralizer order of 'i'; if the representative
  996. ##     order of 'i' is relative prime to <prime>, the centralizer orders of
  997. ##     i and its image must be equal.
  998. ##
  999. ##  2. If <prime> divides the representative order <x> of the class 'i', the
  1000. ##     representative order of its image must be $<x> / <prime>$; otherwise
  1001. ##     the representative orders of 'i' and its image must be equal.
  1002. ##
  1003. ##  If there are classes for which no images are possible, 'false' is returned.
  1004. ##
  1005. InitPowermap := function( tbl, prime )
  1006.     local i, j, k, nccl, powermap, orders, centralizers, sameord, suborder;
  1007.  
  1008.     powermap:= [];
  1009.     centralizers:= tbl.centralizers;
  1010.     nccl:= Length( centralizers );
  1011.     if IsBound( tbl.orders ) and IsList( tbl.orders ) then
  1012.     
  1013.       # both orders and centralizers are known:
  1014.       orders:= tbl.orders;
  1015.       sameord:= [];
  1016.       for i in [ 1 .. Length( orders ) ] do
  1017.         if IsInt( orders[i] ) then
  1018.           if IsBound( sameord[ orders[i] ] ) then
  1019.             AddSet( sameord[ orders[i] ], i );
  1020.           else
  1021.             sameord[ orders[i] ]:= [ i ];
  1022.           fi;
  1023.         else                               # parametrized orders
  1024.           for j in [ 1 .. Length( orders[i] ) ] do
  1025.             if IsBound( sameord[ orders[i][j] ] ) then
  1026.               AddSet( sameord[ orders[i][j] ], i );
  1027.             else
  1028.               sameord[ orders[i][j] ]:= [ i ];
  1029.             fi;
  1030.           od;
  1031.         fi;
  1032.       od;
  1033.       for i in [ 1 .. nccl ] do
  1034.         powermap[i]:= [];
  1035.         if IsInt( orders[i] ) then
  1036.           if orders[i] mod prime = 0 then
  1037.             for j in sameord[ orders[i] / prime ] do
  1038.               if centralizers[j] mod centralizers[i] = 0 then
  1039.                 AddSet( powermap[i], j );
  1040.               fi;
  1041.             od;
  1042.           else
  1043.             for j in sameord[ orders[i] ] do
  1044.               if centralizers[j] = centralizers[i] then
  1045.                 AddSet( powermap[i], j );
  1046.               fi;
  1047.             od;
  1048.           fi;  
  1049.         else
  1050.           for j in orders[i] do
  1051.             if j mod prime = 0 then
  1052.               for k in sameord[ j / prime ] do
  1053.                 if centralizers[k] mod centralizers[i] = 0 then
  1054.                   AddSet( powermap[i], k );
  1055.                 fi;
  1056.               od;
  1057.             else
  1058.               for k in sameord[j] do
  1059.                 if centralizers[k] = centralizers[i] then
  1060.                   AddSet( powermap[i], k );
  1061.                 fi;
  1062.               od;
  1063.             fi;  
  1064.           od;
  1065.           if Gcd( orders[i] ) mod prime = 0 then
  1066.             powermap[i]:= Difference( powermap[i], [ i ] );
  1067.           fi;
  1068.         fi;
  1069.       od;
  1070.     else                          # just centralizers are known
  1071.       for i in [ 1 .. nccl ] do
  1072.         powermap[i]:= [];
  1073.         for j in [ 1 .. nccl ] do
  1074.           if centralizers[j] mod centralizers[i] = 0 then
  1075.             AddSet( powermap[i], j );
  1076.           fi;
  1077.         od;
  1078.       od;
  1079.     fi;
  1080.     for i in [ 1 .. nccl ] do
  1081.       if powermap[i] = [] then
  1082.         InfoCharTable2( "#E InitPowermap: no image possible for classes\n",
  1083.                         "#E ", Filtered( [ 1..nccl ], x -> powermap[x]=[] ),
  1084.                         "\n" );
  1085.         return false;
  1086.       elif Length( powermap[i] ) = 1 then
  1087.         powermap[i]:= powermap[i][1];
  1088.       fi;
  1089.     od;
  1090.     if ( IsInt( powermap[1] ) and powermap[1] <> 1 ) or
  1091.        ( IsList( powermap[1] ) and not 1 in powermap[1] ) then
  1092.       Print( "#E InitPowermap: class 1 cannot contain the identity\n" );
  1093.       return false;
  1094.     fi;
  1095.     powermap[1]:= 1;
  1096.     return powermap;
  1097.     end;
  1098.  
  1099.  
  1100. #############################################################################
  1101. ##
  1102. #F  Congruences( <tbl>, <chars>, <prime_powermap>, <prime> )
  1103. #F  Congruences( <tbl>, <chars>, <prime_powermap>, <prime>, \"quick\" )
  1104. ##
  1105. ##  improves <prime_powermap> which is an approximation for the <prime>-th
  1106. ##  powermap of <tbl> using the property that for each element <chi> of
  1107. ##  <chars> the congruence
  1108. ##  $'Gal'( <chi>(g), <prime> ) \equiv <chi>(g^{<prime>}) \pmod{<prime>}$ holds;
  1109. ##  if the representative order of $g$ is relative prime to <prime> we have
  1110. ##  $'GaloisCyc( <chi>(g), <prime> ) = <chi>(g^{<prime>})$.
  1111. ##  
  1112. ##  If \"quick\" is specified, only those classes with ambiguous images are
  1113. ##  considered.
  1114. ##
  1115. ##  If there are classes for which no images are possible, the value is the
  1116. ##  empty list (not undefined!)
  1117. ##
  1118. Congruences := function( arg )
  1119.     local i, j, x, tbl, chars, prime_powermap, prime, nccl, omega,
  1120.           images, newimage, cand_image, ok, char, errors;
  1121.  
  1122.     if not ( Length( arg ) in [ 4, 5 ] and IsCharTable( arg[1] )
  1123.              and IsList(arg[2]) and IsList(arg[3]) and IsPrimeInt(arg[4]) )
  1124.        or ( Length( arg ) = 5 and arg[5] <> "quick" ) then
  1125.       Error("usage: Congruences(tbl,chars,prime_powermap,prime,\"quick\")\n",
  1126.             " resp. Congruences(tbl,chars,prime_powermap,prime)" );
  1127.     fi;
  1128.  
  1129.     tbl:= arg[1];
  1130.     chars:= arg[2];
  1131.     prime_powermap:= arg[3];
  1132.     prime:= arg[4];
  1133.     nccl:= Length( prime_powermap );
  1134.     omega:= Set( [ 1 .. nccl ] );
  1135.     if Length( arg ) = 5 then     # "quick": only consider ambiguous classes
  1136.       for i in [ 1 .. nccl ] do
  1137.         if IsInt( prime_powermap[i] ) or Length( prime_powermap[i] ) <= 1 then
  1138.           omega:= Difference( omega, [ i ] );
  1139.         fi;
  1140.       od;
  1141.     fi;
  1142.     for i in omega do
  1143.       if IsInt( prime_powermap[i] ) then
  1144.         images:= [ prime_powermap[i] ];
  1145.       else
  1146.         images:= prime_powermap[i];
  1147.       fi;
  1148.       newimage:= [];
  1149.       for cand_image in images do
  1150.         j:= 1;
  1151.         ok:= true;
  1152.         while j <= Length( chars ) and ok do   # loop over characters
  1153.           char:= chars[j];
  1154.           if not IsUnknown( char[ cand_image ] ) then
  1155.             if IsInt( char[i] ) then
  1156.               if not IsCycInt( ( char[ cand_image ] - char[i] ) / prime ) then
  1157.                 ok:= false;
  1158.               fi;
  1159.             elif IsCyc( char[i] ) then
  1160.               if IsBound( tbl.orders ) and IsList( tbl.orders ) and
  1161.                  ( ( IsInt( tbl.orders[i] ) and tbl.orders[i] mod prime <> 0 ) 
  1162.                    or ( IsList( tbl.orders[i] )
  1163.                            and ForAll( tbl.orders[i],
  1164.                                        x -> x mod prime <> 0 ) ) ) then
  1165.                 if char[ cand_image ] <> GaloisCyc( char[i], prime ) then
  1166.                   ok:= false;
  1167.                 fi;
  1168.               elif not IsCycInt( ( char[ cand_image ]
  1169.                                  - GaloisCyc(char[i],prime) ) / prime ) then
  1170.                 ok:= false;
  1171.               fi;
  1172.             fi;
  1173.           fi;
  1174.           j:= j+1;
  1175.         od;
  1176.         if ok then AddSet( newimage, cand_image ); fi;
  1177.       od;
  1178.       prime_powermap[i]:= newimage;
  1179.     od;
  1180.     errors:= [];    # list of classes for which no image is left
  1181.     for i in omega do
  1182.       if Length( prime_powermap[i] ) = 0 then
  1183.         Add( errors, i );
  1184.       elif Length( prime_powermap[i] ) = 1 then
  1185.         prime_powermap[i]:= prime_powermap[i][1];
  1186.       fi;
  1187.     od;
  1188.     if errors <> [] then
  1189.       Print( "#E Congruences(.,.,.,", prime,
  1190.              "): no image possible for classes ", errors, "\n" );
  1191.       return false;
  1192.     fi;
  1193.     return true;
  1194.     end;
  1195.  
  1196.  
  1197. #############################################################################
  1198. ##
  1199. #F  ConsiderKernels( <tbl>, <chars>, <prime_powermap>, <prime> )
  1200. #F  ConsiderKernels( <tbl>, <chars>, <prime_powermap>, <prime>, \"quick\" )
  1201. ##
  1202. ##  improves <prime_powermap> which is an approximation of the <prime>-th
  1203. ##  powermap of <tbl> using the property that for each element <chi> of
  1204. ##  <chars> the kernel of <chi> is a normal subgroup of <tbl>.
  1205. ##  So for every $g \in 'KernelChar( <chi> )'$ we have
  1206. ##  $g^{<prime>} \in 'KernelChar( <chi> )'$;
  1207. ##
  1208. ##  Depending on the order of the factor group modulo 'KernelChar( <chi> )',
  1209. ##  there are two further properties:
  1210. ##  If the order is relative prime to <prime>, for each
  1211. ##  $g \notin 'KernelChar( <chi> )'$ the <prime>-th power is not contained in
  1212. ##  'KernelChar( <chi> )'.
  1213. ##  If the order is equal to <prime>, the <prime>-th powers of all elements
  1214. ##  lie in 'KernelChar( <chi> )'.
  1215. ##
  1216. ##  If 'KernelChar( <chi> )' has an order not dividing the order of <tbl>,
  1217. ##  'false' is returned.
  1218. ##
  1219. ##  Also if no image is left for any class, 'false' is returned.
  1220. ##
  1221. ##  If '\"quick\"' is specified, only those classes are considered where
  1222. ##  <prime_powermap> is ambiguous.
  1223. ##
  1224. ConsiderKernels := function( arg )
  1225.     local i, tbl, chars, prime_powermap, prime, nccl, omega, kernels,
  1226.           chi, kernel, suborder;
  1227.  
  1228.     if not ( Length( arg ) in [ 4, 5 ] and IsCharTable( arg[1] ) and
  1229.              IsList( arg[2] ) and IsList( arg[3] ) and IsPrimeInt( arg[4] ) )
  1230.        or ( Length( arg ) = 5 and arg[5] <> "quick" ) then
  1231.       Error("usage: ConsiderKernels( tbl, chars, prime_powermap, prime )\n",
  1232.            "resp. ConsiderKernels(tbl,chars,prime_powermap,prime,\"quick\")");
  1233.     fi;
  1234.  
  1235.     tbl:= arg[1];
  1236.     chars:= arg[2];
  1237.     prime_powermap:= arg[3];
  1238.     prime:= arg[4];
  1239.     nccl:= Length( prime_powermap );
  1240.     omega:= Set( [ 1 .. nccl ] );
  1241.     kernels:= [];
  1242.     for chi in chars do AddSet( kernels, KernelChar( chi ) ); od;
  1243.     kernels:= Difference( kernels, Set( [ omega, [ 1 ] ] ) );
  1244.     if Length( arg ) = 5  then     # "quick": only consider ambiguous classes
  1245.       omega:= [];
  1246.       for i in [ 1 .. nccl ] do
  1247.         if IsSet(prime_powermap[i]) and Length( prime_powermap[i] ) > 1 then
  1248.           AddSet( omega, i );
  1249.         fi;
  1250.       od;
  1251.     fi;
  1252.     for kernel in kernels do
  1253.       suborder:= 0;
  1254.       for i in kernel do suborder:= suborder + tbl.classes[i]; od;
  1255.       if tbl.order mod suborder <> 0 then
  1256.         InfoCharTable2( "#E ConsiderKernels: kernel of character is not a",
  1257.                         " subgroup\n" );
  1258.         return false;
  1259.       fi;
  1260.       for i in Intersection( omega, kernel ) do
  1261.         if IsList( prime_powermap[i] ) then
  1262.           prime_powermap[i]:= Intersection( prime_powermap[i], kernel );
  1263.         else
  1264.           prime_powermap[i]:= Intersection( [ prime_powermap[i] ], kernel );
  1265.         fi;
  1266.         if Length( prime_powermap[i] ) = 1 then
  1267.           prime_powermap[i]:= prime_powermap[i][1];
  1268.         fi;
  1269.       od;
  1270.       if ( tbl.order / suborder ) mod prime <> 0 then
  1271.         for i in Difference( omega, kernel ) do
  1272.           if IsList( prime_powermap[i] ) then
  1273.             prime_powermap[i]:= Difference( prime_powermap[i], kernel );
  1274.           else
  1275.             prime_powermap[i]:= Difference( [ prime_powermap[i] ], kernel );
  1276.           fi;
  1277.           if Length( prime_powermap[i] ) = 1 then
  1278.             prime_powermap[i]:= prime_powermap[i][1];
  1279.           fi;
  1280.         od;
  1281.       elif ( tbl.order / suborder ) = prime then
  1282.         for i in Difference( omega, kernel ) do
  1283.           if IsList( prime_powermap[i] ) then
  1284.             prime_powermap[i]:= Intersection( prime_powermap[i], kernel );
  1285.           else
  1286.             prime_powermap[i]:= Intersection( [ prime_powermap[i] ], kernel );
  1287.           fi;
  1288.           if Length( prime_powermap[i] ) = 1 then
  1289.             prime_powermap[i]:= prime_powermap[i][1];
  1290.           fi;
  1291.         od;
  1292.       fi;
  1293.     od;
  1294.     if ForAny( prime_powermap, x -> x = [] ) then
  1295.       InfoCharTable2( "#I ConsiderKernels: no images left for classes ", 
  1296.                       Filtered( [ 1 .. Length( prime_powermap ) ],
  1297.                                 x -> prime_powermap[x] = [] ), "\n" );
  1298.       return false;
  1299.     fi;
  1300.     return true;
  1301.     end;
  1302.  
  1303.  
  1304. #############################################################################
  1305. ##
  1306. #F  ConsiderSmallerPowermaps( <tbl>, <prime_powermap>, <prime> )
  1307. #F  ConsiderSmallerPowermaps( <tbl>, <prime_powermap>, <prime>, \"quick\" )
  1308. ##
  1309. ## If $<prime> > 'orders[i]'$, try to improve the <prime>-th powermap at class
  1310. ## 'i' using that $g_i^{'prime'} = g_i^{'prime mod orders[i]'}$; so try to
  1311. ## calculate the '( prime mod orders[i] )'-th powermap at class 'i'.
  1312. ##
  1313. ##  If no 'orders' are stored on <tbl>, 'true' is returned without any tests.
  1314. ##
  1315. ##  If \"quick\" is specified only check those classes where <prime_powermap>
  1316. ##  is not unique.
  1317. ##
  1318. ##  returns 'false' if there are classes for which no image is possible,
  1319. ##  otherwise 'true'.
  1320. ##
  1321. ConsiderSmallerPowermaps := function( arg )
  1322.     local i, j, tbl, prime_powermap, prime, nccl, omega, factors, image,
  1323.           old, errors;
  1324.  
  1325.     if not ( Length( arg ) in [ 3, 4 ] and IsCharTable( arg[1] )
  1326.              and IsList( arg[2] ) and IsPrimeInt( arg[3] ) )
  1327.        or ( Length( arg ) = 4 and arg[4] <> "quick" ) then
  1328.       Error( "usage: ",
  1329.         "ConsiderSmallerPowermaps(<tbl>,<prime_powermap>,<prime>) resp.\n",
  1330.         "ConsiderSmallerPowermaps(<tbl>,<prime_powermap>,<prime>,\"quick\")");
  1331.     fi;
  1332.  
  1333.     tbl:= arg[1];
  1334.     if not IsBound( tbl.orders ) then
  1335.       InfoCharTable2( "#I ConsiderSmallerPowermaps: no orders bound,",
  1336.                       " no test\n" );
  1337.       return true;
  1338.     fi;
  1339.     prime_powermap:= arg[2];
  1340.     prime:= arg[3];
  1341.     nccl:= Length( prime_powermap );
  1342.     omega:= [];
  1343.     if Length( arg ) = 4 then
  1344.       for i in [ 1 .. nccl ] do
  1345.         if IsSet( prime_powermap[i] ) and prime > tbl.orders[i] then
  1346.           Add( omega, i );
  1347.         fi;
  1348.       od;
  1349.     else
  1350.       for i in [ 1 .. nccl ] do
  1351.         if prime > tbl.orders[i] then Add( omega, i ); fi;
  1352.       od;
  1353.     fi;
  1354.     errors:= [];
  1355.     for i in omega do
  1356.       factors:= FactorsInt( prime mod tbl.orders[i] );
  1357.       if factors = [ 1 ] or factors = [ 0 ] then factors:= []; fi;
  1358.       if ForAll( Set( factors ), x -> IsBound( tbl.powermap[x] ) ) then
  1359.         image:= [ i ];
  1360.         for j in factors do
  1361.           image:= [ CompositionMaps( tbl.powermap[j], image, 1 ) ];
  1362.         od;
  1363.         image:= image[1];
  1364.         if IsInt( prime_powermap[i] ) then
  1365.           old:= [ prime_powermap[i] ];
  1366.         else
  1367.           old:= prime_powermap[i];
  1368.         fi;
  1369.         if IsInt( image ) then
  1370.           if image in old then 
  1371.             prime_powermap[i]:= image;
  1372.           else
  1373.             Add( errors, i );
  1374.             prime_powermap[i]:= [];
  1375.           fi;
  1376.         else
  1377.           image:= Intersection( image, old );
  1378.           if image = [] then
  1379.             Add( errors, i );
  1380.             prime_powermap[i]:= [];
  1381.           elif old <> image then
  1382.             if Length( image ) = 1 then image:= image[1]; fi;
  1383.             prime_powermap[i]:= image;
  1384.           fi;
  1385.         fi;
  1386.       fi;
  1387.     od;
  1388.     if errors <> [] then
  1389.       InfoCharTable2( "#E ConsiderSmallerPowermaps: no image possible",
  1390.                       " for classes ", errors, "\n" );
  1391.       return false;
  1392.     fi;
  1393.     return true;
  1394.     end;
  1395.  
  1396.  
  1397. #############################################################################
  1398. ##
  1399. #F  PowermapsAllowedBySymmetrisations( <tbl>, <subchars>, <chars>, <pow>,
  1400. #F                                     <prime>, <parameters> )
  1401. ##
  1402. ##  <parameters> must be a record with fields <maxlen> (int), <contained>,
  1403. ##  <minamb>, <maxamb> and <quick> (boolean).
  1404. ##
  1405. ##  First, for all $\chi \in <chars>$ let
  1406. ##  'minus:= MinusCharacter( $\chi$, <pow>, <prime> )'. If
  1407. ##  '<minamb> \< Indeterminateness( minus ) \< <maxamb>', construct
  1408. ##  'poss:= contained( <tbl>, <subchars>, minus )'.
  1409. ##  (<contained> is a function that will be 'ContainedCharacters' or
  1410. ##  'ContainedPossibleCharacters'.)
  1411. ##  If 'Indeterminateness( minus ) \< <minamb>', delete this character;
  1412. ##  for unique minus-characters, if '<parameters>.quick = false', the
  1413. ##  scalar products with <subchars> are checked.
  1414. ##  (especially if the minus-character is unique, i.e.\ it is not quecked if
  1415. ##  the symmetrizations of such a character decompose correctly).
  1416. ##  Improve <pow> if possible.
  1417. ##
  1418. ##  If the minus character af a character *becomes* unique during the
  1419. ##  processing, its scalar products with <subchars> are checked.
  1420. ##
  1421. ##  If no further improvement is possible, delete all characters with unique
  1422. ##  minus-character, and branch:
  1423. ##  If there is a character left with less or equal <maxlen> possible minus-
  1424. ##  characters, compute the union of powermaps allowed by these characters;
  1425. ##  otherwise choose a class 'c' which is significant for some
  1426. ##  character, and compute the union of all allowed powermaps with image 'x' on
  1427. ##  'c', where 'x' runs over '<pow>[c]'.
  1428. ##
  1429. ##  By recursion, one gets the list of powermaps which are parametrized on all
  1430. ##  classes where no element of <chars> is significant, and which yield
  1431. ##  nonnegative integer scalar products for the minus-characters of <chars>
  1432. ##  with <subchars>.
  1433. ##
  1434. ##  If '<parameters>.quick = true', unique minus characters are never
  1435. ##  considered.
  1436. ##
  1437. PowermapsAllowedBySymmetrisations :=
  1438.               function( tbl, subchars, chars, pow, prime, parameters )
  1439.  
  1440.     local i, j, x, indeterminateness, numbofposs, lastimproved, minus, indet,
  1441.           poss, param, remain, possibilities, improvemap, allowedmaps, rat,
  1442.           powerchars, maxlen, contained, minamb, maxamb, quick;
  1443.     if chars = [] then return [ pow ]; fi;
  1444.     chars:= Set( chars );
  1445.     
  1446.     # but maybe there are characters with equal restrictions ...
  1447.     
  1448.     # record 'parameters'\:
  1449.     if not IsRec( parameters ) then
  1450.       Error( "<parameters> must be a record with fields 'maxlen',\n",
  1451.              "'contained', 'minamb', 'maxamb' and 'quick'" );
  1452.     fi;
  1453.  
  1454.     maxlen:= parameters.maxlen;
  1455.     contained:= parameters.contained;
  1456.     minamb:= parameters.minamb;
  1457.     maxamb:= parameters.maxamb;
  1458.     quick:= parameters.quick;
  1459.     
  1460.     if quick and Indeterminateness( pow ) < minamb then # immediately return
  1461.       InfoCharTable2( "#I PowermapsAllowedBySymmetrisations: ",
  1462.                       " indeterminateness of the map\n",
  1463.                       "#I    is smaller than the parameter value",
  1464.                       " 'minamb'; returned\n" );
  1465.       return [ pow ];
  1466.     fi;
  1467.     
  1468.     # step 1: check all in <chars>; if one has too big indeterminateness
  1469.     #         and contains irrational entries, append its rationalized
  1470.     #         character to <chars>.
  1471.     indeterminateness:= []; # at pos. i the indeterminateness of character i
  1472.     numbofposs:= [];        # at pos. 'i' the number of allowed restrictions
  1473.                             # for '<chars>[i]'
  1474.     lastimproved:= 0;       # last char which led to an improvement of 'pow';
  1475.                             # every run through the list may stop at this char
  1476.     powerchars:= [];        # at position 'i' the <prime>-th power of
  1477.                             # '<chars>[i]'
  1478.     i:= 1;
  1479.     while i <= Length( chars ) do
  1480.       powerchars[i]:= List( chars[i], x -> x ^ prime );
  1481.       minus:= MinusCharacter( chars[i], pow, prime );
  1482.       indet:= Indeterminateness( minus );
  1483.       indeterminateness[i]:= indet;
  1484.       if indet = 1 then
  1485.         if not quick
  1486.            and not NonnegIntScalarProducts( tbl, subchars, minus ) then
  1487.           return [];
  1488.         fi;
  1489.       elif indet < minamb then
  1490.         indeterminateness[i]:= 1;
  1491.       elif indet <= maxamb then
  1492.         poss:= contained( tbl, subchars, minus );
  1493.         if poss = [] then return []; fi;
  1494.         numbofposs[i]:= Length( poss );
  1495.         param:= Parametrized( poss );
  1496.         if param <> minus then  # improvement found
  1497.           UpdateMap( chars[i], pow, List( [ 1 .. Length( powerchars[i] ) ],
  1498.                              x-> powerchars[i][x] - prime * param[x] ) );
  1499.           lastimproved:= i;
  1500.           indeterminateness[i]:= Indeterminateness(
  1501.                                         CompositionMaps( chars[i], pow ) );
  1502.         fi;
  1503.       else
  1504.         numbofposs[i]:= "infinity";
  1505.         if ForAny( chars[i], x -> IsCyc(x) and not IsRat(x) ) then
  1506.  
  1507.           # maybe the indeterminateness of the rationalized character is
  1508.           # smaller but not 1
  1509.           rat:= RationalizedMat( [ chars[i] ] )[1];
  1510.           if not rat in chars then Add( chars, rat ); fi;
  1511.         fi;
  1512.       fi;
  1513.       i:= i + 1;
  1514.     od;
  1515.     if lastimproved > 0 then
  1516.       indeterminateness[ lastimproved ]:=
  1517.             Indeterminateness( CompositionMaps( chars[lastimproved], pow ) );
  1518.     fi;
  1519.     
  1520.     # step 2: (local function 'improvemap')
  1521.     #         loop over characters until no improvement is possible without a
  1522.     #         branch; update 'indeterminateness' and 'numbofposs';
  1523.     #         first character to test is at position 'first'; at least run up
  1524.     #         to character $'lastimproved' - 1$, update 'lastimproved' if an
  1525.     #         improvement occurs; return 'false' in the case of an
  1526.     #         inconsistency, 'true' otherwise.
  1527.     improvemap:= function( chars, pow, first, lastimproved,
  1528.                            indeterminateness, numbofposs, powerchars )
  1529.     local i, x, poss;
  1530.     i:= first;
  1531.     while i <> lastimproved do
  1532.       if indeterminateness[i] <> 1 then
  1533.         minus:= MinusCharacter( chars[i], pow, prime );
  1534.         indet:= Indeterminateness( minus );
  1535.         if indet < indeterminateness[i] then
  1536.  
  1537.           # only test those chars which now have smaller indeterminateness
  1538.           indeterminateness[i]:= indet;
  1539.           if indet = 1 then
  1540.             if not quick
  1541.                and not NonnegIntScalarProducts( tbl, subchars, minus ) then
  1542.               return false;
  1543.             fi;
  1544.           elif indet < minamb then
  1545.             indeterminateness[i]:= 1;
  1546.           elif indet <= maxamb then
  1547.             poss:= contained( tbl, subchars, minus );
  1548.             if poss = [] then return false; fi;
  1549.             numbofposs[i]:= Length( poss );
  1550.             param:= Parametrized( poss );
  1551.             if param <> minus then  # improvement found
  1552.               UpdateMap( chars[i], pow,
  1553.                          List( [ 1 .. Length( param ) ],
  1554.                                x -> powerchars[i][x] - prime * param[x] ) );
  1555.               lastimproved:= i;
  1556.               indeterminateness[i]:= Indeterminateness(
  1557.                                         CompositionMaps( chars[i], pow ) );
  1558.             fi;
  1559.           fi;
  1560.         fi;
  1561.       fi;
  1562.       if lastimproved = 0 then lastimproved:= i; fi;
  1563.       i:= i mod Length( chars ) + 1;
  1564.     od;
  1565.     indeterminateness[ lastimproved ]:=
  1566.             Indeterminateness( CompositionMaps( chars[lastimproved], pow ) );
  1567.     return true;
  1568.     end;
  1569.     
  1570.     # step 3: recursion; (local function 'allowedmaps')
  1571.     #         a) delete all characters which now have indeterminateness 1;
  1572.     #            their minus-characters (with respect to every powermap that
  1573.     #            will be found ) have nonnegative scalar products with
  1574.     #            <subchars>.
  1575.     #         b) branch according to a significant character or class
  1576.     #         c) for each possibility call 'improvemap' and then the recursion
  1577.     
  1578.     allowedmaps:= function( chars, pow, indeterminateness, numbofposs,
  1579.                             powerchars )
  1580.     local i, j, class, possibilities, poss, newpow, newpowerchars, newindet,
  1581.           newnumbofposs, copy;
  1582.     remain:= Filtered( [ 1 .. Length(chars) ], i->indeterminateness[i] > 1 );
  1583.     chars:=             Sublist( chars,             remain );
  1584.     indeterminateness:= Sublist( indeterminateness, remain );
  1585.     numbofposs:=        Sublist( numbofposs,        remain );
  1586.     powerchars:=        Sublist( powerchars,        remain );
  1587.  
  1588.     if chars = [] then
  1589.       InfoCharTable2( "#I PowermapsAllowedBySymmetrisations: no character",
  1590.                       " with indeterminateness\n#I    between ", minamb,
  1591.                       " and ", maxamb, " significant now\n" );
  1592.       return [ pow ];
  1593.     fi;
  1594.     possibilities:= [];
  1595.     if Minimum( numbofposs ) < maxlen then
  1596.       # branch according to a significant character
  1597.       # with minimal number of possible restrictions
  1598.       i:= Position( numbofposs, Minimum( numbofposs ) );
  1599.       InfoCharTable2( "#I PowermapsAllowedBySymmetrisations: branch at",
  1600.                       " character\n",
  1601.                       "#I     ", CharString( chars[i], "" ),
  1602.                       " (", numbofposs[i], " calls)\n" );
  1603.       poss:= contained( tbl, subchars,
  1604.                         MinusCharacter( chars[i], pow, prime ) );
  1605.       for j in poss do
  1606.         newpow:= Copy( pow );
  1607.         UpdateMap( chars[i], newpow, powerchars[i] - prime * j );
  1608.         newindet:= Copy( indeterminateness );
  1609.         newnumbofposs:= Copy( numbofposs );
  1610.         if improvemap( chars, newpow, i, 0, newindet, newnumbofposs,
  1611.                        powerchars ) then
  1612.           Append( possibilities,
  1613.                   allowedmaps( chars, newpow, newindet, newnumbofposs,
  1614.                                ShallowCopy( powerchars ) ) );
  1615.         fi;
  1616.       od;
  1617.       InfoCharTable2("#I PowermapsAllowedBySymmetrisations: return from",
  1618.                      " branch at character\n",
  1619.                      "#I     ", CharString( chars[i], "" ),
  1620.                      " (", numbofposs[i], " calls)\n" );
  1621.     else
  1622.     
  1623.       # branch according to a significant class in a
  1624.       # character with minimal nontrivial indet.
  1625.       i:= Position( indeterminateness, Minimum( indeterminateness ) );
  1626.                              # always nontrivial indet.!
  1627.       minus:= MinusCharacter( chars[i], pow, prime );
  1628.       class:= 1;
  1629.       while not IsList( minus[ class ] ) do class:= class + 1; od;
  1630.     
  1631.       InfoCharTable2( "#I PowermapsAllowedBySymmetrisations: ",
  1632.                       "branch at class ",
  1633.                       class, " (", Length( pow[ class ] ), " calls)\n" );
  1634.     
  1635.       # too many calls!!
  1636.       # (only those were necessary which are different for minus)
  1637.     
  1638.       for j in pow[ class ] do
  1639.         newpow:= Copy( pow );
  1640.         newpow[ class ]:= j;
  1641.         copy:= Copy( tbl.powermap );
  1642.         Unbind( copy[ prime ] );
  1643.         if TestConsistencyMaps( copy, newpow, copy ) then
  1644.           newindet:= Copy( indeterminateness );
  1645.           newnumbofposs:= Copy( numbofposs );
  1646.           if improvemap( chars, newpow, i, 0, newindet, newnumbofposs,
  1647.                          powerchars ) then
  1648.             Append( possibilities,
  1649.                     allowedmaps( chars, newpow, newindet, newnumbofposs,
  1650.                                  ShallowCopy( powerchars ) ) );
  1651.           fi;
  1652.         fi;
  1653.       od;
  1654.     
  1655.       InfoCharTable2( "#I PowermapsAllowedBySymmetrisations: return from",
  1656.                       " branch at class ", class, "\n" );
  1657.     
  1658.     fi;
  1659.     return possibilities;
  1660.     end;
  1661.     
  1662.     # start of the recursion:
  1663.     
  1664.     if lastimproved <> 0 then              # after step 1
  1665.       if not improvemap( chars, pow, 1, lastimproved, indeterminateness,
  1666.                          numbofposs, powerchars ) then
  1667.         return [];
  1668.       fi;
  1669.     fi;
  1670.     return allowedmaps( chars, pow, indeterminateness, numbofposs,
  1671.                         powerchars );
  1672.     end;
  1673.   
  1674.  
  1675. #############################################################################
  1676. ##
  1677. #F  'Powermap( <tbl>, <prime> )'
  1678. #F  'Powermap( <tbl>, <prime>, <parameters> )'
  1679. ##
  1680. ##  returns a list of possibilities for the <prime>-th powermap of the
  1681. ##  character table <tbl>.
  1682. ##  
  1683. ##  The optional record <parameters> may have the following fields\:
  1684. ##  
  1685. ##  'chars':\\
  1686. ##       a list of characters which are used for the check of kernels
  1687. ##       (see "ConsiderKernels"), the test of congruences (see "Congruences")
  1688. ##       and the test of scalar products of symmetrisations
  1689. ##       (see "PowermapsAllowedBySymmetrisations");
  1690. ##       the default is '<tbl>.irreducibles'
  1691. ##  
  1692. ##  'powermap':\\
  1693. ##       a (parametrized) map which is an approximation of the desired map
  1694. ##  
  1695. ##  'decompose':\\
  1696. ##       a boolean; if 'true', the symmetrisations of 'chars' must have all
  1697. ##       constituents in 'chars', that will be used in the algorithm;
  1698. ##       if 'chars' is not bound and '<tbl>.irreducibles' is complete,
  1699. ##       the default value of 'decompose' is 'true', otherwise 'false'
  1700. ##  
  1701. ##  'quick':\\
  1702. ##       a boolean; if 'true', the subroutines are called with the option
  1703. ##       '\"quick\"'; especially, a unique map will be returned immediately
  1704. ##       without checking all symmetrisations; the default value is 'false'
  1705. ##  
  1706. ##  'parameters':\\
  1707. ##       a record with fields 'maxamb', 'minamb' and 'maxlen' which control
  1708. ##       the subroutine 'PowermapsAllowedBySymmetrisations'\:
  1709. ##       It only uses characters with actual indeterminateness up to
  1710. ##       'maxamb', tests decomposability only for characters with actual
  1711. ##       indeterminateness at least 'minamb' and admits a branch only
  1712. ##       according to a character if there is one with at most 'maxlen'
  1713. ##       possible minus-characters.
  1714. ##
  1715. Powermap := function( arg )
  1716.     local i, x, tbl, chars, prime, powermap, indet, maxamb, minamb, maxlen,
  1717.           poss, rat, pow, approxval, powerval, approxpowermap, quick, ok,
  1718.           decompose;
  1719.     
  1720.     if not ( Length( arg ) in [ 2, 3 ] and IsCharTable( arg[1] )
  1721.              and IsPrimeInt( arg[2] ) )
  1722.        or ( Length( arg ) = 3 and not IsRec( arg[3] ) ) then
  1723.       Error( "usage: Powermap( <tbl>, <prime> )\n",
  1724.              " resp. Powermap( <tbl>, <prime>, <parameters> )" );
  1725.     fi;
  1726.     
  1727.     tbl:=   arg[1];
  1728.     prime:= arg[2];
  1729.     
  1730.     if Length( arg ) = 3 then       # parameters
  1731.       if IsBound( arg[3].chars ) then
  1732.         chars:= arg[3].chars;
  1733.         decompose:= false;
  1734.       else
  1735.         if IsBound( tbl.irreducibles ) then
  1736.           chars:= tbl.irreducibles;
  1737.           if Length( chars ) = Length( tbl.centralizers ) then
  1738.             decompose:= true;
  1739.           else
  1740.             decompose:= false;
  1741.           fi;
  1742.         else
  1743.           chars:= [];
  1744.           decompose:= false;
  1745.         fi;
  1746.       fi;
  1747.       if IsBound( arg[3].powermap ) then
  1748.         approxpowermap:= arg[3].powermap;
  1749.       else
  1750.         approxpowermap:= [];
  1751.       fi;
  1752.       if IsBound( arg[3].quick ) and arg[3].quick = true then
  1753.         quick:= true;
  1754.       else
  1755.         quick:= false;
  1756.       fi;
  1757.       if IsBound( arg[3].decompose ) then
  1758.         if arg[3].decompose = true then
  1759.           decompose:= true;
  1760.         else
  1761.           decompose:= false;
  1762.         fi;
  1763.       fi;
  1764.       if IsBound( arg[3].parameters ) then
  1765.         maxamb:= arg[3].parameters.maxamb;
  1766.         minamb:= arg[3].parameters.minamb;
  1767.         maxlen:= arg[3].parameters.maxlen;
  1768.       else
  1769.         maxamb:= 100000;
  1770.         minamb:= 10000;
  1771.         maxlen:= 10;
  1772.       fi;
  1773.     else
  1774.       if IsBound( tbl.irreducibles ) then 
  1775.         chars:= tbl.irreducibles;
  1776.       else
  1777.         chars:= [];
  1778.       fi;
  1779.       if Length( chars ) = Length( tbl.centralizers ) then
  1780.         decompose:= true;
  1781.       else
  1782.         decompose:= false;
  1783.       fi;
  1784.       approxpowermap:= [];
  1785.       quick:= false;
  1786.       maxamb:= 100000;
  1787.       minamb:= 10000;
  1788.       maxlen:= 10;
  1789.     fi;
  1790.     
  1791.     powermap:= InitPowermap( tbl, prime );
  1792.     if powermap = false then
  1793.       InfoCharTable2( "#I Powermap: no initialization possible\n" );
  1794.       return [];
  1795.     fi;
  1796.     
  1797.     # use 'approxpowermap'\:
  1798.     
  1799.     for i in [ 1 .. Minimum( Length(approxpowermap), Length(powermap) ) ] do
  1800.       if IsBound( approxpowermap[i] ) then
  1801.         if IsInt( approxpowermap[i] ) then
  1802.           approxval:= [ approxpowermap[i] ];
  1803.         else
  1804.           approxval:= approxpowermap[i];
  1805.         fi;
  1806.         if IsInt( powermap[i] ) then
  1807.           powerval:= [ powermap[i] ];
  1808.         else
  1809.           powerval:= powermap[i];
  1810.         fi;
  1811.         powerval:= Intersection( approxval, powerval );
  1812.         if powerval = [] then
  1813.           Print( "#I Powermap: possible maps not compatible with ",
  1814.                  "<approxpowermap> at class ", i, "\n" );
  1815.           return [];
  1816.         elif Length( powerval ) = 1 then
  1817.           powermap[i]:= powerval[1];
  1818.         else
  1819.           powermap[i]:= powerval;
  1820.         fi;
  1821.       fi;
  1822.     od;
  1823.     
  1824.     if quick then
  1825.       ok:= Congruences( tbl, chars, powermap, prime, "quick" );
  1826.     else
  1827.       ok:= Congruences( tbl, chars, powermap, prime );
  1828.     fi;
  1829.     if not ok then
  1830.       InfoCharTable2( "#I Powermap: errors in Congruences\n" );
  1831.       return [];
  1832.     fi;
  1833.     if quick then
  1834.       ok:= ConsiderKernels( tbl, chars, powermap, prime, "quick" );
  1835.     else
  1836.       ok:= ConsiderKernels( tbl, chars, powermap, prime );
  1837.     fi;
  1838.     if not ok then
  1839.       InfoCharTable2( "#I Powermap: errors in ConsiderKernels\n" );
  1840.       return [];
  1841.     fi;
  1842.     if IsBound( tbl.powermap ) and IsList( tbl.powermap ) then
  1843.       if quick then
  1844.         ConsiderSmallerPowermaps( tbl, powermap, prime, "quick" );
  1845.       else
  1846.         ConsiderSmallerPowermaps( tbl, powermap, prime );
  1847.       fi;
  1848.     fi;
  1849.     
  1850.     if InfoCharTable2 <> Ignore then
  1851.       Print( "#I Powermap: ", Ordinal( prime ),
  1852.              " powermap initialized; congruences, kernels and\n",
  1853.              "#I    maps for smaller primes considered.\n",
  1854.              "#I    The actual indeterminateness is ",
  1855.              Indeterminateness( powermap ), ".\n" );
  1856.       if quick then
  1857.         Print( "#I    (\"quick\" option specified)\n" );
  1858.       fi;
  1859.     fi;
  1860.     
  1861.     if quick and ForAll( powermap, IsInt ) then return [ powermap ]; fi;
  1862.     
  1863.     # now use restricted characters:
  1864.     # If the parameter \"decompose\" was entered, use decompositions
  1865.     # of minus-characters of <chars> into <chars>;
  1866.     # otherwise only check the scalar products with <chars>.
  1867.     
  1868.     if decompose then                 # usage of decompositions allowed
  1869.       if Indeterminateness( powermap ) < minamb then
  1870.         InfoCharTable2( "#I Powermap: indeterminateness too small for test",
  1871.                         " of decomposability\n" );
  1872.         poss:= [ powermap ];
  1873.       else
  1874.         InfoCharTable2( "#I Powermap: now test decomposability of rational ",
  1875.                         "minus-characters\n" );
  1876.         rat:= RationalizedMat( chars );
  1877.         poss:= PowermapsAllowedBySymmetrisations( tbl, rat, rat, powermap,
  1878.                              prime, rec( maxlen:= maxlen,
  1879.                                          contained:= ContainedCharacters,
  1880.                                          minamb:= minamb,
  1881.                                          maxamb:= "infinity",
  1882.                                          quick:= quick ) );
  1883.         if InfoCharTable2 <> Ignore then
  1884.           Print( "#I Powermap: decomposability tested,\n" );
  1885.           if Length( poss ) = 1 then
  1886.             Print( "#I    1 solution with indeterminateness ",
  1887.                    Indeterminateness( poss[1] ), "\n" );
  1888.           else
  1889.             Print( "#I    ", Length( poss ),
  1890.                    " solutions with indeterminateness\n",
  1891.                    List( poss, Indeterminateness ), "\n" );
  1892.           fi;
  1893.         fi;
  1894.         if quick and Length( poss ) = 1 and ForAll( poss[1], IsInt ) then
  1895.           return [ poss[1] ];
  1896.         fi;
  1897.       fi;
  1898.     else
  1899.       InfoCharTable2( "#I Powermap: no test of decomposability allowed\n" );
  1900.       poss:= [ powermap ];
  1901.     fi;
  1902.     
  1903.     InfoCharTable2( "#I Powermap: test scalar products",
  1904.                     " of minus-characters\n" );
  1905.     
  1906.     powermap:= [];
  1907.     for pow in poss do
  1908.       Append( powermap,
  1909.               PowermapsAllowedBySymmetrisations( tbl, chars, chars, pow,
  1910.                           prime, rec( maxlen:= maxlen,
  1911.                                       contained:= ContainedPossibleCharacters,
  1912.                                       minamb:= 1,
  1913.                                       maxamb:= maxamb,
  1914.                                       quick:= quick ) ) );
  1915.     od;
  1916.  
  1917.     if InfoCharTable2 <> Ignore then
  1918.       if ForAny( powermap, x -> ForAny( x, IsList ) ) then
  1919.         Print( "#I Powermap: ", Length(powermap), " parametrized solution" );
  1920.         if Length(powermap) = 1 then Print(",\n"); else Print("s,\n"); fi;
  1921.         Print( "#I    no further improvement was possible with given",
  1922.                " characters\n",
  1923.                "#I    and maximal checked ambiguity of ", maxamb, "\n" );
  1924.       else
  1925.         Print( "#I Powermap: ", Length( powermap ), " solution" );
  1926.         if Length(powermap) = 1 then Print("\n"); else Print("s\n"); fi;
  1927.       fi;
  1928.     fi;
  1929.     return powermap;
  1930.     end;
  1931.  
  1932.  
  1933. #############################################################################
  1934. ##
  1935. #F  ConsiderTableAutomorphisms( <parafus>, <grp> )
  1936. ##
  1937. ##  improves the parametrized subgroup fusion map <parafus> so that
  1938. ##  afterwards exactly one representative of fusion maps (that is contained
  1939. ##  in <parafus>) in every orbit under the action of the permutation group
  1940. ##  <grp> is contained in <parafus>.
  1941. ##
  1942. ##  The list of positions where improvements were found is returned.
  1943. ##
  1944. ConsiderTableAutomorphisms := function( parafus, grp )
  1945.     local i, support, images, notstable, orbits, isunion, image, orb,
  1946.           im, found, prop;
  1947.     
  1948.     # step 1: Compute the subgroup of <grp> that acts on all images
  1949.     #         under <parafus>; if <parafus> contains all possible subgroup
  1950.     #         fusions, this is the whole group of table automorphisms of the
  1951.     #         supergroup table.
  1952.     
  1953.     if grp.generators = [] then return []; fi;
  1954.     images:= Set( parafus );
  1955.     notstable:= Filtered( images, x -> IsInt(x) and
  1956.                           ForAny( grp.generators, y->x^y<>x ) );
  1957.     if notstable = [] then
  1958.       MakeStabChain( grp );
  1959.     else
  1960.       InfoPermGroup2( "#I ConsiderTableAutomorphisms: not all generators fix",
  1961.                       " uniquely\n#I    determined images;",
  1962.                       " computing admissible subgroup\n" );
  1963.       grp.operations.MakeStabChain(   grp, notstable );
  1964.       grp.operations.ExtendStabChain( grp, notstable );
  1965.       for i in notstable do
  1966.         if grp.generators <> [] then grp:= grp.stabilizer; fi;
  1967.       od;
  1968.       grp:= Group( grp.generators, () );
  1969.     fi;
  1970.     if grp.generators = [] then return []; fi;
  1971.  
  1972.     images:= Filtered( images, IsList );
  1973.     support:= grp.operations.LargestMovedPoint( grp );
  1974.     orbits:= List( Orbits( grp, [ 1 .. support ] ), Set );
  1975.                               # sets because entries of parafus are sets
  1976.  
  1977.     isunion:= function( image )
  1978.     while image <> [] do
  1979.       if image[1] > support then return true; fi;
  1980.       orb:= First( orbits, x -> image[1] in x );
  1981.       if Difference( orb, image ) <> [] then return false; fi;
  1982.       image:= Difference( image, orb );
  1983.     od;
  1984.     return true;
  1985.     end;
  1986.  
  1987.     notstable:= Filtered( images, x -> not isunion(x) );
  1988.     if notstable <> [] then
  1989.       InfoPermGroup2( "#I ConsiderTableAutomorphisms:",
  1990.                       " not all generators act;\n",
  1991.                       "#I    computing admissible subgroup\n" );
  1992.       for i in notstable do
  1993.         grp:= grp.operations.StabilizerSet( grp, i );
  1994.       od;
  1995.     
  1996.     #   prop:= function( perm )
  1997.     #          return ForAll( notstable, x -> Set( x^perm ) = x );
  1998.     #          end;
  1999.     #   grp:= SubgroupProperty( grp, prop );
  2000.     
  2001.     fi;
  2002.     
  2003.     # step 2: If possible, find a class where the image {\em is} a nontrivial
  2004.     #         orbit under <grp>, i.e. no other points are
  2005.     #         possible. Then replace the image by the first point of the
  2006.     #         orbit, and replace <grp> by the stabilizer of
  2007.     #         the new image in <grp>.
  2008.     
  2009.     found:= [];
  2010.     i:= 1;
  2011.     while i <= Length( parafus ) and grp.generators <> [] do
  2012.       if IsList( parafus[i] ) and parafus[i] in orbits then
  2013.         Add( found, i );
  2014.         parafus[i]:= parafus[i][1];
  2015.         grp:= grp.operations.Stabilizer( grp, parafus[i], OnPoints );
  2016.         if grp.generators <> [] then
  2017.           support:= grp.operations.LargestMovedPoint( grp );
  2018.           orbits:= List( Orbits( grp, [ 1 .. support ] ), Set );
  2019.  
  2020.           # Compute orbits of the smaller group; sets because entries
  2021.           # of parafus are sets
  2022.  
  2023.         fi;
  2024.       fi;
  2025.       i:= i + 1;
  2026.     od;
  2027.     
  2028.     # step 3: If 'grp' is not trivial, find classes where the image
  2029.     #         {\em contains} a nontrivial orbit under 'grp'. 
  2030.     
  2031.     i:= 1;
  2032.     while i <= Length( parafus ) and grp.generators <> [] do
  2033.       if IsList( parafus[i] ) and ForAny( grp.generators,
  2034.                                   x -> ForAny( parafus[i], y->y^x<>y ) ) then
  2035.         Add( found, i );
  2036.         image:= [];
  2037.         while parafus[i] <> [] do
  2038.     
  2039.           # now it is necessary to consider orbits of the smaller group,
  2040.           # since improvements in step 2 and 3 may affect the action
  2041.           # on the images.
  2042.     
  2043.           Add( image, parafus[i][1] );
  2044.           parafus[i]:= Difference( parafus[i], Orbit( grp, parafus[i][1] ) );
  2045.         od;
  2046.         for im in image do
  2047.           if grp.generators <> [] then
  2048.             grp:= grp.operations.Stabilizer( grp, im, OnPoints );
  2049.           fi;
  2050.         od;
  2051.         parafus[i]:= image;
  2052.       fi;
  2053.       i:= i+1;
  2054.     od;
  2055.     return found;
  2056.     end;
  2057.  
  2058.  
  2059. #############################################################################
  2060. ##
  2061. #F  OrbitFusions( <subtblautomorphisms>, <fusionmap>, <tblautomorphisms> )
  2062. ##
  2063. ##  returns the orbit of the subgroup fusion map <fusionmap> under the
  2064. ##  actions of maximal admissible subgroups of the table automorphisms
  2065. ##  <subtblautomorphisms> of the subgroup table and <tblautomorphisms> of
  2066. ##  the supergroup table.
  2067. ##  The table automorphisms must be both permutation groups.
  2068. ##
  2069. OrbitFusions := function( subtblautomorphisms, fusionmap, tblautomorphisms )
  2070.     local orb, gen, image;
  2071.  
  2072.     orb:= [ fusionmap ];
  2073.     for fusionmap in orb do
  2074.       for gen in subtblautomorphisms.generators do
  2075.         image:= Permuted( fusionmap, gen );
  2076.         if not image in orb then Add( orb, image ); fi;
  2077.       od;
  2078.     od;
  2079.     for fusionmap in orb do
  2080.       for gen in tblautomorphisms.generators do
  2081.         image:= List( fusionmap, x->x^gen );
  2082.         if not image in orb then Add( orb, image ); fi;
  2083.       od;
  2084.     od;
  2085.     return orb;
  2086.     end;
  2087.  
  2088.  
  2089. #############################################################################
  2090. ##
  2091. #F  OrbitPowermaps( <powermap>, <matautomorphisms> )
  2092. ##
  2093. ##  returns the orbit of the powermap <powermap> under the action of the
  2094. ##  maximal admissible subgroup of the matrix automorphisms
  2095. ##  <matautomorphisms> of the considered character table.
  2096. ##  The matrix automorphisms must be a permutation group.
  2097. ##
  2098. OrbitPowermaps := function( powermap, matautomorphisms )
  2099.     local nccl, orb, gen, image;
  2100.  
  2101.     nccl:= Length( powermap );
  2102.     orb:= [ powermap ];
  2103.     for powermap in orb do
  2104.       for gen in matautomorphisms.generators do
  2105.         image:= List( [ 1 .. nccl ], x -> powermap[ x^gen ] / gen );
  2106.         if not image in orb then Add( orb, image ); fi;
  2107.       od;
  2108.     od;
  2109.     return orb;
  2110.     end;
  2111.  
  2112.  
  2113. #############################################################################
  2114. ##
  2115. #F  RepresentativesFusions( <subtblautomorphisms>, <listoffusionmaps>,
  2116. #F                          <tblautomorphisms> )
  2117. #F  RepresentativesFusions( <subtbl>, <listoffusionmaps>, <tbl> )
  2118. ##
  2119. ##  returns a list of representatives of subgroup fusions in the list
  2120. ##  <listoffusionmaps> under the action of maximal admissible subgroups
  2121. ##  of the table automorphisms <subtblautomorphisms> of the subgroup table
  2122. ##  and <tblautomorphisms> of the supergroup table.
  2123. ##  The table automorphisms must be both permutation groups.
  2124. ##
  2125. RepresentativesFusions := function( subtblautomorphisms, listoffusionmaps,
  2126.                                     tblautomorphisms )
  2127.     local stable, prop, orbits, orbit;
  2128.     
  2129.     if listoffusionmaps = [] then return []; fi;
  2130.     listoffusionmaps:= Set( listoffusionmaps );
  2131.     
  2132.     if IsCharTable( subtblautomorphisms ) then
  2133.       if IsBound( subtblautomorphisms.automorphisms ) then
  2134.         subtblautomorphisms:= subtblautomorphisms.automorphisms;
  2135.       else
  2136.         subtblautomorphisms:= Group( () );
  2137.         Print( "#I RepresentativesFusions:",
  2138.                " no subtable automorphisms stored\n" );
  2139.       fi;
  2140.     fi;
  2141.     if IsCharTable( tblautomorphisms ) then
  2142.       if IsBound( tblautomorphisms.automorphisms ) then
  2143.         tblautomorphisms:= tblautomorphisms.automorphisms;
  2144.       else
  2145.         tblautomorphisms:= Group( () );
  2146.         Print( "#I RepresentativesFusions: no table automorphisms stored\n" );
  2147.       fi;
  2148.     fi;
  2149.       
  2150.     # find the subgroups of the table automorphism groups which act on
  2151.     # <listoffusionmaps>\:
  2152.     
  2153.     stable:= Filtered( subtblautomorphisms.generators,
  2154.                     x -> ForAll( listoffusionmaps, 
  2155.                               y -> Permuted( y, x ) in listoffusionmaps ) );
  2156.     if not stable = subtblautomorphisms.generators then
  2157.       Print("#I RepresentativesFusions: Not all table automorphisms of the\n",
  2158.             "#I    subgroup table do act;",
  2159.             " computing the admissible subgroup.\n" );
  2160.       prop:= ( x -> ForAll( listoffusionmaps, 
  2161.                             y -> Permuted( y, x ) in listoffusionmaps ) );
  2162.       subtblautomorphisms:=
  2163.                PermGroupOps.SubgroupProperty( subtblautomorphisms, prop,
  2164.                                               Group( stable, () ) );
  2165.     fi;
  2166.     
  2167.     stable:= Filtered( tblautomorphisms.generators,
  2168.                     x -> ForAll( listoffusionmaps, 
  2169.                               y -> List( y, z->z^x ) in listoffusionmaps ) );
  2170.     if not stable = tblautomorphisms.generators then
  2171.       Print("#I RepresentativesFusions: Not all table automorphisms of the\n",
  2172.             "#I    supergroup table do act;",
  2173.             " computing the admissible subgroup.\n" );
  2174.       prop:= ( x -> ForAll( listoffusionmaps, 
  2175.                             y -> List( y, z -> z^x ) in listoffusionmaps ) );
  2176.       tblautomorphisms:= 
  2177.             PermGroupOps.SubgroupProperty( tblautomorphisms, prop,
  2178.                                            Group( stable, () ) );
  2179.     fi;
  2180.     
  2181.     # distribute the maps to orbits\:
  2182.     
  2183.     orbits:= [];
  2184.     while listoffusionmaps <> []  do
  2185.       orbit:= OrbitFusions( subtblautomorphisms, listoffusionmaps[1],
  2186.                             tblautomorphisms );
  2187.       Add( orbits, orbit );
  2188.       SubtractSet( listoffusionmaps, orbit );
  2189.     od;
  2190.     
  2191.     if InfoCharTable2 <> Ignore then
  2192.       if Length( orbits ) = 1 then
  2193.         Print( "#I RepresentativesFusions: There is 1 orbit of length ",
  2194.                Length( orbits[1] ), ".\n" );
  2195.       else
  2196.         Print( "#I RepresentativesFusions: There are ", Length( orbits ),
  2197.                " orbits of lengths ", List( orbits, Length ), ".\n" );
  2198.       fi;
  2199.     fi;
  2200.     
  2201.     # choose representatives\:
  2202.     
  2203.     return List( orbits, x -> x[1] );
  2204.     end;
  2205.     
  2206.  
  2207. #############################################################################
  2208. ##
  2209. #F  RepresentativesPowermaps( <listofpowermaps>, <matautomorphisms> )
  2210. ##
  2211. ##  returns a list of representatives of powermaps in the list
  2212. ##  <listofpowermaps> under the action of the maximal admissible subgroup
  2213. ##  of the matrix automorphisms <matautomorphisms> of the considered
  2214. ##  character matrix.
  2215. ##  The matrix automorphisms must be a permutation group.
  2216. ##
  2217. RepresentativesPowermaps := function( listofpowermaps, matautomorphisms )
  2218.     local nccl, stable, prop, orbits, orbit;
  2219.     
  2220.     if listofpowermaps = [] then return []; fi;
  2221.     listofpowermaps:= Set( listofpowermaps );
  2222.     
  2223.     # find the subgroup of the table automorphism group which acts on
  2224.     # <listofpowermaps>\:
  2225.     
  2226.     nccl:= Length( listofpowermaps[1] );
  2227.     stable:= Filtered( matautomorphisms.generators,
  2228.               x -> ForAll( listofpowermaps, 
  2229.               y -> List( [ 1..nccl ], z -> y[z^x]/x ) in listofpowermaps ) );
  2230.     if not stable = matautomorphisms.generators then
  2231.       Print( "#I RepresentativesPowermaps: Not all table automorphisms\n",
  2232.              "#I    do act; computing the admissible subgroup.\n" );
  2233.       prop:= ( x -> ForAll( listofpowermaps, 
  2234.                y -> List( [ 1..nccl ], z -> y[z^x]/x ) in listofpowermaps ) );
  2235.       if stable = [] then stable:= (); fi;
  2236.       matautomorphisms:=
  2237.             PermGroupOps.SubgroupProperty( matautomorphisms, prop,
  2238.                                            Group( stable, () ) );
  2239.     fi;
  2240.     
  2241.     # distribute the maps to orbits\:
  2242.     
  2243.     orbits:= [];
  2244.     while listofpowermaps <> []  do
  2245.       orbit:= OrbitPowermaps( listofpowermaps[1], matautomorphisms );
  2246.       Add( orbits, orbit );
  2247.       SubtractSet( listofpowermaps, orbit );
  2248.     od;
  2249.     
  2250.     if InfoCharTable2 <> Ignore then
  2251.       if Length( orbits ) = 1 then
  2252.         Print( "#I RepresentativesPowermaps: There is 1 orbit of length ",
  2253.                Length( orbits[1] ), ".\n" );
  2254.       else
  2255.         Print( "#I RepresentativesPowermaps: There are ", Length( orbits ),
  2256.                " orbits of lengths ", List( orbits, Length ), ".\n" );
  2257.       fi;
  2258.     fi;
  2259.     
  2260.     # choose representatives\:
  2261.     
  2262.     return List( orbits, x -> x[1] );
  2263.     end;
  2264.     
  2265.  
  2266. #############################################################################
  2267. ##
  2268. #F  FusionsAllowedByRestrictions( <subtbl>, <tbl>, <subchars>, <chars>,
  2269. #F                                <fus>, <parameters> )
  2270. ##
  2271. ##  <parameters must be a record with fields <maxlen> (int), <contained>,
  2272. ##  <minamb>, <maxamb> and <quick> (boolean).
  2273. ##
  2274. ##  First, for all $\chi \in <chars>$ let
  2275. ##  'restricted:= CompositionMaps( $\chi$, <fus> )'.
  2276. ##  If '<minamb> \< Indeterminateness( restricted ) \< <maxamb>', construct
  2277. ##  'poss:= contained( <subtbl>, <subchars>, restricted )'.
  2278. ##  (<contained> is a function that will be 'ContainedCharacters' or
  2279. ##  'ContainedPossibleCharacters'.)
  2280. ##  Improve <fus> if possible.
  2281. ##
  2282. ##  If 'Indeterminateness( restricted ) \< <minamb>', delete this character;
  2283. ##  for unique restrictions and '<parameters>.quick = false', the scalar
  2284. ##  products with <subchars> are checked.
  2285. ##
  2286. ##  If the restriction of a character *becomes* unique during the
  2287. ##  processing, its scalar products with <subchars> are checked.
  2288. ##
  2289. ##  If no further improvement is possible, delete all characters with unique
  2290. ##  restrictions or, more general, indeterminateness at most <minamb>,
  2291. ##  and branch:
  2292. ##  If there is a character left with less or equal <maxlen> possible
  2293. ##  restrictions, compute the union of fusions allowed by these restrictions;
  2294. ##  otherwise choose a class 'c' of <subgroup> which is significant for some
  2295. ##  character, and compute the union of all allowed fusions with image 'x' on
  2296. ##  'c', where 'x' runs over '<fus>[c]'.
  2297. ##
  2298. ##  By recursion, one gets the list of fusions which are parametrized on all
  2299. ##  classes where no element of <chars> is significant, and which yield
  2300. ##  nonnegative integer scalar products for the restrictions of <chars>
  2301. ##  with <subchars> (or additionally decomposability).
  2302. ##
  2303. ##  If '<parameters>.quick = true', unique restrictions are never considered.
  2304. ##
  2305. FusionsAllowedByRestrictions := function( subtbl, tbl, subchars, chars, fus,
  2306.                                           parameters )
  2307.     local x, i, j, indeterminateness, numbofposs, lastimproved, restricted,
  2308.           indet, rat, poss, param, remain, possibilities, improvefusion,
  2309.           allowedfusions, maxlen, contained, minamb, maxamb, quick;
  2310.  
  2311.     if chars = [] then return [ fus ]; fi;
  2312.     chars:= Set( chars );
  2313.     
  2314.     # but maybe there are characters with equal restrictions ...
  2315.     
  2316.     # record <parameters>\:
  2317.     if not IsRec( parameters ) then
  2318.       Error( "<parameters> must be a record with fields 'maxlen',\n",
  2319.              "'contained', 'minamb', 'maxamb' and 'quick'" );
  2320.     fi;
  2321.  
  2322.     maxlen:= parameters.maxlen;
  2323.     contained:= parameters.contained;
  2324.     minamb:= parameters.minamb;
  2325.     maxamb:= parameters.maxamb;
  2326.     quick:= parameters.quick;
  2327.     
  2328.     if quick and Indeterminateness( fus ) < minamb then # immediately return
  2329.       InfoCharTable2( "#I FusionsAllowedByRestrictions: indeterminateness of",
  2330.                       " the map\n#I    is smaller than the parameter value",
  2331.                       " 'minamb'; returned\n" );
  2332.       return [ fus ];
  2333.     fi;
  2334.     
  2335.     # step 1: check all in <chars>; if one has too big indeterminateness
  2336.     #         and contains irrational entries, append its rationalized char
  2337.     #         <chars>.
  2338.     indeterminateness:= []; # at position i the indeterminateness of char i
  2339.     numbofposs:= [];        # at position 'i' the number of allowed
  2340.                             # restrictions for '<chars>[i]'
  2341.     lastimproved:= 0;       # last char which led to an improvement of 'fus';
  2342.                             # every run through the list may stop at this char
  2343.     i:= 1;
  2344.     while i <= Length( chars ) do
  2345.       restricted:= CompositionMaps( chars[i], fus );
  2346.       indet:= Indeterminateness( restricted );
  2347.       indeterminateness[i]:= indet;
  2348.       if indet = 1 then
  2349.         if not quick
  2350.            and not NonnegIntScalarProducts(subtbl,subchars,restricted) then
  2351.           return [];
  2352.         fi;
  2353.       elif indet < minamb then
  2354.         indeterminateness[i]:= 1;
  2355.       elif indet <= maxamb then
  2356.         poss:= contained( subtbl, subchars, restricted );
  2357.         if poss = [] then return []; fi;
  2358.         numbofposs[i]:= Length( poss );
  2359.         param:= Parametrized( poss );
  2360.         if param <> restricted then  # improvement found
  2361.           UpdateMap( chars[i], fus, param );
  2362.           lastimproved:= i;
  2363.       
  2364.       # call of TestConsistencyMaps ? ( with respect to improved classes )
  2365.     
  2366.           indeterminateness[i]:= Indeterminateness(
  2367.                                         CompositionMaps( chars[i], fus ) );
  2368.         fi;
  2369.       else
  2370.         numbofposs[i]:= "infinity";
  2371.         if ForAny( chars[i], x -> IsCyc(x) and not IsRat(x) ) then
  2372.     
  2373.           # maybe the indeterminateness of the rationalized
  2374.           # character is smaller but not 1
  2375.           rat:= RationalizedMat( [ chars[i] ] )[1];
  2376.           AddSet( chars, rat );
  2377.         fi;
  2378.       fi;
  2379.       i:= i + 1;
  2380.     od;
  2381.     
  2382.     # step 2: (local function 'improvefusion')
  2383.     #         loop over chars until no improvement is possible without a
  2384.     #         branch; update 'indeterminateness' and 'numbofposs';
  2385.     #         first character to test is at position 'first'; at least run
  2386.     #         up to character $'lastimproved' - 1$; update 'lastimproved' if
  2387.     #         an improvement occurs;
  2388.     #         return 'false' in the case of an inconsistency, 'true'
  2389.     #         otherwise.
  2390.  
  2391.     #         Note:
  2392.     #         'subtbl', 'subchars' and 'maxlen' are global
  2393.     #         variables for this function, also (but not necessary) global are
  2394.     #         'restricted', 'indet' and 'param'.
  2395.     
  2396.     improvefusion:=
  2397.          function(chars,fus,first,lastimproved,indeterminateness,numbofposs)
  2398.     local i, poss;
  2399.     i:= first;
  2400.     while i <> lastimproved do
  2401.       if indeterminateness[i] <> 1 then
  2402.         restricted:= CompositionMaps( chars[i], fus );
  2403.         indet:= Indeterminateness( restricted );
  2404.         if indet < indeterminateness[i] then
  2405.     
  2406.           # only test those characters which now have smaller
  2407.           # indeterminateness
  2408.           indeterminateness[i]:= indet;
  2409.           if indet = 1 then
  2410.             if not quick and
  2411.                not NonnegIntScalarProducts(subtbl,subchars,restricted) then
  2412.               return false;
  2413.             fi;
  2414.           elif indet < minamb then
  2415.             indeterminateness[i]:= 1;
  2416.           elif indet <= maxamb then
  2417.             poss:= contained( subtbl, subchars, restricted );
  2418.             if poss = [] then return false; fi;
  2419.             numbofposs[i]:= Length( poss );
  2420.             param:= Parametrized( poss );
  2421.             if param <> restricted then  # improvement found
  2422.               UpdateMap( chars[i], fus, param );
  2423.               lastimproved:= i;
  2424.       
  2425.       # call of TestConsistencyMaps ? ( with respect to improved classes )
  2426.     
  2427.               indeterminateness[i]:= Indeterminateness(
  2428.                                         CompositionMaps( chars[i], fus ) );
  2429.             fi;
  2430.           fi;
  2431.         fi;
  2432.       fi;
  2433.       if lastimproved = 0 then lastimproved:= i; fi;
  2434.       i:= i mod Length( chars ) + 1;
  2435.     od;
  2436.     return true;
  2437.     end;
  2438.     
  2439.     # step 3: recursion; (local function 'allowedfusions')
  2440.     #         a) delete all characters which now have indeterminateness 1;
  2441.     #            their restrictions (with respect to every fusion that will be
  2442.     #            found ) have nonnegative scalar products with <subchars>.
  2443.     #         b) branch according to a significant character or class
  2444.     #         c) for each possibility call 'improvefusion' and then the
  2445.     #            recursion
  2446.     
  2447.     allowedfusions:= function( subpowermap, powermap, chars, fus,
  2448.                                indeterminateness, numbofposs )
  2449.     local i, j, class, possibilities, poss, newfus, newpow, newsubpow,
  2450.           newindet, newnumbofposs;
  2451.     remain:= Filtered( [ 1..Length( chars ) ], i->indeterminateness[i] > 1 );
  2452.     chars:=             Sublist( chars,             remain );
  2453.     indeterminateness:= Sublist( indeterminateness, remain );
  2454.     numbofposs:=        Sublist( numbofposs,        remain );
  2455.  
  2456.     if chars = [] then
  2457.       InfoCharTable2( "#I FusionsAllowedByRestrictions: no character with",
  2458.                       " indeterminateness\n#I    between ", minamb, " and ",
  2459.                       maxamb, " significant now\n" );
  2460.       return [ fus ];
  2461.     fi;
  2462.     possibilities:= [];
  2463.     if Minimum( numbofposs ) < maxlen then
  2464.     
  2465.       # branch according to a significant character
  2466.       # with minimal number of possible restrictions
  2467.       i:= Position( numbofposs, Minimum( numbofposs ) );
  2468.       InfoCharTable2("#I FusionsAllowedByRestrictions: branch at",
  2469.                       " character\n",
  2470.                       "#I     ", CharString( chars[i], "" ),
  2471.                       " (", numbofposs[i], " calls)\n" );
  2472.       poss:= contained( subtbl, subchars,
  2473.                         CompositionMaps( chars[i], fus ) );
  2474.       for j in poss do
  2475.         newfus:= Copy( fus );
  2476.         newpow:= Copy( powermap );
  2477.         newsubpow:= Copy( subpowermap );
  2478.         UpdateMap( chars[i], newfus, j );
  2479.         if TestConsistencyMaps( newsubpow, newfus, newpow ) then
  2480.           newindet:= Copy( indeterminateness );
  2481.           newnumbofposs:= Copy( numbofposs );
  2482.           if improvefusion(chars,newfus,i,0,newindet,newnumbofposs) then
  2483.             Append( possibilities,
  2484.                     allowedfusions( newsubpow, newpow, chars,
  2485.                                     newfus, newindet, newnumbofposs ) );
  2486.           fi;
  2487.         fi;
  2488.       od;
  2489.     
  2490.       InfoCharTable2("#I FusionsAllowedByRestrictions: return from branch at",
  2491.                      " character\n",
  2492.                      "#I     ", CharString( chars[i], "" ),
  2493.                      " (", numbofposs[i], " calls)\n" );
  2494.     
  2495.     else
  2496.     
  2497.       # branch according to a significant class in a
  2498.       # character with minimal nontrivial indet.
  2499.       i:= Position( indeterminateness, Minimum( indeterminateness ) );
  2500.       restricted:= CompositionMaps( chars[i], fus );
  2501.       class:= 1;
  2502.       while not IsList( restricted[ class ] ) do class:= class + 1; od;
  2503.       InfoCharTable2( "#I FusionsAllowedByRestrictions: branch at class ",
  2504.                       class, "\n#I     (", Length( fus[ class ] ),
  2505.                       " calls)\n" );
  2506.       for j in fus[ class ] do
  2507.         newfus:= Copy( fus );
  2508.         newfus[ class ]:= j;
  2509.         newpow:= Copy( powermap );
  2510.         newsubpow:= Copy( subpowermap );
  2511.         if TestConsistencyMaps( subpowermap, newfus, tbl.powermap ) then
  2512.           newindet:= Copy( indeterminateness );
  2513.           newnumbofposs:= Copy( numbofposs );
  2514.           if improvefusion(chars,newfus,i,0,newindet,newnumbofposs) then
  2515.             Append( possibilities,
  2516.                     allowedfusions( newsubpow, newpow, chars,
  2517.                                     newfus, newindet, newnumbofposs ) );
  2518.           fi;
  2519.         fi;
  2520.       od;
  2521.       InfoCharTable2("#I FusionsAllowedByRestrictions: return from branch at",
  2522.                      " class ", class, "\n" );
  2523.     fi;
  2524.     return possibilities;
  2525.     end;
  2526.     
  2527.     # begin of the recursion:
  2528.     if lastimproved <> 0 then
  2529.       if not improvefusion( chars, fus, 1, lastimproved, indeterminateness,
  2530.                             numbofposs ) then
  2531.         return [];
  2532.       fi;
  2533.     fi;
  2534.     return allowedfusions( subtbl.powermap, tbl.powermap, chars, fus,
  2535.                            indeterminateness, numbofposs );
  2536.     end;
  2537.   
  2538.  
  2539. #############################################################################
  2540. ##
  2541. #F  'SubgroupFusions( <subtbl>, <tbl> )'
  2542. #F  'SubgroupFusions( <subtbl>, <tbl>, <parameters )'
  2543. ##
  2544. ##  returns the list of all subgroup fusion maps from <subtbl> into <tbl>.
  2545. ##  
  2546. ##  The optional record <parameters> may have the following fields\:
  2547. ##  
  2548. ##  'chars':\\
  2549. ##       a list of characters of <tbl> which will be restricted to <subtbl>,
  2550. ##       (see "FusionsAllowedByRestrictions");
  2551. ##       the default is '<tbl.irreducibles'
  2552. ##  
  2553. ##  'subchars':\\
  2554. ##       a list of characters of <subtbl> which are constituents of the
  2555. ##       retrictions of 'chars', the default is '<subtbl>.irreducibles'
  2556. ##  
  2557. ##  'fusionmap':\\
  2558. ##       a (parametrized) map which is an approximation of the desired map
  2559. ##  
  2560. ##  'decompose':\\
  2561. ##       a boolean; if 'true', the restrictions of 'chars' must have all
  2562. ##       constituents in 'subchars', that will be used in the algorithm;
  2563. ##       if 'subchars' is not bound and '<subtbl>.irreducibles' is complete,
  2564. ##       the default value of 'decompose' is 'true', otherwise 'false'
  2565. ##  
  2566. ##  'permchar':\\
  2567. ##       a permutaion character; only those fusions are computed which
  2568. ##       afford that permutation character
  2569. ##  
  2570. ##  'quick':\\
  2571. ##       a boolean; if 'true', the subroutines are called with the option
  2572. ##       '\"quick\"'; especially, a unique map will be returned immediately
  2573. ##       without checking all symmetrisations; the default value is 'false'
  2574. ##  
  2575. ##  'parameters':\\
  2576. ##       a record with fields 'maxamb', 'minamb' and 'maxlen' which control
  2577. ##       the subroutine 'FusionsAllowedByRestrictions'\:
  2578. ##       It only uses characters with actual indeterminateness up to
  2579. ##       'maxamb', tests decomposability only for characters with actual
  2580. ##       indeterminateness at least 'minamb' and admits a branch only
  2581. ##       according to a character if there is one with at most 'maxlen'
  2582. ##       possible restrictions.
  2583. ##
  2584. SubgroupFusions := function( arg )
  2585.     local x, i, subtbl, tbl, subchars, chars, fus, maxamb, minamb,
  2586.           maxlen, poss, subgroupfusions, imp, subtaut, taut, quick,
  2587.           decompose, approxfus, fusval, approxval, permchar, grp;
  2588.  
  2589.     if not ( Length( arg ) in [ 2, 3 ] and IsCharTable( arg[1] )
  2590.              and IsCharTable( arg[2] ) )
  2591.        or ( Length( arg ) = 3 and not IsRec( arg[3] ) ) then
  2592.       Error( "SubgroupFusions( <subtbl>, <tbl> )\n",
  2593.              " resp. SubgroupFusions( <subtbl>, <tbl>, <parameters> )" );
  2594.     fi;
  2595.     
  2596.     subtbl:= arg[1];
  2597.     tbl:= arg[2];
  2598.     
  2599.     if Length( arg ) = 3 then
  2600.       if IsBound( arg[3].subchars ) then
  2601.         subchars:= arg[3].subchars;
  2602.         decompose:= false;
  2603.       else
  2604.         if IsBound( subtbl.irreducibles ) then
  2605.           subchars:= subtbl.irreducibles;
  2606.           if Length( subchars ) = Length( subtbl.centralizers ) then
  2607.             decompose:= true;
  2608.           else
  2609.             decompose:= false;
  2610.           fi;
  2611.         else
  2612.           subchars:= [];
  2613.           decompose:= false;
  2614.         fi;
  2615.       fi;
  2616.       if IsBound( arg[3].chars ) then
  2617.         chars:= arg[3].chars;
  2618.       else
  2619.         if IsBound( tbl.irreducibles ) then
  2620.           chars:= tbl.irreducibles;
  2621.         else
  2622.           chars:= [];
  2623.         fi;
  2624.       fi;
  2625.       if IsBound( arg[3].quick ) and arg[3].quick = true then
  2626.         quick:= true;
  2627.       else
  2628.         quick:= false;
  2629.       fi;
  2630.       if IsBound( arg[3].decompose ) then
  2631.         if arg[3].decompose = true then
  2632.           decompose:= true;
  2633.         else
  2634.           decompose:= false;
  2635.         fi;
  2636.       fi;
  2637.       if IsBound( arg[3].parameters ) and IsRec( arg[3].parameters ) then
  2638.         maxamb:= arg[3].paramaters.maxamb;
  2639.         minamb:= arg[3].paramaters.minamb;
  2640.         maxlen:= arg[3].paramaters.maxlen;
  2641.       else
  2642.         maxamb:= 200000;
  2643.         minamb:= 10000;
  2644.         maxlen:= 10;
  2645.       fi;
  2646.       if IsBound( arg[3].fusionmap ) then
  2647.         approxfus:= arg[3].fusionmap;
  2648.       else
  2649.         approxfus:= [];
  2650.       fi;
  2651.     else
  2652.       decompose:= false;
  2653.       if IsBound( subtbl.irreducibles ) then
  2654.         subchars:= subtbl.irreducibles;
  2655.         if Length( subchars ) = Length( subtbl.centralizers ) then
  2656.           decompose:= true;
  2657.         fi;
  2658.       else
  2659.         subchars:= [];
  2660.       fi;
  2661.       if IsBound( tbl.irreducibles ) then
  2662.         chars:= tbl.irreducibles;
  2663.       else
  2664.         chars:= [];
  2665.       fi;
  2666.       quick:= false;
  2667.       approxfus:= [];
  2668.       maxamb:= 200000;
  2669.       minamb:= 10000;
  2670.       maxlen:= 10;
  2671.     fi;
  2672.     if Length( arg ) = 3 and IsBound( arg[3].permchar ) then
  2673.       permchar:= arg[3].permchar;
  2674.       if Length( permchar ) <> Length( tbl.centralizers ) then
  2675.         Error( "<permchar> must have same length as <tbl>.centralizers" );
  2676.       fi;
  2677.     else
  2678.       permchar:= [];
  2679.     fi;
  2680.  
  2681.     # initialize the fusion
  2682.     fus:= InitFusion( subtbl, tbl );
  2683.     if fus = false then 
  2684.       InfoCharTable2( "#E SubgroupFusions: no initialisation possible\n" );
  2685.       return [];
  2686.     fi;
  2687.     InfoCharTable2( "#I SubgroupFusions: fusion initialized\n" );
  2688.     
  2689.     # use 'approxfus'\:
  2690.     for i in [ 1 .. Minimum( Length( approxfus ), Length( fus ) ) ] do
  2691.       if IsBound( approxfus[i] ) then
  2692.         if IsInt( approxfus[i] ) then
  2693.           approxval:= [ approxfus[i] ];
  2694.         else
  2695.           approxval:= approxfus[i];
  2696.         fi;
  2697.         if IsInt( fus[i] ) then
  2698.           fusval:= [ fus[i] ];
  2699.         else
  2700.           fusval:= fus[i];
  2701.         fi;
  2702.         fusval:= Intersection( approxval, fusval );
  2703.         if fusval = [] then
  2704.           Print( "#I SubgroupFusions: possible maps not compatible with ",
  2705.                  "<approxfus> at class ", i, "\n" );
  2706.           return [];
  2707.         elif Length( fusval ) = 1 then
  2708.           fus[i]:= fusval[1];
  2709.         else
  2710.           fus[i]:= fusval;
  2711.         fi;
  2712.       fi;
  2713.     od;
  2714.  
  2715.     # use the permutation character for the first time
  2716.     if not CheckPermChar( subtbl, tbl, fus, permchar ) then
  2717.       InfoCharTable2( "#E SubgroupFusions:",
  2718.                       " inconsistency of fusion and permchar\n" );
  2719.       return [];
  2720.     fi;
  2721.     if permchar <> [] then
  2722.       InfoCharTable2("#I SubgroupFusions: permutation character checked\n");
  2723.     fi;
  2724.  
  2725.     # check consistency of fusion and powermaps
  2726.     if not TestConsistencyMaps( subtbl.powermap, fus, tbl.powermap ) then
  2727.       InfoCharTable2( "#E SubgroupFusions:",
  2728.                       " inconsistency of fusion and powermaps\n" );
  2729.       return [];
  2730.     fi;
  2731.     InfoCharTable2( "#I SubgroupFusions: consistency with powermaps",
  2732.                     " checked,\n#I    the actual indeterminateness is ",
  2733.                     Indeterminateness( fus ), "\n" );
  2734.  
  2735.     # may we return?
  2736.     if quick and ForAll( fus, IsInt ) then return [ fus ]; fi;
  2737.     
  2738.     # consider table automorphisms of the supergroup:
  2739.     if IsBound( tbl.automorphisms ) then
  2740.       imp:= ConsiderTableAutomorphisms( fus, tbl.automorphisms );
  2741.       if InfoCharTable2 <> Ignore then
  2742.         Print( "#I SubgroupFusions: table automorphisms checked, " );
  2743.         if imp = [] then
  2744.           Print( "no improvements\n" );
  2745.         else
  2746.           Print( "improvements at classes\n#I   ", imp, "\n" );
  2747.           if not TestConsistencyMaps(subtbl.powermap,fus,tbl.powermap,imp)
  2748.                                                                        then
  2749.             InfoCharTable2( "#I SubgroupFusions: inconsistency of",
  2750.                             " powermaps and fusion map\n" );
  2751.             return [];
  2752.           fi;
  2753.           InfoCharTable2( "#I SubgroupFusions: consistency with powermaps ",
  2754.                           "checked again,\n",
  2755.                           "#I    the actual indeterminateness is ",
  2756.                           Indeterminateness( fus ), "\n" );
  2757.         fi;
  2758.       fi;
  2759.     else
  2760.       InfoCharTable2("#I SubgroupFusions: no table automorphisms stored\n");
  2761.     fi;
  2762.  
  2763.     # use the permutation character for the second time
  2764.     if not CheckPermChar( subtbl, tbl, fus, permchar ) then
  2765.       InfoCharTable2( "#E SubgroupFusions:",
  2766.                       " inconsistency of fusion and permchar\n" );
  2767.       return [];
  2768.     fi;
  2769.     if permchar <> [] then
  2770.       InfoCharTable2( "#I SubgroupFusions: permutation character checked",
  2771.                       " again\n");
  2772.     fi;
  2773.     
  2774.     if quick and ForAll( fus, IsInt ) then return [ fus ]; fi;
  2775.     
  2776.     # now use restricted characters:
  2777.     # If the parameter \"decompose\" was entered, use decompositions of
  2778.     # indirections of <chars> into <subchars>;
  2779.     # otherwise only check the scalar products with <subchars>.
  2780.     
  2781.     if decompose then                      # usage of decompositions allowed
  2782.       if Indeterminateness( fus ) < minamb then
  2783.         InfoCharTable2( "#I SubgroupFusions: indeterminateness too small",
  2784.                         " for test of decomposability\n" );
  2785.         poss:= [ fus ];
  2786.       else
  2787.         InfoCharTable2( "#I SubgroupFusions: now test decomposability of",
  2788.                         " rational restrictions\n" );
  2789.         poss:= FusionsAllowedByRestrictions( subtbl, tbl,
  2790.                       RationalizedMat( subchars ),
  2791.                       RationalizedMat( chars ), fus,
  2792.                       rec( maxlen:= maxlen,
  2793.                            contained:= ContainedCharacters,
  2794.                            minamb:= minamb,
  2795.                            maxamb:= "infinity",
  2796.                            quick:= quick ) );
  2797.  
  2798.         # use the permutation character for the third time
  2799.         poss:= Filtered( poss, x -> CheckPermChar(subtbl,tbl,x,permchar) );
  2800.     
  2801.         if InfoCharTable2 = Print then
  2802.           Print( "#I SubgroupFusions: decomposability tested,\n" );
  2803.           if Length( poss ) = 1 then
  2804.             Print( "#I    1 solution with indeterminateness ",
  2805.                    Indeterminateness( poss[1] ), "\n" );
  2806.           else
  2807.             Print( "#I    ", Length( poss ),
  2808.                    " solutions with indeterminateness\n#I    ",
  2809.                     List( poss, Indeterminateness ), "\n" );
  2810.           fi;
  2811.         fi;
  2812.       fi;
  2813.  
  2814.     else
  2815.       InfoCharTable2( "#I SubgroupFusions: no test of decomposability\n" );
  2816.       poss:= [ fus ];
  2817.     fi;
  2818.     
  2819.     InfoCharTable2( "#I SubgroupFusions: test scalar products",
  2820.                     " of restrictions\n" );
  2821.     
  2822.     subgroupfusions:= [];
  2823.     for fus in poss do
  2824.       Append( subgroupfusions,
  2825.               FusionsAllowedByRestrictions( subtbl, tbl, subchars, chars,
  2826.                         fus, rec( maxlen:= maxlen,
  2827.                                   contained:= ContainedPossibleCharacters,
  2828.                                   minamb:= 1,
  2829.                                   maxamb:= maxamb,
  2830.                                   quick:= quick ) ) );
  2831.     od;
  2832.  
  2833.     #  make orbits under the admissible subgroup of 'tbl.automorphisms'
  2834.     #  to get the whole set of all subgroup fusions;
  2835.     #  admissible means\:\  If there was an approximation 'fusionmap' in
  2836.     #  the argument record, this map must be respected; if the permutation
  2837.     #  character 'permchar' was entered, it must be respected, too.
  2838.  
  2839.     if IsBound( tbl.automorphisms ) then
  2840.       if permchar = [] then
  2841.         grp:= tbl.automorphisms;
  2842.       else
  2843.  
  2844.         # use the permutation character for the fourth time
  2845.         grp:= tbl.automorphisms.operations.SubgroupProperty(
  2846.                    tbl.automorphisms, x->ForAll([1..Length(permchar)],
  2847.                                           y->permchar[y]=permchar[y^x]) );
  2848.       fi;
  2849.       subgroupfusions:= Set( Concatenation( List( subgroupfusions,
  2850.                                 x->OrbitFusions( Group(()), x, grp ) ) ) );
  2851.     fi;
  2852.  
  2853.     if approxfus <> [] then
  2854.       subgroupfusions:= Filtered( subgroupfusions,
  2855.           x -> ForAll( [ 1 .. Length( approxfus ) ],
  2856.                  y -> not IsBound( approxfus[y] )
  2857.                        or ( IsInt(approxfus[y]) and x[y] =  approxfus[y] )
  2858.                        or ( IsList(approxfus[y]) and IsInt( x[y] )
  2859.                             and x[y] in approxfus[y] )
  2860.                        or ( IsList(approxfus[y]) and IsList( x[y] )
  2861.                             and Difference( x[y], approxfus[y] ) = [] )));
  2862.     fi;
  2863.  
  2864.     if InfoCharTable2 <> Ignore then
  2865.       # make orbits under the groups of table automorphisms
  2866.       if IsBound( subtbl.automorphisms ) then
  2867.         subtaut:= subtbl.automorphisms;
  2868.       else
  2869.         subtaut:= Group( () );
  2870.       fi;
  2871.       if IsBound( tbl.automorphisms ) then
  2872.         taut:= tbl.automorphisms;
  2873.       else
  2874.         taut:= Group( () );
  2875.       fi;
  2876.       RepresentativesFusions( subtaut, subgroupfusions, taut );
  2877.       if ForAny( subgroupfusions, x -> ForAny( x, IsList ) ) then
  2878.         Print( "#I SubgroupFusions: ", Length( subgroupfusions ),
  2879.                " parametrized solution" );
  2880.         if Length( subgroupfusions ) = 1 then
  2881.           Print( ",\n" );
  2882.         else
  2883.           Print( "s,\n" );
  2884.         fi;
  2885.         Print( "#I    no further improvement was possible with",
  2886.                " given characters\n",
  2887.                "#I    and maximal checked ambiguity of ", maxamb, "\n" );
  2888.       else
  2889.         Print( "#I SubgroupFusions: ", Length( subgroupfusions ),
  2890.                " solution" );
  2891.         if Length( subgroupfusions ) = 1 then
  2892.           Print( "\n" );
  2893.         else
  2894.           Print( "s\n" );
  2895.         fi;
  2896.       fi;
  2897.     fi;
  2898.     return subgroupfusions;
  2899.     end;
  2900.  
  2901.  
  2902.