|
#############################################################################
##
## 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>, <i> ) . . . . . . . . . . . . . . . . . . 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>, <i> ) . . . . . . . . . . . . . . . . . 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>, <i> ) . . . . . . . . . . . . . . . . . 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 <I>
degI, # degree of <I>
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 <I>
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>, <i> ) . . . . . . . . . . . . . . . . . . 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 <i> 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 );
[ Dauer der Verarbeitung: 0.45 Sekunden
(vorverarbeitet)
]
|
