Quelle gprdperm.gi Sprache: unbekannt

#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Heiko Theißen.
##
## 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
##

#############################################################################
##
#F DirectProductOfPermGroupsWithMovedPoints( <grps>, <pnts> )
##
BindGlobal("DirectProductOfPermGroupsWithMovedPoints",
 function( grps, pnts )
 local i, oldgrps, olds, news, perms, gens,
 deg, grp, old, new, perm, gen, D, info;

 oldgrps := [ ];
 olds := [ ];
 news := [ ];
 perms := [ ];
 gens := [ ];
 deg := 0;

 # loop over the groups
 for i in [1..Length(grps)] do

 # find old domain, new domain, and conjugating permutation
 grp := grps[i];
 old := Immutable(pnts[i]);
 new := MakeImmutable([deg+1..deg+Length(old)]);
 perm := MappingPermListList( old, new );
 deg := deg + Length(old);
 Add( oldgrps, grp );
 Add( olds, old );
 Add( news, new );
 Add( perms, perm );

 # map all the generators of <grp>
 for gen in GeneratorsOfGroup( grp ) do
 Add( gens, gen ^ perm );
 od;

 od;
 D:= GroupWithGenerators( gens, One( grps[1] ) );
 info := rec( groups := oldgrps,
 olds := olds,
 news := news,
 perms := perms,
 embeddings := [],
 projections := [] );

 SetDirectProductInfo( D, info );
 return D;
 end );

#############################################################################
##
#M DirectProductOp( <grps>, <G> ) . . . . . . direct product of perm groups
##
InstallMethod( DirectProductOp,
 "for a list of permutation groups, and a permutation group",
 IsCollsElms,
 [ IsList and IsPermCollColl, IsPermGroup ], 0,
 function( grps, G )

 # Check the arguments.
 if not ForAll( grps, IsGroup ) then
 TryNextMethod();
 fi;

 return DirectProductOfPermGroupsWithMovedPoints(grps, List(grps, MovedPoints));
 end );

#############################################################################
##
#M Size( <D> ) . . . . . . . . . . . . . . . . . . . . . . of direct product
##
InstallMethod( Size,
 "for a permutation group that knows to be a direct product",
 true,
 [ IsPermGroup and HasDirectProductInfo ], 0,
 D -> Product( List( DirectProductInfo( D ).groups, Size ) ) );

#############################################################################
##
#R IsEmbeddingDirectProductPermGroup( <hom> ) . embedding of direct factor
##
DeclareRepresentation( "IsEmbeddingDirectProductPermGroup",
 IsAttributeStoringRep and
 IsGroupHomomorphism and IsInjective and
 IsSPGeneralMapping, [ "component" ] );

#############################################################################
##
#R IsEmbeddingWreathProductPermGroup( <hom> ) . embedding of wreath factor
##
DeclareRepresentation( "IsEmbeddingWreathProductPermGroup",
 IsAttributeStoringRep and
 IsGroupHomomorphism and IsInjective and
 IsSPGeneralMapping, [ "component" ] );

#############################################################################
##
#R IsEmbeddingImprimitiveWreathProductPermGroup( <hom> )
##
## special for case of imprimitive wreath product
DeclareRepresentation( "IsEmbeddingImprimitiveWreathProductPermGroup",
 IsEmbeddingWreathProductPermGroup, [ "component" ] );

#############################################################################
##
#R IsEmbeddingProductActionWreathProductPermGroup( <hom> )
##
## special for case of product action wreath product
DeclareRepresentation(
 "IsEmbeddingProductActionWreathProductPermGroup",
 IsEmbeddingWreathProductPermGroup
 and IsGroupGeneralMappingByAsGroupGeneralMappingByImages,["component"]);

#############################################################################
##
#M Embedding( <D>, ) . . . . . . . . . . . . . . . . . . make embedding
##
InstallMethod( Embedding,"perm direct product", true,
 [ IsPermGroup and HasDirectProductInfo,
 IsPosInt ], 0,
 function( D, i )
 local emb, info;
 info := DirectProductInfo( D );
 if IsBound( info.embeddings[i] ) then return info.embeddings[i]; fi;

 emb := Objectify( NewType( GeneralMappingsFamily( PermutationsFamily,
 PermutationsFamily ),
 IsEmbeddingDirectProductPermGroup ),
 rec( component := i ) );
 SetRange( emb, D );

 info.embeddings[i] := emb;

 return emb;
end );

#############################################################################
##
#M Source( <emb> ) . . . . . . . . . . . . . . . . . . . . . . of embedding
##
InstallMethod( Source,"perm direct product embedding", true,
 [ IsEmbeddingDirectProductPermGroup ], 0,
 emb -> DirectProductInfo( Range( emb ) ).groups[ emb!.component ] );

#############################################################################
##
#M ImagesRepresentative( <emb>, <g> ) . . . . . . . . . . . . of embedding
##
InstallMethod( ImagesRepresentative,"perm direct product embedding",
 FamSourceEqFamElm, [ IsEmbeddingDirectProductPermGroup,
 IsMultiplicativeElementWithInverse ], 0,
 function( emb, g )
 return g ^ DirectProductInfo( Range( emb ) ).perms[ emb!.component ];
end );

