Quelle grppcnrm.gi Sprache: unbekannt

#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Frank Celler.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains the methods for normalizers of polycyclic groups.
##

#############################################################################
##
#F PCGS_STABILIZER( <pcgs>, <pnt>, <op> ) . . . . . . . . . . . . . . local
##
BindGlobal( "PCGS_STABILIZER", function( arg )
 local pcgs, pnt, op, data, one, orb, prod, n, s, i,
 mi, np, j, o, len, l1, k, l2, r, e, stab, ros,dict;

 pcgs := arg[1];
 pnt := arg[2];
 op := arg[3];
 one := OneOfPcgs(pcgs);
 ros := RelativeOrders(pcgs);
 pcgs := ShallowCopy(pcgs);
 dict:=NewDictionary(pnt,true,true);

 # without data blob
 if Length(arg) = 3 then

 # operate on canonical versions
 pnt := op( pnt, one );

 # store representatives in <r>
 orb := [ pnt ];
 AddDictionary(dict,pnt,1);
 prod := [ 1 ];
 n := [];
 s := [];
 stab := [];

 # go *up* the composition series
 for i in Reversed([1..Length(pcgs)]) do
 mi := pcgs[i];
 np := op( pnt, mi );

 # is <np> really a new point or is it in <orb>
 j := LookupDictionary(dict, np );

 # add it if it is new
 if j = fail then
 o := ros[i];
 Add( prod, Last(prod) * o );
 Add( n, i );
 len := Length(orb);
 l1 := 0;
 for k in [ 1 .. o-1 ] do
 l2 := l1 + len;
 for j in [ 1 .. len ] do
 orb[j+l2] := op( orb[j+l1], mi );
 AddDictionary(dict,orb[j+l2],j+l2);
 od;
 l1 := l2;
 od;

 # if it is the start point the element stabilizes
 elif j = 1 then
 Add( s, mi );

 # compute a stabilizing element
 else
 if not IsBound(stab[j]) then
 r := one;
 l1 := j-1;
 len := Length(prod);
 for k in [ 1 .. len-1 ] do
 e := QuoInt( l1, prod[len-k] );
 r := pcgs[n[len-k]]^e * r;
 l1 := l1 mod prod[len-k];
 if l1 = 0 then
 break;
 fi;
 od;
 stab[j] := r;
 fi;
 Add( s, pcgs[i] / stab[j] );
 fi;
 od;

 # with data blob
 else
 data := arg[4];

 # operate on canonical versions
 pnt := op( data, pnt, one );

 # store representatives in <r>
 orb := [ pnt ];
 AddDictionary(dict,pnt,1);
 prod := [ 1 ];
 n := [];
 s := [];
 stab := [];

 # go *up* the composition series
 for i in Reversed([1..Length(pcgs)]) do
 mi := pcgs[i];
 np := op( data, pnt, mi );

 # is <np> really a new point or is it in <orb>
 j := LookupDictionary(dict, np );

 # add it if it is new
 if j = fail then
 o := ros[i];
 Add( prod, Last(prod) * o );
 Add( n, i );
 len := Length(orb);
 l1 := 0;
 for k in [ 1 .. o-1 ] do
 l2 := l1 + len;
 for j in [ 1 .. len ] do
 orb[j+l2] := op( data, orb[j+l1], mi );
 AddDictionary(dict,orb[j+l2],j+l2);
 od;
 l1 := l2;
 od;

 # if it is the start point the element stabilizes
 elif j = 1 then
 Add( s, mi );

 # compute a stabilizing element
 else
 if not IsBound(stab[j]) then
 r := one;
 l1 := j-1;
 len := Length(prod);
 for k in [ 1 .. len-1 ] do
 e := QuoInt( l1, prod[len-k] );
 r := pcgs[n[len-k]]^e * r;
 l1 := l1 mod prod[len-k];
 if l1 = 0 then
 break;
 fi;
 od;
 stab[j] := r;
 fi;
 Add( s, pcgs[i] / stab[j] );
 fi;
 od;
 fi;

 Info( InfoPcNormalizer, 3, "orbit length: ", Length(orb) );
 return Reversed(s);

end );

