Quelle ctblfuns.gi Sprache: unbekannt

Spracherkennung für: .gi vermutete Sprache: Unknown {[0] [0] [0]} [Methode: Schwerpunktbildung, einfache Gewichte, sechs Dimensionen]

#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Thomas Breuer.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains generic methods for class functions.
##
## 2. Basic Operations for Class Functions
## 3. Comparison of Class Functions
## 4. Arithmetic Operations for Class Functions
## 5. Printing Class Functions
## 6. Creating Class Functions from Values Lists
## 7. Creating Class Functions using Groups
## 8. Operations for Class Functions
## 9. Restricted and Induced Class Functions
## 10. Reducing Virtual Characters
## 11. Symmetrizations of Class Functions
## 12. Operations for Brauer Characters
## 13. Domains Generated by Class Functions
## 14. Auxiliary operations
##

#############################################################################
##
#F CharacterString( <char>, <str> ) . . . . . character information string
##
InstallGlobalFunction( CharacterString, function( char, str )
 str:= Concatenation( str, " of degree ", String( char[1] ) );
 ConvertToStringRep( str );
 return str;
end );

#############################################################################
##
## 2. Basic Operations for Class Functions
##

#############################################################################
##
#M ValuesOfClassFunction( <list> )
##
## In order to treat lists as class functions where this makes sense,
## we define that `ValuesOfClassFunction' returns the list <list> itself.
##
InstallOtherMethod( ValuesOfClassFunction,
 "for a dense list",
 [ IsDenseList ],
 function( list )
 if IsClassFunction( list ) and not HasValuesOfClassFunction( list ) then
 Error( "class function <list> must store its values list" );
 else
 return list;
 fi;
 end );

#############################################################################
##
#M \[\]( <psi>, )
#M Length( <psi> )
#M IsBound\[\]( <psi>, )
#M Position( <psi>, <obj>, 0 )
##
## Class functions shall behave as immutable lists,
## we install methods for `\[\]', `Length', `IsBound\[\]', `Position',
## and `ShallowCopy'.
##
InstallMethod( \[\],
 "for class function and positive integer",
 [ IsClassFunction, IsPosInt ],
 function( chi, i )
 return ValuesOfClassFunction( chi )[i];
 end );

InstallMethod( Length,
 "for class function",
 [ IsClassFunction ],
 chi -> Length( ValuesOfClassFunction( chi ) ) );

InstallMethod( IsBound\[\],
 "for class function and positive integer",
 [ IsClassFunction, IsPosInt ],
 function( chi, i )
 return IsBound( ValuesOfClassFunction( chi )[i] );
 end );

InstallMethod( Position,
 "for class function, cyclotomic, and nonnegative integer",
 [ IsClassFunction, IsCyc, IsInt ],
 function( chi, obj, pos )
 return Position( ValuesOfClassFunction( chi ), obj, pos );
 end );

InstallMethod( ShallowCopy,
 "for class function",
 [ IsClassFunction ],
 chi -> ShallowCopy( ValuesOfClassFunction( chi ) ) );

#############################################################################
##
#M UnderlyingGroup( <chi> )
##
InstallOtherMethod( UnderlyingGroup,
 "for a class function",
 [ IsClassFunction ],
 chi -> UnderlyingGroup( UnderlyingCharacterTable( chi ) ) );

#############################################################################
##
## 3. Comparison of Class Functions
##

#############################################################################
##
#M \=( <chi>, <psi> ) . . . . . . . . . . . . . equality of class functions
##
InstallMethod( \=,
 "for two class functions",
 [ IsClassFunction, IsClassFunction ],
 function( chi, psi )
 return ValuesOfClassFunction( chi ) = ValuesOfClassFunction( psi );
 end );

InstallMethod( \=,
 "for a class function and a list",
 [ IsClassFunction, IsList ],
 function( chi, list )
 if IsClassFunction( list ) then
 return ValuesOfClassFunction( chi ) = ValuesOfClassFunction( list );
 else
 return ValuesOfClassFunction( chi ) = list;
 fi;
 end );

InstallMethod( \=,
 "for a list and a class function",
 [ IsList, IsClassFunction ],
 function( list, chi )
 if IsClassFunction( list ) then
 return ValuesOfClassFunction( list ) = ValuesOfClassFunction( chi );
 else
 return list = ValuesOfClassFunction( chi );
 fi;
 end );

#############################################################################
##
#M \<( <chi>, <psi> ) . . . . . . . . . . . . comparison of class functions
##
InstallMethod( \<,
 "for two class functions",
 [ IsClassFunction, IsClassFunction ],
 function( chi, psi )
 return ValuesOfClassFunction( chi ) < ValuesOfClassFunction( psi );
 end );

InstallMethod( \<,
 "for a class function and a list",
 [ IsClassFunction, IsList ],
 function( chi, list )
 if IsClassFunction( list ) then
 return ValuesOfClassFunction( chi ) < ValuesOfClassFunction( list );
 else
 return ValuesOfClassFunction( chi ) < list;
 fi;
 end );

InstallMethod( \<,
 "for a list and a class function",
 [ IsClassFunction, IsList ],
 function( list, chi )
 if IsClassFunction( list ) then
 return ValuesOfClassFunction( list ) < ValuesOfClassFunction( chi );
 else
 return list < ValuesOfClassFunction( chi );
 fi;
 end );

#############################################################################
##
## 4. Arithmetic Operations for Class Functions
##

#############################################################################
##
#M \+( <chi>, <obj> ) . . . . . . . . . . sum of class function and object
#M \+( <obj>, <chi> ) . . . . . . . . . . sum of object and class function
#M \+( <chi>, <psi> ) . . . . . . . . . . . . . . sum of virtual characters
#M \+( <chi>, <psi> ) . . . . . . . . . . . . . . . . . . sum of characters
##
## The sum of two class functions (virtual characters, characters) of the
## same character table is again a class function (virtual character,
## character) of this table.
## In all other cases, the addition is delegated to the list of values of
## the class function(s).
##
InstallOtherMethod( \+,
 "for class function, and object",
 [ IsClassFunction, IsObject ],
 function( chi, obj )
 local tbl, sum;
 tbl:= UnderlyingCharacterTable( chi );
 if IsClassFunction( obj ) and
 IsIdenticalObj( tbl, UnderlyingCharacterTable( obj ) ) then
 sum:= ClassFunction( tbl,
 ValuesOfClassFunction( chi ) + ValuesOfClassFunction( obj ) );
 else
 sum:= ValuesOfClassFunction( chi ) + obj;
 fi;
 return sum;
 end );

InstallOtherMethod( \+,
 "for object, and class function",
 [ IsObject, IsClassFunction ],
 function( obj, chi )
 local tbl, sum;
 tbl:= UnderlyingCharacterTable( chi );
 if IsClassFunction( obj ) and
 IsIdenticalObj( tbl, UnderlyingCharacterTable( obj ) ) then
 sum:= ClassFunction( tbl,
 ValuesOfClassFunction( obj ) + ValuesOfClassFunction( chi ) );
 else
 sum:= obj + ValuesOfClassFunction( chi );
 fi;
 return sum;
 end );

InstallMethod( \+,
 "for two virtual characters",
 IsIdenticalObj,
 [ IsClassFunction and IsVirtualCharacter,
 IsClassFunction and IsVirtualCharacter ],
 function( chi, psi )
 local tbl, sum;
 tbl:= UnderlyingCharacterTable( chi );
 sum:= ValuesOfClassFunction( chi ) + ValuesOfClassFunction( psi );
 if IsIdenticalObj( tbl, UnderlyingCharacterTable( psi ) ) then
 sum:= VirtualCharacter( tbl, sum );
 fi;
 return sum;
 end );

InstallMethod( \+,
 "for two characters",
 IsIdenticalObj,
 [ IsClassFunction and IsCharacter, IsClassFunction and IsCharacter ],
 function( chi, psi )
 local tbl, sum;
 tbl:= UnderlyingCharacterTable( chi );
 sum:= ValuesOfClassFunction( chi ) + ValuesOfClassFunction( psi );
 if IsIdenticalObj( tbl, UnderlyingCharacterTable( psi ) ) then
 sum:= Character( tbl, sum );
 fi;
 return sum;
 end );

#############################################################################
##
#M AdditiveInverseOp( <psi> ) . . . . . . . . . . . . for a class function
##
## The additive inverse of a virtual character is again a virtual character,
## but the additive inverse of a character is not a character,
## so we cannot use `ClassFunctionSameType'.
##
InstallMethod( AdditiveInverseOp,
 "for a class function",
 [ IsClassFunction ],
 psi -> ClassFunction( UnderlyingCharacterTable( psi ),
 AdditiveInverse( ValuesOfClassFunction( psi ) ) ) );

InstallMethod( AdditiveInverseOp,
 "for a virtual character",
 [ IsClassFunction and IsVirtualCharacter ],
 psi -> VirtualCharacter( UnderlyingCharacterTable( psi ),
 AdditiveInverse( ValuesOfClassFunction( psi ) ) ) );

#############################################################################
##
#M ZeroOp( <psi> ) . . . . . . . . . . . . . . . . . . for a class function
##
InstallMethod( ZeroOp,
 "for a class function",
 [ IsClassFunction ],
 psi -> VirtualCharacter( UnderlyingCharacterTable( psi ),
 Zero( ValuesOfClassFunction( psi ) ) ) );

#############################################################################
##
#M \*( <cyc>, <psi> ) . . . . . . . . . scalar multiple of a class function
#M \*( <psi>, <cyc> ) . . . . . . . . . scalar multiple of a class function
##
## We define a multiplication only for two class functions (being the tensor
## product), for scalar multiplication with cyclotomics,
## and for default list times class function (where the class function acts
## as a scalar).
## Note that more is not needed, since class functions are not in
## `IsMultiplicativeGeneralizedRowVector'.
##
InstallMethod( \*,
 "for cyclotomic, and class function",
 [ IsCyc, IsClassFunction ],
 function( cyc, chi )
 return ClassFunction( UnderlyingCharacterTable( chi ),
 cyc * ValuesOfClassFunction( chi ) );
 end );

InstallMethod( \*,
 "for integer, and virtual character",
 [ IsInt, IsVirtualCharacter ],
 function( cyc, chi )
 return VirtualCharacter( UnderlyingCharacterTable( chi ),
 cyc * ValuesOfClassFunction( chi ) );
 end );

InstallMethod( \*,
 "for positive integer, and character",
 [ IsPosInt, IsCharacter ],
 function( cyc, chi )
 return Character( UnderlyingCharacterTable( chi ),
 cyc * ValuesOfClassFunction( chi ) );
 end );

InstallMethod( \*,
 "for class function, and cyclotomic",
 [ IsClassFunction, IsCyc ],
 function( chi, cyc )
 return ClassFunction( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) * cyc );
 end );

InstallMethod( \*,
 "for virtual character, and integer",
 [ IsVirtualCharacter, IsInt ],
 function( chi, cyc )
 return VirtualCharacter( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) * cyc );
 end );

InstallMethod( \*,
 "for character, and positive integer",
 [ IsCharacter, IsPosInt ],
 function( chi, cyc )
 return Character( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) * cyc );
 end );

#############################################################################
##
#M OneOp( <psi> ) . . . . . . . . . . . . . . . . . . for a class function
##
InstallMethod( OneOp,
 "for class function",
 [ IsClassFunction ],
 psi -> TrivialCharacter( UnderlyingCharacterTable( psi ) ) );

#############################################################################
##
#M \*( <chi>, <psi> ) . . . . . . . . . . tensor product of class functions
##
InstallMethod( \*,
 "for two class functions",
 [ IsClassFunction, IsClassFunction ],
 function( chi, psi )
 local tbl, valschi, valspsi;
 tbl:= UnderlyingCharacterTable( chi );
 if not IsIdenticalObj( tbl, UnderlyingCharacterTable( psi ) ) then
 Error( "no product of class functions of different tables" );
 fi;
 valschi:= ValuesOfClassFunction( chi );
 valspsi:= ValuesOfClassFunction( psi );
 return ClassFunction( tbl,
 List( [ 1 .. Length( valschi ) ],
 x -> valschi[x] * valspsi[x] ) );
 end );

InstallMethod( \*,
 "for two virtual characters",
 IsIdenticalObj,
 [ IsVirtualCharacter, IsVirtualCharacter ],
 function( chi, psi )
 local tbl, valschi, valspsi;
 tbl:= UnderlyingCharacterTable( chi );
 if not IsIdenticalObj( tbl, UnderlyingCharacterTable( psi ) ) then
 Error( "no product of class functions of different tables" );
 fi;
 valschi:= ValuesOfClassFunction( chi );
 valspsi:= ValuesOfClassFunction( psi );
 return VirtualCharacter( tbl,
 List( [ 1 .. Length( valschi ) ],
 x -> valschi[x] * valspsi[x] ) );
 end );

InstallMethod( \*,
 "for two characters",
 IsIdenticalObj,
 [ IsCharacter, IsCharacter ],
 function( chi, psi )
 local tbl, valschi, valspsi;
 tbl:= UnderlyingCharacterTable( chi );
 if not IsIdenticalObj( tbl, UnderlyingCharacterTable( psi ) ) then
 Error( "no product of class functions of different tables" );
 fi;
 valschi:= ValuesOfClassFunction( chi );
 valspsi:= ValuesOfClassFunction( psi );
 return Character( tbl,
 List( [ 1 .. Length( valschi ) ],
 x -> valschi[x] * valspsi[x] ) );
 end );

#############################################################################
##
#M \*( <chi>, <list> ) . . . . . . . . . . class function times default list
#M \*( <list>, <chi> ) . . . . . . . . . . default list times class function
##
InstallOtherMethod( \*,
 "for class function, and list in `IsListDefault'",
 [ IsClassFunction, IsListDefault ],
 function( chi, list )
 return List( list, entry -> chi * entry );
 end );

InstallOtherMethod( \*,
 "for list in `IsListDefault', and class function",
 [ IsListDefault, IsClassFunction ],
 function( list, chi )
 return List( list, entry -> entry * chi );
 end );

#############################################################################
##
#M Order( <chi> ) . . . . . . . . . . . . . . . . order of a class function
##
## Note that we are not allowed to regard the determinantal order of an
## arbitrary (virtual) character as its order,
## since nonlinear characters do not have an order as mult. elements.
##
InstallMethod( Order,
 "for a class function",
 [ IsClassFunction ],
 function( chi )
 local order, values;

 values:= ValuesOfClassFunction( chi );
 if 0 in values then
 Error( "<chi> is not invertible" );
 elif ForAny( values, cyc -> not IsIntegralCyclotomic( cyc )
 or cyc * GaloisCyc( cyc, -1 ) <> 1 ) then
 return infinity;
 fi;
 order:= Conductor( values );
 if order mod 2 = 1 and ForAny( values, i -> i^order <> 1 ) then
 order:= 2*order;
 fi;
 return order;
 end );

#############################################################################
##
#M InverseOp( <chi> ) . . . . . . . . . . . . . . . . for a class function
##
InstallMethod( InverseOp,
 "for a class function",
 [ IsClassFunction ],
 function( chi )
 local values;

 values:= List( ValuesOfClassFunction( chi ), Inverse );
 if fail in values then
 return fail;
 elif HasIsCharacter( chi ) and IsCharacter( chi ) and values[1] = 1 then
 return Character( UnderlyingCharacterTable( chi ), values );
 else
 return ClassFunction( UnderlyingCharacterTable( chi ), values );
 fi;
 end );

#############################################################################
##
#M \^( <chi>, <n> ) . . . . . . . . . . for class function and pos. integer
##
InstallOtherMethod( \^,
 "for class function and positive integer (pointwise powering)",
 [ IsClassFunction, IsPosInt ],
 function( chi, n )
 return ClassFunctionSameType( UnderlyingCharacterTable( chi ),
 chi,
 List( ValuesOfClassFunction( chi ), x -> x^n ) );
 end );

#############################################################################
##
#M \^( <chi>, <g> ) . . . . . conjugate class function under action of <g>
##
InstallMethod( \^,
 "for class function and group element",
 [ IsClassFunction, IsMultiplicativeElementWithInverse ],
 function( chi, g )
 local tbl, G, mtbl, pi, fus, inv, imgs;

 tbl:= UnderlyingCharacterTable( chi );
 if HasUnderlyingGroup( tbl ) then
 # 'chi' is an ordinary character.
 G:= UnderlyingGroup( tbl );
 if IsElmsColls( FamilyObj( g ), FamilyObj( G ) ) then
 return ClassFunctionSameType( tbl, chi,
 Permuted( ValuesOfClassFunction( chi ),
 CorrespondingPermutations( tbl, chi, [ g ] )[1] ) );
 fi;
 elif HasOrdinaryCharacterTable( tbl ) then
 # 'chi' is a Brauer character.
 mtbl:= tbl;
 tbl:= OrdinaryCharacterTable( mtbl );
 if HasUnderlyingGroup( tbl ) then
 G:= UnderlyingGroup( tbl );
 if IsElmsColls( FamilyObj( g ), FamilyObj( G ) ) then
 pi:= CorrespondingPermutations( tbl, [ g ] )[1]^-1;
 fus:= GetFusionMap( mtbl, tbl );
 inv:= InverseMap( fus );
 imgs:= List( [ 1 .. Length( fus ) ], i -> inv[ fus[i]^pi ] );
 return ClassFunctionSameType( mtbl, chi,
 ValuesOfClassFunction( chi ){ imgs } );
 fi;
 fi;
 fi;
 TryNextMethod();
 end );

#############################################################################
##
#M \^( <chi>, <galaut> ) . . . Galois automorphism <galaut> applied to <chi>
##
InstallOtherMethod( \^,
 "for class function and Galois automorphism",
 [ IsClassFunction, IsGeneralMapping ],
 function( chi, galaut )
 if IsANFAutomorphismRep( galaut ) then
 galaut:= galaut!.galois;
 return ClassFunctionSameType( UnderlyingCharacterTable( chi ), chi,
 List( ValuesOfClassFunction( chi ),
 x -> GaloisCyc( x, galaut ) ) );
 elif IsOne( galaut ) then
 return chi;
 else
 TryNextMethod();
 fi;
 end );

#############################################################################
##
#M \^( <chi>, <G> ) . . . . . . . . . . . . . . . . induced class function
#M \^( <chi>, <tbl> ) . . . . . . . . . . . . . . . induced class function
##
InstallOtherMethod( \^,
 "for class function and group",
 [ IsClassFunction, IsGroup ],
 InducedClassFunction );

InstallOtherMethod( \^,
 "for class function and nearly character table",
 [ IsClassFunction, IsNearlyCharacterTable ],
 InducedClassFunction );

#############################################################################
##
#M \^( <g>, <chi> ) . . . . . . . . . . value of <chi> on group element <g>
##
InstallOtherMethod( \^,
 [ IsMultiplicativeElementWithInverse, IsClassFunction ],
 function( g, chi )
 local tbl, mtbl, ccl, i;

 tbl:= UnderlyingCharacterTable( chi );
 if HasOrdinaryCharacterTable( tbl ) then
 # 'chi' is a Brauer character.
 mtbl:= tbl;
 tbl:= OrdinaryCharacterTable( mtbl );
 if not HasUnderlyingGroup( tbl ) then
 Error( "table <tbl> of <chi> does not store its group" );
 elif not g in UnderlyingGroup( tbl )
 or Order( g ) mod UnderlyingCharacteristic( mtbl ) = 0 then
 Error( "<g> must be p-regular and lie in the underlying group of <chi>" );
 else
 ccl:= ConjugacyClasses( tbl ){ GetFusionMap( mtbl, tbl ) };
 fi;
 elif not HasUnderlyingGroup( tbl ) then
 Error( "table <tbl> of <chi> does not store its group" );
 elif not g in UnderlyingGroup( tbl ) then
 Error( "<g> must lie in the underlying group of <chi>" );
 else
 ccl:= ConjugacyClasses( tbl );
 fi;

 for i in [ 1 .. Length( ccl ) ] do
 if g in ccl[i] then
 return ValuesOfClassFunction( chi )[i];
 fi;
 od;
 end );

#############################################################################
##
#M \^( <psi>, <chi> ) . . . . . . . . . . conjugation of linear characters
##
InstallOtherMethod( \^,
 "for two class functions (conjugation, trivial action)",
 [ IsClassFunction, IsClassFunction ],
 ReturnFirst);