#############################################################################
##
#M PreImagesRepresentative( <emb>, <g> ) . . . . . . . . . . . of embedding
##
InstallMethod( PreImagesRepresentative, "perm direct product embedding",
 FamRangeEqFamElm,
 [ IsEmbeddingDirectProductPermGroup,
 IsMultiplicativeElementWithInverse ],
 function( emb, g )
 local info;
 info := DirectProductInfo( Range( emb ) );
#T Make this more efficient:
#T Creating the restricted permutation could be avoided
#T if there would be an efficient (kernel) function that tests whether
#T a permutation moves points outside a given set.
#T Inverting the mapping permutation in each call could be avoided
#T by storing also the inverse, and the conjugation could be improved.
 if g = RestrictedPermNC( g, info.news[ emb!.component ] ) then
 return g ^ (info.perms[ emb!.component ] ^ -1);
 else
 return fail;
 fi;
end );

#############################################################################
##
#M ImagesSource( <emb> ) . . . . . . . . . . . . . . . . . . . of embedding
##
InstallMethod( ImagesSource,"perm direct product embedding", true,
[ IsEmbeddingDirectProductPermGroup ], 0,
 function( emb )
 local D, I, info;

 D := Range( emb );
 info := DirectProductInfo( D );
 I := SubgroupNC( D, OnTuples
 ( GeneratorsOfGroup( info.groups[ emb!.component ] ),
 info.perms[ emb!.component ] ) );
 SetIsNormalInParent( I, true );
 return I;
end );

#############################################################################
##
#M ViewObj( <emb> ) . . . . . . . . . . . . . . . . . . . . view embedding
##
InstallMethod( ViewObj,
 "for embedding into direct product",
 true,
 [ IsEmbeddingDirectProductPermGroup ], 0,
 function( emb )
 Print( Ordinal( emb!.component ), " embedding into " );
 View( Range( emb ) );
end );

#############################################################################
##
#M PrintObj( <emb> ) . . . . . . . . . . . . . . . . . . . . print embedding
##
InstallMethod( PrintObj,
 "for embedding into direct product",
 true,
 [ IsEmbeddingDirectProductPermGroup ], 0,
 function( emb )
 Print( "Embedding( ", Range( emb ), ", ", emb!.component, " )" );
end );

#############################################################################
##
#R IsProjectionDirectProductPermGroup( <hom> ) projection onto direct factor
##
DeclareRepresentation( "IsProjectionDirectProductPermGroup",
 IsAttributeStoringRep and
 IsGroupHomomorphism and IsSurjective and
 IsSPGeneralMapping, [ "component" ] );

#############################################################################
##
#M Projection( <D>, ) . . . . . . . . . . . . . . . . . make projection
##
InstallMethod( Projection,"perm direct product", true,
 [ IsPermGroup and HasDirectProductInfo,
 IsPosInt ], 0,
 function( D, i )
 local prj, info;
 info := DirectProductInfo( D );
 if IsBound( info.projections[i] ) then return info.projections[i]; fi;

 prj := Objectify( NewType( GeneralMappingsFamily( PermutationsFamily,
 PermutationsFamily ),
 IsProjectionDirectProductPermGroup ),
 rec( component := i ) );
 SetSource( prj, D );
 info.projections[i] := prj;
 return prj;
end );

#############################################################################
##
#M Range( <prj> ) . . . . . . . . . . . . . . . . . . . . . . of projection
##
InstallMethod( Range, "perm direct product projection",true,
 [ IsProjectionDirectProductPermGroup ], 0,
 prj -> DirectProductInfo( Source( prj ) ).groups[ prj!.component ] );

#############################################################################
##
#M ImagesRepresentative( <prj>, <g> ) . . . . . . . . . . . . of projection
##
InstallMethod( ImagesRepresentative,"perm direct product projection",
 FamSourceEqFamElm,
 [ IsProjectionDirectProductPermGroup,
 IsMultiplicativeElementWithInverse ], 0,
 function( prj, g )
 local info;
 info := DirectProductInfo( Source( prj ) );
 return RestrictedPermNC( g, info.news[ prj!.component ] )
 ^ ( info.perms[ prj!.component ] ^ -1 );
end );

#############################################################################
##
#M PreImagesRepresentative( <prj>, <g> ) . . . . . . . . . . . of projection
##
InstallMethod( PreImagesRepresentative,"perm direct product projection",
 FamRangeEqFamElm,
 [ IsProjectionDirectProductPermGroup,
 IsMultiplicativeElementWithInverse ], 0,
 function( prj, g )
 return g ^ DirectProductInfo( Source( prj ) ).perms[ prj!.component ];
end );

#############################################################################
##
#M KernelOfMultiplicativeGeneralMapping( <prj> ) . . . . . . . of projection
##
InstallMethod( KernelOfMultiplicativeGeneralMapping,
 "perm direct product projection",
 true, [ IsProjectionDirectProductPermGroup ], 0,
 function( prj )
 local D, gens, i, K, info;

 D := Source( prj );
 info := DirectProductInfo( D );
 gens := [ ];
 for i in [ 1 .. Length( info.groups ) ] do
 if i <> prj!.component then
 Append( gens, OnTuples( GeneratorsOfGroup( info.groups[ i ] ),
 info.perms[ i ] ) );
 fi;
 od;
 K := SubgroupNC( D, gens );
 SetIsNormalInParent( K, true );
 return K;
end );

#############################################################################
##
#M ViewObj( <prj> ) . . . . . . . . . . . . . . . . . . . . view projection
##
InstallMethod( ViewObj,
 "for projection from a direct product",
 true,
 [ IsProjectionDirectProductPermGroup ], 0,
 function( prj )
 Print( Ordinal( prj!.component ), " projection of " );
 View( Source( prj ) );
end );

