%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  characte.tex                GAP documentation               Thomas Breuer
%A                                                              & Ansgar Kaup
%A                                                           & Goetz Pfeiffer
%%
%A  @(#)$Id: characte.tex,v 3.29 1994/07/07 17:55:46 mschoene Rel $
%%
%Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
%%
%H  $Log: characte.tex,v $
%H  Revision 3.29  1994/07/07  17:55:46  mschoene
%H  changed introduction slightly to avoid moving reference
%H
%H  Revision 3.28  1994/06/18  12:17:42  sam
%H  fixed 'identifier' component
%H
%H  Revision 3.27  1994/06/17  19:01:17  vfelsch
%H  examples adjusted to version 3.4
%H
%H  Revision 3.26  1994/06/10  04:26:08  vfelsch
%H  updated examples
%H
%H  Revision 3.25  1994/06/03  08:57:20  mschoene
%H  changed a few things to avoid LaTeX warnings
%H
%H  Revision 3.24  1994/05/30  14:50:56  vfelsch
%H  index entries rearranged
%H
%H  Revision 3.23  1994/03/14  12:07:11  sam
%H  added documentation of 'MolienSeries'
%H
%H  Revision 3.22  1993/11/09  00:08:10  martin
%H  fixed overfull box
%H
%H  Revision 3.21  1993/11/02  12:01:55  sam
%H  changed description of 'LLL' functions
%H
%H  Revision 3.20  1993/02/19  10:48:42  gap
%H  adjustments in line length and spelling
%H
%H  Revision 3.19  1993/02/15  08:34:24  felsch
%H  examples fixed
%H
%H  Revision 3.18  1993/02/13  10:29:37  felsch
%H  some examples fixed
%H
%H  Revision 3.17  1992/11/16  16:42:06  sam
%H  generalized 'PermCharInfo'
%H
%H  Revision 3.16  1992/10/08  10:20:32  sam
%H  added 'ATLAS' component in 'PermCharInfo'
%H
%H  Revision 3.15  1992/08/07  08:02:49  sam
%H  extended description of 'Indicator'
%H
%H  Revision 3.14  1992/07/03  10:11:14  sam
%H  changed the author line,
%H  added 'PermCharInfo'
%H
%H  Revision 3.13  1992/06/19  11:40:35  sam
%H  added description of 'LLLReducedGramMat', 'OrthogonalEmbeddings',
%H  'Extract', 'Decreased', and 'DnLattice'
%H
%H  Revision 3.12  1992/05/26  16:57:17  sam
%H  added description of 'Subroutines of Decomposition'
%H
%H  Revision 3.11  1992/04/07  23:05:55  martin
%H  changed the author line
%H
%H  Revision 3.10  1992/03/26  13:37:18  sam
%H  changed arguments of 'Reduced'
%H
%H  Revision 3.9  1992/03/13  18:20:01  goetz
%H  changed section 'PermChars'.
%H
%H  Revision 3.8  1992/02/14  13:32:54  sam
%H  added documentation of 'Eigenvalues'
%H
%H  Revision 3.7  1992/02/03  17:18:51  sam
%H  changed 'LLL' description, reformatted file (now at most 73 chars)
%H
%H  Revision 3.6  1992/01/23  11:25:06  sam
%H  changed description of 'OrthogonalComponents', 'SymplecticComponents',
%H  changed usage of 'MatScalarProducts'
%H
%H  Revision 3.5  1992/01/17  09:25:18  sam
%H  changed usage of 'Tensored', 'Symmetrisations' and
%H  'MurnaghanComponents'
%H
%H  Revision 3.4  1992/01/14  14:13:15  martin
%H  changed two more citations
%H
%H  Revision 3.3  1992/01/14  13:55:23  sam
%H  adjusted citations
%H
%H  Revision 3.2  1991/12/30  09:37:59  sam
%H  corrected a word
%H
%H  Revision 3.1  1991/12/30  08:05:12  sam
%H  initial revision under RCS
%H
%%
\Chapter{Characters}

The functions described in this chapter are used to handle characters
(see Chapter "Character Tables"). For this, in many cases one needs maps
(see Chapter "Maps and Parametrized Maps").

There are four kinds of functions\:

First, those functions which get informations about characters; they
compute the scalar product of characters (see "ScalarProduct",
"MatScalarProducts"), decomposition matrices (see "Decomposition",
"Subroutines of Decomposition"), the kernel of a character (see
"KernelChar"), $p$-blocks (see "PrimeBlocks"), Frobenius-Schur indicators
(see "Indicator"), eigenvalues of the corresponding representations (see
"Eigenvalues"), and Molien series of characters (see "MolienSeries"), and
decide if a character might be a permutation character candidate (see
"Permutation Character Candidates").

Second, those functions which construct characters or virtual characters,
that is, differences of characters; these functions compute reduced
characters (see "Reduced", "ReducedOrdinary"), tensor products (see
"Tensored"), symmetrisations (see "Symmetrisations", "SymmetricParts",
"AntiSymmetricParts", "MinusCharacter", "OrthogonalComponents",
"SymplecticComponents"), and irreducibles differences of virtual
characters (see "IrreducibleDifferences").  Further, one can compute
restricted characters (see "Restricted"), inflated characters (see
"Inflated"), induced characters (see "Induced", "InducedCyclic"), and
permutation character candidates (see "Permutation Character Candidates",
"PermChars").

Third, those functions which use general methods for lattices.  These are
the LLL algorithm to compute a lattice base consisting of short vectors
(see "LLLReducedBasis", "LLLReducedGramMat", "LLL"), functions to compute
all orthogonal embeddings of a lattice (see "OrthogonalEmbeddings"), and
one for the special case of $D_n$ lattices (see "DnLattice").  A
backtrack search for irreducible characters in the span of proper
characters is performed by "Extract".

Finally, those functions which find special elements of parametrized
characters (see "More about Maps and Parametrized Maps"); they compute
the set of contained virtual characters (see "ContainedDecomposables") or
characters (see "ContainedCharacters"), the set of contained vectors
which possibly are virtual characters (see "ContainedSpecialVectors",
"ContainedPossibleVirtualCharacters") or characters (see
"ContainedPossibleCharacters").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ScalarProduct}%
\index{characters!scalar product of}

'ScalarProduct( <tbl>, <character1>, <character2> )'

returns the scalar product of <character1> and <character2>, regarded as
characters of the character table <tbl>.

|    gap> t:= CharTable( "A5" );;
    gap> ScalarProduct( t, t.irreducibles[1], [ 5, 1, 2, 0, 0 ] );
    1
    gap> ScalarProduct( t, [ 4, 0, 1, -1, -1 ], [ 5, -1, 1, 0, 0 ] );
    2/3|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{MatScalarProducts}%
\index{characters!scalar product of}

'MatScalarProducts( <tbl>, <chars1>, <chars2> )'\\
'MatScalarProducts( <tbl>, <chars> )'

For a character table <tbl> and two lists <chars1>, <chars2> of
characters, the first version returns the matrix of scalar products
(see "ScalarProduct"); we have

$'MatScalarProducts( <tbl>, <chars1>, <chars2> )[i][j]' =
 'ScalarProduct( <tbl>, <chars1>[j], <chars2>[i] )'$,

i.e., row 'i' contains the scalar products of '<chars2>[i]' with all
characters in <chars1>.

The second form returns a lower triangular matrix of scalar products\:

$'MatScalarProducts( <tbl>, <chars> )[i][j]' =
 'ScalarProduct( <tbl>, <chars>[j], <chars>[i] )'$

for $'j' \leq 'i'$.