#############################################################################
##
#M GlobalPartitionOfClasses( <tbl> )
##
InstallMethod( GlobalPartitionOfClasses,
 "for an ordinary character table",
 [ IsOrdinaryTable ],
 function( tbl )
 local part, # partition that has to be respected
 list, # list of all maps to be respected
 map, # one map in 'list'
 inv, # contains number of root classes
 newpart, #
 values, #
 j, # loop over 'orb'
 pt; # one point to map

 if HasAutomorphismsOfTable( tbl ) then

 # The orbits define the finest possible global partition.
 part:= OrbitsDomain( AutomorphismsOfTable( tbl ),
 [ 1 .. Length( NrConjugacyClasses( tbl ) ) ] );

 else

 # Conjugate classes must have same representative order and
 # same centralizer order.
 list:= [ OrdersClassRepresentatives( tbl ),
 SizesCentralizers( tbl ) ];

 # The number of root classes is by definition invariant under
 # table automorphisms.
 for map in Compacted( ComputedPowerMaps( tbl ) ) do
 inv:= ZeroMutable( map );
 for j in map do
 inv[j]:= inv[j] + 1;
 od;
 Add( list, inv );
 od;

 # All elements in `list' must be respected.
 # Transform each of them into a partition,
 # and form the intersection of these partitions.
 part:= Partition( [ [ 1 .. Length( list[1] ) ] ] );
 for map in list do
 newpart := [];
 values := [];
 for j in [ 1 .. Length( map ) ] do
 pt:= Position( values, map[j] );
 if pt = fail then
 Add( values, map[j] );
 Add( newpart, [ j ] );
 else
 Add( newpart[ pt ], j );
 fi;
 od;
 StratMeetPartition( part, Partition( newpart ) );
 od;
 part:= List( Cells( part ), Set );
#T unfortunately `Set' necessary ...

 fi;

 return part;
 end );

#############################################################################
##
#M CorrespondingPermutations( <tbl>, <elms> ) . action on the conj. classes
##
InstallMethod( CorrespondingPermutations,
 "for character table and list of group elements",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, elms )
 local classes, # list of conjugacy classes
 perms, # list of permutations, result
 part, # partition that has to be respected
 base, # base of aut. group
 g, # loop over `elms'
 images, # list of images
 pt, # one point to map
 im, # actual image class
 orb, # possible image points
 found, # image point found? (boolean value)
 j, # loop over 'orb'
 list, # one list in 'part'
 first, # first point in orbit of 'g'
 min; # minimal length of nontrivial orbit of 'g'

 classes:= ConjugacyClasses( tbl );

 perms:= [];

 # If the table automorphisms are known then we only must determine
 # the images of a base of this group.
 if HasAutomorphismsOfTable( tbl ) then

 part:= AutomorphismsOfTable( tbl );

 if IsTrivial( part ) then
 return ListWithIdenticalEntries( Length( elms ), () );
 fi;

 # Compute the images of the base points of this group.
 base:= BaseOfGroup( part );

 for g in elms do

 if IsOne( g ) then

 # If `g' is the identity then nothing is to do.
 Add( perms, () );

 else

 images:= [];
 for pt in base do

 im:= Representative( classes[ pt ] ) ^ g;
 found:= false;
 for j in Orbit( part, pt ) do
#T better CanonicalClassElement ??
 if im in classes[j] then
 Add( images, j );
 found:= true;
 break;
 fi;
 od;

 od;

 # Compute a group element.
 Add( perms,
 RepresentativeAction( part, base, images, OnTuples ) );

 fi;

 od;

 else

 # We can use only a partition into unions of orbits.

 part:= GlobalPartitionOfClasses( tbl );
 if Length( part ) = Length( classes ) then
 return ListWithIdenticalEntries( Length( elms ), () );
 fi;

 for g in elms do
#T It would be more natural to write
#T Permutation( g, ConjugacyClasses( tbl ), OnPoints ),
#T *BUT* the `Permutation' method in question first asks whether
#T the list of classes is sorted,
#T and there is no method to compare the classes!

 if IsOne( g ) then

 # If `g' is the identity then nothing is to do.
 Add( perms, () );

 else

 # Compute orbits of `g' on the lists in `part', store the images.
 # Note that if we have taken away a union of orbits such that the
 # number of remaining points is smaller than the smallest prime
 # divisor of the order of `g' then all these points must be fixed.
 min:= Factors(Integers, Order( g ) )[1];
 images:= [];

 for list in part do

 if Length( list ) = 1 then
#T why not `min' ?

 # necessarily fixed point
 images[ list[1] ]:= list[1];

 else

 orb:= ShallowCopy( list );
 while min <= Length( orb ) do

 # There may be nontrivial orbits.
 pt:= orb[1];
 first:= pt;
 j:= 1;

 while j <= Length( orb ) do

 im:= Representative( classes[ pt ] ) ^ g;
 found:= false;
 while j <= Length( orb ) and not found do
#T better CanonicalClassElement ??
 if im in classes[ orb[j] ] then
 images[pt]:= orb[j];
 found:= true;
 fi;
 j:= j+1;
 od;

 RemoveSet( orb, pt );

 if found and pt <> images[ pt ] then
 pt:= images[ pt ];
 j:= 1;
 fi;

 od;

 # The image must be the first point of the orbit under `g'.
 images[pt]:= first;

 od;

 # The remaining points of the orbit must be fixed.
 for pt in orb do
 images[pt]:= pt;
 od;

 fi;

 od;

 # Compute a group element.
 Add( perms, PermList( images ) );

 fi;

 od;

 fi;

 return perms;
 end );

#############################################################################
##
#M CorrespondingPermutations( <tbl>, <chi>, <elms> )
##
InstallOtherMethod( CorrespondingPermutations,
 "for a char. table, a hom. list, and a list of group elements",
 [ IsOrdinaryTable, IsHomogeneousList, IsHomogeneousList ],
 function( tbl, values, elms )
 local classes, # list of conjugacy classes
 perms, # list of permutations, result
 part, # partition that has to be respected
 base, # base of aut. group
 g, # loop over `elms'
 images, # list of images
 pt, # one point to map
 im, # actual image class
 orb, # possible image points
 found, # image point found? (boolean value)
 j, # loop over 'orb'
 list, # one list in 'part'
 first, # first point in orbit of 'g'
 min; # minimal length of nontrivial orbit of 'g'

 classes:= ConjugacyClasses( tbl );
 perms:= [];

 # If the table automorphisms are known then we only must determine
 # the images of a base of this group.
 if HasAutomorphismsOfTable( tbl ) then

 part:= AutomorphismsOfTable( tbl );

 if IsTrivial( part ) then
 return ListWithIdenticalEntries( Length( elms ), () );
 fi;

 # Compute the images of the base points of this group.
 base:= BaseOfGroup( part );

 for g in elms do

 if IsOne( g ) then

 # If `g' is the identity then nothing is to do.
 Add( perms, () );

 else

 images:= [];
 for pt in base do

 im:= Representative( classes[ pt ] ) ^ g;
 found:= false;
 for j in Orbit( part, pt ) do
#T better CanonicalClassElement ??
 if im in classes[j] then
 Add( images, j );
 found:= true;
 break;
 fi;
 j:= j+1;
 od;

 od;

 # Compute a group element (if possible).
 Add( perms,
 RepresentativeAction( part, base, images, OnTuples ) );

 fi;

 od;

 else

 # We can use only a partition into unions of orbits.

 part:= GlobalPartitionOfClasses( tbl );
 if Length( part ) = Length( classes ) then
 return ListWithIdenticalEntries( Length( elms ), () );
 fi;

 for g in elms do

 if IsOne( g ) then

 # If `g' is the identity then nothing is to do.
 Add( perms, () );

 else

 # Compute orbits of `g' on the lists in `part', store the images.
 # Note that if we have taken away a union of orbits such that the
 # number of remaining points is smaller than the smallest prime
 # divisor of the order of `g' then all these points must be fixed.
 min:= Factors(Integers, Order( g ) )[1];
 images:= [];

 for list in part do

 if Length( list ) = 1 then
#T why not `min' ?

 # necessarily fixed point
 images[ list[1] ]:= list[1];

 elif Length( Set( values{ list } ) ) = 1 then

 # We may take any permutation of the orbit.
 for j in list do
 images[j]:= j;
 od;

 else

 orb:= ShallowCopy( list );
 while Length( orb ) >= min do
#T fishy for S4 acting on V4 !!

 # There may be nontrivial orbits.
 pt:= orb[1];
 first:= pt;
 j:= 1;

 while j <= Length( orb ) do

 im:= Representative( classes[ pt ] ) ^ g;
 found:= false;
 while j <= Length( orb ) and not found do
#T better CanonicalClassElement ??
 if im in classes[ orb[j] ] then
 images[pt]:= orb[j];
 found:= true;
 fi;
 j:= j+1;
 od;

 RemoveSet( orb, pt );

 if found then
 j:= 1;
 pt:= images[pt];
 fi;

 od;

 # The image must be the first point of the orbit under `g'.
 images[pt]:= first;

 od;

 # The remaining points of the orbit must be fixed.
 for pt in orb do
 images[pt]:= pt;
 od;

 fi;

 od;

 # Compute a group element.
 Add( perms, PermList( images ) );

 fi;

 od;

 fi;

 return perms;
 end );

#############################################################################
##
#M ComplexConjugate( <chi> )
##
## We use `InstallOtherMethod' because class functions are both scalars and
## lists, so the method matches two declarations of the operation.
##
InstallOtherMethod( ComplexConjugate,
 "for a class function",
 [ IsClassFunction and IsCyclotomicCollection ],
 chi -> GaloisCyc( chi, -1 ) );

#############################################################################
##
#M GaloisCyc( <chi>, <k> )
##
InstallMethod( GaloisCyc,
 "for a class function, and an integer",
 [ IsClassFunction and IsCyclotomicCollection, IsInt ],
 function( chi, k )
 local tbl, char, n, g;

 tbl:= UnderlyingCharacterTable( chi );
 char:= UnderlyingCharacteristic( tbl );
 n:= Conductor( chi );
 g:= Gcd( k, n );

 if k = -1 or
 ( char = 0 and g = 1 ) then
 return ClassFunctionSameType( tbl, chi,
 GaloisCyc( ValuesOfClassFunction( chi ), k ) );
#T also if k acts as some *(p^d) for char = p
#T (reduce k mod n, and then what?)
 else
 return ClassFunction( tbl,
 GaloisCyc( ValuesOfClassFunction( chi ), k ) );
 fi;
 end );

#############################################################################
##
#M Permuted( <chi>, <perm> )
##
InstallMethod( Permuted,
 "for a class function, and a permutation",
 [ IsClassFunction, IsPerm ],
 function( chi, perm )
 return ClassFunction( UnderlyingCharacterTable( chi ),
 Permuted( ValuesOfClassFunction( chi ), perm ) );
 end );

#############################################################################
##
## 5. Printing Class Functions
##

#############################################################################
##
#M ViewObj( <psi> ) . . . . . . . . . . . . . . . . . view a class function
##
## Note that class functions are finite lists, so the default `ViewObj'
## method for finite lists should be avoided.
##
InstallMethod( ViewObj,
 "for a class function",
 [ IsClassFunction ],
 function( psi )
 Print( "ClassFunction( " );
 View( UnderlyingCharacterTable( psi ) );
 Print( ",\<\<\<\>\>\> " );
 View( ValuesOfClassFunction( psi ) );
 Print( " )" );
 end );

InstallMethod( ViewObj,
 "for a virtual character",
 [ IsClassFunction and IsVirtualCharacter ],
 function( psi )
 Print( "VirtualCharacter( " );
 View( UnderlyingCharacterTable( psi ) );
 Print( ",\<\<\<\>\>\> " );
 View( ValuesOfClassFunction( psi ) );
 Print( " )" );
 end );

InstallMethod( ViewObj,
 "for a character",
 [ IsClassFunction and IsCharacter ],
 function( psi )
 Print( "Character( " );
 View( UnderlyingCharacterTable( psi ) );
 Print( ",\<\<\<\>\>\> " );
 View( ValuesOfClassFunction( psi ) );
 Print( " )" );
 end );

#############################################################################
##
#M PrintObj( <psi> ) . . . . . . . . . . . . . . . . print a class function
##
InstallMethod( PrintObj,
 "for a class function",
 [ IsClassFunction ],
 function( psi )
 Print( "ClassFunction( ", UnderlyingCharacterTable( psi ),
 ", ", ValuesOfClassFunction( psi ), " )" );
 end );

InstallMethod( PrintObj,
 "for a virtual character",
 [ IsClassFunction and IsVirtualCharacter ],
 function( psi )
 Print( "VirtualCharacter( ", UnderlyingCharacterTable( psi ),
 ", ", ValuesOfClassFunction( psi ), " )" );
 end );

InstallMethod( PrintObj,
 "for a character",
 [ IsClassFunction and IsCharacter ],
 function( psi )
 Print( "Character( ", UnderlyingCharacterTable( psi ),
 ", ", ValuesOfClassFunction( psi ), " )" );
 end );

#############################################################################
##
#M Display( <chi> ) . . . . . . . . . . . . . . . display a class function
#M Display( <chi>, <arec> )
##
InstallMethod( Display,
 "for a class function",
 [ IsClassFunction ],
 function( chi )
 Display( UnderlyingCharacterTable( chi ), rec( chars:= [ chi ] ) );
 end );

InstallOtherMethod( Display,
 "for a class function, and a record",
 [ IsClassFunction, IsRecord ],
 function( chi, arec )
 arec:= ShallowCopy( arec );
 arec.chars:= [ chi ];
 Display( UnderlyingCharacterTable( chi ), arec );
 end );

#############################################################################
##
## 6. Creating Class Functions from Values Lists
##

#############################################################################
##
#M ClassFunction( <tbl>, <values> )
##
InstallMethod( ClassFunction,
 "for nearly character table, and dense list",
 [ IsNearlyCharacterTable, IsDenseList ],
 function( tbl, values )
 local chi;

 # Check the no. of classes.
 if NrConjugacyClasses( tbl ) <> Length( values ) then
 Error( "no. of classes in <tbl> and <values> must be equal" );
 fi;

 # Create the object.
 chi:= Objectify( NewType( FamilyObj( values ),
 IsClassFunction
 and IsAttributeStoringRep ),
 rec() );

 # Store the defining attribute values.
 SetValuesOfClassFunction( chi, ValuesOfClassFunction( values ) );
 SetUnderlyingCharacterTable( chi, tbl );

 # Store useful information.
 if IsSmallList( values ) then
 SetIsSmallList( chi, true );
 fi;

 return chi;
 end );

#############################################################################
##
#M ClassFunction( <G>, <values> )
##
InstallMethod( ClassFunction,
 "for a group, and a dense list",
 [ IsGroup, IsDenseList ],
 function( G, values )
 return ClassFunction( OrdinaryCharacterTable( G ), values );
 end );

#############################################################################
##
#M VirtualCharacter( <tbl>, <values> )
##
InstallMethod( VirtualCharacter,
 "for nearly character table, and dense list",
 [ IsNearlyCharacterTable, IsDenseList ],
 function( tbl, values )
 values:= ClassFunction( tbl, values );
 SetIsVirtualCharacter( values, true );
 return values;
 end );

#############################################################################
##
#M VirtualCharacter( <G>, <values> )
##
InstallMethod( VirtualCharacter,
 "for a group, and a dense list",
 [ IsGroup, IsDenseList ],
 function( G, values )
 return VirtualCharacter( OrdinaryCharacterTable( G ), values );
 end );

#############################################################################
##
#M Character( <tbl>, <values> )
##
InstallMethod( Character,
 "for nearly character table, and dense list",
 [ IsNearlyCharacterTable, IsDenseList ],
 function( tbl, values )
 values:= ClassFunction( tbl, values );
 SetIsCharacter( values, true );
 return values;
 end );

#############################################################################
##
#M Character( <G>, <values> )
##
InstallMethod( Character,
 "for a group, and a dense list",
 [ IsGroup, IsDenseList ],
 function( G, values )
 return Character( OrdinaryCharacterTable( G ), values );
 end );

#############################################################################
##
#F ClassFunctionSameType( <tbl>, <chi>, <values> )
##
InstallGlobalFunction( ClassFunctionSameType,
 function( tbl, chi, values )
 if not IsClassFunction( chi ) then
 return values;
 elif HasIsCharacter( chi ) and IsCharacter( chi ) then
 return Character( tbl, values );
 elif HasIsVirtualCharacter( chi ) and IsVirtualCharacter( chi ) then
 return VirtualCharacter( tbl, values );
 else
 return ClassFunction( tbl, values );
 fi;
end );

#############################################################################
##
## 7. Creating Class Functions using Groups
##

#############################################################################
##
#M TrivialCharacter( <tbl> ) . . . . . . . . . . . . . for a character table
##
InstallMethod( TrivialCharacter,
 "for a character table",
 [ IsNearlyCharacterTable ],
 function( tbl )
 local chi;

 chi:= Character( tbl,
 ListWithIdenticalEntries( NrConjugacyClasses( tbl ), 1 ) );
 SetIsIrreducibleCharacter( chi, true );
 return chi;
 end );

#############################################################################
##
#M TrivialCharacter( <G> ) . . . . . . . . . . . . . . . . . . . for a group
##
InstallMethod( TrivialCharacter,
 "for a group (delegate to the table)",
 [ IsGroup ],
 G -> TrivialCharacter( OrdinaryCharacterTable( G ) ) );

#############################################################################
##
#M NaturalCharacter( <G> ) . . . . . . . . . . . . . for a permutation group
##
InstallMethod( NaturalCharacter,
 "for a permutation group",
 [ IsGroup and IsPermCollection ],
 function( G )
 local deg, tbl;
 deg:= NrMovedPoints( G );
 tbl:= OrdinaryCharacterTable( G );
 return Character( tbl,
 List( ConjugacyClasses( tbl ),
 C -> deg - NrMovedPoints( Representative( C ) ) ) );
 end );

#############################################################################
##
#M NaturalCharacter( <G> ) . . . . for a matrix group in characteristic zero
##
InstallMethod( NaturalCharacter,
 "for a matrix group in characteristic zero",
 [ IsGroup and IsRingElementCollCollColl ],
 function( G )
 local tbl;
 if Characteristic( G ) = 0 then
 tbl:= OrdinaryCharacterTable( G );
 return Character( tbl,
 List( ConjugacyClasses( tbl ),
 C -> TraceMat( Representative( C ) ) ) );
 else
 TryNextMethod();
 fi;
 end );

#############################################################################
##
#M NaturalCharacter( <hom> ) . . . . . . . . . . . for a group homomorphism
##
## We use shortcuts for homomorphisms onto permutation groups and matrix
## groups in characteristic zero,
## since the meaning of `NaturalCharacter' is clear for these cases and
## we can avoid explicit conjugacy tests in the image.
## For other cases, we use a generic way.
##
InstallMethod( NaturalCharacter,
 "for a group general mapping",
 [ IsGeneralMapping ],
 function( hom )
 local G, R, deg, tbl, chi;
 G:= Source( hom );
 R:= Range( hom );
 tbl:= OrdinaryCharacterTable( G );
 if IsPermGroup( R ) then
 deg:= NrMovedPoints( R );
 return Character( tbl,
 List( ConjugacyClasses( tbl ),
 C -> deg - NrMovedPoints( ImagesRepresentative( hom,
 Representative( C ) ) ) ) );
 elif IsMatrixGroup( R ) and Characteristic( R ) = 0 then
 return Character( tbl,
 List( ConjugacyClasses( tbl ),
 C -> TraceMat( ImagesRepresentative( hom,
 Representative( C ) ) ) ) );
 else
 chi:= NaturalCharacter( Image( hom ) );
 return Character( tbl,
 List( ConjugacyClasses( tbl ),
 C -> ImagesRepresentative( hom,
 Representative( C ) ) ^ chi ) );
 fi;
 end );

#############################################################################
##
#M PermutationCharacter( <G>, <D>, <opr> ) . . . . . . . . for group action
##
InstallMethod( PermutationCharacter,
 "group action on domain",
 [ IsGroup, IsCollection, IsFunction ],
 function( G, dom, opr )
 local tbl;
 tbl:= OrdinaryCharacterTable( G );
 return Character( tbl, List( ConjugacyClasses( tbl ),
 i -> Number( dom, j -> j = opr( j, Representative(i) ) ) ) );
 end);

