home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / permctbl.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  10.0 KB  |  336 lines
  1. #############################################################################
  2. ##
  3. #A  permctbl.g                  GAP library                  Alexander Hulpke
  4. ##
  5. #H  @(#)$Id: permctbl.g,v 3.1 1993/01/18 18:46:52 martin Rel $
  6. ##
  7. #Y  Copyright (C)  1993,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains the PermGroup specific parts for Dixon-Schneider.
  10. ##
  11. #H  $Log: permctbl.g,v $
  12. #H  Revision 3.1  1993/01/18  18:46:52  martin
  13. #H  initial revision under RCS
  14. #H
  15. ##
  16.  
  17.  
  18. #############################################################################
  19. ##
  20. #F  IdentificationPermGroup(<D>,<el>) . . . . .  class invariants for el in G
  21. ##
  22. ##  The class invariant consists of the cycle structure and - if computation
  23. ##  might improve results - of the Fingerprint of the permutation
  24. ##
  25. IdentificationPermGroup := function(D,el)
  26.   local s,t,i,l; # guter Programmier s t i l !
  27.   s:=CycleStructurePerm(el);
  28.   if D.group.isPerfect=false then
  29. Add(s,D.group.operations.CanonicalCosetElement(D.group.derivedSubgroup,el));
  30.   fi;
  31.   t:=ShallowCopy(s);
  32.   if t in D.centmulCandidates then
  33.     Add(s,"c");
  34.     l:=First(D.centmulMults,i->i[1]=t);
  35.     for i in Sublist(l,[2..Length(l)]) do
  36.       s:=Concatenation(s,CycleStructurePerm(
  37.                            el*D.conjugacyClasses[i].representative));
  38.     od;
  39.   fi;
  40.   if t in D.fingerprintCandidates then
  41.     Add(s,-FingerprintPerm(D,el,1,2,D.fingerprintOrbitStabilizer,
  42.                                     D.fingerprintRepresentatives));
  43.   fi;
  44.   return s;
  45. end;
  46.  
  47.  
  48. #############################################################################
  49. ##
  50. #F  RationalIdentificationPermGroup( <D>, <el> )   galois-fix class invariant
  51. ##
  52. ##  When trying to use cheap identifications, we cannot use all
  53. ##  identification routines: For exaple galois conjugated elements must be
  54. ##  multiplied by the *galois conjugate* of the central element!
  55. ##
  56. RationalIdentificationPermGroup := function(D,el)
  57.   return CycleStructurePerm(el);
  58. end;
  59.  
  60.  
  61. #############################################################################
  62. ##
  63. #F  FingerprintPerm( <D>, <el>, <i>, <j>, <orbitJ>, <representatives>)
  64. #F       Entry i,j of the matrix of el in the permutation representation of G
  65. ##
  66. FingerprintPerm := function(D,el,i,j,orbitJ,representatives)
  67.   local x,y,a,cycle,cycles;
  68.   a:=0;
  69.   cycles:=Cycles(el,[1..D.group.degree]);
  70.   for cycle in cycles do
  71.     x:=cycle[1];
  72.     if x^(el*representatives[x]) in orbitJ then
  73.       a:=a+Length(cycle);
  74.     fi;
  75.   od;
  76.   return a;
  77. end;
  78.  
  79.  
  80. #############################################################################
  81. ##
  82. #F  PermGroupOps.DxPreparation(<G>) . . . . . . . specific initialisation for
  83. #F                                                         permutation groups
  84. ##
  85. ##  Set up some functions. Also test, whether calculating fingerprints and
  86. ##  multiplication by central elements might improve the quick
  87. ##  identification
  88. ##
  89. PermGroupOps.DxPreparation := function(G)
  90.   local k,sum,perm,structures,ambiguousStructures,i,j,p,e,cem,ces,z,t,cen,a,
  91.         c,s,f,fc,fs,fos,fr,D;
  92.  
  93.   D:=DixonRecord(G);
  94.   D.identification:=IdentificationPermGroup;
  95.   D.rationalidentification:=RationalIdentificationPermGroup;
  96.   D.ClassMatrixColumn:=StandardClassMatrixColumn;
  97.  
  98.   if IsLargeGroup(G) then
  99.     D.ClassElement:=ClassElementLargeGroup;
  100.   else
  101.     D.ClassElement:=ClassElementSmallGroup;
  102.     Enumeration(G);
  103.     D.classMap:=List([1..Size(G)],i->D.klanz);
  104.     for j in [1..D.klanz-1] do
  105.       for i in Orbit(G,D.conjugacyClasses[j].representative) do
  106.         D.classMap[G.enumeration.number(G,i)]:=j;
  107.       od;
  108.     od;
  109.   fi;
  110.  
  111.   D.fingerprintCandidates:=[];
  112.   D.centmulCandidates:=[];
  113.   G.degree:=PermGroupOps.LargestMovedPoint(G);
  114.   k:=D.klanz;
  115.   if IsLargeGroup(G) then
  116.     # test, if cyclestructure yields no perfect result
  117.     structures:=[];
  118.     ambiguousStructures:=[];
  119.     for i in [1..k] do
  120.       s:=IdentificationPermGroup(D,D.conjugacyClasses[i].representative);
  121.       if not s in structures then
  122.         Add(structures,s);
  123.       else
  124.         AddSet(ambiguousStructures,s);
  125.       fi;
  126.     od;
  127.     if ambiguousStructures<>[] then
  128.       # Centre multiplikation test
  129.       cem:=[];
  130.       cen:=[];
  131.       for i in [2..Length(D.conjugacyClasses)] do
  132.         if Size(D.conjugacyClasses[i])=1 then
  133.           Add(cen,i);
  134.         fi;
  135.       od;
  136.  
  137.       if cen<>[] then
  138.         for s in ambiguousStructures do
  139.           ces:=[s];
  140.           c:=Filtered([1..Length(D.conjugacyClasses)],i->
  141.                IdentificationPermGroup(D,
  142.                   D.conjugacyClasses[i].representative)=s);
  143.           a:=[[1..Length(c)]];
  144.           for z in cen do
  145.             t:=List(c,i->
  146.                      CycleStructurePerm(
  147.                                     D.conjugacyClasses[i].representative*
  148.                                     D.conjugacyClasses[z].representative));
  149.             if Length(Set(t))>1 then
  150.               # improved result ?
  151.               fc:=[];
  152.               fs:=[];
  153.               for i in [1..Length(t)] do
  154.                 p:=Position(fc,t[i]);
  155.                 if p=false then
  156.                   Add(fc,t[i]);
  157.                   p:=Length(fc);
  158.                   fs[p]:=[];
  159.                 fi;
  160.                 Add(fs[p],i);
  161.               od;
  162.               fc:=[];
  163.               for i in a do
  164.                 fc:=Concatenation(fc,Filtered(List(fs,j->Intersection(j,i)),
  165.                                     j->j<>[]));
  166.               od;
  167.               fc:=Set(fc);
  168.               if fc<>a then
  169.                 Add(ces,z);
  170.                 a:=fc;
  171.               fi;
  172.             fi;
  173.           od;
  174.           if Length(ces)>1 then
  175.             Add(cem,ces);
  176.           fi;
  177.         od;
  178.         D.centmulMults:=cem;
  179.       fi;
  180.       # fingerprint test
  181.       if IsTransitive(G,G.operations.MovedPoints(G)) and
  182.     # otherwise lotsa representatives will mess up memory
  183.     Length(PermGroupOps.MovedPoints(G))<1500 then
  184.         fs  := Stabilizer(G,1);
  185.         fos := First(Orbits(fs,[1..G.degree]),o->2 in o);
  186.         fr  := List([1..G.degree],x->RepresentativeOperation(G,x,1));
  187.         fc:=[];
  188.         for s in ambiguousStructures do
  189.           c:=Filtered([1..D.klanz],i->IdentificationPermGroup(D,
  190.                   D.conjugacyClasses[i].representative)=s);
  191.           f:=List(c,i->FingerprintPerm(D,
  192.                     D.conjugacyClasses[i].representative,1,2,fos,fr));
  193.           if Length(Set(f))>1 then Add(fc,s);
  194.           fi;
  195.         od;
  196.         if Length(fc)>0 then
  197.           D.fingerprintCandidates:=fc;
  198.           D.fingerprintOrbitStabilizer:=fos;
  199.           D.fingerprintRepresentatives:=fr;
  200.         fi;
  201.       fi;
  202.       D.centmulCandidates:=Set(List(cem,i->i[1]));
  203.     fi;
  204.   fi;
  205.  
  206.   D.ids:=[];
  207.   D.rids:=[];
  208.   for i in [1..D.klanz] do
  209.     D.ids[i]:=D.identification(D,D.conjugacyClasses[i].representative);
  210.     D.rids[i]:=
  211.      D.rationalidentification(D,D.conjugacyClasses[i].representative);
  212.   od;
  213.  
  214.   return D;
  215.  
  216. end;
  217.  
  218.  
  219. #############################################################################
  220. ##
  221. #F  CharacterDegreePool(G)  . . possible character degrees, using thm. of Ito
  222. ##
  223. PermGroupOps.CharacterDegreePool:=function(G)
  224.   local d,k,r,s;
  225.   r:=RootInt(Size(G));
  226.   s:=Lcm(List(AbelianNormalSubgroups(G),i->Index(G,i)));
  227.   k:=Length(ConjugacyClasses(G));
  228.   return List(Filtered(DivisorsInt(s),i->i<=r),i->[i,k]);
  229. end;
  230.  
  231.  
  232. #############################################################################
  233. ##
  234. #F  PermGroupOps.Enumeration(<G>) . . . .  enumeration for permutation groups
  235. ##
  236. ##  enumerate elements of a PermGroup G, using the representation of an
  237. ##  element as product of the strong generators and identifying the numbers
  238. ##  of the respective coset representative with an multi-adic expansion of
  239. ##  the number.
  240. ##
  241. PermGroupOps.Enumeration:=function ( G )
  242.   local orbits,cosetreps,indices,ptpos,idx,pos,stab,reps,steps,i;
  243.  
  244.   # prepare special base (also used by CCE)
  245.   if not IsBound( G.smallestBase )  or G.smallestBase <> Base( G )  then
  246.       MakeStabChain( G, G.operations.MovedPoints( G ) );
  247.       G.smallestBase := Base( G );
  248.   fi;
  249.  
  250.   orbits := [  ];
  251.   cosetreps := [  ];
  252.   indices := [  ];
  253.   ptpos := [  ];
  254.   stab := G;
  255.   while stab.generators <> [  ]  do
  256.       idx := Length( stab.orbit );
  257.       reps := [  ];
  258.       reps[stab.orbit[1]] := ();
  259.       for i  in stab.orbit  do
  260.       reps[i] := stab.transversal[i] * reps[i ^ stab.transversal[i]];
  261.       od;
  262.       pos := [  ];
  263.       for i  in [ 1 .. idx ]  do
  264.       pos[stab.orbit[i]] := i - 1;
  265.       od;
  266.       Add( orbits, ShallowCopy( stab.orbit ) );
  267.       Add( cosetreps, reps );
  268.       Add( indices, idx );
  269.       Add( ptpos, pos );
  270.       stab := stab.stabilizer;
  271.   od;
  272.   steps := Length( indices );
  273.   return rec(
  274.     number := function ( G,elem )
  275.        local  num, ipt, i;
  276.  
  277.     # prepare special base (also used by CCE)
  278.     if not IsBound( G.smallestBase )  or G.smallestBase <> Base( G )  then
  279.         MakeStabChain( G, G.operations.MovedPoints( G ) );
  280.         G.smallestBase := Base( G );
  281.     fi;
  282.  
  283.        num := 0;
  284.        for i  in [ 1 .. steps ]  do
  285.        if elem <> ()  then
  286.            ipt := orbits[i][1] ^ elem;
  287.            num := num * indices[i] + ptpos[i][ipt];
  288.            elem := elem * cosetreps[i][ipt];
  289.        else
  290.            num := num * indices[i];
  291.        fi;
  292.        od;
  293.        return num + 1;
  294.     end,
  295.     element := function ( G,num )
  296.        local  n, elem, coef, i;
  297.  
  298.     # prepare special base (also used by CCE)
  299.     if not IsBound( G.smallestBase )  or G.smallestBase <> Base( G )  then
  300.         MakeStabChain( G, G.operations.MovedPoints( G ) );
  301.         G.smallestBase := Base( G );
  302.     fi;
  303.  
  304.        n:=num-1;
  305.        coef:=[];
  306.        for i in Reversed(indices) do
  307.      Add(coef,n mod i);
  308.      n:=QuoInt(n,i);
  309.        od;
  310.        coef := Reversed(coef)+1;
  311.        elem := ();
  312.        for i  in [ 1 .. steps ]  do
  313.        elem := elem * cosetreps[i][orbits[i][coef[i]]];
  314.        od;
  315.        return elem ^ (-1);
  316.    end  );
  317. end;
  318.  
  319.  
  320. #############################################################################
  321. ##
  322. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  323. ##
  324. ##  Local Variables:
  325. ##  mode:               outline
  326. ##  outline-regexp:     "#A\\|#F\\|#V\\|#E\\|#R"
  327. ##  tab-width:          2
  328. ##  fill-column:        73
  329. ##  fill-prefix:        "##  "
  330. ##  eval:               (hide-body)
  331. ##  End:
  332. ##
  333.  
  334.  
  335.  
  336.