|    gap> t:= CharTable( "A5" );;
    gap> chars:= Sublist( t.irreducibles, [ 2 .. 4 ] );;
    gap> chars:= Set( Tensored( chars, chars ) );;
    gap> MatScalarProducts( t, chars );
    [ [ 2 ], [ 1, 3 ], [ 1, 2, 3 ], [ 2, 2, 1, 3 ], [ 2, 1, 2, 2, 3 ],
      [ 2, 3, 3, 3, 3, 5 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Decomposition}%
\index{decomposition matrix}%
\index{DEC}

'Decomposition( <A>, <B>, <depth> )'\\
'Decomposition( <A>, <B>, \"nonnegative\" )'

For a $m \times n$ matrix <A> of cyclotomics that has rank $m \leq n$,
and a list <B> of cyclotomic vectors, each of dimension $n$,
'Decomposition' tries to find integral solutions <x> of the linear
equation systems '<x> \* <A> = <B>[i]' by computing the $p$--adic
series of hypothetical solutions.

\vspace{5mm}
'Decomposition( <A>, <B>, <depth> )', where <depth> is a nonnegative
integer, computes for every vector '<B>[i]' the initial part
$\sum_{k=0}^{<depth>} x_k p^k$ (all $x_k$ integer vectors with entries
bounded by $\pm\frac{p-1}{2}$).  The prime $p$ is 83 first; if the
reduction of <A> modulo $p$ is singular, the next prime is chosen
automatically.

A list <X> is returned. If the computed initial part really *is* a
solution of '<x> \* <A> = <B>[i]', we have '<X>[i] = <x>', otherwise
'<X>[i] = false'.

\vspace{5mm}
'Decomposition( <A>, <B>, \"nonnegative\" )' assumes that the solutions
have only nonnegative entries, and that the first column of <A> consists
of positive integers.  In this case the necessary number <depth> of
iterations is computed; the 'i'-th entry of the returned list is 'false'
if there *exists* no nonnegative integral solution of the system
'<x> \* <A> = <B>[i]', and it is the solution otherwise.

If <A> is singular, an error is signalled.

|    gap> a5:= CharTable( "A5" );; a5m3:= CharTable( "A5mod3" );;
    gap> a5m3.irreducibles;
    [ [ 1, 1, 1, 1 ], [ 3, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
      [ 3, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, -1, -1 ] ]
    gap> reg:= CharTableRegular( a5, 3 );;
    gap> chars:= Restricted( a5, reg, a5.irreducibles );
    [ [ 1, 1, 1, 1 ], [ 3, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
      [ 3, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, -1, -1 ],
      [ 5, 1, 0, 0 ] ]
    gap> Decomposition( a5m3.irreducibles, chars, "nonnegative" );
    [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ],
      [ 1, 0, 0, 1 ] ]
    gap> last * a5m3.irreducibles = chars;
    true|

For the subroutines of 'Decomposition', see "Subroutines of
Decomposition".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Subroutines of Decomposition}

Let $A$ be a square integral matrix, $p$ an odd prime.  The reduction of
$A$ modulo $p$ is $\overline{A}$, its entries are chosen in the interval
$[-\frac{p-1}{2}, \frac{p-1}{2}]$.  If $\overline{A}$ is regular over the
field with $p$ elements, we can form $A^{\prime} = \overline{A}^{-1}$.
Now consider the integral linear equation system $x A = b$, i.e., we look
for an integral solution $x$.  Define $b_0 = b$, and then iteratively
compute

\[ x_i = (b_i A^{\prime}) \bmod p,\ \ b_{i+1} = \frac{1}{p} (b_i - x_i A)
   \mbox{\rm\ for} i = 0, 1, 2, \ldots \ . \]

By induction, we get

\[ p^{i+1} b_{i+1} + ( \sum_{j=0}^{i} p^j x_j ) A = b . \]

If there is an integral solution $x$, it is unique, and there is an index
$l$ such that $b_{l+1}$ is zero and $x = \sum_{j=0}^{l} p^j x_j$.

There are two useful generalizations.  First, $A$ need not be square;
it is only necessary that there is a square regular matrix
formed by a subset of columns.  Second, $A$ does not need to be integral;
the entries may be cyclotomic integers as well, in this case one has to
replace each column of <A> by the columns formed by the coefficients
(which are integers).
Note that this preprocessing must be performed compatibly for <A> and <b>.

And these are the subroutines called by 'Decomposition'\:

\vspace{5mm}
'LinearIndependentColumns( <A> )'%
\index{LinearIndependentColumns}

returns for a matrix <A> a maximal list <lic> of positions such that the
rank of 'List( <A>, x -> Sublist( x, <lic> ) )' is the same as the rank
of <A>.

\vspace{5mm}
'InverseMatMod( <A>, <p> )'%
\index{InverseMatMod}

returns for a square integral matrix <A> and a prime <p> a matrix
$A^{\prime}$ with the property that $A^{\prime} A$ is congruent to the
identity matrix modulo <p>; if <A> is singular modulo <p>, 'false' is
returned.

\vspace{5mm}
'PadicCoefficients( <A>, <Amodpinv>, <b>, <p>, <depth> )'%
\index{PadicCoefficients}

returns the list $[ x_0, x_1, \ldots, x_l, b_{l+1} ]$ where $l = <depth>$
or $l$ is minimal with the property that $b_{l+1} = 0$.

\vspace{5mm}
'IntegralizedMat( <A> )'%
\index{IntegralizedMat}\\
'IntegralizedMat( <A>, <inforec> )'

return for a matrix <A> of cyclotomics a record <intmat> with components
'mat' and 'inforec'.  Each family of galois conjugate columns of <A> is
encoded in a set of columns of the rational matrix '<intmat>.mat' by
replacing cyclotomics by their coefficients.  '<intmat>.inforec' is a
record containing the information how to encode the columns.

If the only argument is <A>, the component 'inforec' is computed that
can be entered as second argument <inforec> in a later call of
'IntegralizedMat' with a matrix <B> that shall be encoded compatible
with <A>.

\vspace{5mm}
'DecompositionInt( <A>, <B>, <depth> )'%
\index{DecompositionInt}

does the same as 'Decomposition' (see "Decomposition"), but only for
integral matrices <A>, <B>, and nonnegative integers <depth>.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{KernelChar}

'KernelChar( <char> )'

returns the set of classes which form the kernel of the character <char>,
i.e. the set of positions $i$ with $<char>[i] = <char>[1]$.

For a factor fusion map <fus>, 'KernelChar( <fus> )' is the kernel of the
epimorphism.

|    gap> s4:= CharTable( "Symmetric", 4 );;
    gap> s4.irreducibles;
    [ [ 1, -1, 1, 1, -1 ], [ 3, -1, -1, 0, 1 ], [ 2, 0, 2, -1, 0 ],
      [ 3, 1, -1, 0, -1 ], [ 1, 1, 1, 1, 1 ] ]
    gap> List( last, KernelChar );
    [ [ 1, 3, 4 ], [ 1 ], [ 1, 3 ], [ 1 ], [ 1, 2, 3, 4, 5 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PrimeBlocks}

'PrimeBlocks( <tbl>, <prime> )'\\
'PrimeBlocks( <tbl>, <chars>, <prime> )'

For a character table <tbl> and a prime <prime>,
'PrimeBlocks( <tbl>, <chars>, <prime> )' returns a record with fields

'block':\\
     a list of positive integers which has the same length as the list
     <chars> of characters,
     the entry <n> at position <i> in that list means that '<chars>[<i>]'
     belongs to the <n>-th <prime>-block

'defect':\\
     a list of nonnegative integers, the value at position <i> is the
     defect of the <i>--th block.

'PrimeBlocks( <tbl>, <prime> )' does the same for
'<chars> = <tbl>.irreducibles', and additionally the result is stored
in the 'irredinfo' field of <tbl>.

|    gap> t:= CharTable( "A5" );;
    gap> PrimeBlocks( t, 2 ); PrimeBlocks( t, 3 ); PrimeBlocks( t, 5 );
    rec(
      block := [ 1, 1, 1, 2, 1 ],
      defect := [ 2, 0 ] )
    rec(
      block := [ 1, 2, 3, 1, 1 ],
      defect := [ 1, 0, 0 ] )
    rec(
      block := [ 1, 1, 1, 1, 2 ],
      defect := [ 1, 0 ] )
    gap> InverseMap( last.block ); # distribution of characters to blocks
    [ [ 1, 2, 3, 4 ], 5 ]|

If 'InfoCharTable2 = Print', the defects of the blocks and the heights of
the contained characters are printed.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Indicator}%
\index{Frobenius Schur indicator}

'Indicator( <tbl>, <n> )'\\
'Indicator( <tbl>, <chars>, <n> )'\\
'Indicator( <modtbl>, 2 )'

For a character table <tbl>, 'Indicator( <tbl>, <chars>, <n> )' returns
the list of <n>-th Frobenius Schur indicators for the list <chars> of
characters.

'Indicator( <tbl>, <n> )' does the same for
'<chars> = <tbl>.irreducibles', and additionally the result is stored
in the field 'irredinfo' of <tbl>.

'Indicator( <modtbl>, 2 )' returns the list of 2nd indicators for the
irreducible characters of the Brauer character table <modtbl> and stores
the indicators in the 'irredinfo' component of <modtbl>; this does not
work for tables in characteristic 2.

|    gap> t:= CharTable( "M11" );; Indicator( t, t.irreducibles, 2 );
    [ 1, 1, 0, 0, 1, 0, 0, 1, 1, 1 ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Eigenvalues}

'Eigenvalues( <tbl>, <char>, <class> )'

Let $M$ be a matrix of a representation with character <char> which is
a character of the table <tbl>, for an element in the conjugacy class
<class>.
'Eigenvalues( <tbl>, <char>, <class> )' returns a list of length
'$n$ = <tbl>.orders[ <class> ]' where at position 'i' the multiplicity
of 'E(n)\^i = $e^{\frac{2\pi i}{n}}$' as eigenvalue of $M$ is stored.

|    gap> t:= CharTable( "A5" );;
    gap> chi:= t.irreducibles[2];
    [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ]
    gap> List( [ 1 .. 5 ], i -> Eigenvalues( t, chi, i ) );
    [ [ 3 ], [ 2, 1 ], [ 1, 1, 1 ], [ 0, 1, 1, 0, 1 ], [ 1, 0, 0, 1, 1 ] ]|

'List( [1..<n>], i -> E(n)\^i) \*\ Eigenvalues(<tbl>,<char>,<class>) )'
is equal to '<char>[ <class> ]'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{MolienSeries}

'MolienSeries( <psi> )' \\
'MolienSeries( <psi>, <chi> )' \\
'MolienSeries( <tbl>, <psi> )' \\
'MolienSeries( <tbl>, <psi>, <chi> )'

returns a record that describes the series
\[ M_{\psi,\chi}(z) = \sum_{d=0}^{\infty} (\chi,\psi^{[d]}) z^d \]
where $\psi^{[d]}$ denotes the symmetrization of $\psi$ with the trivial
character of the symmetric group $S_d$ (see "SymmetricParts").

<psi> and <chi> must be characters of the table <tbl>,
the default for $\chi$ is the trivial character.
If no character table is given, <psi> and <chi> must be class function
recods.

\vspace{3mm}

'ValueMolienSeries( <series>, <i> )'%
\index{ValueMolienSeries}

returns the <i>-th coefficient of the Molien series <series>.

|    gap> psi:= Irr( CharTable( "A5" ) )[3];
    Character( CharTable( "A5" ),
    [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ] )
    gap> mol:= MolienSeries( psi );;
    gap> List( [ 1 .. 10 ], i -> ValueMolienSeries( mol, i ) );
    [ 0, 1, 0, 1, 0, 2, 0, 2, 0, 3 ] |

The record returned by 'MolienSeries' has components

'summands': \\ a list of records with components 'numer', 'r', and 'k',
               describing the summand $'numer' / (1-z^r)^k$,

'size':     \\ the 'size' component of the character table,

'degree':   \\ the degree of <psi>.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Reduced}%
\index{characters!reduced}

'Reduced( <tbl>, <constituents>, <reducibles> )'\\
'Reduced( <tbl>, <reducibles> )'

returns a record with fields 'remainders' and 'irreducibles', both
lists\:\
Let 'rems' be the set of nonzero characters obtained from <reducibles>
by subtraction of

\[ \sum_{\chi\in 'constituents'}
   \frac{'ScalarProduct( <tbl>, \chi, <reducibles>[i] )'}
        {'ScalarProduct( <tbl>, \chi, <constituents>[j] )'}
   \cdot \chi \]

from '<reducibles>[i]' in the first case or subtraction of

\[ \sum_{j \leq i}
   \frac{'ScalarProduct( <tbl>, <reducibles>[j], <reducibles>[i] )'}
        {'ScalarProduct( <tbl>, <reducibles>[j], <reducibles>[j] )'}
   \cdot <reducibles>[j] \]

in the second case.

Let 'irrs' be the list of irreducible characters in 'rems'.  'rems' is
reduced with 'irrs' and all found irreducibles until no new irreducibles
are found. Then 'irreducibles' is the set of all found irreducible
characters, 'remainders' is the set of all nonzero remainders.

If one knows that <reducibles> are ordinary characters of <tbl> and
<constituents> are irreducible ones, "ReducedOrdinary" 'ReducedOrdinary'
may be faster.

Note that elements of 'remainders' may be only virtual characters even if
<reducibles> are ordinary characters.

|    gap> t:= CharTable( "A5" );;
    gap> chars:= Sublist( t.irreducibles, [ 2 .. 4 ] );;
    gap> chars:= Set( Tensored( chars, chars ) );;
    gap> Reduced( t, chars );
    rec(
      remainders := [  ],
      irreducibles :=
       [ [ 1, 1, 1, 1, 1 ], [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
          [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, 1, -1, -1 ],
          [ 5, 1, -1, 0, 0 ] ] )|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ReducedOrdinary}%
\index{characters!reduced}

'ReducedOrdinary( <tbl>, <constituents>, <reducibles> )'

works like "Reduced" 'Reduced', but assumes that the elements of
<constituents> and <reducibles> are ordinary characters of the character
table <tbl>.
So scalar products are calculated only for those pairs of characters
where the degree of the constituent is smaller than the degree of the
reducible.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Tensored}%
\index{characters!tensor products of}

