SSL grppcint.gi Sprache: unbekannt

#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Frank Celler, Bettina Eick.
##
## 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 the intersection of polycyclic groups.
##

#############################################################################
##
#V GS_SIZE . . . . . . . . . . . . . . . . size from which on we use glasby
##
GS_SIZE := 20;

#############################################################################
##
#F GlasbyCover( <S>, <A>, , <pcgsK> )
##
## Glasby's generalized covering algorithmus. <S> := <H>/\<N> * <K>/\<N>
## and <A> < <H>, < <K>. <A> ( and also ) generate the intersection
## modulo <S>.
##
BindGlobal( "GlasbyCover", function( S, A, B, pcgsK )
 local Am, Bm, z, i;

 # Decompose the intersection <H> /\ <K> /\ <N>.
 Am := AsList( S.intersection );
 Bm := List( Am, x -> x / SiftedPcElement( pcgsK, x ) );

 # Now cover the other generators.
 for i in [ 1 .. Length( A ) ] do
 z := S.factorization(LeftQuotient( A[i], B[i]) );
 A[ i ] := A[ i ] * z.u;

 # what is the aim of this arithmetic? We can save one inversion
 #B[ i ] := B[ i ] * ( z.n / SiftedPcElement( pcgsK, z.n ) ) ^ -1;
 B[ i ] := B[ i ] * (SiftedPcElement( pcgsK, z.n )/z.n);
 od;

 # Concatenate them and return. The are not normalized.
 Append( A, Am );
 Append( B, Bm );
end );

#############################################################################
##
#F GlasbyShift( <C>, )
##
BindGlobal( "GlasbyShift", function( C, B )
 return List( C, x -> x / SiftedPcElement( B, x ) );
end );

#############################################################################
##
#F GlasbyStabilizer( <pcgs>, <A>, , <pcgsL>)
##
BindGlobal( "GlasbyStabilizer", function( pcgs, A, B, pcgsL )
 local f, transl, matA, pt;

 f := GF( Order( pcgsL[1] ) );

 transl := function( a )
 return ExponentsOfPcElement(pcgsL,SiftedPcElement(B,a)) * One(f);
 end;

 A := InducedPcgsByPcSequenceNC( pcgs, A );
 #U := SubgroupByPcgs( GroupOfPcgs(pcgs), A );
 matA := AffineActionLayer( A, pcgsL, transl );

 pt := List( pcgsL, x -> Zero( f ) );
 Add( pt, One( f ) );
 pt := ImmutableVector(f, pt);

 # was: return Pcgs( Stabilizer( U, pt, A, matA, OnRight ) );
 # we cannot simply return this pcgs here, as we cannot guarantee that
 # the pcgs of this group will be compatible with the pcgs wrt. which we
 # are computing.
 #return InducedPcgs(pcgs, Stabilizer( U, pt, A, matA, OnRight ) );
 return StabilizerPcgs(A, pt, matA, OnRight );
end );

#############################################################################
##
#F AvoidedLayers
##
BindGlobal( "AvoidedLayers", function( pcgs, pcgsH, pcgsK )

 local occur, h, k, first, next, avoided, primes, p, sylow, res, i,
 firsts, weights;

 # get the gens, which do not occur in H or K
 occur := List( [ 1..Length( pcgs ) ], x -> 0 );
 for h in pcgsH do
 occur := occur + ExponentsOfPcElement( pcgs, h );
 od;
 for k in pcgsK do
 occur := occur + ExponentsOfPcElement( pcgs, k );
 od;

 # make a list of the avoided layers
 avoided := [ ];
 firsts := LGFirst( pcgs );
 weights := LGWeights( pcgs );
 for i in [ 1..Length( firsts )-1 ] do
 first := firsts[i];
 next := firsts[i+1];
 if Maximum( occur{[first..next-1]} ) = 0 then
 Add( avoided, first );
 fi;
 od;

 # get the avoided heads
 res := [ ];
 for i in avoided do
 if weights[i][2] = 1 then
 Add( res, i );
 fi;
 od;

 # get the avoided Sylow subgroups
 primes := Set( avoided, x -> weights[x][3] );
 for p in primes do
 sylow := Filtered( firsts{[1..Length(firsts)-1]},
 x -> weights[x][3] = p );
 if IsSubset( avoided, sylow ) then
 Append( res, sylow );
 fi;
 od;

 return Set(res);
end );