#############################################################################
##
#F PCGS_STABILIZER_HOMOMORPHIC( <pcgs>, <homs>, <pnt>, <op> ) . . . . local
##
BindGlobal( "PCGS_STABILIZER_HOMOMORPHIC", function( arg )
 local pcgs, homs, pnt, op, ros, one, hone, orb, prod,
 n, s, stab, i, mi, np, j, o, len, l1, k, l2,
 r, e, dict;

 pcgs := arg[1];
 homs := arg[2];
 pnt := arg[3];
 op := arg[4];
 dict:=NewDictionary(pnt,true,true);
 if 0 = Length(pcgs) then
 return pcgs;
 fi;
 if Length(pcgs) <> Length(homs) then
 Error( "expecting ", Length(pcgs), " homomorphic images in <homs>" );
 fi;
 ros := RelativeOrders(pcgs);
 one := OneOfPcgs(pcgs);
 hone := One(homs[1]);
 pcgs := ShallowCopy(pcgs);

 # without data blob
 if Length(arg) = 4 then

 # operate on canonical versions
 pnt := op( pnt, hone );

 # store representatives in <r>
 orb := [ pnt ];
 AddDictionary(dict,pnt,1);
 prod := [ 1 ];
 n := [];
 s := [];
 stab := [];

 # go *up* the composition series
 for i in Reversed([1..Length(pcgs)]) do
 mi := homs[i];
 np := op( pnt, mi );

 # is <np> really a new point or is it in <orb>
 j := LookupDictionary(dict, np );

 # add it if it is new
 if j = fail then
 o := ros[i];
 Add( prod, Last(prod) * o );
 Add( n, i );
 len := Length(orb);
 l1 := 0;
 for k in [ 1 .. o-1 ] do
 l2 := l1 + len;
 for j in [ 1 .. len ] do
 orb[j+l2] := op( orb[j+l1], mi );
 AddDictionary(dict,orb[j+l2],j+l2);
 od;
 l1 := l2;
 od;

 # if it is the start point the element stabilizes
 elif j = 1 then
 Add( s, pcgs[i] );

 # compute a stabilizing element
 else
 if not IsBound(stab[j]) then
 r := one;
 l1 := j-1;
 len := Length(prod);
 for k in [ 1 .. len-1 ] do
 e := QuoInt( l1, prod[len-k] );
 r := pcgs[n[len-k]]^e * r;
 l1 := l1 mod prod[len-k];
 if l1 = 0 then
 break;
 fi;
 od;
 stab[j] := r;
 fi;
 Add( s, pcgs[i] / stab[j] );
 fi;
 od;

 # with data blob, this case is not used at all
 else
 Error("you should never be here");
 fi;

 Info( InfoPcNormalizer, 3, "orbit length: ", Length(orb) );
 return Reversed(s);

end );

#############################################################################
##
#F PCGS_NORMALIZER( <home>, <norm>, <point>, <pcgs>, <modulo> )
##
BindGlobal( "PCGS_NORMALIZER_OPB", function( home, elm, obj )
 local ord;

 elm := elm^obj;
 ord := RelativeOrderOfPcElement( home, elm );
 return elm ^ ( 1 / LeadingExponentOfPcElement( home, elm ) mod ord );
end );

BindGlobal( "PCGS_NORMALIZER_OPC1", function( data, elm, obj )
 local ord;

 elm := elm^obj;
 ord := RelativeOrderOfPcElement( data[1], elm );
 elm := elm ^ ( 1 / LeadingExponentOfPcElement( data[1], elm ) mod ord );
 return HeadPcElementByNumber( data[1], elm, data[2] );
end );

BindGlobal( "PCGS_NORMALIZER_OPC2", function( data, elm, obj )
# was: return CanonicalPcElement( data[2], elm^obj );
local ord;
 elm := elm^obj;
 ord:=RelativeOrderOfPcElement(data[1],elm);
 elm := elm ^ ( 1 / LeadingExponentOfPcElement( data[1], elm ) mod ord );
 return CanonicalPcElement( data[2], elm );
end );

BindGlobal( "PCGS_NORMALIZER_OPD", function( data, lst, obj )
 lst:=CorrespondingGeneratorsByModuloPcgs(data,List(lst,i->i^obj));
 return lst;
end );

BindGlobal( "PCGS_NORMALIZER_OPE", function( data, lst, obj )
 local home, pag, pos, max, i, g, dg, exp, j, ros;

 home := data[1];
 pag := data[2]; # make sure to reset <pag> before returning
 pos := [];
 max := data[3];
 ros := data[4];
 for i in [ Length(lst), Length(lst)-1 .. 1 ] do
 g := lst[i]^obj;
 dg := DepthOfPcElement( home, g );
 while dg < max do
 if IsBound(pag[dg]) then
 g := ReducedPcElement( home, g, pag[dg] );
 dg := DepthOfPcElement( home, g );
 else
 pag[dg] := g;
 AddSet( pos, dg );
 break;
 fi;
 od;
 od;
 for i in Reversed(pos) do
 exp := LeadingExponentOfPcElement( home, pag[i] );
 if exp <> 1 then
 pag[i] := pag[i] ^ (1/exp mod ros[i]);
 fi;
 for j in [ i+1 .. max-1 ] do
 if IsBound(pag[j]) then
 exp := ExponentOfPcElement( home, pag[i], j );
 if exp <> 0 then
 pag[i] := pag[i] * pag[j]^(ros[j]-exp);
 fi;
 fi;
 od;
 pag[i] := HeadPcElementByNumber( home, pag[i], max );
 od;
 lst := pag{pos};
 for i in pos do Unbind(pag[i]); od;
 return lst;
end );