'Tensored( <chars1>, <chars2> )'

returns the list of tensor products (i.e. pointwise products) of all
characters in the list <chars1> with all characters in the list <chars2>.

|    gap> t:= CharTable( "A5" );;
    gap> chars1:= Sublist( t.irreducibles, [ 1 .. 3 ] );;
    gap> chars2:= Sublist( t.irreducibles, [ 2 .. 3 ] );;
    gap> Tensored( chars1, chars2 );
    [ [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
      [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ],
      [ 9, 1, 0, -2*E(5)-E(5)^2-E(5)^3-2*E(5)^4,
          -E(5)-2*E(5)^2-2*E(5)^3-E(5)^4 ], [ 9, 1, 0, -1, -1 ],
      [ 9, 1, 0, -1, -1 ],
      [ 9, 1, 0, -E(5)-2*E(5)^2-2*E(5)^3-E(5)^4, -2*E(5)-E(5)^2-E(5)^3
             -2*E(5)^4 ] ]|

*Note* that duplicate tensor products are not deleted; the tensor product
of '<chars1>[<i>]' with '<chars2>[<j>]' is stored at position
$(i-1) 'Length( <chars1> )' + j$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Symmetrisations}%
\index{characters!symmetrisations of}

'Symmetrisations( <tbl>, <chars>, <Sn> )'\\
'Symmetrisations( <tbl>, <chars>, <n> )'

returns the list of nonzero symmetrisations of the characters <chars>,
regarded as characters of the character table <tbl>, with the ordinary
characters of the symmetric group of degree <n>; alternatively, the table
of the symmetric group can be entered as <Sn>.

The symmetrisation $\chi^{[\lambda]}$ of the character $\chi$ of <tbl>
with the character $\lambda$ of the symmetric group $S_n$ of degree $n$
is defined by
\[ \chi^{[\lambda]}(g) = \frac{1}{n!} \sum_{\rho \in S_n}
                \lambda(\rho) \prod_{k=1}^{n} \chi(g^k)^{a_k(\rho)}, \]
where $a_k(\rho)$ is the number of cycles of length $k$ in $\rho$.

For special symmetrisations, see "SymmetricParts", "AntiSymmetricParts",
"MinusCharacter" and "OrthogonalComponents", "SymplecticComponents".

|    gap> t:= CharTable( "A5" );;
    gap> chars:= Sublist( t.irreducibles, [ 1 .. 3 ] );;
    gap> Symmetrisations( t, chars, 3 );
    [ [ 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 1, 1, 1, 1, 1 ],
      [ 1, 1, 1, 1, 1 ], [ 8, 0, -1, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
      [ 10, -2, 1, 0, 0 ], [ 1, 1, 1, 1, 1 ],
      [ 8, 0, -1, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 10, -2, 1, 0, 0 ] ]|

*Note* that the returned list may contain zero characters, and duplicate
characters are not deleted.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SymmetricParts}%
\index{characters!symmetrisations of}

'SymmetricParts( <tbl>, <chars>, <n> )'

returns the list of symmetrisations of the characters <chars>,
regarded as characters of the character table <tbl>, with the trivial
character of the symmetric group of degree <n> (see "Symmetrisations").