#############################################################################
##
#M PermutationCharacter( <G>, ) . . . . . . . . . . . . for two groups
##
InstallMethod( PermutationCharacter,
 "for two groups (use double cosets)",
 IsIdenticalObj,
 [ IsGroup, IsGroup ],
 function( G, U )
 local tbl, C, c, s, i;

 tbl:= OrdinaryCharacterTable( G );
 C := ConjugacyClasses( tbl );
 c := [ Index( G, U ) ];
 s := Size( U );

 for i in [ 2 .. Length(C) ] do
 c[i]:= Number( DoubleCosets( G, U,
 SubgroupNC( G, [ Representative( C[i] ) ] ) ),
 x -> Size( x ) = s );
 od;

 # Return the character.
 return Character( tbl, c );
 end );

#T #############################################################################
#T ##
#T #M PermutationCharacter( <G>, ) . . . . . . . . . for two small groups
#T ##
#T InstallMethod( PermutationCharacter,
#T "for two small groups",
#T IsIdenticalObj,
#T [ IsGroup and IsSmallGroup, IsGroup and IsSmallGroup ],
#T function( G, U )
#T local E, I, tbl;
#T
#T E := AsList( U );
#T I := Size( G ) / Length( E );
#T tbl:= OrdinaryCharacterTable( G );
#T return Character( tbl,
#T List( ConjugacyClasses( tbl ),
#T C -> I * Length( Intersection2( AsList( C ), E ) ) / Size( C ) ) );
#T end );

#############################################################################
##
## 8. Operations for Class Functions
##

#############################################################################
##
#M IsCharacter( <obj> ) . . . . . . . . . . . . . . for a virtual character
##
InstallMethod( IsCharacter,
 "for a virtual character",
 [ IsClassFunction and IsVirtualCharacter ],
 obj -> IsCharacter( UnderlyingCharacterTable( obj ),
 ValuesOfClassFunction( obj ) ) );

InstallMethod( IsCharacter,
 "for a class function",
 [ IsClassFunction ],
 function( obj )
 if HasIsVirtualCharacter( obj ) and not IsVirtualCharacter( obj ) then
#T can disappear when inverse implications are supported!
 return false;
 fi;
 return IsCharacter( UnderlyingCharacterTable( obj ),
 ValuesOfClassFunction( obj ) );
 end );

InstallMethod( IsCharacter,
 "for an ordinary character table, and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, list )
 local chi, scpr;

 # Proper characters have positive degree.
 if list[1] <= 0 then
 return false;
 fi;

 # Check the scalar products with all irreducibles.
 for chi in Irr( tbl ) do
 scpr:= ScalarProduct( tbl, chi, list );
 if not IsInt( scpr ) or scpr < 0 then
 return false;
 fi;
 od;
 return true;
 end );

InstallMethod( IsCharacter,
 "for a Brauer table, and a homogeneous list",
 [ IsBrauerTable, IsHomogeneousList ],
 function( tbl, list )
 # Proper characters have positive degree.
 if list[1] <= 0 then
 return false;
 fi;

 # Check the decomposition.
 return Decomposition( Irr( tbl ), [ list ], "nonnegative" )[1] <> fail;
 end );

#############################################################################
##
#M IsVirtualCharacter( <chi> ) . . . . . . . . . . . . for a class function
##
InstallMethod( IsVirtualCharacter,
 "for a class function",
 [ IsClassFunction ],
 chi -> IsVirtualCharacter( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) ) );

InstallMethod( IsVirtualCharacter,
 "for an ordinary character table, and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, list )
 local chi;

 # Check the scalar products with all irreducibles.
 for chi in Irr( tbl ) do
 if not IsInt( ScalarProduct( tbl, chi, list ) ) then
 return false;
 fi;
 od;
 return true;
 end );

# InstallMethod( IsVirtualCharacter,
# "for a Brauer table, and a homogeneous list",
# [ IsBrauerTable, IsHomogeneousList ],
# function( tbl, list )
# ???
# end );

#############################################################################
##
#M IsIrreducibleCharacter( <chi> ) . . . . . . . . . for a class function
##
InstallMethod( IsIrreducibleCharacter,
 "for a class function",
 [ IsClassFunction ],
 chi -> IsIrreducibleCharacter( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) ) );

InstallMethod( IsIrreducibleCharacter,
 "for an ordinary character table, and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, list )
 return IsVirtualCharacter( tbl, list )
 and ScalarProduct( tbl, list, list) = 1
 and list[1] > 0;
 end );

InstallMethod( IsIrreducibleCharacter,
 "for a Brauer table, and a homogeneous list",
 [ IsBrauerTable, IsHomogeneousList ],
 function( tbl, list )
 local i, found;
 list:= Decomposition( Irr( tbl ), [ list ], "nonnegative" )[1];
 if list = fail then
 return false;
 fi;
 found:= false;
 for i in list do
 if i <> 0 then
 if found or i <> 1 then
 return false;
 else
 found:= true;
 fi;
 fi;
 od;
 return found;
 end );

#############################################################################
##
#M ScalarProduct( <chi>, <psi> ) . . . . . . . . . . for two class functions
##
InstallMethod( ScalarProduct,
 "for two class functions",
 [ IsClassFunction, IsClassFunction ],
 function( chi, psi )
 local tbl;

 tbl:= UnderlyingCharacterTable( chi );
 if tbl <> UnderlyingCharacterTable( psi ) then
 Error( "<chi> and <psi> have different character tables" );
 fi;
 return ScalarProduct( tbl, ValuesOfClassFunction( chi ),
 ValuesOfClassFunction( psi ) );
 end );

#############################################################################
##
#M ScalarProduct( <tbl>, <chi>, <psi> ) . scalar product of class functions
##
InstallMethod( ScalarProduct,
 "for character table and two homogeneous lists",
 [ IsCharacterTable, IsRowVector, IsRowVector ],
 function( tbl, x1, x2 )
 local i, # loop variable
 scpr, # scalar product, result
 weight; # lengths of conjugacy classes

 weight:= SizesConjugacyClasses( tbl );
 x1:= ValuesOfClassFunction( x1 );
 x2:= ValuesOfClassFunction( x2 );
 scpr:= 0;
 for i in [ 1 .. Length( x1 ) ] do
 if x1[i]<>0 and x2[i]<>0 then
 scpr:= scpr + x1[i] * GaloisCyc( x2[i], -1 ) * weight[i];
 fi;
 od;
 return scpr / Size( tbl );
 end );

#############################################################################
##
#F MatScalarProducts( [<tbl>, ]<list1>, <list2> )
#F MatScalarProducts( [<tbl>, ]<list> )
##
InstallMethod( MatScalarProducts,
 "for two homogeneous lists",
 [ IsHomogeneousList, IsHomogeneousList ],
 function( list1, list2 )
 if IsEmpty( list1 ) then
 return [];
 elif not IsClassFunction( list1[1] ) then
 Error( "<list1> must consist of class functions" );
 else
 return MatScalarProducts( UnderlyingCharacterTable( list1[1] ),
 list1, list2 );
 fi;
 end );

InstallMethod( MatScalarProducts,
 "for a homogeneous list",
 [ IsHomogeneousList ],
 function( list )
 if IsEmpty( list ) then
 return [];
 elif not IsClassFunction( list[1] ) then
 Error( "<list> must consist of class functions" );
 else
 return MatScalarProducts( UnderlyingCharacterTable( list[1] ), list );
 fi;
 end );

InstallMethod( MatScalarProducts,
 "for an ordinary table, and two homogeneous lists",
 [ IsOrdinaryTable, IsHomogeneousList, IsHomogeneousList ],
 function( tbl, list1, list2 )
 local i, j, chi, nccl, weight, scprmatrix, order, scpr;

 if IsEmpty( list1 ) then
 return [];
 fi;
 list1:= List( list1, ValuesOfClassFunction );

 nccl:= NrConjugacyClasses( tbl );
 weight:= SizesConjugacyClasses( tbl );
 order:= Size( tbl );

 scprmatrix:= [];
 for i in [ 1 .. Length( list2 ) ] do
 scprmatrix[i]:= [];
 chi:= List( ValuesOfClassFunction( list2[i] ), x -> GaloisCyc(x,-1) );
 for j in [ 1 .. nccl ] do
 chi[j]:= chi[j] * weight[j];
 od;
 for j in list1 do
 scpr:= ( chi * j ) / order;
 Add( scprmatrix[i], scpr );
 if not IsInt( scpr ) then
 if IsRat( scpr ) then
 Info( InfoCharacterTable, 2,
 "MatScalarProducts: sum not divisible by group order" );
 elif IsCyc( scpr ) then
 Info( InfoCharacterTable, 2,
 "MatScalarProducts: summation not integer valued");
 fi;
 fi;
 od;
 od;
 return scprmatrix;
 end );

InstallMethod( MatScalarProducts,
 "for an ordinary table, and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, list )
 local i, j, chi, nccl, weight, scprmatrix, order, scpr;

 if IsEmpty( list ) then
 return [];
 fi;
 list:= List( list, ValuesOfClassFunction );

 nccl:= NrConjugacyClasses( tbl );
 weight:= SizesConjugacyClasses( tbl );
 order:= Size( tbl );

 scprmatrix:= [];
 for i in [ 1 .. Length( list ) ] do
 scprmatrix[i]:= [];
 chi:= List( list[i], x -> GaloisCyc( x, -1 ) );
 for j in [ 1 .. nccl ] do
 chi[j]:= chi[j] * weight[j];
 od;
 for j in [ 1 .. i ] do
 scpr:= ( chi * list[j] ) / order;
 Add( scprmatrix[i], scpr );
 if not IsInt( scpr ) then
 if IsRat( scpr ) then
 Info( InfoCharacterTable, 2,
 "MatScalarProducts: sum not divisible by group order" );
 elif IsCyc( scpr ) then
 Info( InfoCharacterTable, 2,
 "MatScalarProducts: summation not integer valued");
 fi;
 fi;
 od;
 od;
 return scprmatrix;
 end );

#############################################################################
##
#M Norm( [<tbl>, ]<chi> ) . . . . . . . . . . . . . . norm of class function
##
InstallOtherMethod( Norm,
 "for a class function",
 [ IsClassFunction ],
 chi -> ScalarProduct( chi, chi ) );

InstallOtherMethod( Norm,
 "for an ordinary character table and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, chi )
 return ScalarProduct( tbl, chi, chi );
 end );

#############################################################################
##
#M CentreOfCharacter( [<tbl>, ]<chi> ) . . . . . . . . centre of a character
##
InstallMethod( CentreOfCharacter,
 "for a class function",
 [ IsClassFunction ],
 chi -> CentreOfCharacter( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) ) );

InstallMethod( CentreOfCharacter,
 "for an ordinary table, and a homogeneous list ",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, list )
 if not HasUnderlyingGroup( tbl ) then
 Error( "<tbl> does not store its group" );
 fi;
 return NormalSubgroupClasses( tbl, ClassPositionsOfCentre( list ) );
 end );

#############################################################################
##
#M ClassPositionsOfCentre( <chi> ) . . classes in the centre of a character
##
## We know that an algebraic integer $\alpha$ is a root of unity
## if and only if all conjugates of $\alpha$ have absolute value at most 1.
## Since $\alpha^{\ast} \overline{\alpha^{\ast}} = 1$ holds for a Galois
## automorphism $\ast$ if and only if $\alpha \overline{\alpha} = 1$ holds,
## a cyclotomic integer is a root of unity iff its absolute value is $1$.
##
## Cf. the comment about the `Order' method for cyclotomics in the file
## `lib/cyclotom.g'.
##
## The `IsCyc' test is necessary to avoid errors in the case that <chi>
## contains unknowns.
##
InstallMethod( ClassPositionsOfCentre,
 "for a homogeneous list",
 [ IsHomogeneousList ],
 function( chi )
 local deg, mdeg, degsquare;

 deg:= chi[1];
 mdeg:= - deg;
 degsquare:= deg^2;

 return PositionsProperty( chi,
 x -> x = deg or x = mdeg or
 ( ( not IsInt( x ) ) and IsCyc( x ) and IsCycInt( x )
 and x * GaloisCyc( x, -1 ) = degsquare ) );
 end );

#############################################################################
##
#M ConstituentsOfCharacter( [<tbl>, ]<chi> ) . irred. constituents of <chi>
##
InstallMethod( ConstituentsOfCharacter,
 [ IsClassFunction ],
 chi -> ConstituentsOfCharacter( UnderlyingCharacterTable( chi ), chi ) );

InstallMethod( ConstituentsOfCharacter,
 "for an ordinary table, and a character",
 [ IsOrdinaryTable, IsClassFunction and IsCharacter ],
 function( tbl, chi )
 local irr, # irreducible characters of `tbl'
 values, # character values
 deg, # degree of `chi'
 const, # list of constituents, result
 i, # loop over `irr'
 irrdeg, # degree of an irred. character
 scpr; # one scalar product

 tbl:= UnderlyingCharacterTable( chi );
 irr:= Irr( tbl );
 values:= ValuesOfClassFunction( chi );
 deg:= values[1];
 const:= [];
 i:= 1;
 while 0 < deg and i <= Length( irr ) do
 irrdeg:= DegreeOfCharacter( irr[i] );
 if irrdeg <= deg then
 scpr:= ScalarProduct( tbl, chi, irr[i] );
 if scpr <> 0 then
 deg:= deg - scpr * irrdeg;
 Add( const, irr[i] );
 fi;
 fi;
 i:= i+1;
 od;

 return Set( const );
 end );

InstallMethod( ConstituentsOfCharacter,
 "for an ordinary table, and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, chi )
 local const, # list of constituents, result
 proper, # is `chi' a proper character
 i, # loop over `irr'
 scpr; # one scalar product

 const:= [];
 proper:= true;
 for i in Irr( tbl ) do
 scpr:= ScalarProduct( tbl, chi, i );
 if scpr <> 0 then
 Add( const, i );
 proper:= proper and IsPosInt( scpr );
 fi;
 od;

 # In the case `proper = true' we know that `chi' is a character.
 if proper then
 SetIsCharacter( chi, true );
 fi;

 return Set( const );
 end );

InstallMethod( ConstituentsOfCharacter,
 "for a Brauer table, and a homogeneous list",
 [ IsBrauerTable, IsHomogeneousList ],
 function( tbl, chi )
 local irr, intA, intB, dec;

 irr:= Irr( tbl );
 intA:= IntegralizedMat( irr );
 intB:= IntegralizedMat( [ chi ], intA.inforec );
 dec:= SolutionIntMat( intA.mat, intB.mat[1] );
 if dec = fail then
 Error( "<chi> is not a virtual character of <tbl>" );
 fi;

 return SortedList( irr{ Filtered( [ 1 .. Length( dec ) ],
 i -> dec[i] <> 0 ) } );
 end );

#############################################################################
##
#M DegreeOfCharacter( <chi> ) . . . . . . . . . . . . for a class function
##
InstallMethod( DegreeOfCharacter,
 "for a class function",
 [ IsClassFunction ],
 chi -> ValuesOfClassFunction( chi )[1] );

#############################################################################
##
#M InertiaSubgroup( [<tbl>, ]<G>, <chi> ) . inertia subgroup of a character
##
InstallMethod( InertiaSubgroup,
 "for a group, and a class function",
 [ IsGroup, IsClassFunction ],
 function( G, chi )
 return InertiaSubgroup( UnderlyingCharacterTable( chi ), G,
 ValuesOfClassFunction( chi ) );
 end );

InstallMethod( InertiaSubgroup,
 "for an ordinary table, a group, and a homogeneous list",
 [ IsOrdinaryTable, IsGroup, IsHomogeneousList ],
 function( tbl, G, chi )
 local H, # group of `chi'
 index, # index of `H' in `G'
 induced, # induced of `chi' from `H' to `G'
 global, # global partition of classes
 part, # refined partition
 p, # one set in `global' and `part'
 val, # one value in `p'
 values, # list of character values on `p'
 new, # list of refinements of `p'
 i, # loop over stored partitions
 pos, # position where to store new partition later
 perms, # permutations corresp. to generators of `G'
 permgrp, # group generated by `perms'
 stab; # the inertia subgroup, result

 # `G' must normalize the group of `chi'.
 H:= UnderlyingGroup( tbl );
 if not ( IsSubset( G, H ) and IsNormal( G, H ) ) then
 Error( "<H> must be a normal subgroup in <G>" );
 fi;

 # For prime index, check the norm of the induced character.
 # (We get a decision if `chi' is irreducible.)
 index:= Index( G, H );
 if IsPrimeInt( index ) then
 induced:= InducedClassFunction( tbl, chi, G );
 if ScalarProduct( CharacterTable( G ), induced, induced ) = 1 then
 return H;
 elif ScalarProduct( tbl, chi, chi ) = 1 then
 return G;
 fi;
 fi;

 # Compute the partition that must be stabilized.
#T Why is `StabilizerPartition' no longer available?
#T In GAP 3.5, there was such a function.
 # (We need only those cells where `chi' really yields a refinement.)
 global:= GlobalPartitionOfClasses( tbl );

 part:= [];
 for p in global do
#T only if `p' has length > 1 !
 val:= chi[ p[1] ];
 if ForAny( p, x -> chi[x] <> val ) then

 # proper refinement will yield a condition.
 values:= [];
 new:= [];
 for i in p do
 pos:= Position( values, chi[i] );
 if pos = fail then
 Add( values, chi[i] );
 Add( new, [ i ] );
 else
 Add( new[ pos ], i );
 fi;
 od;
 Append( part, new );

 fi;
 od;

 # If no refinement occurs, the character is necessarily invariant in <G>.
 if IsEmpty( part ) then
 return G;
 fi;

 # Compute the permutations corresponding to the generators of `G'.
 perms:= CorrespondingPermutations( tbl, chi, GeneratorsOfGroup( G ) );
 permgrp:= GroupByGenerators( perms );

 # `G' acts on the set of conjugacy classes given by each cell of `part'.
 stab:= permgrp;
 for p in part do
 stab:= Stabilizer( stab, p, OnSets );
#T Better one step (partition stabilizer) ??
 od;

 # Construct and return the result.
 if stab = permgrp then
 return G;
 else
 return PreImagesSet( GroupHomomorphismByImages( G, permgrp,
 GeneratorsOfGroup( G ), perms ),
 stab );
 fi;
 end );

#############################################################################
##
#M KernelOfCharacter( [<tbl>, ]<chi> ) . . . . . . . . for a class function
##
InstallMethod( KernelOfCharacter,
 "for a class function",
 [ IsClassFunction ],
 chi -> KernelOfCharacter( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) ) );

InstallMethod( KernelOfCharacter,
 "for an ordinary table, and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, chi )
 return NormalSubgroupClasses( tbl, ClassPositionsOfKernel( chi ) );
 end );

#############################################################################
##
#M ClassPositionsOfKernel( <char> ) . the set of classes forming the kernel
##
InstallMethod( ClassPositionsOfKernel,
 "for a homogeneous list",
 [ IsHomogeneousList ],
 function( char )
 local degree;
 degree:= char[1];
 return Filtered( [ 1 .. Length( char ) ], x -> char[x] = degree );
 end );

#############################################################################
##
#M CycleStructureClass( [<tbl>, ]<permchar>, <class> )
##
## For a permutation character $\pi$ and an element $g$ of $G$, the number
## of $n$-cycles in the underlying permutation representation is equal to
## $\frac{1}{n} \sum_{r|n} \mu(\frac{n}{r}) \pi(g^r)$.
##
InstallMethod( CycleStructureClass,
 "for a class function, and a class position",
 [ IsClassFunction, IsPosInt ],
 function( permchar, class )
 return CycleStructureClass( UnderlyingCharacterTable( permchar ),
 ValuesOfClassFunction( permchar ), class );
 end );

InstallMethod( CycleStructureClass,
 "for an ordinary table, a list, and a class position",
 [ IsOrdinaryTable, IsHomogeneousList, IsPosInt ],
 function( tbl, permchar, class )
 local n, # element order of `class'
 divs, # divisors of `n'
 i, d, j, # loop over `divs'
 fixed, # numbers of fixed points
 cycstruct; # cycle structure, result

 # Compute the numbers of fixed points of powers.
 n:= OrdersClassRepresentatives( tbl )[ class ];
 divs:= DivisorsInt( n );
 fixed:= [];
 for i in [ 1 .. Length( divs ) ] do

 # Compute the number of cycles of the element of order `n / d'.
 d:= divs[i];
 fixed[d]:= permchar[ PowerMap( tbl, d, class ) ];
 for j in [ 1 .. i-1 ] do
 if d mod divs[j] = 0 then

 # Subtract the number of fixed points with stabilizer exactly
 # of order `n / divs[j]'.
 fixed[d]:= fixed[d] - fixed[ divs[j] ];

 fi;
 od;

 od;

 # Convert these numbers into numbers of cycles.
 cycstruct:= [];
 for i in divs do
 if fixed[i] <> 0 and 1 < i then
 cycstruct[ i-1 ]:= fixed[i] / i;
 fi;
 od;

 # Return the cycle structure.
 return cycstruct;
 end );