BindGlobal( "PCGS_NORMALIZER_DATAE", function( home, modulo )
 local ros, sub, i, dg, exp, max;

 ros := RelativeOrders(home);
 sub := [];
 for i in modulo do
 dg := DepthOfPcElement( home, i );
 exp := LeadingExponentOfPcElement( home, i );
 if exp <> 1 then
 i := i ^ (1/exp mod ros[dg]);
 fi;
 sub[dg] := i;
 od;
 max := Length(home)+1;
 while 2 <= max and IsBound(sub[max-1]) do
 max := max-1;
 od;
 return [ home, sub, max, ros ];
end );

BindGlobal( "PCGS_NORMALIZER", function( home, pcgs, pnt, modulo )
 local op, s, data;

 Info( InfoPcNormalizer, 5, "home: ", ShallowCopy(home) );
 Info( InfoPcNormalizer, 4, "normalizer: ", ShallowCopy(pcgs) );
 Info( InfoPcNormalizer, 4, "point: ", ShallowCopy(pnt) );
 Info( InfoPcNormalizer, 5, "modulo: ", ShallowCopy(modulo) );

 # if <pnt> and <modulo> have the same length nothing is to be done
 if Length(pnt) = Length(modulo) then
 Info( InfoPcNormalizer, 3, "PCGS_NORMALIZER case A" );
 return pcgs;

 # if <pnt> mod <modulo> has only one element operate on elements
 elif Length(pnt)-1 = Length(modulo) then
 if 0 = Length(modulo) then
 Info( InfoPcNormalizer, 3, "PCGS_NORMALIZER case B" );
 pnt := pnt[1];
 op := PCGS_NORMALIZER_OPB;
 data := home;
 s := PCGS_STABILIZER( pcgs, pnt, op, home );
 else
 pnt := pnt mod modulo;
 pnt := pnt[1];
 if ParentPcgs(modulo)=home and IsTailInducedPcgsRep(modulo) then
 Info( InfoPcNormalizer, 3, "PCGS_NORMALIZER case C1" );
 op := PCGS_NORMALIZER_OPC1;
 data := [ home, modulo!.tailStart ];
 else
 Info( InfoPcNormalizer, 3, "PCGS_NORMALIZER case C2" );
 op := PCGS_NORMALIZER_OPC2;
 data := [home,modulo];
 fi;
 s := PCGS_STABILIZER( pcgs, pnt, op, data );
 fi;

 # if the <modulo> is trivial it is relatively easy
 elif 0 = Length(modulo) then
 Info( InfoPcNormalizer, 3, "PCGS_NORMALIZER case D" );
 op := PCGS_NORMALIZER_OPD;
 pnt := ShallowCopy(pnt);
 s := PCGS_STABILIZER( pcgs, pnt, op, home );

 # it is get more complicated
 else
 Info( InfoPcNormalizer, 3, "PCGS_NORMALIZER case E" );
 data := PCGS_NORMALIZER_DATAE( home, modulo );
 op := PCGS_NORMALIZER_OPE;
 pnt := ShallowCopy( pnt mod modulo );
 s := PCGS_STABILIZER( pcgs, pnt, op, data );
 fi;

 # convert it into a modulo pcgs
 pcgs := SumPcgs( home, DenominatorOfModuloPcgs(pcgs), s )
 mod DenominatorOfModuloPcgs(pcgs);
 Info( InfoPcNormalizer, 4, "new norm: ", ShallowCopy(pcgs) );
 return pcgs;

end );