#############################################################################
##
#M PrintObj( <prj> ) . . . . . . . . . . . . . . . . . . . print projection
##
InstallMethod( PrintObj,
 "for projection from a direct product",
 true,
 [ IsProjectionDirectProductPermGroup ], 0,
 function( prj )
 Print( "Projection( ", Source( prj ), ", ", prj!.component, " )" );
end );

InstallGlobalFunction(SubdirectDiagonalPerms,function(l,m)
local n,o,p;
 n:=LargestMovedPoint(l);
 o:=LargestMovedPoint(m);
 p:=MappingPermListList([1..o],[n+1..n+o]);
 return List([1..Length(l)],i->l[i]*m[i]^p);
end);

#############################################################################
##
#M SubdirectProduct( <G1>, <G2>, <phi1>, <phi2> ) . . . . . . . constructor
##
InstallMethod( SubdirectProductOp,"permgroup", true,
 [ IsPermGroup, IsPermGroup, IsGroupHomomorphism, IsGroupHomomorphism ], 0,
 function( G1, G2, phi1, phi2 )
 local S, # subdirect product of <G1> and <G2>, result
 gens, # generators of <S>
 D, # direct product of <G1> and <G2>
 emb1, emb2, # embeddings of <G1> and <G2> into <D>
 info, Dinfo,# info records
 gen; # one generator of <G1> or kernel of <phi2>

 # make the direct product and the embeddings
 D := DirectProduct( G1, G2 );
 emb1 := Embedding( D, 1 );
 emb2 := Embedding( D, 2 );

 # the subdirect product is generated by $(g_1,x_{g_1})$ where $g_1$ loops
 # over the generators of $G_1$ and $x_{g_1} \in G_2$ is arbitrary such
 # that $g_1^{phi_1} = x_{g_1}^{phi_2}$ and by $(1,k_2)$ where $k_2$ loops
 # over the generators of the kernel of $phi_2$.
 gens := [];
 for gen in GeneratorsOfGroup( G1 ) do
 Add( gens, gen^emb1 * PreImagesRepresentative(phi2,gen^phi1)^emb2 );
 od;
 for gen in GeneratorsOfGroup(
 KernelOfMultiplicativeGeneralMapping( phi2 ) ) do
 Add( gens, gen ^ emb2 );
 od;

 # and make the subdirect product
 S := GroupByGenerators( gens );
 SetParent( S, D );

 Dinfo := DirectProductInfo( D );
 info := rec( groups := [G1, G2],
 homomorphisms := [phi1, phi2],
 olds := Dinfo.olds,
 news := Dinfo.news,
 perms := Dinfo.perms,
 projections := [] );
 SetSubdirectProductInfo( S, info );
 return S;
end );

#############################################################################
##
#R IsProjectionSubdirectProductPermGroup( <hom> ) . projection onto factor
##
DeclareRepresentation( "IsProjectionSubdirectProductPermGroup",
 IsAttributeStoringRep and
 IsGroupHomomorphism and IsSurjective and
 IsSPGeneralMapping, [ "component" ] );

#############################################################################
##
#M Projection( <S>, ) . . . . . . . . . . . . . . . . . make projection
##
InstallMethod( Projection,"perm subdirect product",true,
 [ IsPermGroup and HasSubdirectProductInfo,
 IsPosInt ], 0,
 function( S, i )
 local prj, info;
 info := SubdirectProductInfo( S );
 if IsBound( info.projections[i] ) then return info.projections[i]; fi;

 prj := Objectify( NewType( GeneralMappingsFamily( PermutationsFamily,
 PermutationsFamily ),
 IsProjectionSubdirectProductPermGroup ),
 rec( component := i ) );
 SetSource( prj, S );
 info.projections[i] := prj;
 SetSubdirectProductInfo( S, info );
 return prj;
end );

#############################################################################
##
#M Range( <prj> ) . . . . . . . . . . . . . . . . . . . . . . of projection
##
InstallMethod( Range,"perm subdirect product projection",
 true, [ IsProjectionSubdirectProductPermGroup ], 0,
 prj -> SubdirectProductInfo( Source( prj ) ).groups[ prj!.component ] );

#############################################################################
##
#M ImagesRepresentative( <prj>, <g> ) . . . . . . . . . . . . of projection
##
InstallMethod( ImagesRepresentative,"perm subdirect product projection",
 FamSourceEqFamElm,
 [ IsProjectionSubdirectProductPermGroup,
 IsMultiplicativeElementWithInverse ], 0,
 function( prj, g )
 local info;
 info := SubdirectProductInfo( Source( prj ) );
 return RestrictedPermNC( g, info.news[ prj!.component ] )
 ^ ( info.perms[ prj!.component ] ^ -1 );
end );

#############################################################################
##
#M PreImagesRepresentative( <prj>, <g> ) . . . . . . . . . . . of projection
##
InstallMethod( PreImagesRepresentative,"perm subdirect product projection",
 FamRangeEqFamElm,
 [ IsProjectionSubdirectProductPermGroup,
 IsMultiplicativeElementWithInverse ], 0,
 function( prj, img )
 local S,
 elm, # preimage of <img> under <prj>, result
 info, # info record
 phi1, phi2; # homomorphisms of components

 S := Source( prj );
 info := SubdirectProductInfo( S );

 # get the homomorphism
 phi1 := info.homomorphisms[1];
 phi2 := info.homomorphisms[2];

 # compute the preimage
 if 1 = prj!.component then
 elm := img ^ info.perms[1]
 * PreImagesRepresentative(phi2,img^phi1) ^ info.perms[2];
 else
 elm := img ^ info.perms[2]
 * PreImagesRepresentative(phi1,img^phi2) ^ info.perms[1];
 fi;

 # return the preimage
 return elm;
end );

