home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / lattperm.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  25.1 KB  |  861 lines
  1. #############################################################################
  2. ##
  3. #A  lattperm.g                  GAP library                    J\"urgen Mnich
  4. ##
  5. #A  @(#)$Id: lattperm.g,v 3.4 1993/02/09 14:25:55 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains the permutation group specifications for calculating
  10. ##  the lattice of subgroups.
  11. ##
  12. #H  $Log: lattperm.g,v $
  13. #H  Revision 3.4  1993/02/09  14:25:55  martin
  14. #H  made undefined globals local
  15. #H
  16. #H  Revision 3.3  1992/03/17  12:31:20  jmnich
  17. #H  minor style changes, more bug fixes
  18. #H
  19. #H  Revision 3.2  1992/02/29  13:25:11  jmnich
  20. #H  general library review, some bug fixes
  21. #H
  22. #H  Revision 3.1  1992/02/12  15:37:22  martin
  23. #H  initial revision under RCS
  24. #H
  25. ##
  26.  
  27.  
  28. #############################################################################
  29. ##
  30. #F  PermGroupOps.Zuppos( <group> )  . . . . . . . . . . . . .  compute zuppos
  31. ##
  32. ##  This  functions  handles  the special case for zuppo calculation when the
  33. ##  given  group  is  a permutation group.  In this case there is an internal
  34. ##  function 'SmallestGeneratorPerm' that is used here.
  35. ##
  36. PermGroupOps.Zuppos := function( group )
  37.     local   zuppos, zuppo_gens, zuppo_powers, zuppo_primes, zuppo_exponents,
  38.             nz, zg, elems, pos, cyc, known, order, forder, good, bad, x, p;
  39.  
  40.     if IsParent( group ) then
  41.  
  42.         # initialize the calculated data
  43.  
  44.         nz := 0;
  45.         zuppos := [];
  46.         zuppo_gens := [ false ];
  47.         zuppo_powers := [];
  48.         zuppo_primes := [];
  49.         zuppo_exponents := [];
  50.  
  51.         # remember good and bad orders
  52.  
  53.         good := [];
  54.         bad  := [ 1 ];
  55.  
  56.         # sorry, but we will loop over all elements
  57.  
  58.         elems := Elements( group );
  59.  
  60.         for pos in [1..Length( elems )] do
  61.  
  62.             order := OrderPerm( elems[pos] );
  63.  
  64.             # check whether it yields a zuppo
  65.  
  66.             if not (order in good or order in bad) then
  67.                 if IsPrimePowerInt( order ) then
  68.                     AddSet( good, order );
  69.                 else
  70.                     AddSet( bad, order );
  71.                 fi;
  72.             fi;
  73.  
  74.             if order in good then
  75.  
  76.                 zg := SmallestGeneratorPerm( elems[pos] );
  77.  
  78.                 if zg = elems[pos] then
  79.  
  80.                     # we have found a new zuppo.
  81.  
  82.                     forder := Factors( order );
  83.  
  84.                     nz := nz + 1;
  85.                     zg := nz;
  86.                     AddSet( zuppos, elems[pos] );
  87.                     zuppo_primes[nz]    := forder[1];
  88.                     zuppo_exponents[nz] := Length( forder );
  89.                     if zuppo_exponents[nz] = 1 then
  90.                         zuppo_powers[nz] := 1;
  91.                     else
  92.                         zuppo_powers[nz] := Position( elems, elems[pos] ^ forder[1] );
  93.                     fi;
  94.  
  95.                 else
  96.  
  97.                     zg := Position( zuppos, zg );
  98.  
  99.                 fi;
  100.  
  101.                 zuppo_gens[pos] := zg;
  102.             fi;
  103.         od;
  104.  
  105.         # correct the values in zuppo_powers to contain 'zuppos' elements
  106.  
  107.         for x in [1..nz] do
  108.             zuppo_powers[x] := zuppo_gens[zuppo_powers[x]];
  109.         od;
  110.  
  111.         group.zuppos := zuppos;
  112.         group.zuppo_generators := zuppo_gens;
  113.         group.zuppo_powers := zuppo_powers;
  114.         group.zuppo_primes := zuppo_primes;
  115.         group.zuppo_exponents := zuppo_exponents;
  116.         group.conjugateZuppoBlist := BlistList( zuppos, [] );
  117.  
  118.     else
  119.  
  120.         zuppos := Intersection( Zuppos( Parent( group ) ), Elements( group ) );
  121.  
  122.     fi;
  123.  
  124.     Unbind( group.elements );
  125.  
  126.     return zuppos;
  127. end;
  128.  
  129.  
  130. PermGroupOps.PlainZuppos := function( group )
  131.     local   zuppos, zuppo_gens, zuppo_powers, zuppo_primes, zuppo_exponents,
  132.             nz, zg, elems, pos, cyc, known, order, forder, good, bad, x, p;
  133.  
  134.     # initialize the calculated data
  135.  
  136.     nz := 0;
  137.     zuppos := [];
  138.     zuppo_gens := [ false ];
  139.     zuppo_powers := [];
  140.     zuppo_primes := [];
  141.     zuppo_exponents := [];
  142.  
  143.     # remember good and bad orders
  144.  
  145.     good := [];
  146.     bad  := [ 1 ];
  147.  
  148.     # sorry, but we will loop over all elements
  149.  
  150.     elems := Elements( group );
  151.  
  152.     for pos in [1..Length( elems )] do
  153.  
  154.         order := OrderPerm( elems[pos] );
  155.  
  156.         # check whether it yields a zuppo
  157.  
  158.         if not (order in good or order in bad) then
  159.             if IsPrimePowerInt( order ) then
  160.                 AddSet( good, order );
  161.             else
  162.                 AddSet( bad, order );
  163.             fi;
  164.         fi;
  165.  
  166.         if order in good then
  167.  
  168.             zg := SmallestGeneratorPerm( elems[pos] );
  169.  
  170.             if zg = elems[pos] then
  171.  
  172.                 # we have found a new zuppo.
  173.  
  174.                 forder := Factors( order );
  175.  
  176.                 nz := nz + 1;
  177.                 zg := nz;
  178.                 AddSet( zuppos, elems[pos] );
  179.                 zuppo_primes[nz]    := forder[1];
  180.                 zuppo_exponents[nz] := Length( forder );
  181.                 if zuppo_exponents[nz] = 1 then
  182.                     zuppo_powers[nz] := 1;
  183.                 else
  184.                     zuppo_powers[nz] := Position( elems, elems[pos] ^ forder[1] );
  185.                 fi;
  186.  
  187.             else
  188.  
  189.                 zg := Position( zuppos, zg );
  190.  
  191.             fi;
  192.  
  193.             zuppo_gens[pos] := zg;
  194.         fi;
  195.     od;
  196.  
  197.     # correct the values in zuppo_powers to contain 'zuppos' elements
  198.  
  199.     for x in [1..nz] do
  200.         zuppo_powers[x] := zuppo_gens[zuppo_powers[x]];
  201.     od;
  202.  
  203.     group.zuppos := zuppos;
  204.     group.zuppo_generators := zuppo_gens;
  205.     group.zuppo_powers := zuppo_powers;
  206.     group.zuppo_primes := zuppo_primes;
  207.     group.zuppo_exponents := zuppo_exponents;
  208.     group.conjugateZuppoBlist := BlistList( zuppos, [] );
  209.  
  210.     Unbind( group.elements );
  211.  
  212.     return zuppos;
  213. end;
  214.  
  215.  
  216. PermGroupOps.SylowZuppos := function( group )
  217.     local   zuppos, zuppo_gens, zuppo_powers, zuppo_primes, zuppo_exponents,
  218.             g, p, S, Szup, zuporb, N, T, t, i;
  219.  
  220.     zuppos := [];
  221.     zuppo_gens := [ false ];
  222.     zuppo_powers := [];
  223.     zuppo_primes := [];
  224.     zuppo_exponents := [];
  225.  
  226.     for p in Set( Factors( Size( group ) ) ) do
  227.  
  228.         InfoLattice1( "#I  Prime ", p, "\n" );
  229.  
  230.         S := SylowSubgroup( group, p );
  231.         Szup := S.operations.PlainZuppos( S );
  232.         zuporb := [];
  233.  
  234.         InfoLattice1( "#I  ", Length( Szup ), " Zuppos\n" );
  235.  
  236.         for g in Szup do
  237.  
  238.             # Zuppos of S may be conjugate, so test first if g is new
  239.  
  240.             if not g in zuporb then
  241.  
  242.                 N := group.operations.Normalizer( group,
  243.                                                   Subgroup( group, [ g ] ) );
  244.                 MakeStabChain( N, group.operations.Base( group ) );
  245.                 ExtendStabChain( N, group.operations.Base( group ) );
  246.                 T := group.operations.RightCosetRepsStab( group, N );
  247.  
  248.                 InfoLattice1( "#I   ", Length( T ), " conjugates\n" );
  249.  
  250.                 for t in T do
  251.                     AddSet( zuporb, SmallestGeneratorPerm( g ^ t ) );
  252.                 od;
  253.             fi;
  254.         od;
  255.  
  256.         UniteSet( zuppos, zuporb );
  257.     od;
  258.  
  259.     InfoLattice1( "#I  calculating powers...\n" );
  260.  
  261.     zuppo_powers := ShallowCopy( zuppos );
  262.     for i in [1..Length( zuppos )] do
  263.         p := Factors( OrderPerm( zuppos[i] ) )[1];
  264.         g := zuppos[i] ^ p;
  265.         if g <> group.identity then
  266.             zuppo_powers[i] := Position( zuppos, SmallestGeneratorPerm( g ) );
  267.         else
  268.             zuppo_powers[i] := false;
  269.         fi;
  270.     od;
  271.  
  272.     InfoLattice1( "#I  ...done\n" );
  273.  
  274.     group.zuppos := zuppos;
  275.     group.zuppo_generators := zuppo_gens;
  276.     group.zuppo_powers := zuppo_powers;
  277.     group.zuppo_primes := zuppo_primes;
  278.     group.zuppo_exponents := zuppo_exponents;
  279.     group.conjugateZuppoBlist := BlistList( zuppos, [] );
  280.  
  281.     return zuppos;
  282. end;
  283.  
  284.  
  285. #############################################################################
  286. ##
  287. #F  PermGroupOps.ZuppoBlist( <group> )  . . . . . . . compute blist of zuppos
  288. ##
  289. ##  This  functions  computes the zuppos of a group represented as a blist on
  290. ##  the zuppos of the parent group.
  291. ##
  292. PermGroupOps.ZuppoBlist := function( group )
  293.     local   zuppob, rng;
  294.  
  295.     if IsParent( group ) then
  296.         rng    := [1 .. Length( Zuppos( group ) )];
  297.         zuppob := BlistList( rng, rng );
  298.     elif IsBound( group.zuppos ) then
  299.         zuppob := BlistList( Zuppos( Parent( group ) ), group.zuppos );
  300.     else
  301.         zuppob := BlistList( Zuppos( Parent( group ) ), Elements( group ) );
  302.         Unbind( group.elements );
  303.     fi;
  304.  
  305.     return zuppob;
  306. end;
  307.  
  308.  
  309. #############################################################################
  310. ##
  311. #F  PermGroupOps.GeneratorZuppos  . . . . . . determine zuppos for generators
  312. ##
  313. PermGroupOps.GeneratorZuppos := function( H )
  314.     local   g, facord, prm, coprm, p, gzup;
  315.  
  316.     gzup := [];
  317.     for g in H.generators do
  318.         facord := Factors( OrderPerm( g ) );
  319.         for prm in Set( facord ) do
  320.             coprm := 1;
  321.             for p in facord do if p <> prm then coprm := coprm * p; fi; od;
  322.             Add( gzup, SmallestGeneratorPerm( g ^ coprm ) );
  323.         od;
  324.     od;
  325.     return gzup;
  326. end;
  327.  
  328.  
  329. #############################################################################
  330. ##
  331. #F  PermGroupOps.GeneratorZuppoBlist  . . determine zuppoblist for generators
  332. ##
  333. PermGroupOps.GeneratorZuppoBlist := function( H )
  334.     local   g, facord, prm, coprm, p, gzup, zuppos;
  335.  
  336.     zuppos := Zuppos( Parent( H ) );
  337.     gzup   := BlistList( zuppos, [] );
  338.     for g in H.generators do
  339.         facord := Factors( OrderPerm( g ) );
  340.         for prm in Set( facord ) do
  341.             coprm := 1;
  342.             for p in facord do if p <> prm then coprm := coprm * p; fi; od;
  343.             gzup[Position( zuppos, SmallestGeneratorPerm( g ^ coprm ) )] := true;
  344.         od;
  345.     od;
  346.     return gzup;
  347. end;
  348.  
  349.  
  350. #############################################################################
  351. ##
  352. #F  PermGroupOps.ConjugateZuppos( <group>, <conjugand> )  . . . . . . . . . .
  353. #F  . . . . . . . . . . . . . . . . . . . . compute blist of conjugate zuppos
  354. ##
  355. ##
  356. ##
  357. PermGroupOps.ConjugateZuppos := function( H, g )
  358.     local   zuppos, zuppop, i;
  359.  
  360.  
  361.     if g = H.identity then
  362.         return Zuppos( H );
  363.     fi;
  364.  
  365.     zuppop := Zuppos( Parent( H ) );
  366.     zuppos := ShallowCopy( Zuppos( H ) );
  367.     for i in [1..Length( zuppos )] do
  368.         zuppos[i] := SmallestGeneratorPerm( zuppos[i] ^ g );
  369.     od;
  370.  
  371.     return Set( zuppos );
  372. end;
  373.  
  374.  
  375. #############################################################################
  376. ##
  377. #F  PermGroupOps.ConjugateZuppoBlist( <group>, <conjugand> )  . . . . . . . .
  378. #F  . . . . . . . . . . . . . . . . . . . . compute blist of conjugate zuppos
  379. ##
  380. ##
  381. ##
  382. PermGroupOps.ConjugateZuppoBlist := function( H, g )
  383.     local   zuppob, zuppop, x;
  384.  
  385.     if g = H.identity then
  386.         return ZuppoBlist( H );
  387.     fi;
  388.  
  389.     zuppop := Zuppos( Parent( H ) );
  390.     zuppob := Parent( H ).conjugateZuppoBlist;
  391.     SubtractBlist( zuppob, zuppob );
  392.     for x in Zuppos( H ) do
  393.         zuppob[Position( zuppop, SmallestGeneratorPerm( x ^ g ) )] := true;
  394.     od;
  395.  
  396.     return zuppob;
  397. end;
  398.  
  399.  
  400. #############################################################################
  401. ##
  402. #F  PermGroupOps.SetLatticeStatus( <L>, <object>, <status> )  . . . . . . . .
  403. #F  . . . . . . . . . . . . . . . . . . . . . . set status of lattice objects
  404. ##
  405. ##  returns
  406. ##
  407. ##      [ <class>, <conjugand>, <isnew> ]
  408. ##
  409. ##
  410. PermGroupOps.SetLatticeStatus := function( L, H, status )
  411.     local   G, CH, N, CN, C, CC, T, equals, qequals, subs, sups,
  412.             hzup, czup, gzup, isnew, issup, size, nelem, pos, t, i, x;
  413.  
  414.  
  415.     G := L.group;
  416.  
  417.     # the first step is to convert H to a conjugacy class of subgroups
  418.     # if it is a group.
  419.  
  420.     if IsGroup( H ) then
  421.  
  422.         # determine its layer
  423.  
  424.         CH   := ConjugacyClassSubgroups( G, H );
  425.         size := Size( H );
  426.  
  427.         if size = 1 then    CH.layer := 0;
  428.         else                CH.layer := Length( Factors( size ) );
  429.         fi;
  430.  
  431.         CH.status := "0 new";
  432.  
  433.     else
  434.  
  435.         CH   := H;
  436.         H    := CH.representative;
  437.         size := Size( H );
  438.  
  439.         if not IsBound( CH.status ) then
  440.             if size = 1 then    CH.layer := 0;
  441.             else                CH.layer := Length( Factors( size ) );
  442.             fi;
  443.  
  444.             CH.status := "0 new";
  445.         fi;
  446.  
  447.     fi;
  448.  
  449.     InfoLattice2( "#I  setstatus ", H, ", size ", size, " to ", status,
  450.                   "in layer ", CH.layer, "\n" );
  451.  
  452.     # if the status of the class is higher than the requested one,
  453.     # return it itself.
  454.  
  455.     if CH.status >= status then
  456.         return [ CH, G.identity, false ];
  457.     fi;
  458.  
  459.     # find list of possibly equal classes
  460.  
  461.     if IsBound( CH.equalClasses ) then
  462.  
  463.         # this has been done already
  464.  
  465.         equals := CH.equalClasses;
  466.  
  467.     elif CH.status >= "2 class" then
  468.  
  469.         # there is no need to test for equality if the class has already
  470.         # been added to the lattice.
  471.  
  472.         equals := [];
  473.  
  474.     else
  475.  
  476.         # o.k. now, go through the list of classes and have a look.
  477.  
  478.         gzup := GeneratorZuppoBlist( H );
  479.         equals := [];
  480.         for CC in L.classes do
  481.             C := CC.representative;
  482.             if C.size = size then
  483.                 if IsSubsetBlist( ZuppoBlist( C ), gzup ) then
  484.  
  485.                     # we were able to identify the representative
  486.  
  487.                     L.statistics.equalGroups := L.statistics.equalGroups + 1;
  488.                     if IsBound( CH.normalsubgroups ) then
  489.                         for x in CH.normalsubgroups do
  490.                             x.normalizerLattice := [ CC, G.identity ];
  491.                         od;
  492.                     fi;
  493.                     InfoLattice2( "#I  ...found in lattice\n" );
  494.                     return [ CC, G.identity, false ];
  495.  
  496.                 else
  497.                     Add( equals, CC );
  498.                 fi;
  499.             fi;
  500.         od;
  501.     fi;
  502.  
  503.     # now go on and improve the objects status one by one.
  504.     # first: shall we add the group to the queue ?
  505.  
  506.     if status = "1 group" then
  507.  
  508.         # make sure H is not already in the queue
  509.  
  510.         gzup := GeneratorZuppoBlist( H );
  511.  
  512.         for i in [1..Length( L.queue )] do
  513.             if IsBound( L.queue[i] ) then
  514.                 CC := L.queue[i];
  515.                 C  := CC.representative;
  516.                 if C.size = size then
  517.                     if IsSubsetBlist( ZuppoBlist( C ), gzup ) then
  518.  
  519.                         # oh, yes. there is a queue group equal to ours.
  520.  
  521.                         L.statistics.equalGroups := L.statistics.equalGroups + 1;
  522.                         if IsBound( CH.normalsubgroups ) then
  523.                             if not IsBound( CC.normalsubgroups ) then
  524.                                 CC.normalsubgroups := [];
  525.                             fi;
  526.                             for x in CH.normalsubgroups do
  527.                                 x.normalizerLattice := [ CC, G.identity ];
  528.                                 Add( CC.normalsubgroups, x );
  529.                             od;
  530.                         fi;
  531.                         InfoLattice2( "#I  ...found in queue\n" );
  532.                         return [ CC, G.identity, false ];
  533.  
  534.                     fi;
  535.                 fi;
  536.             fi;
  537.         od;
  538.  
  539.         InfoLattice1( "#I  ...added to queue\n" );
  540.  
  541.         CH.status       := "1 group";
  542.         CH.equalClasses := equals;
  543.  
  544.         Add( L.queue, CH );
  545.  
  546.         return [ CH, G.identity, false ];
  547.     fi;
  548.  
  549.     # the class will have higher status than being a queue group so
  550.     # remove the list of possibly equal classes.
  551.  
  552.     Unbind( CH.equalClasses );
  553.  
  554.     # second: shall we add the group to the lattice ?
  555.  
  556.     if CH.status < "2 class" and status >= "2 class" then
  557.  
  558.         # if we have to create the class we need the normalizer of H
  559.         # and its (right) transversal in G.
  560.  
  561.         InfoLattice2( "#I  calculating normalizer of H\n" );
  562.  
  563.         N  := G.operations.Normalizer( G, H );
  564.         CN := ConjugacyClassSubgroups( G, N );
  565.         T  := G.operations.RightTransversal( G, N );
  566.  
  567.         L.statistics.normalizers := L.statistics.normalizers + 1;
  568.  
  569.         CN.normalsubgroups   := [ CH ];
  570.         CH.normalizerLattice := [ CN, G.identity ];
  571.         CH.conjugands        := T;
  572.         CH.size              := Length( T );
  573.  
  574.         if Size( N ) <> size then
  575.  
  576.             InfoLattice2( "#I  handling normalizer\n" );
  577.  
  578.             isnew := SetLatticeStatus( L, CN, L.calculatedGroups );
  579.             CH.normalizerLattice := [ isnew[1], isnew[2] ];
  580.             isnew := isnew[3];
  581.  
  582.         else
  583.  
  584.             InfoLattice2( "#I  group is selfnormal -- no handling\n" );
  585.  
  586.             CH.normalizerLattice := [ CH, G.identity ];
  587.             isnew := false;
  588.  
  589.         fi;
  590.  
  591.         # if H's normalizer wasn't known before, H itself must be new.
  592.  
  593.         if isnew then
  594.             equals := [];
  595.         fi;
  596.  
  597.         # we continue with the determination of possible subgroups...
  598.  
  599.         subs := [];
  600.         for CC in L.classes do
  601.             C := CC.representative;
  602.             if CC.layer = CH.layer - 1 and CC.status = "3 extending"
  603.               and size mod C.size = 0 then
  604.                 Add( subs, CC );
  605.             fi;
  606.         od;
  607.  
  608.         # ... and the possibly equal queue groups
  609.  
  610.         gzup    := GeneratorZuppoBlist( H );
  611.         qequals := [];
  612.         for i in [1..Length( L.queue )] do
  613.             if IsBound( L.queue[i] ) then
  614.                 CC := L.queue[i];
  615.                 C  := CC.representative;
  616.                 if C.size = size then
  617.                     if IsSubsetBlist( ZuppoBlist( C ), gzup ) then
  618.  
  619.                         # oh, there is a group in the queue equal to ours.
  620.  
  621.                         L.statistics.equalGroups := L.statistics.equalGroups + 1;
  622.                         if IsBound( CC.normalsubgroups ) then
  623.                             if not IsBound( CH.normalsubgroups ) then
  624.                                 CH.normalsubgroups := [];
  625.                             fi;
  626.                             for x in CC.normalsubgroups do
  627.                                 x.normalizerLattice := [ CH, G.identity ];
  628.                                 Add( CH.normalsubgroups, x );
  629.                             od;
  630.                         fi;
  631.                         InfoLattice2( "#I  ...found in queue\n" );
  632.                         Unbind( L.queue[i] );
  633.  
  634.                     else
  635.                         Add( qequals, i );
  636.                     fi;
  637.                 fi;
  638.             fi;
  639.         od;
  640.  
  641.         # is there anything to do with the conjugates so far ?
  642.  
  643.         if equals = [] and qequals = [] and subs = [] then
  644.             T := [];
  645.         fi;
  646.  
  647.         # generate each conjugate, i.e. its zuppos one after the other,
  648.         # performing all necessary actions with each zuppo blist right
  649.         # here.
  650.  
  651.         InfoLattice2( "#I  conjugating H\n" );
  652.  
  653.         for t in T do
  654.  
  655.             czup := H.operations.ConjugateZuppoBlist( H, t );
  656.             L.statistics.conjugateZuppos := L.statistics.conjugateZuppos + 1;
  657.  
  658.             # first check whether this conjugate is the representative of a
  659.             # known class of subgroups
  660.  
  661.             for CC in equals do
  662.                 C := CC.representative;
  663.                 if ZuppoBlist( C ) = czup then
  664.  
  665.                     # in fact there is a class that contains the conjugate
  666.  
  667.                     L.statistics.equalGroups := L.statistics.equalGroups + 1;
  668.                     if IsBound( CH.normalsubgroups ) then
  669.                         for x in CH.normalsubgroups do
  670.                             x.normalizerLattice := [ CC, t^-1 * x.normalizerLattice[2] ];
  671.                         od;
  672.                     fi;
  673.                     InfoLattice2( "#I  ...found in lattice\n" );
  674.                     return [ CC, t^-1, false ];
  675.  
  676.                 fi;
  677.             od;
  678.  
  679.             # next check whether this group is a member of the queue
  680.  
  681.             for i in qequals do
  682.                 if IsBound( L.queue[i] ) then
  683.                     CC := L.queue[i];
  684.                     C  := CC.representative;
  685.                     if ZuppoBlist( C ) = czup then
  686.  
  687.                         # bingo, we found a group in the queue equal to the
  688.                         # conjugate of H.
  689.  
  690.                         L.statistics.equalGroups := L.statistics.equalGroups + 1;
  691.                         if IsBound( CC.normalsubgroups ) then
  692.                             if not IsBound( CH.normalsubgroups ) then
  693.                                 CH.normalsubgroups := [];
  694.                             fi;
  695.                             for x in CC.normalsubgroups do
  696.                                 x.normalizerLattice := [ CH, t ];
  697.                                 Add( CH.normalsubgroups, x );
  698.                             od;
  699.                         fi;
  700.                         InfoLattice2( "#I  identified queue group\n" );
  701.                         Unbind( L.queue[i] );
  702.  
  703.                     fi;
  704.                 fi;
  705.             od;
  706.  
  707.             # next reduce the extendingZuppos blists of those classes that are
  708.             # yet to be extended and whose representative may be a subgroup
  709.             # of this conjugate.
  710.  
  711.             for CC in subs do
  712.                 C := CC.representative;
  713.                 if IsSubsetBlist( czup, ZuppoBlist( C ) ) then
  714.                     InfoLattice2( "#I  found a subgroup\n" );
  715.                     SubtractBlist( CC.extendingZuppos, czup );
  716.                 fi;
  717.             od;
  718.         od;
  719.  
  720.         # the group survived this step, so it is new
  721.  
  722.         CH.status := "2 class";
  723.  
  724.         Unbind( CH.normalsubgroups );
  725. #T        Unbind( CH.conjugands );
  726.         Add( L.classes, CH );
  727.  
  728.         InfoLattice1( "#I  Class of size ", size, " and length ", CH.size, " added\n" );
  729.     fi;
  730.  
  731.     # third: shall the extendingZuppos blist of the class be created ?
  732.  
  733.     if CH.status < "3 extending" and status >= "3 extending"
  734.       and not LatticeBreak then
  735.  
  736.         # initialize the extendingZuppos blist
  737.  
  738.         CH.extendingZuppos := ShallowCopy(
  739.             CH.normalizerLattice[1].representative.operations.ConjugateZuppoBlist(
  740.                 CH.normalizerLattice[1].representative,
  741.                 CH.normalizerLattice[2]
  742.             )
  743.         );
  744.         SubtractBlist( CH.extendingZuppos, ZuppoBlist( H ) );
  745.         L.statistics.conjugateZuppos := L.statistics.conjugateZuppos + 1;
  746.  
  747.         # change it to reflect the proper list of extending zuppos.
  748.  
  749.         gzup := GeneratorZuppos( H );
  750.  
  751.         for CC in L.classes do
  752.             C := CC.representative;
  753.             if CC.layer = CH.layer + 1 and C.size mod size = 0 then
  754.                 T    := CC.conjugands;
  755.                 czup := ZuppoBlist( C );
  756.                 for t in T do
  757.                     issup := true;
  758.                     i     := Length( gzup );
  759.                     x     := t ^ -1;
  760.                     while issup and i > 0 do
  761.                         issup := czup[Position( G.zuppos, SmallestGeneratorPerm( gzup[i]^x ) )];
  762.                         i := i - 1;
  763.                     od;
  764.                     if issup then
  765.                         InfoLattice2( "#I  supergroup found\n" );
  766.                         SubtractBlist( CH.extendingZuppos, C.operations.ConjugateZuppoBlist( C, t ) );
  767.                         L.statistics.conjugateZuppos := L.statistics.conjugateZuppos + 1;
  768.                     fi;
  769.                 od;
  770.             fi;
  771.         od;
  772.  
  773.         CH.status := "3 extending";
  774.     fi;
  775.  
  776.     # fourth: shall we calculate all cyclic extensions of H ?
  777.  
  778.     if CH.status < "4 extended" and status >= "4 extended"
  779.       and not LatticeBreak then
  780.  
  781.         InfoLattice2( "#I  calculating extensions of H\n" );
  782.  
  783.         hzup := ZuppoBlist( H );
  784.         pos  := Position( CH.extendingZuppos, true );
  785.  
  786.         while pos <> false and not LatticeBreak do
  787.  
  788.             # is the zuppo generator of prime index over H ?
  789.  
  790.             if G.zuppo_powers[pos] = false or hzup[G.zuppo_powers[pos]] then
  791.  
  792.                 # put everything we know into N
  793.  
  794.                 N  := G.operations.Subgroup( G, Concatenation( H.generators, [ G.zuppos[pos] ] ) );
  795.                 CN := ConjugacyClassSubgroups( G, N );
  796.                 CN.equalClasses := [];
  797.  
  798.                 # finally, add it to the lattice
  799.  
  800.                 SetLatticeStatus( L, CN, L.extensionGroups );
  801.                 L.statistics.extensions := L.statistics.extensions + 1;
  802.             fi;
  803.  
  804.             CH.extendingZuppos[pos] := false;
  805.             pos := Position( CH.extendingZuppos, true, pos );
  806.         od;
  807.  
  808.         if not LatticeBreak then
  809.  
  810.             # cleanup H
  811.  
  812.             CH.status := "4 extended";
  813.             Unbind( CH.extendingZuppos );
  814.             Unbind( H.generatorZuppos );
  815.             Unbind( H.generatorZuppoBlist );
  816.             Unbind( H.elements );
  817.  
  818.             if not IsParent( H ) then
  819.                 Unbind( H.zuppos );
  820.                 Unbind( H.stabilizer );
  821.                 Unbind( H.orbit );
  822.                 Unbind( H.transversal );
  823.             fi;
  824.  
  825.             InfoLattice2( "#I  extensions of H done\n" );
  826.         fi;
  827.     fi;
  828.  
  829.     return [ CH, G.identity, true ];
  830. end;
  831.  
  832.  
  833. #############################################################################
  834. ##
  835. #F  PermGroupOps.RightTransversal( <G>, <H> ) . determine a right transversal
  836. ##
  837. ##  returns
  838. ##
  839. ##      <list>
  840. ##
  841. PermGroupOps.RightTransversal := function( G, H )
  842.  
  843.     MakeStabChain( H, G.operations.Base( G ) );
  844.     ExtendStabChain( H, G.operations.Base( G ) );
  845.     return G.operations.RightCosetRepsStab( G, H );
  846. end;
  847.  
  848.  
  849. #############################################################################
  850. ##
  851. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  852. ##
  853. ##  Local Variables:
  854. ##  mode:               outline
  855. ##  outline-regexp:     "#F\\|#V\\|#E"
  856. ##  fill-column:        73
  857. ##  fill-prefix:        "##  "
  858. ##  eval:               (hide-body)
  859. ##  End:
  860. ##
  861.