#############################################################################
##
#F PCGS_NORMALIZER_LINEAR( <home>, <norm>, <point>, <modulo-pcgs> )
##
BindGlobal( "PCGS_NORMALIZER_LINEAR", function( home, pcgs, pnt, modulo )
local f, o, m, sub, s,p,op;

 Info( InfoPcNormalizer, 5, "home: ", ShallowCopy(home) );
 Info( InfoPcNormalizer, 4, "normalizer: ", ShallowCopy(pcgs) );
 Info( InfoPcNormalizer, 4, "point: ", ShallowCopy(pnt) );
 Info( InfoPcNormalizer, 5, "modulo: ", ShallowCopy(modulo) );

 # construct the linear operation
 p:=RelativeOrderOfPcElement( home, modulo[1] );
 f := GF(p);
 o := One(f);
 m := List( pcgs, x -> List( modulo, y ->
 ExponentsConjugateLayer( modulo, y,x ) * o ) );

 for s in [1..Length(m)] do
 m[s]:=ImmutableMatrix(f,m[s]);
 od;

 # convert <pnt> into a subspace
 sub := pnt mod DenominatorOfModuloPcgs(modulo);
 sub := List( sub, x -> ExponentsOfPcElement( modulo, x ) * o );
 sub:=ImmutableMatrix(f,sub);

 # select operation function and prepare matrices if necessary
 if p=2 then
 op:=OnSubspacesByCanonicalBasisGF2;
 else
 op:=OnSubspacesByCanonicalBasis;
 fi;

 # compute the stabilizer
 Info( InfoPcNormalizer, 3, "PCGS_NORMALIZER_LINEAR case A" );
 s := PCGS_STABILIZER_HOMOMORPHIC( pcgs, m, sub, op );

 # convert it into a modulo pcgs
 pcgs := SumPcgs( home, DenominatorOfModuloPcgs(pcgs), s )
 mod DenominatorOfModuloPcgs(pcgs);
 Info( InfoPcNormalizer, 4, "new norm: ", ShallowCopy(pcgs) );
 return pcgs;

end );

#############################################################################
##
#F PCGS_CONJUGATING_WORD_GS( <home>, <n>, , <v>, <k> )
##
## Let / <k> and <v> / <k> be two p-groups such that *<n> = <v>*<n>
## and let <n> be an elementary abelian q-group with q <> p. Then a word x
## of <n> with ^ x = <v> is returned. <k> must be normal in *<n>.
##
## It is important, that the weights of <K> are less than those of <N>.
##
BindGlobal( "PCGS_CONJUGATING_WORD_GS", function( home, n, u, v, k )
 local id, x, q, i, p, t, m, vv, mm, xx, j;

 # if <n> or / <k> is trivial, just return identity
 id := OneOfPcgs(home);
 if 0 = Length(n) or 0 = Length(u) or u = v then
 return id;
 fi;

 # Find the word <n> using the algorithm of Kantor. See S.P.Glasby and
 # Michael C. Slattery, "Computing intersections and normalizers in
 # soluble groups", 1989.

 x := id;
 q := RelativeOrderOfPcElement( home, n[1] );
 for i in Reversed( [ 1 .. Length(u) ] ) do

 # the orders must be coprime
 p := RelativeOrderOfPcElement( home, u[i] );
 if q = p then
 Error( "relative orders and <n> are not coprime" );
 fi;

 # Compute an integer <t> such that <t> * = -1 mod <q>.
 t := -Gcdex( p, q ).coeff1;
 while t > q do t := t - q; od;
 while t < 0 do t := t + q; od;

 m := LeftQuotient( u[i]^x, v[i] );
 m := SiftedPcElement( k, m );
 vv := id;
 mm := id;
 xx := id;

 # construct the product m^v * (m^2)^(v^2) * ... * (m^p-1)^(v^p-1)
 for j in [ 1 .. p-1 ] do
 vv := vv * v[i];
 mm := mm * m;
 xx := xx * ( mm^vv );
 od;
 x := x * ( xx ^ t );
 od;

 return x;

end );