#############################################################################
##
#M KernelOfMultiplicativeGeneralMapping( <prj> ) . . . . . . . of projection
##
InstallMethod( KernelOfMultiplicativeGeneralMapping,
 "perm subdirect product projection",true,
 [ IsProjectionSubdirectProductPermGroup ], 0,
 function( prj )
 local D, i, info;

 D := Source( prj );
 info := SubdirectProductInfo( D );
 i := 3 - prj!.component;
 return SubgroupNC( D, OnTuples
 ( GeneratorsOfGroup( KernelOfMultiplicativeGeneralMapping(
 info.homomorphisms[ i ] ) ),
 info.perms[ i ] ) );
end );

#############################################################################
##
#M ViewObj( <prj> ) . . . . . . . . . . . . . . . . . . . . view projection
##
InstallMethod( ViewObj,
 "for projection from subdirect product",
 true,
 [ IsProjectionSubdirectProductPermGroup ], 0,
 function( prj )
 Print( Ordinal( prj!.component ), " projection of " );
 View( Source( prj ) );
end );

#############################################################################
##
#M PrintObj( <prj> ) . . . . . . . . . . . . . . . . . . . print projection
##
InstallMethod( PrintObj,
 "for projection from subdirect product",
 true,
 [ IsProjectionSubdirectProductPermGroup ], 0,
 function( prj )
 Print( "Projection( ", Source( prj ), ", ", prj!.component, " )" );
end );

#############################################################################
##
#M WreathProductImprimitiveAction( <G>, <H> [,<hom>] )
##
InstallGlobalFunction(WreathProductImprimitiveAction,function( arg )
local G,H, # factors
 GP, # preimage of <G> (if homomorphism)
 Ggens,Igens,# permutation images of generators
 alpha, # action homomorphism for <H>
 permimpr, # product is pure permutation groups imprimitive
 I, # image of <alpha>
 grp, # wreath product of <G> and <H>, result
 gens, # generators of the wreath product
 gens1, # generators of first base part
 gen, # one generator
 domG, # domain of operation of <G>
 degG, # degree of <G>
 domI, # domain of operation of 
 degI, # degree of 
 shift, # permutation permuting the blocks
 perms, # component permutating permutations
 basegens, # generators of base subgroup
 hgens, # complement generators
 components, # components (points) of base group
 rans, # list of arguments that have '.sCO.random'
 info, # info record
 i, k, l; # loop variables

 G:=arg[1];
 H:=arg[2];
 # get the domain of operation of <G> and <H>
 if IsPermGroup( G ) then
 permimpr:=true;
 domG := MovedPoints( G );
 GP:=G;
 Ggens:=GeneratorsOfGroup(G);
 elif IsGroupHomomorphism( G ) and IsPermGroup( Range( G ) ) then
 permimpr:=false;
 GP:=Source(G);
 domG := MovedPoints( Range( G ) );
 Ggens:=List(GeneratorsOfGroup(GP),i->ImageElm(G,i));
 G := Image( G );
 else
 Error( "WreathProduct: <G> must be perm group or homomorphism" );
 fi;
 degG := Length( domG );

 if Length(arg)=2 then
 domI := MovedPoints( H );
 I := H;
 alpha := IdentityMapping( H );
 Igens:=GeneratorsOfGroup(H);
 elif IsGroupHomomorphism(arg[3]) and IsPermGroup(Range(arg[3])) then
 permimpr:=false; # also will fail the permutation imprimitive case
 alpha := arg[3];
 I := Image( alpha );
 domI := MovedPoints( Range( alpha) );
 Igens:=List(GeneratorsOfGroup(H),i->ImageElm(alpha,i));
 else
 Error( "WreathProduct: <H> must be perm group or homomorphism" );
 fi;

 if IsEmpty( domI ) then
 domI := [ 1 ];
 fi;
 domI := MakeImmutable(Set(domI));
 degI := Length( domI );

 # make the generators of the direct product of <deg> copies of <G>
 components:=[];
 gens := [];
 perms:= [];

 # force trivial group to act on 1 point
 if degG = 0 then domG := [1]; degG := 1; fi;

 for i in [1..degI] do
 components[i]:=[(i-1)*degG+1..i*degG];
 shift := MappingPermListList( domG, components[i] );
 Add(perms,shift);
 for gen in Ggens do
 Add( gens, gen ^ shift );
 od;
 if i=1 then gens1:=ShallowCopy(gens);fi;
 od;
 basegens:=gens;
 gens:=Filtered(gens, g -> not IsOne(g));

 # reduce generator number if it becomes too large -- only first base
 # part
 if Length(basegens)>10 and Length(domI)>1 and IsTransitive(I,domI) then
 gens:=gens1;
 fi;

 # add the generators of 
 hgens:=[];
 for gen in Igens do
 shift := [];
 for i in [1..degI] do
 k := Position( domI, domI[i]^gen );
 for l in [1..degG] do
 shift[(i-1)*degG+l] := (k-1)*degG+l;
 od;
 od;
 shift:=PermList(shift);
 if not IsOne(shift) then
 Add( gens, shift );
 fi;
 Add(hgens, shift );
 od;

 # make the group generated by those generators
 grp := GroupWithGenerators( gens, () ); # `gens' arose from `PermList'

 # enter the size
 SetSize( grp, Size( G ) ^ degI * Size( I ) );

 # note random method
 rans := Filtered( [ G, I ], i ->
 IsBound( StabChainOptions( i ).random ) );
 if Length( rans ) > 0 then
 SetStabChainOptions( grp, rec( random :=
 Minimum( List( rans, i -> StabChainOptions( i ).random ) ) ) );
 fi;

 info := rec(
 groups := [GP,H],
 alpha := alpha,
 perms := perms,
 base := SubgroupNC(grp,basegens),
 basegens:=basegens,
 I := I,
 degI := degI,
 domI := domI,
 hgens := hgens,
 components := components,
 embeddingType := NewType(
 GeneralMappingsFamily(PermutationsFamily,PermutationsFamily),
 IsEmbeddingImprimitiveWreathProductPermGroup),
 embeddings := [],
 permimpr:=permimpr);

 SetWreathProductInfo( grp, info );

 # return the group
 return grp;
end);

