An IsCCTable (4.1-1) object is the central data structure used by this package to incrementally collect information about the generalized and irreducible characters of a finite group, using an induce-reduce algorithm.
IsCCTable (4.1-1) object‣ CCTable( G ) | ( attribute ) |
Returns: an IsCCTable object
‣ IsCCTable( CCT ) | ( filter ) |
For a finite group G CCTable returns an (initially empty) partial character table container object, in the filter IsCCTable. Such an object stores incrementally growing information about the (still unknown) generalized and irreducible characters of G, and is used as the central data structure for computing the irreducible characters of G with the tools in the CCTab package. The group G is stored as UnderlyingGroup(CCT) in the result CCT. Many attributes of G (for example RationalClassesInfo (3.2-4)) can also be called with CCT (and delegate to G).
Generalized characters are stored in an IsCCTable object as integer vectors (for each rational class only the value on the representing conjugacy class is stored by Phi(c) integers where c is the conductor of that rational class). See EncodeForCCTable (4.1-2) below for a more precise description and for computing this representation of a generalized character from a class function object.
Generalized characters can be added to an IsCCTable object with ImportToCCTable (4.1-3). The lattice spanned by the known generalized characters is stored via the Hermite normal form of the characters, encoded as integer vectors (in a component !.hnfs).
If the group G has a non-trivial center it can be useful to call SplitByCentre (4.3-1) with CCT. This is not done by default because this may cause some non-negligible computations with conjugacy classes.
The default method for Irr (Reference: Irr) for an IsCCTable object computes the full set of irreducible characters of G. If the CCTab package is loaded then for many groups G its CharacterTable(G) will also have an attribute CCTable and delegate the computation of the irreducible characters to this CCTable.
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> CCT := CCTable(G); CCTable( Alt( [ 1 .. 5 ] ) ) gap> IsCCTable(CCT); true gap> Irr(CCT); [ [ 1, 1, 1, 1, 0, 0, 0 ], [ 3, -1, 0, 0, 0, -1, -1 ], [ 3, -1, 0, 1, 0, 1, 1 ], [ 4, 0, 1, -1, 0, 0, 0 ], [ 5, 1, -1, 0, 0, 0, 0 ] ] gap> ExpandFromCCTable(CCT, Irr(CCT)); [ [ 1, 1, 1, 1, 1 ], [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], [ 4, 0, 1, -1, -1 ], [ 5, 1, -1, 0, 0 ] ]
‣ EncodeForCCTable( CCT, l ) | ( function ) |
Returns: an integer vector, or a list of integer vectors
‣ ExpandFromCCTable( CCT[, enc] ) | ( function ) |
Returns: a character, or a list of characters
Let CCT be an IsCCTable (4.1-1) object. The argument l is either a single character, or a list of characters, of the underlying group of CCT, each given either as a list of values (in the order of the ConjugacyClasses (Reference: ConjugacyClasses attribute) of the underlying group) or as a class function object (with values in the order of IdentificationOfConjugacyClasses (Reference: IdentificationOfConjugacyClasses)) of its character table.
EncodeForCCTable returns the encoded form in which characters are stored in the IsCCTable (4.1-1) object: for each rational class (see RationalClassesInfo (3.2-4)) with conductor 1 this is simply the integer value on that class; for a rational class with conductor c > 1 the value on that class is a cyclotomic integer in the c-th cyclotomic field, and it is encoded by the (integer) coefficients of its representation as a polynomial in E(c) modulo the c-th cyclotomic polynomial. The entries of RationalClassesInfo(CCT) have a component .ind telling the positions of these integer coefficients. If l is a single character, a single integer vector is returned, otherwise a list of vectors, one for each character in l.
ExpandFromCCTable is the converse function. If the optional argument enc is not given, all irreducible characters of CCT found so far are expanded.
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> CCT := CCTable(G);; gap> ind := InducedFromAllMaximalCyclicSubgroups(G);; gap> enc := EncodeForCCTable(CCT, ind); [ [ 12, 0, 0, 2, 0, 0, 0 ], [ 12, 0, 0, 0, 0, 1, 1 ], [ 12, 0, 0, -1, 0, -1, -1 ], [ 20, 0, -1, 0, 0, 0, 0 ], [ 20, 0, 2, 0, 0, 0, 0 ], [ 30, -2, 0, 0, 0, 0, 0 ], [ 30, 2, 0, 0, 0, 0, 0 ] ] gap> ExpandFromCCTable(CCT); [ ] gap> ExpandFromCCTable(CCT, enc); [ [ 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 ] ]
‣ ImportToCCTable( CCT, chs ) | ( function ) |
‣ ImportEncodedToCCTable( CCT, enc ) | ( function ) |
Let CCT be an IsCCTable (4.1-1) object, and let chs be a generalized character, or list of generalized characters, of the underlying group, given as for EncodeForCCTable (4.1-2) (that is, not yet encoded). ImportToCCTable encodes chs via EncodeForCCTable (4.1-2) and imports the result into CCT via ImportEncodedToCCTable.
ImportEncodedToCCTable imports enc into CCT: the (encoded) projections of already known irreducible characters of CCT are subtracted, and the remaining vectors are added to the list(s) of newly found generalized characters stored in CCT (split according to the splitting centre of CCT, see SplitByCentre (4.3-1), if that has been set). This does not yet update the Hermite normal forms describing the lattice(s) of found characters, see UpdateHNFCCTable (4.1-4).
gap> G := AlternatingGroup(5);; gap> ind := InducedFromAllMaximalCyclicSubgroups(G);; gap> CCT := CCTable(G);; gap> ImportToCCTable(CCT, ind); gap> UpdateHNFCCTable(CCT); 0 gap> HasFullRankCCTable(CCT); true
‣ UpdateHNFCCTable( CCT ) | ( function ) |
Returns: a non-negative integer
Let CCT be an IsCCTable (4.1-1) object. This function incorporates the generalized characters recently imported via ImportEncodedToCCTable (4.1-3) (or ImportToCCTable (4.1-3)) into the Hermite normal form basis (or bases, in case of a splitting centre, see SplitByCentre (4.3-1)) of the lattice of generalized characters of CCT found so far, using AddVectorToHNF (4.1-10).
If HasFullRankCCTable (4.1-5) is true for CCT, the return value is the index by which the lattice found so far has shrunk (that is, the product of all indices returned by the individual calls to AddVectorToHNF (4.1-10)); otherwise the Hermite normal forms are simply recomputed from scratch and 0 is returned.
‣ HasFullRankCCTable( CCT ) | ( function ) |
Returns: true or false
Let CCT be an IsCCTable (4.1-1) object. This function returns true if the total number of characters currently collected in the Hermite normal form data of CCT (see UpdateHNFCCTable (4.1-4)), together with the irreducible characters already found, equals the number of conjugacy classes of the underlying group, that is if the lattice of characters found so far already has full rank (the index in the full lattice of generalized characters is finite).
For example, the induced characters from all (maximal) cyclic subgroups always span a lattice of full rank, see the example for ImportToCCTable (4.1-3).
‣ FindIndexCCTable( CCT ) | ( function ) |
Returns: a positive integer, or fail
Let CCT be an IsCCTable (4.1-1) object. If HasFullRankCCTable(CCT) = true this function returns the index of the lattice spanned by the class functions stored in CCT in the full lattice spanned by the irreducible characters of the underlying group. Otherwise, fail is returned.
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> CCT := CCTable(G);; gap> ImportInducedFromAllMaximalCyclicToCCTable(CCT); gap> FindIndexCCTable(CCT); 2 gap> ImportToCCTable(CCT, SmallPowerMapCharacters(G)); gap> UpdateHNFCCTable(CCT); 2 gap> FindIrreduciblesInFullLattices(CCT); gap> CCT!.irr; [ [ 1, 1, 1, 1, 0, 0, 0 ], [ 3, -1, 0, 0, 0, -1, -1 ], [ 3, -1, 0, 1, 0, 1, 1 ], [ 4, 0, 1, -1, 0, 0, 0 ], [ 5, 1, -1, 0, 0, 0, 0 ] ]
‣ ImportInducedFromAllMaximalCyclicToCCTable( CCT ) | ( function ) |
Let CCT be an IsCCTable (4.1-1) object of a group G. Unless this has already been done (recorded in a component of CCT), this function computes the characters of G induced from all maximal cyclic subgroups of G (via InducedFromAllMaximalCyclicSubgroups (3.2-7)), imports them into CCT, and updates its Hermite normal form data. It also computes and stores, for each part of the (possibly split) lattice, the index of the resulting lattice of generalized characters in the full lattice of generalized characters, using that this index is only divisible by primes p for which the Sylow p-subgroups of G are not cyclic. The algorithm makes use of ElementaryDivisorsPPartRk (EDIM: ElementaryDivisorsPPartRk).
gap> G := MathieuGroup(24);; gap> CCT := CCTable(G);; gap> ImportInducedFromAllMaximalCyclicToCCTable(CCT); gap> FindIndexCCTable(CCT); 4718592 gap> StringCollectedFactors(FindIndexCCTable(CCT)); "2^19 3^2"
‣ FindIrreduciblesInFullLattices( CCT ) | ( function ) |
Let CCT be an IsCCTable (4.1-1) object. For every orthogonal subspace in the HNF data of CCT which contains an integer basis of the corresponding sublattice this function computes the irreducible characters in that sublattice using a variant of the LLL algorithm (see LLLTransformUnimodularGram (3.4-4)). The irreducible characters are then moved into the list of known irreducibles (CCT!.irr) and this part of the HNF data is cleared. If SplitByCentre (4.3-1) was used, the function also adds Galois conjugates of the found irreducibles.
See FindIndexCCTable (4.1-6) for an example.
‣ IrrCCTableHNF( CCT ) | ( function ) |
Returns: a list of irreducible characters, or fail
Let CCT be an IsCCTable (4.1-1) object of a group G. This function implements an induce-reduce algorithm that computes and returns the list of irreducible characters of G, and is installed as the default method for Irr (Reference: Irr) for IsCCTable (4.1-1) objects.
It successively imports into CCT (via ImportToCCTable (4.1-3) and UpdateHNFCCTable (4.1-4)) the characters induced from all maximal cyclic subgroups (via ImportInducedFromAllMaximalCyclicToCCTable (4.1-7)), the trivial and NaturalCharacters (4.4-1) of G, cheap generalized characters obtained from power maps (via SmallPowerMapCharacters (3.2-9)), and, if still needed, the characters induced from the maximal non-cyclic elementary subgroups of G (via MaximalNonCyclicElementarySubgroups (3.3-1) and InductionDataFromElementaryCCTable (3.3-4)), stopping as soon as FindIndexCCTable (4.1-6) returns 1. It then calls FindIrreduciblesInFullLattices (4.1-8) to extract the irreducible characters from the completed lattice.
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> CCT := CCTable(G);; gap> IrrCCTableHNF(CCT); [ [ 1, 1, 1, 1, 0, 0, 0 ], [ 3, -1, 0, 0, 0, -1, -1 ], [ 3, -1, 0, 1, 0, 1, 1 ], [ 4, 0, 1, -1, 0, 0, 0 ], [ 5, 1, -1, 0, 0, 0, 0 ] ]
Finally, we document a utility function for adjusting the Hermite normal form of an integer by adding a further vector to the lattices spanned by its rows.
‣ AddVectorToHNF( hnf, piv, v ) | ( function ) |
Returns: a positive integer
Here hnf is an integer matrix in Hermite normal form, already of the (full) rank of the ambient lattice, piv is the list of its pivot column positions, and v is a further integer vector in the rational span of the rows of hnf. This function changes hnf in place to a Hermite normal form of the lattice generated by the old rows of hnf together with v (which, since the rank does not change, still has the same number of rows), and returns the index of the old lattice of hnf in this new lattice (which is 1 if v was already contained in the old lattice). This is used by UpdateHNFCCTable (4.1-4).
gap> hnf := [ [ 1, 0, 1, 478, -2, -649 ], [ 0, 1, 1, 362, 2, -492 ], > [ 0, 0, 0, 546, 0, -742 ] ];; gap> piv := [1,2,4];; gap> v := [3, 7, 1, 6, 0, -1];; gap> AddVectorToHNF(hnf, piv, v); 39 gap> hnf; [ [ 1, 0, 1, 2, -1090, 779 ], [ 0, 1, 1, 12, -798, 558 ], [ 0, 0, 0, 14, 32, -42 ] ]
‣ CCTScalarProduct( CCT, c, d ) | ( function ) |
Returns: an integer
Let CCT be an IsCCTable (4.1-1) object, and let c and d be two generalized characters of CCT, encoded as integer vectors as produced by EncodeForCCTable (4.1-2). This function returns the scalar product of c and d.
This is used as the method for ScalarProduct (Reference: ScalarProduct for two vector objects) for characters of an IsCCTable (4.1-1) object. The CCTab also provides faster implementations of this function as kernel extension. (It can be checked if this is installed with IsBound(CCTScalarProductInternal2);.
Note that this function cannot be used for arbitrary class functions, it only works for class functions which are rational linear combinations of irreducible characters.
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> CCT := CCTable(G);; gap> irr := Irr(CCT); [ [ 1, 1, 1, 1, 0, 0, 0 ], [ 3, -1, 0, 0, 0, -1, -1 ], [ 3, -1, 0, 1, 0, 1, 1 ], [ 4, 0, 1, -1, 0, 0, 0 ], [ 5, 1, -1, 0, 0, 0, 0 ] ] gap> List(irr, c-> List(irr, d-> ScalarProduct(CCT, c, d))); [ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 1 ] ]
‣ SplitByCentre( CCT ) | ( operation ) |
‣ SplitByCentre( CCT, zind ) | ( method ) |
‣ HasSplittingCentre( CCT ) | ( filter ) |
‣ SplittingCentre( CCT ) | ( attribute ) |
Let CCT be an IsCCTable (4.1-1) object of a group G. In the second form, zind must be a list of numbers of conjugacy classes of G forming a subgroup Z of the center of G (with the class of the identity first). In the first form, zind is computed as the set of classes of length 1, that is the full centre of G.
Each irreducible character of G restricted to Z is a multiple of an irreducible character of Z (Schur's Lemma). We get an orthogonal decomposition of the lattice of generalized characters into sublattices spanned by irreducible characters whose restrictions to Z are multiples of the same irreducible character. SplitByCentre computes a data structure which allows to split any generalized character according to this decomposition. We only need to store class functions for one character of Z per Galois orbit (the others can be computed by GaloisCyc (Reference: GaloisCyc for a cyclotomic)).
This splitting is applied to all generalized characters already stored in CCT and to all generalized characters which are imported afterwards.
After a successful call with non-trivial Z the filter HasSplittingCentre is set in CCT and the attribute SplittingCentre of CCT is set to zind.
gap> G := SL(4,5);; gap> CCT := CCTable(G);; gap> SplitByCentre(CCT); gap> HasSplittingCentre(CCT); true gap> SplittingCentre(CCT); [ 1, 10, 19, 28 ]
‣ SplitCharacterByCentre( CCT, ch ) | ( operation ) |
‣ SplitEncodedCharacterByCentre( CCT, ech ) | ( operation ) |
Returns: a list of (encoded) characters
Let CCT be an IsCCTable (4.1-1) object with HasSplittingCentre(CCT) = true. In the first form let ch be a generalized character of the underlying group, given by a list of values on all conjugacy classes (not encoded as by EncodeForCCTable (4.1-2)). In the second form ech is a character endoded for CCT. This function decomposes the character according to the splitting centre (see SplitByCentre (4.3-1)).
gap> G := SmallGroup(96, 14);; gap> G := SmallGroup(96, 14);; gap> CCT := CCTable(G);; gap> SplitByCentre(CCT); gap> U := TrivialSubgroup(G);; gap> reg := InducedClassFunction(TrivialCharacter(U), G);; gap> SplitCharacterByCentre(CCT, reg); [ [ 24, 0, 0, 24, 0, 24, 0, 0, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 24, 0, 0, -24, 0, 24, 0, 0, 0, 0, 0, 0, 0, -24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 24, 0, 0, 24, 0, -24, 0, 0, 0, 0, 0, 0, 0, -24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 24, 0, 0, -24, 0, -24, 0, 0, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ]
‣ NaturalCharacters( G ) | ( attribute ) |
Returns: a list of characters
Returns a list of characters of the finite group G derived from the way G is represented, these are ususally cheap to compute. The following cases are handled:
the permutation characters on the orbits of moved points, minus the trivial character
the character of traces of the elements
the permutation characters on the non-zero vectors of the natural module (over the field of definition and over its quadratic extension), and on the one-dimensional subspaces of the natural module
the regular character of G
gap> NaturalCharacters(AlternatingGroup(5)); [ Character( CharacterTable( Alt( [ 1 .. 5 ] ) ), [ 4, 0, 1, -1, -1 ] ) ] gap> NaturalCharacters(SL(3,5)); [ Character( CharacterTable( SL(3,5) ), [ 124, 4, 4, 0, 0, 4, 24, 4, 4, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ), Character( CharacterTable( SL(3,5) ), [ 15624, 24, 24, 0, 0, 24, 624, 24, 24, 0, 0, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ), Character( CharacterTable( SL(3,5) ), [ 30, 6, 0, 6, 6, 2, 5, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 ] ) ] gap> NaturalCharacters(SmallGroup(24,4)); [ Character( CharacterTable( <pc group of size 24 with 4 generators> ), [ 24, 0, 0, 0, 0, 0, 0, 0, 0 ] ) ]
generated by GAPDoc2HTML