#############################################################################
##
#F PCGS_NORMALIZER_GLASBY( <home>, <norm>, <nis>, <pcgs>, <modulo> )
##
BindGlobal( "PCGS_NORMALIZER_GLASBY", function( home, pcgs, nis, u1, u2 )
 local id, stb, data, pnt, i, cnj, ns, one, mats, sys,
 sol, v, j;

 # The situation is as follows:
 #
 # S
 # \
 # \
 # Us
 # / \
 # / \
 # U1 Ns N
 # \ / \ /
 # \ / \ /
 # U2 NiS
 # \ /
 # \ /
 # Un
 #
 # and <S> stabilizes <U2>

 # first correct (S mod NiS)
 Info( InfoPcNormalizer, 4, "correcting glasby block stabilizer" );
 id := OneOfPcgs(pcgs);
 stb := NumeratorOfModuloPcgs(pcgs) mod NumeratorOfModuloPcgs(nis);
 stb := ShallowCopy(stb);
 data := PCGS_NORMALIZER_DATAE( home, u2 );
 pnt := PCGS_NORMALIZER_OPE( data, u1 mod u2, id );
 for i in [ 1 .. Length(stb) ] do
 cnj := PCGS_NORMALIZER_OPE( data, pnt, stb[i] );
 cnj := PCGS_CONJUGATING_WORD_GS( home, nis, cnj, pnt, u2 );
 stb[i] := stb[i] * cnj;
 od;

 # now compute the stabilizer in <nis>
 Info( InfoPcNormalizer, 4, "computing the centralizer in <nis>" );

 # first the operation of <pnt> on (NiS mod U2)
 ns := SumPcgs( home, u2, NumeratorOfModuloPcgs(nis) ) mod u2;
 one := One( GF(RelativeOrderOfPcElement(home,ns[1])) );
 mats := List( pnt, x -> List( ns, y ->
 ExponentsConjugateLayer( ns, y,x ) * one ) );

 # set up the system of equations
 one := One(mats[1]);
 sys := [];
 for i in [ 1 .. Length(mats[1]) ] do
 sys[i] := [];
 for j in [ 1 .. Length(mats) ] do
 Append( sys[i], one[i] - mats[j][i] );
 od;
 od;
 sol := TriangulizedNullspaceMat(sys);
 for v in sol do
 v := List( v, IntFFE );
 Add( stb, PcElementByExponentsNC(ns,v) );
 od;

 # Now we have the normalizer in <S> / <U2>. Get the complete preimage.
 return SumPcgs( home, u2, stb )
 mod DenominatorOfModuloPcgs(pcgs);

end );

#############################################################################
##
#F PCGS_NORMALIZER_COBOUNDS( <home>, <norm>, <nis>, <pcgs>, <modulo> )
##
BindGlobal( "PCGS_NORMALIZER_COBOUNDS", function( home, pcgs, nis, u1, u2 )
 local ns, us, gf, one, data, u, ui, mats, t, l, i, b,
 nb, c, heads, k, ln1, ln2, op, stab, s, j, v;

 # The situation is as follows:
 #
 # S
 # \
 # \
 # Us
 # / \
 # / \
 # U1 Ns N
 # \ / \ /
 # \ / \ /
 # U2 NiS
 # \ /
 # \ /
 # Un
 #
 # and <S> stabilizes <U2>

 # compute the operation of <u1> mod <u2> on <ns> mod <u2>
 ns := SumPcgs( home, u2, NumeratorOfModuloPcgs(nis) ) mod u2;
 us := SumPcgs( home, u1, NumeratorOfModuloPcgs(nis) );
 gf := GF(RelativeOrderOfPcElement(home,ns[1]));
 one := One(gf);
 data := PCGS_NORMALIZER_DATAE( home, u2 );
 u := PCGS_NORMALIZER_OPE( data, u1 mod u2, OneOfPcgs(home) );
 ui := List( u, Inverse );
 mats := List( u, x -> List(ns, y -> ExponentsConjugateLayer(ns,y,x)*one) );

 # compute the coboundaries
 Info( InfoPcNormalizer, 4, "using coboundaries and centralizer" );

 t := One(mats[1]);
 l := [];
 for i in [ 1 .. Length(mats[1]) ] do
 l[i] := [];
 for j in [ 1 .. Length(mats) ] do
 Append( l[i], t[i]-mats[j][i] );
 od;
 od;
 b := TriangulizedGeneratorsByMatrix( ns, l, gf );
 nb := b[1];
 b := b[2];
 b := ImmutableMatrix(gf, b);

 # trivial coboundaries, use ordinary orbit
 if IsEmpty(b) then
 Info( InfoPcNormalizer, 4, "coboundaries are trivial" );
 return PCGS_NORMALIZER( home, pcgs, u1, u2 );
 fi;
 Info( InfoPcNormalizer, 4, "|coboundaries| = ",
 RelativeOrderOfPcElement(home,ns[1]), "^", Length(b) );

 # compute the stabilizer
 c := List( TriangulizedNullspaceMat(l), x -> PcElementByExponentsNC(ns,x) );

 # compute the heads of the coboundaries
 heads := [];
 k := 1;
 i := 1;
 while i <= Length(b) and k <= Length(b[1]) do
 if IntFFE(b[i][k]) <> 0 then
 heads[i] := k;
 i := i+1;
 fi;
 k := k+1;
 od;

 # now the function which acts on the coboundaries
 ln1 := Length(ns);
 ln2 := Length(u);

 op := function( v, x )
 local w, i;

 # add the coboundary <v> to 
 w := ShallowCopy(u);
 for i in [ 1 .. ln2 ] do
 w[i] := w[i] * PcElementByExponentsNC(ns, v{[(i-1)*ln1+1..i*ln1]});
 od;

 # operate with <x> on <w> and normalize modulo <u2>
 w := PCGS_NORMALIZER_OPE( data, w, x );

 # convert back into a vector
 v := [];
 for i in [ 1 .. ln2 ] do
 Append( v, ExponentsOfPcElement( ns, ui[i]*w[i] ) );
 od;
 v := v * One(gf);
 v := ImmutableVector(gf, v);
 for i in [ 1 .. Length(heads) ] do
 v := v - v[heads[i]] * b[i];
 od;
 return Immutable(v);
 end;

 # compute the blockstabilizer
 Info( InfoPcNormalizer, 4, "computing blockstabilizer" );
 stab := PCGS_STABILIZER( NumeratorOfModuloPcgs(pcgs) mod us,
 b[1] * Zero(gf),
 op );

 # compute and correct the blockstabilizer
 Info( InfoPcNormalizer, 4, "correcting blockstabilizer" );
 nb := List( nb, x -> x ^ -1 );
 for i in [ 1 .. Length(stab) ] do
 s := PCGS_NORMALIZER_OPE( data, u, stab[i] );
 v := [];
 for j in [ 1 .. ln2 ] do
 Append( v, ExponentsOfPcElement( ns, ui[j]*s[j] ) );
 od;
 for j in [ 1 .. Length(heads) ] do
 if v[heads[j] ] <> 0 then
 stab[i] := stab[i] * ( nb[j]^v[heads[j]] );
 fi;
 od;
 od;

 # return sum of <L>, <C> and <U1>
 return InducedPcgsByGeneratorsNC( home, Concatenation( stab, c, u1 ) )
 mod DenominatorOfModuloPcgs(pcgs);

end );