#############################################################################
##
#M IsTransitive( [<tbl>, ]<permchar> )
##
InstallMethod( IsTransitive,
 "for a class function",
 [ IsClassFunction ],
 function( permchar )
 local tbl;
 tbl:= UnderlyingCharacterTable( permchar );
 return ValuesOfClassFunction( permchar ) * SizesConjugacyClasses( tbl )
 = Size( tbl );
 end );

InstallMethod( IsTransitive,
 "for an ordinary table and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, permchar )
 return permchar * SizesConjugacyClasses( tbl ) = Size( tbl );
 end );

#############################################################################
##
#M Transitivity( [<tbl>, ]<permchar> )
##
## The transitivity of a permutation character $\pi$ corresponding to the
## action on the $G$-set $\Omega$ is computed as follows
## (cf.~\cite{Hup98}, Theorem~11.8).
## Let $\Omega_k = \{ (\omega_1, \omega_2, \ldots, \omega_k) \mid
## \omega_i \in \Omega, \omega_i {\rm\ pairwise distinct} \}$.
## Then $\Omega_k$ is a $G$-set w.r.t.~componentwise action,
## and the permutation character $\pi_k$ is given by
## $\pi_k(g) = \pi(g) (\pi(g)-1) (\pi(g)-2) \cdots (\pi(g)-k+1)$.
## $\Omega$ is $k$-transitive if and only if $\Omega_k$ is transitive.
##
InstallMethod( Transitivity,
 "for a class function",
 [ IsClassFunction ],
 pi -> Transitivity( UnderlyingCharacterTable( pi ),
 ValuesOfClassFunction( pi ) ) );

InstallMethod( Transitivity,
 "for an ordinary table, and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, values )
 local order,
 classes,
 n,
 k,
 pik;

 # Check the argument.
 if not ForAll( values, IsInt ) then
 Error( "<values> is not integral" );
 fi;

 order:= Size( tbl );
 classes:= SizesConjugacyClasses( tbl );
 n:= Length( classes );

 k:= 1;
 pik:= values;
 while pik * classes = order do
 k:= k + 1;
 pik:= List( [ 1 .. n ], x -> pik[x] * ( values[x] - k + 1 ) );
 od;

 return k - 1;
 end );

#############################################################################
##
#M CentralCharacter( [<tbl>, ]<chi> ) . . . . . . . . . . . for a character
##
InstallMethod( CentralCharacter,
 "for a class function",
 [ IsClassFunction ],
 chi -> CentralCharacter( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) ) );

InstallMethod( CentralCharacter,
 "for an ordinary table, and a homogeneous list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, char )
 local classes;
 classes:= SizesConjugacyClasses( tbl );
 if Length( classes ) <> Length( char ) then
 Error( "<classes> and <char> must have same length" );
 fi;
 return ClassFunction( tbl, List( [ 1 .. Length( char ) ],
 x -> classes[x] * char[x] / char[1] ) );
 end );

##############################################################################
##
#M DeterminantOfCharacter( [<tbl>, ]<chi> )
##
## The determinant is computed as follows.
## Diagonalize the matrix; the determinant is the product of the diagonal
## entries, which can be computed by `Eigenvalues'.
##
## Note that the determinant of a virtual character $\chi - \psi$ is
## well-defined as the quotient of the determinants of the characters $\chi$
## and $\psi$, since the determinant of a sum of characters is the product
## of the determinants of the summands.
##
InstallMethod( DeterminantOfCharacter,
 "for a class function",
 [ IsClassFunction ],
 function( chi )
 local det;

 if chi[1] = 1 then
 return chi;
 fi;
 det:= DeterminantOfCharacter( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ) );
 if HasIsVirtualCharacter( chi ) and IsVirtualCharacter( chi ) then
 SetIsCharacter( det, true );
 fi;
 return det;
 end );

InstallMethod( DeterminantOfCharacter,
 "for a nearly character table, and a class function",
 [ IsCharacterTable, IsHomogeneousList ],
 function( tbl, chi )
 local det, # result list
 ev, # eigenvalues
 ord, # one element order
 i; # loop over classes

 if chi[1] = 1 then
 return ClassFunction( tbl, chi );
 fi;

 det:= [];

 for i in [ 1 .. Length( chi ) ] do

 ev:= EigenvaluesChar( tbl, chi, i );
 ord:= Length( ev );

 # The determinant is 'E(ord)' to the 'exp'-th power,
 # where $'exp' = \sum_{j=1}^{ord} j 'ev'[j]$.
 # (Note that the $j$-th entry in 'ev' is the multiplicity of
 # 'E(ord)^j' as eigenvalue.)
 det[i]:= E(ord) ^ ( [ 1 .. ord ] * ev );

 od;

 return ClassFunction( tbl, det );
 end );

#############################################################################
##
#M EigenvaluesChar( [<tbl>, ]<char>, <class> )
##
## The eigenvalues can be computed from the values of the character
## <char> together with the power maps up to the order of elements in the
## <class>-th class of <tbl>, see page~231 in~\cite{NPP84};
## note that the multiplicity of a given $n$-th root of unity $\zeta$
## as an eigenvalue of $M$ is equal to the multiplicity of the irreducible
## character of the cyclic group spanned by $g$ that maps $g$ to $\zeta$,
## and this can be computed from the restriction of <char> to this cyclic
## subgroup or, equivalently, by the power maps of <tbl>.
##
#T > I would like to know if there is a quicker way to compute the
#T > characteristic polynomial f=f(G) of a representative G
#T > of a conjugacy class mentioned
#T > above, than using Eigenvalues().
#T > (The latter function involves using algebraic numbers,
#T > whereas it might happen
#T > that f has rational or integer coefficients ,
#T > i.e. all the irrationalies cancel)
#T
#T For example, if the character values in question are rational
#T one can use Galois sums of the irreducible characters of the cyclic
#T subgroup instead of the irreducible characters when computing
#T scalar products,
#T because the multiplicities of Galois conjugate eigenvalues are equal
#T in such a case.
#T This avoids computations with non-rational numbers.
##
InstallMethod( EigenvaluesChar,
 "for a class function and a positive integer",
 [ IsClassFunction, IsPosInt ],
 function( chi, class )
 return EigenvaluesChar( UnderlyingCharacterTable( chi ),
 ValuesOfClassFunction( chi ), class );
 end );

InstallMethod( EigenvaluesChar,
 "for a character table and a hom. list, and a pos.",
 [ IsCharacterTable, IsHomogeneousList, IsPosInt ],
 function( tbl, char, class )
 local i, j, n, powers, eigen, e, val;

 n:= OrdersClassRepresentatives( tbl )[ class ];
 if n = 1 then return [ char[ class ] ]; fi;

 # Compute necessary power maps and the restricted character.
 powers:= [];
 powers[n]:= char[1];
 for i in [ 1 .. n-1 ] do
 if not IsBound( powers[i] ) then

 # necessarily 'i' divides 'n', since 'i/Gcd(n,i)' is invertible
 # mod 'n', and thus powering with 'i' is Galois conjugate to
 # powering with 'Gcd(n,i)'
 powers[i]:= char[ PowerMap( tbl, i, class ) ];
#T better approach:
#T only write down values for one representative of each
#T Galois family, and compute traces;
#T for rational characters, this avoids computation with
#T non-rational values at all.
#T (how much does this help?)
 for j in PrimeResidues( n/i ) do

 # Note that the position cannot be 0.
 powers[ ( i*j ) mod n ]:= GaloisCyc( powers[i], j );
 od;
 fi;
 od;

 # compute the scalar products of the characters given by 'E(n)->E(n)^i'
 # with the restriction of <char> to the cyclic group generated by
 # <class>
 eigen:= [];
 for i in [ 1 .. n ] do
 e:= E(n)^(-i);
 val:= 0;
 for j in [ 1 .. n ] do val:= val + e^j * powers[j]; od;
 eigen[i]:= val / n;
 od;

 return eigen;
 end );

#############################################################################
##
#M Tensored( <chars1>, <chars2> ) . . . . for two lists of class functions
##
InstallMethod( Tensored,
 "method for two homogeneous lists",
 [ IsHomogeneousList, IsHomogeneousList ],
 function( chars1, chars2 )
 local i, j, k, nccl, tensored, single;

 if IsEmpty( chars1 ) or IsEmpty( chars2 ) then
 return [];
 fi;

 nccl:= Length( chars1[1] );
 tensored:= [];

 for i in chars1 do
 for j in chars2 do

 single:= [];
 for k in [ 1 .. nccl ] do
 single[k]:= i[k] * j[k];
 od;

 if HasIsCharacter( i ) and IsCharacter( i ) and
 HasIsCharacter( j ) and IsCharacter( j ) and
 UnderlyingCharacterTable( i ) = UnderlyingCharacterTable( j ) then
 single:= Character( UnderlyingCharacterTable( i ), single );
 elif HasIsVirtualCharacter( i ) and IsVirtualCharacter( i ) and
 HasIsVirtualCharacter( j ) and IsVirtualCharacter( j ) and
 UnderlyingCharacterTable( i ) = UnderlyingCharacterTable( j ) then
 single:= VirtualCharacter( UnderlyingCharacterTable( i ), single );
 elif IsClassFunction( i ) and IsClassFunction( j ) and
 UnderlyingCharacterTable( i ) = UnderlyingCharacterTable( j ) then
 single:= ClassFunction( UnderlyingCharacterTable( i ), single );
 fi;

 Add( tensored, single );

 od;
 od;

 return tensored;
 end );

#############################################################################
##
#M TensorProductOp( <chi>, <psi> )
##
InstallMethod( TensorProductOp,
 "for a list of class functions and a class function",
 [ IsDenseList, IsClassFunction ],
 function( list, chi )
 if Length( list ) = 0 then
 return One( chi );
 else
 return Iterated( list, \* );
 fi;
 end );

#############################################################################
##
## 9. Restricted and Induced Class Functions
##

#############################################################################
##
#M RestrictedClassFunction( [<tbl>, ]<chi>, <H> )
#M RestrictedClassFunction( [<tbl>, ]<chi>, <hom> )
#M RestrictedClassFunction( [<tbl>, ]<chi>, <subtbl> )
##
InstallMethod( RestrictedClassFunction,
 "for a class function, and a group",
 [ IsClassFunction, IsGroup ],
 function( chi, H )
 local subtbl, tbl, fus;

 subtbl:= OrdinaryCharacterTable( H );
 tbl:= UnderlyingCharacterTable( chi );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 subtbl:= subtbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( subtbl, tbl );
 if fus = fail then
 Error( "no fusion from <subtbl> to <tbl>" );
 fi;
 return ClassFunctionSameType( subtbl, chi, chi{ fus } );
 end );

InstallMethod( RestrictedClassFunction,
 "for a character table, a homogeneous list, and a group",
 [ IsNearlyCharacterTable, IsHomogeneousList, IsGroup ],
 function( tbl, chi, H )
 local subtbl, fus;

 subtbl:= OrdinaryCharacterTable( H );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 subtbl:= subtbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( subtbl, tbl );
 if fus = fail then
 Error( "no fusion from <subtbl> to <tbl>" );
 fi;
 return ClassFunction( subtbl, chi{ fus } );
 end );

InstallMethod( RestrictedClassFunction,
 "for a class function and a group homomorphism",
 [ IsClassFunction, IsGeneralMapping ],
 function( chi, hom )
 local tbl, subtbl, fus;

 subtbl:= CharacterTable( PreImage( hom ) );
 tbl:= UnderlyingCharacterTable( chi );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 subtbl:= subtbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( hom, subtbl, tbl );
 if fus = fail then
 Error( "no fusion from <subtbl> to <tbl>" );
 fi;
 return ClassFunctionSameType( subtbl, chi,
 ValuesOfClassFunction( chi ){ fus } );
 end );

InstallMethod( RestrictedClassFunction,
 "for a character table, a homogeneous list, and a group homomorphism",
 [ IsNearlyCharacterTable, IsHomogeneousList, IsGeneralMapping ],
 function( tbl, chi, hom )
 local subtbl, fus;

 subtbl:= CharacterTable( PreImage( hom ) );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 subtbl:= subtbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( hom, subtbl, tbl );
 if fus = fail then
 Error( "no fusion from <subtbl> to <tbl>" );
 fi;
 return ClassFunction( subtbl, chi{ fus } );
 end );

InstallMethod( RestrictedClassFunction,
 "for class function and nearly character table",
 [ IsClassFunction, IsNearlyCharacterTable ],
 function( chi, subtbl )
 local fus;

 fus:= FusionConjugacyClasses( subtbl, UnderlyingCharacterTable( chi ) );
 if fus = fail then
 Error( "class fusion not available" );
 fi;
 return ClassFunctionSameType( subtbl, chi,
 ValuesOfClassFunction( chi ){ fus } );
 end );

InstallMethod( RestrictedClassFunction,
 "for a character table, a homogeneous list, and a character table",
 [ IsNearlyCharacterTable, IsHomogeneousList, IsNearlyCharacterTable ],
 function( tbl, chi, subtbl )
 local fus;

 fus:= FusionConjugacyClasses( subtbl, tbl );
 if fus = fail then
 Error( "class fusion not available" );
 fi;
 return ClassFunction( subtbl, chi{ fus } );
 end );

#############################################################################
##
#M RestrictedClassFunctions( [<tbl>, ]<chars>, <H> )
#M RestrictedClassFunctions( [<tbl>, ]<chars>, <hom> )
#M RestrictedClassFunctions( [<tbl>, ]<chars>, <subtbl> )
##
InstallMethod( RestrictedClassFunctions,
 "for list and group",
 [ IsList, IsGroup ],
 function( chars, H )
 return List( chars, chi -> RestrictedClassFunction( chi, H ) );
 end );

InstallMethod( RestrictedClassFunctions,
 "for list and group homomorphism",
 [ IsList, IsGeneralMapping ],
 function( chars, hom )
 return List( chars, chi -> RestrictedClassFunction( chi, hom ) );
 end );

InstallMethod( RestrictedClassFunctions,
 "for list and character table",
 [ IsList, IsCharacterTable ],
 function( chars, subtbl )
 return List( chars, chi -> RestrictedClassFunction( chi, subtbl ) );
 end );

InstallMethod( RestrictedClassFunctions,
 "for a character table, a list, and a group",
 [ IsCharacterTable, IsList, IsGroup ],
 function( tbl, chars, H )
 local subtbl, fus;

 subtbl:= OrdinaryCharacterTable( H );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 subtbl:= subtbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( subtbl, tbl );
 if fus = fail then
 Error( "no fusion from <subtbl> to <tbl>" );
 fi;
 return List( chars, chi -> ClassFunctionSameType( subtbl, chi,
 ValuesOfClassFunction( chi ){ fus } ) );
 end );

InstallMethod( RestrictedClassFunctions,
 "for a character table, a list, and a group homomorphism",
 [ IsCharacterTable, IsList, IsGeneralMapping ],
 function( tbl, chars, hom )
 local subtbl, fus;

 subtbl:= CharacterTable( PreImage( hom ) );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 subtbl:= subtbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( hom, subtbl, tbl );
 if fus = fail then
 Error( "class fusion not available" );
 fi;
 return List( chars, chi -> ClassFunctionSameType( subtbl, chi,
 ValuesOfClassFunction( chi ){ fus } ) );
 end );

InstallMethod( RestrictedClassFunctions,
 "for a character table, a list, and a character table",
 [ IsCharacterTable, IsList, IsCharacterTable ],
 function( tbl, chars, subtbl )
 local fus;

 fus:= FusionConjugacyClasses( subtbl, tbl );
 if fus = fail then
 Error( "class fusion not available" );
 fi;
 return List( chars, chi -> ClassFunctionSameType( subtbl, chi,
 ValuesOfClassFunction( chi ){ fus } ) );
 end );

#############################################################################
##
#M Restricted( <tbl>, <subtbl>, <chars> )
#M Restricted( <tbl>, <subtbl>, <chars>, <specification> )
#M Restricted( <chars>, <fusionmap> )
##
## These methods are installed just for compatibility with {\GAP}~3.
##
InstallMethod( Restricted,
 [ IsNearlyCharacterTable, IsNearlyCharacterTable, IsHomogeneousList ],
 function( tbl, subtbl, chars )
 local fus;

 fus:= FusionConjugacyClasses( subtbl, tbl );
 if fus = fail then
 Error( "class fusion not available" );
 fi;
 return List( chars, row -> ClassFunction( subtbl, row{ fus } ) );
 end );

InstallMethod( Restricted,
 [ IsNearlyCharacterTable, IsNearlyCharacterTable, IsMatrix, IsObject ],
 function( tbl, subtbl, chars, specification )
 local fus;

 fus:= GetFusionMap( subtbl, tbl, specification );
 if fus = fail then
 Error( "class fusion not available" );
 fi;
 return List( chars, row -> ClassFunction( subtbl, row{ fus } ) );
 end );

InstallMethod( Restricted,
 [ IsList, IsList and IsCyclotomicCollection ],
 function( mat, fus )
 if ForAll( mat, IsList ) then
 return List( mat, row -> row{ fus } );
 fi;
 Error( "<mat> must be a matrix" );
 end );

#############################################################################
##
#M Restricted( [<tbl>, ]<chi>, <H> )
#M Restricted( [<tbl>, ]<chi>, <hom> )
#M Restricted( [<tbl>, ]<chi>, <tbl> )
#M Restricted( [<tbl>, ]<chars>, <H> )
#M Restricted( [<tbl>, ]<chars>, <hom> )
#M Restricted( [<tbl>, ]<chars>, <tbl> )
##
InstallMethod( Restricted,
 [ IsClassFunction, IsGroup ],
 RestrictedClassFunction );

InstallMethod( Restricted,
 [ IsCharacterTable, IsHomogeneousList, IsGroup ],
 function( tbl, list, H )
 if IsMatrix( list ) then
 return RestrictedClassFunctions( tbl, list, H );
 else
 return RestrictedClassFunction( tbl, list, H );
 fi;
 end );

InstallMethod( Restricted,
 [ IsClassFunction, IsGroupHomomorphism ],
 RestrictedClassFunction );

InstallMethod( Restricted,
 [ IsCharacterTable, IsClassFunction, IsGroupHomomorphism ],
 function( tbl, list, hom )
 if IsMatrix( list ) then
 return RestrictedClassFunctions( tbl, list, hom );
 else
 return RestrictedClassFunction( tbl, list, hom );
 fi;
 end );

InstallMethod( Restricted,
 [ IsClassFunction, IsNearlyCharacterTable ],
 RestrictedClassFunction );

InstallMethod( Restricted,
 [ IsCharacterTable, IsClassFunction, IsNearlyCharacterTable ],
 function( tbl, list, subtbl )
 if IsMatrix( list ) then
 return RestrictedClassFunctions( tbl, list, subtbl );
 else
 return RestrictedClassFunction( tbl, list, subtbl );
 fi;
 end );

