home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / ctmapusi.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  33.1 KB  |  968 lines
  1. #############################################################################
  2. ##
  3. #A  ctmapusi.g                  GAP library                     Thomas Breuer
  4. ##
  5. #A  @(#)$Id: ctmapusi.g,v 3.19 1993/02/11 11:14:58 sam Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains  those  functions  that  mainly  deal  with maps.
  10. ##
  11. #H  $Log: ctmapusi.g,v $
  12. #H  Revision 3.19  1993/02/11  11:14:58  sam
  13. #H  change in 'Parametrized', due to new string handling
  14. #H
  15. #H  Revision 3.18  1992/07/31  10:28:53  sam
  16. #H  'Indicator' does now work also for Brauer tables
  17. #H
  18. #H  Revision 3.17  1992/07/03  08:00:17  sam
  19. #H  another change in 'StoreFusion'
  20. #H
  21. #H  Revision 3.16  1992/06/17  09:48:19  sam
  22. #H  changed 'StoreFusion'
  23. #H
  24. #H  Revision 3.15  1992/02/06  11:44:48  sam
  25. #H  changed 'GetFusionMap': now fusions between Brauer tables are allowed
  26. #H
  27. #H  Revision 3.14  1992/01/07  15:01:24  sam
  28. #H  removed use of 'Function'
  29. #H
  30. #H  Revision 3.13  1991/12/20  10:08:55  sam
  31. #H  renamed 'Projection' to 'ProjectionMap'
  32. #H
  33. #H  Revision 3.12  1991/12/13  13:15:55  sam
  34. #H  replaced 'IsPrime' by 'IsPrimeInt'
  35. #H
  36. #H  Revision 3.11  1991/12/05  11:53:57  sam
  37. #H  correction concerning fusionsource
  38. #H
  39. #H  Revision 3.10  1991/12/05  08:38:03  sam
  40. #H  changed 'Add' in 'StoreFusion' to 'AddSet'
  41. #H
  42. #H  Revision 3.9  1991/12/04  17:21:58  sam
  43. #H  changed 'CASPER' in header to 'GAP'
  44. #H
  45. #H  Revision 3.8  1991/12/03  09:05:12  sam
  46. #H  functions indented
  47. #H
  48. #H  Revision 3.7  1991/10/24  08:41:51  sam
  49. #H  bug in ElementOrdersPowermap
  50. #H
  51. #H  Revision 3.6  1991/10/10  10:06:44  sam
  52. #H  little bug in 'ElementOrdersPowermap' fixed
  53. #H
  54. #H  Revision 3.5  1991/10/07  15:41:46  sam
  55. #H  changed 'ScalarProduct' to '<tbl>.operations.ScalarProduct'
  56. #H
  57. #H  Revision 3.4  1991/10/07  13:40:11  casper
  58. #H  added function 'ElementOrdersPowermap'
  59. #H
  60. #H  Revision 3.3  1991/10/01  09:37:14  sam
  61. #H  two lines killed
  62. #H
  63. #H  Revision 3.2  1991/10/01  09:19:46  sam
  64. #H  changed 'VERBOSE' to 'InfoCharTable2'
  65. #H
  66. #H  Revision 3.1  1991/09/03  15:11:07  goetz
  67. #H  changed 'reps' to 'orders'.
  68. #H
  69. #H  Revision 3.0  1991/09/03  14:21:39  goetz
  70. #H  Initial Revision.
  71. #H
  72. ##
  73.  
  74.  
  75. #############################################################################
  76. ##
  77. #F  InfoCharTable1( ... ) . . . info function for the character table package
  78. #F  InfoCharTable2( ... ) . . . info function for the character table package
  79. ##
  80.     if not IsBound( InfoCharTable1 )  then InfoCharTable1 := Ignore;  fi;
  81.     if not IsBound( InfoCharTable2 )  then InfoCharTable2 := Ignore;  fi;
  82.  
  83.  
  84. #############################################################################
  85. ##
  86. #F  InverseMap( <paramap> )  . . . . . . . . .  Inverse of a parametrized map
  87. ##
  88. ##  'InverseMap( <paramap> )[i]' is the unique preimage or the set of all
  89. ##  preimages of 'i' under <paramap>, if there are any; otherwise it is unbound.
  90. ##
  91. ##  We have 'CompositionMaps( <paramap>, InverseMap( <paramap> ) )'
  92. ##  the identity map.
  93. ##
  94. InverseMap := function( paramap )
  95.     local i, inversemap, im;
  96.     inversemap:= [];
  97.     for i in [ 1 .. Length( paramap ) ] do
  98.       if IsSet( paramap[i] ) then
  99.         for im in paramap[i] do
  100.           if IsBound( inversemap[ im ] ) then
  101.             AddSet( inversemap[ im ], i );
  102.           else
  103.             inversemap[ im ]:= [ i ];
  104.           fi;
  105.         od;
  106.       else
  107.         if IsBound( inversemap[ paramap[i] ] ) then
  108.           AddSet( inversemap[ paramap[i] ], i );
  109.         else
  110.           inversemap[ paramap[i] ]:= [ i ];
  111.         fi;
  112.       fi;
  113.     od;
  114.     for i in [ 1 .. Length( inversemap ) ] do
  115.       if IsBound( inversemap[i] ) and Length( inversemap[i] ) = 1 then
  116.         inversemap[i]:= inversemap[i][1];
  117.       fi;
  118.     od;
  119.     return inversemap;
  120.     end;
  121.  
  122.  
  123. #############################################################################
  124. ##
  125. #F  CompositionMaps( <paramap2>, <paramap1> )
  126. #F  CompositionMaps( <paramap2>, <paramap1>, <class> )
  127. ##
  128. ##  'CompositionMaps( <paramap2>, <paramap1> )' is a parametrized map with
  129. ##  image 'CompositionMaps( <paramap2>, <paramap1>, <class> )' at position
  130. ##  <class>. If '<paramap1>[<class>]' is unique,
  131. ##  'CompositionMaps( <paramap2>, <paramap1>, <class> ) =
  132. ##  <paramap2>[ <paramap1>[ <class> ] ]', otherwise it is the union of
  133. ##  '<paramap2>[i]' for 'i' in '<paramap1>[ <class> ]'.
  134. ##
  135. CompositionMaps := function( arg )
  136.     local i, j, k, x, map1, map2, class, result, map1_class, newelement;
  137.     if Length(arg) = 2 and IsList(arg[1]) and IsList(arg[2]) then
  138.       map2:= arg[1];
  139.       map1:= arg[2];
  140.       result:= [];
  141.       for i in [ 1 .. Length( map1 ) ] do
  142.         if IsBound( map1[i] ) then
  143.           result[i]:= CompositionMaps( map2, map1, i );
  144.         fi;
  145.       od;
  146.       return result;
  147.     elif Length( arg ) = 3
  148.          and IsList( arg[1] ) and IsList( arg[2] ) and IsInt( arg[3] ) then
  149.       map2:= arg[1];
  150.       map1:= arg[2];
  151.       class:= arg[3];
  152.       if IsInt( map1[ class ] ) then
  153.         return map2[ map1[ class ] ];
  154.       else
  155.         map1_class:= map1[ class ];
  156.         result:= [];
  157.         for j in map1_class do
  158.           newelement:= map2[j];
  159.           if IsSet( newelement ) then
  160.             result:= Union( result, newelement );
  161.           else                              # may be "int" or "string",
  162.             AddSet( result, newelement );   # but is unique
  163.           fi;
  164.         od;
  165.         if Length( result ) = 1 then result:= result[1]; fi;
  166.         return result;
  167.       fi;
  168.     else
  169.       Error(" usage: CompositionMaps( <map2>, <map1>, <class> ) resp.\n",
  170.             "        CompositionMaps( <map2>, <map1> )" );
  171.     fi;
  172.     end;
  173.  
  174.  
  175. #############################################################################
  176. ##
  177. #F  ProjectionMap( <fusionmap> ) . . projection corresponding to a fusion map
  178. ##
  179. ##  We have 'CompositionMaps( <fusionmap>,ProjectionMap( <fusionmap> ) )' the
  180. ##  identity map, i.e. first projecting and then fusing yields the identity.
  181. ##  Note that <fusionmap> must not be a parametrized map.
  182. ##
  183. ProjectionMap := function( fusionmap )
  184.     local i, projection;
  185.     projection:= [];
  186.     for i in Reversed( [ 1 .. Length( fusionmap ) ] ) do
  187.       projection[ fusionmap[i] ]:= i;
  188.     od;
  189.     return projection;
  190.     end;
  191.  
  192.  
  193. #############################################################################
  194. ##
  195. #F  Indeterminateness( <paramap> ) . . . . the indeterminateness of a paramap
  196. ##
  197. Indeterminateness := function( paramap )
  198.     return Product( paramap, function(x)
  199.                              if IsList(x) then return Length(x);
  200.                              else return 1; fi; end );
  201.     end;
  202.  
  203.  
  204. #############################################################################
  205. ##
  206. #F  PrintAmbiguity( <list>, <paramap> ) . . . .  ambiguity of characters with
  207. ##                                                       respect to a paramap
  208. ##
  209. ##  prints for each character in <list> the position, the indeterminateness
  210. ##  with respect to <paramap> and the list of ambiguous classes
  211. ##
  212. PrintAmbiguity := function( list, paramap )
  213.     local i, j, composition, classes;
  214.     for i in [ 1 .. Length( list ) ] do
  215.       composition:= CompositionMaps( list[i], paramap );
  216.       Print( i, " ", Indeterminateness( composition ), " " );
  217.       classes:= [];
  218.       for j in [ 1 .. Length( composition ) ] do
  219.         if IsList( composition[j] ) then Add( classes, j ); fi;
  220.       od;
  221.       Print( classes, "\n" );
  222.     od;
  223.     end;
  224.  
  225.  
  226. #############################################################################
  227. ##
  228. #F  Parametrized( <list> )
  229. ##
  230. ##  returns the smallest parametrized map containing all elements of <list>.
  231. ##  These elements may be maps or parametrized maps.
  232. ##
  233. Parametrized := function( list )
  234.     local i, j, parametrized;
  235.     if list = [] then return []; fi;
  236.     parametrized:= [];
  237.     for i in [ 1 .. Length( list[1] ) ] do
  238.       if ( IsList( list[1][i] ) and not IsString( list[1][i] ) ) 
  239.          or list[1][i] = [] then
  240.         parametrized[i]:= list[1][i];
  241.       else
  242.         parametrized[i]:= [ list[1][i] ];
  243.       fi;
  244.     od;
  245.     for i in [ 2 .. Length( list ) ] do
  246.       for j in [ 1 .. Length( list[i] ) ] do
  247.         if ( IsList( list[i][j] ) and not IsString( list[i][j] ) ) 
  248.            or list[i][j] = [] then
  249.           parametrized[j]:= Union( parametrized[j], list[i][j] );
  250.         else
  251.           AddSet( parametrized[j], list[i][j] );
  252.         fi;
  253.       od;
  254.     od;
  255.     for i in [ 1 .. Length( list[1] ) ] do
  256.       if Length( parametrized[i] ) = 1 then
  257.         parametrized[i]:= parametrized[i][1];
  258.       fi;
  259.     od;
  260.     return parametrized;
  261.     end;
  262.  
  263.  
  264. #############################################################################
  265. ##
  266. #F  ContainedMaps( <paramap> )
  267. ##
  268. ##  returns the set of all contained maps of <paramap>
  269. ##
  270. ContainedMaps := function( paramap )
  271.     local i, j, containedmaps, copy;
  272.     i:= 1;
  273.     while i <= Length( paramap ) and not IsList( paramap[i] ) do i:= i+1; od;
  274.     if i > Length( paramap ) then
  275.       return [ Copy( paramap ) ];
  276.     else
  277.       containedmaps:= [];
  278.       copy:= ShallowCopy( paramap );
  279.       for j in paramap[i] do
  280.         copy[i]:= j;
  281.         Append( containedmaps, ContainedMaps( copy ) );
  282.       od;
  283.       return containedmaps;
  284.     fi;
  285.     end;
  286.  
  287.  
  288. #############################################################################
  289. ##
  290. #F  Indirected( <character>, <paramap> )
  291. ##
  292. ##  'Indirected( <character>, <paramap> )[i]' = <character>[ <paramap>[i] ]',
  293. ##  if this value is unique; otherwise it is set undefined.
  294. ##  
  295. Indirected := function( character, paramap )
  296.     local i, j, imagelist, indirected;
  297.     indirected:= [];
  298.     for i in [ 1 .. Length( paramap ) ] do
  299.       if IsInt( paramap[i] ) then
  300.         indirected[i]:= character[ paramap[i] ];
  301.       else
  302.         imagelist:= [];
  303.         for j in paramap[i] do AddSet( imagelist, character[j] ); od;
  304.         if Length( imagelist ) = 1 then  #  unique
  305.           indirected[i]:= imagelist[1];
  306.         else
  307.           indirected[i]:= Unknown();
  308.         fi;
  309.       fi;
  310.     od;
  311.     return indirected;
  312.     end;
  313.  
  314.  
  315. #############################################################################
  316. ##
  317. #F  GetFusionMap( <source>, <destination> )
  318. #F  GetFusionMap( <source>, <destination>, <specification> )
  319. ##
  320. ##  For ordinary character tables <source> and <destination>,
  321. ##  'GetFusionMap( <source>, <destination> )' returns the 'map' field of the
  322. ##  fusion stored on the table <source> that has the 'name' field
  323. ##  <destination>, and
  324. ##  'GetFusionMap( <source>, <destination>, <specification> )' gets that
  325. ##  fusion that additionally has the 'specification' field <specification>.
  326. ##  Both versions adjust the ordering of classes of <destination> using
  327. ##  '<destination>.permutation'.
  328. ##
  329. ##  If both <source> and <destination> are Brauer tables, i.e., they have
  330. ##  a record component 'ordinary' which is the corresponding ordinary
  331. ##  table, 'GetFusionMap' returns the fusion map corresponding to that
  332. ##  between the ordinary tables.
  333. ##
  334. ##  If no appropriate fusion could be found, 'false' is returned.
  335. ##
  336. GetFusionMap := function( arg )
  337.     local i, fus, name, permutation;
  338.     if Length(arg) < 2 or Length(arg) > 3 
  339.        or not ( IsCharTable( arg[1] ) and IsCharTable( arg[2] ) ) then
  340.       Error("usage: GetFusionMap( <source>, <destination> ) resp.\n",
  341.             "       GetFusionMap( <source>,<destination>,<specification> )");
  342.     fi;
  343.  
  344.     # fusion between Brauer tables
  345.     if IsBound( arg[1].ordinary ) and IsBound( arg[2].ordinary ) then
  346.       if Length( arg ) = 2 then
  347.         fus:= GetFusionMap( arg[1].ordinary, arg[2].ordinary );
  348.       else
  349.         fus:= GetFusionMap( arg[1].ordinary, arg[2].ordinary, arg[3] );
  350.       fi;
  351.       return
  352.         CompositionMaps( InverseMap(GetFusionMap(arg[2],arg[2].ordinary)),
  353.                       CompositionMaps(fus,
  354.                                     GetFusionMap(arg[1],arg[1].ordinary)) );
  355.     fi;
  356.  
  357.     # fusion between ordinary tables or from Brauer table in ordinary table
  358.     if not IsBound( arg[1].fusions ) then return false; fi;
  359.     name:= arg[2].name;
  360.     if IsBound( arg[2].permutation ) then
  361.       permutation:= arg[2].permutation;
  362.     else
  363.       permutation:= ();
  364.     fi;
  365.     for fus in arg[1].fusions do
  366.       if fus.name = name then
  367.         if Length( arg ) = 2 then
  368.           if IsBound( fus.specification ) then
  369.             Print( "#I GetFusionMap: Used fusion has specification ",
  370.                      fus.specification, "\n");
  371.           fi;
  372.           return List( fus.map, function(x)
  373.                                  if IsInt(x) then return x^permutation;
  374.                                  else return List( x, y -> y^permutation );
  375.                                  fi; end );
  376.         elif arg[3] = fus.specification then
  377.           return List( fus.map, function(x)
  378.                                   if IsInt(x) then return x^permutation;
  379.                                   else return List( x, y -> y^permutation );
  380.                                   fi; end );
  381.         fi;
  382.       fi;
  383.     od;
  384.     return false;
  385.     end;
  386.  
  387.  
  388. #############################################################################
  389. ##
  390. #F  StoreFusion( <source>, <destination>, <fusion> )
  391. #F  StoreFusion( <source>, <destination>, <fusionmap> )
  392. ##
  393. ##  The record <fusion> is stored on <source> if no ambiguity arises.
  394. ##  The 'map' field of <fusion> is rejusted by '<destination>.permutation'.
  395. ##  '<source>.name' is added to '<destination>.fusionsource'.
  396. ##
  397. ##  If a list <fusionmap> is entered, the same holds for
  398. ##  '<fusion> = rec( map:= <fusionmap> )'.
  399. ##
  400. StoreFusion := function( source, destination, fusion )
  401.     local fus;
  402.     if not ( IsList(fusion) or ( IsRec(fusion) and IsBound(fusion.map) ) )
  403.        then
  404.       Error( "<fusion> must be a list or a record containing at least",
  405.              " <fusion>.map" );
  406.     fi;
  407.     if not IsBound( destination.name ) or
  408.        ( IsRec( fusion ) and IsBound( fusion.name ) and
  409.          fusion.name <> destination.name ) then
  410.       Error("<destination> must have a name; will be equal to <fusion>.name");
  411.     fi;
  412.     if IsList( fusion ) then
  413.       fusion:= rec( name:= destination.name, map:= fusion );
  414.     else
  415.       fusion.name:= destination.name;
  416.     fi;
  417.  
  418.     if IsBound( destination.permutation ) then
  419.       fusion.map:= List( fusion.map, x -> x/destination.permutation );
  420.     fi;
  421.  
  422.     if not IsBound( source.fusions ) then source.fusions:= []; fi;
  423.     if not IsBound( destination.fusionsource ) then
  424.       destination.fusionsource:= [ source.name ];
  425.     else
  426.       destination.fusionsource:= Union( destination.fusionsource,
  427.                                         [ source.name ] );
  428.     fi;
  429.  
  430.     for fus in source.fusions do
  431.       if fus.name = fusion.name and fus.map <> fusion.map
  432.          and ( not IsBound(fusion.specification)
  433.                or ( IsBound( fus.specification )
  434.                     and fusion.specification = fus.specification ) ) then
  435.  
  436.         # fusion to same destination, with different map,
  437.         # not specified
  438.         Error( "fusion to <destination> stored on <source> yet;\n",
  439.                " to store another one, assign different specifications",
  440.                " to both fusions" );
  441.       elif fus.name = fusion.name and fus.map = fusion.map then
  442.  
  443.         # simply replace the old fusion
  444.         source.fusions[ Position( source.fusions, fus ) ]:= fusion;
  445.         return;
  446.       fi;
  447.     od;
  448.  
  449.     # new fusion
  450.     Add( source.fusions, fusion );
  451.     end;
  452.  
  453.  
  454. #############################################################################
  455. ##
  456. #F  'ElementOrdersPowermap( <powermap> )'
  457. ##
  458. ##  returns the list of element orders given by the maps in the powermap
  459. ##  <powermap>.
  460. ##  The entries at positions where the powermaps do not uniquely determine
  461. ##  the element orders are set to an unknown.
  462. ##
  463. ElementOrdersPowermap := function( powermap )
  464.     local i, primes, elementorders, nccl, bound, newbound, map, pos;
  465.  
  466.     if powermap = [] then Error( "no powermaps bound" ); fi;
  467.  
  468.     primes:= Filtered( [ 1 .. Length( powermap ) ],
  469.                        x -> IsBound( powermap[x] ) );
  470.     nccl:= Length( powermap[ primes[1] ] );
  471.  
  472.     if InfoCharTable2 <> Ignore then
  473.       for i in primes do
  474.         if ForAny( powermap[i], IsList ) then
  475.           InfoCharTable2( "#I ElementOrdersPowermap: ", Ordinal( i ),
  476.                           " powermap not unique at classes\n",
  477.                           "#I ", Filtered( [ 1 .. nccl ],
  478.                                            x -> IsList( powermap[i][x] ) ),
  479.                           " (ignoring these entries)\n" );
  480.         fi;
  481.       od;
  482.     fi;
  483.      
  484.     elementorders:= [ 1 ];
  485.     bound:= [ 1 ];
  486.  
  487.     while bound <> [] do
  488.       newbound:= [];
  489.       for i in primes do
  490.         map:= powermap[i];
  491.         for pos in [ 1 .. nccl ] do
  492.           if IsInt( map[ pos ] ) and map[ pos ] in bound
  493.              and IsBound( elementorders[ map[ pos ] ] )
  494.              and not IsBound( elementorders[ pos ] ) then
  495.             elementorders[ pos ]:= i * elementorders[ map[ pos ] ];
  496.             AddSet( newbound, pos );
  497.           fi;
  498.         od;
  499.       od;
  500.       bound:= newbound;
  501.     od;
  502.     for i in [ 1 .. nccl ] do
  503.       if not IsBound( elementorders[i] ) then
  504.         elementorders[i]:= Unknown();
  505.       fi;
  506.     od;
  507.     if InfoCharTable2 = Print and ForAny( elementorders, IsUnknown ) then
  508.       Print( "#I ElementOrdersPowermap: element orders not determined for",
  509.              " classes in\n",
  510.              "#I ", Filtered( [ 1 .. nccl ],
  511.                               x-> IsUnknown( elementorders[x] ) ), "\n" );
  512.     fi;
  513.     return elementorders;
  514.     end;
  515.  
  516.  
  517. #############################################################################
  518. ##
  519. #F  Restricted( <tbl>, <subtbl>, <chars> )
  520. #F  Restricted( <tbl>, <subtbl>, <chars>, <specification> )
  521. #F  Restricted( <chars>, <fusionmap> )
  522. ##
  523. ##  'Restricted()' returns the indirections of <chars> from <tbl>
  524. ##  to <subtbl> by a fusion map.
  525. ##  This map can either be entered directly, or it is stored on the table
  526. ##  <source>; in the latter case the value of the 'specification' field may
  527. ##  be specified.
  528. ##
  529. Restricted := function( arg )
  530.     local x, fusion, chars;
  531.     if Length( arg ) = 2 and IsList( arg[1] ) and IsList( arg[2] ) then
  532.       chars:= arg[1];
  533.       fusion:= arg[2];
  534.     elif IsCharTable( arg[1] ) and IsCharTable( arg[2] ) and
  535.          Length( arg ) in [ 3, 4 ] and IsList( arg[3] ) then
  536.       chars:= arg[3];
  537.       if Length( arg ) = 3 then  
  538.         fusion:= GetFusionMap( arg[2], arg[1] );
  539.       else
  540.         fusion:= GetFusionMap( arg[2], arg[1], arg[4] );
  541.       fi;
  542.       if fusion = false then return false; fi;
  543.     else
  544.       Error( "usage: Restricted( <tbl>, <subtbl>, <chars> )\n",
  545.           "resp. Restricted( <tbl>, <subtbl>, <chars>, <specification> )\n",
  546.           "resp. Restricted( <chars>, <fusionmap> )" );
  547.     fi;
  548.     return List( chars, x -> Indirected( x, fusion ) );
  549.     end;
  550.  
  551.  
  552. #############################################################################
  553. ##
  554. #F  Inflated( <source>, <destination>, <chars> )
  555. #F  Inflated( <source>, <destination>, <chars>, <specification> )
  556. #F  Inflated( <chars>, <fusionmap> )
  557. ##
  558. Inflated := Restricted;
  559.  
  560.  
  561. #############################################################################
  562. ##
  563. #F  Induced( <subgroup>, <group>, <chars> )
  564. #F  Induced( <subgroup>, <group>, <chars>, <specification> )
  565. #F  Induced( <subgroup>, <group>, <chars>, <fusionmap> )
  566. ##
  567. ##  'Induced()' induces <chars> from <subgroup> to <group>. The fusion
  568. ##  map can either be entered directly as <fusionmap>, or it must be stored
  569. ##  on the table <subgroup>; in the latter case the value of the
  570. ##  'specification' field may be specified.
  571. ##
  572. ##  Note that <specification> must not be a list!
  573. ##
  574. Induced := function( arg )
  575.     local i, j, im, fusion, centralizers, nccl, suborder, subclasses,
  576.           subnccl, chars, induced, singleinduced, char;
  577.     if not ( Length(arg) in [ 3, 4 ]
  578.              and IsCharTable( arg[1] ) and IsCharTable( arg[2] )
  579.              and IsList( arg[3] ) ) then
  580.       Error("usage: Induced( <subgroup>, <group>, <chars> )\n",
  581.            "resp. Induced( <subgroup>, <group>, <chars>, <specification> )\n",
  582.            "resp. Induced( <subgroup>, <group>, <chars>, <fusionmap> )");
  583.     fi;
  584.     if Length( arg ) = 3 then
  585.       fusion:= GetFusionMap( arg[1], arg[2] );
  586.     elif IsList( arg[4] ) then
  587.       fusion:= arg[4];
  588.     else
  589.       fusion:= GetFusionMap( arg[1], arg[2], arg[4] );
  590.     fi;
  591.     if fusion = false then return false; fi;
  592.     centralizers:= arg[2].centralizers;           # group.centralizers
  593.     nccl:= Length( centralizers );
  594.     suborder:= arg[1].order;                      # subgroup.order
  595.     subclasses:= arg[1].classes;                  # subgroup.classes
  596.     subnccl:= Length( subclasses );
  597.     chars:= arg[3];
  598.     induced:= [];
  599.     for char in chars do
  600.       singleinduced:= [];                  # shall contain the induced char
  601.       for j in [ 1 .. nccl ] do singleinduced[j]:= 0; od;
  602.       for j in [ 1 .. subnccl ] do
  603.         if char[j] <> 0 then
  604.           if IsInt( fusion[j] ) then
  605.             singleinduced[ fusion[j] ]:= singleinduced[ fusion[j] ]
  606.                                      + char[j] * subclasses[j];
  607.           else
  608.             for im in fusion[j] do singleinduced[ im ]:= Unknown(); od;
  609.           fi;
  610.         fi;
  611.       od;
  612.       for j in [ 1 .. nccl ] do
  613.         singleinduced[j]:= singleinduced[j] * centralizers[j] / suborder;
  614.         if not IsCycInt( singleinduced[j] ) then
  615.           singleinduced[j]:= Unknown();
  616.           Print("#I Induced: subgroup order not dividing sum in character ");
  617.           Print( Length( induced ) + 1, " at class ", j, "\n" );
  618.         fi;
  619.       od;
  620.       Add( induced, singleinduced );
  621.     od;
  622.     return induced;
  623.     end;
  624.  
  625.  
  626. #############################################################################
  627. ##
  628. #F  CollapsedMat( <mat>, <maps> )
  629. ##
  630. ##  returns a record with fields 'mat' and 'fusion'; 
  631. ##  the 'fusion' field contains the fusion that collapses the columns of
  632. ##  <mat> that are identical also for all maps in the list <maps>, the
  633. ##  'mat' field contains the image of <mat> under that fusion.
  634. ##
  635. CollapsedMat := function( mat, maps )
  636.     local i, j, k, nontrivblock, nontrivblocks, row, rows, newblocks, values,
  637.             blocks, pos, minima, fusion;
  638.     nontrivblocks:= [ Set( [ 1 .. Length( mat[1] ) ] ) ];
  639.     rows:= Concatenation( maps, mat );
  640.     for row in rows do
  641.       newblocks:= [];
  642.       for nontrivblock in nontrivblocks do
  643.         values:= [];
  644.         blocks:= [];
  645.         for k in nontrivblock do
  646.           pos:= 1;
  647.           while pos <= Length( values ) and values[ pos ] <> row[k] do
  648.             pos:= pos + 1;
  649.           od;
  650.           if pos > Length( values ) then
  651.             values[ pos ]:= row[k];
  652.             blocks[ pos ]:= [ k ];
  653.           else
  654.             AddSet( blocks[ pos ], k );
  655.           fi;
  656.         od;
  657.         for k in blocks do
  658.           if Length( k ) > 1 then Add( newblocks, k ); fi;
  659.         od;
  660.       od;
  661.       nontrivblocks:= newblocks;
  662.     od;
  663.     minima:= List( nontrivblocks, Minimum );
  664.     nontrivblocks:= Permuted( nontrivblocks, Sortex( minima ) );
  665.     minima:= Concatenation( [ 0 ], minima );
  666.     fusion:= [];
  667.     pos:= 1;
  668.     for i in [ 1 .. Length( minima ) - 1 ] do
  669.       for j in [ minima[i] + 1 .. minima[i+1] - 1 ] do
  670.         if not IsBound( fusion[j] ) then
  671.           fusion[j]:= pos;
  672.           pos:= pos + 1;
  673.         fi;
  674.       od;
  675.       for j in nontrivblocks[i] do fusion[j]:= pos; od;
  676.       pos:= pos + 1;
  677.     od;
  678.     for i in [ minima[ Length( minima ) ] + 1 .. Length( mat[1] ) ] do
  679.       if not IsBound( fusion[i] ) then
  680.         fusion[i]:= pos;
  681.         pos:= pos + 1;
  682.       fi;
  683.     od;
  684.     return rec( mat:= Restricted( mat, ProjectionMap( fusion ) ),
  685.                 fusion:= fusion );
  686.     end;
  687.  
  688.  
  689. #############################################################################
  690. ##
  691. #F  Powmap( <powermap>, <n> )
  692. #F  Powmap( <powermap>, <n>, <class> )
  693. ##
  694. ##  For all valid classes <class>, 'Powmap( <powermap>, <n> )[ <class> ] =
  695. ##  Powmap( <powermap>, <n>, <class> )'.
  696. ##  'Powmap( <powermap>, <n>, <class> )' is the image of <class> under the
  697. ##  <n>-th powermap where this map is calculated from the powermaps of the
  698. ##  prime factors of <n> that must be stored in <powermap>.
  699. ##
  700. Powmap := function( arg )
  701.     local i, n, powermap, class, nth_powermap, map;
  702.     if arg[1] = [] then
  703.       Error( "empty powermap" );
  704.     fi;
  705.     if Length( arg ) = 2 and IsList( arg[1] ) and IsInt( arg[2] ) then
  706.       powermap:= arg[1];
  707.       n:= arg[2];
  708.       if IsBound( powermap[n] ) then
  709.         return powermap[n];
  710.       else
  711.         nth_powermap:=
  712.                 List( [ 1 .. Length( powermap[ Length( powermap ) ] ) ] );
  713.         for i in Factors( n ) do
  714.           if not IsBound( powermap[i] ) then
  715.             Error( "powermap of prime factor ", i, " not available");
  716.           fi;
  717.           map:= powermap[i];
  718.           nth_powermap:= CompositionMaps( map, nth_powermap );
  719.         od;
  720.         return nth_powermap;
  721.       fi;
  722.     elif Length( arg ) = 3 and IsList( arg[1] ) and IsInt( arg[2] )
  723.          and IsInt( arg[3] ) then
  724.       powermap:= arg[1];
  725.       n:= arg[2];
  726.       class:= arg[3];
  727.       if n = 1 then return class; fi;
  728.       if IsBound( powermap[n] ) then
  729.         return powermap[n][ class ];
  730.       else
  731.         nth_powermap:= [ class ];
  732.         for i in Factors( n ) do
  733.           if  not IsBound( powermap[i] ) then
  734.             Error( "powermap of prime factor ", i, " not available");
  735.           fi;
  736.           map:= powermap[i];
  737.           nth_powermap[1]:= CompositionMaps( map, nth_powermap, 1 );
  738.         od;
  739.         return nth_powermap[1];
  740.       fi;
  741.     else
  742.       Error( "usage: Powmap(powermap,n) resp. Powmap(powermap,n,class)" );
  743.     fi;
  744.     end;
  745.  
  746.  
  747. #############################################################################
  748. ##
  749. #F  InducedCyclic( <tbl> )
  750. #F  InducedCyclic( <tbl>, \"all\" )
  751. #F  InducedCyclic( <tbl>, <classes> )
  752. #F  InducedCyclic( <tbl>, <classes>, \"all\" )
  753. ##
  754. ##  'InducedCyclic()' calculates characters induced up from cyclic subgroups
  755. ##  of <tbl> to <tbl>. If `"all"` is specified, all irreducible characters
  756. ##  of those subgroups are induced, otherwise only the permutation characters
  757. ##  are calculated. If a list <classes> is specified, only those cyclic
  758. ##  subgroups generated by these classes are considered, otherwise all classes
  759. ##  of <tbl> are considered. 'InducedCyclic()' returns a set of characters.
  760. ##
  761. InducedCyclic := function( arg )
  762.     local i, j, k, x, fusion, tbl, powermap, orders, inducedcyclic, single,
  763.           approxpowermap, independent, classes, upper;
  764.  
  765.     if not ( Length( arg ) in [ 1, 2, 3 ] and IsCharTable( arg[1] ) ) or
  766.        ( Length(arg) = 2 and not ( arg[2] = "all" or IsList(arg[2]) ) ) or
  767.        ( Length(arg) = 3 and not ( arg[3] = "all" and IsList(arg[2]) ) ) then
  768.       Error( "usage: InducedCyclic( tbl ) resp.\n",
  769.       "              InducedCyclic( tbl, \"all\" ) resp.\n",
  770.       "              InducedCyclic( tbl, classes ) resp.\n",
  771.       "              InducedCyclic( tbl, classes, \"all\" )");
  772.     fi;
  773.     tbl:= arg[1];
  774.     powermap:= tbl.powermap;
  775.     orders:= tbl.orders;
  776.     inducedcyclic:= [];
  777.     independent:= [];
  778.     for i in [ 1 .. Length( orders ) ] do independent[i]:= true; od;
  779.     if Length( arg ) = 1 or ( Length( arg ) = 2 and arg[2] = "all" ) then
  780.       classes:= [ 1 .. Length( orders ) ];
  781.     else
  782.       classes:= arg[2];
  783.     fi;
  784.     if classes <> Filtered( classes, x -> IsInt( orders[x] ) ) then
  785.       Print( "#I InducedCyclic: will consider only classes",
  786.              " with unique orders\n" );
  787.       classes:= Filtered( classes, x -> IsInt( orders[x] ) );
  788.     fi;
  789.     if arg[ Length( arg ) ] = "all" then
  790.       upper:= orders;
  791.     else                           # only permutation characters
  792.       upper:= [];
  793.       for i in classes do upper[i]:= 1; od;
  794.     fi;
  795.     # check powermaps:
  796.     for i in [ 1 .. Maximum( CompositionMaps( orders, classes ) ) ] do
  797.       if IsPrimeInt( i ) and not IsBound( powermap[i] ) then
  798.         Print( "#I InducedCyclic: powermap for prime ", i, " not available,\n",
  799.                "#I      calling Powermap( ., ", i,
  800.                ", rec( quick:= true ) )\n" );
  801.         approxpowermap:= Parametrized( Powermap(tbl,i,rec(quick:= true)) );
  802.         if ForAny( approxpowermap, IsSet ) then
  803.           Print( "#I InducedCyclic: powermap for prime ", i,
  804.                  " not determined\n" );
  805.         fi;
  806.         tbl.powermap[i]:= approxpowermap;
  807.         Print( "#I InducedCyclic: ", Ordinal(i),
  808.                " powermap stored on table\n" );
  809.       fi;
  810.     od;
  811.     inducedcyclic:= [];
  812.     for i in classes do                         # induce from i-th class
  813.       if independent[i] then
  814.         fusion:= [ i ];
  815.         for j in [ 2 .. orders[i] ] do
  816.           fusion[j]:= Powmap( powermap, j, i ); # j-th powermap at class i
  817.         od;
  818.         for k in [ 0 .. upper[i] - 1 ] do       # induce k-th character
  819.           single:= [ ];
  820.           for j in [ 1 .. Length( orders ) ] do single[j]:= 0; od;
  821.           single[i]:= E( orders[i] ) ^ ( k );
  822.           for j in [ 2 .. orders[i] ] do
  823.             if IsInt( fusion[j] ) then
  824.               if orders[ fusion[j] ] = orders[i] then
  825.  
  826.                 # pos. is galois conj. class
  827.                 independent[ fusion[j] ]:= false;
  828.               fi;
  829.               single[ fusion[j] ]:=
  830.                   single[ fusion[j] ] + E( orders[i] )^( k*j mod orders[i] );
  831.             else
  832.               for x in fusion[j] do single[x]:= Unknown(); od;
  833.             fi;
  834.           od;
  835.           for j in [ 1 .. Length( orders ) ] do
  836.             single[j]:= single[j] * tbl.centralizers[j] / orders[i];
  837.             if not IsCycInt( single[j] ) then
  838.               single[j]:= Unknown();
  839.               Print( "#I InducedCyclic: subgroup order not dividing sum",
  840.                      " (induce from class ", i, ")\n" );
  841.             fi;
  842.           od;
  843.           AddSet( inducedcyclic, single );
  844.         od;
  845.       fi;
  846.     od;
  847.     return inducedcyclic;
  848.     end;
  849.  
  850.  
  851. #############################################################################
  852. ##
  853. #F  Power( <powermap>, <characters>, <n> )
  854. ##
  855. ##  the indirections of <characters> by the <n>-th powermap; this map is
  856. ##  calculated from the powermap of the prime divisors of <n>.
  857. ##
  858. Power := function( powermap, characters, n )
  859.     local character, nth_powermap, power;
  860.     power:= [];
  861.     nth_powermap:= Powmap( powermap, n );
  862.     for character in characters do
  863.       Add( power, Indirected( character, nth_powermap ) );
  864.     od;
  865.     return power;
  866.     end;
  867.  
  868.  
  869. #############################################################################
  870. ##
  871. #F  Indicator( <tbl>, <n> )
  872. #F  Indicator( <tbl>, <characters>, <n> )
  873. #F  Indicator( <modtbl>, 2 )
  874. ##
  875. ##  the list of <n>-th Frobenius-Schur indicators of <characters>
  876. ##  or <tbl>.irreducibles, for Brauer tables in characteristic $\not= 2$
  877. ##  the second indicator
  878. ##
  879. Indicator := function( arg )
  880.     local i, j, tbl, characters, n, indicator, principal, powers, power,
  881.           ordindicator, chi, fus, odd;
  882.     if not ( Length( arg ) in [ 2, 3 ] and IsCharTable( arg[1] )
  883.              and IsInt( arg[ Length( arg ) ] ) )
  884.        or ( Length( arg ) = 3 and not IsList( arg[2] ) ) then
  885.       Error( "usage: Indicator( <tbl>, <n> )\n",
  886.              " resp. Indicator( <tbl>, <characters>, <n> )" );
  887.     fi;
  888.     tbl:= arg[1];
  889.     n:= arg[ Length( arg ) ];
  890.     if Length( arg ) = 2 then
  891.       characters:= tbl.irreducibles;
  892.     else
  893.       characters:= arg[2];
  894.     fi;
  895.     indicator:= [];
  896.     if IsBound( tbl.prime ) then
  897.  
  898.       # Brauer table
  899.       if Length( arg ) <> 2 or n <> 2 then
  900.         Error("for Brauer table <tbl> only for irreducibles and <n> = 2");
  901.       fi;
  902.       if tbl.prime = 2 then
  903.         Error( "for Brauer table <tbl> not for characteristic 2" );
  904.       fi;
  905.  
  906.       # compute indicators block by block
  907.       ordindicator:= Indicator( tbl.ordinary, tbl.ordinary.irreducibles, 2 );
  908.       fus:= GetFusionMap( tbl, tbl.ordinary );
  909.       for i in tbl.blocks do
  910.         if not IsBound( i.decmat ) then
  911.           i.decmat:= Decomposition( Sublist( tbl.irreducibles, i.modchars ),
  912.                            List( Sublist( tbl.ordinary.irreducibles,
  913.                                           i.ordchars ),
  914.                                  x -> Sublist( x, fus ) ), "nonnegative" );
  915.         fi;
  916.         for j in [ 1 .. Length( i.modchars ) ] do
  917.           chi:= tbl.irreducibles[ i.modchars[j] ];
  918.           if ForAny( chi, x -> not IsInt(x) and GaloisCyc(x,-1) <> x ) then
  919.  
  920.             # indicator of a Brauer character is 0 iff it has
  921.             # at least one nonreal value
  922.             indicator[ i.modchars[j] ]:= 0;
  923.  
  924.           else
  925.  
  926.             # indicator is equal to the indicator of any real ordinary
  927.             # character containing it as constituent, with odd multiplicity
  928.             odd:= Filtered( [ 1 .. Length( i.decmat ) ],
  929.                             x -> i.decmat[x][j] mod 2 <> 0 );
  930.             odd:= List( odd, x -> ordindicator[ i.ordchars[x] ] );
  931.             indicator[ i.modchars[j] ]:= First( odd, x -> x <> 0 );
  932.  
  933.           fi;
  934.         od;
  935.       od;
  936.  
  937.     else
  938.  
  939.       # ordinary table
  940.       principal:= List( tbl.centralizers, x -> 1 );
  941.       powers:= Power( tbl.powermap, characters, n );
  942.       for power in powers do
  943.         Add( indicator,
  944.              tbl.operations.ScalarProduct( tbl, power, principal ) );
  945.       od;
  946.  
  947.       if Length( arg ) = 3 then return indicator; fi;
  948.  
  949.     fi;
  950.  
  951.     # write indicator to the table
  952.     if not IsBound( tbl.irredinfo ) then tbl.irredinfo:= []; fi;
  953.     for i in [ 1 .. Length( characters ) ] do
  954.       if not IsBound( tbl.irredinfo[i] ) then
  955.         tbl.irredinfo[i]:= rec( indicator:= [] );
  956.       elif not IsBound( tbl.irredinfo[i].indicator ) then
  957.         tbl.irredinfo[i].indicator:= [];
  958.       fi;
  959.       tbl.irredinfo[i].indicator[n]:= indicator[i];
  960.     od;
  961.     InfoCharTable2( "#I Indicator: ", Ordinal( n ),
  962.                     " indicator written to the table\n" );
  963.  
  964.     return indicator;
  965.     end;
  966.  
  967.  
  968.