# 50 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).

## 50.1 ScalarProduct

`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```

## 50.2 MatScalarProducts

`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 ] ]```

## 50.3 Decomposition

`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.

`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 pmfrac{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`.

`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```

## 50.4 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 = frac1p (b_i - x_i A) mboxrm 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`:

`LinearIndependentColumns( A )`

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.

`InverseMatMod( A, p )`

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.

`PadicCoefficients( A, Amodpinv, b, p, depth )`

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.

`IntegralizedMat( A )` `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.

`DecompositionInt( A, B, depth )`

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

## 50.5 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 ] ]```

## 50.6 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.

## 50.7 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 ]```

## 50.8 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{2pi 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 ]`.

## 50.9 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.

`ValueMolienSeries( series, i )`

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.

## 50.10 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_chiin `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 ] ] )```

## 50.11 ReducedOrdinary

`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.

## 50.12 Tensored

`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.

## 50.13 Symmetrisations

`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) = frac1n! 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.

## 50.14 SymmetricParts

`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 ] ]```

## 50.15 AntiSymmetricParts

`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 ] ]```

## 50.16 MinusCharacter

`MinusCharacter( char, prime_powermap, prime )`

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 ] ] ]```

## 50.17 OrthogonalComponents

`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~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~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 ] ]```

## 50.18 SymplecticComponents

`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~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 ] ]```

## 50.19 IrreducibleDifferences

`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 ] ]```

## 50.20 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.

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 ] ]```

## 50.21 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.

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 ] ]```

## 50.22 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.

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 ] ]```

## 50.23 InducedCyclic

`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.

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 ] ]```

## 50.24 CollapsedMat

`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 ] ]```

## 50.25 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 ] ]```

## 50.26 Permutation Character Candidates

For groups H, G with Hleq 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]leqpsi(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 1not= g in G,

:
pi(g)leqpi(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 < g > .

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).

## 50.27 IsPermChar

`IsPermChar( tbl, pi )`

missing, like tests `TestPerm1`, `TestPerm2`, `TestPerm3`

## 50.28 PermCharInfo

`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```

## 50.29 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.

## 50.30 PermBounds

`PermBounds( tbl, d )`

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.

## 50.31 PermChars

`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 ] ] ```

## 50.32 Faithful Permutation Characters

`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.

## 50.33 LLLReducedBasis

`LLLReducedBasis([L],vectors[,y][,"linearcomb"])`

`LLLReducedBasis` provides an implementation of the LLL lattice reduction algorithm by Lenstra, Lenstra and Lovaccent19 asz (see~LLL82, Poh87). The implementation follows the description on pages 94f. in~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 ] ] ) ```

## 50.34 LLLReducedGramMat

`LLLReducedGramMat( G [,y] )`

`LLLReducedGramMat` provides an implementation of the LLL lattice reduction algorithm by Lenstra, Lenstra and Lovaccent19 asz (see~LLL82, Poh87). The implementation follows the description on pages 94f. in~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 ] ) ```

## 50.35 LLL

`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 := [  ] )```

## 50.36 OrthogonalEmbeddings

`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~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 ] ]```

`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> 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 ] ] )```

## 50.37 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`.

## 50.38 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" )```

## 50.39 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 := [  ] )```

## 50.40 DnLattice

`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 ] ] )```

`DnLatticeIterative( tbl, arec )`

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 := [  ] )```

## 50.41 ContainedDecomposables

`ContainedDecomposables( constituents, moduls, parachar, func )`

For a list of rational characters constituents and a parametrized 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; 1leq ileq 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.

## 50.42 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`.

## 50.43 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.

## 50.44 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.

## 50.45 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.

GAP 3.4.4
April 1997