InstallMethod( WreathProduct,"permgroups: imprimitive",
 true, [ IsPermGroup, IsPermGroup ], 0,
 WreathProductImprimitiveAction);

InstallOtherMethod( WreathProduct,"permgroups and action", true,
[ IsPermGroup, IsPermGroup, IsSPGeneralMapping ], 0,
 WreathProductImprimitiveAction);

#############################################################################
##
#M Embedding( <W>, ) . . . . . . . . . . . . . . . . . . make embedding
##
InstallMethod( Embedding,"perm wreath product", true,
 [ IsPermGroup and HasWreathProductInfo,
 IsPosInt ], 0,
function( W, i )
local emb, info;
 info := WreathProductInfo( W );
 if IsBound( info.embeddings[i] ) then return info.embeddings[i]; fi;

 if i<=info.degI then
 emb := Objectify( info.embeddingType , rec( component := i ) );
 if IsBound(info.productType) and info.productType=true then
 SetAsGroupGeneralMappingByImages(emb,GroupHomomorphismByImagesNC(
 info.groups[1],W,GeneratorsOfGroup(info.groups[1]),
 info.basegens[i]));
 fi;
 elif i=info.degI+1 then
 if IsBound(info.productType) and info.productType=true then
 emb:= GroupHomomorphismByImagesNC(info.I,W,GeneratorsOfGroup(info.I),
 info.hgens);
 emb:= GroupHomomorphismByImagesNC(info.groups[2],W,
 GeneratorsOfGroup(info.groups[2]),
 List(GeneratorsOfGroup(info.groups[2]),
 i->ImageElm(emb,ImageElm(info.alpha,i))));
 SetIsInjective(emb,true);
 else
 emb := Objectify( info.embeddingType , rec( component := i ) );
 fi;
 else
 Error("no embedding defined");
 fi;
 SetRange( emb, W );

 info.embeddings[i] := emb;

 return emb;
end );

#############################################################################
##
#M Source( <emb> ) . . . . . . . . . . . . . . . . . . . . . . of embedding
##
InstallMethod( Source,"perm wreath product embedding",
 true, [ IsEmbeddingWreathProductPermGroup ], 0,
 function(emb)
 local info;
 info := WreathProductInfo( Range( emb ) );
 # Embedding into top group
 if emb!.component = info.degI + 1 then
 return info.groups[2];
 # Embedding into a component of the base group
 else
 return info.groups[1];
 fi;
 end);

#############################################################################
##
#M ImagesRepresentative( <emb>, <g> ) . . . . . . . . . . . . of embedding
##
InstallMethod( ImagesRepresentative,
 "imprim perm wreath product embedding",FamSourceEqFamElm,
 [ IsEmbeddingImprimitiveWreathProductPermGroup,
 IsMultiplicativeElementWithInverse ], 0,
 function( emb, g )
 local info, degI, x, shift, domI, degG, i, k, l;
 info := WreathProductInfo(Range(emb));
 degI := info.degI;
 # Embedding into a component of the base group
 if emb!.component <> degI + 1 then
 return g ^ info.perms[emb!.component];
 fi;
 # Embedding into top group
 x := g ^ info.alpha;
 domI := info.domI;
 degG := NrMovedPoints(info.groups[1]);
 # force trivial group to act on 1 point
 if degG = 0 then
 degG := 1;
 fi;
 shift := [];
 for i in [1 .. degI] do
 k := Position(domI, domI[i] ^ x);
 if k = fail then
 return fail;
 fi;
 for l in [1 .. degG] do
 shift[(i - 1) * degG + l] := (k - 1) * degG + l;
 od;
 od;
 return PermList(shift);
end );

#############################################################################
##
#M PreImagesRepresentative( <emb>, <g> ) . . . . . . . . . . . of embedding
##
InstallMethod( PreImagesRepresentative,
 "imprim perm wreath product embedding", FamRangeEqFamElm,
 [ IsEmbeddingImprimitiveWreathProductPermGroup,
 IsMultiplicativeElementWithInverse ], 0,
 function( emb, g )
 local info;
 info := WreathProductInfo( Range( emb ) );
 # Embedding into top group
 if emb!.component = info.degI + 1 then
 return g ^ Projection(Range(emb));
 fi;
 # Embedding into component of base group
 if not g in info.base then
 return fail;
 fi;
 return RestrictedPermNC( g, info.components[ emb!.component ] )
 ^ (info.perms[ emb!.component ] ^ -1);
end );