|    gap> t:= CharTable( "A5" );;
    gap> SymmetricParts( t, t.irreducibles, 3 );
    [ [ 1, 1, 1, 1, 1 ], [ 10, -2, 1, 0, 0 ], [ 10, -2, 1, 0, 0 ],
      [ 20, 0, 2, 0, 0 ], [ 35, 3, 2, 0, 0 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{AntiSymmetricParts}%
\index{characters!symmetrisations of}

'AntiSymmetricParts( <tbl>, <chars>, <n> )'

returns the list of symmetrisations of the characters <chars>,
regarded as characters of the character table <tbl>, with the alternating
character of the symmetric group of degree <n> (see "Symmetrisations").

|    gap> t:= CharTable( "A5" );;
    gap> AntiSymmetricParts( t, t.irreducibles, 3 );
    [ [ 0, 0, 0, 0, 0 ], [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 1, 1 ],
      [ 4, 0, 1, -1, -1 ], [ 10, -2, 1, 0, 0 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{MinusCharacter}%
\index{characters!symmetrisations of}

'MinusCharacter( <char>, <prime\_powermap>, <prime> )'

returns the (possibly parametrized, see chapter "Maps and Parametrized
Maps") character $\chi^{p-}$ for the character $\chi = <char>$ and a
prime $p = <prime>$, where $\chi^{p-}$ is defined by
$\chi^{p-}(g) = ( \chi(g)^p - \chi(g^p) ) / p$, and
<prime\_powermap> is the (possibly parametrized) $p$-th powermap.

|    gap> t:= CharTable( "S7" );; pow:= InitPowermap( t, 2 );;
    gap> Congruences( t, t.irreducibles, pow, 2 );; pow;
    [ 1, 1, 3, 4, [ 2, 9, 10 ], 6, 3, 8, 1, 1, [ 2, 9, 10 ], 3, 4, 6,
      [ 7, 12 ] ]
    gap> chars:= Sublist( t.irreducibles, [ 2 .. 5 ] );;
    gap> List( chars, x-> MinusCharacter( x, pow, 2 ) );
    [ [ 0, 0, 0, 0, [ 0, 1 ], 0, 0, 0, 0, 0, [ 0, 1 ], 0, 0, 0, [ 0, 1 ] ],
      [ 15, -1, 3, 0, [ -2, -1, 0 ], 0, -1, 1, 5, -3, [ 0, 1, 2 ], -1, 0,
          0, [ 0, 1 ] ],
      [ 15, -1, 3, 0, [ -1, 0, 2 ], 0, -1, 1, 5, -3, [ 1, 2, 4 ], -1, 0,
          0, 1 ],
      [ 190, -2, 1, 1, [ 0, 2 ], 0, 1, 1, -10, -10, [ 0, 2 ], -1, -1, 0,
          [ -1, 0 ] ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OrthogonalComponents}%
\index{symmetrizations!orthogonal}%
\index{Frame}%
\index{Murnaghan components}

'OrthogonalComponents( <tbl>, <chars>, <m> )'

If $\chi$ is a (nonlinear) character with indicator $+1$, a splitting
of the tensor power $\chi^m$ is given by the so-called Murnaghan
functions (see~\cite{Mur58}).  These components in general have fewer
irreducible constituents than the symmetrizations with the symmetric
group of degree <m> (see "Symmetrisations").

'OrthogonalComponents' returns the set of orthogonal symmetrisations of
the characters of the character table <tbl> in the list <chars>, up to
the power <m>, where the integer <m> is one of $\{ 2, 3, 4, 5, 6 \}$.

*Note*\:\ It is not checked if all characters in <chars> do really have
indicator $+1$; if there are characters with indicator 0 or $-1$, the
result might contain virtual characters, see also "SymplecticComponents".

The Murnaghan functions are implemented as in~\cite{Fra82}.

|    gap> t:= CharTable( "A8" );; chi:= t.irreducibles[2];
    [ 7, -1, 3, 4, 1, -1, 1, 2, 0, -1, 0, 0, -1, -1 ]
    gap> OrthogonalComponents( t, [ chi ], 4 );
    [ [ 21, -3, 1, 6, 0, 1, -1, 1, -2, 0, 0, 0, 1, 1 ],
      [ 27, 3, 7, 9, 0, -1, 1, 2, 1, 0, -1, -1, -1, -1 ],
      [ 105, 1, 5, 15, -3, 1, -1, 0, -1, 1, 0, 0, 0, 0 ],
      [ 35, 3, -5, 5, 2, -1, -1, 0, 1, 0, 0, 0, 0, 0 ],
      [ 77, -3, 13, 17, 2, 1, 1, 2, 1, 0, 0, 0, 2, 2 ],
      [ 189, -3, -11, 9, 0, 1, 1, -1, 1, 0, 0, 0, -1, -1 ],
      [ 330, -6, 10, 30, 0, -2, -2, 0, -2, 0, 1, 1, 0, 0 ],
      [ 168, 8, 8, 6, -3, 0, 0, -2, 2, -1, 0, 0, 1, 1 ],
      [ 35, 3, -5, 5, 2, -1, -1, 0, 1, 0, 0, 0, 0, 0 ],
      [ 182, 6, 22, 29, 2, 2, 2, 2, 1, 0, 0, 0, -1, -1 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SymplecticComponents}%
\index{symmetrizations!symplectic}%
\index{Murnaghan components}

'SymplecticComponents( <tbl>, <chars>, <m> )'

If $\chi$ is a (nonlinear) character with indicator $-1$, a splitting
of the tensor power $\chi^m$ is given in terms of the so-called
Murnaghan functions (see~\cite{Mur58}).  These components in general
have fewer irreducible constituents than the symmetrizations with the
symmetric group of degree <m> (see "Symmetrisations").

'SymplecticComponents' returns the set of symplectic symmetrisations of
the characters of the character table <tbl> in the list <chars>, up to
the power <m>, where the integer <m> is one of $\{ 2, 3, 4, 5 \}$.

*Note*\:\ It is not checked if all characters in <chars> do really have
indicator $-1$; if there are characters with indicator 0 or $+1$, the
result might contain virtual characters, see also "OrthogonalComponents".

|    gap> t:= CharTable( "U3(3)" );; chi:= t.irreducibles[2];
    [ 6, -2, -3, 0, -2, -2, 2, 1, -1, -1, 0, 0, 1, 1 ]
    gap> SymplecticComponents( t, [ chi ], 4 );
    [ [ 14, -2, 5, -1, 2, 2, 2, 1, 0, 0, 0, 0, -1, -1 ],
      [ 21, 5, 3, 0, 1, 1, 1, -1, 0, 0, -1, -1, 1, 1 ],
      [ 64, 0, -8, -2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 ],
      [ 14, 6, -4, 2, -2, -2, 2, 0, 0, 0, 0, 0, -2, -2 ],
      [ 56, -8, 2, 2, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0 ],
      [ 70, -10, 7, 1, 2, 2, 2, -1, 0, 0, 0, 0, -1, -1 ],
      [ 189, -3, 0, 0, -3, -3, -3, 0, 0, 0, 1, 1, 0, 0 ],
      [ 90, 10, 9, 0, -2, -2, -2, 1, -1, -1, 0, 0, 1, 1 ],
      [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
      [ 126, 14, -9, 0, 2, 2, 2, -1, 0, 0, 0, 0, -1, -1 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IrreducibleDifferences}%
\index{characters!irreducible differences of}

'IrreducibleDifferences( <tbl>, <chars1>, <chars2> )'\\
'IrreducibleDifferences( <tbl>, <chars1>, <chars2>, <scprmat> )'\\
'IrreducibleDifferences( <tbl>, <chars>, \"triangle\" )'\\
'IrreducibleDifferences( <tbl>, <chars>, \"triangle\", <scprmat> )'

returns the list of irreducible characters which occur as difference of
two elements of <chars> (if '\"triangle\"' is specified) or of an
element of <chars1> and an element of <chars2>; if <scprmat> is not
specified it will be computed (see "MatScalarProducts"), otherwise we
must have
\[ '<scprmat>[i][j] = ScalarProduct( <tbl>, <chars>[i], <chars>[j] )'
\] resp. \[
   '<scprmat>[i][j] = ScalarProduct( <tbl>, <chars1>[i], <chars2>[j] )'
\].

|    gap> t:= CharTable( "A5" );;
    gap> chars:= Sublist( t.irreducibles, [ 2 .. 4 ] );;
    gap> chars:= Set( Tensored( chars, chars ) );;
    gap> IrreducibleDifferences( t, chars, "triangle" );
    [ [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
      [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Restricted}%
\index{characters!restricted}

'Restricted( <tbl>, <subtbl>, <chars> )'\\
'Restricted( <tbl>, <subtbl>, <chars>, <specification> )'\\
'Restricted( <chars>, <fusionmap> )'

returns the restrictions, i.e. the indirections, of the characters in the
list <chars> by a subgroup fusion map.
This map can either be entered directly as <fusionmap>, or it must be
stored on the character table <subtbl> and must have destination <tbl>;
in the latter case the value of the 'specification' field of the desired
fusion may be specified as <specification> (see "GetFusionMap").
If no such fusion is stored, 'false' is returned.

The fusion map may be a parametrized map
(see "More about Maps and Parametrized Maps");
any value that is not uniquely determined in a restricted character is
set to an unknown (see "Unknown"); for parametrized indirection of
characters, see "CompositionMaps".

Restriction and inflation are the same procedures, so 'Restricted'
and 'Inflated' are identical, see "Inflated".

|    gap> s5:= CharTable( "A5.2" );; a5:= CharTable( "A5" );;
    gap> Restricted( s5, a5, s5.irreducibles );
    [ [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 1, 1 ], [ 6, -2, 0, 1, 1 ],
      [ 4, 0, 1, -1, -1 ], [ 4, 0, 1, -1, -1 ], [ 5, 1, -1, 0, 0 ],
      [ 5, 1, -1, 0, 0 ] ]
    gap> Restricted( s5.irreducibles, [ 1, 6, 2, 6 ] );
                        # restrictions to the cyclic group of order 4
    [ [ 1, 1, 1, 1 ], [ 1, -1, 1, -1 ], [ 6, 0, -2, 0 ], [ 4, 0, 0, 0 ],
      [ 4, 0, 0, 0 ], [ 5, -1, 1, -1 ], [ 5, 1, 1, 1 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Inflated}%
\index{characters!inflated}

'Inflated( <factortbl>, <tbl>, <chars> )'\\
'Inflated( <factortbl>, <tbl>, <chars>, <specification> )'\\
'Inflated( <chars>, <fusionmap> )'

returns the inflations, i.e. the indirections of <chars> by a factor
fusion map.  This map can either be entered directly as <fusionmap>, or
it must be stored on the character table <tbl> and must have destination
<factortbl>; in the latter case the value of the 'specification' field
of the desired fusion may be specified as <specification> (see
"GetFusionMap").  If no such fusion is stored, 'false' is returned.

The fusion map may be a parametrized map (see "More about Maps and
Parametrized Maps"); any value that is not uniquely determined in an
inflated character is set to an unknown (see "Unknown"); for parametrized
indirection of characters, see "CompositionMaps".

Restriction and inflation are the same procedures, so 'Restricted'
and 'Inflated' are identical, see "Restricted".

|    gap> s4:= CharTable( "Symmetric", 4 );;
    gap> s3:= CharTableFactorGroup( s4, [3] );;
    gap> s3.irreducibles;
    [ [ 1, -1, 1 ], [ 2, 0, -1 ], [ 1, 1, 1 ] ]
    gap> s4.fusions;
    [ rec(
          map := [ 1, 2, 1, 3, 2 ],
          type := "factor",
          name := [ 'S', '4', '/', '[', ' ', '3', ' ', ']' ] ) ]
    gap> Inflated( s3, s4, s3.irreducibles );
    [ [ 1, -1, 1, 1, -1 ], [ 2, 0, 2, -1, 0 ], [ 1, 1, 1, 1, 1 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Induced}%
\index{characters!induced}

'Induced( <subtbl>, <tbl>, <chars> )'\\
'Induced( <subtbl>, <tbl>, <chars>, <specification> )'\\
'Induced( <subtbl>, <tbl>, <chars>, <fusionmap> )'

returns a set of characters induced from <subtbl> to <tbl>; the elements
of the list <chars> will be induced. The subgroup fusion map can either
be entered directly as <fusionmap>, or it must be stored on the table
<subtbl> and must have destination <tbl>; in the latter case the value
of the 'specification' field may be specified by <specification>
(see "GetFusionMap"). If no such fusion is stored, 'false' is returned.

The fusion map may be a parametrized map
(see "More about Maps and Parametrized Maps");
any value that is not uniquely determined in an induced character is set
to an unknown (see "Unknown").

|    gap> Induced( a5, s5, a5.irreducibles );
    [ [ 2, 2, 2, 2, 0, 0, 0 ], [ 6, -2, 0, 1, 0, 0, 0 ],
      [ 6, -2, 0, 1, 0, 0, 0 ], [ 8, 0, 2, -2, 0, 0, 0 ],
      [ 10, 2, -2, 0, 0, 0, 0 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{InducedCyclic}%
\index{characters!induce from cyclic subgroups}

'InducedCyclic( <tbl> )'\\
'InducedCyclic( <tbl>, \"all\" )'\\
'InducedCyclic( <tbl>, <classes> )'\\
'InducedCyclic( <tbl>, <classes>, \"all\" )'

returns a set of characters of the character table <tbl>. They are
characters induced from cyclic subgroups of <tbl>.
If '\"all\"' is specified, all irreducible characters
of those subgroups are induced, otherwise only the permutation characters
are computed. If a list <classes> is specified, only those cyclic
subgroups generated by these classes are considered, otherwise all
classes of <tbl> are considered.

Note that the powermaps for primes dividing '<tbl>.order' must be stored
on <tbl>; if any powermap for a prime not dividing '<tbl>.order' that is
smaller than the maximal representative order is not stored, this map
will be computed (see "Powermap") and stored afterwards.

The powermaps may be parametrized maps
(see "More about Maps and Parametrized Maps");
any value that is not uniquely determined in an induced character is set
to an unknown (see "Unknown").
The representative orders of the classes to induce from must not be
parametrized (see "More about Maps and Parametrized Maps").

|    gap> t:= CharTable( "A5" );; InducedCyclic( t, "all" );
    [ [ 12, 0, 0, 2, 2 ], [ 12, 0, 0, E(5)^2+E(5)^3, E(5)+E(5)^4 ],
      [ 12, 0, 0, E(5)+E(5)^4, E(5)^2+E(5)^3 ], [ 20, 0, -1, 0, 0 ],
      [ 20, 0, 2, 0, 0 ], [ 30, -2, 0, 0, 0 ], [ 30, 2, 0, 0, 0 ],
      [ 60, 0, 0, 0, 0 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CollapsedMat}%
\index{classes!collapse}

'CollapsedMat( <mat>, <maps> )'

returns a record with fields 'mat' and 'fusion'\:\
The 'fusion' field contains the fusion that collapses the columns of
<mat> that are identical also for all maps in the list <maps>, the 'mat'
field contains the image of <mat> under that fusion.

|    gap> t.irreducibles;
    [ [ 1, 1, 1, 1, 1 ], [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ],
      [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, 1, -1, -1 ],
      [ 5, 1, -1, 0, 0 ] ]
    gap> t:= CharTable( "A5" );; RationalizedMat( t.irreducibles );
    [ [ 1, 1, 1, 1, 1 ], [ 6, -2, 0, 1, 1 ], [ 4, 0, 1, -1, -1 ],
      [ 5, 1, -1, 0, 0 ] ]
    gap> CollapsedMat( last, [] );
    rec(
      mat := [ [ 1, 1, 1, 1 ], [ 6, -2, 0, 1 ], [ 4, 0, 1, -1 ],
          [ 5, 1, -1, 0 ] ],
      fusion := [ 1, 2, 3, 4, 4 ] )
    gap> Restricted( last.mat, last.fusion );
    [ [ 1, 1, 1, 1, 1 ], [ 6, -2, 0, 1, 1 ], [ 4, 0, 1, -1, -1 ],
      [ 5, 1, -1, 0, 0 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Power}

'Power( <powermap>, <chars>, <n> )'

returns the list of indirections of the characters <chars> by the <n>-th
powermap; for a character $\chi$ in <chars>, this indirection is often
called $\chi^{(n)}$.  The powermap is calculated from the (necessarily
stored) powermaps of the prime divisors of <n> if it is not stored in
<powermap> (see "Powmap").

*Note* that $\chi^{(n)}$ is in general only a virtual characters.


|    gap> t:= CharTable( "A5" );; Power( t.powermap, t.irreducibles, 2 );
    [ [ 1, 1, 1, 1, 1 ], [ 3, 3, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ],
      [ 3, 3, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 4, 4, 1, -1, -1 ],
      [ 5, 5, -1, 0, 0 ] ]
    gap> MatScalarProducts( t, t.irreducibles, last );
    [ [ 1, 0, 0, 0, 0 ], [ 1, -1, 0, 0, 1 ], [ 1, 0, -1, 0, 1 ],
      [ 1, -1, -1, 1, 1 ], [ 1, -1, -1, 0, 2 ] ]|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Permutation Character Candidates}%
\index{characters!permutation}%
\index{candidates!for permutation characters}%
\index{permutation characters!candidates for}

For groups $H, G$ with $H\leq G$, the induced character $(1_G)^H$ is
called the *permutation character* of the operation of $G$ on the right
cosets of $H$.  If only the character table of $G$ is known, one can try
to get informations about possible subgroups of $G$ by inspection of
those characters $\pi$ which might be permutation characters, using that
such a character must have at least the following properties\:

:$\pi(1)$ divides $\|G\|$,

:$[\pi,\psi]\leq\psi(1)$ for each character $\psi$ of $G$,

:$[\pi,1_G]=1$,

:$\pi(g)$ is a nonnegative integer for $g \in G$,

:$\pi(g)$ is smaller than the centralizer order of $g$ for
      $1\not= g\in G$,

:$\pi(g)\leq\pi(g^m)$ for $g\in G$ and any integer $m$,

:$\pi(g)=0$ for every $\|g\|$ not diving $\frac{\|G\|}{\pi(1)}$,

:$\pi(1) \|N_G(g)\|$ divides $\|G\| \pi(g)$, where $\|N_G(g)\|$ denotes
      the normalizer order of $\langle g \rangle$.

Any character with these properties will be called a
*permutation character candidate* from now on.

{\GAP} provides some algorithms to compute permutation character
candidates, see "PermChars".  Some information about the subgroup
can computed from a permutation character using 'PermCharInfo'
(see "PermCharInfo").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsPermChar}%
\index{characters!permutation}%
\index{candidates!for permutation characters}%
\index{permutation characters!candidates for}

'IsPermChar( <tbl>, <pi> )'

*missing, like tests* 'TestPerm1', 'TestPerm2', 'TestPerm3'

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PermCharInfo}%
\index{subgroup and permutation character}

'PermCharInfo( <tbl>, <permchars> )'

Let <tbl> be the character table of the group $G$, and <permchars> the
permutation character $(1_U)^G$ for a subgroup $U$ of $G$, or a list
of such characters.
'PermCharInfo' returns a record with components

'contained':\\
  a list containing for each character in <permchars> a list containing
  at position <i> the number of elements of $U$ that are contained in
  class <i> of <tbl>, this is equal to
  $'permchar[<i>]' \|U\| / 'tbl.centralizers[<i>]'$,

'bound':\\
  Let '<permchars>[k]' be the permutation character $(1_U)^G$.  Then the
  class length in $U$ of an element in class <i> of <tbl> must be a
  multiple of the value
  $'bound[<k>][<i>]' = \|U\| / \gcd( \|U\|, '<tbl>.centralizers[<i>]' )$,

'display':\\
  a record that can be used as second argument of 'DisplayCharTable'
  to display the permutation characters and the corresponding components
  'contained' and 'bound', for the classes where at least one character
  of <permchars> is nonzero,

'ATLAS':\\
  list of strings containing for each character in <permchars> the
  decomposition into '<tbl>.irreducibles' in {\ATLAS} notation.

|    gap> t:= CharTable("A6");;
    gap> PermCharInfo( t, [ 15, 3, 0, 3, 1, 0, 0 ] );
    rec(
      contained := [ [ 1, 9, 0, 8, 6, 0, 0 ] ],
      bound := [ [ 1, 3, 8, 8, 6, 24, 24 ] ],
      display := rec(
          classes := [ 1, 2, 4, 5 ],
          chars := [ [ 15, 3, 0, 3, 1, 0, 0 ], [ 1, 9, 0, 8, 6, 0, 0 ],
              [ 1, 3, 8, 8, 6, 24, 24 ] ],
          letter := "I" ),
      ATLAS := [ "1a+5b+9a" ] )
    gap> DisplayCharTable( t, last.display );
    A6

         2  3  3  .  2
         3  2  .  2  .
         5  1  .  .  .

           1a 2a 3b 4a
        2P 1a 1a 3b 2a
        3P 1a 2a 1a 4a
        5P 1a 2a 3b 4a

    I.1    15  3  3  1
    I.2     1  9  8  6
    I.3     1  3  8  6|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Inequalities}

'Inequalities( <tbl> )'

The condition $\pi(g) \geq 0$ for every permutation character candidate
$\pi$ places restrictions on the multiplicities $a_i$ of the irreducible
constituents $\chi_i$ of $\pi = \sum_{i=1}^r a_i \chi_i$.
For every group element $g$ holds $\sum_{i=1}^r a_i \chi_i(g) \geq 0$.
The power map provides even stronger conditions.

This system of inequalities is kind of diagonalized, resulting in a
system of inequalities restricting $a_i$ in terms of $a_j, j \< i$.
These inequalities are used to construct characters with nonnegative
values (see "PermChars").
'PermChars' either calls 'Inequalities' or takes this information from
the record field 'ineq' of its argument record.

The number of inequalities arising in the process of diagonalization may
grow very strong.

There are two strategies to perform this diagonalization. The default is
to simply eliminate one unknown $a_i$ after the other with decreasing
$i$.  In some cases it turns out to be better first to look which choice
for the next unknown will yield the fewest new inequalities.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PermBounds}

'PermBounds( <tbl> )'

All characters $\pi$ satisfying $\pi(g) > 0$ and $\pi(1) = d$ for a given
degree $d$ lie in a simplex described by these conditions. 'PermBounds'
computes the boundary points of this simplex for $d = 0$, from which the
boundary points for any other $d$ are easily derived.
Some conditions from the powermap are also involved.

For this purpose a matrix similar to the rationalized character table
has to be inverted.

These boundary points are used by 'PermChars' (see "PermChars") to
construct all permutation character candidates of a given degree.
'PermChars' either calls 'PermBounds' or takes this information from
the record field 'bounds' of its argument record.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PermChars}%
\index{permutation characters}

'PermChars( <tbl> )' \\
'PermChars( <tbl>, <degree> )' \\
'PermChars( <tbl>, <arec> )'

{\GAP} provides  several  algorithms to  determine  permutation character
candidates from a given  character table.  The algorithm is selected from
the  choice of the  record fields of the optional argument record <arec>.
The  user is  encouraged to  try different approaches  especially  if one
choice fails to come to an end.

Regardless of the algorithm used in a special case, 'PermChars' returns a
list of *all* permutation character candidates with  the properties given
in <arec>.  There is no guarantee  that  a character of this  list  is in
fact a  permutation character. But an empty list always means there is no
permutation character with these properties (e.g.\ of a certain degree).

In  the  first  form  'PermChars(  <tbl>  )'  returns  the  list  of  all
permutation characters of the group with character table <tbl>. This list
might be  rather long  for big groups, and it might take  much time.  The
algorithm depends on a preprocessing step, where the inequalities arising
from the  condition  $\pi(g)  \leq  0$ are transformed  into  a system of
inequalities that guides the search (see "Inequalities").

|    gap> m11:= CharTable("M11");;
    gap> PermChars(m11);;     # will return the list of 39 permutation
                              # character candidates of $M11$. |

There are two different search strategies for  this algorithm. One simply
constructs all characters with nonnegative values and then tests for each
such character whether its degree is a divisor of the order of the group.
This is the default.  The other strategy uses the inequalities to predict
if  it  is  possible  to find  a character of  a  certain degree  in  the
currently  searched part of the search tree. To choose this strategy set
the field 'mode' of <arec> to '\"preview\"' and the field 'degree' to the
degree (or a list of degrees  which might be all divisors of the order of
the group) you want to look for.  The  record field  'ineq' can  take the
inequalities from 'Inequalities' if they are needed more than once.

In the second form 'PermChars( <tbl>, <degree> )' returns the list of all
permutation  characters  of  degree  <degree>.    For   that  purpose   a
preprocessing  step  is  performed  where  essentially  the  rationalized
character table is inverted in order to determine boundary points for the
simplex in which  the permutation character candidates of a given  degree
must lie (see  "PermBounds").   Note that inverting big  integer matrices
needs  a  lot of time and space.  So this preprocessing is  restricted to
groups with less than 100 classes, say.

|    gap> PermChars(m11, 220);
    [ [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ],
      [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ],
      [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ] |

In the third form 'PermChars( <tbl>, <arec>  )' returns  the list of  all
permutation  characters which have the properties given  in  the argument
record  <arec>. If <arec> contains a  degree in the record field 'degree'
then 'PermChars' will behave exactly as in the second form.

|    gap> PermChars(m11, rec(degree:= 220));
    [ [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ],
      [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ],
      [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ] |

Alternatively <arec> may  have the  record  fields 'chars'  and  'torso'.
<arec>.'chars' is  a list  of (in most cases  all) *rational* irreducible
characters   of  <tbl>  which  might  be  constituents  of  the  required
characters, and <arec>.'torso' is a list that  contains some known values
of the required characters at the right positions.

*Note*\:\ At least the degree '<arec>.torso[1]'  must be an integer.   If
<arec>.'chars' does not contain  all  rational irreducible characters  of
$G$,  it may happen  that any scalar  product of  $\pi$ with  an  omitted
character is negative; there should be nontrivial reasons for excluding a
character that is known to be not a constituent of $\pi$.

|    gap> rat:= RationalizedMat(m11.irreducibles);;
    gap> PermChars(m11, rec(torso:= [220], chars:= rat));
    [ [ 220, 4, 4, 0, 0, 4, 0, 0, 0, 0 ],
      [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ],
      [ 220, 12, 4, 4, 0, 0, 0, 0, 0, 0 ] ]
    gap> PermChars(m11, rec(torso:= [220,,,,,2], chars:= rat));
    [ [ 220, 20, 4, 0, 0, 2, 0, 0, 0, 0 ] ] |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Faithful Permutation Characters}%
\index{permutation characters!faithful candidates for}

'PermChars( <tbl>, <arec> )'

'PermChars' may as  well  determine faithful candidates  for  permutation
characters. In  that  case  <arec>  requires the  fields  'normalsubgrp',
'nonfaithful', 'chars', 'lower', 'upper', and 'torso'.

Let <tbl> be the character table  of the group $G$, <arec>.'normalsubgrp'
a   list   of  classes   forming   a   normal   subgroup   $N$  of   $G$.
<arec>.'nonfaithful'   is   a   permutation   character   candidate  (see
"Permutation   Character   Candidates")   of   $G$   with   kernel   $N$.
<arec>.'chars' is a  list  of (in  most cases  all)  rational irreducible
characters of <tbl>.

'PermChars' computes  all those  permutation character  candidates  $\pi$
having following properties\:

:  <arec>.'chars'  contains  every  rational  irreducible  constituent of
$\pi$.

:  $\pi[i] \geq  <arec>.'lower'[i]$ for  all integer  values of the  list
<arec>.'lower'.

:  $\pi[i] \leq <arec>.'upper'[i]$  for  all integer values  of  the list
<arec>.'upper'.

:  $\pi[i]  =  <arec>.'torso'[i]$  for  all  integer  values  of the list
<arec>.'torso'.

: No irreducible constituent of $\pi-<arec>.'nonfaithful'$ has $N$ in its
kernel.

If  there exists a subgroup $V$ of $G$, $V \geq N$, with $<nonfaithful> =
(1_V)^G$, the last condition means that the candidates for those possible
subgroups $U$ with $V = UN$ are constructed.

*Note*\:  At  least  the degree  $<torso>[1]$ must  be  an  integer.   If
<chars> does  not contain all  rational irreducible characters of $G$, it
may  happen that any scalar product of $\pi$ with an omitted character is
negative;  there should be nontrivial  reasons  for excluding a character
that is known to be not a constituent of $\pi$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LLLReducedBasis}%
\index{LLL algorithm!for vectors}%
\index{short vectors spanning a lattice}%
\index{lattice base reduction}

'LLLReducedBasis([<L>],<vectors>[,<y>][,\"linearcomb\"])'

'LLLReducedBasis' provides an implementation of the LLL lattice reduction
algorithm by Lenstra, Lenstra and Lov{\accent19 a}sz (see~\cite{LLL82},
\cite{Poh87}).  The implementation follows the description on pages
94f. in~\cite{Coh93}.

'LLLReducedBasis' returns a record whose component 'basis' is a list of
LLL reduced linearly independent vectors spanning the same lattice as
the list <vectors>.

<L> must be  a lattice record whose scalar  product function is stored in
the         component        'operations.NoMessageScalarProduct'       or
'operations.ScalarProduct'.  It  must be a  function  of three arguments,
namely the lattice and the  two vectors.  If  no lattice <L> is given the
standard scalar product is taken.

In the case of option '\"linearcomb\"', the record contains also the
components 'relations' and 'transformation', which have the following
meaning.
'relations' is a basis of the relation space of <vectors>, i.e., of
vectors <x> such that '<x> \* <vectors>' is zero.
'transformation' gives the expression of the new lattice basis in
terms of the old, i.e.,
'transformation \* <vectors>' equals the 'basis' component of the result.

Another optional argument is <y>, the ``sensitivity\'\' of the algorithm,
a rational number between $\frac{1}{4}$ and 1 (the default value is
$\frac{3}{4}$).

(The function "LLLReducedGramMat" computes an LLL reduced Gram matrix.)

|    gap> vectors:= [ [ 9, 1, 0, -1, -1 ], [ 15, -1, 0, 0, 0 ],
    >                [ 16, 0, 1, 1, 1 ], [ 20, 0, -1, 0, 0 ],
    >                [ 25, 1, 1, 0, 0 ] ];;
    gap> LLLReducedBasis( vectors, "linearcomb" );
    rec(
      basis :=
       [ [ 1, 1, 1, 1, 1 ], [ 1, 1, -2, 1, 1 ], [ -1, 3, -1, -1, -1 ],
          [ -3, 1, 0, 2, 2 ] ],
      relations := [ [ -1, 0, -1, 0, 1 ] ],
      transformation :=
       [ [ 0, -1, 1, 0, 0 ], [ -1, -2, 0, 2, 0 ], [ 1, -2, 0, 1, 0 ],
          [ -1, -2, 1, 1, 0 ] ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LLLReducedGramMat}%
\index{LLL algorithm!for Gram matrices}%
\index{lattice base reduction}

'LLLReducedGramMat( <G> [,<y>] )'

'LLLReducedGramMat' provides an implementation of the LLL lattice
reduction algorithm by Lenstra, Lenstra and Lov{\accent19 a}sz
(see~\cite{LLL82}, \cite{Poh87}).  The implementation follows the
description on pages 94f. in~\cite{Coh93}.

Let <G> the Gram matrix of the vectors $(b_1, b_2, \ldots, b_n)$;
this means <G> is either a square symmetric matrix or lower triangular
matrix (only the entries in the lower triangular half are used by the
program).

'LLLReducedGramMat' returns a record whose component 'remainder' is the
Gram matrix of the LLL reduced basis corresponding to $(b_1, b_2, \ldots,
b_n)$.
If <G> was a lower triangular matrix then also the 'remainder' component
is a lower triangular matrix.

The result record contains also the components 'relations' and
'transformation', which have the following meaning.

'relations' is a basis of the space of vectors $(x_1,x_2,\ldots,x_n)$
such that $\sum_{i=1}^n x_i b_i$ is zero,
and 'transformation' gives the expression of the new lattice basis in
terms of the old, i.e., 'transformation' is the matrix $T$ such that
$T \cdot <G> \cdot T^{tr}$ is the 'remainder' component of the result.

The optional argument <y> denotes the ``sensitivity'' of the algorithm,
it must be a rational number between $\frac{1}{4}$ and 1; the default
value is $<y> = \frac{3}{4}$.

(The function "LLLReducedBasis" computes an LLL reduced basis.)

|    gap> g:= [ [ 4, 6, 5, 2, 2 ], [ 6, 13, 7, 4, 4 ],
    >    [ 5, 7, 11, 2, 0 ], [ 2, 4, 2, 8, 4 ], [ 2, 4, 0, 4, 8 ] ];;
    gap> LLLReducedGramMat( g );
    rec(
      remainder :=
       [ [ 4, 2, 1, 2, -1 ], [ 2, 5, 0, 2, 0 ], [ 1, 0, 5, 0, 2 ],
          [ 2, 2, 0, 8, 2 ], [ -1, 0, 2, 2, 7 ] ],
      relation := [  ],
      transformation :=
       [ [ 1, 0, 0, 0, 0 ], [ -1, 1, 0, 0, 0 ], [ -1, 0, 1, 0, 0 ],
          [ 0, 0, 0, 1, 0 ], [ -2, 0, 1, 0, 1 ] ],
      scalarproducts := [ , [ 1/2 ], [ 1/4, -1/8 ], [ 1/2, 1/4, -2/25 ],
          [ -1/4, 1/8, 37/75, 8/21 ] ],
      bsnorms := [ 4, 4, 75/16, 168/25, 32/7 ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LLL}%
\index{LLL algorithm!for characters}%
\index{short vectors spanning a lattice}%
\index{lattice base reduction}

'LLL( <tbl>, <characters> [, <y>] [, \"sort\"] [, \"linearcomb\"] )'

calls the LLL algorithm (see "LLLReducedBasis") in the case of lattices
spanned by (virtual) characters <characters> of the character table <tbl>
(see "ScalarProduct").  By finding shorter vectors in the lattice spanned
by <characters>, i.e.  virtual characters of smaller norm, in some cases
'LLL' is able to find irreducible characters.

'LLL' returns a record with at least components 'irreducibles' (the list
of found irreducible characters), 'remainders' (a list of reducible
virtual characters), and 'norms' (the list of norms of 'remainders').
'irreducibles' together with 'remainders' span the same lattice as
<characters>.

There are some optional parameters\:

<y>:\\ controls the sensitivity of the algorithm; the value of <y> must
       be between $1/4$ and 1, the default value is $3/4$.

'\"sort\"':\\
       'LLL' sorts <characters> and the 'remainders' component of the
       result according to the degrees.

'\"linearcomb\"':\\ The returned record contains components 'irreddecomp'
       and 'reddecomp' which are decomposition matrices of 'irreducibles'
       and 'remainders', with respect to <characters>.

|    gap> s4:= CharTable( "Symmetric", 4 );;
    gap> chars:= [ [ 8, 0, 0, -1, 0 ], [ 6, 0, 2, 0, 2 ],
    >     [ 12, 0, -4, 0, 0 ], [ 6, 0, -2, 0, 0 ], [ 24, 0, 0, 0, 0 ],
    >     [ 12, 0, 4, 0, 0 ], [ 6, 0, 2, 0, -2 ], [ 12, -2, 0, 0, 0 ],
    >     [ 8, 0, 0, 2, 0 ], [ 12, 2, 0, 0, 0 ], [ 1, 1, 1, 1, 1 ] ];;
    gap> LLL( s4, chars );
    rec(
      irreducibles :=
       [ [ 2, 0, 2, -1, 0 ], [ 1, 1, 1, 1, 1 ], [ 3, 1, -1, 0, -1 ],
          [ 3, -1, -1, 0, 1 ], [ 1, -1, 1, 1, -1 ] ],
      remainders := [  ],
      norms := [  ] )|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OrthogonalEmbeddings}%
\index{embeddings of lattices}

'OrthogonalEmbeddings( <G> [, \"positive\" ] [, <maxdim> ] )'

computes all possible orthogonal embeddings of a lattice given by its
Gram matrix $G$ which must be a regular matrix (see "LLLReducedGramMat").
In other words, all solutions $X$ of the problem

\[ X^{tr} X = G \]

are calculated (see~\cite{Ple90}).  Usually there are many solutions $X$
but all their rows are chosen from a small set of vectors, so
'OrthogonalEmbeddings' returns the solutions in an encoded form, namely
as a record with components

'vectors':\\ the list $[ x_1, x_2, \ldots, x_n ]$ of vectors that may
             be rows of a solution; these are exactly those vectors
             that fulfill the condition $x_i G^{-1} x_{i}^{tr} \leq 1$
             (see "ShortestVectors"), and we have
             $G = \sum^n_{i=1} x_i^{tr} x_i$,

'norms':     the list of values $x_i G^{-1}x_i^{tr}$, and

'solutions':\\ a list <S> of lists; the $i$--th solution matrix is
              'Sublist( <L>, <S>[<i>] )', so the dimension of the
              $i$--th solution is the length of '<S>[<i>]'.

The optional argument '\"positive\"' will cause 'OrthogonalEmbeddings'
to compute only vectors $x_i$ with nonnegative entries.  In the context
of characters this is allowed (and useful) if $G$ is the matrix of
scalar products of ordinary characters.

When 'OrthogonalEmbeddings' is called with the optional argument
<maxdim> (a positive integer), it computes only solutions up to
dimension <maxdim>; this will accelerate the algorithm in some cases.

$G$ may be the matrix of scalar products of some virtual characters.
From the characters and the embedding given by the matrix $X$,
'Decreased' (see "Decreased") may be able to compute irreducibles.

|    gap> b := [ [  3, -1, -1 ], [ -1,  3, -1 ], [ -1, -1,  3 ] ];;
    gap> c:=OrthogonalEmbeddings(b);
    rec(
      vectors :=
       [ [ -1, 1, 1 ], [ 1, -1, 1 ], [ -1, -1, 1 ], [ -1, 1, 0 ],
          [ -1, 0, 1 ], [ 1, 0, 0 ], [ 0, -1, 1 ], [ 0, 1, 0 ],
          [ 0, 0, 1 ] ],
      norms := [ 1, 1, 1, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2 ],
      solutions := [ [ 1, 2, 3 ], [ 1, 6, 6, 7, 7 ], [ 2, 5, 5, 8, 8 ],
          [ 3, 4, 4, 9, 9 ], [ 4, 5, 6, 7, 8, 9 ] ] )
    gap> Sublist( c.vectors, c.solutions[1] );
    [ [ -1, 1, 1 ], [ 1, -1, 1 ], [ -1, -1, 1 ] ]|

\vspace{5mm}
'OrthogonalEmbeddingsSpecialDimension'%
\index{OrthogonalEmbeddingsSpecialDimension}\\
|          |'( <tbl>, <reducibles>, <grammat> [, \"positive\" ], <dim> )'

This form can be used if you want to find irreducible characters of the
table <tbl>, where <reducibles> is a list of virtual characters,
<grammat> is the matrix of their scalar products, and <dim> is the
maximal dimension of an embedding.
First all solutions up to <dim> are compute, and then "Decreased"
'Decreased' is called in order to find irreducible characters of <tab>.

If <reducibles> consists of ordinary characters only, you should enter
the optional argument '\"positive\"'; this imposes some conditions on
the possible embeddings (see the description of 'OrthogonalEmbeddings').

'OrthogonalEmbeddingsSpecialDimension' returns a record with components

'irreducibles':  a list of found irreducibles, the intersection of all
                 lists of irreducibles found by 'Decreased', for all
                 possible embeddings, and

'remainders':    a list of remaining reducible virtual characters


|    gap> s6:= CharTable( "Symmetric", 6 );;
    gap> b:= InducedCyclic( s6, "all" );;
    gap> Add( b, [1,1,1,1,1,1,1,1,1,1,1] );
    gap> c:= LLL( s6, b ).remainders;;
    gap> g:= MatScalarProducts( s6, c, c );;
    gap> d:= OrthogonalEmbeddingsSpecialDimension( s6, c, g, 8 );
    rec(
      irreducibles :=
       [ [ 5, -3, 1, 1, 2, 0, -1, -1, -1, 0, 1 ], [ 5, 1, 1, -3, -1, 1,
              2, -1, -1, 0, 0 ], [ 10, -2, -2, 2, 1, 1, 1, 0, 0, 0, -1 ],
          [ 10, 2, -2, -2, 1, -1, 1, 0, 0, 0, 1 ] ],
      remainders :=
       [ [ 0, 4, 0, -4, 3, 1, -3, 0, 0, 0, -1 ], [ 4, 0, 0, 4, -2, 0, 1,
              -2, 2, -1, 1 ], [ 6, 2, 2, -2, 3, -1, 0, 0, 0, 1, -2 ],
          [ 14, 6, 2, 2, 2, 0, -1, 0, 0, -1, -1 ] ] )|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ShortestVectors}

'ShortestVectors( <G>, <m> )'\\
'ShortestVectors( <G>, <m>, \"positive\" )'

computes all vectors $x$ with $x G x^{tr} \leq m$, where $G$ is a matrix of
a symmetric bilinear form, and $m$ is a nonnegative integer.
If the optional argument '\"positive\"' is entered, only those vectors $x$
with nonnegative entries are computed.

'ShortestVectors' returns a record with components

'vectors':  the list of vectors $x$, and

'norms':    the list of their norms according to the Gram matrix $G$.

|    gap> g:= [ [ 2, 1, 1 ], [ 1, 2, 1 ], [ 1, 1, 2 ] ];;
    gap> ShortestVectors(g,4);
    rec(
      vectors := [ [ -1, 1, 1 ], [ 0, 0, 1 ], [ -1, 0, 1 ], [ 1, -1, 1 ],
          [ 0, -1, 1 ], [ -1, -1, 1 ], [ 0, 1, 0 ], [ -1, 1, 0 ],
          [ 1, 0, 0 ] ],
      norms := [ 4, 2, 2, 4, 2, 4, 2, 2, 2 ] )|

This algorithm is used in "OrthogonalEmbeddings" 'OrthogonalEmbeddings'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Extract}

'Extract( <tbl>, <reducibles>, <grammat> )'\\
'Extract( <tbl>, <reducibles>, <grammat>, <missing> )'

tries to find irreducible characters by drawing conclusions out of a
given matrix <grammat> of scalar products of the reducible characters in
the list <reducibles>, which are characters of the table <tbl>.
'Extract' uses combinatorial and backtrack means.

*Note\:\ 'Extract' works only with ordinary characters!*

<missing>: number of characters missing to complete the <tbl>
           perhaps 'Extract' may be accelerated by the specification of
           <missing>.

'Extract' returns a record <extr> with components 'solution' and 'choice'
where 'solution' is a list $[ M_1, \ldots, M_n ]$ of decomposition
matrices that satisfy the equation
\[ M_i^{tr} \cdot X = 'Sublist( <reducibles>, <extr>.choice[i] )'\ , \]
for a matrix $X$ of irreducible characters, and 'choice' is a list of
length $n$ whose entries are lists of indices.

So each column stands for one of the reducible input characters, and
each row stands for an irreducible character.  You can use
"Decreased" 'Decreased' to examine the solution for computable
irreducibles.

|    gap> s4 := CharTable( "Symmetric", 4 );;
    gap> y := [ [ 5, 1, 5, 2, 1 ], [ 2, 0, 2, 2, 0 ], [ 3, -1, 3, 0, -1 ],
    >  [ 6, 0, -2, 0, 0 ], [ 4, 0, 0, 1, 2 ] ];;
    gap> g := MatScalarProducts( s4, y, y );
    [ [ 6, 3, 2, 0, 2 ], [ 3, 2, 1, 0, 1 ], [ 2, 1, 2, 0, 0 ],
      [ 0, 0, 0, 2, 1 ], [ 2, 1, 0, 1, 2 ] ]
    gap> e:= Extract( s4, y, g, 5 );
    rec(
      solution :=
       [ [ [ 1, 1, 0, 0, 2 ], [ 1, 0, 1, 0, 1 ], [ 0, 1, 0, 1, 0 ],
              [ 0, 0, 1, 0, 1 ], [ 0, 0, 0, 1, 0 ] ] ],
      choice := [ [ 2, 5, 3, 4, 1 ] ] )
    # continued in 'Decreased' ( see "Decreased" )|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Decreased}

'Decreased( <tbl>, <reducibles>, <mat> )'\\
'Decreased( <tbl>, <reducibles>, <mat>, <choice> )'

tries to solve the output of "OrthogonalEmbeddings"
'OrthogonalEmbeddings' or "Extract" 'Extract' in order to find
irreducible characters.  <tbl> must be a character table, <reducibles>
the list of characters used for the call of 'OrtgogonalEmbeddings' or
'Extract', <mat> one solution, and in the case of a solution returned
by 'Extract', 'choice' must be the corresponding 'choice' component.

'Decreased' returns a record with components

'irreducibles':\\
      the list of found irreducible characters,

'remainders':\\
      the remaining reducible characters, and

'matrix':\\
      the decomposition matrix of the characters in the 'remainders'
      component, which could not be solved.

|    # see example in "Extract" 'Extract'
    gap> d := Decreased( s4, y, e.solution[1], e.choice[1] );
    rec(
      irreducibles :=
       [ [ 1, 1, 1, 1, 1 ], [ 3, -1, -1, 0, 1 ], [ 1, -1, 1, 1, -1 ],
          [ 3, 1, -1, 0, -1 ], [ 2, 0, 2, -1, 0 ] ],
      remainders := [  ],
      matrix := [  ] )|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DnLattice}%
\index{$D_n$ lattices}

'DnLattice( <tbl>, <grammat>, <reducibles> )'

tries to find sublattices isomorphic to root lattices of type $D_n$
(for $n \geq 5$ or $n = 4$) in a lattice that is generated by the norm 2
characters <reducibles>, which must be characters of the table <tbl>.
<grammat> must be the matrix of scalar products of <reducibles>, i.e.,
the Gram matrix of the lattice.

'DnLattice' is able to find irreducible characters if there is a lattice
with $n>4$.  In the case $n = 4$ 'DnLattice' only in some cases finds
irreducibles.

'DnLattice' returns a record with components

'irreducibles':\\
       the list of found irreducible characters,

'remainders':\\
       the list of remaining reducible characters, and

'gram':\\
       the Gram matrix of the characters in 'remainders'.

The remaining  reducible characters  are  transformed into  a  normalized
form, so that the lattice-structure is cleared  up for further treatment.
So  'DnLattice' might be  useful  even  if it  fails to  find irreducible
characters.

|    gap> tbl:= CharTable( "Symmetric", 4 );;
    gap> y1:=[ [ 2, 0, 2, 2, 0 ], [ 4, 0, 0, 1, 2 ], [ 5, -1, 1, -1, 1 ],
    >          [ -1, 1, 3, -1, -1 ] ];;
    gap> g1:= MatScalarProducts( tbl, y1, y1 );
    [ [ 2, 1, 0, 0 ], [ 1, 2, 1, -1 ], [ 0, 1, 2, 0 ], [ 0, -1, 0, 2 ] ]
    gap> e:= DnLattice( tbl, g1, y1 );
    rec(
      gram := [  ],
      remainders := [  ],
      irreducibles :=
       [ [ 2, 0, 2, -1, 0 ], [ 1, -1, 1, 1, -1 ], [ 1, 1, 1, 1, 1 ],
          [ 3, -1, -1, 0, 1 ] ] )|

\vspace{5mm}
'DnLatticeIterative( <tbl>, <arec> )'%
\index{DnLatticeIterative}

was made for iterative use of 'DnLattice'. <arec> must be either a list
of characters of the table <tbl>, or a record with components

'remainders':\\
       a list of characters of the character table <tbl>, and

'norms':\\
       the norms of the characters in 'remainders',

e.g., a record returned by "LLL" 'LLL'.  'DnLatticeIterative'
will select the characters of norm 2, call 'DnLattice', reduce the
characters with found irreducibles, call 'DnLattice' for the
remaining characters, and so on, until no new irreducibles are found.

'DnLatticeIterative' returns (like "LLL" 'LLL') a record with
components

'irreducibles':\\
     the list of found irreducible characters,

'remainders':\\
     the list of remaining reducible characters, and

'norms':\\
     the list of norms of the characters in 'remainders'.

|    gap> tbl:= CharTable( "Symmetric", 4 );;
    gap> y1:= [ [ 2, 0, 2, 2, 0 ], [ 4, 0, 0, 1, 2 ],
    >   [ 5, -1, 1, -1, 1 ], [ -1, 1, 3, -1, -1 ], [ 6, -2, 2, 0, 0 ] ];;
    gap> DnLatticeIterative( tbl, y1);
    rec(
      irreducibles :=
       [ [ 2, 0, 2, -1, 0 ], [ 1, -1, 1, 1, -1 ], [ 1, 1, 1, 1, 1 ],
          [ 3, -1, -1, 0, 1 ] ],
      remainders := [  ],
      norms := [  ] )|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ContainedDecomposables}

'ContainedDecomposables( <constituents>, <moduls>, <parachar>, <func> )'

For a list of *rational* characters <constituents> and a parametrized
rational character <parachar>
(see "More about Maps and Parametrized Maps"),
the set of all elements $\chi$ of <parachar> is returned
that satisfy $<func>( \chi )$ (i.e., for that 'true' is returned)
and that ``modulo <moduls> lie in the lattice
spanned by <constituents>\'\'. This means they lie in the lattice spanned
by <constituents> and the set $\{ <moduls>[i]\cdot e_i; 1\leq i\leq n\}$,
where $n$ is the length of <parachar> and $e_i$ is the $i$-th vector
of the standard base.

|    gap> hs:= CharTable("HS");; s:= CharTable("HSM12");; s.identifier;
    "5:4xa5"
    gap> rat:= RationalizedMat(s.irreducibles);;
    gap> fus:= InitFusion( s, hs );
    [ 1, [ 2, 3 ], [ 2, 3 ], [ 2, 3 ], 4, 5, 5, [ 5, 6, 7 ], [ 5, 6, 7 ],
      9, [ 8, 9 ], [ 8, 9 ], [ 8, 9, 10 ], [ 8, 9, 10 ], [ 11, 12 ],
      [ 17, 18 ], [ 17, 18 ], [ 17, 18 ], 21, 21, 22, [ 23, 24 ],
      [ 23, 24 ], [ 23, 24 ], [ 23, 24 ] ]
    # restrict a rational character of 'hs' by 'fus',
    # see chapter "Maps and Parametrized Maps"\:
    gap> rest:= CompositionMaps( hs.irreducibles[8], fus );
    [ 231, [ -9, 7 ], [ -9, 7 ], [ -9, 7 ], 6, 15, 15, [ -1, 15 ],
      [ -1, 15 ], 1, [ 1, 6 ], [ 1, 6 ], [ 1, 6 ], [ 1, 6 ], [ -2, 0 ],
      [ 1, 2 ], [ 1, 2 ], [ 1, 2 ], 0, 0, 1, 0, 0, 0, 0 ]
    # all vectors in the lattice\:
    gap> ContainedDecomposables( rat, s.centralizers, rest, x -> true );
    [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, -9, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ] ]
    # better filter, only characters (see "ContainedCharacters")\:
    gap> ContainedDecomposables( rat, s.centralizers, rest,
    >                  x->NonnegIntScalarProducts(s,s.irreducibles,x) );
    [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ] ]|

An application of 'ContainedDecomposables' is "ContainedCharacters"
'ContainedCharacters'.

For another strategy that works also for irrational characters,
see "ContainedSpecialVectors".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ContainedCharacters}

'ContainedCharacters( <tbl>, <constituents>, <parachar> )'

returns the set of all characters contained in the parametrized rational
character <parachar> (see "More about Maps and Parametrized Maps"),
that modulo centralizer orders lie in the linear span of the *rational*
characters <constituents> of the character table <tbl> and that have
nonnegative integral scalar products with all elements of <constituents>.

*Note*\:\ This does not imply that an element of the returned list is
necessary a linear combination of <constituents>.

|    gap> s:= CharTable( "HSM12" );; hs:= CharTable( "HS" );;
    gap> rat:= RationalizedMat( s.irreducibles );;
    gap> fus:= InitFusion( s, hs );;
    gap> rest:= CompositionMaps( hs.irreducibles[8], fus );;
    gap> ContainedCharacters( s, rat, rest );
    [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ] ]|

'ContainedCharacters' calls "ContainedDecomposables"
'ContainedDecomposables'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ContainedSpecialVectors}

'ContainedSpecialVectors( <tbl>, <chars>, <parachar>, <func> )'

returns the list of all elements <vec> of the parametrized character
<parachar> (see "More about Maps and Parametrized Maps"), that have
integral norm and integral scalar product with the principal character
of the character table <tbl> and that satisfy '<func>( <tbl>, <chars>,
 <vec> )', i.e., for that 'true' is returned.

|    gap> s:= CharTable( "HSM12" );; hs:= CharTable( "HS" );;
    gap> fus:= InitFusion( s, hs );;
    gap> rest:= CompositionMaps( hs.irreducibles[8], fus );;
    # no further condition\:
    gap> ContainedSpecialVectors( s, s.irreducibles, rest,
    >                      function(tbl,chars,vec) return true; end );;
    gap> Length( last );
    24
    # better filter\:\ those with integral scalar products
    gap> ContainedSpecialVectors( s, s.irreducibles, rest,
    >                             IntScalarProducts );
    [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, -9, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ] ]
    # better filter\:\ the scalar products must be nonnegative
    gap> ContainedSpecialVectors( s, s.irreducibles, rest,
    >                             NonnegIntScalarProducts );
    [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ] ]|

Special cases of 'ContainedSpecialVectors' are
"ContainedPossibleCharacters" 'ContainedPossibleCharacters' and
"ContainedPossibleVirtualCharacters"
'ContainedPossibleVirtualCharacters'.

'ContainedSpecialVectors' successively examines all vectors contained in
<parachar>, thus it might not be useful if the indeterminateness
exceeds $10^6$.  For another strategy that works for rational characters
only, see "ContainedDecomposables".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ContainedPossibleCharacters}

