  
  [1X3 [33X[0;0YUtility functions from the [5XCCTab[105X[101X[1X package[133X[101X
  
  [33X[0;0YThis  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.[133X
  
  
  [1X3.1 [33X[0;0YIdentifying conjugacy classes of elements[133X[101X
  
  [1X3.1-1 PositionConjugacyClass[101X
  
  [33X[1;0Y[29X[2XPositionConjugacyClass[102X( [3XG[103X, [3Xx[103X[, [3Xexclude[103X] ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya positive integer[133X
  
  [33X[0;0YLet  [3XG[103X  be  a  finite group and [3Xx[103X an element of [3XG[103X. This function returns the
  position  of  the  conjugacy  class of [3Xx[103X in the list [10XConjugacyClasses([3XG[103X[10X)[110X. It
  uses  [2XConjugacyClassInvariants[102X  ([14X3.1-2[114X)  to  identify the class by computing
  class invariants of [3Xx[103X until the class is uniquely determined.[133X
  
  [33X[0;0YIf  the  optional  argument  [3Xexclude[103X  is  given,  it must be a list of class
  positions which is guaranteed not to contain the class position of the class
  of [3Xx[103X. This information can sometimes help to speed up the identification.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27Xcreps := List(ConjugacyClasses(G), Representative);;[127X[104X
    [4X[25Xgap>[125X [27XList(creps, x-> PositionConjugacyClass(G, x^Random(G)));[127X[104X
    [4X[28X[ 1, 2, 3, 4, 5 ][128X[104X
  [4X[32X[104X
  
  [1X3.1-2 ConjugacyClassInvariants[101X
  
  [33X[1;0Y[29X[2XConjugacyClassInvariants[102X( [3XG[103X[, [3Xfuncs[103X] ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya record[133X
  
  [33X[0;0YLet  [3XG[103X be a finite group. This function computes and returns a record [22Xr[122X that
  is  used by [2XPositionConjugacyClass[102X ([14X3.1-1[114X) to quickly identify the conjugacy
  class    of    an    element    of    [3XG[103X.    The    result   is   cached   in
  [10X[3XG[103X[10X!.ConjugacyClassInvariants[110X, so it is computed only once.[133X
  
  [33X[0;0YThe  record  [22Xr[122X  has  components  [10XG[110X,  [10Xclasses[110X (the result of [2XConjugacyClasses[102X
  ([14XReference:    ConjugacyClasses    attribute[114X)    for    [3XG[103X),    [10Xreps[110X   (their
  representatives),  and  [10Xtree[110X,  a  recursively  built  decision  tree used to
  distinguish  the  conjugacy  classes  of  [3XG[103X  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.[133X
  
  [33X[0;0YThe  optional  argument  [3Xfuncs[103X, if given, is a list of functions [10Xfu(r, tree)[110X
  used  to  (further) build up the tree, overriding the default choices, which
  depend  on whether [3XG[103X is a permutation group, a matrix group, or neither. See
  [10XCCInvFuncs.CycStruct[110X as an example of such a function.[133X
  
  [33X[0;0YIn  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.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XConjugacyClassInvariants(G);[127X[104X
    [4X[28Xrec( G := Alt( [ 1 .. 5 ] ), [128X[104X
    [4X[28X  classes := [ ()^G, (1,2)(3,4)^G, (1,2,3)^G, (1,2,3,4,5)^G, [128X[104X
    [4X[28X      (1,2,3,5,4)^G ], [128X[104X
    [4X[28X  reps := [ (), (1,2)(3,4), (1,2,3), (1,2,3,4,5), (1,2,3,5,4) ], [128X[104X
    [4X[28X  tree := [ [ 1 .. 5 ], function( r, x ) ... end, [128X[104X
    [4X[28X      [ 1, 2, 3, 4, 5, fail ], [128X[104X
    [4X[28X      [ 1, 2, 3, 4, 5, [128X[104X
    [4X[28X          [ [ 1 .. 5 ], function( r, x ) ... end, [128X[104X
    [4X[28X              [ [  ], [ ,,, 1 ], [ , 1 ], [ 2 ] ], [128X[104X
    [4X[28X              [ 1, [128X[104X
    [4X[28X                  [ [ 4, 5 ], function( r, x ) ... end, [ 4, 5 ], [128X[104X
    [4X[28X                      [ 4, 5 ] ], 3, 2 ] ] ] ] )[128X[104X
  [4X[32X[104X
  
  
  [1X3.2 [33X[0;0YPower maps and rational classes[133X[101X
  
  [33X[0;0YLet  [22Xx_1,  ...,  x_k[122X be conjugacy class representatives of a finite group [22XG[122X.
  The  [13X[22Xn[122X-th  power map of [22XG[122X[113X is the list of [22Xk[122X integers such that the [22Xi[122X-th entry
  is  [22Xj[122X  when [22Xx_i^n[122X is conjugate to [22Xx_j[122X. If [22Xx_i[122X has order [22Xm[122X then the [13Xpower map
  of  class [22Xi[122X[113X is a list of length [22Xm[122X such that the [22Xn[122X-th entry is [22Xj[122X if [22Xx_i^{n-1}[122X
  is conjugate to [22Xx_j[122X.[133X
  
  [33X[0;0YLet  [22Xx[122X be an element of order [22Xm[122X in a group [22XG[122X. The [13Xrational class[113X of [22Xx[122X is the
  union  of  the  conjugacy  classes  of  all elements which generate the same
  cyclic subgroup of [22XG[122X as [22Xx[122X (that is, of all [22Xx^i[122X with [22Xgcd(i, m) = 1)[122X.[133X
  
  [1X3.2-1 PowerMapsOfAllClasses[101X
  
  [33X[1;0Y[29X[2XPowerMapsOfAllClasses[102X( [3XG[103X ) [32X attribute[133X
  [33X[1;0Y[29X[2XPowerMapsOfAllClasses[102X( [3Xtbl[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya list of lists of positive integers[133X
  
  [33X[0;0YLet   [3XG[103X   be  a  finite  group  and  number  its  conjugacy  classes  as  in
  [10XConjugacyClasses([3XG[103X[10X)[110X.  If  [22Xx[122X  is  a  representative of class number [22Xi[122X and has
  order [22Xm[122X, then the [22Xi[122X-th entry of [10XPowerMapsOfAllClasses(G)[110X is a list of length
  [22Xm[122X whose [22Xj[122X-th entry is the number of the class containing [22Xx^{j-1}[122X, for [22Xj = 1,
  ..., m[122X (so the first entry is always [22X1[122X, corresponding to [22Xx^0[122X).[133X
  
  [33X[0;0YIn  this way the result encodes the power maps of [13Xall[113X conjugacy classes of [3XG[103X
  at  once.  The  implementation  tries  to  minimize the number of, sometimes
  expensive,  calls  to [2XPositionConjugacyClass[102X ([14X3.1-1[114X); the algorithm computes
  the  orbit  of  the  class  of  [22Xx[122X  under the action of the unit group of the
  integers modulo [22Xm[122X.[133X
  
  [33X[0;0YIn  the second form [10XPowerMapsOfAllClasses(tbl)[110X the result is with respect to
  the ordering of conjugacy classes in the character table [3Xtbl[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XList(ConjugacyClasses(G), c-> Order(Representative(c)));[127X[104X
    [4X[28X[ 1, 2, 3, 5, 5 ][128X[104X
    [4X[25Xgap>[125X [27XPowerMapsOfAllClasses(G);[127X[104X
    [4X[28X[ [ 1 ], [ 1, 2 ], [ 1, 3, 3 ], [ 1, 4, 5, 5, 4 ], [ 1, 5, 4, 4, 5 ] ][128X[104X
    [4X[25Xgap>[125X [27Xt := CharacterTable("M11");[127X[104X
    [4X[28XCharacterTable( "M11" )[128X[104X
    [4X[25Xgap>[125X [27XPowerMapsOfAllClasses(t);[127X[104X
    [4X[28X[ [ 1 ], [ 1, 2 ], [ 1, 3, 3 ], [ 1, 4, 2, 4 ], [ 1, 5, 5, 5, 5 ], [128X[104X
    [4X[28X  [ 1, 6, 3, 2, 3, 6 ], [ 1, 7, 4, 7, 2, 8, 4, 8 ], [128X[104X
    [4X[28X  [ 1, 8, 4, 8, 2, 7, 4, 7 ], [ 1, 9, 10, 9, 9, 9, 10, 10, 10, 9, 10 ][128X[104X
    [4X[28X    , [ 1, 10, 9, 10, 10, 10, 9, 9, 9, 10, 9 ] ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YSeveral other attributes and functions in this package are implemented using
  [2XPowerMapsOfAllClasses[102X.[133X
  
  [1X3.2-2 RationalClassSets[101X
  
  [33X[1;0Y[29X[2XRationalClassSets[102X( [3XG[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya list of lists of positive integers[133X
  
  [33X[0;0YReturns  a list of lists, where each inner list is the set of numbers of the
  conjugacy  classes  of  [3XG[103X  whose  representatives  generate conjugate cyclic
  subgroups (i.e., the union of these classes is a single [13Xrational class[113X). 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.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XList(ConjugacyClasses(G), c-> Order(Representative(c)));[127X[104X
    [4X[28X[ 1, 2, 3, 5, 5 ][128X[104X
    [4X[25Xgap>[125X [27XRationalClassSets(G);[127X[104X
    [4X[28X[ [ 1 ], [ 2 ], [ 3 ], [ 4, 5 ] ][128X[104X
  [4X[32X[104X
  
  [1X3.2-3 NrRationalClasses[101X
  
  [33X[1;0Y[29X[2XNrRationalClasses[102X( [3XG[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya non-negative integer[133X
  
  [33X[0;0YReturns the number of rational classes of the finite group [3XG[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XNrRationalClasses(AlternatingGroup(5));[127X[104X
    [4X[28X4[128X[104X
  [4X[32X[104X
  
  [1X3.2-4 RationalClassesInfo[101X
  
  [33X[1;0Y[29X[2XRationalClassesInfo[102X( [3XG[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya list of records[133X
  
  [33X[0;0YReturns  a  list  of  records, one for each rational class of [3XG[103X (in the same
  order  as  [2XRationalClassSets[102X ([14X3.2-2[114X)([3XG[103X)). This collects detailed information
  about  the  classes,  used,  for  example,  to encode character values in an
  [2XIsCCTable[102X ([14X4.1-1[114X) object via [2XEncodeForCCTable[102X ([14X4.1-2[114X).[133X
  
  [33X[0;0YIf the rational class consists of a single conjugacy class, say class number
  [22Xi[122X, the record has the components:[133X
  
  [8X[10Xclasses[110X[8X[108X
        [33X[0;6Y[10X[ i ][110X[133X
  
  [8X[10Xconductor[110X[8X[108X
        [33X[0;6Y[10X1[110X[133X
  
  [8X[10Xclasslen[110X[8X[108X
        [33X[0;6Ythe length of class [22Xi[122X[133X
  
  [8X[10Xorder[110X[8X[108X
        [33X[0;6Ythe order of the elements in class [22Xi[122X[133X
  
  [8X[10Xind[110X[8X[108X
        [33X[0;6Ythe  position  of  the  (rational)  character value on this class in a
        character encoded by [2XEncodeForCCTable[102X ([14X4.1-2[114X)[133X
  
  [8X[10Xexponents[110X[8X[108X
        [33X[0;6Y[10X[ i, i ][110X[133X
  
  [33X[0;0YOtherwise,  that  is  if  the  rational  class consists of several conjugacy
  classes, the record has the components:[133X
  
  [8X[10Xclasses[110X[8X[108X
        [33X[0;6Ythe  list  of  numbers of the conjugacy classes in this rational class
        (see [2XRationalClassSets[102X ([14X3.2-2[114X))[133X
  
  [8X[10Xclasslen[110X[8X[108X
        [33X[0;6Ythe (common) length of these conjugacy classes[133X
  
  [8X[10Xorder[110X[8X[108X
        [33X[0;6Ythe (common) order of their elements[133X
  
  [8X[10Xconductor[110X[8X[108X
        [33X[0;6Ythe  smallest  [10Xk  >  1[110X such that the character values on this rational
        class are contained in [22XQ[122X extended by [10Xk[110X-th roots of unity[133X
  
  [8X[10Xind[110X[8X[108X
        [33X[0;6Ythe  list  of  positions  (of  length  [10XPhi(conductor)[110X)  in a character
        encoded  by  [2XEncodeForCCTable[102X  ([14X4.1-2[114X)  which  describe  the character
        values on this rational class[133X
  
  [8X[10Xcpol[110X[8X[108X
        [33X[0;6Ythe coefficient list of the [10Xconductor[110X-th cyclotomic polynomial[133X
  
  [8X[10Xstabilizer[110X[8X[108X
        [33X[0;6Ya  list  of  generating  invertible  residue  classes  mod [10Xorder[110X which
        generate the stabilizer of the class under the unit group mod [10Xorder[110X[133X
  
  [8X[10Xfield[110X[8X[108X
        [33X[0;6Ythe field generated by the character values on this class[133X
  
  [8X[10Xdim[110X[8X[108X
        [33X[0;6Ythe degree of [10Xfield[110X over the rationals[133X
  
  [8X[10Xexponents[110X[8X[108X
        [33X[0;6Y[10X[ i, j, k1, ... ][110X: if [10Xx[110X is in class [22Xi[122X then [22Xj[122X is the class of [10Xx^-1[110X, and
        [10Xx^k1[110X,  ...  are  representatives of the other classes in this rational
        class (ordered as in [10Xclasses[110X)[133X
  
  [8X[10Xratvec[110X[8X[108X
        [33X[0;6Ya  sparse encoding of a vector related to the character values on this
        class, see below[133X
  
  [33X[0;0YFor [10Xx[110X in the field generated by [10XE(k)[110X let [10Xf(x)[110X be the coefficient at [10X1[110X when [10Xx[110X
  is  written  as  a polynomial modulo the [10Xk[110X-th cyclotomic polynomial. Let [10Xe =
  E(k)[110X,  [10Xi[110X  in  [10X[0..  order-1][110X, and let [10Xx[110X, [10Xx^k1[110X, ... be representatives of the
  classes in the rational class of [10Xx[110X. Then let [10Xl[110X be the list with [10Xl[i] = f(e^i
  + e^(i*k1) + ...)[110X. The component [10Xratvec[110X is a sparse representation of [10Xl[110X: the
  list  [10X[i1, l[i1], i2, l[i2], ...][110X, where indices with [10Xl[i] = 0[110X are left out.
  (This  data  structure  is  used  by  a  fast  function for computing scalar
  products of generalized characters.)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27Xrci := RationalClassesInfo(G);;[127X[104X
    [4X[25Xgap>[125X [27Xrci[2];[127X[104X
    [4X[28Xrec( classes := [ 2 ], classlen := 15, conductor := 1, [128X[104X
    [4X[28X  exponents := [ 2, 2 ], ind := 2, order := 2 )[128X[104X
    [4X[25Xgap>[125X [27Xrci[4];[127X[104X
    [4X[28Xrec( classes := [ 4, 5 ], classlen := 12, conductor := 5, [128X[104X
    [4X[28X  cpol := [ 1, 1, 1, 1, 1 ], dim := 4, exponents := [ 4, 4, 2 ], [128X[104X
    [4X[28X  field := NF(5,[ 1, 4 ]), ind := [ 4 .. 7 ], order := 5, [128X[104X
    [4X[28X  ratvec := [ 0, 2, 2, -1, 4, -1 ], stabilizer := [ 1, 4 ] )[128X[104X
  [4X[32X[104X
  
  [1X3.2-5 MaximalCyclics[101X
  
  [33X[1;0Y[29X[2XMaximalCyclics[102X( [3XG[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya list of positive integers[133X
  
  [33X[0;0YReturns  a  list  [22Xl[122X  of  class  numbers such that the representatives of the
  classes [22Xi ∈ l[122X generate representatives of the maximal cyclic subgroups (that
  is  cyclic  subgroups  not contained in larger cyclic subgroups) of [3XG[103X, up to
  conjugacy.  The  returned  numbers  are always first entries of the lists in
  [2XRationalClassSets[102X ([14X3.2-2[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XMaximalCyclics(AlternatingGroup(5));[127X[104X
    [4X[28X[ 4, 3, 2 ][128X[104X
  [4X[32X[104X
  
  [1X3.2-6 InduceAllFromCyclicSubgroup[101X
  
  [33X[1;0Y[29X[2XInduceAllFromCyclicSubgroup[102X( [3XG[103X, [3Xi[103X ) [32X function[133X
  [33X[1;0Y[29X[2XInduceAllFromCyclicSubgroup[102X( [3XCCT[103X, [3Xi[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya list of row vectors of cyclotomic numbers[133X
  
  [33X[0;0YIn  the  first  form  [3XG[103X  is  a group. In the second form [3XCCT[103X is an [2XIsCCTable[102X
  ([14X4.1-1[114X)  object  of  a  group.  Let  [3Xi[103X 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  [3Xi[103X  (as  lists  of  values,  not as class function
  objects).[133X
  
  [33X[0;0YIn the first form each value is the list of character values in the order of
  [10XConjugacyClasses([3XG[103X[10X)[110X.[133X
  
  [33X[0;0YIn  the  second  form  each  vector instead has one entry for every [13Xrational[113X
  class  of  the group, in the order given by [2XRationalClassSets[102X ([14X3.2-2[114X) (i.e.,
  conjugacy classes belonging to the same rational class share one entry).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XT := CCTable(G);;[127X[104X
    [4X[25Xgap>[125X [27XInduceAllFromCyclicSubgroup(G, 4);[127X[104X
    [4X[28X[ [ 12, 0, 0, 2, 2 ], [ 12, 0, 0, E(5)+E(5)^4, E(5)^2+E(5)^3 ], [128X[104X
    [4X[28X  [ 12, 0, 0, E(5)^2+E(5)^3, E(5)+E(5)^4 ] ][128X[104X
    [4X[25Xgap>[125X [27XInduceAllFromCyclicSubgroup(T, 4);[127X[104X
    [4X[28X[ [ 12, 0, 0, 2 ], [ 12, 0, 0, E(5)+E(5)^4 ], [128X[104X
    [4X[28X  [ 12, 0, 0, E(5)^2+E(5)^3 ] ][128X[104X
  [4X[32X[104X
  
  [1X3.2-7 InducedFromAllMaximalCyclicSubgroups[101X
  
  [33X[1;0Y[29X[2XInducedFromAllMaximalCyclicSubgroups[102X( [3XG[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya list of lists of cyclotomic numbers[133X
  
  [33X[0;0YReturns  the  set of all characters of [3XG[103X induced from irreducible characters
  of  the  maximal  cyclic subgroups of [3XG[103X, computed via [2XMaximalCyclics[102X ([14X3.2-5[114X)
  and  [2XInduceAllFromCyclicSubgroup[102X  ([14X3.2-6[114X).  These characters always span the
  vector space of class functions on [3XG[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27Xindcyc := InducedFromAllMaximalCyclicSubgroups(G);[127X[104X
    [4X[28X[ [ 12, 0, 0, 2, 2 ], [ 12, 0, 0, E(5)^2+E(5)^3, E(5)+E(5)^4 ], [128X[104X
    [4X[28X  [ 12, 0, 0, E(5)+E(5)^4, E(5)^2+E(5)^3 ], [ 20, 0, -1, 0, 0 ], [128X[104X
    [4X[28X  [ 20, 0, 2, 0, 0 ], [ 30, -2, 0, 0, 0 ], [ 30, 2, 0, 0, 0 ] ][128X[104X
    [4X[25Xgap>[125X [27XRank(indcyc);[127X[104X
    [4X[28X5[128X[104X
  [4X[32X[104X
  
  [1X3.2-8 PowerMapCharacters[101X
  
  [33X[1;0Y[29X[2XPowerMapCharacters[102X( [3XG[103X, [3Xn[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya list of lists of integers[133X
  
  [33X[0;0YThis  function  returns  a list of class functions on the finite group [3XG[103X (as
  lists  of  values in the order of the conjugacy classes in [3XG[103X), associated to
  the map [22Xg ↦ g^[3Xn[103X[122X on [3XG[103X. For each rational class [22XC[122X of [3XG[103X, the class function has
  value  [22X|G|/gcd(|G|,n)[122X  on  elements  [22Xx[122X  with [22Xx^n ∈ C[122X, and [22X0[122X 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).[133X
  
  [33X[0;0YOnly  the non-zero class functions (for rational classes in the image of [22Xg ↦
  g^[3Xn[103X[122X) are returned.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27Xpmchars := PowerMapCharacters(G, 2);[127X[104X
    [4X[28X[ [ 30, 30, 0, 0, 0 ], [ 0, 0, 30, 0, 0 ], [ 0, 0, 0, 30, 30 ] ][128X[104X
    [4X[25Xgap>[125X [27XMatScalarProducts(Irr(G), pmchars);[127X[104X
    [4X[28X[ [ 8, 2, 10, -6, -6 ], [ 10, 10, -10, 0, 0 ], [ 12, -12, 0, 6, 6 ] ][128X[104X
  [4X[32X[104X
  
  [1X3.2-9 SmallPowerMapCharacters[101X
  
  [33X[1;0Y[29X[2XSmallPowerMapCharacters[102X( [3XG[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya list of lists of integers[133X
  
  [33X[0;0YApplies [2XPowerMapCharacters[102X ([14X3.2-8[114X) for a selection of divisors [22Xn[122X of [22X|[3XG[103X|[122X that
  are  large (so that the value [22X|[3XG[103X|/gcd(|[3XG[103X|,n)[122X occurring in [2XPowerMapCharacters[102X
  ([14X3.2-8[114X)  is  small  but  non-zero),  one  [22Xn[122X associated to each element order
  occurring  in  [3XG[103X.  Class functions with the same pattern of zero entries are
  reduced to the one with (componentwise) minimal non-zero values.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XSmallPowerMapCharacters(G);[127X[104X
    [4X[28X[ [ 0, 0, 0, 5, 5 ], [ 0, 0, 3, 0, 0 ], [ 0, 4, 0, 0, 0 ], [128X[104X
    [4X[28X  [ 4, 0, 4, 4, 4 ], [ 3, 3, 0, 3, 3 ], [ 5, 5, 5, 0, 0 ] ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YAnd  here  is  a  utility  function  that makes use of [2XPowerMapsOfAllClasses[102X
  ([14X3.2-1[114X).[133X
  
  [1X3.2-10 ActionAutomorphismsOnConjugacyClasses[101X
  
  [33X[1;0Y[29X[2XActionAutomorphismsOnConjugacyClasses[102X( [3XG[103X, [3XA[103X ) [32X function[133X
  [33X[1;0Y[29X[2XActionAutomorphismsOnRationalClasses[102X( [3XG[103X, [3XA[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya permutation group[133X
  
  [33X[0;0YLet  [3XA[103X  be a group of automorphisms of [3XG[103X (for example [10XAutomorphismGroup([3XG[103X[10X)[110X).
  The  first  function  returns  the  permutation group describing the induced
  action  of  [3XA[103X on the conjugacy classes of [3XG[103X (identified by their position in
  [10XConjugacyClasses([3XG[103X[10X)[110X).   The   generators   of   the   result  correspond  to
  [10XGeneratorsOfGroup([3XA[103X[10X)[110X.[133X
  
  [33X[0;0YThe  second function returns the permutation group for the induced action on
  the rational classes of [3XG[103X.[133X
  
  [33X[0;0YThe  first function finds the classes of the images of generators of maximal
  cyclic subgroups and deduces the rest from [2XPowerMapsOfAllClasses[102X ([14X3.2-1[114X) for
  [3XG[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XA := AutomorphismGroup(G);[127X[104X
    [4X[28X<group of size 120 with 3 generators>[128X[104X
    [4X[25Xgap>[125X [27XActionAutomorphismsOnConjugacyClasses(G, A);[127X[104X
    [4X[28XGroup([ (4,5), (), () ])[128X[104X
    [4X[25Xgap>[125X [27XActionAutomorphismsOnRationalClasses(G, A);[127X[104X
    [4X[28XGroup(())[128X[104X
  [4X[32X[104X
  
  
  [1X3.3 [33X[0;0YInduction from elementary subgroups[133X[101X
  
  [33X[0;0YTo  compute the irreducible characters of a finite group [22XG[122X we are interested
  in  the characters of [22XG[122X induced from [22Xp[122X-elementary subgroups [22X⟨x⟩ × P[122X, where [22Xp[122X
  is  a  prime, [22Xx ∈ G[122X is of order not divisible by [22Xp[122X, and [22XP[122X is a [22Xp[122X-subgroup of
  the  centralizer  of  [22Xx[122X  in [22XG[122X. An elementary subgroup of [22XG[122X is a [22Xp[122X-elementary
  subgroup  for  some  prime [22Xp[122X. We are mainly interested in maximal elementary
  subgroups (those not contained in larger elementary subgroups).[133X
  
  [1X3.3-1 MaximalNonCyclicElementarySubgroups[101X
  
  [33X[1;0Y[29X[2XMaximalNonCyclicElementarySubgroups[102X( [3XG[103X ) [32X attribute[133X
  [6XReturns:[106X  [33X[0;10Ya list of pairs of positive integers[133X
  
  [33X[0;0YThis  function  returns a list of pairs [10X[ i, p ][110X, where [10Xi[110X is the number of a
  conjugacy  class  in  [3XG[103X  and  [10Xp[110X  is a prime. To each such pair we consider a
  subgroup  [22X⟨x⟩  ×  P[122X,  where  [22Xx[122X  is  a  representative  of class [3Xi[103X and [22XP[122X is a
  Sylow-[22Xp[122X-subgroup  of  the  centralizer  of  [22Xx[122X.  These  subgroups form, up to
  conjugacy in [3XG[103X, the non-cyclic maximal elementary subgroups of [3XG[103X.[133X
  
  [33X[0;0YBrauer's  theorem  on  the characterization of characters of [3XG[103X says that the
  full  lattice  of  generalized  characters  of [3XG[103X (that is all integer linear
  combinations of irreducible characters) is spanned by the characters induced
  from  the  maximal  elementary  subgroups  of  [3XG[103X, that is the maximal cyclic
  subgroups  (see  [2XMaximalCyclics[102X  ([14X3.2-5[114X)) and the subgroups descibed by this
  function. See [Isa76, Chapter 8] for more details.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := SL(4,2);;[127X[104X
    [4X[25Xgap>[125X [27XMaximalNonCyclicElementarySubgroups(G);[127X[104X
    [4X[28X[ [ 1, 3 ], [ 1, 2 ], [ 6, 2 ] ][128X[104X
  [4X[32X[104X
  
  [1X3.3-2 InducedFromElementary[101X
  
  [33X[1;0Y[29X[2XInducedFromElementary[102X( [3XG[103X, [3Xi[103X, [3Xp[103X[, [3Xopts...[103X] ) [32X function[133X
  [33X[1;0Y[29X[2XInducedFromElementary[102X( [3XCCT[103X, [3Xi[103X, [3Xp[103X[, [3Xopts...[103X] ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya list of lists of cyclotomic numbers, or an integer[133X
  
  [33X[0;0YIn  the  first  form  [3XG[103X  is  a group, in the second form [3XCCT[103X is an [2XIsCCTable[102X
  ([14X4.1-1[114X) object of a group [3XG[103X. Let [3Xi[103X be an integer and [3Xp[103X be a prime, such that
  [22Xx[122X  contained  the [3Xi[103X-th conjugacy class of [22XG[122X has order not divisible by [3Xp[103X. We
  consider the [3Xp[103X-elementary subgroup [22XE = ⟨x⟩ × S[122X where [22XS[122X is a Sylow-[3Xp[103X-subgroup
  of the centralizer of [22Xx[122X.[133X
  
  [33X[0;0YThis function returns the pairwise distinct characters of [22XG[122X induced from the
  irreducible   characters  of  [22XE[122X  (as  lists  of  values,  in  the  order  of
  [10XConjugacyClasses([3XG[103X[10X)[110X).[133X
  
  [33X[0;0YThe following further optional arguments may be given, in any order:[133X
  
  [8X[10X"linear"[110X[8X[108X
        [33X[0;6Yonly  the  characters  induced  from  the  linear  characters of [22XE[122X are
        computed[133X
  
  [8X[10X"nonlinear"[110X[8X[108X
        [33X[0;6Yonly the characters induced from the non-linear irreducible characters
        of [22XE[122X are computed[133X
  
  [8Xa positive integer [3Xmax[103X[8X[108X
        [33X[0;6Yif the number of conjugacy classes of [22XE[122X, say [22Xk[122X, is larger than [3Xmax[103X, no
        characters are computed and [22Xk[122X is returned instead (this can be used to
        skip elementary subgroups that would be too expensive to handle)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XInducedFromElementary(G, 1, 2);[127X[104X
    [4X[28X[ [ 15, -1, 0, 0, 0 ], [ 15, 3, 0, 0, 0 ] ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  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.[133X
  
  [1X3.3-3 FusionElementaryCCTable[101X
  
  [33X[1;0Y[29X[2XFusionElementaryCCTable[102X( [3XCCT[103X, [3Xi[103X, [3Xp[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya list of length 2[133X
  
  [33X[0;0YLet  [3XCCT[103X  be an [2XIsCCTable[102X ([14X4.1-1[114X) object of a group [22XG[122X. The arguments [3Xi[103X and [3Xp[103X
  decribe   an   elementary   subgroup   [22XE   =   ⟨x⟩  ×  S[122X,  as  explained  in
  [2XInducedFromElementary[102X ([14X3.3-2[114X).[133X
  
  [33X[0;0YThis  function  computes  the  fusion of the conjugacy classes of [22XE[122X into the
  classes  of  [22XG[122X.  The implementation tries to avoid class identifications and
  uses  the  power  maps.  The result is a list [10X[ fus, needed ][110X. Here [10Xfus[110X is a
  list with one entry of form[133X
  
  [33X[0;0Y[10X[ j, [ e1, k1, k2, ... ], [ e2, ... ], ... ][110X[133X
  
  [33X[0;0Yfor  every class [3Xj[103X of [22XG[122X representing a rational class (see [2XRationalClassSets[102X
  ([14X3.2-2[114X))  that  occurs  in  the  image  of  the fusion. Here [10Xe1, e2, ...[110X are
  exponents and they are followed by numbers [10Xk[110X such that the classes of x^ei y
  with y in class k of S fuse into class j of G.[133X
  
  [33X[0;0YThe  second  entry [10Xneeded[110X is the set of numbers of classes of [22XS[122X occurring in
  [10Xfus[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := AlternatingGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27XFusionElementaryCCTable(CCTable(G), 1,2);[127X[104X
    [4X[28X[ [ [ 1, [ 0, 1 ] ], [ 2, [ 0, 2, 3, 4 ] ] ], [ 1, 2, 3, 4 ] ][128X[104X
  [4X[32X[104X
  
  [1X3.3-4 InductionDataFromElementaryCCTable[101X
  
  [33X[1;0Y[29X[2XInductionDataFromElementaryCCTable[102X( [3XCCT[103X, [3Xi[103X, [3Xp[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya record[133X
  
  [33X[0;0YLet  [3XCCT[103X,  [3Xi[103X  and  [3Xp[103X be as for [2XFusionElementaryCCTable[102X ([14X3.3-3[114X), describing a
  [22Xp[122X-elementary  subgroup  [22XE  =  ⟨x⟩  ×  S[122X  of the group [22XG[122X underlying [3XCCT[103X. This
  function  provides  an alternative, more memory efficient way to compute the
  characters   of  [22XG[122X  induced  from  the  irreducible  characters  of  [22XE[122X  than
  [2XInducedFromElementary[102X  ([14X3.3-2[114X).  This  is  useful in particular when [22XS[122X has a
  large number of conjugacy classes.[133X
  
  [33X[0;0YThe   irreducible   characters   of   the   [3Xp[103X-group   [22XS[122X  are  described  via
  [10XBaumClausenInfo[110X  (see  [2XIrrBaumClausen[102X  ([14XReference: IrrBaumClausen[114X)), and the
  record  returned  by  this  function  contains  a component [10Xnext[110X, a function
  without  arguments. Each call of [10X.next()[110X returns [22X|x|[122X induced characters from
  [22XE[122X; or [9Xfail[109X when there are no more such characters.[133X
  
  [33X[0;0YIn  contrast to [2XInducedFromElementary[102X ([14X3.3-2[114X), this function does not detect
  and remove induced characters occurring several times.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := SymmetricGroup(5);;[127X[104X
    [4X[25Xgap>[125X [27Xind := InductionDataFromElementaryCCTable(CCTable(G),1,2);;[127X[104X
    [4X[25Xgap>[125X [27Xind.next();[127X[104X
    [4X[28X[ [ 15, 3, 3, 0, 1, 0, 0 ] ][128X[104X
    [4X[25Xgap>[125X [27Xind.next();[127X[104X
    [4X[28X[ [ 15, 3, -1, 0, -1, 0, 0 ] ][128X[104X
    [4X[25Xgap>[125X [27Xind.next();[127X[104X
    [4X[28X[ [ 15, -3, 3, 0, -1, 0, 0 ] ][128X[104X
    [4X[25Xgap>[125X [27Xind.next();[127X[104X
    [4X[28X[ [ 15, -3, -1, 0, 1, 0, 0 ] ][128X[104X
    [4X[25Xgap>[125X [27Xind.next();[127X[104X
    [4X[28X[ [ 30, 0, -2, 0, 0, 0, 0 ] ][128X[104X
    [4X[25Xgap>[125X [27Xind.next();[127X[104X
    [4X[28Xfail[128X[104X
  [4X[32X[104X
  
  
  [1X3.4 [33X[0;0YSome utilities for integer matrices[133X[101X
  
  [33X[0;0YThis  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.[133X
  
  [33X[0;0YThere  are  variants  of these functions written in [5XGAP[105X. 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  [10XNRFlintThreads[110X, it defaults to [10X8[110X (but you can
  change it, depending on the number of cores of your machine).[133X
  
  [1X3.4-1 HermiteIntMat[101X
  
  [33X[1;0Y[29X[2XHermiteIntMat[102X( [3Xmat[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Yan integer matrix[133X
  
  [33X[0;0YReturns  the  Hermite normal form of the integer matrix [3Xmat[103X. The [5XGAP[105X variant
  is           just           [2XHermiteNormalFormIntegerMat[102X          ([14XReference:
  HermiteNormalFormIntegerMat[114X),  the  standalone variant uses a translation of
  DoNFIM to FLINT.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XHermiteIntMat(RandomUnimodularMat(4));[127X[104X
    [4X[28X[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ][128X[104X
  [4X[32X[104X
  
  [1X3.4-2 PermutedFractionFreeIntegerGaussPositiveDefinite[101X
  
  [33X[1;0Y[29X[2XPermutedFractionFreeIntegerGaussPositiveDefinite[102X( [3XA[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya list [10X[ B, perm ][110X[133X
  
  [33X[0;0YHere  [3XA[103X  must be a square, symmetric, positive definite integer matrix. This
  function  computes  a  fraction free Gauss elimination of [3XA[103X, together with a
  permutation  [10Xperm[110X  of  the  rows  and  columns  of [3XA[103X, such that the diagonal
  entries  of the resulting matrix [10XB[110X are minimal (the [22Xi[122X-th diagonal entry of [10XB[110X
  is the determinant of the upper left [22Xi × i[122X submatrix of the permuted [3XA[103X, that
  is, its [22Xi[122X-th principal minor).[133X
  
  [33X[0;0YRemark: The matrix [10XB[110X is the transpose of the [22Xμ[122X-matrix in classical LLL, with
  its [22Xi[122X-th row multiplied by the [22Xi[122X-th principal minor [22Xd_i[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XA := [ [ 9, -3, 1, -2 ], [ -3, 3, 1, 1 ], [ 1, 1, 13, -2 ],[127X[104X
    [4X[25X>[125X [27X  [ -2, 1, -2, 5 ] ];;[127X[104X
    [4X[25Xgap>[125X [27XPermutedFractionFreeIntegerGaussPositiveDefinite(A);[127X[104X
    [4X[28X[ [ [ 3, 1, -3, 1 ], [ 0, 14, -3, -7 ], [ 0, 0, 81, 21 ], [128X[104X
    [4X[28X      [ 0, 0, 0, 900 ] ], (1,3,4,2) ][128X[104X
  [4X[32X[104X
  
  [1X3.4-3 InverseUnimodularMat[101X
  
  [33X[1;0Y[29X[2XInverseUnimodularMat[102X( [3XA[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Yan integer matrix[133X
  
  [33X[0;0YHere [3XA[103X must be a unimodular integer matrix (that is, a square integer matrix
  with  determinant  [22X± 1[122X). This function returns the inverse of [3XA[103X, which again
  is an integer matrix.[133X
  
  [33X[0;0YThis  is  a simplified variant of [2XInverseRatMat[102X ([14XEDIM: InverseRatMat[114X), based
  on a [22Xp[122X-adic lifting approach.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XA := RandomUnimodularMat(5);;[127X[104X
    [4X[25Xgap>[125X [27XA := RandomUnimodularMat(5);;[127X[104X
    [4X[25Xgap>[125X [27XA * InverseUnimodularMat(A);[127X[104X
    [4X[28X[ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [128X[104X
    [4X[28X  [ 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 1 ] ][128X[104X
  [4X[32X[104X
  
  [1X3.4-4 LLLTransformUnimodularGram[101X
  
  [33X[1;0Y[29X[2XLLLTransformUnimodularGram[102X( [3Xgr[103X ) [32X function[133X
  [6XReturns:[106X  [33X[0;10Ya unimodular integer matrix[133X
  
  [33X[0;0YHere  [3Xgr[103X  must  be  a  symmetric,  positive  definite integer matrix (a Gram
  matrix).  This  function returns a unimodular integer matrix [10XH[110X such that [10XH *
  gr * TransposedMat(H)[110X is the identity matrix.[133X
  
  [33X[0;0YThe  algorithm  is  similar  to  the  modular  variant  of the LLL-algorithm
  described in [Sto96], but here the main loop is parallelized.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XA := RandomUnimodularMat(5);;[127X[104X
    [4X[25Xgap>[125X [27XA := RandomUnimodularMat(5);;[127X[104X
    [4X[25Xgap>[125X [27Xgr := A * TransposedMat(A);;[127X[104X
    [4X[25Xgap>[125X [27Xh := LLLTransformUnimodularGram(gr);;[127X[104X
    [4X[25Xgap>[125X [27Xh * gr * TransposedMat(h);[127X[104X
    [4X[28X[ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [128X[104X
    [4X[28X  [ 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 1 ] ][128X[104X
  [4X[32X[104X
  
