home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / agctbl.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  11.3 KB  |  444 lines
  1. #############################################################################
  2. ##
  3. #A  agctbl.g                    GAP library                  Alexander Hulpke
  4. ##
  5. #H  @(#)$Id: agctbl.g,v 3.2 1993/02/09 14:25:55 martin Rel $
  6. ##
  7. #Y  Copyright (C)  1993,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains AgGroup specific parts of the Dixon-Schneider.
  10. ##
  11. #H  $Log: agctbl.g,v $
  12. #H  Revision 3.2  1993/02/09  14:25:55  martin
  13. #H  made undefined globals local
  14. #H
  15. #H  Revision 3.1  1993/01/18  18:46:52  martin
  16. #H  initial revision under RCS
  17. #H
  18. ##
  19.  
  20.  
  21. #############################################################################
  22. ##
  23. #F  AgGroupClassMatrixColumn(<D>,<mat>,<r>,<t>) . . calculate the t-th column
  24. #F       of the r-th class matrix and store it in the appropriate column of M
  25. ##
  26. AgGroupClassMatrixColumn := function(D,M,r,t)
  27.   local orb, # orbits of Stab_Gal(r) etc.
  28.         p,   # class permutation, position in a list
  29.         c,   # class number
  30.         T,   # List of the identefees and their multiples
  31.         z,   # representative of class t
  32.         l,   # length of (elementary) abelian series
  33.         fg,  # factor group
  34.         fgh, # 1 in factor group G/N2 \ where N2<N1
  35.         fgi, # 1 in factor group G/N1 /
  36.         n,   # image of N1 in G/N2
  37.         ng,  # IGS of n
  38.         es,  # canonical class representatives in factor group
  39.         rep, # one of them
  40.         conju, # conjugating elements
  41.         conj,  # one of them
  42.         res, # rec(conjugating correction,new centralizer)
  43.         ci,  # numbers of the corresponding centralizers
  44.         cent,# centralizers
  45.         newcent,# centralizers for next step
  46.         ce,  # one of them
  47.         i,j, # loop variables
  48.         ic,  # indicator for central step
  49.         fxt, # yet calculated images in factor group
  50.         xt,  # tail part of the identifee
  51.         uniques; # heads, that identify a class uniquely
  52.  
  53.   if t=1 then
  54.     M[D.charTable.inversemap[r]][t]:=Size(D.conjugacyClasses[r]);
  55.   else
  56.     orb:=GaloisOrbits(D,r);
  57.     z:=D.conjugacyClasses[t].representative;
  58.     c:=orb.orbits[t][1];
  59.     if c<>t then
  60.       p:=RepresentativeOperation(orb.group,c,t);
  61.       for i in [1..D.klanz] do
  62.         M[i^p][t]:=M[i][c];
  63.       od;
  64.       InfoCharTable2("by GaloisImage");
  65.       return;
  66.     fi;
  67.  
  68.     T:=DoubleCentralizerOrbit(D,r,t);
  69.     InfoCharTable2(Length(T[1])," instead of ",D.conjugacyClasses[r].size);
  70.  
  71.     Apply(T[1],i->i*z);
  72.  
  73.     fgi:=D.facs[1].identity;
  74.     l:=Length(D.facs);
  75.   # as long as abelian, classes are the same, as elements
  76.     es:=List(T[1],i->FactorAgWord(i,fgi));
  77.     conju:=List(es,i->fgi);
  78.     ci:=List(es,i->1);
  79.     cent:=[ShallowCopy(D.facs[1].generators)];
  80.     uniques:=D.uniques;
  81.  
  82.     for i in [2..l] do
  83.       fg:=D.facs[i];
  84.       fgi:=fg.identity;
  85.       fgh:=D.facs[i-1].identity;
  86.       n:=D.imgs[i];
  87.       ng:=Igs(n);
  88.       ic:=D.iscentral[i];
  89.  
  90.       for j in [1..Length(cent)] do
  91.     Apply(cent[j],x->FactorAgWord(x,fgi));
  92.       od;
  93.  
  94.       newcent:=[];
  95.       fxt:=[];
  96.  
  97.       for j in [1..Length(T[1])] do
  98.  
  99.     if es[j] in uniques then
  100.       if i=l then
  101.         es[j]:=FactorAgWord(es[j],fgi);
  102.         D.shorttests:=D.shorttests+1;
  103.       fi;
  104.     else
  105.       # es contains the canonical form one step above
  106.  
  107.       xt:=FactorAgWord(T[1][j],fgi);
  108.       # have we yet considered this element ?
  109.       p:=Position(fxt,xt);
  110.       if p=false then
  111.         fxt[j]:=xt;
  112.         rep:=FactorAgWord(es[j],fgi);
  113.         conj:=FactorAgWord(conju[j],fgi);
  114.         xt:=rep^(-1)*xt^conj;
  115.  
  116.         if ic then
  117.           res:=CentralCaseECAgWords(fg,n,cent[ci[j]],ng,rep,xt);
  118.         else
  119.           res:=GeneralCaseECAgWords(fg,n,cent[ci[j]],ng,rep,xt);
  120.         fi;
  121.  
  122.         conju[j]:=conj*res.conjugand;
  123.         es[j]:=res.representative;
  124.         ce:=res.centralizer;
  125.  
  126.         p:=Position(newcent,ce);
  127.         if p=false then
  128.           Add(newcent,ce);
  129.           ci[j]:=Length(newcent);
  130.         else
  131.           ci[j]:=p;
  132.         fi;
  133.       else
  134.         conju[j]:=conju[p];
  135.         es[j]:=es[p];
  136.         ci[j]:=ci[p];
  137.       fi;
  138.     fi;
  139.  
  140.       od;
  141.       cent:=newcent;
  142.     od;
  143.  
  144.     # evaluate
  145.  
  146.     rep:=D.replist;
  147.     for i in [1..Length(es)] do
  148.       p:=Position(rep,es[i]);
  149.       M[p][t]:=M[p][t]+T[2][i];
  150.     od;
  151.  
  152.   fi;
  153. end;
  154.  
  155.  
  156. #############################################################################
  157. ##
  158. #F  IdentificationAgGroup(<D>,<el>)  calculate canonical class representative
  159. #F                                                                 of el in G
  160. ##
  161. IdentificationAgGroup := function(D,el)
  162.   local fgi,l,es,conj,cent,fg,n,ng,rep,res,xt,i;
  163.  
  164.   fgi:=D.facs[1].identity;
  165.   l:=Length(D.facs);
  166.   # as long as abelian, classes are the same, as elements
  167.   es:=FactorAgWord(el,fgi);
  168.   conj:=fgi;
  169.   cent:=ShallowCopy(D.facs[1].generators);
  170.  
  171.   for i in [2..l] do
  172.  
  173.     xt:=FactorAgWord(el,fgi);
  174.     # can we shorten the procedure ?
  175.     if xt in D.uniques then
  176.       D.shorttests:=D.shorttests+1;
  177.       return FactorAgWord(xt,D.group.identity);
  178.     fi;
  179.  
  180.     fg:=D.facs[i];
  181.     fgi:=fg.identity;
  182.     n:=D.imgs[i];
  183.     ng:=Igs(n);
  184.  
  185.     Apply(cent,x->FactorAgWord(x,fgi));
  186.  
  187.     rep:=FactorAgWord(es,fgi);
  188.     conj:=FactorAgWord(conj,fgi);
  189.  
  190.     xt:=rep mod FactorAgWord(el,fgi)^conj;
  191.  
  192.     if D.iscentral[i] then
  193.       res:=CentralCaseECAgWords(fg,n,cent,ng,rep,xt);
  194.     else
  195.       res:=GeneralCaseECAgWords(fg,n,cent,ng,rep,xt);
  196.     fi;
  197.  
  198.     conj:=conj*res.conjugand;
  199.     es:=res.representative;
  200.     cent:=res.centralizer;
  201.  
  202.   od;
  203.  
  204.   return es;
  205.  
  206. end;
  207.  
  208.  
  209. #############################################################################
  210. ##
  211. #F  AgGroupOps.DxPreparation(<G>) . specific initialisation for PAG presented
  212. #F                                                                     groups
  213. ##
  214. ##  Set up some functions. Initialize the computation of canonic
  215. ##  class representatives
  216. ##
  217. AgGroupOps.DxPreparation := function(G)
  218.   local i,j,k,orb,hom,D;
  219.  
  220.   # falls n"otig bessere Reihe berechnen
  221.  
  222.   if not(IsParent(G) and IsElementaryAbelianAgSeries(G)) then
  223.     InfoCharTable1("#I Calculating ElementaryAbelianSeries\n");
  224.     hom:=IsomorphismAgGroup(ElementaryAbelianSeriesThrough(
  225.            [G,DerivedSubgroup(G)]));
  226.     hom.isMapping:=true;
  227.     hom.isGroupHomomorphism:=true;
  228.     hom.isInjective:=true;
  229.     hom.isSurjective:=true;
  230.     hom.isBijection:=true;
  231.     hom.kernel:=TrivialSubgroup(G);
  232.     hom.range.oldG:=G;
  233.     if IsBound(G.name) then
  234.       hom.range.name:=G.name;
  235.     fi;
  236.     G:=hom.range; # hom on the range
  237.     # force canonical representatives
  238.     G.conjugacyClasses:=AgGroupOps.ConjugacyClasses(G,List(
  239.           ConjugacyClasses(G.oldG),i->i.representative^hom));
  240.   fi;
  241.  
  242.   D:=DixonRecord(G);
  243.  
  244.   InitAgConjugacyTest(D);
  245.  
  246.   if IsBound(G.oldG) then
  247.     D.oldG:=G.oldG;
  248.     Unbind(G.oldG);
  249.   fi;
  250.  
  251.   # Don't care about LARGE groups
  252.   D.ClassElement:=ClassElementLargeGroup;
  253.   D.ClassMatrixColumn:=AgGroupClassMatrixColumn;
  254.   D.identification:=IdentificationAgGroup;
  255.   D.rationalidentification:=IdentificationAgGroup;
  256.  
  257.   D.ids:=[];
  258.   for i in [1..D.klanz] do
  259.     # representatives are identification
  260.     D.ids[i]:=D.conjugacyClasses[i].representative;
  261.   od;
  262.   D.rids:=D.ids;
  263.  
  264.   return D;
  265.  
  266. end;
  267.  
  268.  
  269. #############################################################################
  270. ##
  271. #F  InitAgConjugacyTest( <D> ) . . prepare for fast computations of canonical
  272. #F                                                             class elements
  273. ##
  274. InitAgConjugacyTest := function(D)
  275.   local G,    # the group
  276.         eas,  # elementary abelian series
  277.         offs, # offset of the series we are starting with (the first factor
  278.               # need not to be elementary abelian but only abelian)
  279.         facs, # factor groups
  280.         l,    # length of this
  281.         imgs, # images of the normal subgroups in next factorgroup
  282.         iscentral, # central step indicator
  283.         i,j,  # loop variables
  284.         f,    # factor group
  285.         uniques, # representatives of classes in factor group, which do not
  286.                  # split
  287.         uniquecands, # candidates therefore
  288.         stilluniques, # still candidates in former factorgroup
  289.         adduniques, # unique in factor, but not in higher factor
  290.         p,   # position
  291.         fe,  # factor group element
  292.         fgi, # factor group identity
  293.         fused; # representatives of classes, that fuse together
  294.  
  295.   G:=D.group;
  296. # suppose, we have an elementary abelian Ag Series
  297.   eas:=ElementaryAbelianSeries(G);
  298. # factor Groups
  299.   facs:=[];
  300.   j:=1;
  301.   offs:=-1;
  302.   for i in [1..Length(eas)-1] do
  303.     f:=G/eas[i];
  304.     if (j=2) and IsAbelian(f) then
  305.       j:=1;
  306.       # still abelian factor, starting lower in the row
  307.       offs:=offs+1;
  308.     fi;
  309.     facs[j]:=f;
  310.     j:=j+1;
  311.   od;
  312.   Add(facs,G);
  313.   l:=Length(facs);
  314. # images of previous eas-step as normal abelian subgroup
  315.   imgs:=[];
  316.   iscentral:=[];
  317.   for i in [2..l] do
  318.     f:=facs[i];
  319.     imgs[i]:=Subgroup(f,List(eas[i+offs].generators,
  320.                       j->FactorAgWord(j,f.identity)));
  321.     iscentral[i]:=IsCentral(f,imgs[i]);
  322.   od;
  323.   D.facs:=facs;
  324.   D.imgs:=imgs;
  325.   D.iscentral:=iscentral;
  326.   D.replist:=List(D.conjugacyClasses,i->i.representative);
  327.   uniquecands:=D.replist;
  328.   uniques:=[];
  329.   for i in Reversed([1..l-1]) do
  330.     f:=facs[i];
  331.     fgi:=f.identity;
  332.     imgs:=[];
  333.     fused:=[];
  334.     for j in D.replist do
  335.       fe:=FactorAgWord(j,fgi);
  336.       p:=Position(imgs,fe);
  337.       if p<>false then
  338.         Add(fused,fe);
  339.       else
  340.         Add(imgs,fe);
  341.       fi;
  342.     od;
  343.  
  344.     adduniques:=[];
  345.     stilluniques:=[];
  346.  
  347.     for j in uniquecands do
  348.       fe:=FactorAgWord(j,fgi);
  349.       # does uniqueness extend to factor?
  350.       if fe in fused then
  351.         Add(adduniques,j);
  352.       else
  353.         Add(stilluniques,fe);
  354.       fi;
  355.     od;
  356.     uniquecands:=stilluniques;
  357.  
  358.     if i<(l-1) then
  359.       Append(uniques,adduniques);
  360.     fi;
  361.   od;
  362.   # note those, that stayed unique during the whole run
  363.  
  364.   Append(uniques,stilluniques);
  365.   D.uniques:=Set(uniques);
  366.   D.shorttests:=0;
  367. end;
  368.  
  369.  
  370. #############################################################################
  371. ##
  372. #F  CharacterDegreePool(G)  . . possible character degrees, using thm. of Ito
  373. ##
  374. GroupOps.CharacterDegreePool:=function(G)
  375.   return Copy(CharDegAgGroup(G));
  376. end;
  377.  
  378.  
  379. #############################################################################
  380. ##
  381. #F  AgGroupOps.Enumeration(<G>) . . . . . . . . .  enumeration for an aggroup
  382. ##
  383. ##  enumerate elements of a AgGroup G, using the representation of an
  384. ##  element as product of the generators and identifying the exponents
  385. ##  of the generators with an multi-adic expansion of the
  386. ##  number.
  387. ##
  388. AgGroupOps.Enumeration:=function ( G )
  389. local indices,steps,i,U,V;
  390.   steps:=Length(G.generators);
  391.   indices:=[];
  392.   U:=Subgroup(G,[]);
  393.   i:=steps;
  394.   while i>0 do
  395.     V:=Closure(U,G.generators[i]);
  396.     indices:=Concatenation([Index(V,U)],indices);
  397.     U:=V;
  398.     i:=i-1;
  399.   od;
  400.   return rec(
  401.     number := function(G,elem)
  402.      local num,ind,i;
  403.      ind:=Exponents(G,elem);
  404.      num:=0;
  405.      for i in [1..steps] do
  406.        num:=num*indices[i]+ind[i];
  407.      od;
  408.      return num+1;
  409.   end,
  410.     element := function (G,num)
  411.      local  n, elem, coef, i;
  412.      n:=num-1;
  413.      coef:=[];
  414.      for i in Reversed(indices) do
  415.        Add(coef,n mod i);
  416.        n:=QuoInt(n,i);
  417.      od;
  418.      coef := Reversed(coef);
  419.      elem:=G.identity;
  420.      for i in [1..steps] do
  421.        elem:=elem*G.generators[i]^coef[i];
  422.      od;
  423.     return elem;
  424.   end );
  425. end;
  426.  
  427.  
  428. #############################################################################
  429. ##
  430. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  431. ##
  432. ##  Local Variables:
  433. ##  mode:               outline
  434. ##  outline-regexp:     "#A\\|#F\\|#V\\|#E\\|#R"
  435. ##  tab-width:          2
  436. ##  fill-column:        73
  437. ##  fill-prefix:        "##  "
  438. ##  eval:               (hide-body)
  439. ##  End:
  440. ##
  441.  
  442.  
  443.  
  444.