InstallMethod( Restricted,
 [ IsHomogeneousList, IsGroup ],
 function( list, H )
 if ForAll( list, IsClassFunction ) then
 return RestrictedClassFunctions( list, H );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( Restricted,
 [ IsHomogeneousList, IsGroupHomomorphism ],
 function( list, hom )
 if ForAll( list, IsClassFunction ) then
 return RestrictedClassFunctions( list, hom );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( Restricted,
 [ IsHomogeneousList, IsNearlyCharacterTable ],
 function( list, subtbl )
 if ForAll( list, IsClassFunction ) then
 return RestrictedClassFunctions( list, subtbl );
 else
 TryNextMethod();
 fi;
 end );

#############################################################################
##
#F InducedClassFunctionsByFusionMap( <subtbl>, <tbl>, <chars>, <fusionmap> )
##
InstallGlobalFunction( InducedClassFunctionsByFusionMap,
 function( subtbl, tbl, chars, fusion )
 local j, im, # loop variables
 centralizers, # centralizer orders in the supergroup
 nccl, # number of conjugacy classes of the group
 subnccl, # number of conjugacy classes of the subgroup
 suborder, # order of the subgroup
 subclasses, # class lengths in the subgroup
 induced, # list of induced characters, result
 singleinduced, # one induced character
 char; # one character to be induced

 if fusion = fail then
 return fail;
 fi;

 centralizers:= SizesCentralizers( tbl );
 nccl:= Length( centralizers );
 suborder:= Size( subtbl );
 subclasses:= SizesConjugacyClasses( subtbl );
 subnccl:= Length( subclasses );

 induced:= [];

 for char in chars do

 # Preset the character with zeros.
 singleinduced:= ListWithIdenticalEntries( nccl, 0 );

 # Add the contribution of each class of the subgroup.
 for j in [ 1 .. subnccl ] do
 if char[j] <> 0 then
 if IsInt( fusion[j] ) then
 singleinduced[ fusion[j] ]:= singleinduced[ fusion[j] ]
 + char[j] * subclasses[j];
 else
 for im in fusion[j] do singleinduced[ im ]:= Unknown(); od;
#T only for TableInProgress!
 fi;
 fi;
 od;

 # Adjust the values by multiplication.
 for j in [ 1 .. nccl ] do
 singleinduced[j]:= singleinduced[j] * centralizers[j] / suborder;
 if not IsCycInt( singleinduced[j] ) then
 singleinduced[j]:= Unknown();
 Info( InfoCharacterTable, 1,
 "Induced: subgroup order not dividing sum in character ",
 Length( induced ) + 1, " at class ", j );
 fi;
 od;

 # Create the class function object.
 if IsClassFunction( char ) then
 singleinduced:= ClassFunctionSameType( tbl, char, singleinduced );
 else
 singleinduced:= ClassFunction( tbl, singleinduced );
 fi;

 Add( induced, singleinduced );

 od;

 # Return the list of induced characters.
 return induced;
end );

#############################################################################
##
#M InducedClassFunction( [<tbl>, ]<chi>, <H> )
#M InducedClassFunction( [<tbl>, ]<chi>, <hom> )
#M InducedClassFunction( [<tbl>, ]<chi>, <suptbl> )
##
InstallMethod( InducedClassFunction,
 "for a class function and a group",
 [ IsClassFunction, IsGroup ],
 function( chi, G )
 local tbl, suptbl, fus;
 tbl:= UnderlyingCharacterTable( chi );
 suptbl:= OrdinaryCharacterTable( G );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 suptbl:= suptbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, [ chi ], fus )[1];
 end );

InstallMethod( InducedClassFunction,
 "for a character table, a homogeneous list, and a group",
 [ IsCharacterTable, IsHomogeneousList, IsGroup ],
 function( tbl, chi, G )
 local suptbl, fus;
 suptbl:= OrdinaryCharacterTable( G );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 suptbl:= suptbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, [ chi ], fus )[1];
 end );

InstallMethod( InducedClassFunction,
 "for class function and nearly character table",
 [ IsClassFunction, IsNearlyCharacterTable ],
 function( chi, suptbl )
 local tbl, fus;
 tbl:= UnderlyingCharacterTable( chi );
 fus:= FusionConjugacyClasses( tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, [ chi ], fus )[1];
 end );

InstallMethod( InducedClassFunction,
 "for character table, homogeneous list, and nearly character table",
 [ IsCharacterTable, IsHomogeneousList, IsNearlyCharacterTable ],
 function( tbl, chi, suptbl )
 local fus;
 fus:= FusionConjugacyClasses( tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, [ chi ], fus )[1];
 end );

InstallMethod( InducedClassFunction,
 "for a class function and a group homomorphism",
 [ IsClassFunction, IsGeneralMapping ],
 function( chi, hom )
 local tbl, suptbl, fus;
 tbl:= UnderlyingCharacterTable( chi );
 suptbl:= OrdinaryCharacterTable(Image( hom ));
 if UnderlyingCharacteristic( tbl ) <> 0 then
 suptbl:= suptbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( hom, tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, [ chi ], fus )[1];
 end );

InstallMethod( InducedClassFunction,
 "for a character table, a homogeneous list, and a group homomorphism",
 [ IsCharacterTable, IsHomogeneousList, IsGeneralMapping ],
 function( tbl, chi, hom )
 local suptbl, fus;
 suptbl:= OrdinaryCharacterTable(Image( hom ));
 if UnderlyingCharacteristic( tbl ) <> 0 then
 suptbl:= suptbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( hom, tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, [ chi ], fus )[1];
 end );

#############################################################################
##
#M InducedClassFunctions( [<tbl>, ]<chars>, <H> )
#M InducedClassFunctions( [<tbl>, ]<chars>, <hom> )
#M InducedClassFunctions( [<tbl>, ]<chars>, <suptbl> )
##
InstallMethod( InducedClassFunctions,
 "for list, and group",
 [ IsList, IsGroup ],
 function( chars, H )
 return List( chars, chi -> InducedClassFunction( chi, H ) );
 end );

InstallMethod( InducedClassFunctions,
 "for list, and group homomorphism",
 [ IsList, IsGeneralMapping ],
 function( chars, hom )
 return List( chars, chi -> InducedClassFunction( chi, hom ) );
 end );

InstallMethod( InducedClassFunctions,
 "for list, and group homomorphism",
 [ IsList, IsCharacterTable ],
 function( chars, suptbl )
 return List( chars, chi -> InducedClassFunction( chi, suptbl ) );
 end );

InstallMethod( InducedClassFunctions,
 "for a character table, a homogeneous list, and a group",
 [ IsCharacterTable, IsHomogeneousList, IsGroup ],
 function( tbl, chars, G )
 local suptbl, fus;
 suptbl:= OrdinaryCharacterTable( G );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 suptbl:= suptbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, chars, fus );
 end );

InstallMethod( InducedClassFunctions,
 "for character table, homogeneous list, and nearly character table",
 [ IsCharacterTable, IsHomogeneousList, IsNearlyCharacterTable ],
 function( tbl, chars, suptbl )
 local fus;
 fus:= FusionConjugacyClasses( tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, chars, fus );
 end );

InstallMethod( InducedClassFunctions,
 "for a character table, a homogeneous list, and a group homomorphism",
 [ IsCharacterTable, IsHomogeneousList, IsGeneralMapping ],
 function( tbl, chars, hom )
 local suptbl, fus;
 suptbl:= Image( hom );
 if UnderlyingCharacteristic( tbl ) <> 0 then
 suptbl:= suptbl mod UnderlyingCharacteristic( tbl );
 fi;
 fus:= FusionConjugacyClasses( hom, tbl, suptbl );
 return InducedClassFunctionsByFusionMap( tbl, suptbl, chars, fus );
 end );

#############################################################################
##
#M Induced( [<tbl>, ]<chi>, <H> )
#M Induced( [<tbl>, ]<chi>, <hom> )
#M Induced( [<tbl>, ]<chi>, <suptbl> )
#M Induced( [<tbl>, ]<chars>, <H> )
#M Induced( [<tbl>, ]<chars>, <hom> )
#M Induced( [<tbl>, ]<chars>, <suptbl> )
##
InstallMethod( Induced,
 [ IsClassFunction, IsGroup ],
 InducedClassFunction );

InstallMethod( Induced,
 [ IsCharacterTable, IsHomogeneousList, IsGroup ],
 function( tbl, list, H )
 if IsMatrix( list ) then
 return InducedClassFunctions( tbl, list, H );
 else
 return InducedClassFunction( tbl, list, H );
 fi;
 end );

InstallMethod( Induced,
 [ IsClassFunction, IsGroupHomomorphism ],
 InducedClassFunction );

InstallMethod( Induced,
 [ IsCharacterTable, IsHomogeneousList, IsGroupHomomorphism ],
 function( tbl, list, hom )
 if IsMatrix( list ) then
 return InducedClassFunctions( tbl, list, hom );
 else
 return InducedClassFunction( tbl, list, hom );
 fi;
 end );

InstallMethod( Induced,
 [ IsClassFunction, IsNearlyCharacterTable ],
 InducedClassFunction );

InstallMethod( Induced,
 [ IsCharacterTable, IsHomogeneousList, IsNearlyCharacterTable ],
 function( tbl, list, suptbl )
 if IsMatrix( list ) then
 return InducedClassFunctions( tbl, list, suptbl );
 else
 return InducedClassFunction( tbl, list, suptbl );
 fi;
 end );

