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

Subsections

  1. ScalarProduct
  2. MatScalarProducts
  3. Decomposition
  4. Subroutines of Decomposition
  5. KernelChar
  6. PrimeBlocks
  7. Indicator
  8. Eigenvalues
  9. MolienSeries
  10. Reduced
  11. ReducedOrdinary
  12. Tensored
  13. Symmetrisations
  14. SymmetricParts
  15. AntiSymmetricParts
  16. MinusCharacter
  17. OrthogonalComponents
  18. SymplecticComponents
  19. IrreducibleDifferences
  20. Restricted
  21. Inflated
  22. Induced
  23. InducedCyclic
  24. CollapsedMat
  25. Power
  26. Permutation Character Candidates
  27. IsPermChar
  28. PermCharInfo
  29. Inequalities
  30. PermBounds
  31. PermChars
  32. Faithful Permutation Characters
  33. LLLReducedBasis
  34. LLLReducedGramMat
  35. LLL
  36. OrthogonalEmbeddings
  37. ShortestVectors
  38. Extract
  39. Decreased
  40. DnLattice
  41. ContainedDecomposables
  42. ContainedCharacters
  43. ContainedSpecialVectors
  44. ContainedPossibleCharacters
  45. ContainedPossibleVirtualCharacters

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

Subroutines of Decomposition.

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 fracScalarProduct( 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 fracScalarProduct( 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> 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 ] ] )

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.

Previous Up Next
Index

GAP 3.4.4
April 1997