'ContainedPossibleCharacters( <tbl>, <chars>, <parachar> )'

returns the list of all elements <vec> of the parametrized character
<parachar> (see "More about Maps and Parametrized Maps"), which have
integral norm and integral scalar product with the principal character
of the character table <tbl> and nonnegative integral scalar product
with all elements of the list <chars> of characters of <tbl>.

|    # see example in "ContainedSpecialVectors"
    gap> ContainedPossibleCharacters( s, s.irreducibles, rest );
    [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ] ]|

'ContainedPossibleCharacters' calls "ContainedSpecialVectors"
'ContainedSpecialVectors'.

'ContainedPossibleCharacters' successively examines all vectors contained
in <parachar>, thus it might not be useful if the indeterminateness
exceeds $10^6$.  For another strategy that works for rational characters
only, see "ContainedDecomposables".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ContainedPossibleVirtualCharacters}

'ContainedPossibleVirtualCharacters( <tbl>, <chars>, <parachar> )'

returns the list of all elements <vec> of the parametrized character
<parachar> (see "More about Maps and Parametrized Maps"), which have
integral norm and integral scalar product with the principal character
of the character table <tbl> and integral scalar product with all
elements of the list <chars> of characters of <tbl>.

|    # see example in "ContainedSpecialVectors"
    gap> ContainedPossibleVirtualCharacters( s, s.irreducibles, rest );
    [ [ 231, 7, -9, -9, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, -1, -1, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, -9, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ],
      [ 231, 7, -9, 7, 6, 15, 15, 15, 15, 1, 6, 6, 1, 1, -2, 1, 2, 2, 0,
          0, 1, 0, 0, 0, 0 ] ]|

'ContainedPossibleVirtualCharacters' calls "ContainedSpecialVectors"
'ContainedSpecialVectors'.

'ContainedPossibleVirtualCharacters' successively examines all vectors
that are contained in <parachar>, thus it might not be useful if the
indeterminateness exceeds $10^6$.
For another strategy that works for rational characters only,
see "ContainedDecomposables".


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E  Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables
%%
%%  Local Variables:
%%  mode:               outline
%%  outline-regexp:     "\\\\Chapter\\|\\\\Section"
%%  fill-column:        73
%%  eval:               (hide-body)
%%  End:
%%