#############################################################################
##
#F PcGroup_NormalizerWrtHomePcgs( , <f1>, <f2>, <f3>, <f4> )
##
## compute the normalizer of in its home pcgs, the flags <f1> to <f4>
## can be used to fine tune the normalizer computation:
##
## <f1> if 'true', intersections with the same prime than the module are
## computed using one cobounds. Otherwise an ordinary orbit
## stabilizer algorithm is used.
##
## <f2> if 'true', intersections with different prime than the module are
## computed using one cobounds. Otherwise the method of computation
## depends on the flag <f3>.
##
## <f3> if 'true' and <f2> is 'false', then intersections with different
## prime than the module are computed using Glasby's algorithm.
## Otherwise a ordinary orbit stabilizer algorithm is used.
##
## <f4> if 'true', the first intersection is computed using linear
## operations. Otherwise a ordinary orbit stabilizer algorithm is
## used.
##
DeclareGlobalName("PcGroup_NormalizerWrtHomePcgs");
BindGlobal( "PcGroup_NormalizerWrtHomePcgs", function( u, f1, f2, f3, f4 )

 local g, # home pcgs of <pcgs>
 e, r, # elementary abelian series of <G> and its length
 ue, # factor pcgs <pcgs><e>[i] mod <e>[i]
 uk, uj, ui_1, # intersections of <pcgs> with <e>[x]
 s, si_1, # stabilizer and its intersection with <e>[i-1]
 ei_1, # <e>[i-1] mod <e>[i]
 pj, pi_1, # primes of <e>[j] and <e>[i-1]
 st, # used for checking the algorithm
 i, j, k, # loops
 pcgs, # pcgs of 
 id, # identity element
 tmp; # temporary

 # get the parent pcgs and the elementary abelian series
 g := HomePcgs(u);
 id := OneOfPcgs(g);
 e := ElementaryAbelianSubseries(g);
 if e = fail then
 Info( InfoPcNormalizer, 1, "Computing el.ab. PCGS" );
 s := SpecialPcgs(g);
 k := NaturalIsomorphismByPcgs( GroupOfPcgs(g), s );
 if ElementaryAbelianSubseries(Pcgs(Image(k))) = fail then
 Error( "corrupted special pcgs" );
 fi;
 tmp := InducedPcgsByGeneratorsNC( g, List(
 PcGroup_NormalizerWrtHomePcgs( Image(k,u), f1, f2, f3, f4 ),
 x -> PreImage( k, x ) ) );
 SetHomePcgs( tmp, g );
 return tmp;
 fi;
 r := Length(e);

 # get a canonical pcgs for 
 pcgs := CanonicalPcgsWrtHomePcgs(u);

 # If <r> = 2, <g> is abelian, so we can return <g>
 if r = 2 then
 return g;
 fi;

 # compute the closure of <pcgs> and <e>[i]
 ue := [];
 for i in [ 1 .. r ] do
 ue[i] := SumPcgs( g, e[i], pcgs );
 od;

 # begin with <g>/<e>[2], in this factorgroup nothing is to be done
 s := e[1] mod e[2];
 Info( InfoPcNormalizer, 1, "skipping level 1 of ", r );
 Info( InfoPcNormalizer, 1, "skipping level 2 of ", r );

 # start with <g>/<e>[3] because <g>/<e>[2] is abelian
 for i in [ 3 .. r ] do

 # <s> = Normalizer( <G>/<E>[i-1], <pcgs> )
 #
 # The first step looks like ( U = <pcgs> )
 #
 # S
 # \
 # \
 # U Ei-1
 # \ /
 # \ /
 # Ui-1
 # \
 # \
 # Ei
 #
 # Now get the complete preimage of <s> in <g>/<e>[i] and start the
 # whole computation for that factorgroup.

 s := NumeratorOfModuloPcgs(s) mod e[i];
 Info( InfoPcNormalizer, 1, "reached level ", i, " of ", r );
 Info( InfoPcNormalizer, 4, "normalizer: ", AsList(s) );
 Info( InfoPcNormalizer, 4, "subgroup: ", AsList(ue[i]) );
 Info( InfoPcNormalizer, 5, "modulo: ", AsList(e[i]) );

 # keep the old stabilizer for an assert later
 st := s;

 # if <ue>[i] is trivial we can skip this step
 ei_1 := e[i-1] mod e[i];
 if Length(ue[i]) = Length(e[i]) then
 Info( InfoPcNormalizer, 2, "<ue>[", i, "] is trivial" );
 Assert( 1, IsNormal(GroupOfPcgs(st),GroupOfPcgs(ue[i])) );

 # if <e>[i-1] is a subgroup of <ue>[i] we can skip this step
 elif ForAll( ei_1, x -> SiftedPcElement(ue[i],x) = id ) then
 Info( InfoPcNormalizer, 2, "<e>[",i,"] > <ue>[",i-1,"]" );
 Assert( 1, IsNormal(GroupOfPcgs(st),GroupOfPcgs(ue[i])) );

 # now do some real work
 else

 # remember the prime of the current section for later
 pi_1 := RelativeOrderOfPcElement( g, ei_1[1] );

 # get the first section
 ui_1 := NormalIntersectionPcgs( g, e[i-1], ue[i] );

 # if the factor is trivial do nothing
 if Length(ui_1) = Length(e[i]) then
 Info( InfoPcNormalizer, 2,
 "<ue>[",i,"] /\\ <e>[",i-1,"] is trivial" );

 # if <f4> is true, use linear operations
 elif f4 then
 Info( InfoPcNormalizer, 2, "<ue>[", i, "] /\\ <e>[", i-1,
 "] using linear operation" );

 s := PCGS_NORMALIZER_LINEAR( g, s, ui_1, ei_1 );

 # otherwise use a normal stabilizer
 else
 Info( InfoPcNormalizer, 2, "<ue>[", i, "] /\\ <e>[", i-1,
 "] using orbit" );
 s := PCGS_NORMALIZER( g, s, ui_1, e[i] );
 fi;

 # check the stabilizer
 Assert( 3, Stabilizer( GroupOfPcgs(st), GroupOfPcgs(ui_1),
 function(U,g) return U^g;end)
 = GroupOfPcgs(s) );

 # now <ui_1> must be stabilized by <s>
 st := s;
 Assert( 1, IsNormal(GroupOfPcgs(st),GroupOfPcgs(ui_1)) );

 # find <ue>[i]/\<E>[j] which is larger then <ue>[i]/\<E>[i-1]
 j := i-2;
 uj := NormalIntersectionPcgs( g, e[j], ue[i] );
 k := i-1;
 uk := ui_1;
 while 0 < j and Length(uj) = Length(ui_1) do
 Info( InfoPcNormalizer, 2, "<ue>[",i,"] /\\ <e>[", j,
 "] = <ue>[", i, "] /\\ e[", k, "]" );
 k := j;
 uk := uj;
 j := j - 1;
 if 0 < j then
 uj := NormalIntersectionPcgs( g, e[j], ue[i] );
 fi;
 od;

 # The next step for <s> = Normalizer( <uk> ) is
 #
 # S
 # \ Ej
 # \ / \
 # U ** \
 # \ / \ Ek
 # \ / \ / \
 # Uj ** \
 # \ / \ Ei-1
 # \ / \ /
 # Uk Si-1
 # \ /
 # \ /
 # Ui-1
 # \
 # \
 # Ei
 #
 # If <j> = 0 or <s> and have the same <E>[i-1] intersection
 # we are finished with this step.

 si_1 := NormalIntersectionPcgs(
 g,
 e[i-1],
 NumeratorOfModuloPcgs(s) )
 mod e[i];

 while 0<j and not ForAll(si_1,x ->SiftedPcElement(ui_1,x)=id) do

 # this only works for subseries <e>
 tmp := First( e[j], x -> not x in e[j+1] );
 pj := RelativeOrderOfPcElement( g, tmp );

 # cobounds
 if ( pj = pi_1 and f1 ) or ( pj <> pi_1 and f2 ) then
 Info( InfoPcNormalizer, 2, "<ue>[", i, "] /\\ <e>[", j,
 "] using cobounds" );
 s := PCGS_NORMALIZER_COBOUNDS( g, s, si_1, uj, uk );

 # glasby
 elif pj <> pi_1 and f3 then
 Info( InfoPcNormalizer, 2, "<ue>[", i, "] /\\ <e>[", j,
 "] using Glasby" );
 s := PCGS_NORMALIZER_GLASBY( g, s, si_1, uj, uk );

 # orbit
 else
 Info( InfoPcNormalizer, 2, "<ue>[", i, "] /\\ <e>[", j,
 "] using orbit" );
 s := PCGS_NORMALIZER( g, s, uj, uk );
 fi;

 # check the stabilizer
 Assert( 3, Stabilizer( GroupOfPcgs(st), GroupOfPcgs(uj),
 function(U,g) return U^g;end)
 = GroupOfPcgs(s) );

 # now <uj> must be stabilized by <s>
 st := s;
 Assert( 1, IsNormal(GroupOfPcgs(st),GroupOfPcgs(uj)) );

 # find the next non-trivial intersection
 k := j;
 uk := uj;
 while 0 < j and Length(uj) = Length(uk) do
 if k <> j then
 Info( InfoPcNormalizer, 2, "<ue>[", i, "] /\\ <e>[",
 j, "] = <ue>[", i, "] /\\ e[", k, "]" );
 fi;

 k := j;
 uk := uj;
 j := j - 1;
 if 0 < j then
 uj := NormalIntersectionPcgs( g, e[j], ue[i] );
 fi;
 od;

 # Now we know our new <S>, if <j>-1 is still nonzero, compute
 # the intersection in order to see, if we are finished.

 if 0 < j then
 si_1 := NormalIntersectionPcgs(
 g,
 e[i-1],
 NumeratorOfModuloPcgs(s) )
 mod e[i];
 fi;

 od;
 fi;
 od;
 Assert( 1, IsNormal( GroupOfPcgs(s), u ) );

 if Length(s) = Length(pcgs) then
 return pcgs;
 else
 tmp := InducedPcgsByPcSequence( g, List( s, x -> x ) );
 SetHomePcgs( tmp, g );
 return tmp;
 fi;

end );