#############################################################################
##
#F GlasbyIntersection
##
BindGlobal( "GlasbyIntersection", function( pcgs, pcgsH, pcgsK )
 local m, G, first, avoid, A, B, i, start, next, HmN, KmN,
 sum, pcgsS, pcgsR, C, D,
 new, U, deptH, deptK,pcgsL,depthS,depthN;

 # compute a cgs for <H> and <K>
 G := GroupOfPcgs( pcgs );
 m := Length( pcgs );

 # use the special pcgs
 first := LGFirst( pcgs );
 avoid := AvoidedLayers( pcgs, pcgsH, pcgsK );

 deptH := List( pcgsH, x -> DepthOfPcElement( pcgs, x ) );
 deptK := List( pcgsK, x -> DepthOfPcElement( pcgs, x ) );

 # go down the elementary abelian series. <A> < <H>, < <K>.
 A := [ ];
 B := [ ];
 depthN:=[1..m];
 for i in [ 1..Length(first)-1 ] do
 start := first[i];
 next := first[i+1];
 depthS := depthN;
 depthN := [next..m];
 if not start in avoid then
 #pcgsN := InducedPcgsByPcSequenceNC( pcgs, pcgs{depthN} );
 HmN := pcgsH{Filtered( [1..Length(deptH)],
 x -> start <= deptH[x] and next > deptH[x] )};
 KmN := pcgsK{Filtered( [1..Length(deptK)],
 x -> start <= deptK[x] and next > deptK[x] )};

 #pcgsHmN := Concatenation( HmN, pcgsN );
 #pcgsHmN := InducedPcgsByPcSequenceNC( pcgs, pcgsHmN );
 #pcgsHF := pcgsHmN mod pcgsN;
 #pcgsKmN := Concatenation( KmN, pcgsN );
 #pcgsKmN := InducedPcgsByPcSequenceNC( pcgs, pcgsKmN );
 #pcgsKF := pcgsKmN mod pcgsN;

 # SumFactorizationFunction takes *LISTS* as arguments 2,3, so we
 # don't need to make pcgs at all.
 #pcgsHF := ModuloTailPcgsByList(pcgs,HmN,[next..m]);
 #pcgsKF := ModuloTailPcgsByList(pcgs,KmN,[next..m]);
 #sum := SumFactorizationFunctionPcgs( pcgs, pcgsHF, pcgsKF, pcgsN );

 # and `SFF' now takes a tail depth, so the expensive sifting to
 # find the identity can be ignored.
 sum := SumFactorizationFunctionPcgs( pcgs, HmN, KmN, next );

 # Maybe there is nothing left to stabilize.
 if Length( sum.sum ) = next - start then
 C := ShallowCopy( AsList( A ) );
 D := ShallowCopy( AsList( B ) );
 else
 # GlasbyStabilizer would make a pcgs out of it first anyhow
 B := InducedPcgsByPcSequenceNC( pcgs, B );
 if Length(sum.sum)>0 then
 pcgsS := InducedPcgsByPcSequenceNC( pcgs, pcgs{depthS} );
 pcgsR := Concatenation( sum.sum, pcgs{depthN} );
 pcgsR := InducedPcgsByPcSequenceNC( pcgs, pcgsR );
 pcgsL:=pcgsS mod pcgsR;
 else
 pcgsL:=ModuloTailPcgsByList(pcgs,
 pcgs{Difference(depthS,depthN)},
 depthN);

 fi;

 C := GlasbyStabilizer( pcgs, A, B, pcgsL );
 C := ShallowCopy( AsList( C ) );
 #D := GlasbyShift( C, InducedPcgsByPcSequenceNC(pcgs, B) );
 D := GlasbyShift( C, B );
 D := ShallowCopy( AsList( D ) );
 fi;

 # Now we can cover <C> and <D>.
 GlasbyCover( sum, C, D, pcgsK );
 A := ShallowCopy( C );
 B := ShallowCopy( D ) ;
 fi;
 od;

 # <A> is the unnormalized intersection.
 new := InducedPcgsByPcSequenceNC( pcgs, A );
 U := SubgroupByPcgs( G, new );
 return U;
end );

