This package implements various utility functions which may also be of independent interest. For example, there are functions for identifying the conjugacy class of a given element, or for computing all power maps of a finite group, or for computing information about rational conjugacy classes. Furthermore there are utilities for certain integer matrices.
‣ PositionConjugacyClass( G, x[, exclude] ) | ( function ) |
Returns: a positive integer
Let G be a finite group and x an element of G. This function returns the position of the conjugacy class of x in the list ConjugacyClasses(G). It uses ConjugacyClassInvariants (3.1-2) to identify the class by computing class invariants of x until the class is uniquely determined.
If the optional argument exclude is given, it must be a list of class positions which is guaranteed not to contain the class position of the class of x. This information can sometimes help to speed up the identification.
gap> G := AlternatingGroup(5);; gap> creps := List(ConjugacyClasses(G), Representative);; gap> List(creps, x-> PositionConjugacyClass(G, x^Random(G))); [ 1, 2, 3, 4, 5 ]
‣ ConjugacyClassInvariants( G[, funcs] ) | ( function ) |
Returns: a record
Let G be a finite group. This function computes and returns a record r that is used by PositionConjugacyClass (3.1-1) to quickly identify the conjugacy class of an element of G. The result is cached in G!.ConjugacyClassInvariants, so it is computed only once.
The record r has components G, classes (the result of ConjugacyClasses (Reference: ConjugacyClasses attribute) for G), reps (their representatives), and tree, a recursively built decision tree used to distinguish the conjugacy classes of G by successively computed class invariants (such as element order, cycle structure, or characteristic and minimal polynomial for matrix groups), falling back to explicit conjugacy tests if necessary.
The optional argument funcs, if given, is a list of functions fu(r, tree) used to (further) build up the tree, overriding the default choices, which depend on whether G is a permutation group, a matrix group, or neither. See CCInvFuncs.CycStruct as an example of such a function.
In the following example, the first function compares with the stored class representatives; the second computes the cycle type and the third is only relevant for 5-cycles and does one conjugacy test against the representative of class 4.
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> ConjugacyClassInvariants(G); rec( G := Alt( [ 1 .. 5 ] ), classes := [ ()^G, (1,2)(3,4)^G, (1,2,3)^G, (1,2,3,4,5)^G, (1,2,3,5,4)^G ], reps := [ (), (1,2)(3,4), (1,2,3), (1,2,3,4,5), (1,2,3,5,4) ], tree := [ [ 1 .. 5 ], function( r, x ) ... end, [ 1, 2, 3, 4, 5, fail ], [ 1, 2, 3, 4, 5, [ [ 1 .. 5 ], function( r, x ) ... end, [ [ ], [ ,,, 1 ], [ , 1 ], [ 2 ] ], [ 1, [ [ 4, 5 ], function( r, x ) ... end, [ 4, 5 ], [ 4, 5 ] ], 3, 2 ] ] ] ] )
Let x_1, ..., x_k be conjugacy class representatives of a finite group G. The n-th power map of G is the list of k integers such that the i-th entry is j when x_i^n is conjugate to x_j. If x_i has order m then the power map of class i is a list of length m such that the n-th entry is j if x_i^{n-1} is conjugate to x_j.
Let x be an element of order m in a group G. The rational class of x is the union of the conjugacy classes of all elements which generate the same cyclic subgroup of G as x (that is, of all x^i with gcd(i, m) = 1).
‣ PowerMapsOfAllClasses( G ) | ( attribute ) |
‣ PowerMapsOfAllClasses( tbl ) | ( attribute ) |
Returns: a list of lists of positive integers
Let G be a finite group and number its conjugacy classes as in ConjugacyClasses(G). If x is a representative of class number i and has order m, then the i-th entry of PowerMapsOfAllClasses(G) is a list of length m whose j-th entry is the number of the class containing x^{j-1}, for j = 1, ..., m (so the first entry is always 1, corresponding to x^0).
In this way the result encodes the power maps of all conjugacy classes of G at once. The implementation tries to minimize the number of, sometimes expensive, calls to PositionConjugacyClass (3.1-1); the algorithm computes the orbit of the class of x under the action of the unit group of the integers modulo m.
In the second form PowerMapsOfAllClasses(tbl) the result is with respect to the ordering of conjugacy classes in the character table tbl.
gap> G := AlternatingGroup(5);; gap> List(ConjugacyClasses(G), c-> Order(Representative(c))); [ 1, 2, 3, 5, 5 ] gap> PowerMapsOfAllClasses(G); [ [ 1 ], [ 1, 2 ], [ 1, 3, 3 ], [ 1, 4, 5, 5, 4 ], [ 1, 5, 4, 4, 5 ] ] gap> t := CharacterTable("M11"); CharacterTable( "M11" ) gap> PowerMapsOfAllClasses(t); [ [ 1 ], [ 1, 2 ], [ 1, 3, 3 ], [ 1, 4, 2, 4 ], [ 1, 5, 5, 5, 5 ], [ 1, 6, 3, 2, 3, 6 ], [ 1, 7, 4, 7, 2, 8, 4, 8 ], [ 1, 8, 4, 8, 2, 7, 4, 7 ], [ 1, 9, 10, 9, 9, 9, 10, 10, 10, 9, 10 ] , [ 1, 10, 9, 10, 10, 10, 9, 9, 9, 10, 9 ] ]
Several other attributes and functions in this package are implemented using PowerMapsOfAllClasses.
‣ RationalClassSets( G ) | ( attribute ) |
Returns: a list of lists of positive integers
Returns a list of lists, where each inner list is the set of numbers of the conjugacy classes of G whose representatives generate conjugate cyclic subgroups (i.e., the union of these classes is a single rational class). The outer list is sorted by increasing element order and then by increasing class length. The first entry of each inner list can be used as a canonical representative number for that rational class.
gap> G := AlternatingGroup(5);; gap> List(ConjugacyClasses(G), c-> Order(Representative(c))); [ 1, 2, 3, 5, 5 ] gap> RationalClassSets(G); [ [ 1 ], [ 2 ], [ 3 ], [ 4, 5 ] ]
‣ NrRationalClasses( G ) | ( attribute ) |
Returns: a non-negative integer
Returns the number of rational classes of the finite group G.
gap> NrRationalClasses(AlternatingGroup(5)); 4
‣ RationalClassesInfo( G ) | ( attribute ) |
Returns: a list of records
Returns a list of records, one for each rational class of G (in the same order as RationalClassSets (3.2-2)(G)). This collects detailed information about the classes, used, for example, to encode character values in an IsCCTable (4.1-1) object via EncodeForCCTable (4.1-2).
If the rational class consists of a single conjugacy class, say class number i, the record has the components:
classes[ i ]
conductor1
classlenthe length of class i
orderthe order of the elements in class i
indthe position of the (rational) character value on this class in a character encoded by EncodeForCCTable (4.1-2)
exponents[ i, i ]
Otherwise, that is if the rational class consists of several conjugacy classes, the record has the components:
classesthe list of numbers of the conjugacy classes in this rational class (see RationalClassSets (3.2-2))
classlenthe (common) length of these conjugacy classes
orderthe (common) order of their elements
conductorthe smallest k > 1 such that the character values on this rational class are contained in Q extended by k-th roots of unity
indthe list of positions (of length Phi(conductor)) in a character encoded by EncodeForCCTable (4.1-2) which describe the character values on this rational class
cpolthe coefficient list of the conductor-th cyclotomic polynomial
stabilizera list of generating invertible residue classes mod order which generate the stabilizer of the class under the unit group mod order
fieldthe field generated by the character values on this class
dimthe degree of field over the rationals
exponents[ i, j, k1, ... ]: if x is in class i then j is the class of x^-1, and x^k1, ... are representatives of the other classes in this rational class (ordered as in classes)
ratveca sparse encoding of a vector related to the character values on this class, see below
For x in the field generated by E(k) let f(x) be the coefficient at 1 when x is written as a polynomial modulo the k-th cyclotomic polynomial. Let e = E(k), i in [0.. order-1], and let x, x^k1, ... be representatives of the classes in the rational class of x. Then let l be the list with l[i] = f(e^i + e^(i*k1) + ...). The component ratvec is a sparse representation of l: the list [i1, l[i1], i2, l[i2], ...], where indices with l[i] = 0 are left out. (This data structure is used by a fast function for computing scalar products of generalized characters.)
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> rci := RationalClassesInfo(G);; gap> rci[2]; rec( classes := [ 2 ], classlen := 15, conductor := 1, exponents := [ 2, 2 ], ind := 2, order := 2 ) gap> rci[4]; rec( classes := [ 4, 5 ], classlen := 12, conductor := 5, cpol := [ 1, 1, 1, 1, 1 ], dim := 4, exponents := [ 4, 4, 2 ], field := NF(5,[ 1, 4 ]), ind := [ 4 .. 7 ], order := 5, ratvec := [ 0, 2, 2, -1, 4, -1 ], stabilizer := [ 1, 4 ] )
‣ MaximalCyclics( G ) | ( attribute ) |
Returns: a list of positive integers
Returns a list l of class numbers such that the representatives of the classes i ∈ l generate representatives of the maximal cyclic subgroups (that is cyclic subgroups not contained in larger cyclic subgroups) of G, up to conjugacy. The returned numbers are always first entries of the lists in RationalClassSets (3.2-2).
gap> MaximalCyclics(AlternatingGroup(5)); [ 4, 3, 2 ]
‣ InduceAllFromCyclicSubgroup( G, i ) | ( function ) |
‣ InduceAllFromCyclicSubgroup( CCT, i ) | ( function ) |
Returns: a list of row vectors of cyclotomic numbers
In the first form G is a group. In the second form CCT is an IsCCTable (4.1-1) object of a group. Let i be the number of one of its conjugacy classes. This function returns the pairwise distinct characters of the group induced from the linear characters of the cyclic subgroup generated by a representative of class i (as lists of values, not as class function objects).
In the first form each value is the list of character values in the order of ConjugacyClasses(G).
In the second form each vector instead has one entry for every rational class of the group, in the order given by RationalClassSets (3.2-2) (i.e., conjugacy classes belonging to the same rational class share one entry).
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> T := CCTable(G);; gap> InduceAllFromCyclicSubgroup(G, 4); [ [ 12, 0, 0, 2, 2 ], [ 12, 0, 0, E(5)+E(5)^4, E(5)^2+E(5)^3 ], [ 12, 0, 0, E(5)^2+E(5)^3, E(5)+E(5)^4 ] ] gap> InduceAllFromCyclicSubgroup(T, 4); [ [ 12, 0, 0, 2 ], [ 12, 0, 0, E(5)+E(5)^4 ], [ 12, 0, 0, E(5)^2+E(5)^3 ] ]
‣ InducedFromAllMaximalCyclicSubgroups( G ) | ( function ) |
Returns: a list of lists of cyclotomic numbers
Returns the set of all characters of G induced from irreducible characters of the maximal cyclic subgroups of G, computed via MaximalCyclics (3.2-5) and InduceAllFromCyclicSubgroup (3.2-6). These characters always span the vector space of class functions on G.
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> indcyc := InducedFromAllMaximalCyclicSubgroups(G); [ [ 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 ] ] gap> Rank(indcyc); 5
‣ PowerMapCharacters( G, n ) | ( function ) |
Returns: a list of lists of integers
This function returns a list of class functions on the finite group G (as lists of values in the order of the conjugacy classes in G), associated to the map g ↦ g^n on G. For each rational class C of G, the class function has value |G|/gcd(|G|,n) on elements x with x^n ∈ C, and 0 everywhere else. According to a theorem of Frobenius (see [Ser77, Section 11.2]) these class functions are generalized characters (we sum the functions in the cited reference over all conjugacy classes in a rational class to get rational integer coefficients).
Only the non-zero class functions (for rational classes in the image of g ↦ g^n) are returned.
gap> G := AlternatingGroup(5);; gap> pmchars := PowerMapCharacters(G, 2); [ [ 30, 30, 0, 0, 0 ], [ 0, 0, 30, 0, 0 ], [ 0, 0, 0, 30, 30 ] ] gap> MatScalarProducts(Irr(G), pmchars); [ [ 8, 2, 10, -6, -6 ], [ 10, 10, -10, 0, 0 ], [ 12, -12, 0, 6, 6 ] ]
‣ SmallPowerMapCharacters( G ) | ( function ) |
Returns: a list of lists of integers
Applies PowerMapCharacters (3.2-8) for a selection of divisors n of |G| that are large (so that the value |G|/gcd(|G|,n) occurring in PowerMapCharacters (3.2-8) is small but non-zero), one n associated to each element order occurring in G. Class functions with the same pattern of zero entries are reduced to the one with (componentwise) minimal non-zero values.
gap> G := AlternatingGroup(5);; gap> G := AlternatingGroup(5);; gap> SmallPowerMapCharacters(G); [ [ 0, 0, 0, 5, 5 ], [ 0, 0, 3, 0, 0 ], [ 0, 4, 0, 0, 0 ], [ 4, 0, 4, 4, 4 ], [ 3, 3, 0, 3, 3 ], [ 5, 5, 5, 0, 0 ] ]
And here is a utility function that makes use of PowerMapsOfAllClasses (3.2-1).
‣ ActionAutomorphismsOnConjugacyClasses( G, A ) | ( function ) |
‣ ActionAutomorphismsOnRationalClasses( G, A ) | ( function ) |
Returns: a permutation group
Let A be a group of automorphisms of G (for example AutomorphismGroup(G)). The first function returns the permutation group describing the induced action of A on the conjugacy classes of G (identified by their position in ConjugacyClasses(G)). The generators of the result correspond to GeneratorsOfGroup(A).
The second function returns the permutation group for the induced action on the rational classes of G.
The first function finds the classes of the images of generators of maximal cyclic subgroups and deduces the rest from PowerMapsOfAllClasses (3.2-1) for G.
gap> G := AlternatingGroup(5);; gap> A := AutomorphismGroup(G); <group of size 120 with 3 generators> gap> ActionAutomorphismsOnConjugacyClasses(G, A); Group([ (4,5), (), () ]) gap> ActionAutomorphismsOnRationalClasses(G, A); Group(())
To compute the irreducible characters of a finite group G we are interested in the characters of G induced from p-elementary subgroups ⟨x⟩ × P, where p is a prime, x ∈ G is of order not divisible by p, and P is a p-subgroup of the centralizer of x in G. An elementary subgroup of G is a p-elementary subgroup for some prime p. We are mainly interested in maximal elementary subgroups (those not contained in larger elementary subgroups).
‣ MaximalNonCyclicElementarySubgroups( G ) | ( attribute ) |
Returns: a list of pairs of positive integers
This function returns a list of pairs [ i, p ], where i is the number of a conjugacy class in G and p is a prime. To each such pair we consider a subgroup ⟨x⟩ × P, where x is a representative of class i and P is a Sylow-p-subgroup of the centralizer of x. These subgroups form, up to conjugacy in G, the non-cyclic maximal elementary subgroups of G.
Brauer's theorem on the characterization of characters of G says that the full lattice of generalized characters of G (that is all integer linear combinations of irreducible characters) is spanned by the characters induced from the maximal elementary subgroups of G, that is the maximal cyclic subgroups (see MaximalCyclics (3.2-5)) and the subgroups descibed by this function. See [Isa76, Chapter 8] for more details.
gap> G := SL(4,2);; gap> MaximalNonCyclicElementarySubgroups(G); [ [ 1, 3 ], [ 1, 2 ], [ 6, 2 ] ]
‣ InducedFromElementary( G, i, p[, opts...] ) | ( function ) |
‣ InducedFromElementary( CCT, i, p[, opts...] ) | ( function ) |
Returns: a list of lists of cyclotomic numbers, or an integer
In the first form G is a group, in the second form CCT is an IsCCTable (4.1-1) object of a group G. Let i be an integer and p be a prime, such that x contained the i-th conjugacy class of G has order not divisible by p. We consider the p-elementary subgroup E = ⟨x⟩ × S where S is a Sylow-p-subgroup of the centralizer of x.
This function returns the pairwise distinct characters of G induced from the irreducible characters of E (as lists of values, in the order of ConjugacyClasses(G)).
The following further optional arguments may be given, in any order:
"linear"only the characters induced from the linear characters of E are computed
"nonlinear"only the characters induced from the non-linear irreducible characters of E are computed
if the number of conjugacy classes of E, say k, is larger than max, no characters are computed and k is returned instead (this can be used to skip elementary subgroups that would be too expensive to handle)
gap> G := AlternatingGroup(5);; gap> InducedFromElementary(G, 1, 2); [ [ 15, -1, 0, 0, 0 ], [ 15, 3, 0, 0, 0 ] ]
The following two functions try to find the fusion with fewer class identifications, respectively provide an iterator for the irreducible characters of an elementary subgroup. This can be useful in cases where elementary subgroups have a huge number of conjugacy classes.
‣ FusionElementaryCCTable( CCT, i, p ) | ( function ) |
Returns: a list of length 2
Let CCT be an IsCCTable (4.1-1) object of a group G. The arguments i and p decribe an elementary subgroup E = ⟨x⟩ × S, as explained in InducedFromElementary (3.3-2).
This function computes the fusion of the conjugacy classes of E into the classes of G. The implementation tries to avoid class identifications and uses the power maps. The result is a list [ fus, needed ]. Here fus is a list with one entry of form
[ j, [ e1, k1, k2, ... ], [ e2, ... ], ... ]
for every class j of G representing a rational class (see RationalClassSets (3.2-2)) that occurs in the image of the fusion. Here e1, e2, ... are exponents and they are followed by numbers k such that the classes of x^ei y with y in class k of S fuse into class j of G.
The second entry needed is the set of numbers of classes of S occurring in fus.
gap> G := AlternatingGroup(5);; gap> FusionElementaryCCTable(CCTable(G), 1,2); [ [ [ 1, [ 0, 1 ] ], [ 2, [ 0, 2, 3, 4 ] ] ], [ 1, 2, 3, 4 ] ]
‣ InductionDataFromElementaryCCTable( CCT, i, p ) | ( function ) |
Returns: a record
Let CCT, i and p be as for FusionElementaryCCTable (3.3-3), describing a p-elementary subgroup E = ⟨x⟩ × S of the group G underlying CCT. This function provides an alternative, more memory efficient way to compute the characters of G induced from the irreducible characters of E than InducedFromElementary (3.3-2). This is useful in particular when S has a large number of conjugacy classes.
The irreducible characters of the p-group S are described via BaumClausenInfo (see IrrBaumClausen (Reference: IrrBaumClausen)), and the record returned by this function contains a component next, a function without arguments. Each call of .next() returns |x| induced characters from E; or fail when there are no more such characters.
In contrast to InducedFromElementary (3.3-2), this function does not detect and remove induced characters occurring several times.
gap> G := SymmetricGroup(5);; gap> ind := InductionDataFromElementaryCCTable(CCTable(G),1,2);; gap> ind.next(); [ [ 15, 3, 3, 0, 1, 0, 0 ] ] gap> ind.next(); [ [ 15, 3, -1, 0, -1, 0, 0 ] ] gap> ind.next(); [ [ 15, -3, 3, 0, -1, 0, 0 ] ] gap> ind.next(); [ [ 15, -3, -1, 0, 1, 0, 0 ] ] gap> ind.next(); [ [ 30, 0, -2, 0, 0, 0, 0 ] ] gap> ind.next(); fail
This package uses a variant of the LLL algorithm to find the irreducible characters from another integral basis of the lattice of generalized characters. And there are functions to compute Hermite normal forms and inverses of unimodular matrices.
There are variants of these functions written in GAP. But we also provide variants which use standalone programs which need to be compiled during installation. These depend on the FLINT library, see [{FLI}]. These standalone programs use several threads. The number of these threads is configured in the variable NRFlintThreads, it defaults to 8 (but you can change it, depending on the number of cores of your machine).
‣ HermiteIntMat( mat ) | ( function ) |
Returns: an integer matrix
Returns the Hermite normal form of the integer matrix mat. The GAP variant is just HermiteNormalFormIntegerMat (Reference: HermiteNormalFormIntegerMat), the standalone variant uses a translation of DoNFIM to FLINT.
gap> HermiteIntMat(RandomUnimodularMat(4)); [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ]
‣ PermutedFractionFreeIntegerGaussPositiveDefinite( A ) | ( function ) |
Returns: a list [ B, perm ]
Here A must be a square, symmetric, positive definite integer matrix. This function computes a fraction free Gauss elimination of A, together with a permutation perm of the rows and columns of A, such that the diagonal entries of the resulting matrix B are minimal (the i-th diagonal entry of B is the determinant of the upper left i × i submatrix of the permuted A, that is, its i-th principal minor).
Remark: The matrix B is the transpose of the μ-matrix in classical LLL, with its i-th row multiplied by the i-th principal minor d_i.
gap> A := [ [ 9, -3, 1, -2 ], [ -3, 3, 1, 1 ], [ 1, 1, 13, -2 ], > [ -2, 1, -2, 5 ] ];; gap> PermutedFractionFreeIntegerGaussPositiveDefinite(A); [ [ [ 3, 1, -3, 1 ], [ 0, 14, -3, -7 ], [ 0, 0, 81, 21 ], [ 0, 0, 0, 900 ] ], (1,3,4,2) ]
‣ InverseUnimodularMat( A ) | ( function ) |
Returns: an integer matrix
Here A must be a unimodular integer matrix (that is, a square integer matrix with determinant ± 1). This function returns the inverse of A, which again is an integer matrix.
This is a simplified variant of InverseRatMat (EDIM: InverseRatMat), based on a p-adic lifting approach.
gap> A := RandomUnimodularMat(5);; gap> A := RandomUnimodularMat(5);; gap> A * InverseUnimodularMat(A); [ [ 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 ] ]
‣ LLLTransformUnimodularGram( gr ) | ( function ) |
Returns: a unimodular integer matrix
Here gr must be a symmetric, positive definite integer matrix (a Gram matrix). This function returns a unimodular integer matrix H such that H * gr * TransposedMat(H) is the identity matrix.
The algorithm is similar to the modular variant of the LLL-algorithm described in [Sto96], but here the main loop is parallelized.
gap> A := RandomUnimodularMat(5);; gap> A := RandomUnimodularMat(5);; gap> gr := A * TransposedMat(A);; gap> h := LLLTransformUnimodularGram(gr);; gap> h * gr * TransposedMat(h); [ [ 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 ] ]
generated by GAPDoc2HTML