home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / cdaggrp.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  29.5 KB  |  837 lines
  1. #############################################################################
  2. ##
  3. #A  cdaggrp.g                   GAP library                Hans Ulrich Besche
  4. ##
  5. #A  @(#)$Id: cdaggrp.g,v 3.1 1992/10/29 15:33:52 sam Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. #H  $Log: cdaggrp.g,v $
  10. #H  Revision 3.1  1992/10/29  15:33:52  sam
  11. #H  changed local function 'number'
  12. #H
  13. #H  Revision 3.0  1992/10/28  13:58:22  goetz
  14. #H  initial revision under RCS
  15. #H
  16. ##
  17. ##  This file contains the functions for calculating the degrees of the
  18. ##  irreducible characters above an algebraic closed filed of
  19. ##  characteristic zero or p of an arbitrary solvable group. The used
  20. ##  algorithm is from S. B. Conlon, published in the J. Symbolic
  21. ##  Computation (1990) 9, 551-570. This algorithm is generalized to
  22. ##  calculate the irreducible characters of a supersolvable group, using
  23. ##  an ideas like in the article from S.B. Conlon in the same journal
  24. ##  on the pages 535-550.
  25. ##
  26.  
  27. ##  
  28. ##  The main theoretic tool for the algorithm is Clifford theory. One
  29. ##  recursive step of the algorithm will be discribed. Given are a solvable
  30. ##  group G, a central element z and the characteristic q of the used
  31. ##  algebraic closed filed F.  An hypothetical faithfull linear charakter
  32. ##  lambda of <z> is concerned. The character degrees (G,z,q) of those
  33. ##  irreducibles of G will be calculated, which restirict on <z> to a
  34. ##  multiple of lambda.
  35. ##  If G is abelian, the degrees could be computed imeaditly.
  36. ##  If G is not abelian, a normal subgroup N with the property that N/<z>
  37. ##    is a chief factor of G is choosen.
  38. ##    If N is not abelian, a subgroup L is calculated such that the
  39. ##      intersection of N and L is <z>, L centralizes N and NL=G. The order
  40. ##      of the chief factor N/<z> is a square r^2. The character degrees of
  41. ##      the (G,z,q) are the degrees of the (L,z,q), each multiplied with r.
  42. ##    If N is abelian, the size of N/<z> is a primepower p^i. P will be the
  43. ##      p-Sylowsubgroup of N. According to Clifford's theorem stabilizers S
  44. ##      and representatives for the orbits of G on those characters of P
  45. ##      which restirct to lambda|_P are calculated. For this purpose 3
  46. ##      cases for the structure of P must be differenciated.
  47. ##      If z is a p'-element the 1-character of P builds up one orbit.
  48. ##        The character degress of (G/P,zP,q) must be found.
  49. ##        The operation on the nontrivial characters of P is the dual
  50. ##        operation too the operation on the elementary abelian subgroup
  51. ##        (or vectorspace) P. For every representative the
  52. ##        kernel K must be found, and the degrees (S/K,zK,q) must
  53. ##        be calculated recursive. All those degrees will be returned.
  54. ##      In the next case P is cyclic and not of primeorder. Let y be a
  55. ##        generator of P. If y is central in G, p copies of the character
  56. ##        degrees of (G,zy,q) will be returned. Else the degrees of 
  57. ##        (C_G(y),zy,q) should be found, each multiplied by p and
  58. ##        returned.
  59. ##      Now P is not cyclic and z is no p'-element, the omega_1 O of P must
  60. ##        be found. As in the last case the dual operation too the
  61. ##        operation on O is needed. For every representative it must be
  62. ##        checked if it restricts to O as lambda|_O. For those which
  63. ##        restirct so the degrees (S/K,zK,q) are calculated and returned.
  64. ##
  65.  
  66.  
  67. ###########################################################################  
  68. ##
  69. #F  con_col_list. . . . . . . . . . . . . . . . . . . . . . . . . . . local
  70. ##
  71. ##  returns the concatenation of two collected lists.
  72. ##
  73. con_col_list := function(a,b)
  74.  
  75.     local d, p, i, j;
  76.  
  77.     d:=Union(List(a,x->[x[1],0]),List(b,x->[x[1],0]));
  78.     for j in [a,b] do 
  79.         p:=0;
  80.         for i in j do
  81.             repeat p:=p+1; until d[p][1]=i[1];
  82.             d[p][2]:=d[p][2]+i[2];
  83.             od;
  84.         od;
  85.     return d;
  86.     end;
  87.  
  88.  
  89.  
  90. ###########################################################################
  91. ##
  92. #F  f2_orbit_priv . . . . . . . . . . . . . . . . . . . . . . . . . . local
  93. ##
  94. ##  returns the orbit and the stabilizer of an element under the linear
  95. ##  operation of the ag-generators gens on an F2-space.
  96. ##
  97. f2_orbit_priv := function( gens, linear, elem )
  98.     local orbit, torbit, stab, gen, orbpos, actor, pv, gn, p, i, j, k;
  99.  
  100.  
  101.     orbit := [ elem ]; stab := []; pv := [ 1 ]; gn := [];
  102.     for i in Reversed( [1..Length( gens )] ) do
  103.         gen    := gens[i];
  104.         orbpos := Position( orbit, elem * linear[i] );
  105.         if orbpos = false then
  106.             p := RelativeOrderAgWord( gen );
  107.             Add( pv, pv[Length( pv )] * p );
  108.             Add( gn, i );
  109.             torbit := ShallowCopy( orbit );
  110.             for j in [1..p-1] do
  111.                 for k in [1..Length( torbit )] do
  112.                     torbit[k] := torbit[k] * linear[i];
  113.                 od;
  114.                 Append( orbit, torbit );
  115.             od;
  116.         elif orbpos = 1 then   Add( stab, gen );
  117.         else
  118.             actor  := gen^0;
  119.             orbpos := orbpos - 1;
  120.             j      := Length( pv ) - 1;
  121.             while orbpos <> false and j > 0 do
  122.                 actor  := gens[gn[j]] ^ QuoInt( orbpos, pv[j] ) * actor;
  123.                 orbpos := orbpos mod pv[j];
  124.                 j      := j - 1;
  125.             od;
  126.             Add( stab, gen / actor );
  127.         fi;
  128.     od;
  129.     return rec(
  130.         orbit       := orbit,
  131.         stabilizer  := Reversed( stab ));
  132.     end;
  133.  
  134.  
  135. ###########################################################################
  136. ##
  137. #F  f2_orbits_priv. . . . . . . . . . . . . . . . . . . . . . . . . . local
  138. ##
  139. ##  returns representatives and stabilizers of the linear operation of
  140. ##  the ag-generators on the f2-space.
  141. ##
  142. f2_orbits_priv := function( gens, linear )
  143. local space, reps, stabs, orb, v, w, next, number, element, plist, dim, fr;
  144.  
  145.     number := function( v )
  146.     local i, r;
  147.         r:=0;
  148.         v:= IntFFE( v );
  149.         for i in [ 1 .. dim ] do 
  150.           r := 2 * r + v[i];
  151.         od;
  152.         return r;
  153.         end;
  154.  
  155.     element := function( n )
  156.     local i, c;
  157.         return fr * Coefficients( plist, n );
  158.         end;
  159.  
  160.     fr := Z(2); dim := Length( linear[ 1 ]);
  161.     plist := List( [1..dim], x -> 2 ); reps := []; stabs := [];
  162.     space := BlistList( [1..2^dim-1], [] ); next := 1;
  163.     while next <> false do
  164.         v     := element( next );
  165.         orb   := f2_orbit_priv( gens, linear, v );
  166.         for w in orb.orbit do
  167.             space[number( w )] := true;
  168.         od;
  169.         Add( reps, v );
  170.         Add( stabs, orb.stabilizer );
  171.         next := Position( space, false, next );
  172.     od;
  173.     return rec(
  174.         representatives := reps,
  175.         stabilizers     := stabs);
  176.     end;
  177.  
  178.  
  179. ###########################################################################
  180. ##
  181. #F  ls_orbit_priv . . . . . . . . . . . . . . . . . . . . . . . . . . local
  182. ##
  183. ##  returns the orbit and the stabilizer of an 1-dimensional subspace under
  184. ##  the linear operation of the ag-generators gens.
  185. ##
  186. ls_orbit_priv := function( gens, linear, elem )
  187.     local orbit, torbit, stab, gen, orbpos, actor, pv, gn, p, i, j, k,
  188.         dim, normvector;
  189.  
  190.     normvector := function ( v )
  191.     local i;
  192.  
  193.         for i in [1..dim] do
  194.             if v[ i ] <> 0 * v[i] then
  195.                 return ( 1 / v[ i ]) * v;
  196.                 fi;
  197.             od;
  198.         end;
  199.     
  200.     dim := Length( elem ); elem := normvector( elem ); orbit := [ elem ];
  201.     stab := []; pv := [ 1 ]; gn := [];
  202.     for i in Reversed( [1..Length( gens )] ) do
  203.         gen    := gens[i];
  204.         orbpos := Position( orbit, normvector ( elem * linear[i] ));
  205.         if orbpos = false then
  206.             p := RelativeOrderAgWord( gen );
  207.             Add( pv, pv[Length( pv )] * p );
  208.             Add( gn, i );
  209.             torbit := ShallowCopy( orbit );
  210.             for j in [1..p-1] do
  211.                 for k in [1..Length( torbit )] do
  212.                      torbit[k] := normvector ( torbit[k] * linear[i] );
  213.                 od;
  214.                 Append( orbit, torbit );
  215.             od;
  216.         elif orbpos = 1 then   Add( stab, gen );
  217.         else
  218.             actor  := gen^0;
  219.             orbpos := orbpos - 1;
  220.             j      := Length( pv ) - 1;
  221.             while orbpos <> false and j > 0 do
  222.                 actor  := gens[gn[j]] ^ QuoInt( orbpos, pv[j] ) * actor;
  223.                 orbpos := orbpos mod pv[j];
  224.                 j      := j - 1;
  225.             od;
  226.             Add( stab, gen / actor );
  227.         fi;
  228.     od;
  229.     return rec(
  230.         orbit       := orbit,
  231.         stabilizer  := Reversed( stab ));
  232.     end;
  233.     
  234.     
  235. ###########################################################################
  236. ##
  237. #F  ls_orbits_priv. . . . . . . . . . . . . . . . . . . . . . . . . . local
  238. ##
  239. ##  returns representatives and stabilizers of the linear operation of
  240. ##  the ag-generators on the the 1-dimensional subspaces.
  241. ##
  242. ls_orbits_priv := function( gens, linear )
  243.     local space, reps, stabs, orb, v, w, next, p, fr, 
  244.         weightseq, number, element, plist, dim;
  245.     number := function( v )
  246.     local i, r, j;
  247.     
  248.         for i in [1..dim] do 
  249.             if v[ i ] <> 0 * v[i] then
  250.                 r := 0;
  251.                 for j in [i+1..dim] do
  252.                     r := p * r + IntFFE( v[ j ]);
  253.                     od;
  254.                 return weightseq[ i ] + r;
  255.                 fi;
  256.             od;
  257.         end;
  258.  
  259.     element := function( n )
  260.     local i, c;
  261.  
  262.         for i in [1..dim] do
  263.             if n < weightseq [ i+1 ] then 
  264.                 c := Coefficients( plist, n - weightseq[ i ]);
  265.                 c[ i ] := 1;
  266.                 return fr * c;
  267.                 fi;
  268.             od;
  269.         end;
  270.  
  271.     p      := CharFFE( linear[ 1 ][ 1 ][ 1 ]);
  272.     fr     := linear[ 1 ][ 1 ][ 1 ]^0;
  273.     dim    := Length( linear[ 1 ]);
  274.     plist  := List( [1..dim], x -> p );
  275.     weightseq := List([0..dim], x -> ( p^dim - p^( dim-x)) / ( p-1 ) + 1 );
  276.     reps   := [];
  277.     stabs  := [];
  278.     space := BlistList( [1..weightseq[ dim ]], [] );
  279.     next  := 1;
  280.     while next <> false do
  281.         v     := element( next );
  282.         orb   := ls_orbit_priv( gens, linear, v );
  283.         for w in orb.orbit do
  284.             space[number( w )] := true;
  285.         od;
  286.         Add( reps, v );
  287.         Add( stabs, orb.stabilizer );
  288.         next := Position( space, false, next );
  289.     od;
  290.     return rec(
  291.         representatives := reps,
  292.         stabilizers     := stabs);
  293.     end;
  294.  
  295.  
  296.  
  297. ###########################################################################
  298. ##
  299. #F  omega_1_priv( G ) . . . . . . . . . . . . . . . . . . . . . . . . local
  300. ##
  301. ##  G should be an abelian ag-representated p-group.
  302. ##
  303. omega_1_priv := function(g)
  304.  
  305.     local    i, j, rel, rl, rc, ng, ml, mc, m, k, q, p;
  306.  
  307.     p:=RelativeOrder(g.generators[1]); ng:=Copy(Igs(g));
  308.     # rel is the relation matrix of g
  309.     rel:=List(ng,x->List(ng,function(y) if x=y then return p;
  310.         else return 0; fi; end)-Exponents(g,x^p));
  311.     # rl, rc are the remainding lines and columns of rel to be used
  312.     rl:=[1..Length(ng)]; rc:=[1..Length(ng)];
  313.     while Length(rl)>1 do
  314.         # find empty column, find min entry
  315.         m:=AbsInt(Maximum(rel[rl[1]]))+1;
  316.         for i in rl do
  317.             for j in rc do
  318.                 if rel[i][j] <> 0 and AbsInt(rel[i][j]) < m then
  319.                     # rel[ml][mc] is minimal entry of rel
  320.                     ml:=i; mc:=j; m:=AbsInt(rel[i][j]);
  321.                     fi;
  322.                 od;
  323.             od;
  324.         while Maximum(List(Difference(rl,[ml]),x->AbsInt(rel[x][mc])))>0 do
  325.             for i in Difference(rl,[ml]) do
  326.                 rel[i]:=rel[i]-QuoInt(rel[i][mc],rel[ml][mc])*rel[ml];
  327.                 od;    
  328.             # find min entry
  329.             m:=AbsInt(Maximum(rel[rl[1]]))+1;
  330.             for i in rl do
  331.                 for j in rc do
  332.                     if rel[i][j] <> 0 and AbsInt(rel[i][j]) < m then
  333.                         # rel[ml][mc] is minimal entry of rel
  334.                         ml:=i; mc:=j; m:=AbsInt(rel[i][j]);
  335.                         fi;
  336.                     od;
  337.                 od;
  338.             od;
  339.         for i in Difference(rc,[mc]) do
  340.             q:=QuoInt(rel[ml][i],rel[ml][mc]);
  341.             rel[ml][i]:=rel[ml][i]-q*rel[ml][mc]; ng[mc]:=ng[mc]*ng[i]^q;
  342.             od;
  343.         if Maximum(List(Difference(rc,[mc]),x->AbsInt(rel[ml][x])))=0 then
  344.             SubtractSet(rl,[ml]); SubtractSet(rc,[mc]);
  345.             fi;
  346.         od;
  347.     m:=[]; for i in ng do if i<>i^0 then Add(m,i^(Order(g,i)/p)); fi; od;
  348.     return Subgroup(Parent(g),m);
  349.     end;
  350.  
  351.  
  352.  
  353. ###########################################################################
  354. ##
  355. #F  kernel_priv_ag_char( U , v ). . . . . . . . . . . . . . . . . . . local
  356. ##
  357. ##  U is an elementary abelian aggroup. v is a vector in the dual space
  358. ##  of U. The kernel of v is returned.
  359. ##
  360. kernel_priv_ag_char := function(n,v)
  361.  
  362.     local    gens, i, j, ig;
  363.  
  364.     # gens are the generators of the result
  365.     gens:=[]; ig:=Igs(n);
  366.     for i in Reversed([1..Length(v)]) do
  367.         if v[i]=0*v[i] then
  368.             Add(gens,ig[i]);
  369.         else
  370.             # i is the position of the last non zero entry of v
  371.             for j in Reversed([1..i-1]) do
  372.                 Add(gens,ig[j]*ig[i]^(IntFFE(-v[j]/v[i])));
  373.                 od;
  374.             return Subgroup(Parent(n),Reversed(gens));
  375.             fi;
  376.         od;
  377.     end;
  378.  
  379.  
  380.  
  381. ###########################################################################
  382. ##
  383. #F  ProjectiveCharDegAgGroup( G , z , q ) . . . . . . . . . . . . . . . . .
  384. #F  . . . . . . . . . . . . . . . . . . . degrees of irreducible characters
  385. #F  .of G which restirct to a multiple of a faithfull irreducibles of < z >
  386. ##
  387. ##  rec(
  388. ##       degrees         := [ < integer > ],
  389. ##       multiplicity    := [ < integer > ] )
  390. ##
  391. ##  G must be an ag-group and z must be element of Z(G). There are no tests
  392. ##  after the call because of the recursive use of the function.
  393. ##  The function returns the character degress of those characters X of G,
  394. ##  so that X(z) = n * E(|z|), n an interger. q is the characteristic
  395. ##  of the algebraic closed field used.
  396. ##
  397. ProjectiveCharDegAgGroup := function(G,z,q)
  398.  
  399.     local    oz, N, t, r, h, a, o, ti, k, c, ci, zn, i, p, P, O, L;
  400.  
  401.     oz:=Order(G,z);
  402.     if IsAbelian(G) then
  403.         i:=1;
  404.         for k in Igs(G) do
  405.             r:=RelativeOrderAgWord(k); if r<>q then i:=i*r; fi;
  406.             od;
  407.         return [[1,i/oz]];
  408.         fi;
  409.     # G is not abelian
  410.     h:=NaturalHomomorphism(G,G/Subgroup(Parent(G),[z]));
  411.     N:=ElementaryAbelianSeries(h.range); N:=N[Length(N)-1];
  412.     if Length(N.cgs)>1 then
  413.         N:=AgGroupOps.ChiefSeries(h.range,N); N:=N[Length(N)-1];
  414.         fi;
  415.     # N is normal subgroup such that N/<z> is a chieffactor of G
  416.     N:=PreImage(h,N);
  417.     # i=p^? is the order of this chieffactor
  418.     i:=Size(N)/oz; p:=Factors(i)[1];
  419.     if not IsAbelian(N) then
  420.         h:=NaturalHomomorphism(G,G/Subgroup(Parent(G),[z]));
  421.         # c is a list of complementclasses of N modulo z
  422.         c:=List(Complementclasses(h.range,Image(h,N)),x->PreImage(h,x));
  423.         r:=Centralizer(G,N);
  424.         for L in c do
  425.             if IsSubgroup(L,r) then
  426.                # L is a complement to N in G modulo <z> which centralizes N
  427.                r:=RootInt(Size(N)/oz);
  428.                return
  429.                    List(ProjectiveCharDegAgGroup(L,z,q),x->[x[1]*r,x[2]]);
  430.                fi;
  431.             od;
  432.         Error("ProjectiveCharDegAgGroup: this should never appear");
  433.         fi;
  434.     # N is not ablelian, P is the sylow-p-subgroup of N
  435.     if Set(FactorsInt(oz))=[p] then
  436.         P:=N;
  437.     else
  438.         r:=Product(Filtered(FactorsInt(Size(N)),x->x<>p));
  439.         P:=Subgroup(Parent(G),List(N.generators,x->x^r));
  440.         fi;
  441.     if p=q then
  442.         # p is the characteristik of the used field, P is factored out.
  443.         h:=NaturalHomomorphism(G,G/P);
  444.         return ProjectiveCharDegAgGroup(h.range,Image(h,z),q);
  445.         fi;
  446.     if i=Size(P) then 
  447.         # z is a p'-element, P is elementary abelian
  448.         # first find the characters of the factorgroup needed
  449.         h:=NaturalHomomorphism(G,G/P);
  450.         r:=ProjectiveCharDegAgGroup(h.range,Image(h,z),q);
  451.         if p=i then
  452.             # P has order p
  453.             zn:=P.generators[1]; t:=Stabilizer(G,zn);
  454.             if t=G then i:=1; else i:=Size(G)/Size(t); fi;
  455.             return con_col_list(r,List(ProjectiveCharDegAgGroup(t,zn*z,q),
  456.                 x->[x[1]*i,x[2]*(p-1)/i]));
  457.             fi;
  458.         # P has order p^i > p
  459.         # a discribes the contragardient operation of G on P
  460.         a:=List(Igs(G),x->TransposedMat(List(Igs(P),
  461.             y->Exponents(P,y^(x^-1)))*Z(p)^0));
  462.         if p=2 then
  463.             o:=f2_orbits_priv(Igs(G),a);
  464.         else
  465.             o:=ls_orbits_priv(Igs(G),a);
  466.             fi;
  467.         o.stabilizers:=List(o.stabilizers,x->Subgroup(Parent(G),x));
  468.         for i in [1..Length(o.representatives)] do
  469.             # k is the kernel of the character
  470.             k:=kernel_priv_ag_char(P,o.representatives[i]);
  471.             h:=NaturalHomomorphism(o.stabilizers[i],o.stabilizers[i]/k);
  472.             # zn is an element of h.range, |Image(h,P)|=p
  473.             zn:=Image(h,P).generators[1]*Image(h,z);
  474.             # c is stabilizer of the character, ci is the number of
  475.             # orbits of characters with equal kernels
  476.             if p=2 then
  477.                 c:=h.range; ci:=1;
  478.             else
  479.                 c:=Stabilizer(h.range,zn); ci:=Size(h.range)/Size(c);
  480.                 fi;
  481.             k:=Size(G)/Size(o.stabilizers[i])*ci;
  482.             r:=con_col_list(r,List(ProjectiveCharDegAgGroup(c,zn,q),
  483.                 x->[x[1]*k,x[2]*(p-1)/ci]));
  484.             od;
  485.         return r;
  486.         fi;
  487.     if IsCyclic(P) then
  488.         # |P| > p, zn is a generator of P
  489.         zn:=Igs(P)[1]; t:=Stabilizer(G,zn);
  490.         if G=t then
  491.             # P is a central subgroup of G
  492.             return
  493.                 List(ProjectiveCharDegAgGroup(G,zn*z,q),x->[x[1],x[2]*p]);
  494.             fi;
  495.         # P is not central in G
  496.         return List(ProjectiveCharDegAgGroup(t,zn*z,q),x->[x[1]*p,x[2]]);
  497.         fi;
  498.     # P is the direct product of the sylow-p-subgroup of z and a elementary
  499.     # abelian subgroup
  500.     O:=omega_1_priv(P); Cgs(O);
  501.     # zn is a generator of the intersection of <z> and O
  502.     zn:=z^(oz/p); r:=[];
  503.     a:=List(Igs(G),
  504.             x->TransposedMat(List(O.cgs,y->Exponents(O,y^(x^-1)))*Z(p)^0));
  505.     if p=2 then
  506.         o:=f2_orbits_priv(Igs(G),a);
  507.     else
  508.         o:=ls_orbits_priv(Igs(G),a);
  509.         fi;
  510.     # in this case the stabilzers of the kernels are allready the
  511.     # stabilizers of the characters
  512.     for i in [1..Length(o.representatives)] do
  513.         k:=kernel_priv_ag_char(O,o.representatives[i]);
  514.         if not zn in k then
  515.             # the kernel avoids zn
  516.             t:=Subgroup(Parent(G),o.stabilizers[i]);
  517.             h:=NaturalHomomorphism(t,t/k);
  518.             t:=Size(G)/Size(t);
  519.             r:=con_col_list(r,List(ProjectiveCharDegAgGroup(h.range,
  520.                 Image(h,z),q),x->[x[1]*t,x[2]]));
  521.             fi;
  522.         od;
  523.     return r;
  524.     end;
  525.  
  526.  
  527.  
  528. ###########################################################################
  529. ##
  530. #F  CharDegAgGroup( G {, q }) . . . . . . . .character degress of aggroup G
  531. ##
  532. ##  rec(
  533. ##       degrees         := [ < integer > ],
  534. ##       multiplicity    := [ < integer > ] )
  535. ##
  536. ##  The G must be an ag-group. The character degress of G are returned.
  537. ##  The used field has characteristic q.
  538. ##
  539. ##  Just those cases of the algorithm of ProjektiveCharDeg are
  540. ##  needed, which can apear if z is trivial. Especialy N is elementary
  541. ##  abelian.
  542. ##
  543. CharDegAgGroup := function(arg)
  544.  
  545.     local    r, p, a, o, i, k, c, ci, z, t, h, N, G, q;
  546.  
  547.     if not IsAgGroup(arg[1]) or Length(arg)>2 or 
  548.         (Length(arg)=2 and not (IsInt(arg[2]) and
  549.         (IsPrime(arg[2]) or arg[2]=0))) then
  550.         Error("usage: CharDegAgGroup( ag-group )\n",
  551.               "       CharDegAgGroup( ag-group, prime )\n");
  552.         fi;
  553.     G:=arg[1]; if Length(arg)=2 then q:=arg[2]; else q:=0; fi;
  554.     if IsAbelian(G) then
  555.         i:=1;
  556.         for k in Igs(G) do
  557.             r:=RelativeOrderAgWord(k); if r<>q then i:=i*r; fi;
  558.             od;
  559.         return [[1,i]];
  560.         fi;
  561.     # N is just a normal elementary abelian subgroup, may be not 
  562.     # minimal. N is a p-group.
  563.     N:=ElementaryAbelianSeries(G); N:=N[Length(N)-1];
  564.     p:=RelativeOrderAgWord(N.cgs[1]); r:=CharDegAgGroup(G/N,q);
  565.     # N may be a q-group
  566.     if p=q then return r; fi;
  567.     if Size(N)=p then
  568.         z:=N.cgs[1]; t:=Stabilizer(G,z); i:=Size(G)/Size(t);
  569.         r:=con_col_list(r,List(ProjectiveCharDegAgGroup(t,z,q),x->[x[1]*i,
  570.             x[2]*(p-1)/i]));
  571.         if q=0 then G.charDeg:=r; fi; return r;
  572.         fi;
  573.     # N is elementary abelian of order p^? > p
  574.     a:=List(Igs(G),
  575.         x->TransposedMat((List(N.cgs,y->Exponents(N,y^x))*Z(p)^0)^-1));
  576.     if p=2 then
  577.         o:=f2_orbits_priv(Igs(G),a);
  578.     else
  579.         o:=ls_orbits_priv(Igs(G),a);
  580.         fi;
  581.     o.stabilizers:=List(o.stabilizers,x->Subgroup(Parent(G),x));
  582.     for i in [1..Length(o.representatives)] do
  583.         k:=kernel_priv_ag_char(N,o.representatives[i]);
  584.         h:=NaturalHomomorphism(o.stabilizers[i],o.stabilizers[i]/k);
  585.         # |stabilizers[i]/k| = p
  586.         z:=Image(h,N).generators[1];
  587.         if p=2 then
  588.             c:=h.range; ci:=1;
  589.         else
  590.             c:=Stabilizer(h.range,z); ci:=Size(h.range)/Size(c);
  591.             fi;
  592.         k:=Size(G)/Size(o.stabilizers[i])*ci;
  593.         r:=con_col_list(r,List(ProjectiveCharDegAgGroup(c,z,q),x->
  594.             [x[1]*k,x[2]*(p-1)/ci]));
  595.     od;
  596.     if q=0 then G.charDeg:=r; fi; return r;
  597.     end;
  598.  
  599.  
  600.  
  601. ###########################################################################
  602. ##
  603. #F  char_sec_prev( hom , l ). . . . . . . . . . . . . . . . . . . . . local
  604. ##
  605. char_sec_prev := function(hom,l)
  606.  
  607.     local r, x;
  608.  
  609.     r:=[];
  610.     for x in l do
  611.             Add(r,[PreImage(hom,x[1]),PreImage(hom,x[2]),
  612.             PreImagesRepresentative(hom,x[3])]);
  613.         od;
  614.     return r;
  615.     end;
  616.  
  617.  
  618.  
  619. ###########################################################################
  620. ##
  621. #F  char_sec( G , z ) . . . . . . . . . . . . . . . . . . . . . . . . local
  622. ##
  623. ##  G must be an supersolvable ag-group and z must be element of Z(G).
  624. ##  The function returns a list of tripels [T, K, e], so that every
  625. ##  irreducible character X of G with the property  that X(z) = n * E(|z|)
  626. ##  for an arbitrary interger n is the induced of a linear character of
  627. ##  some T with kernel K. The element e is choosen so that <eK> is
  628. ##  generating T/K.
  629. ##
  630. ##  The algorithm used is the same as in ProjektiveCharDeg, but the 
  631. ##  recursion stops just if G=<z>. The structure and the names of the
  632. ##  variables are the same.
  633. char_sec := function(G,z)
  634.  
  635.     local    oz, N, t, r, h, a, o, ti, k, c, ci, zn, i, p, P, O;
  636.  
  637.     # the 1-character will be found more easy
  638.     if Size(G)=1 then return []; fi;
  639.     oz:=Order(G,z);
  640.     if Size(G)=oz then return [[G,Subgroup(Parent(G),[]),z]]; fi;
  641.     h:=NaturalHomomorphism(G,G/Subgroup(Parent(G),[z]));
  642.     N:=ElementaryAbelianSeries(h.range); N:=N[Length(N)-1];
  643.     if Length(N.cgs)>1 then
  644.         N:=AgGroupOps.ChiefSeries(h.range,N); N:=N[Length(N)-1];
  645.         fi;
  646.     N:=PreImage(h,N);
  647.     if not IsAbelian(N) then
  648.         Print("#W: CharTableSSGroup, not all characters found\n");
  649.         return [];
  650.         fi;
  651.     i:=Size(N)/oz; p:=Factors(i)[1];
  652.     if Set(FactorsInt(oz))=[p] then
  653.         P:=N;
  654.     else
  655.         r:=Product(Filtered(FactorsInt(Size(N)),x->x<>p));
  656.         P:=Subgroup(Parent(G),List(N.generators,x->x^r));
  657.         fi;
  658.     if i=Size(P) then 
  659.         h:=NaturalHomomorphism(G,G/P);
  660.         r:=char_sec_prev(h,char_sec(h.range,Image(h,z)));
  661.         if p=i then
  662.             zn:=P.generators[1];
  663.             return Concatenation(r,char_sec(Stabilizer(G,zn),zn*z));
  664.             fi;
  665.         a:=List(Igs(G),
  666.             x->TransposedMat((List(Igs(P),y->Exponents(P,y^x))*Z(p)^0)^-1));
  667.         if p=2 then o:=f2_orbits_priv(Igs(G),a);
  668.         else o:=ls_orbits_priv(Igs(G),a);
  669.             fi;
  670.         o.stabilizers:=List(o.stabilizers,x->Subgroup(Parent(G),x));
  671.         for i in [1..Length(o.representatives)] do
  672.             k:=kernel_priv_ag_char(P,o.representatives[i]);
  673.             h:=NaturalHomomorphism(o.stabilizers[i],o.stabilizers[i]/k);
  674.             zn:=Image(h,P).generators[1]*Image(h,z);
  675.             if p=2 then c:=h.range;
  676.             else c:=Stabilizer(h.range,zn);
  677.                 fi;
  678.             r:=Concatenation(r,char_sec_prev(h,char_sec(c,zn)));
  679.             od;
  680.         return r;
  681.         fi;
  682.     if IsCyclic(P) then
  683.         zn:=Igs(P)[1]; return char_sec(Stabilizer(G,zn),zn*z);
  684.         fi;
  685.     O:=omega_1_priv(P); Cgs(O); zn:=z^(oz/p); r:=[];
  686.     a:=List(Igs(G),
  687.             x->TransposedMat((List(O.cgs,y->Exponents(O,y^x))*Z(p)^0)^-1));
  688.     if p=2 then
  689.         o:=f2_orbits_priv(Igs(G),a);
  690.     else
  691.         o:=ls_orbits_priv(Igs(G),a);
  692.         fi;
  693.     for i in [1..Length(o.representatives)] do
  694.         k:=kernel_priv_ag_char(O,o.representatives[i]);
  695.         if not zn in k then
  696.             t:=Subgroup(Parent(G),o.stabilizers[i]);
  697.             h:=NaturalHomomorphism(t,t/k);
  698.             r:=Concatenation(r,char_sec_prev(h,char_sec(
  699.                 h.range,Image(h,z))));
  700.             fi;
  701.         od;
  702.     return r;
  703.     end;
  704.  
  705.  
  706.  
  707. ###########################################################################
  708. ##
  709. #F  CharTableSSGroup( G ) . . . .character table of supersolvable aggroup G
  710. ##
  711. ##  This function calculates the character table of a supersolvable 
  712. ##  ag-represented group. It is not used as default algorithm. For every 
  713. ##  character in the table the information from which linear character of
  714. ##  which subgroup this monomial character is induced is written to the
  715. ##  '<t>.irredinfo[i].inducedFrom'. The linear charakter is discribed by
  716. ##  the subgroup its induced from and the kernel it has.
  717. ##
  718. ##  For this purpose first the head of the character table is calculated.
  719. ##  Then the function char_sec gives a list of triples discribing linear
  720. ##  representations of subgroups of G. These linear representations will
  721. ##  be induced to G, and evaluated on representatives of the conjugacy
  722. ##  classes. 
  723. ##
  724. CharTableSSGroup := function(g)
  725.  
  726.     local ecs, evl, ct, i, t, ni, j, mat, k, cgs, sec, hom, zi, oz,
  727.         ee, zp, co, dim, rep, bco, p, r, pecs, pl, mulmoma, i1, re;
  728.  
  729.     # function returns the product of 2 monomial matrices
  730.     mulmoma:=function(a,b)
  731.     re:=rec(perm:=[],diag:=[]);
  732.     for i1 in [1..Length(a.perm)] do
  733.         re.perm[i1]:=b.perm[a.perm[i1]];
  734.         re.diag[b.perm[i1]]:=(b.diag[b.perm[i1]]+a.diag[i1]) mod oz;
  735.         od;
  736.     return re;
  737.     end;
  738.  
  739.  
  740.     ecs:=ConjugacyClasses(g); evl:=[];
  741.     cgs:=Cgs(g); dim:=Length(ecs); pecs:=[];
  742.     ct:=rec(order:=Size(g),classes:=List(ecs,Size),powermap:=[],
  743.         operations:=CharTableOps,group:=g,
  744.         irreducibles:=[[1..Length(ecs)]*0+1],
  745.         orders:=List(ecs,x->Order(g,x.representative)),
  746.         irredinfo:=[rec(inducedFrom:=rec(subgroup:=g,kernel:=g))]);
  747.     # evl will be list discribing the representatives of the conjugacy
  748.     # classes. If e=g.1^2*g.2^0*g.3^1, then eval will be
  749.     # [ ... , [ 1, 1, 3 ], ... ]
  750.     for i in [2..dim] do
  751.         k:=Exponents(g,ecs[i].representative); t:=[];
  752.         for j in [1..Length(k)] do
  753.             if k[j]>0 then Append(t,[1..k[j]]*0+j); fi;
  754.             od;
  755.         Add(evl,t);
  756.         od;
  757.     ct.centralizers:=List(ct.classes,x->ct.order/x);
  758.     if IsBound(g.name) then
  759.         ct.name:=g.name;
  760.     else
  761.         if IsBound(Parent(g).name) then
  762.             ct.name:=Parent(g).name;
  763.             for k in g.generators do
  764.                 ct.name:=ConcatenationString(ct.name,"_",String(k));
  765.                 od;
  766.             fi;
  767.         ct.name:="";
  768.         fi;
  769.     pl:=Set(Factors(ct.order));
  770.     for i in pl do
  771.         ct.powermap[i]:=[];
  772.         for j in ecs do
  773.             Add(pecs,j.representative^i);
  774.             od;
  775.         od;
  776.     pecs:=AgGroupOps.ConjugacyClasses(g,pecs);
  777.     for i in [1..Length(pl)] do
  778.         for j in [1..dim] do
  779.             r:=pecs[(i-1)*dim+j].representative;
  780.             k:=0; repeat k:=k+1; until r=ecs[k].representative;
  781.             Add(ct.powermap[pl[i]],k);
  782.             od;
  783.         od;
  784.     for sec in char_sec(g,g.identity) do
  785.         hom:=NaturalHomomorphism(sec[1],sec[1]/sec[2]);
  786.         zi:=Image(hom,sec[3]); oz:=Order(hom.range,zi); ee:=E(oz);
  787.         zp:=List([1..oz],x->zi^x);
  788.         co:=Cosets(g,sec[1]);
  789.         dim:=Length(co);
  790.         # rep is a representation from the right on a module with a base
  791.         # being a transversal of the stabilizer in g. The monomial matrices
  792.         # used are the same as in the function RepresentationsPGroup
  793.         rep:=[];
  794.         for i in cgs do
  795.             mat:=rec(perm:=[],diag:=[]);
  796.             for j in [1..dim] do
  797.                 bco:=co[j]*i;
  798.                 p:=Position(co,bco);
  799.                 Add(mat.perm,p);
  800.                 mat.diag[p]:=Position(zp,Image(hom,co[j].representative*i*
  801.                     co[p].representative^-1));
  802.                 od;
  803.             Add(rep,mat);
  804.             od;
  805.         # ni get the irreducible
  806.         ni:=[dim];
  807.         for j in evl do
  808.             mat:=Iterated(List(j,x->rep[x]),mulmoma); t:=0;
  809.             for k in [1..Length(mat.diag)] do
  810.                 if mat.perm[k]=k then 
  811.                    t:=t+ee^mat.diag[k];
  812.                    fi;
  813.                 od;
  814.                 Add(ni,t);
  815.             od;
  816.         # test if ni is known and and ni and its galios-conjugates to the
  817.         # table
  818.         if not ni in ct.irreducibles then
  819.             i:=GaloisMat([ni]).mat;
  820.             Append(ct.irreducibles,i);
  821.             # write information in .irredinfo
  822.             for j in i do
  823.                 if sec[1]=g then
  824.                     Add(ct.irredinfo,rec(inducedFrom:=rec(subgroup:=g,
  825.                         kernel:=Subgroup(Parent(g),sec[2].generators))));
  826.                 else
  827.                     Add(ct.irredinfo,rec(inducedFrom:=
  828.                     rec(subgroup:=Subgroup(Parent(g),sec[1].generators),
  829.                         kernel:=Subgroup(Parent(g),sec[2].generators))));
  830.                     fi;
  831.                 od;
  832.             fi;
  833.         od;
  834.     return ct;
  835.     end;
  836.  
  837.