#############################################################################
##
#M NormalizerInHomePcgs( <pc-group> )
##
InstallMethod( NormalizerInHomePcgs,
 "for group with home pcgs",
 true,
 [ IsGroup and HasHomePcgs ],
 0,

function( u )
 if not IsPrimeOrdersPcgs(HomePcgs(u)) then
 TryNextMethod();
 fi;
 return PcGroup_NormalizerWrtHomePcgs( u, true, false, true, true );
end );

#############################################################################
##
#M Normalizer( <pc-group>, <pc-group> )
##
InstallMethod( NormalizerOp, "for groups with home pcgs", IsIdenticalObj,
 [ IsGroup and HasHomePcgs and CanComputeFittingFree, IsGroup and HasHomePcgs ],
 1, #better than the next method
function( g, u )
 local home, norm, pcgs;

 # for small groups use direct calculation
 if Size(g) < 1000 or (Size(g)<100000 and Size(g)/Size(u)<500) then
 TryNextMethod();
 fi;
 home := HomePcgs(g);
 if home <> HomePcgs(u) then
 TryNextMethod();
 fi;

 # first compute the normalizer with respect to the home
 pcgs := NormalizerInHomePcgs(u);
 norm := SubgroupByPcgs( g, pcgs );

 # then the intersection
 norm := Intersection( g, norm );

 # and return
 return norm;

end );

InstallMethod( NormalizerOp, "slightly better orbit algorithm for pc groups",
 IsIdenticalObj, [ IsGroup and HasHomePcgs, IsGroup and HasHomePcgs ], 0,
function( G, U )
local N,h,opfun;
 h:=HomePcgs(G);
 opfun:=function(p,g)
 return CanonicalPcgs(InducedPcgsByGeneratorsNC(h,List(p,i->i^g)));
 end;

 N:=Stabilizer(G,CanonicalPcgs(InducedPcgs(h,U)),opfun);
 return N;
end);

Quelle grppcnrm.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.43 Sekunden (vorverarbeitet) ]