#############################################################################
##
#M ViewObj( <emb> ) . . . . . . . . . . . . . . . . . . . . view embedding
##
InstallMethod( ViewObj,
 "for embedding into wreath product",
 true,
 [ IsEmbeddingWreathProductPermGroup ], 0,
 function( emb )
 Print( Ordinal( emb!.component ), " embedding into ", Range( emb ) );
end );

#############################################################################
##
#M PrintObj( <emb> ) . . . . . . . . . . . . . . . . . . . . print embedding
##
InstallMethod( PrintObj,
 "for embedding into wreath product",
 true,
 [ IsEmbeddingWreathProductPermGroup ], 0,
 function( emb )
 Print( "Embedding( ", Range( emb ), ", ", emb!.component, " )" );
end );

#############################################################################
##
#M Projection( <W> ) . . . . . . . . . . . . . . projection of wreath on top
##
InstallOtherMethod( Projection,"perm wreath product", true,
 [ IsPermGroup and HasWreathProductInfo ],0,
function( W )
local info, proj, H, degI, degK, constPoints, projFunc;
 info := WreathProductInfo( W );
 if IsBound( info.projection ) then return info.projection; fi;

 # Imprimitive Action, tuple (i, j) corresponds
 # to point i + degK * (j - 1)
 if IsBound(info.permimpr) and info.permimpr=true then
 proj:=ActionHomomorphism(W,info.components,OnSets,"surjective");
 # Primitive Action, tuple (t_1, ..., t_degI) corresponds
 # to point Sum_{i=1}^degI t_i * degK ^ (i - 1)
 elif IsBound(info.productType) and info.productType=true then
 degI := info.degI;
 degK := NrMovedPoints(info.groups[1]);
 # constPoints correspond to [1, 1, ...] and the one-vectors with a 2 in each position,
 # i.e. [2, 1, 1, ...], [1, 2, 1, ...], [1, 1, 2, ...], ...
 constPoints := Concatenation([0], List([0 .. degI - 1], i -> degK ^ i)) + 1;
 projFunc := function(x)
 local imageComponents, i, comp, topImages;
 # Let x = (f_1, ..., f_m; h).
 # imageComponents = [ [1 ^ f_1, 1 ^ f_2, 1 ^ f_3, ...] ^ (1, h)
 # [2 ^ f_1, 1 ^ f_2, 1 ^ f_3, ...] ^ (1, h),
 # [1 ^ f_1, 2 ^ f_2, 1 ^ f_3, ...] ^ (1, h), ... ]
 # So we just need to check where the bit differs from the first point
 # in order to compute the action of the top element h.
 imageComponents := List(OnTuples(constPoints, x) - 1,
 p -> CoefficientsQadic(p, degK) + 1);
 # The qadic expansion has no "trailing" zeros. Thus we need to append them.
 # For example if (1, ..., 1) ^ (f_1, ..., f_m) = (1, ..., 1),
 # we have imageComponents[1] = CoefficientsQadic(0, degK) + 1 = [].
 # Note that we append 1's instead of 0's,
 # since we already transformed the result of the qadic expansion
 # from [{0, ..., degK - 1}, ...] to [{1, ..., degK}, ...].
 for i in [1 .. degI + 1] do
 comp := imageComponents[i];
 Append(comp, ListWithIdenticalEntries(degI - Length(comp), 1));
 od;
 # For some reason, the action of the top component is in reverse order,
 # i.e. [ p[m], ..., p[1] ] ^ (1, h) = [ p[m ^ (h ^ -1)], ..., p[1 ^ (h ^ -1)] ]
 topImages := List([0 .. degI - 1], i -> PositionProperty([0 .. degI - 1],
 j -> imageComponents[1, degI - j] <>
 imageComponents[degI - i + 1, degI - j]));
 return PermList(topImages);
 end;
 proj := GroupHomomorphismByFunction(W, info.groups[2], projFunc);
 else # weird cases where we use `hom` for the construction of the wreath product
 H:=info.groups[2];
 proj:=List(info.basegens,i->One(H));
 proj:=GroupHomomorphismByImagesNC(W,H,
 Concatenation(info.basegens,info.hgens),
 Concatenation(proj,GeneratorsOfGroup(H)));
 fi;
 SetKernelOfMultiplicativeGeneralMapping(proj,info.base);

 info.projection:=proj;
 return proj;
end);

