Quelle grppcnrm.gi Sprache: Shell

#############################################################################
##
## 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);

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.34 Sekunden (vorverarbeitet am 2026-10-13) ¤

Wurzel

Suchen

PVS Prover

Isabelle Prover

NIST Cobol Testsuite

Cephes Mathematical Library

Vienna Development Method

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.