#############################################################################
##
#F ZassenhausIntersection( pcgs, pcgsN, pcgsU )
##
BindGlobal( "ZassenhausIntersection", function( pcgs, pcgsN, pcgsU )
 local sw, m, ins, g, new;

 if Length(pcgsN)=0 then
 return SubgroupByPcgs( GroupOfPcgs( pcgs ), pcgsN );
 fi;
 # If <N> is composition subgroup, no calculation is needed. We can use
 # weights instead. Otherwise 'IntersectionSumAgGroup' will do the work.
 sw := DepthOfPcElement( pcgs, pcgsN[1] );
 m := Length( pcgs );
 if pcgs{[sw..m]} = pcgsN then
 ins := [];
 for g in pcgsU do
 if DepthOfPcElement( pcgs, g ) >= sw then
 Add( ins, g );
 fi;
 od;
 new := InducedPcgsByPcSequenceNC( pcgs, ins );
 ins := SubgroupByPcgs( GroupOfPcgs( pcgs ), new );
 return ins;
 else
 new := ExtendedIntersectionSumPcgs( pcgs, pcgsN, pcgsU, true );
 new := InducedPcgsByPcSequenceNC( pcgs, new.intersection );
 ins := SubgroupByPcgs( GroupOfPcgs( pcgs ), new );
 return ins;
 fi;
end );

#############################################################################
##
#M Intersection2( , <V> )
##
InstallMethod( Intersection2,
 "groups with pcgs",
 true,
 [ IsGroup and HasHomePcgs,
 IsGroup and HasHomePcgs ],
 0,

function( U, V )
 local G, home, pcgs, pcgsU, pcgsV;

 # Check the parent and catch a trivial case
 home := HomePcgs(U);
 if home <> HomePcgs(V) then
 TryNextMethod();
 fi;

 # check for trivial cases
 if IsInt(Size(V)/Size(U))
 and ForAll( GeneratorsOfGroup(U), x -> x in V ) then
 return U;
 # here we can test Size(V)<Size(U): if they are the same the test before
 # would have found out.
 elif Size(V)<Size(U) and IsInt(Size(U)/Size(V))
 and ForAll( GeneratorsOfGroup(V), x -> x in U ) then
 return V;
 fi;

 G := GroupOfPcgs(home);
 if Size(U) < GS_SIZE then
 return SubgroupNC( G, Filtered( AsList(U), x -> x in V and
 x <> Identity(V) ) );
 elif Size(V) < GS_SIZE then
 return SubgroupNC( G, Filtered( AsList(V), x -> x in U and
 x <> Identity(U) ) );
 fi;

 # compute nice pcgs's
 pcgs := SpecialPcgs(home);
 pcgsU := InducedPcgs(pcgs, U );
 pcgsV := InducedPcgs(pcgs, V );

 # disabled calls to `ZassenhausIntersection' that seems to be not
 # applicable. AH, 4/12/05
 # # test if one the groups is known to be normal
 # if IsNormal( G, U ) then
 # return ZassenhausIntersection( pcgs, pcgsU, pcgsV );
 # elif IsNormal( G, V ) then
 # return ZassenhausIntersection( pcgs, pcgsV, pcgsU );
 # fi;

 return GlasbyIntersection( pcgs, pcgsU, pcgsV );

end );

#############################################################################
##
#M NormalIntersection( <G>, ) . . . . . intersection with normal subgrp
##
InstallMethod( NormalIntersection,
 "method for two groups with home pcgs",
 IsIdenticalObj, [ IsGroup and HasHomePcgs, IsGroup and HasHomePcgs],
function( G, H )
local home;
 home:=HomePcgs(G);
 if home<>HomePcgs(H) then
 TryNextMethod();
 fi;
 return ZassenhausIntersection(home,InducedPcgs(home,G),InducedPcgs(home,H));
end );

SSL grppcint.gi Sprache: unbekannt

[ Verzeichnis aufwärts0.63unsichere Verbindung Übersetzung europäischer Sprachen durch Browser ]