#############################################################################
##
#M ListWreathProductElementNC( <G>, <x> )
##
InstallMethod( ListWreathProductElementNC, "perm wreath product", true,
[ IsPermGroup and HasWreathProductInfo, IsObject, IsBool ], 0,
function(G, x, testDecomposition)
 local info, list, h, hIm, f, degK, i, j, constPoints, imageComponents, comp, restPerm;

 info := WreathProductInfo(G);
 # The top group element
 h := x ^ Projection(G);
 if h = fail then
 return fail;
 fi;
 hIm := ImageElm(Embedding(G, info.degI + 1), h);
 if hIm = fail then
 return fail;
 fi;
 # The product of the base group elements
 f := x * hIm ^ (-1);
 list := EmptyPlist(info!.degI + 1);
 list[info.degI + 1] := h;
 # Imprimitive Action, tuple (i, j) corresponds
 # to point i + degK * (j - 1)
 if IsBound(info.permimpr) and info.permimpr then
 for i in [1 .. info.degI] do
 restPerm := RESTRICTED_PERM(f, info.components[i], testDecomposition);
 if restPerm = fail then
 return fail;
 fi;
 list[i] := restPerm ^ info.perms[i];
 od;
 # Primitive Action, tuple (t_1, ..., t_degI) corresponds
 # to point Sum_{i=1}^degI t_i * degK ^ (i - 1)
 elif IsBound(info.productType) and info.productType then
 degK := NrMovedPoints(info.groups[1]);
 # constPoints correspond to [1, 1, 1, ...], [2, 2, 2, ...], ...
 constPoints := List([0 .. degK - 1], i -> Sum([0 .. info.degI - 1],
 j -> i * degK ^ j)) + 1;
 # imageComponents = [ [1 ^ f_1, 1 ^ f_2, 1 ^ f_3, ...],
 # [2 ^ f_1, 2 ^ f_2, 2 ^ f_3, ...], ... ]
 imageComponents := List(OnTuples(constPoints, f) - 1,
 p -> CoefficientsQadic(p, degK) + 1);
 # The qadic expansion has no "trailing" zeros. Thus we need to append them.
 # For example if (1, ..., 1) ^ (f_1, ..., f_m) = (1, ..., 1),
 # we have imageComponents[1] = CoefficientsQadic(0, degK) + 1 = [].
 # Note that we append 1's instead of 0's,
 # since we already transformed the result of the qadic expansion
 # from [{0, ..., degK - 1}, ...] to [{1, ..., degK}, ...].
 for i in [1 .. degK] do
 comp := imageComponents[i];
 Append(comp, ListWithIdenticalEntries(info.degI - Length(comp), 1));
 od;
 for j in [1 .. info.degI] do
 list[j] := PermList(List([1 .. degK], i -> imageComponents[i,j]));
 if list[j] = fail then
 return fail;
 fi;
 od;
 else
 ErrorNoReturn("Error: cannot determine which action ",
 "was used for wreath product");
 fi;
 return list;
end);

#############################################################################
##
#M WreathProductElementListNC(<G>, <list>)
##
InstallMethod( WreathProductElementListNC, "perm wreath product", true,
[ IsPermGroup and HasWreathProductInfo, IsList ], 0,
function(G, list)
 local info;

 info := WreathProductInfo(G);
 return Product(List([1 .. info.degI + 1], i -> list[i] ^ Embedding(G, i)));
end);

#############################################################################
##
#F WreathProductProductAction( <G>, <H> ) wreath product in product action
##
InstallGlobalFunction( WreathProductProductAction, function( G, H )
 local W, domG, domI, map, I, deg, n, N, gens, gen, i, list,
 p, adic, q, Val, val, rans,basegens,hgens,info,degI;

 # get the domain of operation of <G> and <H>
 if IsPermGroup( G ) then
 domG := MovedPoints( G );
 elif IsGroupHomomorphism( G ) and IsPermGroup( Range( G ) ) then
 domG := MovedPoints( Range( G ) );
 G := Image( G );
 else
 Error(
 "WreathProductProductAction: <G> must be perm group or homomorphism" );
 fi;
 deg := Length( domG );
 if IsPermGroup( H ) then
 domI := MovedPoints( H );
 map := IdentityMapping( H );
 elif IsGroupHomomorphism( H ) and IsPermGroup( Range( H ) ) then
 map := H;
 domI := MovedPoints( Range( H ) );
 H := Source( H );
 else
 Error(
 "WreathProductProductAction: <H> must be perm group or homomorphism" );
 fi;
 I := Image( map );
 if IsEmpty( domI ) then
 domI := [ 1 ];
 fi;
 degI := Length( domI );
 n := Length( domI );

 N := deg ^ n;
 gens := [ ];
 basegens:=List([1..n],i->[]);
 for gen in GeneratorsOfGroup( G ) do
 val := 1;
 for i in [ 1 .. n ] do
 Val := val * deg;
 list := [ ];
 for p in [ 0 .. N - 1 ] do
 q := QuoInt( p mod Val, val ) + 1;
 Add( list, p +
 ( Position( domG, domG[ q ] ^ gen ) - q ) * val );
 od;
 q:=PermList( list + 1 );
 if not IsOne(q) then
 Add(gens,q);
 fi;
 Add(basegens[i],q);
 val := Val;
 od;
 od;
 hgens:=[];
 for gen in GeneratorsOfGroup( I ) do
 list := [ ];
 for p in [ 0 .. N - 1 ] do
 adic := [ ];
 for i in [ 0 .. n - 1 ] do
 adic[ Position( domI, domI[ n - i ] ^ gen ) ] := p mod deg;
 p := QuoInt( p, deg );
 od;
 q := 0;
 for i in adic do
 q := q * deg + i;
 od;
 Add( list, q );
 od;
 q:=PermList( list + 1 );
 if not IsOne(q) then
 Add(gens,q);
 fi;
 Add(hgens,q);
 od;
 W := GroupByGenerators( gens, () ); # `gens' arose from `PermList'
 SetSize( W, Size( G ) ^ n * Size( I ) );

 # note random method
 rans := Filtered( [ G, H ], i ->
 IsBound( StabChainOptions( i ).random ) );
 if Length( rans ) > 0 then
 SetStabChainOptions( W, rec( random :=
 Minimum( List( rans, i -> StabChainOptions( i ).random ) ) ) );
 fi;

 info := rec(
 groups := [G,H],
 alpha := map,
 I := I,
 degI := degI,
 productType:=true,
 basegens := basegens,
 base := SubgroupNC(W,Flat(basegens)),
 hgens := hgens,
 embeddingType := NewType(
 GeneralMappingsFamily(PermutationsFamily,PermutationsFamily),
 IsEmbeddingProductActionWreathProductPermGroup),
 embeddings := []);

 SetWreathProductInfo( W, info );

 return W;
end );

