home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / ctpgrp.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  35.0 KB  |  909 lines
  1. #############################################################################
  2. ##
  3. #A  ctpgrp.g                    GAP library                Hans-Ulrich Besche
  4. ##
  5. #A  @(#)$Id: ctpgrp.g,v 3.17 1992/09/28 11:18:24 hbesche Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains those functions which calculate the irreducible
  10. ##  representaions and characters of supersolvable ag-groups with the 
  11. ##  algorithm published by Ulrich Baum, University of Bonn, Germany, 1991
  12. ##
  13. #H  $Log: ctpgrp.g,v $
  14. #H  Revision 3.17  1992/09/28  11:18:24  hbesche
  15. #H  fixed a bug.
  16. #H
  17. #H  Revision 3.16  1992/09/14  11:56:56  hbesche
  18. #H  Added some more comments
  19. #H
  20. #H  Revision 3.15  1992/09/09  15:25:32  hbesche
  21. #H  added some comments
  22. #H
  23. #H  Revision 3.14  1992/08/06  13:21:21  hbesche
  24. #H  minor changes
  25. #H
  26. #H  Revision 3.13  1992/07/15  09:53:16  hbesche
  27. #H  minor changes
  28. #H
  29. #H  Revision 3.12  1992/05/27  13:49:46  hbesche
  30. #H  Added posibility to surpress warnings in 'CharTablePGroup'
  31. #H
  32. #H  Revision 3.11  1992/05/25  14:28:01  hbesche
  33. #H  fixed a bug in 'SupersolvableResiduumAgGroup'
  34. #H
  35. #H  Revision 3.10  1992/04/07  16:15:32  jmnich
  36. #H  adapted to changes in the finite field module
  37. #H
  38. #H  Revision 3.9  1992/03/11  00:25:27  hbesche
  39. #H  Added dispatcher 'SupersolvableResiduum'
  40. #H
  41. #H  Revision 3.8  1992/03/08  14:46:35  hbesche
  42. #H  find the maximal factorgroup useable with the algorithm automaticaly
  43. #H
  44. #H  Revision 3.7  1992/03/04  18:43:53  hbesche
  45. #H  some problems with finding the correct normal subgroup
  46. #H
  47. #H  Revision 3.6  1992/03/03  20:46:19  hbesche
  48. #H  'FusionConjugacyClasses' should work even if there are no '.charTable'
  49. #H
  50. #H  Revision 3.5  1992/03/02  13:50:27  hbesche
  51. #H  fixed some bugs
  52. #H
  53. #H  Revision 3.4  1992/02/17  12:53:40  hbesche
  54. #H  the first parameter of subgroup should be a parent group
  55. #H
  56. #H  Revision 3.3  1992/02/13  15:09:23  hbesche
  57. #H  Use Size and ConjugacyClasses instead of AgGroupOps. ...
  58. #H
  59. #H  Revision 3.2  1992/02/13  14:04:14  hbesche
  60. #H  Hack in powermap to avoid an error in AreConjugated.
  61. #H
  62. #H  Revision 3.1  1992/02/10  10:25:39  martin
  63. #H  initial revision under RCS
  64. #H
  65. ##
  66.  
  67.  
  68. #############################################################################
  69. ##
  70. #F  RepresenatationsPGroup(G) . irr. representations of a supersolvable group
  71. ##
  72. ##  The matrices for the monomial representations are discribed as a record 
  73. ##  with entries perm and diag. E.g. the matrix (perm:=[3,1,2],diag:=[1,2,3])
  74. ##  is the product of 
  75. ##  [ . , . , 1 ]     [  Ee^1 ,   .   ,   .   ]   [   .   ,   .   ,  Ee^3 ]
  76. ##  [ 1 , . , . ]  *  [   .   ,  Ee^2 ,   .   ] = [  Ee^1 ,   .   ,   .   ]
  77. ##  [ . , 1 , . ]     [   .   ,   .   ,  Ee^3 ]   [   .   ,  Ee^2 ,   .   ]
  78. ##  where Ee:=E(g.exponent). If g.exponent is unknown then
  79. ##  Ee is E(Size(g)). The Representations are returned in a record with the
  80. ##  components exponent, lin for the list of linear representations and 
  81. ##  nonlin for the nonlinear representations. The linear representations are
  82. ##  given as the list of exponents of E(exponent) on the igs, the nonlinear
  83. ##  as matrices on the igs as discribed above.
  84. ##
  85. ##  This function is able to compute the representations of a solvable group
  86. ##  if it has an abelian normal subgroup with supersolvable factorgroup.
  87. ##  If the supersolvable residuum of the group is not abelian, the 
  88. ##  algorithm is applied to the factorgroup of g to the commutator subgroup
  89. ##  of the supersolvable residuum of g.
  90. ##
  91. ##  For this purpose a composition series of g is used, such that the 
  92. ##  maximal abelian and all nonabelian composition subgroups are normal.
  93. ##  Along this series increasing the representations of the composition
  94. ##  subgroups are calculated knowing the representations of the subgroup
  95. ##  below.
  96. ##
  97. ##  These representations have the property, that on every subgroup below
  98. ##  they restirct to a direct sum of irreducible representations, and
  99. ##  if two irreducible components are similar, they are allready equal.
  100. ##
  101. ##  For the computation of the representation of the subgroup G using
  102. ##  those of the subgroup N below the theorem of clifford is used. The
  103. ##  index [G:N] is prime, so for every representation F of N the induced
  104. ##  representation is irreducible or N could be extended to G in p
  105. ##  different ways.
  106. ##
  107. ##  In the first case the representation will be induced in the usall way.
  108. ##  If the induced representation is restircted to N again, it is the sum
  109. ##  of all the conjugates of R under the operation of G. For every conjugate
  110. ##  the equivalent representative from the list of representations of N
  111. ##  is found, and the induced of R is modified such that it restricts to
  112. ##  the direct sum of the representatives.
  113. ##
  114. ##  In the other case some matrix must be found which operates on R like
  115. ##  an element g form G\N. Modified by scalar matrices this matrix can
  116. ##  be used to construct the p different extensions.
  117. ##
  118. ##  For both purposes an algorithm is needed which tests (recursive)
  119. ##  wheather two representations F and D of the subgroups are equivalent,
  120. ##  and, if they are, returns a conjugating matrix. Therefore F and D should
  121. ##  be a representation of G. N should be the smaller composition subgroup
  122. ##  of primindex p. 
  123. ##  
  124. ##  If F and D are linear representation the recursion stops and the
  125. ##  representations are equivalent if they are equal.
  126. ##
  127. ##  If they are not linear, it is tested by locking at their permutation
  128. ##  structure if their restrictions to N are irreducible or not.
  129. ##
  130. ##  If both restrictions are irreducible, this test is recursive applied
  131. ##  to the restrictions. If they are irreducible, a conjugating matrix is
  132. ##  returned and it has just to be tested, if this matrix conjugates F
  133. ##  and D.
  134. ##
  135. ##  If both restrictions are reducible, pairs of equivalent irreducible
  136. ##  components of the restrictions are searched recursiv. The conjugation
  137. ##  matrix will be combinated from the permutation matrix of the conponents
  138. ##  and those conjugating matrices which transform the single components.
  139. ##
  140. RepresentationsPGroup := function(arg)
  141.  
  142.     local   mulmoma, opmoma, poweval, conrep, conlinrep, contest, isredrep,
  143.         liftreps, liftlinreps, liftrepsab, liftlinrepsab,
  144.         i, j, exp, replist, linreplist, coli, poli, lg, gexps, expl, igs,
  145.         flag, s, cs, ssr, hom, iso, t, k, g, rep,
  146.         i1, i2, i3, r, rr, rrr, aip, aid, bap, bad;
  147.  
  148.     # mulmoma returns the product of 2 monomial matrices
  149.     mulmoma:=function(a,b)
  150.     r:=rec(perm:=[],diag:=[]);
  151.     for i1 in [1..Length(a.perm)] do
  152.         r.perm[i1]:=b.perm[a.perm[i1]];
  153.         r.diag[b.perm[i1]]:=(b.diag[b.perm[i1]]+a.diag[i1]) mod exp;
  154.         od;
  155.     return r;
  156.     end;
  157.  
  158.     # opmoma returns a^-1*b*a for monomial matrices
  159.     opmoma:=function(b,a)
  160.     aip:=[]; aid:=[]; bap:=[]; bad:=[];
  161.     for i1 in [1..Length(a.perm)] do
  162.         aip[a.perm[i1]]:=i1; aid[i1]:=exp-a.diag[a.perm[i1]];
  163.         bad[a.perm[i1]]:=a.diag[a.perm[i1]]+b.diag[i1];
  164.         bap[i1]:=a.perm[b.perm[i1]];
  165.     od;
  166.     r:=rec(perm:=[],diag:=[]);
  167.     for i1 in [1..Length(a.perm)] do
  168.         r.perm[i1]:=bap[aip[i1]];
  169.         r.diag[bap[i1]]:=(bad[bap[i1]]+aid[i1]) mod exp;
  170.     od;
  171.     return r;
  172.     end;
  173.  
  174.     # poweval evalutes the representation rep on the p-th power of
  175.     # the conjugating element. The p-th power of this element is discribed
  176.     # by poli
  177.     poweval:=function(rep)
  178.     if poli=[] then
  179.         return rec( perm:=[1..Length(rep[1].perm)],
  180.                     diag:=[1..Length(rep[1].perm)]*0);
  181.     fi;
  182.     if Length(poli)=1 then return Copy(rep[poli[1]]); fi;
  183.     rr:=mulmoma(rep[poli[1]],rep[poli[2]]);
  184.     for i2 in [3..Length(poli)] do rr:=mulmoma(rr,rep[poli[i2]]); od;
  185.     return rr;
  186.     end;
  187.  
  188.     # conrep returns the conjugate representation of rep.
  189.     # The operation on rep is discribed by coli
  190.     conrep:=function(rep)
  191.     rr:=[];
  192.     for i2 in coli do
  193.         rrr:=rep[i2[1]];
  194.         for i3 in [2..Length(i2)] do rrr:=mulmoma(rrr,rep[i2[i3]]); od;
  195.         Add(rr,rrr);
  196.         od;
  197.     return rr;
  198.     end;
  199.  
  200.     # conlinrep does the same like conrep for a linear representation
  201.     conlinrep:=function(rep)
  202.     r:=[];
  203.     for i1 in coli do
  204.         rr:=rep[i1[1]];
  205.         for i2 in [2..Length(i1)] do
  206.             rr:=rr+rep[i1[i2]];
  207.             od;
  208.             Add(r,rr mod exp);
  209.         od;
  210.     return r;
  211.     end;
  212.  
  213.     # test if the restriction of the representation rep is reducible
  214.     isredrep:=function(rep,rp,b,p)
  215.     for i1 in [rp..Length(rep)] do
  216.         for i2 in [1..p]*b do
  217.             for i3 in [i2-b+1..i2] do
  218.                 if rep[i1].perm[i3]>i2 then return false; fi;
  219.                 od;
  220.             od;
  221.         od;
  222.     return true;
  223.     end;
  224.  
  225.     # contest tests whether r1 and r2 are conjugate representations.
  226.     # If it is so, the function returns a conjugating matrix.
  227.     # r1 and r2 must have the same degree and be nonlinear
  228.     contest:=function(r1,r2)
  229.     local   i, j, d, b, p, rp, Ap, flag, rr, rrr,
  230.         c, B, P, PP, X, XX, zr1, zr2, rr2, rrr2;
  231.     # d is the degree of the representations
  232.     d:=Length(r1[1].perm);
  233.     # check if r1=r2 for time improvement
  234.     if r1=r2 then return rec(perm:=[1..d],diag:=[1..d]*0); fi;
  235.     # search for maximal composition subgroup so that r1 and r2 are
  236.     # reducible
  237.     rp:=1; flag:=false;
  238.     repeat
  239.         rp:=rp+1; p:=gexps[lg-Length(r1)+rp-1]; b:=d/p;
  240.         if IsInt(b) then
  241.             if not isredrep(r1,rp,b,p) then
  242.                 if isredrep(r2,rp,b,p) then return false; fi;
  243.                 # if one of representations is reducible and the other
  244.                 # is not, they aren't equivalent
  245.             else
  246.                 if not isredrep(r2,rp,b,p) then
  247.                     return false;
  248.                 else flag:=true;
  249.                     fi;
  250.                 fi;
  251.             fi;
  252.     until flag;
  253.     # zr1 and zr2 will be lists of the irreducible components of r1 and r2
  254.     zr1:=[]; zr2:=[];
  255.     for i1 in [0..p-1]*b do
  256.         rr:=[]; rr2:=[];
  257.         for i2 in [rp..Length(r1)] do
  258.             rrr:=rec(perm:=[],diag:=[]); rrr2:=rec(perm:=[],diag:=[]);
  259.             for i3 in [i1+1..i1+b] do
  260.                 Add(rrr.perm,r1[i2].perm[i3]-i1);
  261.                 Add(rrr.diag,r1[i2].diag[i3]);
  262.                 Add(rrr2.perm,r2[i2].perm[i3]-i1);
  263.                 Add(rrr2.diag,r2[i2].diag[i3]);
  264.             od;
  265.             Add(rr,rrr); Add(rr2,rrr2);
  266.         od;
  267.         Add(zr1,rr); Add(zr2,rr2);
  268.     od;
  269.     # X is a list of those matrices conjugating the pairs of
  270.     # irreducible components, PP discribes the permutation on the set
  271.     # of components
  272.     X:=[]; PP:=rec(perm:=[],diag:=[1..d]*0);
  273.     if b=1 then
  274.         # the irreducible components are linear
  275.         for i in [1..p] do
  276.             j:=Position(zr2,zr1[i]);
  277.             # linear representations are equivalient if they are equal
  278.             if j=false then return false; fi;
  279.             # if their is a component which has no equivalent partner,
  280.             # then r1 and r2 aren't equivalent
  281.             Add(X,rec(perm:=[1],diag:=[0])); Add(PP.perm,j);
  282.         od;
  283.     else
  284.         # the irreducible components aren't linear
  285.         # searching for pairs of equivalent components
  286.         P:=[1..p];
  287.         for i in [1..p] do
  288.             flag:=true;
  289.             for j in P do
  290.                 if flag then 
  291.                     c:=contest(zr1[i],zr2[j]);
  292.                     if c<>false then
  293.                         RemoveSet(P,j); Add(X,c); flag:=false;
  294.                         Append(PP.perm,[(j-1)*b+1..j*b]);
  295.                     fi;
  296.                 fi;
  297.             od;
  298.             # zr1[i] is not equivalent to any zr2[j]
  299.             if flag then return false; fi;
  300.         od;
  301.     fi;
  302.     # find coefficients for the X[i] and construct conjugating matrix
  303.     j:=Copy(PP.perm); for i in [1..d] do PP.perm[j[i]]:=i; od;
  304.     P:=opmoma(r2[rp-1],PP); XX:=Copy(X[1]); c:=0;
  305.     for i in [1..p-1] do
  306.         Ap:=r1[rp-1].perm[i*b+1]-(i-1)*b; B:=rec(perm:=[],diag:=[]);
  307.         for j in [(i-1)*b+1..i*b] do
  308.             Add(B.perm,P.perm[j+b]-(i-1)*b); Add(B.diag,P.diag[j]);
  309.         od;
  310.         c:=c+mulmoma(B,X[i]).diag[Ap]-r1[rp-1].diag[Ap+(i-1)*b]
  311.             -X[i+1].diag[1];
  312.         Append(XX.perm,X[i+1].perm+b*i); Append(XX.diag,X[i+1].diag+c);
  313.     od;
  314.     XX:=mulmoma(PP,XX);
  315.     for i in [1..rp-2] do if opmoma(r2[i],XX)<>r1[i] then return false; fi; od;
  316.     return XX;
  317.     end;
  318.  
  319.     # liftreps does one iterativ step by constructing all representations
  320.     # of the next composition subgroup which arise from nonlinear
  321.     # representations
  322.     liftreps:=function(replist)
  323.     local   i, j, k, p, dim, d, used, flag, rep, con, result, D, g, c, X, r;
  324.     p:=gexps[lg-Length(replist[1])];
  325.     # used is a list mentioning all those representations which have be 
  326.     # used for the construction
  327.     used:=BlistList([1..Length(replist)],[]); result:=[]; d:=1;
  328.     while d<>false do
  329.         used[d]:=true; rep:=replist[d]; con:=conrep(rep); g:=poweval(rep);
  330.         c:=contest(rep,con);
  331.         if c<>false then
  332.             # rep can be extended in p different ways, c is a operating
  333.             # matrix
  334.             j:=mulmoma(c,c); for k in [3..p] do j:=mulmoma(c,j); od;
  335.             j:=j.diag[1]+g.diag[g.perm[1]]; r:=rec(perm:=[],diag:=[]);
  336.             # r:=c^-1
  337.             for k in [1..Length(c.perm)] do
  338.                 r.perm[c.perm[k]]:=k; r.diag[c.perm[k]]:=exp-c.diag[k];
  339.             od;
  340.             # adjust r by a scalar and contruct the p extensions
  341.             for k in (j/p)+[0..p-1]*(exp/p) do
  342.                 X:=[]; for i in r.diag do Add(X,(i+k) mod exp); od;
  343.                 Add(result,Concatenation([rec(perm:=r.perm,diag:=X)],rep));
  344.             od;
  345.         else
  346.             # rep could not be extended
  347.             dim:=Length(rep[1].diag); D:=Copy(rep); r:=(p-1)*dim;
  348.             X:=rec(perm:=[1..dim],diag:=[1..dim]*0);
  349.             # search for the representatives of the G-conjugates of rep
  350.             for j in [1..p-1]*dim do
  351.                 flag:=false; i:=1;
  352.                 repeat
  353.                     if (not used[i]) and
  354.                         (Length(con[1].perm)=Length(replist[i][1].perm)) then
  355.                         c:=contest(replist[i],con);
  356.                         if c<>false then
  357.                             Append(X.diag,c.diag); Append(X.perm,c.perm+j);
  358.                             for k in [1..Length(rep)] do
  359.                                 Append(D[k].diag,replist[i][k].diag);
  360.                                 Append(D[k].perm,replist[i][k].perm+j);
  361.                             od;
  362.                             # theese representatives are used
  363.                             used[i]:=true; flag:=true;
  364.                         fi;
  365.                     fi;
  366.                     i:=i+1;
  367.                 until flag;
  368.                 if j<>r then con:=conrep(con); fi;
  369.             od;
  370.             Add(result,Concatenation([opmoma(rec(perm:=Concatenation(g.perm+r,
  371.                 [1..r]),diag:=Concatenation([1..r]*0,g.diag)),X)],D));
  372.         fi;
  373.         d:=Position(used,false,d);
  374.     od;
  375.     return result;
  376.     end;
  377.  
  378.     # liftrepsab does the same like liftreps if the operation is trivial
  379.     liftrepsab:=function(replist)
  380.     local   result, rep, p, k, o;
  381.     p:=gexps[lg-Length(replist[1])]; result:=[];
  382.     for rep in replist do
  383.         o:=[1..Length(rep[1].perm)]*0;
  384.         for k in (poweval(rep).diag[1]/p)+[0..p-1]*(exp/p) do
  385.             Add(result,Concatenation([rec(perm:=
  386.                 [1..Length(rep[1].perm)],diag:=o+k)],rep));
  387.         od;
  388.     od;
  389.     return result;
  390.     end;
  391.  
  392.     # liftlinreps does the same like liftreps for linear represenations
  393.     liftlinreps:=function(replist)
  394.     local   i, j, k, d, p, pot, rep, con, used, lin, nonlin, D; 
  395.     used:=BlistList([1..Length(replist)],[]); lin:=[]; nonlin:=[]; d:=1;
  396.     p:=gexps[lg-Length(replist[1])];
  397.     while d<>false do
  398.         rep:=replist[d]; used[d]:=true; con:=conlinrep(rep);
  399.         if poli=[] then
  400.             pot:=0;
  401.         else
  402.             pot:=rep[poli[1]];
  403.             for i in [2..Length(poli)] do pot:=pot+rep[poli[i]]; od;
  404.             pot:=pot mod exp;
  405.         fi;
  406.         if con=rep then 
  407.             for i in (pot/p)+[0..p-1]*(exp/p) do
  408.                 Add(lin,Concatenation([i],rep));
  409.             od;
  410.         else
  411.             D:=[];
  412.             for i in rep do Add(D,rec(perm:=[1..p],diag:=[i])); od;
  413.             for j in [2..p] do
  414.                 i:=Position(replist,con);
  415.                 for k in [1..Length(rep)] do Add(D[k].diag,replist[i][k]); od;
  416.                 used[i]:=true;
  417.                 if j<>p then con:=conlinrep(con); fi;
  418.             od;
  419.             Add(nonlin,Concatenation([rec(perm:=Concatenation([p],
  420.                 [1..p-1]),diag:=Concatenation([1..p-1]*0,[pot]))],D));
  421.         fi;
  422.         d:=Position(used,false,d);
  423.     od;
  424.     return rec(lin:=Set(lin),nonlin:=nonlin);
  425.     end;
  426.  
  427.     # liftlinrepsab ...
  428.     liftlinrepsab:=function(replist)
  429.     local   i, p, pot, rep, result;
  430.     result:=[]; p:=gexps[lg-Length(replist[1])];
  431.     if poli=[] then
  432.         pot:=[0..p-1]*(exp/p);
  433.         for rep in replist do
  434.             for i in pot do Add(result,Concatenation([i],rep)); od;
  435.         od;
  436.     else
  437.         for rep in replist do
  438.             pot:=rep[poli[1]];
  439.             for i in [2..Length(poli)] do pot:=pot+rep[poli[i]]; od;
  440.             pot:=pot mod exp;
  441.             for i in (pot/p)+[0..p-1]*(exp/p) do
  442.                 Add(result,Concatenation([i],rep));
  443.             od;
  444.         od;
  445.     fi;
  446.     return result;
  447.     end;
  448.  
  449.  
  450.     # main procedure
  451.     g:=arg[1];
  452.     lg:=Length(Igs(g)); i:=1; igs:=Igs(g); cs:=CompositionSeries(g);
  453.     if IsBound(g.exponent) then exp:=g.exponent; else exp:=Size(g); fi;
  454.     # test and adjust the composition series
  455.     for i in [2..Length(cs)-1] do
  456.         if not (IsNormal(g,cs[i]) or IsAbelian(cs[i-1])) then
  457.             # the composition series of g is not suitable for the algorithm
  458.             replist:=[]; linreplist:=[]; expl:=[];
  459.             ssr:=SupersolvableResiduumAgGroup(g);
  460.             hom:=NaturalHomomorphism(g,g/DerivedSubgroup(ssr));
  461.             if ( Size(hom.kernel)>1 and Length(arg)=1 ) then
  462.     Print("#W  RepresentationsPGroup:not all representations known\n");
  463.                 fi;
  464.             iso:=IsomorphismAgGroup(ElementaryAbelianSeriesThrough(
  465.                 List(g.ds,x->Image(hom,x))));
  466.             iso.range.exponent:=exp;
  467.             # Apply function recursiv to the new group or factorgroup
  468.             rep:=RepresentationsPGroup(iso.range);
  469.             lg:=Length(iso.range.generators);
  470.             # look how the images of the original igs is written in the
  471.             # new group
  472.             for i in igs do
  473.                 k:=Exponents(iso.range,Image(iso,Image(hom,i)));
  474.                 t:=[];
  475.                 for j in [1..lg] do for i1 in [1..k[j]] do Add(t,j); od; od;
  476.                 Add(expl,t);
  477.                 od;
  478.             # find linear representations of original group
  479.             for i in rep.lin do
  480.                 s:=[];
  481.                 for j in expl do
  482.                     t:=0; for k in j do t:=t+i[k]; od; Add(s,t mod exp);
  483.                     od;
  484.                 Add(linreplist,s);
  485.                 od;
  486.             # find nonlinear representations of original group
  487.             for i in rep.nonlin do
  488.                 s:=[]; rr:=Length(i[1].perm);
  489.                 for j in expl do
  490.                     t:=rec(perm:=[1..rr],diag:=[1..rr]*0);
  491.                     for k in j do t:=mulmoma(t,i[k]); od; Add(s,t);
  492.                     od;
  493.                 Add(replist,s);
  494.                 od;
  495.             return rec(exponent:=exp,nonlin:=replist,lin:=linreplist);
  496.             fi;
  497.         od;
  498.     gexps:=[]; for i in igs do Add(gexps,RelativeOrderAgWord(i)); od;
  499.     # the representations of the smallest nontrivial compositionsubgroup
  500.     # are initialissed
  501.     linreplist:=List([0..gexps[lg]-1]*(exp/gexps[lg]),x->[x]); replist:=[];
  502.     # this loop runs along the composition series constructing the
  503.     # representations
  504.     for i in Reversed([1..lg-1]) do
  505.         # coli discribes the operation on the character of the normal subgroup
  506.         coli:=[]; flag:=true;
  507.         for j in [i+1..lg] do
  508.             expl:=igs[j]^igs[i]; if expl <> igs[j] then flag:=false; fi;
  509.             expl:=Exponents(g,expl);
  510.             Add(coli,Concatenation(List([i+1..lg],x->
  511.                 List([1..expl[x]],y->x-i))));
  512.         od;
  513.         expl:=Exponents(g,igs[i]^gexps[i]);
  514.         # poli discribes the p-th power of the conjugating element
  515.         poli:=Concatenation(List([i+1..lg],x->List([1..expl[x]],y->x-i)));
  516.         if flag then
  517.             # the operation is trivial
  518.             linreplist:=liftlinrepsab(linreplist);
  519.             if replist<>[] then replist:=liftrepsab(replist); fi;
  520.         else
  521.             # the operation is not trivial
  522.             if replist<>[] then replist:=liftreps(replist); fi;
  523.             j:=liftlinreps(linreplist); Append(replist,j.nonlin);
  524.             linreplist:=j.lin;
  525.         fi;
  526.     od;
  527.     return rec(exponent:=exp,nonlin:=replist,lin:=linreplist);
  528. end;
  529.  
  530.  
  531.  
  532. #############################################################################
  533. ##
  534. #F  MatRepresentationsPGroup( G [, int ] ). .  irr. matrix representations of
  535. #F  . . . . . . . . . . . . . . . . . . . . . . . . . . a supersolvable group
  536. ##
  537. ##  This function returns a list of homomorphism from the ag-group G 
  538. ##  to complex matrix groups realising the represenatations belonging
  539. ##  to the characters which can be computed by CharTablePGroup. If the
  540. ##  second argument is given, only the int-th representation is retuned.
  541. ##
  542. MatRepresentationsPGroup := function(arg)
  543.  
  544.     local   rep, mrep, i, j, k, t, r, e, mulmoma, m, al, Ee, lg, ew, evl,
  545.         ni, tt, g;
  546.  
  547.     mulmoma:=function(a,b)
  548.     r:=rec(perm:=[],diag:=[]);
  549.     for m in [1..al] do
  550.         r.perm[m]:=b.perm[a.perm[m]];
  551.         r.diag[b.perm[m]]:=(b.diag[b.perm[m]]+a.diag[m]);
  552.     od;
  553.     return r;
  554.     end;
  555.  
  556.     if Length(arg)>2 or not IsAgGroup(arg[1]) or
  557.         Length(arg)=2 and not IsInt(arg[2]) then
  558.         Error("MatRepresentationsPGroup:usage( <ag-group> )\n",
  559.               "                                     ( <ag-group> , <int> )\n");
  560.         fi;
  561.     g:=arg[1]; rep:=RepresentationsPGroup(g); mrep:=[]; e:=E(rep.exponent);
  562.     Ee:=E(rep.exponent); lg:=Length(Igs(g)); mrep:=[]; evl:=[];
  563.     # look how the generators are expressed in the igs
  564.     for i in g.generators do
  565.         ew:=Exponents(g,i); t:=[];
  566.         for j in [1..lg] do for k in [1..ew[j]] do Add(t,j); od; od;
  567.         Add(evl,t);
  568.     od;
  569.     if Length(arg)=2 then
  570.         if Length(rep.lin)<arg[2] then 
  571.             rep.nonlin:=[rep.nonlin[arg[2]-Length(rep.lin)]]; rep.lin:=[];
  572.         else
  573.             rep.nonlin:=[]; rep.lin:=[rep.lin[arg[2]]];
  574.             fi;
  575.         fi;
  576.     # get linear representations
  577.     for i in rep.lin do
  578.         ni:=[];
  579.         for j in evl do
  580.             t:=0; for k in j do t:=t+i[k]; od; Add(ni,[[Ee^t]]);
  581.             od;
  582.         Add(mrep,ni);
  583.     od;
  584.     # get nonlinear representations
  585.     for i in rep.nonlin do
  586.         ni:=[]; al:=Length(i[1].perm);
  587.         for j in evl do 
  588.             t:=rec(perm:=[1..Length(i[1].perm)]); t.diag:=t.perm*0;
  589.             for k in j do t:=mulmoma(t,i[k]); od;
  590.             tt:=List(t.perm,x->0*t.perm);
  591.             # transform into a cyclotomic matrix
  592.             for k in [1..Length(t.perm)] do
  593.                 tt[k][t.perm[k]]:=Ee^t.diag[t.perm[k]];
  594.             od;
  595.             Add(ni,tt);
  596.         od;
  597.         Add(mrep,ni);
  598.     od;
  599.     if Length(arg)=2 then
  600.         return GroupHomomorphismByImages(g,MatGroup(mrep[1],CF(rep.exponent)),
  601.             g.generators,mrep[1]);
  602.         fi;
  603.     return List(mrep,x->GroupHomomorphismByImages(g,MatGroup(x,
  604.         CF(rep.exponent)),g.generators,x));
  605. end;
  606.  
  607.  
  608.  
  609. #############################################################################
  610. ##
  611. #F  CharTablePGroup(G)  . . . . . .  character table of a supersolvable group
  612. ##
  613. ##  This function calculates the character table of an ag-represented group
  614. ##  G, if there is an abelian normal subgroup N such that G/N is
  615. ##  supersolvable. If this is not, the characters of the largest factorgroup
  616. ##  with this property are computed and inflated to G. In this case a 
  617. ##  warning is printed out. The character table is returned and fixed in
  618. ##  G.charTable. If there are more then one arguments, they are ignored
  619. ##  but no warnings are printed.
  620. ##
  621. CharTablePGroup := function(arg)
  622.  
  623.     local   ecs, evl, lg, Ee, rep, t, tt, i, j, k, mulmoma, ew, ni, r, m,
  624.         al, p, pl, powermap, tbl, g;
  625.  
  626.     mulmoma:=function(a,b)
  627.     r:=rec(perm:=[],diag:=[]);
  628.     for m in [1..al] do
  629.         r.perm[m]:=b.perm[a.perm[m]];
  630.         r.diag[b.perm[m]]:=(b.diag[b.perm[m]]+a.diag[m]);
  631.     od;
  632.     return r;
  633.     end;
  634.  
  635.     g:=arg[1];
  636.     lg:=Length(Igs(g)); evl:=[]; ecs:=ConjugacyClasses(g);
  637.     if IsBound(g.charTable) then
  638.         tbl:=g.charTable;
  639.     else
  640.         tbl:=rec(order:=Size(g),centralizers:=[],classes:=[], orders:=[],
  641.             irreducibles:=[],operations:=CharTableOps);
  642.         for i in ecs do
  643.             j:=Size(i); Add(tbl.orders,Order(g,i.representative));
  644.             Add(tbl.centralizers,tbl.order/j); Add(tbl.classes,j);
  645.             od;
  646.         fi;
  647.     for i in ecs do
  648.         Elements(i); ew:=Exponents(g,i.representative); t:=[];
  649.         for j in [1..lg] do for k in [1..ew[j]] do Add(t,j); od; od;
  650.         Add(evl,t);
  651.         od;
  652.     if not IsBound(g.exponent) then g.exponent:=Lcm(Set(tbl.orders)); fi;
  653.     if Length(arg)=1 then 
  654.         rep:=RepresentationsPGroup(g);
  655.     else
  656.         rep:=RepresentationsPGroup(g,1);
  657.         fi;
  658.     Ee:=E(rep.exponent);
  659.     for i in rep.lin do
  660.         ni:=[];
  661.         for j in evl do t:=0; for k in j do t:=t+i[k]; od; Add(ni,Ee^t); od;
  662.         if not ni in tbl.irreducibles then Add(tbl.irreducibles,ni); fi;
  663.     od;
  664.     for i in rep.nonlin do
  665.         ni:=[]; al:=Length(i[1].perm);
  666.         for j in evl do 
  667.             t:=rec(perm:=[1..Length(i[1].perm)]); tt:=0; t.diag:=t.perm*0;
  668.             for k in j do t:=mulmoma(t,i[k]); od;
  669.             for k in [1..Length(i[1].perm)] do
  670.                 if t.perm[k]=k then tt:=tt+Ee^t.diag[k]; fi;
  671.             od;
  672.             Add(ni,tt);
  673.         od;
  674.         if not ni in tbl.irreducibles then Add(tbl.irreducibles,ni); fi;
  675.     od;
  676.     if not IsBound(tbl.powermap) then
  677.         tbl.powermap:=[]; pl:=Set(Factors(tbl.order));
  678.         for i in pl do
  679.             tbl.powermap[i]:=[];
  680.             for j in ecs do
  681.                 k:=j.representative^i; p:=0; t:=Order(g,k);
  682.                 repeat p:=p+1; until t=tbl.orders[p] and k in ecs[p];
  683.                 Add(tbl.powermap[i],p);
  684.                 od;
  685.             od;
  686.         fi;
  687.     if not IsBound(tbl.name) then 
  688.         if IsBound(g.name) then
  689.             tbl.name:=g.name;
  690.         elif IsBound(Parent(g).name) then
  691.             tbl.name:=Parent(g).name;
  692.             for k in g.generators do
  693.                 tbl.name:=ConcatenationString(tbl.name,"_",String(k));
  694.                 od;
  695.         else 
  696.             tbl.name:="";
  697.             fi;
  698.         fi;
  699.     if ( Sum(List(tbl.irreducibles,x->x[1]*x[1])) <> tbl.order
  700.             and Length(arg)=1) then
  701.         Print("#W  CharTablePGroup:incomplete CharTable\n");
  702.         fi;
  703.     g.charTable:=tbl; g.charTable.group:=g;
  704.     return g.charTable;
  705. end;
  706.  
  707.  
  708. #############################################################################
  709. ##
  710. #F  FusionConjugacyClasses. . . . . . . . . . . . . . . . . .construct fusion
  711. ##
  712. ##  The fusion of the conjugacy classes of the two groups d (domain) and
  713. ##  r (range) is returned as a list of the positions of the fusionclass in
  714. ##  the list of the classes of r. If both groups have a .charTable entry, the
  715. ##  fusion is added in the .charTable components.
  716. ## 
  717. FusionConjugacyClasses := function( d, r )
  718.  
  719.     local dc, rc, i, k, t, p, f, h, o, type;
  720.  
  721.     if not IsGroup(d) or not IsGroup(r) then
  722.         Error("usage: FusionConjugacyClasses( <subgroup>, <group>      )\n",
  723.        "              FusionConjugacyClasses( <group>   , <factorgroup>)\n");
  724.         fi;
  725.     dc:=ConjugacyClasses(d); rc:=ConjugacyClasses(r);
  726.     for i in rc do Elements(i); od; f:=[];
  727.     if Parent(d)=Parent(r) then 
  728.         if IsBound(r.charTable) then
  729.             o:=r.charTable.orders;
  730.         else
  731.             o:=List(rc,x->Order(r,x.representative));
  732.             fi;
  733.         for i in dc do
  734.             k:=i.representative; t:=Order(r,k); p:=0;
  735.             repeat p:=p+1; until t=o[p] and k in rc[p].elements; Add(f,p);
  736.         od;
  737.         type:="normal";
  738.     else
  739.         h:=NaturalHomomorphism(d,r);
  740.         for i in dc do
  741.             k:=Image(h,i.representative); p:=0;
  742.             repeat p:=p+1; until k in rc[p].elements; Add(f,p);
  743.             od;
  744.         type:="factor";
  745.         fi;
  746.     if IsBound(d.charTable) and IsBound(r.charTable) then
  747.         if not IsBound(d.charTable.fusions) then d.charTable.fusions:=[]; fi;
  748.         Add(d.charTable.fusions,rec(name:=r.charTable.name,map:=f,type:=type));
  749.         if not IsBound(r.charTable.fusionsource) then
  750.             r.charTable.fusionsource:=[];
  751.             fi;
  752.         Add(r.charTable.fusionsource,d.charTable.name);
  753.         fi;
  754.     return f;
  755.     end;
  756.  
  757.  
  758.  
  759. ##############################################################################
  760. ##
  761. #F  SupersolvableResiduumAgGroup . . . . . . . . . . . . . . . . . . . . . . .
  762. ##
  763. ##  The algorithm constricts a descending series of normal subgroups with
  764. ##  supersolvable factorgroup form the group to the supersolvable residuum.
  765. ##  Any refining subgroup for this series is normal. One step of the
  766. ##  algorithm does the following. N is a normal subgroup of G with
  767. ##  supersolvable factorgroup. Then the commutatorfactorgroup is constructed
  768. ##  and decomposed in its Sylowgroups. For every Sylowgroup the
  769. ##  Frattinifactorgroup is found. This is a G-module. Those submodules with
  770. ##  1-dimensional factor are wanted. For this case the eigenspaces of the
  771. ##  dual submodule are calculated and the preimages of their orthogonal
  772. ##  spaces are used to construct new normal subgoups with supersolvable
  773. ##  factorgroup. If no eigenspaces is found within one step, the residdum
  774. ##  is reached.
  775. ##  An entry '.ds' is added to the grouprecord such that any composition
  776. ##  series throgh '.ds' from the group down to the residuum is a chief series.
  777. ## 
  778. SupersolvableResiduumAgGroup := function(g)
  779.  
  780.     local   ssr, assr, dh, df, p, ph, ff, mg, fs, np, gen, cf, pu, v, ve, b,
  781.         i, z, ints, o, s, gs, idm, ii, vsl, nvsl, nullspace, iii,
  782.         iiii, iiiii, tmp, tmp2, pp;
  783.  
  784.     g.ds:=[g];
  785.     if IsAbelian(g) then Add(g.ds,TrivialSubgroup(g)); return g.ds[2]; fi;
  786.     # find small generating system 'gs' of g
  787.     gs:=[g.generators[1]];
  788.     p:=2; o:=Order(g,g.generators[1]);
  789.     repeat
  790.         s:=Subgroup(Parent(g),Concatenation(gs,[g.generators[p]]));
  791.         if Size(s)>o then
  792.             Add(gs,g.generators[p]); o:=Size(s);
  793.             fi;
  794.         p:=p+1;
  795.     until s=g;
  796.     ssr:=DerivedSubgroup(g); Add(g.ds,ssr);
  797.     repeat
  798.         # remember the last candidate  as 'assr'
  799.         assr:=ssr; ssr:=DerivedSubgroup(assr);
  800.         dh:=NaturalHomomorphism(assr,assr/ssr);
  801.         # df is the commutatorfactorgroup 'assr/ssr'
  802.         df:=dh.range; fs:=Factors(Size(df));
  803.         # gen collects the generators for the next candidate
  804.         gen:=Copy(df.generators);
  805.         for p in Set(fs) do
  806.             np:=Product(Filtered(fs,x->x<>p));
  807.             pp:=Product(Filtered(fs,x->x=p));
  808.             # pu is the p-sylow-subgroup of the commutatorfactorgroup
  809.             pu:=Subgroup(df,List(df.generators,x->x^np));
  810.             # remove the p-part from the generatorlist 'gen'
  811.             gen:=List(gen,x->x^pp);
  812.             # add the agemo_1 to the generatorlist
  813.             tmp:=List(Igs(pu),x->x^p);
  814.             Append(gen,tmp);
  815.             ph:=NaturalHomomorphism(pu,pu/Subgroup(df,tmp));
  816.             # ff is the frattini factorgroup
  817.             ff:=ph.range;
  818.             if Size(ff)>p then
  819.                 idm:=IdentityMat(Length(Factors(Size(ff))),GF(p));
  820.                 ints:=IntegerTable(GF(p));
  821.                 # mg is the list of matrices for the operation of g 
  822.                 # on the dual space of the module
  823.                 mg:=Filtered(List(gs,x->Transposed(List(ff.generators,
  824.                     y->Z(p)^0*Exponents(ff,Image(ph,Image(dh,
  825.                     PreImagesRepresentative(dh,PreImagesRepresentative
  826.                     (ph,y))^x)))))^-1),z->z<>idm);
  827.                 # vsl is a list of all the simultanous eigenspaces
  828.                 vsl:=[VectorSpace(idm,GF(p))];
  829.                 for ii in mg do
  830.                     nvsl:=[];
  831.                     # all eigenvalues of ii will be used 
  832.                     for iii in List(Filtered(Factors(
  833.                             CharacteristicPolynomial(ii)),x->Length(
  834.                             x.coefficients)=2),y->-y.coefficients[1]) do
  835.                         nullspace:=NullspaceMat(ii-iii*idm);
  836.                         if nullspace <>[] then 
  837.                             nullspace:=VectorSpace(nullspace,GF(p));
  838.                             for iiii in vsl do
  839.                                 iiiii:=Intersection(iiii,nullspace);
  840.                                 if Length(iiiii.generators)>0 then
  841.                                     Add(nvsl,iiiii);
  842.                                     fi;
  843.                                 od;
  844.                             fi;
  845.                         od;
  846.                     vsl:=nvsl;
  847.                     od;
  848.                 # now calculate the dual spaces of the eigensp.
  849.                 if vsl=[] then
  850.                     Append(gen,pu.generators);
  851.                 else
  852.                     # tmp collects the eigenspaces
  853.                     tmp:=[];
  854.                     for ii in vsl do
  855.                         # tmp2 will be the dualspace base
  856.                         tmp2:=[];
  857.                         Append(tmp,ii.generators);
  858.                         nullspace:=NullspaceMat(Transposed(tmp));
  859.                         for v in nullspace do
  860.                             # construct a group element corresponding to
  861.                             # the basis element of the submodul 
  862.                             ve:=ff.identity;
  863.                             for i in [1..Length(v)] do
  864.                                 z:=LogVecFFE(v,i);
  865.                                 if z<>false then
  866.                                     ve:=ve*ff.generators[i]^ints[z+1];
  867.                                     fi;
  868.                                 od;
  869.                             Add(tmp2,PreImagesRepresentative(ph,ve));
  870.                             od;
  871.                         Add(g.ds,PreImage(dh,Subgroup(df,
  872.                             Concatenation(tmp2,gen))));
  873.                         od;
  874.                     Append(gen,tmp2);
  875.                     fi;
  876.             else
  877.                 Add(g.ds,PreImage(dh,Subgroup(df,gen)));
  878.                 fi;
  879.             od;
  880.         # generate the new candidate and clear-up the generators
  881.         ssr:=Subgroup(Parent(g),Igs(PreImage(dh,Subgroup(df,gen))));
  882.     until Size(ssr)=1 or assr=ssr;
  883.     return ssr;
  884.     end;
  885.  
  886.  
  887.  
  888. #############################################################################
  889. ##
  890. #F  SupersolvableResiduum . . . . . . . . . . . . . . . . . . . . . . . . . .
  891. ##
  892. SupersolvableResiduum := function( g )
  893.  
  894.     local ssr;
  895.     if not IsGroup(g) then
  896.         Error("usage:SupersolvableResiduum( <group> )");
  897.     elif IsBound(g.supersolvableResiduum) then
  898.         return g.supersolvableResiduum;
  899.     elif IsBound(g.operations.SupersolvableResiduum) then
  900.         ssr:=g.operations.SupersolvableResiduum(g);
  901.     elif IsAgGroup(g) then
  902.         ssr:=SupersolvableResiduumAgGroup(g);
  903.     else
  904.         Error("sorry, 'SupersolvableResiduum' not aplicable for this group");
  905.         fi;
  906.     g.supersolvableResiduum:=ssr;
  907.     return ssr;
  908.     end;
  909.