home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / agclass.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  66.1 KB  |  2,033 lines
  1. #############################################################################
  2. ##
  3. #A  agclass.g                   GAP library                    J\"urgen Mnich
  4. ##
  5. #A  @(#)$Id: agclass.g,v 3.9 1993/01/15 12:06:27 fceller Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains functions for calculating classes of elements in
  10. ##  groups given by a pcp-presentation.
  11. ##
  12. #H  $Log: agclass.g,v $
  13. #H  Revision 3.9  1993/01/15  12:06:27  fceller
  14. #H  fixed ".domain" entry, but the 'ConjugacyClass' command
  15. #H  is still very strange (and maybe buggy) and should be
  16. #H  correct soon
  17. #H
  18. #H  Revision 3.8  1992/12/16  19:47:27  martin
  19. #H  replaced quoted record names with escaped ones
  20. #H
  21. #H  Revision 3.7  1992/05/12  11:45:54  jmnich
  22. #H  inserted missing 'return' statement.
  23. #H
  24. #H  Revision 3.6  1992/04/07  16:15:32  jmnich
  25. #H  adapted to changes in the finite field module
  26. #H
  27. #H  Revision 3.5  1992/04/01  06:50:42  jmnich
  28. #H  changed use of 'Exponents'
  29. #H
  30. #H  Revision 3.4  1992/03/17  12:31:20  jmnich
  31. #H  minor style changes, more bug fixes
  32. #H
  33. #H  Revision 3.3  1992/02/29  13:25:11  jmnich
  34. #H  general library review, some bug fixes
  35. #H
  36. #H  Revision 3.1  1992/02/12  15:37:22  martin
  37. #H  initial revision under RCS
  38. #H  
  39. ##
  40.  
  41.  
  42. #############################################################################
  43. ##
  44. #F  InfoAgClass1(...) . . . . . . . . . . . . . . . . . . package information
  45. #F  InfoAgClass2(...) . . . . . . . . . . . . . . . package debug information
  46. ##
  47. if not IsBound( InfoAgClass1 )  then  InfoAgClass1 := Ignore;  fi;
  48. if not IsBound( InfoAgClass2 )  then  InfoAgClass2 := Ignore;  fi;
  49.  
  50.  
  51. #############################################################################
  52. ##
  53. #V  Statistics Variables  . . . . . . . . . . . . . . . . . . . . . . . . . .
  54. ##
  55. ecs_ag_time            := 0;
  56. ecs_ag_centrality_cnt  := 0;
  57. ecs_ag_central_cnt     := [ 0, 0 ];
  58. ecs_ag_non_central_cnt := [ 0, 0, 0, 0, 0, 0 ];
  59. ncs_ag_time            := 0;
  60. ncs_ag_central_cnt     := [ 0 ];
  61. ncs_ag_non_central_cnt := [ 0, 0 ];
  62. scs_ag_time            := 0;
  63. scs_ag_central_cnt     := [ 0 ];
  64. scs_ag_non_central_cnt := [ 0, 0 ];
  65.  
  66.  
  67. #############################################################################
  68. ##
  69. #F  InHomSolutions( <oldmat>, <newmat>, <vec>, <field> )  . . . . . . . . . .
  70. ##
  71. ##  'InHomSolutions' solves the inhomogeneous system of linear equations that
  72. ##  is given by the concatenation of the first two arguments as the left side
  73. ##  and the third argument as the part of the right side belonging to the
  74. ##  second argument. The triangulized matrix (for iterative use) is returned
  75. ##  as well as the cardinality of the set of solutions.
  76. ##
  77. ##  returns
  78. ##
  79. ##      rec(
  80. ##          matrix      := [ [ <ffelem> ] ],
  81. ##          cardinality := <integer>
  82. ##      )
  83. ##
  84. InHomSolutions := function( A, B, b, field )
  85.     local   len, bad, pos, num, v, i;
  86.  
  87.     len := Length( B[1] ) + 1;
  88.     for i in [1..Length( b )] do  B[i][len] := b[i];  od;
  89.  
  90.     Append( A, B );
  91.     TriangulizeMat( A );
  92.  
  93.     bad := false;
  94.     pos := 0;
  95.     i   := 1;
  96.     for v in A do
  97.         while i <= len and v[i] = field.zero do  i   := i   + 1;  od;
  98.         if    i <= len then                      pos := pos + 1;  fi;
  99.         if    i  = len then                      bad := true;     fi;
  100.     od;
  101.  
  102.     if bad then  num := 0;
  103.     else         num := field.char ^ (len - 1 - pos);
  104.     fi;
  105.  
  106.     return rec(
  107.         matrix      := A,
  108.         cardinality := num
  109.     );
  110. end;
  111.  
  112.  
  113. #############################################################################
  114. ##
  115. #F  CommutatorGauss( <mat>, <field> ) . . . . . . . . . . . . . . . . . . . .
  116. ##
  117. ##  'CommutatorGauss' performs a gauss algorithm on the supplied finite field
  118. ##  matrix and extracts all information from the triangulized form which
  119. ##  may be interpreted as a special way of calculating centralizers and
  120. ##  commutator groups under certain conditions.
  121. ##
  122. ##  returns
  123. ##
  124. ##      rec(
  125. ##          commutator       := [ [ <integer> ] ],
  126. ##          commutatorFactor := [ [ <integer> ] ],
  127. ##          centralizer      := [ [ <integer> ] ],
  128. ##      )
  129. ##
  130. CommutatorGauss := function( A, field )
  131.     local   res, ndim, cdim, pos, v, i, j;
  132.  
  133.     cdim  := Length( A );
  134.     ndim  := Length( A[1] );
  135.  
  136.     for i in [ndim+1..ndim+cdim] do
  137.         for j in [1..cdim] do
  138.             A[j][i] := field.zero;
  139.         od;
  140.         A[i-ndim][i] := field.one;
  141.     od;
  142.  
  143. #T    as soon as martin fixes the 'Append' bug
  144. #T
  145. #T    local   c;
  146. #T
  147. #T    c     := [];
  148. #T    for i in [1..cdim] do
  149. #T        c[i] := field.zero;
  150. #T    od;
  151. #T    IsVector( c );
  152. #T
  153. #T
  154. #T    for i in [1..cdim] do
  155. #T        Append( A[i], c );
  156. #T        A[i][ndim+i] := field.one;
  157. #T    od;
  158.  
  159.     TriangulizeMat( A );
  160.  
  161.     res := rec(
  162.         matrix           := A,
  163.         commutator       := 0,
  164.         commutatorFactor := [1..ndim],
  165.         centralizer      := 0,
  166.         integers         := [],
  167.         dimensionN       := ndim,
  168.         dimensionC       := cdim
  169.     );
  170.  
  171.     pos := [];
  172.     i   := 1;
  173.     for v in A do
  174.         while v[i] = field.zero do  i := i + 1;  od;
  175.         Add( pos, i );
  176.         if i <= ndim then  res.commutator  := res.commutator  + 1;
  177.         else               res.centralizer := res.centralizer + 1;
  178.         fi;
  179.     od;
  180.     SubtractSet( res.commutatorFactor, pos );
  181.  
  182.     res.integers := IntegerTable( field );
  183.  
  184.     return res;
  185. end;
  186.  
  187.  
  188. #############################################################################
  189. ##
  190. #F  CorrectedStabilizer( <mat>, <N>, <S>, <M>, <h>, <n>, <hom> )  . . . . . .
  191. ##
  192. ##  'CorrectedStabilizer' solves a special problem that arises when the
  193. ##  classes of elements are calculated for a solvable group using linear
  194. ##  methods. For short, a stabilizer of an affine operation on a factor group
  195. ##  has to be modified (corrected) to eliminate a non-trivial operation in
  196. ##  the normal subgroup. Of course this must be possible by theory.
  197. ##
  198. ##  returns
  199. ##
  200. ##      <list>
  201. ##
  202. CorrectedStabilizer := function( A, N, S, M, h, n, hom )
  203.     local   integers, pos, v, res, sol, s, g, gens, len, map, z, i;
  204.  
  205.     InfoAgClass2( "#I  ecs: correcting stabilizer ", S, "\n" );
  206.  
  207.     if hom = false then  map := x -> x;
  208.     else                 map := x -> FactorAgWord( x, hom.source.identity );
  209.     fi;
  210.  
  211.     integers := IntegerTable( N.field );
  212.  
  213.     A    := AbstractBaseMat( M, A, N.field );
  214.     gens := A[1];
  215.     A    := A[2];
  216.  
  217.     pos := [];
  218.     i   := 1;
  219.     for v in A do
  220.         while v[i] = N.field.zero do  i := i + 1;  od;
  221.         Add( pos, i );
  222.     od;
  223.     len := Length( pos );
  224.  
  225.     res := [];
  226.     for s in S do
  227.         s   := map( s );
  228.         sol := Exponents( N, Comm( n, s ) * Comm( h, s ), N.field );
  229.         g   := N.identity;
  230.         for i in [1..len] do
  231.             z := LogVecFFE( sol, pos[i] );
  232.             if z <> false then
  233.                 g := g * gens[i] ^ integers[z+1];
  234.             fi;
  235.         od;
  236.         Add( res, s / g );
  237.     od;
  238.  
  239. #T    alternative avoiding AbstractBaseMat
  240. #T
  241. #T    gens := M;
  242. #T    len  := Length( gens );
  243. #T    res  := [];
  244. #T    for s in S do
  245. #T        s   := map( s );
  246. #T        sol := SolutionMat( A, Exponents( N, Comm( n, s ) * Comm( h, s ), N.field ) );
  247. #T        g   := N.identity;
  248. #T        for i in [1..len] do
  249. #T            z := LogVecFFE( sol, i );
  250. #T            if z <> false then
  251. #T                g := g * gens[i] ^ integers[z+1];
  252. #T            fi;
  253. #T        od;
  254. #T        Add( res, s / g );
  255. #T    od;
  256.  
  257.     InfoAgClass2( "#I  ecs: correcting stabilizer done\n" );
  258.  
  259.     return res;
  260. end;
  261.  
  262.  
  263. #############################################################################
  264. ##
  265. #F  AffineOrbitsAgGroup( <G>, <matrices>, <field> ) . . . . . . . . . . . . .
  266. ##
  267. ##  This function is one of those that are mainly used by the author's
  268. ##  ag-modules. It determines all the orbits of a soluble group acting affine
  269. ##  on a full vector space.
  270. ##
  271. ##  returns
  272. ##
  273. ##      rec(
  274. ##          representatives := <vectors>,
  275. ##          stabilizers     := <aggroups>,
  276. ##          orbits          := <integer>,
  277. ##          integers        := <list>
  278. ##      )
  279. ##
  280. AffineOrbitsAgGroup := function( G, mats, field )
  281.     local   space, reps, stabs, spsize, orb, vs, v, w, z, next, enum, num,
  282.             orbs, dim, i;
  283.  
  284.     reps   := [];
  285.     stabs  := [];
  286.     dim    := Length( mats[1] ) - 1;
  287.     vs     := RowSpace( dim, field );
  288.     spsize := Size( vs );
  289.     enum   := Enumeration( vs );
  290.  
  291.     orbs  := 0;
  292.     space := BlistList( [1..spsize], [] );
  293.     next  := Position( space, false );
  294.     while next <> false do
  295.         v   := MakeVecFFE( CoefficientsInt( enum.exponents, next-1 ), enum.field.one );
  296.  
  297. #T        testing the performance enhancement of 'CoefficientsInt'
  298. #T
  299. #T        v    := ShallowCopy( enum.exponents );
  300. #T        next := next - 1;
  301. #T        for i in Reversed( [1..dim] ) do
  302. #T            v[i] := next mod enum.exponents[i];
  303. #T            next := QuoInt( next, enum.exponents[i] );
  304. #T        od;
  305. #T        v := MakeVecFFE( v, enum.field.one );
  306.  
  307.         v[dim+1] := field.one;
  308.         orb := AgOrbitStabilizer( G, mats, v );
  309.         for w in orb.orbit do
  310. #T            num := 1;
  311. #T            for i in [1..enum.dimension] do
  312. #T                z := LogVecFFE( w, i );
  313. #T                if z <> false then
  314. #T                    num := num + enum.powers[i] * enum.integers[z+1];
  315. #T                fi;
  316. #T            od;
  317.             num := NumberVecFFE( w, enum.powers, enum.integers );
  318.             space[num] := true;
  319.         od;
  320.         orbs := orbs + 1;
  321.         reps[orbs]  := v;
  322.         stabs[orbs] := orb.stabilizer;
  323.         next := Position( space, false, next );
  324.     od;
  325.     return rec(
  326.         representatives := reps,
  327.         stabilizers     := stabs,
  328.         orbits          := orbs,
  329.         integers        := enum.integers
  330.     );
  331. end;
  332.  
  333.  
  334. #############################################################################
  335. ##
  336. #F  MinimalVectorAgOrbit( <G>, <matrices>, <vector>, <field> )  . . . . . . .
  337. ##
  338. ##  This function is more or less only used by the author's ag modules.
  339. ##  It determines the 'smallest' vector in the orbit under an affine action
  340. ##  of an aggroup on a vector space. This is necessary, when using linear
  341. ##  methods for soluble groups, to determine a canonical class representative
  342. ##  for the conjugacy classes.
  343. ##
  344. ##  returns
  345. ##
  346. ##      rec(
  347. ##          vector     := <vector>
  348. ##          operator   := <agword>,
  349. ##          stabilizer := <aggroup>
  350. ##      )
  351. ##
  352. MinimalVectorAgOrbit := function( group, mats, vec, field )
  353.     local   vs, orbit, torbit, stab, gen, orbpos, operator, pv, gn,
  354.             dim, enum, mvec, mnum, num, p, z, i, j, k;
  355.  
  356.     dim  := Length( mats[1] ) - 1;
  357.     vs   := RowSpace( dim, field );
  358.     enum := Enumeration( vs );
  359.  
  360.     orbit := [ vec ];
  361.     stab  := [];
  362.     pv    := [ 1 ];
  363.     gn    := [];
  364.  
  365.     for i in Reversed( [1..Length( group.generators )] ) do
  366.         gen    := group.generators[i];
  367.         orbpos := Position( orbit, vec * mats[i] );
  368.         if orbpos = false then
  369.             p := RelativeOrderAgWord( gen );
  370.             Add( pv, pv[Length( pv )] * p );
  371.             Add( gn, i );
  372.             torbit := ShallowCopy( orbit );
  373.             for j in [1..p-1] do
  374.                 for k in [1..Length( torbit )] do
  375.                     torbit[k] := torbit[k] * mats[i];
  376.                 od;
  377.                 Append( orbit, torbit );
  378.             od;
  379.         elif orbpos = 1 then   Add( stab, gen );
  380.         else
  381.             operator := group.identity;
  382.             orbpos   := orbpos - 1;
  383.             j        := Length( pv ) - 1;
  384.             while orbpos > 0 and j > 0 do
  385.                 operator := group.generators[gn[j]] ^ QuoInt( orbpos, pv[j] ) * operator;
  386.                 orbpos   := orbpos mod pv[j];
  387.                 j        := j - 1;
  388.             od;
  389.             Add( stab, gen / operator );
  390.         fi;
  391.     od;
  392.  
  393.     mvec := vec;
  394. #T    mnum := 1;
  395. #T    for i in [1..enum.dimension] do
  396. #T        z := LogVecFFE( vec, i );
  397. #T        if z <> false then
  398. #T            mnum := mnum + enum.powers[i] * enum.integers[z+1];
  399. #T        fi;
  400. #T    od;
  401.     mnum := NumberVecFFE( vec, enum.powers, enum.integers );
  402.  
  403.     orbpos := 1;
  404.     j      := Length( orbit );
  405.     while j > 1 and mnum > 1 do
  406. #T        num := 1;
  407. #T        for i in [1..enum.dimension] do
  408. #T            z := LogVecFFE( orbit[j], i );
  409. #T            if z <> false then
  410. #T                num := num + enum.powers[i] * enum.integers[z+1];
  411. #T            fi;
  412. #T        od;
  413.         num := NumberVecFFE( orbit[j], enum.powers, enum.integers );
  414.  
  415.         if num < mnum then
  416.             mnum   := num;
  417.             mvec   := orbit[j];
  418.             orbpos := j;
  419.         fi;
  420.         j := j - 1;
  421.     od;
  422.     operator := group.identity;
  423.     orbpos   := orbpos - 1;
  424.     j        := Length( pv ) - 1;
  425.     while orbpos > 0 and j > 0 do
  426.         operator := group.generators[gn[j]] ^ QuoInt( orbpos, pv[j] ) * operator;
  427.         orbpos   := orbpos mod pv[j];
  428.         j        := j - 1;
  429.     od;
  430.  
  431.     return rec(
  432.         vector     := mvec,
  433.         operator   := operator,
  434.         stabilizer := AgSubgroup( group, Reversed( stab ), false )
  435.     );
  436. end;
  437.  
  438.  
  439. #############################################################################
  440. ##
  441. #F  CentralCaseECSAgGroup( <G>, <N>, <C>, <M>, <h>, <hom> ) . . . . . . . . .
  442. ##
  443. ##  'CentralCaseECSAgGroup' implements the central part of the
  444. ##  algorithm for the calculation of conjugacy classes in soluble groups using
  445. ##  linear methods.
  446. ##  In the case where the elementary abelian normal subgroup is central in
  447. ##  a (somehow defined) group, the algorithm basically simplifies to solving
  448. ##  a system of linear equations.
  449. ##
  450. ##  returns
  451. ##
  452. ##      rec(
  453. ##          representatives := [ <agword> ],
  454. ##          centralizers    := [ [ <agword> ] ]
  455. ##      )
  456. ##
  457. CentralCaseECSAgGroup := function( G, N, C, M, h, hom )
  458.     local   h_C_comm, cg, rep2, cent2, ncgs, cigs, migs, tmp, v, z, g, i, j;
  459.  
  460.     InfoAgClass1( "#I  ecs: central case main dispatcher\n" );
  461.  
  462.     if not IsBound( N.field ) then
  463.         N.field := GF( RelativeOrderAgWord( N.generators[1] ) );
  464.     fi;
  465.  
  466.     if C.generators = [] then
  467.         InfoAgClass2( "#I  ecs: central_1\n" );
  468.         ecs_ag_central_cnt[1] := ecs_ag_central_cnt[1] + 1;
  469.  
  470.         h := FactorAgWord( h, hom.source.identity );
  471.         rep2  := Elements( N );
  472.         cent2 := ShallowCopy( rep2 );
  473.         for i in [1..Length( rep2 )] do
  474.             rep2[i]  := h * rep2[i];
  475.             cent2[i] := M;
  476.         od;
  477.     else
  478.         InfoAgClass2( "#I  ecs: central_2\n" );
  479.         ecs_ag_central_cnt[2] := ecs_ag_central_cnt[2] + 1;
  480.  
  481.         ncgs := Cgs( N );
  482.         cigs := ShallowCopy( Igs( C ) );
  483.         migs := Igs( M );
  484.  
  485.         h := FactorAgWord( h, hom.source.identity );
  486.         h_C_comm := [];
  487.         for i in [1..Length( cigs )] do
  488.             cigs[i] := FactorAgWord( cigs[i], hom.source.identity );
  489.             h_C_comm[i] := Exponents( N, Comm( h, cigs[i] ), N.field );
  490.         od;
  491.  
  492.         cg := CommutatorGauss( Copy( h_C_comm ), N.field );
  493.  
  494.         cg.commutatorFactor := AgSubgroup(
  495.             G,
  496.             Sublist( ncgs, cg.commutatorFactor ),
  497.             true
  498.         );
  499.  
  500.         tmp := [];
  501.         for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  502.             v := cg.matrix[i];
  503.             g := G.identity;
  504.             for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  505.                 z := LogVecFFE( v, j );
  506.                 if z <> false then
  507.                     g := g * cigs[j-cg.dimensionN] ^ cg.integers[z+1];
  508.                 fi;
  509.             od;
  510.             tmp[i-cg.commutator] := g;
  511.         od;
  512.         Append( tmp, migs );
  513.         cg.centralizer := AgSubgroup( G, tmp, false );
  514.  
  515.         rep2  := Elements( cg.commutatorFactor );
  516.         cent2 := ShallowCopy( rep2 );
  517.         for i in [1..Length( rep2 )] do
  518.             rep2[i]  := h * rep2[i];
  519.             cent2[i] := cg.centralizer;
  520.         od;
  521.     fi;
  522.  
  523.     return rec(
  524.         representatives := rep2,
  525.         centralizers    := cent2
  526.     );
  527. end;
  528.  
  529.  
  530. #############################################################################
  531. ##
  532. #F  GeneralCaseECSAgGroup( <G>, <N>, <C>, <M>, <h>, <hom> ) . . . . . . . . .
  533. ##
  534. ##  'GeneralCaseECSAgGroup' implements the non-central part of the
  535. ##  algorithm for the calculation of conjugacy classes in soluble groups using
  536. ##  linear methods.
  537. ##
  538. ##  returns
  539. ##
  540. ##      rec(
  541. ##          representatives := [ <agword> ],
  542. ##          centralizers    := [ <aggroup> ]
  543. ##      )
  544. ##
  545. GeneralCaseECSAgGroup := function( G, N, C, M, h, hom )
  546.     local   ncgs, cigs, migs, centrala, centralb, N_C_pow, h_M_comm, h_C_comm,
  547.             ndim, clen, mlen, N2, n2cgs, wn2cgs, n2dim, N2_C_pow, cg, cg2,
  548.             orb, rep2, cent2, tmp, v, z, g, i, j;
  549.  
  550.     InfoAgClass1( "#I  ecs: general case main dispatcher\n" );
  551.  
  552.     if not IsBound( N.field ) then
  553.         N.field := GF( RelativeOrderAgWord( N.generators[1] ) );
  554.     fi;
  555.  
  556.     ncgs := Cgs( N );
  557.     cigs := ShallowCopy( Igs( C ) );
  558.     migs := Igs( M );
  559.     ndim := Length( ncgs );
  560.     clen := Length( cigs );
  561.     mlen := Length( migs );
  562.  
  563.     centrala := true;
  564.     centralb := true;
  565.     N_C_pow  := [];
  566.     for i in [1..clen] do
  567.         cigs[i] := FactorAgWord( cigs[i], hom.source.identity );
  568.         N_C_pow[i] := [];
  569.         for j in [1..ndim] do
  570.             N_C_pow[i][j] := ncgs[j] ^ cigs[i];
  571.             if N_C_pow[i][j] <> ncgs[j] then  centrala := false;  fi;
  572.         od;
  573.     od;
  574.  
  575.     h_M_comm := [];
  576.     h := FactorAgWord( h, hom.source.identity );
  577.     for i in [1..mlen] do
  578.         h_M_comm[i] := Comm( h, migs[i] );
  579.         if h_M_comm[i] <> N.identity then  centralb := false;  fi;
  580.     od;
  581.  
  582.     if centrala and centralb then
  583.         InfoAgClass2( "#I  ecs: non_central_1 ->\n" );
  584.         ecs_ag_non_central_cnt[1] := ecs_ag_non_central_cnt[1] + 1;
  585.  
  586.         return CentralCaseECSAgGroup( G, N, C, M, h, hom );
  587.     fi;
  588.  
  589.     if centralb then
  590.         InfoAgClass2( "#I  ecs: non_central_2\n" );
  591.         ecs_ag_non_central_cnt[2] := ecs_ag_non_central_cnt[2] + 1;
  592.  
  593.         for i in [1..clen] do
  594.             tmp := N_C_pow[i];
  595.             for j in [1..ndim] do
  596.                 tmp[j] := Exponents( N, tmp[j], N.field );
  597.                 tmp[j][ndim+1] := N.field.zero;
  598.             od;
  599.             tmp[ndim+1] := Exponents( N, Comm( h, cigs[i] ), N.field );
  600.             tmp[ndim+1][ndim+1] := N.field.one;
  601.         od;
  602.         orb := AffineOrbitsAgGroup( C, N_C_pow, N.field );
  603.  
  604.         rep2  := orb.representatives;
  605.         cent2 := orb.stabilizers;
  606.         for i in [1..orb.orbits] do
  607.             g := h;
  608.             for j in [1..ndim] do
  609.                 z := LogVecFFE( rep2[i], j );
  610.                 if z <> false then
  611.                     g := g * ncgs[j] ^ orb.integers[z+1];
  612.                 fi;
  613.             od;
  614.             rep2[i] := g;
  615.             tmp := ShallowCopy( Igs( cent2[i] ) );
  616.             for j in [1..Length( tmp )] do
  617.                 tmp[j] := FactorAgWord( tmp[j], hom.source.identity );
  618.             od;
  619.             Append( tmp, migs );
  620.             cent2[i] := AgSubgroup( G, tmp, false );
  621.         od;
  622.  
  623.         return rec(
  624.             representatives := rep2,
  625.             centralizers    := cent2
  626.         );
  627.     fi;
  628.  
  629.     for i in [1..mlen] do
  630.         h_M_comm[i] := Exponents( N, h_M_comm[i], N.field );
  631.     od;
  632.  
  633.     if centrala then
  634.         InfoAgClass2( "#I  ecs: non_central_3\n" );
  635.         ecs_ag_non_central_cnt[3] := ecs_ag_non_central_cnt[3] + 1;
  636.  
  637.         h_C_comm := [];
  638.         for i in [1..clen] do
  639.             h_C_comm[i] := Exponents( N, Comm( h, cigs[i] ), N.field );
  640.         od;
  641.         Append( cigs, migs );
  642.         Append( h_C_comm, h_M_comm );
  643.  
  644.         cg := CommutatorGauss( Copy( h_C_comm ), N.field );
  645.         cg.commutatorFactor := AgSubgroup(
  646.             G,
  647.             Sublist( ncgs, cg.commutatorFactor ),
  648.             true
  649.         );
  650.  
  651.         tmp := [];
  652.         for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  653.             v := cg.matrix[i];
  654.             g := G.identity;
  655.             for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  656.                 z := LogVecFFE( v, j );
  657.                 if z <> false then
  658.                     g := g * cigs[j-cg.dimensionN] ^ cg.integers[z+1];
  659.                 fi;
  660.             od;
  661.             tmp[i-cg.commutator] := g;
  662.         od;
  663.         cg.centralizer := AgSubgroup( G, tmp, false );
  664.  
  665.         rep2  := Elements( cg.commutatorFactor );
  666.         cent2 := ShallowCopy( rep2 );
  667.         for i in [1..Length( rep2 )] do
  668.             rep2[i]  := h * rep2[i];
  669.             cent2[i] := cg.centralizer;
  670.         od;
  671.  
  672.         return rec(
  673.             representatives := rep2,
  674.             centralizers    := cent2
  675.         );
  676.     fi;
  677.  
  678.     cg := CommutatorGauss( Copy( h_M_comm ), N.field );
  679.  
  680.     if cg.commutatorFactor = [] then
  681.         InfoAgClass2( "#I  ecs: non_central_4\n" );
  682.         ecs_ag_non_central_cnt[4] := ecs_ag_non_central_cnt[4] + 1;
  683.  
  684.         rep2  := [ h ];
  685.         cent2 := [
  686.             AgSubgroup(
  687.                 G,
  688.                 CorrectedStabilizer( h_M_comm, N, Igs( C ), Igs( M ), h, N.identity, hom ),
  689.                 false
  690.             )
  691.         ];
  692.     else
  693.         tmp := [];
  694.         for i in [1..cg.commutator] do
  695.             v := cg.matrix[i];
  696.             g := G.identity;
  697.             for j in [1..cg.dimensionN] do
  698.                 z := LogVecFFE( v, j );
  699.                 if z <> false then
  700.                     g := g * ncgs[j] ^ cg.integers[z+1];
  701.                 fi;
  702.             od;
  703.             tmp[i] := g;
  704.         od;
  705.  
  706.         # don't bound cg.commutator to tmp here. this field is re-used later.
  707.  
  708.         N2       := N mod AgSubgroup( G, tmp, false );
  709.         N2.field := N.field;
  710.         n2cgs    := N2.generators;
  711.         n2dim    := Length( n2cgs );
  712.         tmp      := DepthAgWord( ncgs[1] ) - 1;
  713.         wn2cgs   := List( n2cgs, x -> DepthAgWord( x ) - tmp );
  714.         centrala := true;
  715.  
  716.         N2_C_pow := [];
  717.         for i in [1..clen] do
  718.             N2_C_pow[i] := [];
  719.             for j in [1..n2dim] do
  720.                 N2_C_pow[i][j] := N_C_pow[i][wn2cgs[j]];
  721.                 if centrala
  722.                  and not N2_C_pow[i][j] / n2cgs[j] in N2.factorDen then
  723.                     centrala := false;
  724.                 fi;
  725.             od;
  726.         od;
  727.  
  728.         if centrala then
  729.             InfoAgClass2( "#I  ecs: non_central_5\n" );
  730.             ecs_ag_non_central_cnt[5] := ecs_ag_non_central_cnt[5] + 1;
  731.  
  732.             h_C_comm := [];
  733.             for i in [1..clen] do
  734.                 h_C_comm[i] := Exponents( N2, Comm( h, cigs[i] ), N2.field );
  735.             od;
  736.  
  737.             cg2 := CommutatorGauss( Copy( h_C_comm ), N.field );
  738.  
  739.             tmp := [];
  740.             for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  741.                 v := cg.matrix[i];
  742.                 g := G.identity;
  743.                 for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  744.                     z := LogVecFFE( v, j );
  745.                     if z <> false then
  746.                         g := g * migs[j-cg.dimensionN] ^ cg.integers[z+1];
  747.                     fi;
  748.                 od;
  749.                 tmp[i-cg.commutator] := g;
  750.             od;
  751.             cg.centralizer := tmp;
  752.  
  753.             tmp := [];
  754.             for i in [cg2.commutator+1..cg2.commutator+cg2.centralizer] do
  755.                 v := cg2.matrix[i];
  756.                 g := C.identity;
  757.                 for j in [cg2.dimensionN+1..cg2.dimensionN+cg2.dimensionC] do
  758.                     z := LogVecFFE( v, j );
  759.                     if z <> false then
  760.                         g := g * C.generators[j-cg2.dimensionN] ^ cg2.integers[z+1];
  761.                     fi;
  762.                 od;
  763.                 tmp[i-cg2.commutator] := g;
  764.             od;
  765.             cg2.centralizer      := tmp;
  766.             cg2.commutatorFactor := Sublist( n2cgs, cg2.commutatorFactor );
  767.  
  768.             rep2  := Elements( AgSubgroup( N, cg2.commutatorFactor, true ) );
  769.             cent2 := ShallowCopy( rep2 );
  770.             for i in [1..Length( rep2 )] do
  771.                 cent2[i] := CorrectedStabilizer( h_M_comm, N, cg2.centralizer, Igs( M ), h, rep2[i], hom );
  772.                 Append( cent2[i], cg.centralizer );
  773.                 cent2[i] := AgSubgroup( G, cent2[i], false );
  774.                 rep2[i]  := h * rep2[i];
  775.             od;
  776.         else
  777.             InfoAgClass2( "#I  ecs: non_central_6\n" );
  778.             ecs_ag_non_central_cnt[6] := ecs_ag_non_central_cnt[6] + 1;
  779.  
  780.             for i in [1..clen] do
  781.                 tmp := N2_C_pow[i];
  782.                 for j in [1..n2dim] do
  783.                     tmp[j] := Exponents( N2, tmp[j], N2.field );
  784.                     tmp[j][n2dim+1] := N.field.zero;
  785.                 od;
  786.                 tmp[n2dim+1] := Exponents( N2, Comm( h, cigs[i] ), N2.field );
  787.                 tmp[n2dim+1][n2dim+1] := N.field.one;
  788.             od;
  789.  
  790.             tmp := [];
  791.             for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  792.                 v := cg.matrix[i];
  793.                 g := G.identity;
  794.                 for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  795.                     z := LogVecFFE( v, j );
  796.                     if z <> false then
  797.                         g := g * migs[j-cg.dimensionN] ^ cg.integers[z+1];
  798.                     fi;
  799.                 od;
  800.                 tmp[i-cg.commutator] := g;
  801.             od;
  802.             cg.centralizer := tmp;
  803.  
  804.             orb := AffineOrbitsAgGroup( C, N2_C_pow, N2.field );
  805.  
  806.             rep2  := orb.representatives;
  807.             cent2 := orb.stabilizers;
  808.             for i in [1..orb.orbits] do
  809.                 g := G.identity;
  810.                 for j in [1..n2dim] do
  811.                     z := LogVecFFE( rep2[i], j );
  812.                     if z <> false then
  813.                         g := g * n2cgs[j] ^ orb.integers[z+1];
  814.                     fi;
  815.                 od;
  816.                 tmp := CorrectedStabilizer( h_M_comm, N, Igs( cent2[i] ), Igs( M ), h, g, hom );
  817.                 Append( tmp, cg.centralizer );
  818.                 cent2[i] := AgSubgroup( G, tmp, false );
  819.                 rep2[i]  := h * g;
  820.             od;
  821.         fi;
  822.     fi;
  823.  
  824.     return rec(
  825.         representatives := rep2,
  826.         centralizers    := cent2
  827.     );
  828. end;
  829.  
  830.  
  831. #############################################################################
  832. ##
  833. #F  MainEntryECSAgGroup( <G>, <U>, <H>, <ser>, <skip> ) . . . . . . . . . . .
  834. #F  . . . . . . . . . . . . main entry point for the conjugacy class function
  835. ##
  836. ##  This is main routine for the computation of conjugacy classes in soluble
  837. ##  groups. It handles all initialization, takes care of the inductive nature
  838. ##  of the algorithm and dispatches to the case-handling functions as
  839. ##  far as centrality is obvious.
  840. ##
  841. ##  returns
  842. ##
  843. ##      rec(
  844. ##          representatives := [ <agword> ],
  845. ##          centralizers    := [ <aggroup> ]
  846. ##      )
  847. ##  or
  848. ##      rec(
  849. ##          representatives         := [ <agword> ],
  850. ##          centralizers            := [ <aggroup> ]
  851. ##          naturalHomomorphisms    := [ <aghom> ],
  852. ##          domains                 := [ <aggroup> ],
  853. ##          nextStep                := <integer>,
  854. ##          elementaryAbelianSeries := [ <aggroup> ]
  855. ##      )
  856. ##
  857. ##  A short explanation of the arguments for those who decide to go through
  858. ##  this function rather than using the supplied top-level funtion.
  859. ##  By the way, greetings to H.U.   8-) 
  860. ##
  861. ##  G           the supergroup
  862. ##  U           the subgroup of G acting on H
  863. ##  H           a normal composition subgroup of G, an element of elabser
  864. ##  elabser     an elementary abelian composition series of G containing H
  865. ##  skip        the number of steps to skip at the end of the algorithm
  866. ##
  867. ##  the last argument is basically implemented to provide programs such as
  868. ##  the computation of the number of conjugacy classes with an easy way to
  869. ##  compute the classes of the whole group modulo the last elementary abelian
  870. ##  normal subgroup. If this feature is used, i.e. 'skip' is positive, the
  871. ##  second form of the return record is returned otherwise always a return
  872. ##  record of the first type is returned.
  873. ##
  874. ##  Remark: the conditions that are implicitly given by the above description
  875. ##          of the arguments is not tested by the function.
  876. ##          So you hacker, be aware !
  877. ##
  878. MainEntryECSAgGroup := function( G, U, H, elabser, skip )
  879.     local   rep, cent, step, repnum, newclasses, newrep, newcent,
  880.             fachom, facU, facN, facC, fach, fhom, tmpU, idx;
  881.  
  882.     if U.generators = [] then
  883.         rep  := Elements( H );
  884.         cent := List( rep, x -> U );
  885.         return rec(
  886.             representatives := rep,
  887.             centralizers    := cent
  888.         );
  889.     fi;
  890.  
  891.     if H.generators = [] then
  892.         return rec(
  893.             representatives := [ H.identity ],
  894.             centralizers    := [ U ]
  895.         );
  896.     fi;
  897.  
  898.     ecs_ag_time            := Runtime();
  899.     ecs_ag_centrality_cnt  := 0;
  900.     ecs_ag_central_cnt     := [ 0, 0 ];
  901.     ecs_ag_non_central_cnt := [ 0, 0, 0, 0, 0, 0 ];
  902.  
  903.     idx := 1;
  904.     while elabser[idx] <> H do                idx := idx + 1;  od;
  905.     while IsSubgroup( elabser[idx+1], U ) do  idx := idx + 1;  od;
  906.  
  907.     if idx <> 1 then
  908.         elabser := Sublist( elabser, [idx..Length( elabser )] );
  909.     fi;
  910.     fachom := HomomorphismsSeries( G, elabser );
  911.  
  912.  
  913.     # initialize the inductive algorithm
  914.  
  915.     tmpU := Image( fachom[1], U );
  916.     rep  := Elements( Image( fachom[1], H ) );
  917.     cent := List( rep, x -> tmpU );
  918.  
  919.     # prepare the involved data for each following step
  920.  
  921.     tmpU := U;
  922.     U    := [];
  923.     U[Length( elabser )] := tmpU;
  924.     for step in Reversed( [2..Length( elabser )] ) do
  925.         tmpU := Image( fachom[step], tmpU );
  926.         U[step-1] := tmpU;
  927.     od;
  928.  
  929.     # loop over the elementary abelian series
  930.  
  931.     for step in [2..Length( elabser )-skip] do
  932.  
  933.         InfoAgClass1( "#I  ecs: step ", step, " / (", Length( elabser ), "-", skip, ")\n" );
  934.  
  935.         # get the appropriate new data
  936.  
  937.         fhom := fachom[step];
  938.         facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  939.         facU := Intersection( U[step], facN );
  940.  
  941.         # initialize data for this step
  942.  
  943.         newrep  := [];
  944.         newcent := [];
  945.  
  946.         if IsCentral( fhom.source, facN ) then
  947.             for repnum in [1..Length( rep )] do
  948.                 InfoAgClass2( "#I  ecs: coset ", repnum, " / ", Length( rep ), "\n" );
  949.                 ecs_ag_centrality_cnt := ecs_ag_centrality_cnt + 1;
  950.                 newclasses := CentralCaseECSAgGroup(
  951.                                 fhom.source, facN, cent[repnum], facU, rep[repnum], fhom );
  952.                 Append( newrep,  newclasses.representatives );
  953.                 Append( newcent, newclasses.centralizers );
  954.             od;
  955.         else
  956.             for repnum in [1..Length( rep )] do
  957.                 InfoAgClass2( "#I  ecs: coset ", repnum, " / ", Length( rep ), "\n" );
  958.                 newclasses := GeneralCaseECSAgGroup(
  959.                                 fhom.source, facN, cent[repnum], facU, rep[repnum], fhom );
  960.                 Append( newrep,  newclasses.representatives );
  961.                 Append( newcent, newclasses.centralizers );
  962.             od;
  963.         fi;
  964.  
  965.         rep  := newrep;
  966.         cent := newcent;
  967.     od;
  968.  
  969.     ecs_ag_time := Runtime() - ecs_ag_time;
  970.     if skip = 0 then
  971.         return rec(
  972.             representatives         := rep,
  973.             centralizers            := cent
  974.         );
  975.     else
  976.         return rec(
  977.             representatives         := rep,
  978.             centralizers            := cent,
  979.             naturalHomomorphisms    := fachom,
  980.             domains                 := U,
  981.             nextStep                := Length( elabser ) - skip + 1,
  982.             elementaryAbelianSeries := elabser
  983.         );
  984.     fi;
  985. end;
  986.  
  987.  
  988. #############################################################################
  989. ##
  990. #F  AgGroupOps.ConjugacyClasses( [<U>, ]<obj> ) . . . . . . . . . . . . . . .
  991. #F  . . . . . . . . . . . compute conjugacyclasses of elements in an ag-group
  992. ##
  993. ##  This function determines all conjugacyclasses of elements of an ag-group
  994. ##  under the operation of an other ag-group which may be passed as an
  995. ##  optional first argument. The function implements an algorithm that uses
  996. ##  linear methods for calculations in a soluble group.
  997. ##  If <obj> is a list of elements instead of an ag group, the classes of the
  998. ##  elements, i.e. especially their canonical representative is determined.
  999. ##
  1000. ##  returns
  1001. ##
  1002. ##      <list>
  1003. ##
  1004. AgGroupOps.ConjugacyClasses := function( arg )
  1005.     local   G, H, U, HU, T, elabser, natisom, classes, res, i;
  1006.  
  1007.     if    Length( arg ) = 1 then  H := arg[1]; U := H;
  1008.     elif  Length( arg ) = 2 then  H := arg[2]; U := arg[1];
  1009.     else
  1010.         Error( "usage: ConjugacyClasses( [<U>, ]<obj> )" );
  1011.     fi;
  1012.  
  1013.     G := Parent( U );
  1014.     T := TrivialSubgroup( G );
  1015.  
  1016.     if IsList( H ) then
  1017.         if not IsElementaryAbelianAgSeries( G ) then
  1018.             elabser := ElementaryAbelianSeries( G );
  1019.             natisom := IsomorphismAgGroup( elabser );
  1020.             elabser := ElementaryAbelianSeries( natisom.range );
  1021.             res     := MainEntryECAgWords( natisom.range,
  1022.                         Image( natisom, U ), List( H, x -> Image( natisom, x ) ), elabser );
  1023.  
  1024.             # now construct the conjugacy classes with additional entries
  1025.             # from the data returned in 'res'.
  1026.  
  1027.             classes := ShallowCopy( res.representatives );
  1028.  
  1029.             for i in [1..Length( classes )] do
  1030.                 classes[i] := ConjugacyClass( U,
  1031.                  PreImagesRepresentative( natisom, res.representatives[i] ) );
  1032.                 classes[i].element :=
  1033.                  PreImagesRepresentative( natisom, res.elements[i] );
  1034.                 classes[i].conjugand :=
  1035.                  PreImagesRepresentative( natisom, res.conjugands[i] );
  1036.                 classes[i].centralizer :=
  1037.                  PreImage( natisom, res.centralizers[i] );
  1038.             od;
  1039.         else
  1040.             elabser := ElementaryAbelianSeries( G );
  1041.             res     := MainEntryECAgWords( G, U, H, elabser );
  1042.  
  1043.             classes := ShallowCopy( res.representatives );
  1044.  
  1045.             for i in [1..Length( classes )] do
  1046.                 classes[i] := ConjugacyClass( U, res.representatives[i] );
  1047.                 classes[i].element := res.elements[i];
  1048.                 classes[i].conjugand := res.conjugands[i];
  1049.                 classes[i].centralizer := res.centralizers[i];
  1050.             od;
  1051.         fi;
  1052.     elif IsNormal( G, H ) then
  1053.         if IsElementaryAbelianAgSeries( G )
  1054.          and IsElementAgSeries( H ) then
  1055.             elabser := ElementaryAbelianSeries( [ G, H, T ] );
  1056.             res     := MainEntryECSAgGroup( G, U, H, elabser, 0 );
  1057.  
  1058.             classes := ShallowCopy( res.representatives );
  1059.  
  1060.             for i in [1..Length( classes )] do
  1061.                 classes[i] := ConjugacyClass( U, res.representatives[i] );
  1062.                 classes[i].centralizer := res.centralizers[i];
  1063.             od;
  1064.         else
  1065.             elabser := ElementaryAbelianSeries( [ G, H, T ] );
  1066.             natisom := IsomorphismAgGroup( elabser );
  1067.             elabser := ElementaryAbelianSeries( natisom.range );
  1068.             res     := MainEntryECSAgGroup( natisom.range,
  1069.                         Image( natisom, U ), Image( natisom, H ), elabser, 0 );
  1070.  
  1071.             classes := ShallowCopy( res.representatives );
  1072.  
  1073.             for i in [1..Length( classes )] do
  1074.                 classes[i] := ConjugacyClass( U,
  1075.                  PreImagesRepresentative( natisom, res.representatives[i] ) );
  1076.                 classes[i].centralizer :=
  1077.                  PreImage( natisom, res.centralizers[i] );
  1078.             od;
  1079.         fi;
  1080.     elif IsNormal( U, H ) then
  1081.         HU := SumAgGroup( H, U );
  1082.         elabser := ElementaryAbelianSeries( [ HU, H, T ] );
  1083.         natisom := IsomorphismAgGroup( elabser );
  1084.         elabser := ElementaryAbelianSeries( natisom.range );
  1085.         res     := MainEntryECSAgGroup( natisom.range,
  1086.                     Image( natisom, U ), Image( natisom, H ), elabser, 0 );
  1087.  
  1088.         classes := ShallowCopy( res.representatives );
  1089.  
  1090.         for i in [1..Length( classes )] do
  1091.             classes[i] := ConjugacyClass( U,
  1092.              PreImagesRepresentative( natisom, res.representatives[i] ) );
  1093.             classes[i].centralizer :=
  1094.              PreImage( natisom, res.centralizers[i] );
  1095.         od;
  1096.     else
  1097.         Error( "sorry, U must operate on H" );
  1098.     fi;
  1099.  
  1100.     return classes;
  1101. end;
  1102.  
  1103.  
  1104. #############################################################################
  1105. ##
  1106. #F  FusionsECSAgGroup( <G>, <U>, <H>, <ser>, <split> )  . . . . . . . . . . .
  1107. #F  . . . . . . . . . . . . . . . . . . compute conjugacy classes and fusions
  1108. ##
  1109. ##
  1110. ##  returns
  1111. ##
  1112. ##      rec(
  1113. ##          representatives         := [ <agword> ],
  1114. ##          centralizers            := [ <aggroup> ]
  1115. ##          naturalHomomorphisms    := [ <aghom> ],
  1116. ##          domains                 := [ <aggroup> ],
  1117. ##          elementaryAbelianSeries := [ <aggroup> ]
  1118. ##          representativeTree      := [ <agword> ],
  1119. ##          centralizerTree         := [ <aggroup> ],
  1120. ##          fusionTree              := [ <integer> ]
  1121. ##      )
  1122. ##
  1123. ##  A short explanation of the arguments.
  1124. ##
  1125. ##  G           the supergroup
  1126. ##  U           the subgroup of G acting on H
  1127. ##  H           a normal composition subgroup of G, an element of elabser
  1128. ##  elabser     an elementary abelian composition series of G containing H
  1129. ##  split       steps in which a check for a complete split is performed
  1130. ##              only classes that completely split are considered in further
  1131. ##              computations
  1132. ##
  1133. ##
  1134. ##  Remark: the conditions that are implicitly given by the above description
  1135. ##          of the arguments is not tested by the function.
  1136. ##
  1137. FusionsECSAgGroup := function( G, U, H, elabser, split )
  1138.     local   rep, cent, step, repnum, newclasses, newrep, newcent, fachom,
  1139.             facU, facN, facC, fach, fhom, tmpU, idx, rtree, ctree, ftree;
  1140.  
  1141.  
  1142.     if U.generators = [] then
  1143.         rep  := Elements( H );
  1144.         cent := List( rep, x -> U );
  1145.         return rec(
  1146.             representatives := rep,
  1147.             centralizers    := cent
  1148.         );
  1149.     fi;
  1150.  
  1151.     if H.generators = [] then
  1152.         return rec(
  1153.             representatives := [ H.identity ],
  1154.             centralizers    := [ U ]
  1155.         );
  1156.     fi;
  1157.  
  1158.     ecs_ag_time            := Runtime();
  1159.     ecs_ag_centrality_cnt  := 0;
  1160.     ecs_ag_central_cnt     := [ 0, 0 ];
  1161.     ecs_ag_non_central_cnt := [ 0, 0, 0, 0, 0, 0 ];
  1162.  
  1163.     idx := 1;
  1164.     while elabser[idx] <> H do                idx := idx + 1;  od;
  1165.     while IsSubgroup( elabser[idx+1], U ) do  idx := idx + 1;  od;
  1166.  
  1167.     if idx <> 1 then
  1168.         elabser := Sublist( elabser, [idx..Length( elabser )] );
  1169.     fi;
  1170.     fachom := HomomorphismsSeries( G, elabser );
  1171.  
  1172.     if split <> [] then  split := split + 1 - idx; fi;
  1173.  
  1174.  
  1175.     # initialize the inductive algorithm
  1176.  
  1177.     tmpU := Image( fachom[1], U );
  1178.     rep  := Elements( Image( fachom[1], H ) );
  1179.     cent := List( rep, x -> tmpU );
  1180.  
  1181.     rtree := [ rep ];
  1182.     ctree := [ cent ];
  1183.     ftree := [ [] ];
  1184.  
  1185.     # prepare the involved data for each following step
  1186.  
  1187.     tmpU := U;
  1188.     U    := [];
  1189.     U[Length( elabser )] := tmpU;
  1190.     for step in Reversed( [2..Length( elabser )] ) do
  1191.         tmpU := Image( fachom[step], tmpU );
  1192.         U[step-1] := tmpU;
  1193.     od;
  1194.  
  1195.     # loop over the elementary abelian series
  1196.  
  1197.     for step in [2..Length( elabser )] do
  1198.  
  1199.         InfoAgClass1( "#I  becs: step ", step, " / ", Length( elabser ), "\n" );
  1200.  
  1201.         # get the appropriate new data
  1202.  
  1203.         fhom := fachom[step];
  1204.         facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  1205.         facU := Intersection( U[step], facN );
  1206.  
  1207.         # initialize data for this step
  1208.  
  1209.         newrep      := [];
  1210.         newcent     := [];
  1211.         ftree[step] := [];
  1212.  
  1213.         if IsCentral( fhom.source, facN ) then
  1214.             for repnum in [1..Length( rep )] do
  1215.                 InfoAgClass2( "#I  becs: coset ", repnum, " / ", Length( rep ), "\n" );
  1216.                 ecs_ag_centrality_cnt := ecs_ag_centrality_cnt + 1;
  1217.                 newclasses := CentralCaseECSAgGroup(
  1218.                                 fhom.source, facN, cent[repnum], facU, rep[repnum], fhom );
  1219.                 if not step in split
  1220.                   or Length( newclasses.representatives ) = Size( facN ) then
  1221.                     Append( newrep,  newclasses.representatives );
  1222.                     Append( newcent, newclasses.centralizers );
  1223.  
  1224.                     Append( ftree[step],
  1225.                             List( newclasses.representatives, x -> repnum ) );
  1226.                 fi;
  1227.             od;
  1228.         else
  1229.             for repnum in [1..Length( rep )] do
  1230.                 InfoAgClass2( "#I  becs: coset ", repnum, " / ", Length( rep ), "\n" );
  1231.                 newclasses := GeneralCaseECSAgGroup(
  1232.                                 fhom.source, facN, cent[repnum], facU, rep[repnum], fhom );
  1233.                 if not step in split
  1234.                   or Length( newclasses.representatives ) = Size( facN ) then
  1235.                     Append( newrep,  newclasses.representatives );
  1236.                     Append( newcent, newclasses.centralizers );
  1237.  
  1238.                     Append( ftree[step],
  1239.                             List( newclasses.representatives, x -> repnum ) );
  1240.                 fi;
  1241.             od;
  1242.         fi;
  1243.  
  1244.         rep  := newrep;
  1245.         cent := newcent;
  1246.  
  1247.         rtree[step] := newrep;
  1248.         ctree[step] := newcent;
  1249.     od;
  1250.  
  1251.     ecs_ag_time := Runtime() - ecs_ag_time;
  1252.     return rec(
  1253.         representatives         := rep,
  1254.         centralizers            := cent,
  1255.         naturalHomomorphisms    := fachom,
  1256.         domains                 := U,
  1257.         elementaryAbelianSeries := elabser,
  1258.         representativeTree      := rtree,
  1259.         centralizerTree         := ctree,
  1260.         fusionTree              := ftree
  1261.     );
  1262. end;
  1263.  
  1264.  
  1265. #############################################################################
  1266. ##
  1267. #F  Fusions2ECSAgGroup( <G>, <U>, <H>, <ser>, <idx>, <reps>, <cents>, <split> )
  1268. #F  . . . . . . . . .  compute conjugacy classes and fusions from lower level
  1269. ##
  1270. ##
  1271. ##  returns
  1272. ##
  1273. ##      rec(
  1274. ##          representatives         := [ <agword> ],
  1275. ##          centralizers            := [ <aggroup> ]
  1276. ##          naturalHomomorphisms    := [ <aghom> ],
  1277. ##          domains                 := [ <aggroup> ],
  1278. ##          elementaryAbelianSeries := [ <aggroup> ]
  1279. ##          representativeTree      := [ <agword> ],
  1280. ##          centralizerTree         := [ <aggroup> ],
  1281. ##          fusionTree              := [ <integer> ]
  1282. ##      )
  1283. ##
  1284. ##  A short explanation of the arguments.
  1285. ##
  1286. ##  G           the supergroup
  1287. ##  U           the subgroup of G acting on H
  1288. ##  H           a normal composition subgroup of G, an element of elabser
  1289. ##  elabser     an elementary abelian composition series of G containing H
  1290. ##  idx         start index to begin computation
  1291. ##  rep         list of representatives so far
  1292. ##  cent        list of centralizers (as groups !) relative to rep
  1293. ##  split       steps in which a check for a complete split is performed
  1294. ##              only classes that completely split are considered in further
  1295. ##              computations
  1296. ##
  1297. ##
  1298. ##  Remark: the conditions that are implicitly given by the above description
  1299. ##          of the arguments is not tested by the function.
  1300. ##
  1301. Fusions2ECSAgGroup := function( G, U, H, elabser, idx, rep, cent, split )
  1302.     local   step, repnum, newclasses, newrep, newcent, fachom,
  1303.             facU, facN, facC, fach, fhom, tmpU, rtree, ctree, ftree;
  1304.  
  1305.  
  1306.     if U.generators = [] then
  1307.         cent := List( rep, x -> U );
  1308.         return rec(
  1309.             representatives := rep,
  1310.             centralizers    := cent
  1311.         );
  1312.     fi;
  1313.  
  1314.     if H.generators = [] then
  1315.         return rec(
  1316.             representatives := [ H.identity ],
  1317.             centralizers    := [ U ]
  1318.         );
  1319.     fi;
  1320.  
  1321.     ecs_ag_time            := Runtime();
  1322.     ecs_ag_centrality_cnt  := 0;
  1323.     ecs_ag_central_cnt     := [ 0, 0 ];
  1324.     ecs_ag_non_central_cnt := [ 0, 0, 0, 0, 0, 0 ];
  1325.  
  1326.     if idx <> 1 then
  1327.         elabser := Sublist( elabser, [idx..Length( elabser )] );
  1328.     fi;
  1329.     fachom := HomomorphismsSeries( G, elabser );
  1330.  
  1331.     if split <> [] then  split := split + 1 - idx; fi;
  1332.  
  1333.  
  1334.     # initialize the inductive algorithm
  1335.  
  1336.     Apply(  rep, x -> Image( fachom[1], x ) );
  1337.     Apply( cent, x -> Image( fachom[1], x ) );
  1338.  
  1339.     rtree := [ rep ];
  1340.     ctree := [ cent ];
  1341.     ftree := [ [] ];
  1342.  
  1343.     # prepare the involved data for each following step
  1344.  
  1345.     tmpU := U;
  1346.     U    := [];
  1347.     U[Length( elabser )] := tmpU;
  1348.     for step in Reversed( [2..Length( elabser )] ) do
  1349.         tmpU := Image( fachom[step], tmpU );
  1350.         U[step-1] := tmpU;
  1351.     od;
  1352.  
  1353.     # loop over the elementary abelian series
  1354.  
  1355.     for step in [2..Length( elabser )] do
  1356.  
  1357.         InfoAgClass1( "#I  becs2: step ", step, " / ", Length( elabser ), "\n" );
  1358.  
  1359.         # get the appropriate new data
  1360.  
  1361.         fhom := fachom[step];
  1362.         facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  1363.         facU := Intersection( U[step], facN );
  1364.  
  1365.         # initialize data for this step
  1366.  
  1367.         newrep      := [];
  1368.         newcent     := [];
  1369.         ftree[step] := [];
  1370.  
  1371.         if IsCentral( fhom.source, facN ) then
  1372.             for repnum in [1..Length( rep )] do
  1373.                 InfoAgClass2( "#I  becs2: coset ", repnum, " / ", Length( rep ), "\n" );
  1374.                 ecs_ag_centrality_cnt := ecs_ag_centrality_cnt + 1;
  1375.                 newclasses := CentralCaseECSAgGroup(
  1376.                                 fhom.source, facN, cent[repnum], facU, rep[repnum], fhom );
  1377.                 if not step in split
  1378.                   or Length( newclasses.representatives ) = Size( facN ) then
  1379.                     Append( newrep,  newclasses.representatives );
  1380.                     Append( newcent, newclasses.centralizers );
  1381.  
  1382.                     Append( ftree[step],
  1383.                             List( newclasses.representatives, x -> repnum ) );
  1384.                 fi;
  1385.             od;
  1386.         else
  1387.             for repnum in [1..Length( rep )] do
  1388.                 InfoAgClass2( "#I  becs2: coset ", repnum, " / ", Length( rep ), "\n" );
  1389.                 newclasses := GeneralCaseECSAgGroup(
  1390.                                 fhom.source, facN, cent[repnum], facU, rep[repnum], fhom );
  1391.                 if not step in split
  1392.                   or Length( newclasses.representatives ) = Size( facN ) then
  1393.                     Append( newrep,  newclasses.representatives );
  1394.                     Append( newcent, newclasses.centralizers );
  1395.  
  1396.                     Append( ftree[step],
  1397.                             List( newclasses.representatives, x -> repnum ) );
  1398.                 fi;
  1399.             od;
  1400.         fi;
  1401.  
  1402.         rep  := newrep;
  1403.         cent := newcent;
  1404.  
  1405.         rtree[step] := newrep;
  1406.         ctree[step] := newcent;
  1407.     od;
  1408.  
  1409.     ecs_ag_time := Runtime() - ecs_ag_time;
  1410.     return rec(
  1411.         representatives         := rep,
  1412.         centralizers            := cent,
  1413.         naturalHomomorphisms    := fachom,
  1414.         domains                 := U,
  1415.         elementaryAbelianSeries := elabser,
  1416.         representativeTree      := rtree,
  1417.         centralizerTree         := ctree,
  1418.         fusionTree              := ftree
  1419.     );
  1420. end;
  1421.  
  1422.  
  1423. #############################################################################
  1424. ##
  1425. #F  SubEntryNECSAgGroup( <G>, <N>, <C>, <M>, <h>, <cl>, <hom> ) . . . . . . .
  1426. ##
  1427. ##  This  is  the basic subroutine of the function for calculating the number
  1428. ##  of conjugacy classes in a  soluble group.  Its main duty is to solve some
  1429. ##  inhomogeneous  systems  of linear equations and determine the cardinality
  1430. ##  of the corresponding set of solutions.
  1431. ##
  1432. ##  returns
  1433. ##
  1434. ##      <integer>
  1435. ##
  1436. SubEntryNECSAgGroup := function( G, N, C, M, h, cl, hom )
  1437.     local   num, ncgs, cigs, migs, ndim, clen, mlen, central, h_M_comm,
  1438.             N2, n2cgs, N2_c_comm, cg, sol, repnum, rep, tmp, v, g, z, i, j;
  1439.  
  1440.     if not IsBound( N.field ) then
  1441.         N.field := GF( RelativeOrderAgWord( N.generators[1] ) );
  1442.     fi;
  1443.  
  1444.     num  := 0;
  1445.  
  1446.     ncgs := Cgs( N );
  1447.     cigs := ShallowCopy( Igs( C ) );
  1448.     migs := Igs( M );
  1449.     ndim := Length( ncgs );
  1450.     clen := Length( cigs );
  1451.     mlen := Length( migs );
  1452.  
  1453.     central  := true;
  1454.     h_M_comm := [];
  1455.     h := FactorAgWord( h, hom.source.identity );
  1456.     for i in [1..mlen] do
  1457.         h_M_comm[i] := Comm( h, migs[i] );
  1458.         if h_M_comm[i] <> N.identity then  central := false;  fi;
  1459.     od;
  1460.  
  1461.     if central then
  1462.         ncs_ag_central_cnt[1] := ncs_ag_central_cnt[1] + 1;
  1463.  
  1464.         N2    := N;
  1465.         n2cgs := ncgs;
  1466.     else
  1467.         for i in [1..mlen] do
  1468.             h_M_comm[i] := Exponents( N, h_M_comm[i], N.field );
  1469.         od;
  1470.         cg := CommutatorGauss( Copy( h_M_comm ), N.field );
  1471.         if cg.commutatorFactor = [] then
  1472.             ncs_ag_non_central_cnt[1] := ncs_ag_non_central_cnt[1] + 1;
  1473.  
  1474.             return 1;
  1475.         else
  1476.             ncs_ag_non_central_cnt[2] := ncs_ag_non_central_cnt[2] + 1;
  1477.  
  1478.             tmp := [];
  1479.             for i in [1..cg.commutator] do
  1480.                 v := cg.matrix[i];
  1481.                 g := G.identity;
  1482.                 for j in [1..cg.dimensionN] do
  1483.                     z := LogVecFFE( v, j );
  1484.                     if z <> false then
  1485.                         g := g * ncgs[j] ^ cg.integers[z+1];
  1486.                     fi;
  1487.                 od;
  1488.                 tmp[i] := g;
  1489.             od;
  1490.             cg.commutator := tmp;
  1491.  
  1492.             N2       := N mod AgSubgroup( G, cg.commutator, true );
  1493.             n2cgs    := N2.generators;
  1494.             N2.field := N.field;
  1495.         fi;
  1496.     fi;
  1497.  
  1498.     for repnum in [1..Length( cl.representatives )] do
  1499.         rep := FactorAgWord( cl.representatives[repnum], hom.source.identity );
  1500.         N2_c_comm := [];
  1501.         for i in [1..Length( n2cgs )] do
  1502.             N2_c_comm[i] := Exponents( N2, Comm( n2cgs[i], rep ), N2.field );
  1503.         od;
  1504.  
  1505.         sol := SolutionMat( N2_c_comm, Exponents( N2, Comm( h, rep ), N2.field ) );
  1506.  
  1507.         if sol <> false then
  1508.             num := num + cl.classlengths[repnum]
  1509.                 * Size( RowSpace( NullspaceMat( N2_c_comm ), N2.field, 0 * sol ) );
  1510.         fi;
  1511.     od;
  1512.  
  1513.     return num / Size( C );
  1514. end;
  1515.  
  1516.  
  1517. #############################################################################
  1518. ##
  1519. #F  MainEntryNECSAgGroup( <aggroup>, <aggroup>, <aggroup>, [ <aggroup> ] )  .
  1520. ##
  1521. ##  This is the main function of the algorithm for calculating the number of
  1522. ##  conjugacy classes in a soluble group. Due to the used algorithm, this
  1523. ##  function makes calls to 'MainEntryECSAgGroup' described above for calculating
  1524. ##  the conjugacy classes of the found centralizers in the last factorgroup and
  1525. ##  then calls its only special subroutine to determine, following the lemma
  1526. ##  of cauchy/frobenius, the number of conjugacy classes that are found in each
  1527. ##  coset.
  1528. ##
  1529. ##  returns
  1530. ##
  1531. ##      <integer>
  1532. ##
  1533. MainEntryNECSAgGroup := function( G, U, H, elabser )
  1534.     local   num, cl, cl2, ec, step, rep, cent, fhom, facN, facU, h, ser, cnum,
  1535.             grp, isom, order, tmp, tmp2, i;
  1536.  
  1537.     if U.generators = [] then  return Size( H );  fi;
  1538.     if H.generators = [] then  return         1;  fi;
  1539.  
  1540.     ncs_ag_time            := Runtime();
  1541.     ncs_ag_central_cnt     := [ 0 ];
  1542.     ncs_ag_non_central_cnt := [ 0, 0 ];
  1543.  
  1544.     # get the conjugacy classes for the biggest factorgroup
  1545.  
  1546.     cl  := MainEntryECSAgGroup( G, U, H, elabser, 1 );
  1547.     ec  := Equivalenceclasses(  cl.centralizers,
  1548.                                 function ( x, y ) return x = y; end );
  1549.     Apply( ec.classes, x -> [ x[1], Length( x ) ] );
  1550.  
  1551.     rep  := cl.representatives;
  1552.     step := cl.nextStep;
  1553.     fhom := cl.naturalHomomorphisms[step];
  1554.     facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  1555.     facU := Intersection( cl.domains[step], facN );
  1556.     ser  := cl.elementaryAbelianSeries;
  1557.  
  1558.     # compute elementary abelian series for factor group
  1559.  
  1560.     elabser := [];
  1561.     for i in [1..Length( ser )-1] do  Add( elabser, Image( fhom, ser[i] ) );  od;
  1562.  
  1563.     # initialize the inductive algorithm
  1564.  
  1565.     num := 0;
  1566.  
  1567.     # loop over all conjugacy classes of the factor group
  1568.  
  1569.     for cnum in [1..Length( ec.classes )] do
  1570.         cent := ec.classes[cnum][1];
  1571.  
  1572.         if fhom.range = cent then
  1573.             order := Size( fhom.range );
  1574.             cl2 := rec(
  1575.                 representatives := cl.representatives,
  1576.                 classlengths    := List( cl.centralizers, x -> order / Size( x ) )
  1577.             );
  1578.         else
  1579.             tmp  := TrivialSubgroup( fhom.range );
  1580.             ser  := [];
  1581.             for grp in elabser do
  1582.                 tmp2 := Intersection( grp, cent );
  1583.                 if tmp <> tmp2 then
  1584.                     Add( ser, tmp2 );
  1585.                     tmp := tmp2;
  1586.                 fi;
  1587.             od;
  1588.             if ser = [] then ser := [ tmp ]; fi;
  1589.  
  1590.             isom  := IsomorphismAgGroup( ser );
  1591.             ser   := ElementaryAbelianSeries( isom.range );
  1592.             cl2   := MainEntryECSAgGroup( isom.range, isom.range, isom.range, ser, 0 );
  1593.             order := Size( isom.range );
  1594.             cl2 := rec(
  1595.                 representatives := List( cl2.representatives, x -> PreImagesRepresentative( isom, x ) ),
  1596.                 classlengths := List( cl2.centralizers, x -> order / Size( x ) )
  1597.             );
  1598.         fi;
  1599.         for i in [1..ec.classes[cnum][2]] do
  1600.             h   := rep[ec.indices[cnum][i]];
  1601.             num := num + SubEntryNECSAgGroup( fhom.source, facN, cent, facU, h, cl2, fhom );
  1602.         od;
  1603.     od;
  1604.     ncs_ag_time := Runtime() - ncs_ag_time;
  1605.     return num;
  1606. end;
  1607.  
  1608.  
  1609. #############################################################################
  1610. ##
  1611. #F  SubEntrySECSAgGroup( <G>, <N>, <C>, <M>, <h>, <latt>, <mat>, <integer>, <hom> )
  1612. ##
  1613. ##  This is the basic subroutine for the function that calculates the types
  1614. ##  of conjugacy classes in a soluble group. It uses the subgroup lattice of the
  1615. ##  operating centralizer to determine the transitive constituents of the
  1616. ##  operation, which itself is computed via inhomogeneous systems of linear
  1617. ##  equations. From this information the desired results are computed.
  1618. ##
  1619. ##  returns
  1620. ##
  1621. ##      rec(
  1622. ##          classlengths := [ <integer> ],
  1623. ##          occurences   := [ <integer> ]
  1624. ##      )
  1625. ##
  1626. SubEntrySECSAgGroup := function( G, N, C, M, h, latt, bs, opord, hom )
  1627.     local   ncgs, cigs, migs, ndim, clen, mlen, v, g, z,
  1628.             central, h_M_comm, N2, n2cgs, cg, facord, bsvec, cllen,
  1629.             clnum, group, ugens, gennum, res, N2_c_comm, tmp, i, j;
  1630.  
  1631.     if not IsBound( N.field ) then
  1632.         N.field := GF( RelativeOrderAgWord( N.generators[1] ) );
  1633.     fi;
  1634.  
  1635.     ncgs := Cgs( N );
  1636.     cigs := ShallowCopy( Igs( C ) );
  1637.     migs := Igs( M );
  1638.     ndim := Length( ncgs );
  1639.     clen := Length( cigs );
  1640.     mlen := Length( migs );
  1641.  
  1642.     central  := true;
  1643.     h_M_comm := [];
  1644.     h := FactorAgWord( h, hom.source.identity );
  1645.     for i in [1..mlen] do
  1646.         h_M_comm[i] := Comm( h, migs[i] );
  1647.         if h_M_comm[i] <> N.identity then  central := false;  fi;
  1648.     od;
  1649.  
  1650.     if central then
  1651.         scs_ag_central_cnt[1] := scs_ag_central_cnt[1] + 1;
  1652.  
  1653.         N2     := N;
  1654.         n2cgs  := ncgs;
  1655.         facord := Size( N2 );
  1656.     else
  1657.         for i in [1..mlen] do
  1658.             h_M_comm[i] := Exponents( N, h_M_comm[i], N.field );
  1659.         od;
  1660.         cg := CommutatorGauss( Copy( h_M_comm ), N.field );
  1661.         if cg.commutatorFactor = [] then
  1662.             scs_ag_non_central_cnt[1] := scs_ag_non_central_cnt[1] + 1;
  1663.  
  1664.             return rec(
  1665.                 classlengths := [ opord / Size( latt.group ) ],
  1666.                 occurences   := [ 1 ]
  1667.             );
  1668.         else
  1669.             scs_ag_non_central_cnt[2] := scs_ag_non_central_cnt[2] + 1;
  1670.  
  1671.             tmp := [];
  1672.             for i in [1..cg.commutator] do
  1673.                 v := cg.matrix[i];
  1674.                 g := G.identity;
  1675.                 for j in [1..cg.dimensionN] do
  1676.                     z := LogVecFFE( v, j );
  1677.                     if z <> false then
  1678.                         g := g * ncgs[j] ^ cg.integers[z+1];
  1679.                     fi;
  1680.                 od;
  1681.                 tmp[i] := g;
  1682.             od;
  1683.             cg.commutator := tmp;
  1684.  
  1685.             N2       := N mod AgSubgroup( G, cg.commutator, true );
  1686.             n2cgs    := N2.generators;
  1687.             N2.field := N.field;
  1688.             facord   := Size( N2.factorNum ) / Size( N2.factorDen );
  1689.         fi;
  1690.     fi;
  1691.  
  1692.     bsvec  := [ facord ];
  1693.     cllen  := [ opord / facord ];
  1694.     for clnum in [2..Length( latt.classes )] do
  1695.         group := latt.classes[clnum].representative;
  1696.         ugens := group.generators;
  1697.         Apply( ugens, x -> FactorAgWord( x, hom.source.identity ) );
  1698.         cllen[clnum] := opord / (Size( group ) * facord);
  1699.         gennum := 1;
  1700.         res    := rec( matrix := [] );
  1701.         repeat
  1702.             N2_c_comm := [];
  1703.             for i in [1..Length( n2cgs )] do
  1704.                 N2_c_comm[i] := Exponents( N2, Comm( n2cgs[i], ugens[gennum] ), N2.field );
  1705.             od;
  1706.             res := InHomSolutions( res.matrix, N2_c_comm,
  1707.                     Exponents( N2, Comm( h, ugens[gennum] ), N2.field ), N2.field );
  1708.             gennum := gennum + 1;
  1709.         until gennum > Length( ugens ) or res.cardinality = 0;
  1710.         bsvec[clnum] := res.cardinality;
  1711.     od;
  1712.     for i in Reversed( [1..Length( bsvec )-1] ) do
  1713.         for j in [i+1..Length( bsvec )] do
  1714.             bsvec[i] := bsvec[i] - bsvec[j] * bs[j][i];
  1715.         od;
  1716.         bsvec[i] := bsvec[i] / bs[i][i];
  1717.     od;
  1718.     return rec(
  1719.         classlengths := cllen,
  1720.         occurences   := bsvec
  1721.     );
  1722. end;
  1723.  
  1724.  
  1725. #############################################################################
  1726. ##
  1727. #F  MainEntrySECSAgGroup( <aggroup>, <aggroup>, <aggroup>, [ <aggroup> ] )  .
  1728. ##
  1729. ##  This is the main function for the calculation of the types of
  1730. ##  conjugacy classes in a soluble group. This function makes calls to
  1731. ##  'MainEntryECSAgGroup' to determine the classes of elements up to the last
  1732. ##  factorgroup and then calculates for each centralizer the whole lattice
  1733. ##  of subgroups and the burnside matrix using the author's lattice module.
  1734. ##  This information is then passed to the subgoup 'SubEntrySECSAgGroup' which finally
  1735. ##  determines the desired result.
  1736. ##
  1737. ##  returns
  1738. ##
  1739. ##      rec(
  1740. ##          classlengths := [ <integer> ],
  1741. ##          occurences   := [ <integer> ]
  1742. ##      )
  1743. ##
  1744. MainEntrySECSAgGroup := function( G, U, H, elabser )
  1745.     local   cllen, clcnt, cl, ec, step, rep, cent, h, facN, facU,
  1746.             ser, cnum, fhom, isom, uord, latt, bs, layer, crep, res, tmp, tmp2, i;
  1747.  
  1748.     if U.generators = [] then
  1749.         return rec(
  1750.             classlengths := [ 1 ],
  1751.             occurences   := [ Size( H ) ]
  1752.         );
  1753.     fi;
  1754.  
  1755.     if H.generators = [] then
  1756.         return rec(
  1757.             classlengths := [ 1 ],
  1758.             occurences   := [ 1 ]
  1759.         );
  1760.     fi;
  1761.  
  1762.     scs_ag_time            := Runtime();
  1763.     scs_ag_central_cnt     := [ 0 ];
  1764.     scs_ag_non_central_cnt := [ 0, 0 ];
  1765.  
  1766.     # get the conjugacy classes for the biggest factorgroup
  1767.  
  1768.     cl  := MainEntryECSAgGroup( G, U, H, elabser, 1 );
  1769.     ec  := Equivalenceclasses(  cl.centralizers,
  1770.                                 function ( x, y ) return x = y; end );
  1771.     Apply( ec.classes, x -> [ x[1], Length( x ) ] );
  1772.  
  1773.     rep  := cl.representatives;
  1774.     step := cl.nextStep;
  1775.     fhom := cl.naturalHomomorphisms[step];
  1776.     facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  1777.     facU := Intersection( cl.domains[step], facN );
  1778.     ser  := cl.elementaryAbelianSeries;
  1779.     uord := Size( U );
  1780.  
  1781.     # compute elementary abelian series for factor group
  1782.  
  1783.     elabser := [];
  1784.     for i in [1..Length( ser )-1] do  Add( elabser, Image( fhom, ser[i] ) );  od;
  1785.  
  1786.     # initialize the inductive algorithm
  1787.  
  1788.     cllen := [];
  1789.     clcnt := [];
  1790.  
  1791.     # loop over all conjugacy classes of the factor group
  1792.  
  1793.     for cnum in [1..Length( ec.classes )] do
  1794.         cent := ec.classes[cnum][1];
  1795.         isom := NaturalHomomorphism( cent, cent / TrivialSubgroup( cent ) );
  1796.         latt := Lattice( isom.range );
  1797.         Sort( latt.classes,
  1798.                 function ( x, y )
  1799.                     return x.representative.size < y.representative.size;
  1800.                 end );
  1801.         bs := TableOfMarks( latt );
  1802.         Apply( latt.classes, x -> ConjugacyClassSubgroups( isom.source,
  1803.                 PreImage( isom, x.representative ) ) );
  1804.  
  1805.         for i in [1..ec.classes[cnum][2]] do
  1806.             h   := rep[ec.indices[cnum][i]];
  1807.             res := SubEntrySECSAgGroup( fhom.source, facN, cent, facU, h, latt, bs, uord, fhom );
  1808.             Append( cllen, res.classlengths );
  1809.             Append( clcnt, res.occurences );
  1810.         od;
  1811.     od;
  1812.  
  1813.     # now sort out those entries that do not occur really, i.e. which have
  1814.     # an occurence count of zero
  1815.  
  1816.     tmp   := cllen;
  1817.     tmp2  := clcnt;
  1818.     cllen := [];
  1819.     clcnt := [];
  1820.     for i in [1..Length( tmp )] do
  1821.         if tmp2[i] <> 0 then
  1822.             Add( cllen, tmp[i] );
  1823.             Add( clcnt, tmp2[i] );
  1824.         fi;
  1825.     od;
  1826.  
  1827.     scs_ag_time := Runtime() - scs_ag_time;
  1828.     return rec(
  1829.         classlengths := cllen,
  1830.         occurences   := clcnt
  1831.     );
  1832. end;
  1833.  
  1834.  
  1835. #############################################################################
  1836. ##
  1837. #F  NumberConjugacyClasses( [<U>, ]<H> )  . . . . . . . . . . . . . . . . . .
  1838. #F  . . . . .  compute the number of conjugacy classes of elements in a group
  1839. ##
  1840. NumberConjugacyClasses := function( arg )
  1841.     if Length( arg ) = 1 then
  1842.         return arg[1].operations.NumberConjugacyClasses( arg[1] );
  1843.     elif Length( arg ) = 2 then
  1844.         return arg[1].operations.NumberConjugacyClasses( arg[1], arg[2] );
  1845.     else
  1846.         Error( "usage: NumberConjugacyClasses( [<U>, ]<H> )" );
  1847.     fi;
  1848. end;
  1849.  
  1850.  
  1851. #############################################################################
  1852. ##
  1853. #F  AgGroupOps.NumberConjugacyClasses( [<U>, ]<H> ) . . . . . . . . . . . . .
  1854. #F  . . .  compute the number of conjugacy classes of elements in an ag-group
  1855. ##
  1856. ##  This  function  determines the number of conjugacy classes of elements in
  1857. ##  an  ag-group using linear methods.  First the conjugacy classes of the group
  1858. ##  modulo  the  last  normal  subgroup  in  an elementary abelian series are
  1859. ##  computed  using  'MainEntryECSAgGroup'.   Then  for  each coset and corresponding
  1860. ##  centralizer  the  number  of classes in that coset under the operation of
  1861. ##  the  centralizer is determined using the lemma of cauchy/frobenius.  This
  1862. ##  may,  for  soluble  groups,  efficiently be done by solving inhomogeneous
  1863. ##  systems  of linear equations and by determining the conjugacy classes of the
  1864. ##  centralizer.
  1865. ##
  1866. ##  returns
  1867. ##
  1868. ##      <integer>
  1869. ##
  1870. AgGroupOps.NumberConjugacyClasses := function( arg )
  1871.     local   usage, G, H, U, HU, T, elabser, natisom, number;
  1872.  
  1873.     if    Length( arg ) = 1 then  H := arg[1]; U := H;
  1874.     elif  Length( arg ) = 2 then  H := arg[2]; U := arg[1];
  1875.     else
  1876.         Error( "usage: NumberConjugacyClasses( [<U>, ]<H> )" );
  1877.     fi;
  1878.  
  1879.     G := Parent( H );
  1880.     T := TrivialSubgroup( G );
  1881.  
  1882.     if IsNormal( G, H ) then
  1883.         if IsElementaryAbelianAgSeries( G )
  1884.           and IsElementAgSeries( H ) then
  1885.             elabser := ElementaryAbelianSeries( [ G, H, T ] );
  1886.             number  := MainEntryNECSAgGroup( G, U, H, elabser );
  1887.         else
  1888.             elabser := ElementaryAbelianSeries( [ G, H, T ] );
  1889.             natisom := IsomorphismAgGroup( elabser );
  1890.             elabser := ElementaryAbelianSeries( natisom.range );
  1891.             number  := MainEntryNECSAgGroup(
  1892.                 natisom.range, Image( natisom, U ), Image( natisom, H ),
  1893.                 elabser );
  1894.         fi;
  1895.     elif IsNormal( U, H ) then
  1896.         HU := SumAgGroup( H, U );
  1897.         elabser := ElementaryAbelianSeries( [ HU, H, T ] );
  1898.         natisom := IsomorphismAgGroup( elabser );
  1899.         elabser := ElementaryAbelianSeries( natisom.range );
  1900.         number  := MainEntryNECSAgGroup(
  1901.             natisom.range, Image( natisom, U ), Image( natisom, H ), elabser );
  1902.     else
  1903.         Error( "sorry, U must operate on H" );
  1904.     fi;
  1905.  
  1906.     return number;
  1907. end;
  1908.  
  1909.  
  1910. #############################################################################
  1911. ##
  1912. #F  StructureConjugacyClasses( [<U>, ]<H> ) . . . . . . . . . . . . . . . . .
  1913. #F  . . . . compute the structure of conjugacy classes of elements in a group
  1914. ##
  1915. StructureConjugacyClasses := function( arg )
  1916.     if Length( arg ) = 1 then
  1917.         return arg[1].operations.StructureConjugacyClasses( arg[1] );
  1918.     elif Length( arg ) = 2 then
  1919.         return arg[1].operations.StructureConjugacyClasses( arg[1], arg[2] );
  1920.     else
  1921.         Error( "usage: StructureConjugacyClasses( [<U>, ]<H> )" );
  1922.     fi;
  1923. end;
  1924.  
  1925.  
  1926. #############################################################################
  1927. ##
  1928. #F  AgGroupOps.StructureConjugacyClasses( [<U>, ]<H> )  . . . . . . . . . . .
  1929. #F  . determine the structure of conjugacy classes of elements in an ag-group
  1930. ##
  1931. ##  This  function  determines the structure of conjugacy classes of elements
  1932. ##  in  an  ag-group  using  linear methods.  First the conjugacy classes of the
  1933. ##  group modulo the last normal subgroup in an elementary abelian series are
  1934. ##  computed  using  'MainEntryECSAgGroup'.   Then  for  each coset and corresponding
  1935. ##  centralizer the structure of classes in that coset under the operation of
  1936. ##  the   centralizer   is  determined  using  the  burnside  matrix  of  the
  1937. ##  centralizer.
  1938. ##
  1939. ##  returns
  1940. ##
  1941. ##      rec(
  1942. ##          classlengths := [ <integer> ],
  1943. ##          occurences   := [ <integer> ]
  1944. ##      )
  1945. ##
  1946. AgGroupOps.StructureConjugacyClasses := function( arg )
  1947.     local   usage, G, H, U, HU, T, elabser, natisom, strct;
  1948.  
  1949.     if    Length( arg ) = 1 then  H := arg[1]; U := H;
  1950.     elif  Length( arg ) = 2 then  H := arg[2]; U := arg[1];
  1951.     else
  1952.         Error( "usage: StructureConjugacyClasses( [<U>, ]<H> )" );
  1953.     fi;
  1954.  
  1955.     G := Parent( H );
  1956.     T := TrivialSubgroup( G );
  1957.  
  1958.     if IsNormal( G, H ) then
  1959.         if IsElementaryAbelianAgSeries( G )
  1960.           and IsElementAgSeries( H ) then
  1961.             elabser := ElementaryAbelianSeries( [ G, H, T ] );
  1962.             strct   := MainEntrySECSAgGroup( G, U, H, elabser );
  1963.         else
  1964.             elabser := ElementaryAbelianSeries( [ G, H, T ] );
  1965.             natisom := IsomorphismAgGroup( elabser );
  1966.             elabser := ElementaryAbelianSeries( natisom.range );
  1967.             strct   := MainEntrySECSAgGroup(
  1968.                 natisom.range, Image( natisom, U ), Image( natisom, H ),
  1969.                 elabser );
  1970.         fi;
  1971.     elif IsNormal( U, H ) then
  1972.         HU := SumAgGroup( H, U );
  1973.         elabser := ElementaryAbelianSeries( [ HU, H, T ] );
  1974.         natisom := IsomorphismAgGroup( elabser );
  1975.         elabser := ElementaryAbelianSeries( natisom.range );
  1976.         strct   := MainEntrySECSAgGroup(
  1977.             natisom.range, Image( natisom, U ), Image( natisom, H ), elabser );
  1978.     else
  1979.         Error( "sorry, U must operate on H" );
  1980.     fi;
  1981.  
  1982.     return strct;
  1983. end;
  1984.  
  1985.  
  1986. AgGroupOps.ConjugacyClass := function( G, g )
  1987.    local c;
  1988.  
  1989.    c := GroupOps.ConjugacyClass( G, g );
  1990.    c.operations := ConjugacyClassAgGroupOps;
  1991.    return c;
  1992. end;
  1993.  
  1994.  
  1995. ConjugacyClassAgGroupOps := Copy( ConjugacyClassGroupOps );
  1996.  
  1997.  
  1998. ConjugacyClassAgGroupOps.\= := function( C, D )
  1999.     local   isEql;
  2000.  
  2001.     if     IsRec( C ) and IsBound( C.isConjugacyClass )
  2002.        and IsRec( D ) and IsBound( D.isConjugacyClass )
  2003.        and C.group = D.group
  2004.     then
  2005.         isEql := C.group.operations.ConjugacyTest( C.group,
  2006.                     [ C.representative, D.representative ] ) <> false;
  2007.     else
  2008.         isEql := DomainOps.\=( C, D );
  2009.    fi;
  2010.    return isEql;
  2011. end;
  2012.  
  2013.  
  2014. ConjugacyClassAgGroupOps.\in := function( g, C )
  2015.     return  C.group.operations.ConjugacyTest( C.group, [g,C.representative] )
  2016.            <>
  2017.             false;
  2018. end;
  2019.  
  2020.  
  2021. #############################################################################
  2022. ##
  2023. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  2024. ##
  2025. ##  Local Variables:
  2026. ##  mode:               outline
  2027. ##  outline-regexp:     "#F\\|#V\\|#E"
  2028. ##  fill-column:        73
  2029. ##  fill-prefix:        "##  "
  2030. ##  eval:               (hide-body)
  2031. ##  End:
  2032. ##
  2033.