home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / agcent.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  47.0 KB  |  1,528 lines
  1. #############################################################################
  2. ##
  3. #A  agcent.g                    GAP library                    J\"urgen Mnich
  4. ##
  5. #A  @(#)$Id: agcent.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 centralizers in groups given
  10. ##  by a pcp-presentation and related problems.
  11. ##
  12. #H  $Log: agcent.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/10/28  14:04:00  fceller
  19. #H  fixed a bug 'MainEntryCentAgGroup'
  20. #H
  21. #H  Revision 3.7  1992/04/07  16:15:32  jmnich
  22. #H  adapted to changes in the finite field module
  23. #H
  24. #H  Revision 3.6  1992/04/03  09:11:20  jmnich
  25. #H  added 'field' to factorgroups
  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  InfoAgCent1(...)  . . . . . . . . . . . . . . . . . . package information
  45. #F  InfoAgCent2(...)  . . . . . . . . . . . . . . . package debug information
  46. ##
  47. if not IsBound( InfoAgCent1 )  then  InfoAgCent1 := Ignore;  fi;
  48. if not IsBound( InfoAgCent2 )  then  InfoAgCent2 := Ignore;  fi;
  49.  
  50.  
  51. #############################################################################
  52. ##
  53. #V  Statistics Variables  . . . . . . . . . . . . . . . . . . . . . . . . . .
  54. ##
  55. cs_ag_time             := 0;
  56. cs_ag_trivial_cnt      := [ 0, 0 ];
  57. cs_ag_general_cnt      := [ 0 ];
  58. ec_ag_time             := 0;
  59. ec_ag_central_cnt      := [ 0, 0 ];
  60. ec_ag_non_central_cnt  := [ 0, 0, 0, 0, 0, 0 ];
  61. cen_ag_time            := 0;
  62. cen_ag_central_cnt     := [ 0, 0 ];
  63. cen_ag_non_central_cnt := [ 0, 0, 0, 0, 0, 0 ];
  64.  
  65.  
  66. #############################################################################
  67. ##
  68. #F  MainEntryCSAgGroup( <G>, <U>, <H>, <elabser> )  . . . . . . . . . . . . .
  69. ##
  70. ##  This  is the main routine for the computation of a chiefseries in soluble
  71. ##  groups.  (However there are no subroutines.  Nearly.  8-) )
  72. ##  The  author's  MeatAxe module is used to decompose the elementary abelian
  73. ##  factors of the given group.
  74. ##
  75. ##  returns
  76. ##
  77. ##      <list>
  78. ##
  79. ##  Again,  for  those  who wish to use this function directly, without going
  80. ##  through the top-level function, here is what you need:
  81. ##
  82. ##  G           the parentgroup
  83. ##  U           the subgroup of G acting on H
  84. ##  H           a normal composition subgroup of G, an element of elabser
  85. ##  elabser     an elementary abelian composition series of G containing H
  86. ##
  87. MainEntryCSAgGroup := function( G, U, H, elabser )
  88.     local   series, subser, fachom, tmpU, facU, facN, fhom, module,
  89.             idx, step, ints, nigs, ndim, tmp, v, g, z, i, j;
  90.  
  91.     if U.generators = [] then  return CompositionSeries( H );  fi;
  92.     if H.generators = [] then  return [ H ];                   fi;
  93.  
  94.     cs_ag_time        := Runtime();
  95.     cs_ag_trivial_cnt := [ 0, 0 ];
  96.     cs_ag_general_cnt := [ 0 ];
  97.  
  98.     idx := 1;
  99.     while elabser[idx] <> H do  idx := idx + 1;  od;
  100.  
  101.     if idx <> 1 then
  102.         elabser := Sublist( elabser, [idx..Length( elabser )] );
  103.     fi;
  104.     fachom := HomomorphismsSeries( G, elabser );
  105.  
  106.  
  107.     # initialize the inductive algorithm
  108.  
  109.     series := [];
  110.  
  111.     # prepare the involved data for each following step
  112.  
  113.     tmpU := U;
  114.     U    := [];
  115.     U[Length( elabser )] := tmpU;
  116.     for step in Reversed( [2..Length( elabser )] ) do
  117.         tmpU := Image( fachom[step], tmpU );
  118.         U[step-1] := tmpU;
  119.     od;
  120.  
  121.     # loop over the elementary abelian series
  122.  
  123.     for step in [2..Length( elabser )] do
  124.  
  125.         InfoAgCent1( "#I  cs: step ", step, " / ", Length( elabser ), "\n" );
  126.  
  127.         # get the appropriate new data
  128.  
  129.         fhom := fachom[step];
  130.         facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  131.         facU := U[step-1];
  132.  
  133.         # map results from last step to current step
  134.  
  135.         Apply( series, x -> PreImage( fhom, x ) );
  136.  
  137.         if Length( facN.generators ) = 1 then
  138.             cs_ag_trivial_cnt[1] := cs_ag_trivial_cnt[1] + 1;
  139.  
  140.             Add( series, facN );
  141.         elif facU.generators = [] then
  142.             cs_ag_trivial_cnt[2] := cs_ag_trivial_cnt[2] + 1;
  143.  
  144.             Append( series, CompositionSeries( facN ) );
  145.         else
  146.             cs_ag_general_cnt[1] := cs_ag_general_cnt[1] + 1;
  147.  
  148.             facN.field := GF( RelativeOrderAgWord( facN.generators[1] ) );
  149.  
  150.             nigs   := Igs( facN );
  151.             ndim   := Length( nigs );
  152.             tmp    := List( Igs( facU ), x -> FactorAgWord( x, fhom.source.identity ) );
  153.             tmp    := List( tmp, x -> List( nigs, y -> Exponents( facN, y ^ x, facN.field ) ) );
  154.             module := MatGroup( tmp, facN.field );
  155.             subser := CompositionFactors( module ).bases;
  156.             ints   := IntegerTable( facN.field );
  157.  
  158.             for tmp in subser do
  159.                 for i in [1..Length( tmp )] do
  160.                     v := tmp[i];
  161.                     g := facN.identity;
  162.                     for j in [1..ndim] do
  163.                         z := LogVecFFE( v, j );
  164.                         if z <> false then
  165.                             g := g * nigs[j] ^ ints[z+1];
  166.                         fi;
  167.                     od;
  168.                     tmp[i] := g;
  169.                 od;
  170.             od;
  171.             for i in Reversed( [1..Length( subser )-1] ) do
  172.                 Append( subser[i], subser[i+1] );
  173.             od;
  174.             Apply( subser, x -> AgSubgroup( facN, x, false ) );
  175.             Append( series, subser );
  176.         fi;
  177.     od;
  178.     Add( series, TrivialSubgroup( G ) );
  179.     cs_ag_time := Runtime() - cs_ag_time;
  180.     return series;
  181. end;
  182.  
  183.  
  184. #############################################################################
  185. ##
  186. #F  AgGroupOps.ChiefSeries( [<U>, ]<H> )  . . . . chiefseries for an ag-group
  187. ##
  188. ##  This function determines a chiefseries for a given ag-group with respect
  189. ##  to the operation of the optional argument <U> which is an ag-group that acts
  190. ##  on <H> by conjugation. The author's MeatAxe module is used to
  191. ##  determine the simple factormodules in the elementary abelian factors of
  192. ##  <H> and the result is recomputed in terms of factorgroups for
  193. ##  <H>.
  194. ##
  195. ##  returns
  196. ##
  197. ##      <list>
  198. ##
  199. AgGroupOps.ChiefSeries := function( arg )
  200.     local   usage, G, H, U, HU, T, elabser, natisom, series;
  201.  
  202.     if    Length( arg ) = 1 then  H := arg[1]; U := H;
  203.     elif  Length( arg ) = 2 then  H := arg[2]; U := arg[1];
  204.     else
  205.         Error( "usage: ChiefSeries( [<U>, ]<H> )" );
  206.     fi;
  207.  
  208.     G := Parent( H );
  209.     T := TrivialSubgroup( G );
  210.  
  211.     if IsNormal( G, H ) then
  212.         if IsElementaryAbelianAgSeries( G )
  213.           and IsElementAgSeries( H ) then
  214.             elabser := ElementaryAbelianSeries( [ G, H, T ] );
  215.             series  := MainEntryCSAgGroup( G, U, H, elabser );
  216.         else
  217.             elabser := ElementaryAbelianSeries( [ G, H, T ] );
  218.             natisom := IsomorphismAgGroup( elabser );
  219.             elabser := ElementaryAbelianSeries( natisom.range );
  220.             series  := MainEntryCSAgGroup( natisom.range,
  221.                         Image( natisom, U ), Image( natisom, H ), elabser );
  222.             Apply( series, x -> PreImage( natisom, x ) );
  223.         fi;
  224.     elif IsNormal( U, H ) then
  225.         HU := SumAgGroup( H, U );
  226.         elabser := ElementaryAbelianSeries( [ HU, H, T ] );
  227.         natisom := IsomorphismAgGroup( elabser );
  228.         elabser := ElementaryAbelianSeries( natisom.range );
  229.         series  := MainEntryCSAgGroup( natisom.range,
  230.                     Image( natisom, U ), Image( natisom, H ), elabser );
  231.         Apply( series, x -> PreImage( natisom, x ) );
  232.     else
  233.         Error( "sorry, U must operate on H" );
  234.     fi;
  235.  
  236.     return series;
  237. end;
  238.  
  239.  
  240. #############################################################################
  241. ##
  242. #F  CentralCaseCentAgGroup( <G>, <N>, <C>, <M>, <h>, <n> )  . . . . . . . . .
  243. ##
  244. ##  returns
  245. ##
  246. ##      rec(
  247. ##          C := <aggroup>,
  248. ##          M := <aggroup>
  249. ##      )
  250. ##
  251. CentralCaseCentAgGroup := function( G, N, C, M, h, n )
  252.     local   h_C_comm, cg, newC, newM, cigs, tmp, v, g, z, i, j;
  253.  
  254.     InfoAgCent1( "#I  cent: central case main dispatcher\n" );
  255.  
  256.     if not IsBound( N.field ) then
  257.         N.field := GF( RelativeOrderAgWord( N.generators[1] ) );
  258.     fi;
  259.  
  260.     if C = [] then
  261.         InfoAgCent2( "#I  cent: central_1\n" );
  262.         cen_ag_central_cnt[1] := cen_ag_central_cnt[1] + 1;
  263.  
  264.         newC := C;
  265.         newM := M;
  266.     else
  267.         InfoAgCent2( "#I  cent: central_2\n" );
  268.         cen_ag_central_cnt[2] := cen_ag_central_cnt[2] + 1;
  269.  
  270.         h_C_comm := [];
  271.         for i in [1..Length( C )] do
  272.             h_C_comm[i] := Exponents( N, Comm( h, C[i] ), N.field );
  273.         od;
  274.  
  275.         cg  := CommutatorGauss( Copy( h_C_comm ), N.field );
  276.         tmp := [];
  277.         for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  278.             v := cg.matrix[i];
  279.             g := G.identity;
  280.             for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  281.                 z := LogVecFFE( v, j );
  282.                 if z <> false then
  283.                     g := g * C[j-cg.dimensionN] ^ cg.integers[z+1];
  284.                 fi;
  285.             od;
  286.             tmp[i-cg.commutator] := g;
  287.         od;
  288.         cg.centralizer := tmp;
  289.  
  290.         newC := cg.centralizer;
  291.         newM := M;
  292.     fi;
  293.  
  294.     return rec( C := newC, M := newM );
  295. end;
  296.  
  297.  
  298. #############################################################################
  299. ##
  300. #F  GeneralCaseCentAgGroup( <G>, <N>, <C>, <M>, <h>, <n> )  . . . . . . . . .
  301. ##
  302. ##  returns
  303. ##
  304. ##      rec(
  305. ##          C := <aggroup>,
  306. ##          M := <aggroup>
  307. ##      )
  308. ##
  309. GeneralCaseCentAgGroup := function( G, N, C, M, h, n )
  310.     local   N_C_pow, h_M_comm, centrala, centralb, ncgs, cigs, migs, n2cgs,
  311.             ndim, clen, mlen, n2dim, orb, v, g, z, newC, newM, cg, cg2,
  312.             wn2cgs, comm_h_M, N2_C_pow, h_C_comm, N2, tmp, i, j;
  313.  
  314.     InfoAgCent1( "#I  cent: general case main dispatcher\n" );
  315.  
  316.     if not IsBound( N.field ) then
  317.         N.field := GF( RelativeOrderAgWord( N.generators[1] ) );
  318.     fi;
  319.  
  320.     ncgs := Cgs( N );
  321.     cigs := C;
  322.     migs := M;
  323.     ndim := Length( ncgs );
  324.     clen := Length( cigs );
  325.     mlen := Length( migs );
  326.  
  327.     centrala := true;
  328.     centralb := true;
  329.     N_C_pow  := [];
  330.     for i in [1..clen] do
  331.         N_C_pow[i] := [];
  332.         for j in [1..ndim] do
  333.             N_C_pow[i][j] := ncgs[j] ^ cigs[i];
  334.             if N_C_pow[i][j] <> ncgs[j] then  centrala := false;  fi;
  335.         od;
  336.     od;
  337.  
  338.     h_M_comm := [];
  339.     for i in [1..mlen] do
  340.         h_M_comm[i] := Comm( h, migs[i] );
  341.         if h_M_comm[i] <> N.identity then  centralb := false;  fi;
  342.     od;
  343.  
  344.     if centrala and centralb then
  345.         InfoAgCent2( "#I  cent: non_central_1 ->\n" );
  346.         cen_ag_non_central_cnt[1] := cen_ag_non_central_cnt[1] + 1;
  347.  
  348.         return CentralCaseCentAgGroup( G, N, C, M, h, n );
  349.     fi;
  350.  
  351.     if centralb then
  352.         InfoAgCent2( "#I  cent: non_central_2\n" );
  353.         cen_ag_non_central_cnt[2] := cen_ag_non_central_cnt[2] + 1;
  354.  
  355.         for i in [1..clen] do
  356.             tmp := N_C_pow[i];
  357.             for j in [1..ndim] do
  358.                 tmp[j] := Exponents( N, tmp[j], N.field );
  359.                 tmp[j][ndim+1] := N.field.zero;
  360.             od;
  361.             tmp[ndim+1] := Exponents( N, Comm( h, cigs[i] ), N.field );
  362.             tmp[ndim+1][ndim+1] := N.field.one;
  363.         od;
  364.         v    := Exponents( N, n, N.field );
  365.         v[ndim+1] := N.field.one;
  366.         orb  := AgOrbitStabilizer( AgSubgroup( G, C, false ), N_C_pow, v );
  367.         newC := Igs( orb.stabilizer );
  368.         newM := M;
  369.  
  370.         return rec( C := newC, M := newM );
  371.     fi;
  372.  
  373.     for i in [1..mlen] do
  374.         h_M_comm[i] := Exponents( N, h_M_comm[i], N.field );
  375.     od;
  376.  
  377.     if centrala then
  378.         InfoAgCent2( "#I  cent: non_central_3\n" );
  379.         cen_ag_non_central_cnt[3] := cen_ag_non_central_cnt[3] + 1;
  380.  
  381.         h_C_comm := [];
  382.         for i in [1..clen] do
  383.             h_C_comm[i] := Exponents( N, Comm( h, cigs[i] ), N.field );
  384.         od;
  385.         Append( cigs, migs );
  386.         Append( h_C_comm, h_M_comm );
  387.  
  388.         cg := CommutatorGauss( Copy( h_C_comm ), N.field );
  389.  
  390.         tmp := [];
  391.         for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  392.             v := cg.matrix[i];
  393.             g := G.identity;
  394.             for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  395.                 z := LogVecFFE( v, j );
  396.                 if z <> false then
  397.                     g := g * cigs[j-cg.dimensionN] ^ cg.integers[z+1];
  398.                 fi;
  399.             od;
  400.             tmp[i-cg.commutator] := g;
  401.         od;
  402.         cg.centralizer := tmp;
  403.  
  404.         newC := cg.centralizer;
  405.         newM := [];
  406.  
  407.         return rec( C := newC, M := newM );
  408.     fi;
  409.  
  410.     cg := CommutatorGauss( Copy( h_M_comm ), N.field );
  411.  
  412.     if cg.commutatorFactor = [] then
  413.         InfoAgCent2( "#I  cent: non_central_4\n" );
  414.         cen_ag_non_central_cnt[4] := cen_ag_non_central_cnt[4] + 1;
  415.  
  416.         newC := CorrectedStabilizer( h_M_comm, N, C, M, h, n, false );
  417.         newM := [];
  418.     else
  419.         tmp := [];
  420.         for i in [1..cg.commutator] do
  421.             v := cg.matrix[i];
  422.             g := G.identity;
  423.             for j in [1..cg.dimensionN] do
  424.                 z := LogVecFFE( v, j );
  425.                 if z <> false then
  426.                     g := g * ncgs[j] ^ cg.integers[z+1];
  427.                 fi;
  428.             od;
  429.             tmp[i] := g;
  430.         od;
  431.  
  432.         # don't bound cg.commutator to tmp here. this field is re-used later.
  433.  
  434.         N2       := N mod AgSubgroup( G, tmp, false );
  435.         N2.field := N.field;
  436.         n2cgs    := N2.generators;
  437.         n2dim    := Length( n2cgs );
  438.         tmp      := DepthAgWord( ncgs[1] ) - 1;
  439.         wn2cgs   := List( n2cgs, x -> DepthAgWord( x ) - tmp );
  440.         centrala := true;
  441.  
  442.         N2_C_pow := [];
  443.         for i in [1..clen] do
  444.             N2_C_pow[i] := [];
  445.             for j in [1..n2dim] do
  446.                 N2_C_pow[i][j] := N_C_pow[i][wn2cgs[j]];
  447.                 if centrala
  448.                  and not N2_C_pow[i][j] / n2cgs[j] in N2.factorDen then
  449.                     centrala := false;
  450.                 fi;
  451.             od;
  452.         od;
  453.  
  454.         if centrala then
  455.             InfoAgCent2( "#I  cent: non_central_5\n" );
  456.             cen_ag_non_central_cnt[5] := cen_ag_non_central_cnt[5] + 1;
  457.  
  458.             h_C_comm := [];
  459.             for i in [1..clen] do
  460.                 h_C_comm[i] := Exponents( N2, Comm( h, cigs[i] ), N2.field );
  461.             od;
  462.  
  463.             cg2 := CommutatorGauss( Copy( h_C_comm ), N.field );
  464.  
  465.             tmp := [];
  466.             for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  467.                 v := cg.matrix[i];
  468.                 g := G.identity;
  469.                 for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  470.                     z := LogVecFFE( v, j );
  471.                     if z <> false then
  472.                         g := g * migs[j-cg.dimensionN] ^ cg.integers[z+1];
  473.                     fi;
  474.                 od;
  475.                 tmp[i-cg.commutator] := g;
  476.             od;
  477.             cg.centralizer := tmp;
  478.  
  479.             tmp := [];
  480.             for i in [cg2.commutator+1..cg2.commutator+cg2.centralizer] do
  481.                 v := cg2.matrix[i];
  482.                 g := G.identity;
  483.                 for j in [cg2.dimensionN+1..cg2.dimensionN+cg2.dimensionC] do
  484.                     z := LogVecFFE( v, j );
  485.                     if z <> false then
  486.                         g := g * C[j-cg2.dimensionN] ^ cg2.integers[z+1];
  487.                     fi;
  488.                 od;
  489.                 tmp[i-cg2.commutator] := g;
  490.             od;
  491.             cg2.centralizer := tmp;
  492.  
  493.             newC := Concatenation(
  494.                CorrectedStabilizer( h_M_comm, N, cg2.centralizer, M, h, n, false ),
  495.                cg.centralizer
  496.             );
  497.             newM := [];
  498.         else
  499.             InfoAgCent2( "#I  cent: non_central_6\n" );
  500.             cen_ag_non_central_cnt[6] := cen_ag_non_central_cnt[6] + 1;
  501.  
  502.             for i in [1..clen] do
  503.                 tmp := N2_C_pow[i];
  504.                 for j in [1..n2dim] do
  505.                     tmp[j] := Exponents( N2, tmp[j], N2.field );
  506.                     tmp[j][n2dim+1] := N.field.zero;
  507.                 od;
  508.                 tmp[n2dim+1] := Exponents( N2, Comm( h, cigs[i] ), N2.field );
  509.                 tmp[n2dim+1][n2dim+1] := N.field.one;
  510.             od;
  511.  
  512.             tmp := [];
  513.             for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  514.                 v := cg.matrix[i];
  515.                 g := G.identity;
  516.                 for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  517.                     z := LogVecFFE( v, j );
  518.                     if z <> false then
  519.                         g := g * migs[j-cg.dimensionN] ^ cg.integers[z+1];
  520.                     fi;
  521.                 od;
  522.                 tmp[i-cg.commutator] := g;
  523.             od;
  524.             cg.centralizer := tmp;
  525.  
  526.             v    := Exponents( N2, n, N2.field );
  527.             v[n2dim+1] := N.field.one;
  528.             orb  := AgOrbitStabilizer( AgSubgroup( G, C, false ), N2_C_pow, v );
  529.             newC := Concatenation(
  530.                CorrectedStabilizer( h_M_comm, N, Igs( orb.stabilizer ), M, h, n, false ),
  531.                cg.centralizer
  532.             );
  533.             newM := [];
  534.         fi;
  535.     fi;
  536.  
  537.     return rec( C := newC, M := newM );
  538. end;
  539.  
  540.  
  541. #############################################################################
  542. ##
  543. #F  MainEntryCentAgGroup( <G>, <U>, <H>, <ser> )  . . . . . . . . . . . . . .
  544. ##
  545. ##  returns
  546. ##
  547. ##      <aggroup>
  548. ##
  549. MainEntryCentAgGroup := function( G, U, H, elabser )
  550.     local   tmpU, tmpH, fachom, fhom, C, hn, h, n, facU, facN, idx,
  551.             step, repnum, res, i;
  552.  
  553.     if U.generators = [] then  return U;  fi;
  554.     if H.generators = [] then  return U;  fi;
  555.  
  556.     cen_ag_time            := Runtime();
  557.     cen_ag_central_cnt     := [ 0, 0 ];
  558.     cen_ag_non_central_cnt := [ 0, 0, 0, 0, 0, 0 ];
  559.  
  560.     idx := 1;
  561.     while IsSubgroup( elabser[idx+1], H ) do  idx := idx + 1;  od;
  562.     while IsSubgroup( elabser[idx+1], U ) do  idx := idx + 1;  od;
  563.  
  564.     if idx <> 1 then
  565.         elabser := Sublist( elabser, [idx..Length( elabser )] );
  566.     fi;
  567.     fachom := HomomorphismsSeries( G, elabser );
  568.  
  569.     # initialize the inductive algorithm
  570.  
  571.     C := Igs( Image( fachom[1], U ) );
  572.  
  573.     # prepare the involved data for each following step
  574.  
  575.     tmpU := U;
  576.     tmpH := H.generators;
  577.     U    := [];
  578.     H    := [];
  579.     U[Length( elabser )] := tmpU;
  580.     H[Length( elabser )] := tmpH;
  581.     for step in Reversed( [2..Length( elabser )] ) do
  582.         tmpU := Image( fachom[step], tmpU );
  583.         U[step-1] := tmpU;
  584.         tmpH := List( tmpH, x -> Image( fachom[step], x ) );
  585.         H[step-1] := tmpH;
  586.     od;
  587.  
  588.     # loop over the elementary abelian series
  589.  
  590.     for step in [2..Length( elabser )] do
  591.  
  592.         InfoAgCent1( "#I  cent: step ", step, " / ", Length( elabser ), "\n" );
  593.  
  594.         # get the appropriate new data
  595.  
  596.         fhom := fachom[step];
  597.         facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  598.  
  599.         # map results from last step to current step
  600.  
  601.         tmpU := SumFactorizationFunctionAgGroup( U[step], facN );
  602.         facU := Igs( tmpU.intersection );
  603.         Apply( C, x -> tmpU.factorization( FactorAgWord( x, 
  604.                        fhom.source.identity ) ).u );
  605.         res := rec( C := C, M := facU );
  606.  
  607.         hn  := H[step];
  608.         h   := List( H[step-1], x -> FactorAgWord( x, fhom.source.identity ) );
  609.         n   := [];
  610.         for i in [1..Length( h )] do  n[i] := h[i]^-1 * hn[i];   od;
  611.  
  612.         if IsCentral( fhom.source, facN ) then
  613.             for repnum in [1..Length( h )] do
  614.                 res := CentralCaseCentAgGroup(
  615.                         fhom.source, facN, res.C, res.M, h[repnum], n[repnum] );
  616.             od;
  617.         else
  618.             for repnum in [1..Length( h )] do
  619.                 res := GeneralCaseCentAgGroup(
  620.                         fhom.source, facN, res.C, res.M, h[repnum], n[repnum] );
  621.             od;
  622.         fi;
  623.  
  624.         C := Concatenation( res.C, res.M );
  625.     od;
  626.     cen_ag_time := Runtime() - cen_ag_time;
  627.     return AgSubgroup( G, C, false );
  628. end;
  629.  
  630.  
  631. #############################################################################
  632. ##
  633. #F  AgGroupOps.Centralizer( [<U>, ]<H> )  . . . . . . . . . . . . . . . . . .
  634. ##
  635. ##
  636. ##  returns
  637. ##
  638. ##      <aggroup>
  639. ##
  640. AgGroupOps.Centralizer := function( arg )
  641.     local   G, U, H, elabser, natisom, res;
  642.  
  643.     if    Length( arg ) = 1 then
  644.         H := arg[1];
  645.         G := Parent( H );
  646.         U := G;
  647.     elif  Length( arg ) = 2 then
  648.         if IsAgWord( arg[2] ) then
  649.             U := arg[1];
  650.             H := U.operations.Subgroup( U, [ arg[2] ] );
  651.             G := Parent( H );
  652.         else
  653.             U := arg[1];
  654.             H := arg[2];
  655.             G := Parent( H );
  656.         fi;
  657.     else
  658.         Error( "usage: Centralizer( [<U>, ]<H> )" );
  659.     fi;
  660.  
  661.     if not IsElementaryAbelianAgSeries( G ) then
  662.         elabser := ElementaryAbelianSeries( G );
  663.         natisom := IsomorphismAgGroup( elabser );
  664.         elabser := ElementaryAbelianSeries( natisom.range );
  665.         res     := MainEntryCentAgGroup(
  666.                     natisom.range, Image( natisom, U ), Image( natisom, H ),
  667.                     elabser );
  668.         res     := PreImage( natisom, res );
  669.     else
  670.         elabser := ElementaryAbelianSeries( G );
  671.         res     := MainEntryCentAgGroup( G, U, H, elabser );
  672.     fi;
  673.  
  674.     return res;
  675. end;
  676.  
  677.  
  678. #############################################################################
  679. ##
  680. #F  AgGroupOps.Centralizer2( [<U>, ]<H> ) . . . . . . . . . . . . . . . . . .
  681. ##
  682. ##  returns
  683. ##
  684. ##      <aggroup>
  685. ##
  686. AgGroupOps.Centralizer2 := function( arg )
  687.     local   G, U, H, rep, res;
  688.  
  689.     if    Length( arg ) = 1 then
  690.         H := arg[1];
  691.         G := Parent( H );
  692.         U := G;
  693.     elif  Length( arg ) = 2 then
  694.         if IsAgWord( arg[2] ) then
  695.             U := arg[1];
  696.             H := AgSubgroup( U, [ arg[2] ], false );
  697.             G := Parent( H );
  698.         else
  699.             U := arg[1];
  700.             H := arg[2];
  701.             G := Parent( H );
  702.         fi;
  703.     else
  704.         Error( "usage: Centralizer( [<U>, ]<H> )" );
  705.     fi;
  706.  
  707.     if U.generators = [] then  return U;  fi;
  708.     if H.generators = [] then  return U;  fi;
  709.  
  710.     for rep in H.generators do
  711.         res := ConjugacyClasses( U, [ rep ] );
  712.         U   := res[1].centralizer ^ (res[1].conjugand^-1);
  713.     od;
  714.  
  715.     return U;
  716. end;
  717.  
  718.  
  719. #############################################################################
  720. ##
  721. #F  CentralCaseECAgWords( <G>, <N>, <C>, <M>, <h>, <n> )  . . . . . . . . . .
  722. ##
  723. ##  returns
  724. ##
  725. ##      rec(
  726. ##          representative := <agword>,
  727. ##          centralizer    := [ <agword> ],
  728. ##          conjugand      := <agword>
  729. ##      )
  730. ##
  731. CentralCaseECAgWords := function( G, N, C, M, h, n )
  732.    local    h_C_comm, ncgs, cigs, migs, N2, n2cgs, cg, rep, cent, conj,
  733.             tmp, v, g, z, i, j;
  734.  
  735.  
  736.     if not IsBound( N.field ) then
  737.         N.field := GF( RelativeOrderAgWord( N.generators[1] ) );
  738.     fi;
  739.  
  740.     if C = [] then
  741.         ec_ag_central_cnt[1] := ec_ag_central_cnt[1] + 1;
  742.  
  743.         rep  := h * n;
  744.         cent := M;
  745.         conj := G.identity;
  746.     else
  747.         ec_ag_central_cnt[2] := ec_ag_central_cnt[2] + 1;
  748.  
  749.         ncgs := Cgs( N );
  750.         cigs := C;
  751.         migs := M;
  752.  
  753.         h_C_comm := [];
  754.         for i in [1..Length( cigs )] do
  755.             h_C_comm[i] := Exponents( N, Comm( h, cigs[i] ), N.field );
  756.         od;
  757.  
  758.         cg := CommutatorGauss( Copy( h_C_comm ), N.field );
  759.  
  760.         tmp := [];
  761.         for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  762.             v := cg.matrix[i];
  763.             g := G.identity;
  764.             for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  765.                 z := LogVecFFE( v, j );
  766.                 if z <> false then
  767.                     g := g * cigs[j-cg.dimensionN] ^ cg.integers[z+1];
  768.                 fi;
  769.             od;
  770.             tmp[i-cg.commutator] := g;
  771.         od;
  772.         cg.centralizer := tmp;
  773.  
  774.         tmp := [];
  775.         for i in [1..cg.commutator] do
  776.             v := cg.matrix[i];
  777.             g := G.identity;
  778.             for j in [1..cg.dimensionN] do
  779.                 z := LogVecFFE( v, j );
  780.                 if z <> false then
  781.                     g := g * ncgs[j] ^ cg.integers[z+1];
  782.                 fi;
  783.             od;
  784.             tmp[i] := g;
  785.         od;
  786.         cg.commutator := tmp;
  787.  
  788.         N2       := N mod AgSubgroup( G, cg.commutator, true );
  789.         N2.field := N.field;
  790.         n2cgs    := N2.generators;
  791.  
  792.         v := Exponents( N2, n );
  793.         g := G.identity;
  794.         for j in [1..Length( n2cgs )] do
  795.             z := v[j];
  796.             if z <> 0 then
  797.                 g := g * n2cgs[j] ^ z;
  798.             fi;
  799.         od;
  800.         rep := g;
  801.  
  802.         v := SolutionMat( h_C_comm, Exponents( N, n^-1 * rep, N.field ) );
  803.         g := G.identity;
  804.         for j in [1..Length( cigs )] do
  805.             z := LogVecFFE( v, j );
  806.             if z <> false then
  807.                 g := g * cigs[j] ^ cg.integers[z+1];
  808.             fi;
  809.         od;
  810.  
  811.         conj := g;
  812.         rep  := h * rep;
  813.         cent := Concatenation( cg.centralizer, migs );
  814.    fi;
  815.    return rec(
  816.       representative := rep,
  817.       centralizer    := cent,
  818.       conjugand      := conj
  819.    );
  820. end;
  821.  
  822.  
  823. #############################################################################
  824. ##
  825. #F  GeneralCaseECAgWords( <G>, <N>, <C>, <M>, <h>, <n> )  . . . . . . . . . .
  826. ##
  827. ##  returns
  828. ##
  829. ##      rec(
  830. ##          representative := <agword>,
  831. ##          centralizer    := [ <agword> ],
  832. ##          conjugand      := <agword>
  833. ##      )
  834. ##
  835. GeneralCaseECAgWords := function( G, N, C, M, h, n )
  836.    local    N_C_pow, h_M_comm, ncgs, cigs, migs, ndim, clen, mlen,
  837.             centrala, centralb, orb, v, g, z, cent, rep, conj, cg, cg2,
  838.             comm_h_M, N2_C_pow, h_C_comm, N2, N3, n2cgs, n2dim, n3cgs,
  839.             minp, comm_h_CM, wn2cgs, tmp, i, j;
  840.  
  841.     if not IsBound( N.field ) then
  842.         N.field := GF( RelativeOrderAgWord( N.generators[1] ) );
  843.     fi;
  844.  
  845.     ncgs := Cgs( N );
  846.     cigs := C;
  847.     migs := M;
  848.     ndim := Length( ncgs );
  849.     clen := Length( cigs );
  850.     mlen := Length( migs );
  851.  
  852.     centrala := true;
  853.     centralb := true;
  854.     N_C_pow  := [];
  855.     for i in [1..clen] do
  856.         N_C_pow[i] := [];
  857.         for j in [1..ndim] do
  858.             N_C_pow[i][j] := ncgs[j] ^ cigs[i];
  859.             if N_C_pow[i][j] <> ncgs[j] then  centrala := false;  fi;
  860.         od;
  861.     od;
  862.  
  863.     h_M_comm := [];
  864.     for i in [1..mlen] do
  865.         h_M_comm[i] := Comm( h, migs[i] );
  866.         if h_M_comm[i] <> N.identity then  centralb := false;  fi;
  867.     od;
  868.  
  869.     if centrala and centralb then
  870.         ec_ag_non_central_cnt[1] := ec_ag_non_central_cnt[1] + 1;
  871.  
  872.         return CentralCaseECAgWords( G, N, C, M, h, n );
  873.     fi;
  874.  
  875.     if centralb then
  876.         ec_ag_non_central_cnt[2] := ec_ag_non_central_cnt[2] + 1;
  877.  
  878.         for i in [1..clen] do
  879.             tmp := N_C_pow[i];
  880.             for j in [1..ndim] do
  881.                 tmp[j] := Exponents( N, tmp[j], N.field );
  882.                 tmp[j][ndim+1] := N.field.zero;
  883.             od;
  884.             tmp[ndim+1] := Exponents( N, Comm( h, cigs[i] ), N.field );
  885.             tmp[ndim+1][ndim+1] := N.field.one;
  886.         od;
  887.         v    := Exponents( N, n, N.field );
  888.         v[ndim+1] := N.field.one;
  889.         orb  := MinimalVectorAgOrbit( AgSubgroup( G, C, false ), N_C_pow, v, N.field );
  890.         cg   := IntegerTable( N.field );
  891.  
  892.         v := orb.vector;
  893.         g := G.identity;
  894.         for j in [1..ndim] do
  895.             z := LogVecFFE( v, j );
  896.             if z <> false then
  897.                 g := g * ncgs[j] ^ cg[z+1];
  898.             fi;
  899.         od;
  900.         rep  := h * g;
  901.         conj := orb.operator;
  902.         cent := Concatenation( Igs( orb.stabilizer ^ conj ), migs );
  903.  
  904.         return rec(
  905.             representative := rep,
  906.             centralizer    := cent,
  907.             conjugand      := conj
  908.         );
  909.     fi;
  910.  
  911.     for i in [1..mlen] do
  912.         h_M_comm[i] := Exponents( N, h_M_comm[i], N.field );
  913.     od;
  914.  
  915.     if centrala then
  916.         ec_ag_non_central_cnt[3] := ec_ag_non_central_cnt[3] + 1;
  917.  
  918.         h_C_comm := [];
  919.         for i in [1..clen] do
  920.             h_C_comm[i] := Exponents( N, Comm( h, cigs[i] ), N.field );
  921.         od;
  922.         Append( cigs, migs );
  923.         Append( h_C_comm, h_M_comm );
  924.  
  925.         cg := CommutatorGauss( Copy( h_C_comm ), N.field );
  926.  
  927.         tmp := [];
  928.         for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  929.             v := cg.matrix[i];
  930.             g := G.identity;
  931.             for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  932.                 z := LogVecFFE( v, j );
  933.                 if z <> false then
  934.                     g := g * cigs[j-cg.dimensionN] ^ cg.integers[z+1];
  935.                 fi;
  936.             od;
  937.             tmp[i-cg.commutator] := g;
  938.         od;
  939.         cg.centralizer := tmp;
  940.  
  941.         tmp := [];
  942.         for i in [1..cg.commutator] do
  943.             v := cg.matrix[i];
  944.             g := G.identity;
  945.             for j in [1..cg.dimensionN] do
  946.                 z := LogVecFFE( v, j );
  947.                 if z <> false then
  948.                     g := g * ncgs[j] ^ cg.integers[z+1];
  949.                 fi;
  950.             od;
  951.             tmp[i] := g;
  952.         od;
  953.         cg.commutator := tmp;
  954.  
  955.         N2       := N mod AgSubgroup( G, cg.commutator, true );
  956.         N2.field := N.field;
  957.         n2cgs    := N2.generators;
  958.  
  959.         v := Exponents( N2, n );
  960.         g := G.identity;
  961.         for j in [1..Length( n2cgs )] do
  962.             z := v[j];
  963.             if z <> 0 then
  964.                 g := g * n2cgs[j] ^ z;
  965.             fi;
  966.         od;
  967.         rep := g;
  968.  
  969.         v := SolutionMat( h_C_comm, Exponents( N, n^-1 * rep, N.field ) );
  970.         g := G.identity;
  971.         for j in [1..Length( cigs )] do
  972.             z := LogVecFFE( v, j );
  973.             if z <> false then
  974.                 g := g * cigs[j] ^ cg.integers[z+1];
  975.             fi;
  976.         od;
  977.  
  978.         conj := g;
  979.         rep  := h * rep;
  980.         cent := cg.centralizer;
  981.  
  982.         return rec(
  983.             representative := rep,
  984.             centralizer    := cent,
  985.             conjugand      := conj
  986.         );
  987.     fi;
  988.  
  989.     cg := CommutatorGauss( Copy( h_M_comm ), N.field );
  990.  
  991.     if cg.commutatorFactor = [] then
  992.         ec_ag_non_central_cnt[4] := ec_ag_non_central_cnt[4] + 1;
  993.  
  994.         rep := h;
  995.  
  996.         v := SolutionMat( h_M_comm, Exponents( N, n^-1, N.field ) );
  997.         g := G.identity;
  998.         for j in [1..mlen] do
  999.             z := LogVecFFE( v, j );
  1000.             if z <> false then
  1001.                 g := g * migs[j] ^ cg.integers[z+1];
  1002.             fi;
  1003.         od;
  1004.  
  1005.         conj := g;
  1006.         cent := CorrectedStabilizer( h_M_comm, N, C, migs, h, N.identity, false );
  1007.    else
  1008.         tmp := [];
  1009.         for i in [1..cg.commutator] do
  1010.             v := cg.matrix[i];
  1011.             g := G.identity;
  1012.             for j in [1..cg.dimensionN] do
  1013.                 z := LogVecFFE( v, j );
  1014.                 if z <> false then
  1015.                     g := g * ncgs[j] ^ cg.integers[z+1];
  1016.                 fi;
  1017.             od;
  1018.             tmp[i] := g;
  1019.         od;
  1020.  
  1021.         # don't bound cg.commutator to tmp here. this field is re-used later.
  1022.  
  1023.         N2       := N mod AgSubgroup( G, tmp, false );
  1024.         N2.field := N.field;
  1025.         n2cgs    := N2.generators;
  1026.         n2dim    := Length( n2cgs );
  1027.         tmp      := DepthAgWord( ncgs[1] ) - 1;
  1028.         wn2cgs   := List( n2cgs, x -> DepthAgWord( x ) - tmp );
  1029.         centrala := true;
  1030.  
  1031.         N2_C_pow := [];
  1032.         for i in [1..clen] do
  1033.             N2_C_pow[i] := [];
  1034.             for j in [1..n2dim] do
  1035.                 N2_C_pow[i][j] := N_C_pow[i][wn2cgs[j]];
  1036.                 if centrala
  1037.                  and not N2_C_pow[i][j] / n2cgs[j] in N2.factorDen then
  1038.                     centrala := false;
  1039.                 fi;
  1040.             od;
  1041.         od;
  1042.  
  1043.         if centrala then
  1044.             ec_ag_non_central_cnt[5] := ec_ag_non_central_cnt[5] + 1;
  1045.  
  1046.             h_C_comm := [];
  1047.             for i in [1..clen] do
  1048.                 h_C_comm[i] := Exponents( N2, Comm( h, cigs[i] ), N2.field );
  1049.             od;
  1050.             cg2 := CommutatorGauss( Copy( h_C_comm ), N.field );
  1051.  
  1052.             tmp := [];
  1053.             for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  1054.                 v := cg.matrix[i];
  1055.                 g := G.identity;
  1056.                 for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  1057.                     z := LogVecFFE( v, j );
  1058.                     if z <> false then
  1059.                         g := g * migs[j-cg.dimensionN] ^ cg.integers[z+1];
  1060.                     fi;
  1061.                 od;
  1062.                 tmp[i-cg.commutator] := g;
  1063.             od;
  1064.             cg.centralizer := tmp;
  1065.  
  1066.             tmp := [];
  1067.             for i in [cg2.commutator+1..cg2.commutator+cg2.centralizer] do
  1068.                 v := cg2.matrix[i];
  1069.                 g := G.identity;
  1070.                 for j in [cg2.dimensionN+1..cg2.dimensionN+cg2.dimensionC] do
  1071.                     z := LogVecFFE( v, j );
  1072.                     if z <> false then
  1073.                         g := g * C[j-cg2.dimensionN] ^ cg2.integers[z+1];
  1074.                     fi;
  1075.                 od;
  1076.                 tmp[i-cg2.commutator] := g;
  1077.             od;
  1078.             cg2.centralizer := tmp;
  1079.  
  1080.             tmp := [];
  1081.             for i in [1..cg2.commutator] do
  1082.                 v := cg2.matrix[i];
  1083.                 g := G.identity;
  1084.                 for j in [1..cg2.dimensionN] do
  1085.                     z := LogVecFFE( v, j );
  1086.                     if z <> false then
  1087.                         g := g * n2cgs[j] ^ cg2.integers[z+1];
  1088.                     fi;
  1089.                 od;
  1090.                 tmp[i] := g;
  1091.             od;
  1092.             cg2.commutator := tmp;
  1093.  
  1094.             N3 := N mod MergedIgs( N, N2.factorDen, cg2.commutator, false );
  1095.             N3.field := N.field;
  1096.             n3cgs    := N3.generators;
  1097.  
  1098.             v := Exponents( N3, n );
  1099.             g := G.identity;
  1100.             for j in [1..Length( n3cgs )] do
  1101.                 z := v[j];
  1102.                 if z <> 0 then
  1103.                     g := g * n3cgs[j] ^ z;
  1104.                 fi;
  1105.             od;
  1106.             rep := g;
  1107.  
  1108.             v := SolutionMat( h_C_comm, Exponents( N2, n^-1 * rep, N2.field ) );
  1109.             g := G.identity;
  1110.             for j in [1..clen] do
  1111.                 z := LogVecFFE( v, j );
  1112.                 if z <> false then
  1113.                     g := g * cigs[j] ^ cg.integers[z+1];
  1114.                 fi;
  1115.             od;
  1116.             conj := g;
  1117.  
  1118.             v := SolutionMat( h_M_comm,
  1119.                               Exponents( N, ((h * rep)^-1 * (h * n)^conj)^-1, N.field ) );
  1120.             g := G.identity;
  1121.             for j in [1..mlen] do
  1122.                 z := LogVecFFE( v, j );
  1123.                 if z <> false then
  1124.                     g := g * migs[j] ^ cg.integers[z+1];
  1125.                 fi;
  1126.             od;
  1127.             conj := conj * g;
  1128.  
  1129.             cent := Concatenation(
  1130.                 CorrectedStabilizer( h_M_comm, N, cg2.centralizer, migs, h, rep, false ),
  1131.                 cg.centralizer
  1132.             );
  1133.             rep := h * rep;
  1134.         else
  1135.             ec_ag_non_central_cnt[6] := ec_ag_non_central_cnt[6] + 1;
  1136.  
  1137.             for i in [1..clen] do
  1138.                 tmp := N2_C_pow[i];
  1139.                 for j in [1..n2dim] do
  1140.                     tmp[j] := Exponents( N2, tmp[j], N2.field );
  1141.                     tmp[j][n2dim+1] := N.field.zero;
  1142.                 od;
  1143.                 tmp[n2dim+1] := Exponents( N2, Comm( h, cigs[i] ), N2.field );
  1144.                 tmp[n2dim+1][n2dim+1] := N.field.one;
  1145.             od;
  1146.  
  1147.             tmp := [];
  1148.             for i in [cg.commutator+1..cg.commutator+cg.centralizer] do
  1149.                 v := cg.matrix[i];
  1150.                 g := G.identity;
  1151.                 for j in [cg.dimensionN+1..cg.dimensionN+cg.dimensionC] do
  1152.                     z := LogVecFFE( v, j );
  1153.                     if z <> false then
  1154.                         g := g * migs[j-cg.dimensionN] ^ cg.integers[z+1];
  1155.                     fi;
  1156.                 od;
  1157.                 tmp[i-cg.commutator] := g;
  1158.             od;
  1159.             cg.centralizer := tmp;
  1160.  
  1161.             v    := Exponents( N2, n, N2.field );
  1162.             v[n2dim+1] := N.field.one;
  1163.             orb  := MinimalVectorAgOrbit( AgSubgroup( G, C, false ), N2_C_pow, v, N.field );
  1164.  
  1165.             v := orb.vector;
  1166.             g := G.identity;
  1167.             for j in [1..n2dim] do
  1168.                 z := LogVecFFE( v, j );
  1169.                 if z <> false then
  1170.                     g := g * n2cgs[j] ^ cg.integers[z+1];
  1171.                 fi;
  1172.             od;
  1173.             rep  := g;
  1174.             conj := orb.operator;
  1175.             cent := orb.stabilizer ^ conj;
  1176.             cent := Concatenation(
  1177.                 CorrectedStabilizer( h_M_comm, N, Igs( cent ), migs, h, rep, false ),
  1178.                 cg.centralizer
  1179.             );
  1180.  
  1181.             v := SolutionMat( h_M_comm,
  1182.                               Exponents( N, ((h * rep)^-1 * (h * n)^conj)^-1, N.field ) );
  1183.             g := G.identity;
  1184.             for j in [1..mlen] do
  1185.                 z := LogVecFFE( v, j );
  1186.                 if z <> false then
  1187.                     g := g * migs[j] ^ cg.integers[z+1];
  1188.                 fi;
  1189.             od;
  1190.             conj := conj * g;
  1191.             rep  := h * rep;
  1192.        fi;
  1193.    fi;
  1194.    return rec(
  1195.       representative := rep,
  1196.       centralizer    := cent,
  1197.       conjugand      := conj
  1198.    );
  1199. end;
  1200.  
  1201.  
  1202. #############################################################################
  1203. ##
  1204. #F  MainEntryECAgWords( <G>, <U>, <elems>, <elabser> )  . . . . . . . . . . .
  1205. ##
  1206. ##  returns
  1207. ##
  1208. ##      rec(
  1209. ##          elements        := [ <agword> ],
  1210. ##          representatives := [ <agword> ],
  1211. ##          centralizers    := [ <aggroups> ],
  1212. ##          conjugands      := [ <agword> ]
  1213. ##      )
  1214. ##
  1215. MainEntryECAgWords := function( G, U, elems, elabser )
  1216.     local   tmpU, tmpe, fachom, fhom, rep, cent, conj, facU, face, felems,
  1217.             step, facN, ctrly, repnum, idx, res;
  1218.  
  1219.     if U.generators = [] or Set( elems ) = [ G.identity ] then
  1220.         return rec(
  1221.             elements        := elems,
  1222.             representatives := elems,
  1223.             centralizers    := List( elems, x -> U ),
  1224.             conjugands      := List( elems, x -> U.identity )
  1225.         );
  1226.     fi;
  1227.  
  1228.     ec_ag_time            := Runtime();
  1229.     ec_ag_central_cnt     := [ 0, 0 ];
  1230.     ec_ag_non_central_cnt := [ 0, 0, 0, 0, 0, 0 ];
  1231.  
  1232.     idx := 1;
  1233.     while IsSubgroup( elabser[idx+1], U ) do  idx := idx + 1;  od;
  1234.     while not false in List( elems, x -> x in elabser[idx+1] ) do
  1235.         idx := idx + 1;
  1236.     od;
  1237.  
  1238.     if idx <> 1 then
  1239.         elabser := Sublist( elabser, [idx..Length( elabser )] );
  1240.     fi;
  1241.     fachom := HomomorphismsSeries( G, elabser );
  1242.  
  1243.  
  1244.     # initialize the inductive algorithm
  1245.  
  1246.     tmpU := Image( fachom[1], U );
  1247.     rep  := List( elems, x -> Image( fachom[1], x ) );
  1248.     cent := List( elems, x -> tmpU.generators );
  1249.     conj := List( elems, x -> tmpU.identity );
  1250.  
  1251.     # prepare the involved data for each following step
  1252.  
  1253.     tmpU := U;
  1254.     tmpe := elems;
  1255.     U     := [];
  1256.     elems := [];
  1257.     U[Length( elabser )]     := tmpU;
  1258.     elems[Length( elabser )] := tmpe;
  1259.     for step in Reversed( [2..Length( elabser )] ) do
  1260.         tmpU := Image( fachom[step], tmpU );
  1261.         U[step-1] := tmpU;
  1262.         tmpe := List( tmpe, x -> Image( fachom[step], x ) );
  1263.         elems[step-1] := tmpe;
  1264.     od;
  1265.  
  1266.     # loop over the elementary abelian series
  1267.  
  1268.     for step in [2..Length( elabser )] do
  1269.  
  1270.         InfoAgCent1( "#I  ec: step ", step, " / ", Length( elabser ), "\n" );
  1271.  
  1272.         # get the appropriate new data
  1273.  
  1274.         fhom := fachom[step];
  1275.         facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  1276.         facU := Igs( Intersection( U[step], facN ) );
  1277.         face := elems[step];
  1278.  
  1279.         # map results from last step to current step
  1280.  
  1281.         Apply( rep,  x -> FactorAgWord( x, fhom.source.identity ) );
  1282.         Apply( cent, x -> List( x, y -> FactorAgWord( y, fhom.source.identity ) ) );
  1283.         Apply( conj, x -> FactorAgWord( x, fhom.source.identity ) );
  1284.  
  1285.         if IsCentral( fhom.source, facN ) then
  1286.             for repnum in [1..Length( rep )] do
  1287.                 res := CentralCaseECAgWords( fhom.source, facN, cent[repnum], facU, rep[repnum],
  1288.                         rep[repnum]^-1 * (face[repnum] ^ conj[repnum]) );
  1289.                 cent[repnum] := res.centralizer;
  1290.                 rep[repnum]  := res.representative;
  1291.                 conj[repnum] := conj[repnum] * res.conjugand;
  1292.             od;
  1293.         else
  1294.             for repnum in [1..Length( rep )] do
  1295.                 res := GeneralCaseECAgWords( fhom.source, facN, cent[repnum], facU, rep[repnum],
  1296.                         rep[repnum]^-1 * (face[repnum] ^ conj[repnum]) );
  1297.                 cent[repnum] := res.centralizer;
  1298.                 rep[repnum]  := res.representative;
  1299.                 conj[repnum] := conj[repnum] * res.conjugand;
  1300.             od;
  1301.         fi;
  1302.     od;
  1303.     Apply( cent, x -> AgSubgroup( G, x, false ) );
  1304.  
  1305.     ec_ag_time := Runtime() - ec_ag_time;
  1306.     return rec(
  1307.         elements        := elems[Length( elabser )],
  1308.         representatives := rep,
  1309.         centralizers    := cent,
  1310.         conjugands      := conj
  1311.     );
  1312. end;
  1313.  
  1314.  
  1315. #############################################################################
  1316. ##
  1317. #F  MainEntryACAgWords( <G>, <U>, <elems>, <elabser> ) . . . . . . . . . . . .
  1318. ##
  1319. ##  returns
  1320. ##
  1321. ##      rec(
  1322. ##          areConjugate    := <boolean>,
  1323. ##          elements        := [ <agword> ],
  1324. ##          representative  := <agword>,
  1325. ##          centralizer     := <aggroups>,
  1326. ##          conjugands      := [ <agword> ]
  1327. ##      )
  1328. ##
  1329. MainEntryACAgWords := function( G, U, elems, elabser )
  1330.     local   tmpU, tmpe, fachom, fhom, felems, rep, cent, conj, facU,
  1331.             step, facN, face, ctrly, elnum, res, rep2, cent2, idx;
  1332.  
  1333.  
  1334.     if U.generators = [] then
  1335.         if Length( Set( elems ) ) = 1 then
  1336.             return rec(
  1337.                 areConjugate   := true,
  1338.                 elements       := elems,
  1339.                 representative := elems[1],
  1340.                 centralizer    := U,
  1341.                 conjugands     := List( elems, x -> U.identity )
  1342.             );
  1343.         else
  1344.             return rec( areConjugate := false );
  1345.         fi;
  1346.     fi;
  1347.  
  1348.     if Set( elems ) = [ G.identity ] then
  1349.         return rec(
  1350.             areConjugate   := true,
  1351.             elements       := elems,
  1352.             representative := elems[1],
  1353.             centralizer    := U,
  1354.             conjugands     := List( elems, x -> U.identity )
  1355.         );
  1356.     fi;
  1357.  
  1358.     ec_ag_time            := Runtime();
  1359.     ec_ag_central_cnt     := [ 0, 0 ];
  1360.     ec_ag_non_central_cnt := [ 0, 0, 0, 0, 0, 0 ];
  1361.  
  1362.     idx := 1;
  1363.     while IsSubgroup( elabser[idx+1], U ) do  idx := idx + 1;  od;
  1364.     while not false in List( elems, x -> x in elabser[idx+1] ) do
  1365.         idx := idx + 1;
  1366.     od;
  1367.  
  1368.     if idx <> 1 then
  1369.         elabser := Sublist( elabser, [idx..Length( elabser )] );
  1370.     fi;
  1371.     fachom := HomomorphismsSeries( G, elabser );
  1372.  
  1373.     felems := List( elems, x -> Image( fachom[1], x ) );
  1374.     rep    := felems[1];
  1375.     cent   := Image( fachom[1], U );
  1376.     conj   := List( elems, x -> cent.identity );
  1377.     cent   := cent.generators;
  1378.  
  1379.     if Length( Set( felems ) ) <> 1 then
  1380.         return rec( areConjugate := false );
  1381.     fi;
  1382.  
  1383.     tmpU := U;
  1384.     tmpe := elems;
  1385.     U     := [];
  1386.     elems := [];
  1387.     U[Length( elabser )]     := tmpU;
  1388.     elems[Length( elabser )] := tmpe;
  1389.     for step in Reversed( [2..Length( elabser )] ) do
  1390.         tmpU := Image( fachom[step], tmpU );
  1391.         U[step-1] := tmpU;
  1392.         tmpe := List( tmpe, x -> Image( fachom[step], x ) );
  1393.         elems[step-1] := tmpe;
  1394.     od;
  1395.  
  1396.     for step in [2..Length( elabser )] do
  1397.  
  1398.         fhom := fachom[step];
  1399.         facN := PreImage( fhom, TrivialSubgroup( fhom.range ) );
  1400.         facU := Igs( Intersection( U[step], facN ) );
  1401.         face := elems[step];
  1402.  
  1403.         rep  := FactorAgWord( rep, fhom.source.identity );
  1404.         Apply( cent, x -> FactorAgWord( x, fhom.source.identity ) );
  1405.         Apply( conj, x -> FactorAgWord( x, fhom.source.identity ) );
  1406.  
  1407.         if IsCentral( fhom.source, facN ) then
  1408.             for elnum in [1..Length( face )] do
  1409.                 res := CentralCaseECAgWords( fhom.source,
  1410.                         facN, cent, facU, rep, rep^-1 * (face[elnum] ^ conj[elnum]) );
  1411.  
  1412.                 conj[elnum] := conj[elnum] * res.conjugand;
  1413.                 if elnum = 1 then
  1414.                     rep2  := res.representative;
  1415.                     cent2 := res.centralizer;
  1416.                 elif rep2 <> res.representative then
  1417.                     return rec( areConjugate := false );
  1418.                 fi;
  1419.             od;
  1420.             rep  := rep2;
  1421.             cent := cent2;
  1422.         else
  1423.             for elnum in [1..Length( face )] do
  1424.                 res := GeneralCaseECAgWords( fhom.source,
  1425.                         facN, cent, facU, rep, rep^-1 * (face[elnum] ^ conj[elnum]) );
  1426.  
  1427.                 conj[elnum] := conj[elnum] * res.conjugand;
  1428.                 if elnum = 1 then
  1429.                     rep2  := res.representative;
  1430.                     cent2 := res.centralizer;
  1431.                 elif rep2 <> res.representative then
  1432.                     return rec( areConjugate := false );
  1433.                 fi;
  1434.             od;
  1435.             rep  := rep2;
  1436.             cent := cent2;
  1437.         fi;
  1438.     od;
  1439.     cent := AgSubgroup( G, cent, false );
  1440.  
  1441.     ec_ag_time := Runtime() - ec_ag_time;
  1442.     return rec(
  1443.         areConjugate   := true,
  1444.         elements       := elems[Length( elabser )],
  1445.         representative := rep,
  1446.         centralizer    := cent,
  1447.         conjugands     := conj
  1448.     );
  1449. end;
  1450.  
  1451.  
  1452. #############################################################################
  1453. ##
  1454. #F  AgGroupOps.ConjugacyTest( <U>, <elems> )  . . . . . . . . . . . . . . . .
  1455. ##
  1456. ##  returns
  1457. ##
  1458. ##      <false>
  1459. ##
  1460. ##    or
  1461. ##
  1462. ##      <conjugacy class>
  1463. ##      .elements   := <list>
  1464. ##      .conjugands := <list>
  1465. ##
  1466. AgGroupOps.ConjugacyTest := function( U, elems )
  1467.     local   G, elabser, natisom, res, class;
  1468.  
  1469.     if not IsAgGroup( U ) or not IsList( elems ) or Length( elems ) < 2 then
  1470.         Error( "usage: ConjugacyTest( <U>, <elems> )" );
  1471.     fi;
  1472.  
  1473.     G := Parent( U );
  1474.  
  1475.     if not IsElementaryAbelianAgSeries( G ) then
  1476.         elabser := ElementaryAbelianSeries( G );
  1477.         natisom := IsomorphismAgGroup( elabser );
  1478.         elabser := ElementaryAbelianSeries( natisom.range );
  1479.         res     := MainEntryACAgWords( natisom.range,
  1480.                     Image( natisom, U ), List( elems, x -> Image( natisom, x ) ), elabser );
  1481.  
  1482.         if res.areConjugate then
  1483.             Apply( res.elements, x -> PreImagesRepresentative( natisom, x ) );
  1484.             res.representative := PreImagesRepresentative( natisom, res.representative );
  1485.             res.centralizer    := PreImage( natisom, res.centralizer );
  1486.             Apply( res.conjugands, x -> PreImagesRepresentative( natisom, x ) );
  1487.             class := ConjugacyClass( U, res.representative );
  1488.             class.elements := res.elements;
  1489.             class.conjugands := res.conjugands;
  1490.             class.centralizer := res.centralizer;
  1491.  
  1492.             return class;
  1493.         else
  1494.             return false;
  1495.         fi;
  1496.     else
  1497.         elabser := ElementaryAbelianSeries( G );
  1498.         res     := MainEntryACAgWords( G, U, elems, elabser );
  1499.  
  1500.         if res.areConjugate then
  1501.             class := ConjugacyClass( U, res.representative );
  1502.             class.elements := res.elements;
  1503.             class.conjugands := res.conjugands;
  1504.             class.centralizer := res.centralizer;
  1505.  
  1506.             return class;
  1507.         else
  1508.             return false;
  1509.         fi;
  1510.     fi;
  1511.  
  1512.     return res;
  1513. end;
  1514.  
  1515.  
  1516. #############################################################################
  1517. ##
  1518. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1519. ##
  1520. ##  Local Variables:
  1521. ##  mode:               outline
  1522. ##  outline-regexp:     "#F\\|#V\\|#E"
  1523. ##  fill-column:        73
  1524. ##  fill-prefix:        "##  "
  1525. ##  eval:               (hide-body)
  1526. ##  End:
  1527. ##
  1528.