##############################################################################
##
#M SemidirectProduct for permutation groups

##
## Use regular action
## Original version by Derek Holt, 6/9/96, in first GAP3 version of xmod
##
InstallMethod( SemidirectProduct, "generic method for permutation groups",
 [ IsPermGroup, IsGroupHomomorphism, IsPermGroup ],
function( R, map, S )

 local P, genP, genR, genS, L3, perm, r, s, ordS, genno, LS, info, aut;

 # Take the action of R on S by conjugation.
 LS := AsSSortedList( S );
 genP := [ ];
 genR := GeneratorsOfGroup( R );
 genS := GeneratorsOfGroup( S );
 for r in genR do
 aut:= Image( map, r );
 L3 := List( LS, x -> Position( LS, Image( aut, x ) ) );
 Add( genP, PermList( L3 ) );
 od;
 # Check order of group at this stage, to see if the action is faithful.
 # If not, adjoin the action of R as a permutation group.
 P := Group( genP, () ); # `genP' arose from `PermList'
 if ( Size( P ) <> Size( R ) ) then
 ordS := Size( S );
 genno := 0;
 for r in genR do
 genno := genno + 1;
 genP[ genno ] := genP[ genno ]
 * PermList( Concatenation( [1..ordS], ListPerm( r ) + ordS ) );
 od;
 fi;
 # Take the action of S on S by right multiplication.
 for s in genS do
 L3 := List( LS, x -> Position( LS, x*s ) );
 Add( genP, PermList( L3 ) );
 od;
 P := Group( genP, () ); # `genP' arose from `PermList'
 info := rec( groups := [ R, S ],
 lenlist := [ 0, Length( genR ), Length( genP ) ],
 embeddings := [ ],
 projections := true );
 SetSemidirectProductInfo( P, info );
 return P;
end );

InstallMethod( SemidirectProduct, "Induced permutation automorphisms",
 [ IsPermGroup, IsGroupHomomorphism, IsPermGroup ],
function( U, map, N )
local Ugens,imgs,conj,auc,d,embn,embs,l,u,P,info;
 Ugens:=GeneratorsOfGroup(U);
 imgs:=List(Ugens,x->Image(map,x));
 if ForAll(imgs,IsConjugatorIsomorphism) then
 conj:=List(imgs,ConjugatorOfConjugatorIsomorphism);
 auc:=ClosureGroup(N,conj);
 d:=DirectProduct(U,auc);
 embn:=Embedding(d,2);
 embs:=Embedding(d,1);
 # images of generators of U
 l:=List([1..Length(imgs)],x->Image(embn,conj[x])*Image(embs,Ugens[x]));
 u:=SubgroupNC(d,l);
 if Size(u)=Size(U) then # so the conjugating elements don't generate
 # something extra
 # (i.e. the map U->S_N, u->conj.perm. of auto is
 # a hom.)
 P:=ClosureGroup(Image(embn,N),l);
 embs:=GroupHomomorphismByImagesNC(U,P,Ugens,l);
 info := rec( groups := [ U, N ],
 embeddings := [embs,RestrictedMapping(embn,N) ],
 projections := RestrictedMapping(Projection(d,1),P));
 SetSemidirectProductInfo( P, info );
 return P;
 fi;
 fi;
 TryNextMethod();
end);

##############################################################################
##
#M Embedding for permutation semidirect products
##
InstallMethod( Embedding, "generic method for perm semidirect products",
 true, [ IsPermGroup and HasSemidirectProductInfo, IsPosInt ], 0,
function( D, i )
 local info, G, genG, imgs, hom;

 info := SemidirectProductInfo( D );
 if IsBound( info.embeddings[i] ) then
 return info.embeddings[i];
 fi;
 G := info.groups[i];
 genG := GeneratorsOfGroup( G );
 imgs := GeneratorsOfGroup( D ){[info.lenlist[i]+1 .. info.lenlist[i+1]]};
 hom := GroupHomomorphismByImagesNC( G, D, genG, imgs );
 SetIsInjective( hom, true );
 info.embeddings[i] := hom;
 return hom;
end );

##############################################################################
##
#M Projection for permutation semidirect products
##
InstallOtherMethod( Projection, "generic method for perm semidirect products",
 true, [ IsPermGroup and HasSemidirectProductInfo ], 0,
function( D )
 local info, genD, G, genG, imgs, hom, ker, list;

 info := SemidirectProductInfo( D );
 if not IsBool( info.projections ) then
 return info.projections;
 fi;
 G := info.groups[1];
 genG := GeneratorsOfGroup( G );
 genD := GeneratorsOfGroup( D );
 list := [ info.lenlist[2]+1 .. info.lenlist[3] ];
 imgs := Concatenation( genG, List( list, j -> One( G ) ) );
 hom := GroupHomomorphismByImagesNC( D, G, genD, imgs );
 SetIsSurjective( hom, true );
 ker := Subgroup( D, genD{ list } );
 SetKernelOfMultiplicativeGeneralMapping( hom, ker );
 info.projections := hom;
 return hom;
end );

Quelle gprdperm.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.29 Sekunden (vorverarbeitet) ]