InstallMethod( Induced,
 [ IsHomogeneousList, IsGroup ],
 function( list, H )
 if ForAll( list, IsClassFunction ) then
 return InducedClassFunctions( list, H );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( Induced,
 [ IsHomogeneousList, IsGeneralMapping ],
 function( list, hom )
 if ForAll( list, IsClassFunction ) then
 return InducedClassFunctions( list, hom );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( Induced,
 [ IsHomogeneousList, IsCharacterTable ],
 function( list, suptbl )
 if ForAll( list, IsClassFunction ) then
 return InducedClassFunctions( list, suptbl );
 else
 TryNextMethod();
 fi;
 end );

#############################################################################
##
#M Induced( <subtbl>, <tbl>, <chars> )
#M Induced( <subtbl>, <tbl>, <chars>, <specification> )
#M Induced( <subtbl>, <tbl>, <chars>, <fusionmap> )
##
## These methods are installed just for compatibility with {\GAP}~3.
##
InstallMethod( Induced,
 "for two nearly character tables, and homog list",
 [ IsNearlyCharacterTable, IsNearlyCharacterTable, IsHomogeneousList ],
 function( subtbl, tbl, chars )
 return InducedClassFunctionsByFusionMap( subtbl, tbl, chars,
 FusionConjugacyClasses( subtbl, tbl ) );
 end );

InstallMethod( Induced,
 "for two nearly character tables, homog list, and string",
 [ IsNearlyCharacterTable, IsNearlyCharacterTable,
 IsHomogeneousList, IsString ],
 function( subtbl, tbl, chars, specification )
 return InducedClassFunctionsByFusionMap( subtbl, tbl, chars,
 FusionConjugacyClasses( subtbl, tbl, specification ) );
 end );

InstallMethod( Induced,
 "for two nearly character tables and two homog. lists",
 [ IsNearlyCharacterTable, IsNearlyCharacterTable,
 IsHomogeneousList, IsHomogeneousList and IsCyclotomicCollection ],
 InducedClassFunctionsByFusionMap );

#############################################################################
##
#M InducedCyclic( <tbl> )
#M InducedCyclic( <tbl>, \"all\" )
#M InducedCyclic( <tbl>, <classes> )
#M InducedCyclic( <tbl>, <classes>, \"all\" )
##
InstallMethod( InducedCyclic,
 "for a character table",
 [ IsOrdinaryTable ],
 tbl -> InducedCyclic( tbl, [ 1 .. NrConjugacyClasses( tbl ) ] ) );

InstallMethod( InducedCyclic,
 "for a character table and a string",
 [ IsOrdinaryTable, IsString ],
 # The `string' should overrule over the `homogeneous list' installed in
 # the next method
 1,
 function( tbl, all )
 return InducedCyclic( tbl, [ 1 .. NrConjugacyClasses( tbl ) ], all );
 end );

InstallMethod( InducedCyclic,
 "for a character table and a hom. list",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( tbl, classes )
 local centralizers,
 orders,
 independent,
 inducedcyclic,
 i,
 fusion,
 j,
 single;

 if HasUnderlyingGroup( tbl ) then
 # Precompute the power maps if possible.
 ComputeAllPowerMaps( tbl );
 fi;

 centralizers:= SizesCentralizers( tbl );
 orders:= OrdersClassRepresentatives( tbl );
 independent:= List( orders, ReturnTrue );
 inducedcyclic:= [];
 for i in classes do # induce from i-th class
 if independent[i] then
 fusion:= [ i ];
 for j in [ 2 .. orders[i] ] do
 fusion[j]:= PowerMap( tbl, j, i ); # j-th powermap at class i
 od;
 single:= ListWithIdenticalEntries(Length(orders),0);
 for j in fusion do
 if orders[j] = orders[i] then
 # position is Galois conjugate to 'i'
 independent[j]:= false;
 fi;
 single[j]:= single[j] + 1;
 od;
 for j in [ 1 .. Length( orders ) ] do
 single[j]:= single[j] * centralizers[j] / orders[i];
 if not IsInt( single[j] ) then
 single[j]:= Unknown();
 Info( InfoCharacterTable, 1,
 "InducedCyclic: subgroup order not dividing sum",
 " (induce from class ", i, ")" );
 fi;
 od;
 AddSet( inducedcyclic, Character( tbl, single ) );
 fi;
 od;
 return inducedcyclic;
 end );

InstallMethod( InducedCyclic,
 "for a character table, a hom. list, and a string",
 [ IsOrdinaryTable, IsHomogeneousList, IsString ],
 function( tbl, classes, all )
 local centralizers,
 orders,
 independent,
 inducedcyclic,
 i,
 fusion,
 j,
 k,
 single;

 centralizers:= SizesCentralizers( tbl );
 orders:= OrdersClassRepresentatives( tbl );
 independent:= List( orders, ReturnTrue );
 inducedcyclic:= [];
 for i in classes do # induce from i-th class
 if independent[i] then
 fusion:= [ i ];
 for j in [ 2 .. orders[i] ] do
 fusion[j]:= PowerMap( tbl, j, i ); # j-th powermap at class i
 od;

 for k in [ 0 .. orders[i] - 1 ] do # induce k-th character
 single:= ListWithIdenticalEntries(Length(orders),0);
 single[i]:= E( orders[i] ) ^ ( k );
 for j in [ 2 .. orders[i] ] do
 if orders[ fusion[j] ] = orders[i] then

 # position is Galois conjugate
 independent[ fusion[j] ]:= false;
 fi;
 single[ fusion[j] ]:=
 single[ fusion[j] ] + E( orders[i] )^( k*j mod orders[i] );
 od;
 for j in [ 1 .. Length( orders ) ] do
 single[j]:= single[j] * centralizers[j] / orders[i];
 if not IsCycInt( single[j] ) then
 single[j]:= Unknown();
 Info( InfoCharacterTable, 1,
 "InducedCyclic: subgroup order not dividing sum",
 " (induce from class ", i, ")" );
 fi;
 od;
 AddSet( inducedcyclic, Character( tbl, single ) );
 od;
 fi;
 od;
 return inducedcyclic;
 end );

#############################################################################
##
## 10. Reducing Virtual Characters
##

#############################################################################
##
#M ReducedClassFunctions( [<ordtbl>, ]<constituents>, <reducibles> )
#M ReducedClassFunctions( [<ordtbl>, ]<reducibles> )
##
InstallMethod( ReducedClassFunctions,
 "for two lists (of class functions)",
 [ IsHomogeneousList, IsHomogeneousList ],
 function( constituents, reducibles )
 if IsEmpty( constituents ) then
 return rec( irreducibles:= [],
 remainders:= ShallowCopy( reducibles ) );
 elif IsClassFunction( constituents[1] ) then
 return ReducedClassFunctions(
 UnderlyingCharacterTable( constituents[1] ),
 constituents, reducibles );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( ReducedClassFunctions,
 "for a list (of class functions)",
 [ IsHomogeneousList ],
 function( reducibles )
 if IsEmpty( reducibles ) then
 return rec( irreducibles:= [],
 remainders:= [] );
 elif IsClassFunction( reducibles[1] ) then
 return ReducedClassFunctions(
 UnderlyingCharacterTable( reducibles[1] ),
 reducibles );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( ReducedClassFunctions,
 "for ordinary character table, and two lists (of class functions)",
 [ IsOrdinaryTable, IsHomogeneousList , IsHomogeneousList ],
 function( ordtbl, constituents, reducibles )
 local i, j,
 normsquare,
 upper,
 found, # list of found irreducible characters
 remainders, # list of reducible remainders after reduction
 single,
 reduced,
 scpr;

 upper:= Length( constituents );
 upper:= List( reducibles, x -> upper );
 normsquare:= List( constituents, x -> ScalarProduct( ordtbl, x, x ) );
 found:= [];
 remainders:= [];

 for i in [ 1 .. Length( reducibles ) ] do
 single:= reducibles[i];

 j:=1;
 while j<=upper[i] do
 scpr:= ScalarProduct( ordtbl, single, constituents[j] );
 if IsInt( scpr ) then
 scpr:= Int( scpr / normsquare[j] );
 if scpr <> 0 then
 single:= single - scpr * constituents[j];
 if ForAll(single,x->x=0) then
 j:=upper[i];
 fi;
 fi;
 else
 Info( InfoCharacterTable, 1,
 "ReducedClassFunctions: scalar product of X[", j,
 "] with Y[", i, "] not integral (ignore)" );
 fi;
 j:=j+1;
 od;
 if ForAny( single, x -> x <> 0 ) then
 if single[1] < 0 then
 single:= - single;
 fi;
 if ScalarProduct( ordtbl, single, single ) = 1 then
 if not single in found and not single in constituents then
 Info( InfoCharacterTable, 2,
 "ReducedClassFunctions: irreducible character of degree ",
 single[1], " found" );
 if IsClassFunction( single ) then
 SetIsCharacter( single, true );
 fi;
 AddSet( found, single );
 fi;
 else
 AddSet( remainders, single );
 fi;
 fi;
 od;

 # If no irreducibles were found, return the remainders.
 if IsEmpty( found ) then
 return rec( remainders:= remainders, irreducibles:= [] );
 fi;

 # Try to find new irreducibles by recursively calling the reduction.
 reduced:= ReducedClassFunctions( ordtbl, found, remainders );

 # Return the result.
 return rec( remainders:= reduced.remainders,
 irreducibles:= Union( found, reduced.irreducibles ) );
 end );

InstallMethod( ReducedClassFunctions,
 "for ordinary character table, and list of class functions",
 [ IsOrdinaryTable, IsHomogeneousList ],
 function( ordtbl, reducibles )
 local upper,
 normsquare,
 found, # list of found irreducible characters
 remainders, # list of reducible remainders after reduction
 i, j,
 single,
 reduced,
 scpr;

 upper:= [ 0 .. Length( reducibles ) - 1 ];
 normsquare:= List( reducibles, x -> ScalarProduct( ordtbl, x, x ) );
 found:= [];
 remainders:= [];

 for i in [ 1 .. Length( reducibles ) ] do
 if normsquare[i] = 1 then
 if 0 < reducibles[i][1] then
 AddSet( found, reducibles[i] );
 else
 AddSet( found, - reducibles[i] );
 fi;
 fi;
 od;

 for i in [ 1 .. Length( reducibles ) ] do
 single:= reducibles[i];
 for j in [ 1 .. upper[i] ] do
 scpr:= ScalarProduct( ordtbl, single, reducibles[j] );
 if IsInt( scpr ) then
 scpr:= Int( scpr / normsquare[j] );
 if scpr <> 0 then
 single:= single - scpr * reducibles[j];
 fi;
 else
 Info( InfoCharacterTable, 1,
 "ReducedClassFunctions: scalar product of X[", j,
 "] with Y[", i, "] not integral (ignore)" );
 fi;
 od;
 if ForAny( single, x -> x <> 0 ) then
 if single[1] < 0 then
 single:= - single;
 fi;
 if ScalarProduct( ordtbl, single, single ) = 1 then
 if not single in found and not single in reducibles then
 Info( InfoCharacterTable, 2,
 "ReducedClassFunctions: irreducible character of degree ",
 single[1], " found" );
 if IsClassFunction( single ) then
 SetIsCharacter( single, true );
 fi;
 AddSet( found, single );
 fi;
 else
 AddSet( remainders, single );
 fi;
 fi;
 od;

 # If no irreducibles were found, return the remainders.
 if IsEmpty( found ) then
 return rec( remainders:= remainders, irreducibles:= [] );
 fi;

 # Try to find new irreducibles by recursively calling the reduction.
 reduced:= ReducedClassFunctions( ordtbl, found, remainders );

 # Return the result.
 return rec( remainders:= reduced.remainders,
 irreducibles:= Union( found, reduced.irreducibles ) );
 end );

#############################################################################
##
#M ReducedCharacters( [<ordtbl>, ]<constituents>, <reducibles> )
##
InstallMethod( ReducedCharacters,
 "for two lists (of characters)",
 [ IsHomogeneousList , IsHomogeneousList ],
 function( constituents, reducibles )
 if IsEmpty( constituents ) then
 return rec( irreducibles:= [],
 remainders:= ShallowCopy( reducibles ) );
 elif IsClassFunction( constituents[1] ) then
 return ReducedCharacters(
 UnderlyingCharacterTable( constituents[1] ),
 constituents, reducibles );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( ReducedCharacters,
 "for ordinary character table, and two lists of characters",
 [ IsOrdinaryTable, IsHomogeneousList , IsHomogeneousList ],
 function( ordtbl, constituents, reducibles )
 local normsquare,
 found,
 remainders,
 single,
 i, j,
 nchars,
 reduced,
 scpr;

 normsquare:= List( constituents, x -> ScalarProduct( ordtbl, x, x ) );
 found:= [];
 remainders:= [];
 nchars:= Length( constituents );
 for i in [ 1 .. Length( reducibles ) ] do

 single:= reducibles[i];
 for j in [ 1 .. nchars ] do
 if constituents[j][1] <= single[1] then
 scpr:= ScalarProduct( ordtbl, single, constituents[j] );
 if IsInt( scpr ) then
 scpr:= Int( scpr / normsquare[j] );
 if scpr <> 0 then
 single:= single - scpr * constituents[j];
 fi;
 else
 Info( InfoCharacterTable, 1,
 "ReducedCharacters: scalar product of X[", j, "] with Y[",
 i, "] not integral (ignore)" );
 fi;
 fi;
 od;

 if ForAny( single, x -> x <> 0 ) then
 if ScalarProduct( ordtbl, single, single ) = 1 then
 if single[1] < 0 then single:= - single; fi;
 if not single in found and not single in constituents then
 Info( InfoCharacterTable, 2,
 "ReducedCharacters: irreducible character of",
 " degree ", single[1], " found" );
 if IsClassFunction( single ) then
 SetIsCharacter( single, true );
 fi;
 AddSet( found, single );
 fi;
 else
 AddSet( remainders, single );
 fi;
 fi;

 od;

 # If no irreducibles were found, return the remainders.
 if IsEmpty( found ) then
 return rec( remainders:= remainders, irreducibles:= [] );
 fi;

 # Try to find new irreducibles by recursively calling the reduction.
 reduced:= ReducedCharacters( ordtbl, found, remainders );

 # Return the result.
 return rec( remainders:= reduced.remainders,
 irreducibles:= Union( found, reduced.irreducibles ) );
 end );

#############################################################################
##
#F IrreducibleDifferences( <tbl>, <reducibles>, <reducibles2> )
#F IrreducibleDifferences( <tbl>, <reducibles>, <reducibles2>, <scprmat> )
#F IrreducibleDifferences( <tbl>, <reducibles>, \"triangle\" )
#F IrreducibleDifferences( <tbl>, <reducibles>, \"triangle\", <scprmat> )
##
#T compute/consider scalar product of i-th and j-th character only if the
#T norms have different parity!
##
InstallGlobalFunction( IrreducibleDifferences, function( arg )
 local tbl,
 reducibles,
 irreducibledifferences,
 scprmatrix,
 i, j,
 diff,
 reducibles2,
 norms, norms2;

 if not ( Length( arg ) in [ 3, 4 ] and IsOrdinaryTable( arg[1] ) and
 IsList( arg[2] ) and ( IsList( arg[3] ) or IsString( arg[3] ) ) )
 or ( Length( arg ) = 4 and not IsList( arg[4] ) ) then
 Error( "usage: IrreducibleDifferences(tbl,reducibles,\"triangle\")\n",
 "resp. IrreducibleDifferences(tbl,reducibles,\"triangle\",scprmat)",
 "\n resp. IrreducibleDifferences(tbl,reducibles,reducibles2)\nresp.",
 " IrreducibleDifferences(tbl,reducibles,reducibles2,scprmat)" );
 fi;

 tbl:= arg[1];
 reducibles:= arg[2];
 irreducibledifferences:= [];
 if IsString( arg[3] ) then # "triangle"
 if Length( arg ) = 3 then
 scprmatrix:= MatScalarProducts( tbl, reducibles );
 else
 scprmatrix:= arg[4];
 fi;
 for i in [ 1 .. Length( scprmatrix ) ] do
 for j in [ 1 .. i-1 ] do
 if scprmatrix[i][i] + scprmatrix[j][j] - 2*scprmatrix[i][j] = 1 then
 if reducibles[i][1] > reducibles[j][1] then
 diff:= reducibles[i] - reducibles[j];
 Info( InfoCharacterTable, 2,
 "IrreducibleDifferences: X[",i, "] - X[",j, "] found" );
 else
 diff:= reducibles[j] - reducibles[i];
 Info( InfoCharacterTable, 2,
 "IrreducibleDifferences: X[",j, "] - X[",i, "] found" );
 fi;
 if IsClassFunction( diff ) then
 SetIsCharacter( diff, true );
 fi;
 AddSet( irreducibledifferences, diff );
 fi;
 od;
 od;
 else # not "triangle"
 reducibles2:= arg[3];
 if Length( arg ) = 3 then
 scprmatrix:= MatScalarProducts( tbl, reducibles, reducibles2 );
 else
 scprmatrix:= arg[4];
 fi;
 norms := List( reducibles , x -> ScalarProduct(tbl,x,x) );
 norms2:= List( reducibles2, x -> ScalarProduct(tbl,x,x) );
 for i in [ 1 .. Length( norms ) ] do
 for j in [ 1 .. Length( norms2 ) ] do
 if norms[i] + norms2[j] - 2 * scprmatrix[i][j] = 1 then
 if reducibles[j][1] > reducibles2[i][1] then
 diff:= reducibles[j] - reducibles2[i];
 Info( InfoCharacterTable, 2,
 "IrreducibleDifferences: X[",j, "] - Y[",i, "] found" );
 else
 diff:= reducibles2[i] - reducibles[j];
 Info( InfoCharacterTable, 2,
 "IrreducibleDifferences: Y[",i, "] - X[",j, "] found" );
 fi;
 if IsClassFunction( diff ) then
 SetIsCharacter( diff, true );
 fi;
 AddSet( irreducibledifferences, diff );
 fi;
 od;
 od;
 fi;
 return irreducibledifferences;
end );

#############################################################################
##
## 11. Symmetrizations of Class Functions
##

#############################################################################
##
#F Symmetrizations( [<tbl>, ]<characters>, <n> )
#F Symmetrizations( [<tbl>, ]<characters>, <Sn> )
#F Symmetrizations( <tbl>, <characters>, <arec> )
##
InstallMethod( Symmetrizations,
 "for homogeneous list (of class functions) and positive integer",
 [ IsHomogeneousList, IsPosInt ],
 function( list, n )
 if IsEmpty( list ) then
 return [];
 elif IsClassFunction( list[1] ) then
 return Symmetrizations( UnderlyingCharacterTable( list[1] ), list, n );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( Symmetrizations,
 "for homogeneous list (of class functions) and character table",
 [ IsHomogeneousList, IsOrdinaryTable ],
 function( list, Sn )
 if IsEmpty( list ) then
 return [];
 elif IsClassFunction( list[1] ) then
 return Symmetrizations( UnderlyingCharacterTable( list[1] ),
 list, Sn );
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( Symmetrizations,
 "for char. table, homog. list (of class functions), and pos. integer",
 [ IsCharacterTable, IsHomogeneousList, IsPosInt ],
 function( tbl, characters, n )
 local gensymm, classparam, siz, classes;

 gensymm:= CharTableSymmetric;
 classparam:= gensymm.classparam[1]( n );
 siz:= gensymm.size( n );
 classes:= List( classparam, p -> siz / gensymm.centralizers[1]( n, p ) );

 return Symmetrizations( tbl, characters,
 rec( classparam := List( classparam, x -> [ 1, x ] ),
 symmirreds := gensymm.matrix( n ),
 symmclasses := classes,
 symmorder := siz ) );
 end );

InstallMethod( Symmetrizations,
 "for char. table, homog. list (of class functions), and table of Sn",
 [ IsCharacterTable, IsHomogeneousList, IsOrdinaryTable ],
 function( tbl, characters, Sn )

 if not HasClassParameters( Sn ) then
 Error( "partitions corresponding to classes must be stored",
 " as `ClassParameters( <Sn> )'" );
 fi;

 return Symmetrizations( tbl, characters,
 rec( classparam := ClassParameters( Sn ),
 symmirreds := List( Irr( Sn ), ValuesOfClassFunction ),
 symmclasses := SizesConjugacyClasses( Sn ),
 symmorder := Size( Sn ) ) );
 end );

InstallOtherMethod( Symmetrizations,
 "for char. table, homog. list (of class functions), and record",
 [ IsCharacterTable, IsHomogeneousList, IsRecord ],
 function( tbl, characters, arec )
 local i, j, l, n,
 powermap,
 cyclestruct,
 classparam,
 symmirreds,
 symmclasses,
 symmorder,
 cycl,
 symmetrizations,
 chi,
 psi,
 prodmatrix,
 single,
 value,
 val;

 classparam := arec.classparam;
 symmirreds := arec.symmirreds;
 symmclasses := arec.symmclasses;
 symmorder := arec.symmorder;

 cyclestruct:= [];
 for i in [ 1 .. Length( classparam ) ] do
 if Length( classparam[i][2] ) = 1 then
 n:= classparam[i][2][1];
 fi;
 cyclestruct[i]:= [];
 for j in [ 1 .. Maximum( classparam[i][2] ) ] do
 cyclestruct[i][j]:= 0;
 od;
 for j in classparam[i][2] do
 cyclestruct[i][j]:= cyclestruct[i][j] + 1;
 od;
 od;

 # Compute necessary power maps.
 powermap:= ComputedPowerMaps( tbl );
 for i in [ 1 .. n ] do
 if not IsBound( powermap[i] ) then
 powermap[i]:= MakeImmutable( PowerMap( tbl, i ) );
 fi;
 od;

 symmetrizations:= [];
 for chi in characters do

 # Symmetrize the character `chi' of `tbl' ...
 prodmatrix:= [];
 for i in [ 1 .. Length( characters[1] ) ] do
 prodmatrix[i]:= [];
 for j in [ 1 .. Length( symmclasses ) ] do
 value:= symmclasses[j];
 cycl:= cyclestruct[j];
 for l in [ 1 .. Length( cycl ) ] do
 if cycl[l] <> 0 then
 if IsInt( powermap[l][i] ) then
 value:= value * ( chi[ powermap[l][i] ] ^ cycl[l] );
 else
 val:= CompositionMaps( chi, powermap[l][i] );
 if IsInt( val ) then
 value:= value * ( val ^ cycl[l] );
 else
 value:= Unknown();
 fi;
 fi;
 fi;
 od;
 prodmatrix[i][j]:= value;
 od;
 od;

 # ... with the character `psi' ...
 for psi in symmirreds do
 single:= [];
 for i in [ 1 .. Length( chi ) ] do

 # ... at class `i'
 single[i]:= psi * prodmatrix[i] / symmorder;
 if not ( IsCycInt( single[i] ) or IsUnknown( single[i] ) ) then
 single[i]:= Unknown();
 Print( "#E Symmetrizations: value not dividing group order,",
 " set to ", single[i], "\n" );
 fi;

 od;
 if IsClassFunction( chi ) and single[1] > 0 then
 single:= ClassFunctionSameType( tbl, chi, single );
 elif HasIsVirtualCharacter( chi ) and IsVirtualCharacter( chi ) then
 single:= VirtualCharacter( tbl, single );
 fi;
 Add( symmetrizations, single );
 od;

 od;

 # Return the symmetrizations.
 return symmetrizations;
 end );

#############################################################################
##
#F SymmetricParts( <tbl>, <characters>, <n> )
##
InstallGlobalFunction( SymmetricParts, function( tbl, characters, n )
 local i,
 j,
 k,
 nccl,
 exponents,
 symcentralizers, # list of symmetrizations, result
 symmetricparts,
 chi, # loop over 'characters'
 sym,
 exp,
 factor,
 powermap; # list of computed power maps of 'tbl'

 if IsEmpty( characters ) then
 return [];
 fi;

 nccl:= NrConjugacyClasses( tbl );
 exponents:= Partitions( n );
 symcentralizers:= CharTableSymmetric.centralizers[1];
 symcentralizers:= List( exponents, x -> symcentralizers( n, x ) );

 for i in [ 1 .. Length( exponents ) ] do

 # Transform partitions to exponent vectors.
 # At position $i$ we store the number of cycles of length $i$.
 exp:= [];
 for j in [ 1 .. Maximum( exponents[i] ) ] do exp[j]:= 0; od;
 for j in exponents[i] do exp[j]:= exp[j] + 1; od;
 exponents[i]:= exp;

 od;

 # Compute necessary power maps.
 powermap:= ComputedPowerMaps( tbl );
 for i in [ 1 .. n ] do
 if not IsBound( powermap[i] ) then
 powermap[i]:= MakeImmutable( PowerMap( tbl, i ) );
 fi;
 od;

 symmetricparts:= [];
 for chi in characters do

 Info( InfoCharacterTable, 2,
 "SymmetricParts: chi[.]" );
 sym:= List( chi, x -> 0 );

 # Loop over the conjugacy classes of the symmetric group.
 for j in [ 1 .. Length( symcentralizers ) ] do

 exp:= exponents[j];

 for k in [ 1 .. nccl ] do
 factor:= 1;
 for i in [ 1 .. Length( exp ) ] do
 if IsBound( exp[i] ) then
 factor:= factor * chi[ powermap[i][k] ]^exp[i];
 fi;
 od;
 sym[k]:= sym[k] + factor / symcentralizers[j];
 od;

 od;
 if IsClassFunction( chi ) then
 sym:= ClassFunctionSameType( tbl, chi, sym );
 fi;
 Add( symmetricparts, sym );

 od;

 # Return the symmetrizations.
 return symmetricparts;
end );

#############################################################################
##
#F AntiSymmetricParts( <tbl>, <character>, <n> )
##
InstallGlobalFunction( AntiSymmetricParts, function( tbl, characters, n )
 local i,
 j,
 k,
 nccl,
 exponents,
 symcentralizers,
 antisymmetricparts,
 chi,
 sym,
 exp,
 factor,
 powermap;

 if IsEmpty( characters ) then
 return [];
 fi;

 nccl:= NrConjugacyClasses( tbl );
 exponents:= Partitions( n );
 symcentralizers:= CharTableSymmetric.centralizers[1];
 symcentralizers:= List( exponents, x -> symcentralizers( n, x ) );

 for i in [ 1 .. Length( exponents ) ] do

 # Transform partitions to exponent vectors.
 # At position $i$ we store the number of cycles of length $i$.

 exp:= [];
 for j in [ 1 .. Maximum( exponents[i] ) ] do exp[j]:= 0; od;
 for j in exponents[i] do exp[j]:= exp[j] + 1; od;
 exponents[i]:= exp;

 od;

 # Compute necessary power maps.
 powermap:= ComputedPowerMaps( tbl );
 for i in [ 1 .. n ] do
 if not IsBound( powermap[i] ) then
 powermap[i]:= MakeImmutable( PowerMap( tbl, i ) );
 fi;
 od;

 # Compute the symmetrizations.
 antisymmetricparts:= [];
 for chi in characters do

 Info( InfoCharacterTable, 2,
 "AntiSymmetricParts: chi[.]" );
 sym:= List( chi, x -> 0 );
 for j in [ 1 .. Length( exponents ) ] do

 exp:= exponents[j];

 for k in [ 1 .. nccl ] do
 factor:= 1;
 for i in [ 1 .. Length( exp ) ] do
 if IsBound( exp[i] ) then
 if i mod 2 = 0 and exp[i] mod 2 = 1 then
 factor:= -factor * chi[ powermap[i][k] ]^exp[i];
 else
 factor:= factor * chi[ powermap[i][k] ]^exp[i];
 fi;
 fi;
 od;
 sym[k]:= sym[k] + factor / symcentralizers[j];
 od;

 od;
 if IsClassFunction( chi ) then
 if IsZero( sym ) then
 sym:= VirtualCharacter( tbl, sym );
 else
 sym:= ClassFunctionSameType( tbl, chi, sym );
 fi;
 fi;
 Add( antisymmetricparts, sym );

 od;

 # Return the symmetrizations.
 return antisymmetricparts;
end );

#############################################################################
##
#M ExteriorPower( <chi>, <n> )
##
InstallMethod( ExteriorPower,
 "for a class function and a pos. integer",
 [ IsClassFunction, IsPosInt ],
 function( chi, n )
 return AntiSymmetricParts( UnderlyingCharacterTable( chi ), [ chi ], n )[1];
 end );

#############################################################################
##
#M SymmetricPower( <chi>, <n> )
##
InstallMethod( SymmetricPower,
 "for a class function and a pos. integer",
 [ IsClassFunction, IsPosInt ],
 function( chi, n )
 return SymmetricParts( UnderlyingCharacterTable( chi ), [ chi ], n )[1];
 end );

#############################################################################
##
#F RefinedSymmetrizations( <tbl>, <chars>, <m>, <func> )
##
## (Note: It suffices to change `F2' and `F4' in order to get the
## symplectic components from the orthogonal ones.)
##
## We have (see J.S. Frame, Recursive computation of tensor power
## components, Bayreuther Mathematische Schriften 10, 153--159)
##
## \begintt
## component orthogonal symplectic
## M0 = L0 L0 ( = 1 )
## M1 = L1 L1
## M11 = L11 L11-L0
## M2 = L2-L0 L2
## M111 = L111 L111-L1
## M21 = L21-L1 L21-L1
## M3 = L3-L1 L3
## M1111 = L1111 L1111-L11
## M211 = L211-L11 L211-L11-L2+L0
## M22 = L22-L2 L22-L11
## M31 = L31-L2-L11+L0 L31-L2
## M4 = L4-L2 L4
## M11111 = L11111 L11111-L111
## M2111 = L2111-L111 L2111-L111-L21+L1
## M221 = L221-L21 L221-L111-L21+L1
## M311 = L311-L21-L111+L1 L311-L21-L3+L1
## M32 = L32-L3-L21+L1 L32-L21
## M41 = L41-L3-L21+L1 L41-L3
## M5 = L5-L3 L5
## M111111 = L111111 L111111-L1111
## M21111 = L21111-L1111 L21111-L1111-L211+L11
## M2211 = L2211-L211 L2211-L1111-L211-L22+L11+L2
## M3111 = L3111-L211-L1111+L11 L3111-L211-L31+L11+L2-L0
## M222 = L222-L22 L222-L211+L11-L0
## M321 = L321-L31-L22-L211+L2+L11 L321-L31-L22-L211+L2+L11
## M33 = L33-L31+L2-L0 L33-L22
## M411 = L411-L31-L211+L2+L11-L0 L411-L31-L4+L2
## M42 = L42-L4-L31-L22+L2+L11 L42-L31
## M51 = L51-L4-L31+L2 L51-L4
## M6 = L6-L4 L6
## \endtt
##
InstallGlobalFunction( RefinedSymmetrizations,
 function( tbl, chars, m, func )
 local classes, components,
 F2, F3, F4, F5, F6,
 M1,
 M2, M11,
 M3, M21, M111,
 M4, M31, M22, M211, M1111,
 M5, M41, M32, M311, M221, M2111, M11111,
 M6, M51, M42, M411, M33, M321, M3111, M222, M2211, M21111, M111111;

 # Linear characters are not allowed since their symmetrizations need not
 # to be proper characters.
 chars:= Filtered( chars, x -> 1 < x[1] );
 components:= [];
 classes:= [ 1 .. NrConjugacyClasses( tbl ) ];

 for M1 in chars do

 F2 := MinusCharacter( M1, PowerMap( tbl, 2 ), 2 );

 # orthogonal case: 'M11 = F2'
 # symplectic case: 'M11 = F2 - 1'
 M11:= func( F2, 1 );
 M2 := List( classes, x -> M1[x]^2 - M11[x] - 1 );

 Add( components, M11 );
 Add( components, M2 );

 if m > 2 then

 F3:= MinusCharacter( M1, PowerMap( tbl, 3 ), 3 );
 M21:= F3 - M1;
 M111:= List( classes, x -> M1[x] * M11[x] - F3[x] );
 M3:= List( classes, x -> M1[x] * M2[x] - F3[x] );

 Append( components, [ M21, M111, M3 ] );

 if m > 3 then

 F4:= MinusCharacter( F2, PowerMap( tbl, 2 ), 2 );

 # orthogonal case: 'F4 := F4'
 # symplectic case: 'F4 := F4 - M2'
 F4:= func( F4, M2 );
 M211:= F4 - M11;
 M31:= List( classes, x -> M11[x]*M2[x]-F4[x]-M2[x]);
 M22:= List( classes, x -> M1[x]*M21[x]-F4[x]-M2[x]-M31[x] );
 M1111:= List( classes, x -> M1[x]*M111[x]-F4[x] );
 M4:= List( classes, x -> M1[x]*M3[x]-M31[x]-M2[x] );

 Append( components, [ M211, M31, M22, M1111, M4 ] );

 if m > 4 then

 F5:= MinusCharacter( M1, PowerMap( tbl, 5 ), 5 );
 M2111:= List( classes, x-> F5[x]-M2[x]*F3[x]-M1[x]*M11[x] );
 M311:= List( classes, x-> M2[x]*M111[x]-M2111[x]-M21[x]
 -M111[x] );
 M221:= List( classes, x-> M1[x]*M211[x]-M2[x]*M111[x] );
 M11111:= List( classes, x-> M1[x]*M1111[x]-M2111[x]-M111[x]);
 M32:= List( classes, x-> M1[x]*M22[x]-M221[x]-M21[x] );
 M41:= List( classes, x-> M11[x]*M3[x]-M311[x]-M21[x]
 -M3[x] );
 M5:= List( classes, x-> M1[x]*M4[x]-M41[x]-M3[x] );

 Append( components, [ M2111, M311, M221, M11111, M32, M41, M5 ]);

 if m = 6 then

 F6:= MinusCharacter( F2, PowerMap( tbl, 3 ), 3 );
 M3111:= List( classes, x-> M21[x]*M111[x]-F6[x]+F2[x] );
 M411:= List( classes, x-> M3[x]*M111[x]-M3111[x]-M31[x]
 -M211[x] );
 M21111:= List( classes, x-> M2[x]*M1111[x]-M3111[x]
 -M211[x]-M1111[x] );
 M111111:= List( classes, x-> M1[x]*M11111[x]-M21111[x]
 -M1111[x] );
 M2211:= List( classes, x-> M1[x]*M2111[x]-M3111[x]
 -M21111[x]-M211[x]-M1111[x] );
 M321:= List( classes, x-> M1[x]*M311[x]-M3111[x]
 -M411[x]-M31[x]-M211[x] );
 M33:= List( classes, x-> F2[x]*M22[x]-M321[x]-M2211[x]
 -M31[x]-M22[x]-M211[x]-F2[x] );
 M51:= List( classes, x-> F2[x]*M4[x]-M411[x]-M31[x]
 -M4[x] );
 M42:= List( classes, x-> M1[x]*M41[x]-M411[x]-M51[x]
 -M31[x]-M4[x] );
 M222:= List( classes, x-> M2[x]*M22[x]-M321[x]-M42[x]
 -M31[x]-M22[x]-M211[x]-M2[x] );
 M6:= List( classes, x-> M1[x]*M5[x]-M51[x]-M4[x] );

 Append( components, [ M3111, M411, M21111, M111111, M2211,
 M321, M33, M51, M42, M222, M6 ] );

 fi;
 fi;
 fi;
 fi;
 od;

 return List( components, chi -> ClassFunction( tbl, chi ) );
end );

#############################################################################
##
#F OrthogonalComponents( <tbl>, <chars>, <m> )
##
InstallGlobalFunction( OrthogonalComponents, function( tbl, chars, m )
 if IsCharacterTable( tbl ) and IsList( chars )
 and IsInt( m ) and 1 < m and m < 7 then
 return RefinedSymmetrizations( tbl, chars, m,
 function( x, y ) return x; end );
 else
 Error( "usage: OrthogonalComponents( <tbl>, <chars>, <m> ) with ",
 "integer 2 <= m <= 6" );
 fi;
end );

#############################################################################
##
#F SymplecticComponents( <tbl>, <chars>, <m> )
##
InstallGlobalFunction( SymplecticComponents, function( tbl, chars, m )
 if IsCharacterTable( tbl ) and IsList( chars )
 and IsInt( m ) and 1 < m and m < 6 then
 return RefinedSymmetrizations( tbl, chars, m,
 function( x, y ) return x-y; end );
 else
 Error( "usage: SymplecticComponents( <tbl>, <chars>, <m> ) with ",
 "integer 2 <= m <= 5" );
 fi;
end );

#############################################################################
##
## 12. Operations for Brauer Characters
##

###############################################################################
##
#F FrobeniusCharacterValue( <value>, )
##
## Let $n$ be the conductor of $v$.
## Let $k$ be the order of $p$ modulo $n$, that is, $\F_{p^k}$ is the
## smallest field of characteristic $p$ containing $n$-th roots of unity.
## Let $m$ be minimal with $v^{\ast p^m} = v$, that is, $\F_{p^m}$ is a
## (not necessarily minimal) field containing the Frobenius character value
## $\overline{v}$.
##
## Let $C_k$ and $C_m$ be the Conway polynomials of degrees $k$ and $m$,
## and $z = X + (C_k)$ in $\F_{p^k} = \F_p[X] / (C_k)$.
## Then $\hat{y} = z^{\frac{p^k-1}{p^m-1}}$ may be identified with
## $y = X + (C_m)$ in $\F_{p^m} = \F_p[X] / (C_m)$.
##
## For $v = \sum_{i=1}^n a_i E(n)^i$, a representation of $\overline{v}$ in
## $\F_{p^k}$ is $\sum_{i=1}^n \overline{a_i} z^{\frac{p^k-1}{n} i}$ where
## $\overline{a_i}$ is the reduction of $a_i$ modulo $p$, viewed as
## element of $\F_p$.
##
## A representation of $\overline{v}$ in $\F_{p^m}$ can be found by
## solving the linear equation system
## $\overline{v} = \sum_{i=0}^{m-1} c_i \hat{y}^i$ over $\F_p$, which
## gives us $\overline{v} = \sum{i=0}^{m-1} c_i y^i$ in $\F_{p^m}$.
##
InstallGlobalFunction( FrobeniusCharacterValue, function( value, p )
 local n, # conductor of `value'
 k, # degree of smallest field containing `n'-th roots
 size, # `p^k'
 power, # `( size - 1 ) / n'
 ffe, # primitive `n'-th root in `GF( size )'
 cf, # canonical basis of `CF(n)'
 m, # degree of some field containing the result
 image, # image of `value' under Galois conjugation
 primefield, # `GF(p)'
 zero, # zero of `primefield'
 one, # identity of `primefield'
 conwaypol, # coeffs. of the `k'-th Conway pol. in char. `p'
 x, # coeffs. of an indeterminate
 y,
 lastvalue,
 fieldbase,
 i;

 # If <value> belongs to a -singular element then return `fail'.
 n:= Conductor( value );
 if n mod p = 0 then
 return fail;
 elif n = 1 then
 if DenominatorRat( value ) mod p = 0 then
 return fail;
 else
 return value * One( GF(p) );
 fi;
 elif IsCycInt( value / p ) then
 return Zero( GF(p) );
 fi;

 # Compute the size $p^k$ of the smallest finite field of characteristic
 # `p' that contains 'n'-th roots of unity.
 k:= OrderMod( p, n );
 size:= p^k;

 # The root `E(n)' is identified with the smallest primitive `n'-th
 # root in the finite field, that is, the `(size-1) / n'-th power of
 # the primitive root of the field
 # (which is given by the Conway polynomial).
 power:= ( size - 1 ) / n;

 if size <= MAXSIZE_GF_INTERNAL then

 # Use GAP's internal finite fields.
 # (Express the Brauer character value in terms of the Zumbroich basis
 # of the underlying cyclotomic field.)
 ffe:= PrimitiveRoot( GF( size ) ) ^ power;
 cf:= CanonicalBasis( CF( n ) );
 value:= Coefficients( cf, value ) *
 List( ZumbroichBase( n, 1 ), exp -> ffe ^ exp );

 elif not IsCheapConwayPolynomial( p, k ) then

 # Give up if the required Conway polynomial is hard to compute.
 Info( InfoWarning, 1,
 "the Conway polynomial of degree ", k, " for p = ", p,
 " is not known" );
 return fail;

 else

 # Compute a finite field that contains the Frobenius character value.
 # An upper bound is given by the field of order $p^m$
 # where $m$ is the smallest number such that <value> is fixed
 # by the Galois automorphism that raises roots of unity
 # to the $p^m$-th power.
 m:= 1;
 image:= GaloisCyc( value, p );
 while image <> value do
 m:= m+1;
 image:= GaloisCyc( image, p );
 od;

 # Compute the representation of the Frobenius character value
 # in the field $\F_{p^k}$.
 primefield:= GF(p);
 zero:= Zero( primefield );
 one:= One( primefield );

 conwaypol:= ConwayPol( p, k ) * one;
 x:= [ zero, one ];
 value:= COEFFS_CYC( value ) * one;

 ConvertToVectorRepNC( conwaypol, p );
 ConvertToVectorRepNC( x, p );
 ConvertToVectorRepNC( value, p );

 value:= PowerModEvalPol( conwaypol,
 value,
 PowerModCoeffs( x, 2, power, conwaypol, k+1 ) );
 if IsEmpty( value ) then
 return zero;
 fi;
 PadCoeffs( value, k, zero );

 # Compute a $\F_p$-basis $(\hat{y}^i; 0\leq i\leq m-1)$ of
 # the subfield of $\F_{p^k}$ isomorphic with $\F_{p^m}$.
 y:= PowerModCoeffs( x, 2, (size - 1) / (p^m - 1), conwaypol, k+1 );

 lastvalue:= [ one ];
 fieldbase:= [ [ one ] ];
 PadCoeffs( fieldbase[1], k, zero );
 ConvertToVectorRepNC( fieldbase[1], p );

 for i in [ 2 .. m ] do
 lastvalue:= ProductCoeffs( y, lastvalue );
 ReduceCoeffs( lastvalue, conwaypol );
 ShrinkRowVector( lastvalue );
 PadCoeffs( lastvalue, k, zero );
 fieldbase[i]:= lastvalue;
 ConvertToVectorRepNC( fieldbase[i], p );
 od;

 value:= ValuePol( SolutionMatDestructive( fieldbase, value ),
 Z( p, m ) );
 fi;

 # Return the Frobenius character value.
 return value;
end );

##############################################################################
##
#F ReductionToFiniteField( <value>, )
##
InstallGlobalFunction( ReductionToFiniteField, function( value, p )
 local n, primefield, one, zero, k, size, power, ffe, cf, frob, d,
 conwaypol, x, m, primes, sol, l, mc, y, leny, lastvalue, fieldbase,
 i, redsol;

 # If <value> belongs to a -singular element then return `fail'.
 n:= Conductor( value );
 if n mod p = 0 then
 return fail;
 fi;

 primefield:= GF(p);

 # Catch the case where the reduction trivially lies in the prime field.
 if n = 1 then
 if DenominatorRat( value ) mod p = 0 then
 return fail;
 else
 return [ value * One( Indeterminate( primefield ) ), 1 ];
 fi;
 elif IsCycInt( value / p ) then
 return [ Zero( Indeterminate( primefield ) ), 1 ];
 fi;

 one:= One( primefield );
 zero:= Zero( primefield );

 # Compute the size $p^k$ of the smallest finite field of characteristic
 # `p' that contains `n'-th roots of unity.
 k:= OrderMod( p, n );
 size:= p^k;

 # The root `E(n)' is identified with the smallest primitive `n'-th
 # root in the finite field, that is, the `(size-1) / n'-th power of
 # the primitive root of the field
 # (which is given by the Conway polynomial).
 power:= ( size - 1 ) / n;

 if size <= MAXSIZE_GF_INTERNAL then
 # Use GAP's internal finite fields.
 # (Compute the Frobenius character value and the corresponding pol.)
 ffe:= PrimitiveRoot( GF( size ) ) ^ power;
 cf:= CanonicalBasis( CF( n ) );
 frob:= Coefficients( cf, value ) *
 List( ZumbroichBase( n, 1 ), exp -> ffe ^ exp );
 if IsZero( frob ) then
 return [ Zero( Indeterminate( primefield ) ), 1 ];
 fi;

 d:= DegreeFFE( frob );
 if d = 1 then
 return [ frob * One( Indeterminate( primefield ) ), 1 ];
 fi;

 # Note that `LogFFE' returns a nonzero value.
 conwaypol:= ConwayPol( p, d ) * one;
 x:= [ zero, one ];
 ConvertToVectorRepNC( conwaypol, p );
 ConvertToVectorRepNC( x, p );
 frob:= PowerModCoeffs( x, 2, LogFFE( frob, Z( p, d ) ), conwaypol, d+1 );
 return [ UnivariatePolynomialByCoefficients( FamilyObj( one ),
 frob, 1 ),
 d ];
 elif not IsCheapConwayPolynomial( p, k ) then
 # Give up if the required Conway polynomial is hard to compute.
 Info( InfoWarning, 1,
 "the Conway polynomial of degree ", k, " for p = ", p,
 " is not known" );
 return fail;
 fi;

 conwaypol:= ConwayPol( p, k ) * one;

 x:= [ zero, one ];
 value:= COEFFS_CYC( value ) * one;

 ConvertToVectorRepNC( conwaypol, p );
 ConvertToVectorRepNC( x, p );
 ConvertToVectorRepNC( value, p );

 value:= PowerModEvalPol( conwaypol, value,
 PowerModCoeffs( x, 2, power, conwaypol, k+1 ) );
 if IsEmpty( value ) then
 return [ Zero( Indeterminate( primefield ) ), 1 ];
 fi;
 PadCoeffs( value, k, zero );

 # Reduce the representation into the smallest finite field.
 # The currently known field has size `p^k'.
 m:= k;

 if k <> 1 then

 primes:= ShallowCopy( PrimeDivisors( m ) );
 sol:= fail;

 while not IsEmpty( primes ) do

 for l in ShallowCopy( primes ) do

 # `p^(m/l)' is the candidate for next smaller field.
 mc:= m / l;

 # Compute a $\F_p$-basis $(\hat{y}^i; 0 \leq i \leq m/l - 1)$ of
 # the subfield of $\F_{p^k}$ isomorphic with $\F_{p^{(m/l)}}$.
 y:= PowerModCoeffs( x, 2, (size - 1) / (p^mc - 1), conwaypol, k+1 );
 leny:= Length( y );

 lastvalue:= [ one ];
 PadCoeffs( lastvalue, k, zero );
 fieldbase:= [ [ one ] ];
 PadCoeffs( fieldbase[1], k, zero );
 ConvertToVectorRepNC( lastvalue, p );
 ConvertToVectorRepNC( fieldbase[1], p );

 for i in [ 2 .. mc ] do
 lastvalue:= ProductCoeffs( y, leny, lastvalue, k );
 ReduceCoeffs( lastvalue, conwaypol );
 PadCoeffs( lastvalue, k, zero );
 ConvertToVectorRepNC( lastvalue, p );
#T needed?
 fieldbase[i]:= lastvalue;
 od;

 # Check whether `value' is a linear combination of this basis.
 redsol:= SolutionMatDestructive( fieldbase, ShallowCopy( value ) );
 if redsol = fail then
 RemoveSet( primes, l );
 else
 sol:= redsol;
 m:= mc;
 fi;

 od;

 IntersectSet( primes, Factors( m ) );

 od;

 if sol <> fail then
 # We have found a smaller field.
 value:= sol;
 fi;

 fi;

 # Return the reduction into the minimal field.
 return [ UnivariatePolynomialByCoefficients( FamilyObj( one ), value, 1 ),
 m ];
end );

# # alternative implementation
# ReductionToFiniteField2:= function( value, p )
# local frob, d, z, one, zero, conwaypol, x;
#
# frob:= FrobeniusCharacterValue( value, p );
# if frob = fail then
# return fail;
# elif IsZero( frob ) then
# return [ Zero( Indeterminate( GF(p) ) ), 1 ];
# fi;
#
# d:= DegreeFFE( frob );
#
# if d = 1 then
# return [ frob * One( Indeterminate( GF(p) ) ), 1 ];
# elif p^d <= MAXSIZE_GF_INTERNAL then
# z:= Z( p, d );
# one:= One( z );
# zero:= Zero( z );
# conwaypol:= ConwayPol( p, d ) * one;
# x:= [ zero, one ];
# ConvertToVectorRepNC( conwaypol, p );
# ConvertToVectorRepNC( x, p );
#
# # Note that `LogFFE' returns a nonzero value.
# frob:= PowerModCoeffs( x, 2, LogFFE( frob, z ), conwaypol, d+1 );
# frob:= UnivariatePolynomialByCoefficients( FamilyObj( one ),
# frob, 1 );
# elif IsCoeffsModConwayPolRep( frob ) then
# frob:= UnivariatePolynomialByCoefficients( FamilyObj( Z(p) ),
# frob![1], 1 );
# else
# # This should never happen, since `FrobeniusCharacterValue' worked.
# Info( InfoWarning, 1,
# "no coefficients w.r.t. the Conway polynomial available" );
# return fail;
# fi;
# return [ frob, d ];
# end;

##############################################################################
##
#F SizeOfFieldOfDefinition( <val>, )
##
## Typically, <val> is a (Brauer) character, that is, a list of cyclotomic
## integers with conductor coprime to , which is closed under Galois
## conjugacy.
## In this situation, the size of the field of definition is the smallest
## power <q> of such that the difference of <val> and its image under
## the Galois automorphism 'GaloisCyc( ., <q> )' is divisible by in the
## ring of cyclotomic integers.
## (This follows with the same number theoretic argument that is used in the
## proof of <Cite Key="Isa76" Where="Theorem 15.18."/>.)
##
## If <val> is not closed under Galois automorphisms then the result depends
## on the definition of the reduction from cyclotomics to finite fields,
## and in general there is no way to avoid computing the reduction of <val>.
## For example, if we assume the reduction w.r.t. Conway polynomials then
## the reduction of the value 'EX(63)' in characteristic 2 lies in the prime
## field, whereas the reduction of its complex conjugate does not lie in the
## prime field.
## If we choose a different reduction homomorphism
## (for example, if we choose other polynomials to define the fields)
## then the situation may be the other way round.
##
## If the coefficients of the Zumbroich basis representation of the
## difference $\alpha^{\ast p} - \alpha$ are divisible by $p$
## then $\alpha$ is mapped to an element of the prime field under
## the reduction modulo any maximal ideal.
## (This covers the special cases that $\alpha$ is fixed under the
## automorphism $\ast p$ or that all coefficients of $\alpha$
## are divisible by $p$.)
##
InstallGlobalFunction( SizeOfFieldOfDefinition, function( val, p )
 local closed, values, entry, q;

 closed:= false;

 # The first argument may be a cyclotomic or a list of cyclotomics.
 if IsInt( val ) then
 return p;
 elif IsCyc( val ) then
 val:= [ val ];
 elif IsClassFunction( val ) then
 # This is expected to be the typical situation.
 # We know in advance that 'val' is closed under Galois conjugacy.
 closed:= true;
 val:= ValuesOfClassFunction( val );
 elif not ( IsList( val ) and IsCyclotomicCollection( val ) ) then
 Error( "<val> must be a cyclotomic or a list of cyclotomics" );
 fi;

 values:= [];
 for entry in val do
 if DenominatorCyc( entry ) mod p = 0 or
 Conductor( entry ) mod p = 0 then
 return fail;
 elif not IsRat( entry ) then
 Add( values, entry );
 fi;
 od;

 if ForAll( values, x -> IsCycInt( ( GaloisCyc( x, p ) - x ) / p ) ) then
 # All reductions lie in the prime field.
 return p;
 elif closed then
 # It is sufficient to look at powers of the map '*p'.
 q:= p;
 while true do
 q:= q * p;
 if ForAll( values,
 x -> IsCycInt( ( GaloisCyc( x, q ) - x ) / p ) ) then
 return q;
 fi;
 od;
 fi;

 # We have no better idea than to reduce each value.
 # (Well, we could check whether 'values' is perhaps closed under
 # Galois conjugacy, or check some generalization of this condition,
 # but this is probably not worth the effort.)
 values:= List( values, x -> FrobeniusCharacterValue( x, p ) );
 if fail in values then
 return fail;
 fi;
 return p ^ DegreeFFE( values );
end );

#############################################################################
##
#M BrauerCharacterValue( <mat> )
##
## Let $M$ be a matrix of order $n$, with entries in the finite field $F$,
## and suppose that $M$ is diagonalizable over the extension field $K$ with
## $p^d$ elements.
##
## It could in principle be computed by determining the diagonal form,
## identifying the entries in the diagonal with $(p^d -1)$-th complex roots
## of unity,
## and then summing up these roots.
##
## But one can do better.
## (This is the approach used by the C-{\MeatAxe}.)
## For each irreducible factor $f$ of $X^n - 1$ over $F$, the multiplicities
## of its roots over $K$ as eigenvalues of $M$ are equal,
## hence one needs to compute these multiplicities and the corresponding
## sums of roots of unity.
## The former means to solve an equation system over $F$,
## and the latter depends only on $n$ and $F$, but not on $M$;
## so one can use a database for speeding up the computations.
## This database is implemented by the global variable `ZEV_DATA' and the
## functions `ZevData' and `ZevDataValue'.
##
InstallMethod( BrauerCharacterValue,
 "for a matrix",
 [ IsMatrix ],
 function( mat )
 local n, # order of `mat'
 p, # characteristic of `mat'
 info, # list of pairs returned by `ZevData'
 value, # Brauer character value, result
 pair, # loop over `info'
 f, # polynomial part of `pair'
 nullity; # dimension of a nullspace

 n:= Order( mat );

 # Handle the trivial cases first.
 if n = 1 then
 return Length( mat );
 fi;

 p:= Characteristic( mat );
 if n mod p = 0 then
 return fail;
 fi;

 # Get the complex values corresponding to the irreducible
 # factors of $X^n - 1$ over $F$.
 info:= ZevData( p^DegreeFFE( mat ), n );

 # Compute the coefficients of the complex summands,
 # as quotients of nullities and degrees.
 value:= 0;
 for pair in info do
 f:= pair[1];
 nullity:= Length( NullspaceMat( ValuePol( f, mat ) ) );
 if nullity <> 0 then
 nullity:= nullity / ( Length( f ) - 1 );
 Assert( 1, IsInt( nullity ), "degree of <f> must divide <nullity>" );
 value:= value + nullity * pair[2];
 fi;
 od;

 return value;
 end );

#############################################################################
##
#F ZevDataValue( <q>, <n> )
##
InstallGlobalFunction( ZevDataValue, function( q, n )
 local F, dimext, extfieldsize, Ee, value, K, z, quot, R, f, y, fac,
 p, one, conw, conwlen, x, zpol, zpollen, zeta, zetalen, coeffs, l,
 power, powerlen, i, exp, res, reslen, j;

 # Compute the field $F$ of matrix entries and the smallest field $K
 # over which a matrix of order `n' is diagonalizable.
 F:= GF( q );
 dimext:= DegreeOverPrimeField( F ) * OrderMod( q, n );
 extfieldsize:= Characteristic( F ) ^ dimext;
 Ee:= E( n );
 value:= [];

 if extfieldsize <= MAXSIZE_GF_INTERNAL then

 # The splitting field is supported in {\GAP},
 # and the stored primitive root is given by the Conway polynomial.
 K:= GF( extfieldsize );
 z:= PrimitiveRoot( K );
 quot:= ( extfieldsize - 1 ) / n;

 R:= PolynomialRing( K );
 for f in Factors( PolynomialRing( F ), Indeterminate(F)^n - 1 ) do

 y:= 0;
 for fac in Factors( R, f ) do

 # The factors are all linear, i.e., of the form $X - \alpha$.
 # Sum up the lifts of the numbers $\alpha$.
 y:= y + Ee^ ( LogFFE(
 -CoefficientsOfLaurentPolynomial( fac )[1][1], z ) / quot );

 od;
 Add( value, [ CoefficientsOfLaurentPolynomial( f )[1], y ] );

 od;

 else

 # The splitting field is not available in {\GAP},
 # use computations with polynomials.
 p:= Characteristic( F );
 z:= PrimitiveRoot( F );

 one:= One( F );
 conw:= ConwayPol( p, dimext ) * one;
 conwlen:= dimext + 1;
 x:= [ Zero( F ), one ];

 # polynomial corresponding to the primitive root of `F'
 zpol:= PowerModCoeffs( x, 2, ( extfieldsize-1 ) / ( Size(F)-1 ),
 conw, conwlen );
 zpollen:= Length( zpol );

 # polynomial corresponding to a primitive `n'-th root $\zeta$
 zeta:= PowerModCoeffs( x, 2, ( extfieldsize-1 ) / n,
 conw, conwlen );
 zetalen:= Length( zeta );

 for f in Factors( PolynomialRing( F ), Indeterminate(F)^n - 1 ) do

 y:= 0;
 coeffs:= CoefficientsOfUnivariatePolynomial( f );
 l:= Length( coeffs );
 power:= [ one ];
 powerlen:= 1;

 for i in [ 0 .. n-1 ] do

 # Compute $\sum_{j=0}^{l-1} c_j \zeta^{i j}$,
 # where `f' has the form $\sum_{j=0}^{l-1} c_j X^j$.
 exp:= LogFFE( coeffs[l], z );
 if exp = 0 then
 res:= [ one ];
 else
 res:= PowerModCoeffs( zpol, zpollen, exp, conw, conwlen );
 fi;
 reslen:= Length( res );
 for j in [ 1 .. l-1 ] do
 reslen:= MultCoeffs( res, res, reslen, power, powerlen );
 if not IsZero( coeffs[l-j] ) then
 exp:= LogFFE( coeffs[l-j], z );
 if exp = 0 then
 res:= res + [ one ];
 else
 res:= res + PowerModCoeffs( zpol, zpollen, exp,
 conw, conwlen );
 fi;
 fi;
 reslen:= ReduceCoeffs( res, Length( res ), conw, conwlen );
 ShrinkRowVector( res ); # needed?
 reslen:= Length( res ); # needed?
 od;

 # If $\zeta^i$ is a root of `f' then take the corresponding
 # complex root of unity.
 if reslen = 0 then
 y:= y + Ee^i;
 fi;

 powerlen:= MultCoeffs( power, power, powerlen, zeta, zetalen );
 powerlen:= ReduceCoeffs( power, powerlen, conw, conwlen );

 od;

 Add( value, [ coeffs, y ] );

 od;

 fi;

 return value;
 end );

#############################################################################
##
#F ZevData( <q>, <n> )
#F ZevData( <q>, <n>, <listofpairs> )
##
InstallGlobalFunction( ZevData, function( q, n, listofpairs... )
 local aux, result;

 aux := GET_FROM_SORTED_CACHE(ZEV_DATA, q, {} -> NEW_SORTED_CACHE(false));

 if Length( listofpairs ) = 1 then
 listofpairs := listofpairs[1];
 result := GET_FROM_SORTED_CACHE(aux, n, {} -> Immutable(listofpairs));
 if result <> listofpairs then
 Error( "incompatible ZevData( ", q, ", ", n, " )" );
 fi;
 return result;

 else
 return GET_FROM_SORTED_CACHE(aux, n, {} -> ZevDataValue( q, n ));
 fi;
end );

##############################################################################
##
#F RealizableBrauerCharacters( <matrix>, <q> )
##
InstallGlobalFunction( RealizableBrauerCharacters, function( matrix, q )
 local result, factors, p, m, done, row, d, g, qq, image, newrow, i;

 result:= [];
 factors:= Factors( q );
 p:= factors[1];
 m:= Length( factors );
 done:= [];

 for row in matrix do
 if not row in done then
 d:= SizeOfFieldOfDefinition( row, p );
 if d = fail then
 return fail;
 fi;
 d:= Length( Factors( d ) );
 g:= Gcd( d, m );
 qq:= p^g;
 image:= row;
 newrow:= row;
 Add( done, row );

 for i in [ 1 .. d/g-1 ] do
 image:= GaloisCyc( image, qq );
 newrow:= newrow + image;
 Add( done, image );
 od;

 if not newrow in result then
 Add( result, newrow );
 fi;
 fi;
 od;

 return result;
end );

#############################################################################
##
## 13. Domains Generated by Class Functions
##

#############################################################################
##
#M GroupWithGenerators( <classfuns>[, <id>] )
##
InstallOtherMethod( GroupWithGenerators,
 "for a homogeneous list (of class functions)",
 [ IsHomogeneousList ],
 function( gens )
 local filter, G;

 # Check that the list consists of invertible class functions.
 if IsEmpty( gens ) or not ForAll( gens, IsClassFunction ) then
 TryNextMethod();
 elif ForAny( gens, psi -> Inverse( psi ) = fail ) then
 Error( "class functions in <gens> must be invertible" );
#T move to `IsGeneratorsOfGroup'
 fi;

 filter:= IsGroup and IsAttributeStoringRep;
 if IsFinite( gens ) then
 filter:= filter and IsFinitelyGeneratedGroup;
 fi;

 # Construct the group.
 G:= Objectify( NewType( FamilyObj( gens ), filter ), rec() );
 SetGeneratorsOfMagmaWithInverses( G, AsList( gens ) );
 return G;
 end );

InstallOtherMethod( GroupWithGenerators,
 "for list (of class functions) and class function",
 IsCollsElms,
 [ IsHomogeneousList, IsClassFunction ],
 function( gens, id )
 local filter, G;

 # Check that the class functions are invertible.
 if not ForAll( gens, IsClassFunction ) then
 TryNextMethod();
 elif ForAny( gens, psi -> Inverse( psi ) = fail ) then
 Error( "class functions in <gens> must be invertible" );
#T move to `IsGeneratorsOfGroup'
 elif not IsOne( id ) then
 Error( "<id> must be an identity" );
 fi;

 filter:= IsGroup and IsAttributeStoringRep;
 if IsFinite( gens ) then
 filter:= filter and IsFinitelyGeneratedGroup;
 fi;

 # Construct the group.
 G:= Objectify( NewType( FamilyObj( gens ), filter), rec() );
 SetGeneratorsOfMagmaWithInverses( G, AsList( gens ) );
 SetOne( G, id );
 return G;
 end );

InstallOtherMethod( GroupWithGenerators,
 "for empty list and trivial character",
 [ IsList and IsEmpty, IsClassFunction ],
 function( empty, id )
 local G;

 if not IsOne( id ) then
 Error( "<id> must be an identity" );
 fi;

 # Construct the group.
 G:= Objectify( NewType( CollectionsFamily( FamilyObj( id ) ),
 IsGroup and IsAttributeStoringRep and
 IsFinitelyGeneratedGroup and IsTrivial ),

 rec() );
 SetGeneratorsOfMagmaWithInverses( G, empty );
 SetOne( G, id );
 return G;
 end );

#############################################################################
##
## 5. vector spaces of class functions
##
## Free left modules and algebras of class functions are handled by nice
## bases,
## for admitting the default procedure of closure under multiplication.
## In order to apply `NiceVector' and `UglyVector', algebras of class
## functions are in the filter `IsClassFunctionsSpace'.
##
InstallHandlingByNiceBasis( "IsClassFunctionsSpace", rec(
 detect:= function( R, gens, V, zero )
 local tbl;
 if not ForAll( gens, IsClassFunction ) then
 return false;
 elif zero = false then
 tbl:= UnderlyingCharacterTable( gens[1] );
 elif not IsClassFunction( zero ) then
 return false;
 else
 tbl:= UnderlyingCharacterTable( zero );
 fi;
 if ForAny( gens, chi -> UnderlyingCharacterTable( chi ) <> tbl ) then
 return false;
 fi;
 return true;
 end,

 NiceFreeLeftModuleInfo := function( V )
 return UnderlyingCharacterTable( Zero( V ) );
 end,

 NiceVector := function( V, v )
 if UnderlyingCharacterTable( v ) = NiceFreeLeftModuleInfo( V ) then
 return ValuesOfClassFunction( v );
 else
 return fail;
 fi;
 end,

 UglyVector := function( V, r )
 return ClassFunction( NiceFreeLeftModuleInfo( V ), r );
 end ) );

#############################################################################
##
#M ScalarProduct( <V>, <chi>, <psi> ) . . . . for module of class functions
##
## Left modules of class functions carry the usual bilinear form.
##
InstallOtherMethod( ScalarProduct,
 "for left module of class functions, and two class functions",
 IsCollsElmsElms,
 [ IsFreeLeftModule, IsClassFunction, IsClassFunction ],
 function( V, x1, x2 )
 local tbl;
 tbl:= UnderlyingCharacterTable( x1 );
 if tbl = UnderlyingCharacterTable( x2 ) then
 return ScalarProduct( tbl, x1, x2 );
 else
 TryNextMethod();
 fi;
 end );

#############################################################################
##
#M ScalarProduct( <V>, <chivals>, <psivals> ) . . for module of class funs.
##
## Left modules of class functions carry the usual bilinear form.
##
InstallOtherMethod( ScalarProduct,
 "for module of class functions, and two values lists",
 [ IsFreeLeftModule and IsClassFunctionsSpace,
 IsHomogeneousList, IsHomogeneousList ],
 function( V, x1, x2 )
 return ScalarProduct( NiceFreeLeftModuleInfo( V ), x1, x2 );
 end );

#############################################################################
##
## 14. Auxiliary operations
##

##############################################################################
##
#F OrbitChar( <chi>, <linear> )
##
InstallGlobalFunction( OrbitChar, function( chi, linear )
 local classes, # range of positions in `chi'
 nofcyc, # describes the conductor of values of `chi'
 gens, # generators of Galois automorphism group
 orb, # the orbit, result
 gen, # loop over `gens'
 image; # one image of `chi' under operation

 classes:= [ 1 .. Length( chi ) ];
 nofcyc:= Conductor( chi );

 # Apply Galois automorphisms if necessary.
 orb:= [ chi ];
 if 1 < nofcyc then
 gens:= Flat( GeneratorsPrimeResidues( nofcyc ).generators );
 for chi in orb do
 for gen in gens do
 image:= List( chi, x -> GaloisCyc( x, gen ) );
 if not image in orb then
 Add( orb, image );
 fi;
 od;
 od;
 fi;

 # Apply multiplication with linear characters.
 for chi in orb do
 for gen in linear do
 image:= List( classes, x -> gen[x] * chi[x] );
 if not image in orb then
 Add( orb, image );
 fi;
 od;
 od;

 # Return the orbit.
 return orb;
end );

##############################################################################
##
#F OrbitsCharacters( <irr> )
##
InstallGlobalFunction( OrbitsCharacters, function( irr )
 local irrvals, # list of value lists
 oldirrvals, # store original succession
 tbl, # underlying character table
 linear, # linear characters of `tbl'
 orbits, # list of orbits, result
 indices, # from 1 to number of conjugacy classes of `tbl'
 orb, # one orbit
 gens, # generators of the acting group
 chi, # one irreducible character
 gen, # one generator of the acting group
 image, # image of a character
 i, # loop over one orbit
 pos; # position of value list in `oldirrvals'

 orbits:= [];

 if not IsEmpty( irr ) then

 if IsClassFunction( irr[1] ) then

 # Replace group characters by their value lists.
 # Store the succession in the original list.
 irrvals:= List( irr, ValuesOfClassFunction );
 oldirrvals:= ShallowCopy( irrvals );
 irrvals:= Set( irrvals );

 else
 irrvals:= Set( irr );
 fi;

 indices:= [ 1 .. Length( irrvals[1] ) ];

 # Compute the orbit of linear characters if there are any.
 linear:= Filtered( irrvals, x -> x[1] = 1 );

 if 0 < Length( linear ) then

 # The linear characters form an orbit.
 # We remove them from the other characters,
 # and remove the trivial character from `linear'.
 orb:= ShallowCopy( linear );
 SubtractSet( irrvals, linear );
 RemoveSet( linear, List( linear[1], x -> 1 ) );

 # Make `linear' closed under Galois automorphisms.
 gens:= Flat( GeneratorsPrimeResidues(
 Conductor( Flat( linear ) ) ).generators );

 for chi in orb do
 for gen in gens do
 image:= List( chi, x -> GaloisCyc( x, gen ) );
 if not image in orb then
 Add( orb, image );
 fi;
 od;
 od;

 # Make `linear' closed under multiplication with linear characters.
 for chi in orb do
 for gen in linear do
 image:= List( indices, x -> gen[x] * chi[x] );
 if not image in orb then
 Add( orb, image );
 fi;
 od;
 od;

 orbits[1]:= orb;

 fi;

 # Compute the other orbits.
 while Length( irrvals ) > 0 do

 orb:= OrbitChar( irrvals[1], linear );
 Add( orbits, orb );
 SubtractSet( irrvals, orb );

 od;

 # Replace the value lists by the group characters
 # if the input was a list of characters.
 # Be careful not to copy characters if not necessary.
 if IsCharacter( irr[1] ) then
 tbl:= UnderlyingCharacterTable( irr[1] );
 for orb in orbits do
 for i in [ 1 .. Length( orb ) ] do
 pos:= Position( oldirrvals, orb[i] );
 if pos = fail then
 orb[i]:= Character( tbl, orb[i] );
 else
 orb[i]:= irr[ pos ];
 fi;
 od;
 od;
 fi;

 fi;

 return orbits;
end );

##############################################################################
##
#F OrbitRepresentativesCharacters( <irr> )
##
InstallGlobalFunction( OrbitRepresentativesCharacters, function( irr )
 local irrvals, # list of value lists
 oldirrvals, # store original succession
 chi, # loop over `irrvals'
 linear, # linear characters in `irr'
 nonlin, # nonlinear characters in `irr'
 repres, # list of representatives, result
 orb; # one orbit

 repres:= [];

 if not IsEmpty( irr ) then

 if IsCharacter( irr[1] ) then

 # Replace group characters by their value lists.
 # Store the succession in the original list.
 irrvals:= List( irr, ValuesOfClassFunction );
 oldirrvals:= ShallowCopy( irrvals );
 irrvals:= Set( irrvals );

 else
 irrvals:= Set( irr );
 fi;

 # Get the linear characters.
 linear := [];
 nonlin := [];
 for chi in irrvals do
 if chi[1] = 1 then
 Add( linear, chi );
 else
 Add( nonlin, chi );
 fi;
 od;
 if Length( linear ) > 0 then
 repres[1]:= linear[1];
 fi;

 # Compute orbits and remove them until the set is empty.
 while Length( nonlin ) > 0 do
 Add( repres, nonlin[1] );
 orb:= OrbitChar( nonlin[1], linear );
 SubtractSet( nonlin, orb );
 od;

 # Replace the value lists by the group characters
 # if the input was a list of characters.
 # Do not copy characters!
 if IsCharacter( irr[1] ) then
 repres:= List( repres, x -> irr[ Position( oldirrvals, x ) ] );
 fi;

 fi;

 # Return the representatives.
 return repres;
end );

#############################################################################
##
#F CharacterTableQuaternionic( <4n> )
##
InstallGlobalFunction( CharacterTableQuaternionic, function( 4n )
 local quaternionic;

 if 4n mod 4 <> 0 then
 Error( "argument must be a multiple of 4" );
 elif 4n = 4 then
 quaternionic:= CharacterTable( "Cyclic", 4 );
 else
 quaternionic:= CharacterTableIsoclinic(
 CharacterTable( "Dihedral", 4n ),
 [ 1 .. 4n / 4 + 1 ] );
 fi;
 ResetFilterObj( quaternionic, HasIdentifier );
 SetIdentifier( quaternionic, Concatenation( "Q", String( 4n ) ) );
 return quaternionic;
end );

#############################################################################
##
#F CollapsedMat( <mat>, <maps> )
##
InstallGlobalFunction( CollapsedMat, function( mat, maps )
 local i, j, k, nontrivblock, nontrivblocks, row, newblocks, values,
 blocks, pos, minima, fusion;

 # Compute successivly the partition of column families defined by
 # the rows already processed.
 nontrivblocks:= [ [ 1 .. Length( mat[1] ) ] ];
 for row in Concatenation( maps, mat ) do
 newblocks:= [];
 for nontrivblock in nontrivblocks do
 values:= [];
 blocks:= [];
 for k in nontrivblock do
 pos:= 1;
 while pos <= Length( values ) and values[ pos ] <> row[k] do
 pos:= pos + 1;
 od;
 if Length( values ) < pos then
 values[ pos ]:= row[k];
 blocks[ pos ]:= [ k ];
 else
 AddSet( blocks[ pos ], k );
 fi;
 od;
 for k in blocks do
 if 1 < Length( k ) then Add( newblocks, k ); fi;
 od;
 od;
 nontrivblocks:= newblocks;
 od;

 minima:= List( nontrivblocks, Minimum );
 nontrivblocks:= Permuted( nontrivblocks, Sortex( minima ) );
 minima:= Concatenation( [ 0 ], minima );
 fusion:= [];
 pos:= 1;
 for i in [ 1 .. Length( minima ) - 1 ] do
 for j in [ minima[i] + 1 .. minima[i+1] - 1 ] do
 if not IsBound( fusion[j] ) then
 fusion[j]:= pos;
 pos:= pos + 1;
 fi;
 od;
 for j in nontrivblocks[i] do fusion[j]:= pos; od;
 pos:= pos + 1;
 od;
 for i in [ Last(minima) + 1 .. Length( mat[1] ) ] do
 if not IsBound( fusion[i] ) then
 fusion[i]:= pos;
 pos:= pos + 1;
 fi;
 od;

 values:= ProjectionMap( fusion );
 return rec( mat:= List( mat, x -> x{ values } ),
#T do I really need the component 'mat'?
 fusion:= fusion );
end );

Quelle ctblfuns.gi Sprache: unbekannt

[Dauer der Verarbeitung: 0.114 Sekunden, vorverarbeitet 2026-04-25]