|
#############################################################################
##
## 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 groups with a polycyclic collector.
##
#############################################################################
##
#M CanonicalPcgsWrtFamilyPcgs( <grp> )
##
InstallMethod( CanonicalPcgsWrtFamilyPcgs,
true,
[ IsGroup and HasFamilyPcgs ],
0,
function( grp )
local cgs;
cgs := CanonicalPcgs( InducedPcgsWrtFamilyPcgs(grp) );
if cgs = FamilyPcgs(grp) then
SetIsWholeFamily( grp, true );
fi;
return cgs;
end );
#############################################################################
##
#M CanonicalPcgsWrtHomePcgs( <grp> )
##
InstallMethod( CanonicalPcgsWrtHomePcgs,
true,
[ IsGroup and HasHomePcgs ],
0,
function( grp )
return CanonicalPcgs( InducedPcgsWrtHomePcgs(grp) );
end );
#############################################################################
##
#M InducedPcgsWrtFamilyPcgs( <grp> )
##
InstallMethod( InducedPcgsWrtFamilyPcgs,
true,
[ IsGroup and HasFamilyPcgs ],
0,
function( grp )
local pa, igs;
pa := FamilyPcgs(grp);
if HasPcgs(grp) and IsInducedPcgs(Pcgs(grp)) then
if pa = ParentPcgs(Pcgs(grp)) then
return Pcgs(grp);
fi;
fi;
igs := InducedPcgsByGenerators( pa, GeneratorsOfGroup(grp) );
if igs = pa then
SetIsWholeFamily( grp, true );
fi;
SetGroupOfPcgs (igs, grp);
return igs;
end );
InstallMethod( InducedPcgsWrtFamilyPcgs,"whole family", true,
[ IsPcGroup and IsWholeFamily], 0,
FamilyPcgs);
#############################################################################
##
#M InducedPcgsWrtHomePcgs( <G> )
##
InstallMethod( InducedPcgsWrtHomePcgs,"from generators", true, [ IsGroup ], 0,
function( G )
local home, ind;
home := HomePcgs( G );
if HasPcgs(G) and IsInducedPcgs(Pcgs(G)) then
if IsIdenticalObj(home,ParentPcgs(Pcgs(G))) then
return Pcgs(G);
fi;
fi;
ind := InducedPcgsByGenerators( home, GeneratorsOfGroup( G ) );
SetGroupOfPcgs (ind, G);
return ind;
end );
InstallMethod( InducedPcgsWrtHomePcgs,"pc group: home=family", true,
[ IsPcGroup ], 0,
InducedPcgsWrtFamilyPcgs);
#############################################################################
##
#M InducedPcgs( <pcgs>,<G> )
##
InstallGlobalFunction( InducedPcgs, function(pcgs, G)
local cache, i, igs;
if not IsPcgs(pcgs) then
Error("InducedPcgs: <pcgs> must be a pcgs");
fi;
if not IsGroup(G) then
Error("InducedPcgs: <G> must be a group");
fi;
pcgs := ParentPcgs (pcgs);
cache := ComputedInducedPcgses(G);
i := 1;
while i <= Length (cache) do
if cache[i]= pcgs then
return cache[i+1];
fi;
i := i + 2;
od;
igs := InducedPcgsOp( pcgs, G );
SetGroupOfPcgs (igs, G);
Append (cache, [pcgs, igs]);
if not HasPcgs(G) then
SetPcgs (G, igs);
fi;
# set home pcgs stuff
if not HasHomePcgs(G) then
SetHomePcgs (G, pcgs);
fi;
if IsIdenticalObj (HomePcgs(G), pcgs) then
SetInducedPcgsWrtHomePcgs (G, igs);
fi;
return igs;
end );
#############################################################################
##
#M InducedPcgsOp
##
InstallMethod (InducedPcgsOp, "generic method",
IsIdenticalObj, [IsPcgs, IsGroup],
function (pcgs, G)
return InducedPcgsByGenerators(
ParentPcgs(pcgs), GeneratorsOfGroup( G ) );
end);
#############################################################################
##
#M InducedPcgsOp
##
InstallMethod (InducedPcgsOp, "sift existing pcgs",
IsIdenticalObj, [IsPcgs, IsGroup and HasPcgs],
function (pcgs, G)
local seq, # pc sequence wrt pcgs (and its parent)
depths, # depths of this sequence
len, # length of the sequence
pos, # index
x, # a group element
d; # depth of x
pcgs := ParentPcgs (pcgs);
seq := [];
depths := [];
len := 0;
for x in Reversed (Pcgs (G)) do
# sift x through seq
d := DepthOfPcElement (pcgs, x);
pos := PositionSorted (depths, d);
while pos <= len and depths[pos] = d do
x := ReducedPcElement (pcgs, x, seq[pos]);
d := DepthOfPcElement (pcgs, x);
pos := PositionSorted (depths, d);
od;
if d> Length(pcgs) then
Error ("Panic: Pcgs (G) does not seem to be a pcgs");
else
seq{[pos+1..len+1]} := seq{[pos..len]};
depths{[pos+1..len+1]} := depths{[pos..len]};
seq[pos] := x;
depths[pos] := d;
len := len + 1;
fi;
od;
return InducedPcgsByPcSequenceNC (pcgs, seq, depths);
end);
#############################################################################
##
#M ComputedInducedPcgses
##
InstallMethod (ComputedInducedPcgses, "default method", [IsGroup],
G -> []);
#############################################################################
##
#F SetInducedPcgs( <home>,<G>,<pcgs> )
##
InstallGlobalFunction(SetInducedPcgs,function(home,G,pcgs)
home := ParentPcgs(home);
if not HasHomePcgs(G) then
SetHomePcgs(G,home);
fi;
if IsIdenticalObj(ParentPcgs(pcgs),home) then
Append (ComputedInducedPcgses(G), [home, pcgs]);
if IsIdenticalObj(HomePcgs(G),home) then
SetInducedPcgsWrtHomePcgs(G,pcgs);
fi;
fi;
SetGroupOfPcgs (pcgs, G);
end);
#############################################################################
##
#M Pcgs( <G> )
##
InstallMethod( Pcgs, "fail if not solvable", true,
[ IsGroup and HasIsSolvableGroup ],
SUM_FLAGS, # for groups for which we know that they are not solvable
# this is the best we can do.
function( G )
if not IsSolvableGroup( G ) then return fail;
else TryNextMethod(); fi;
end );
#############################################################################
##
#M Pcgs( <pcgrp> )
##
InstallMethod( Pcgs,
"for a group with known family pcgs",
true,
[ IsGroup and HasFamilyPcgs ],
0,
InducedPcgsWrtFamilyPcgs );
InstallMethod( Pcgs,
"for a group with known home pcgs",
true,
[ IsGroup and HasHomePcgs ],
1,
InducedPcgsWrtHomePcgs );
InstallMethod( Pcgs, "take induced pcgs", true,
[ IsGroup and HasInducedPcgsWrtHomePcgs ], SUM_FLAGS,
InducedPcgsWrtHomePcgs );
#############################################################################
##
#M Pcgs( <whole-family-grp> )
##
InstallMethod( Pcgs,
"for a group containing the whole family and with known family pcgs",
true,
[ IsGroup and HasFamilyPcgs and IsWholeFamily ],
0,
FamilyPcgs );
#############################################################################
##
#M GeneralizedPcgs( <G> )
##
# This used to be an immediate method. It was replaced by an ordinary
# method as the attribute is set when creating pc groups.
InstallMethod( GeneralizedPcgs,true,[ IsGroup and HasPcgs], 0, Pcgs );
#############################################################################
##
#M HomePcgs( <G> )
##
## BH: changed Pcgs to G -> ParentPcgs (Pcgs(G))
##
InstallMethod( HomePcgs, true, [ IsGroup ], 0, G -> ParentPcgs( Pcgs( G ) ) );
#############################################################################
##
#M PcgsChiefSeries( <pcgs> )
##
InstallMethod( PcgsChiefSeries,"compute chief series and pcgs",true,
[IsGroup],0,
function(G)
local p,cs,csi,l,i,pcs,ins,j,u;
p:=Pcgs(G);
if p=fail then
Error("<G> must be solvable");
fi;
if not HasParent(G) then
SetParentAttr(G,Parent(G));
fi;
cs:=ChiefSeries(G);
csi:=List(cs,i->InducedPcgs(p,i));
l:=Length(cs);
pcs:=[];
ins:=[0];
for i in [l-1,l-2..1] do
# extend the pc sequence. We have a vector space factor, so we can
# simply add *some* further generators.
u:=AsSubgroup(Parent(G),cs[i+1]);
for j in Reversed(Filtered(csi[i],k->not k in cs[i+1])) do
if not j in u then
Add(pcs,j);
#NC is safe
u:=ClosureSubgroupNC(u,j);
fi;
od;
if Length(pcs)<>Length(csi[i]) then
Error("pcgs length!");
fi;
Add(ins,Length(pcs));
od;
l:=Length(pcs)+1;
pcs:=PcgsByPcSequenceNC(FamilyObj(OneOfPcgs(p)),Reversed(pcs));
SetGroupOfPcgs (pcs, G);
# store the indices
SetIndicesChiefNormalSteps(pcs,Reversed(List(ins,i->l-i)));
return pcs;
end);
#############################################################################
##
#M GroupWithGenerators( <gens> ) . . . . . . . . . . . . group by generators
#M GroupWithGenerators( <gens>, <id> )
##
## These methods override the generic code. They are installed for
## `IsMultiplicativeElementWithInverseByPolycyclicCollectorCollection' and
## automatically set family pcgs and home pcgs.
##
InstallMethod( GroupWithGenerators,
"method for pc elements collection",
true, [ IsCollection and
IsMultiplicativeElementWithInverseByPolycyclicCollectorCollection and
IsFinite] ,
# override methods for `IsList' or `IsEmpty'.
10,
function( gens )
local G,fam,id,pcgs;
fam:=FamilyObj(gens);
pcgs:=DefiningPcgs(ElementsFamily(fam));
id:=One(gens[1]);
# pc groups are always finite and gens is finite.
G:=MakeGroupyObj(fam, IsSolvableGroup and IsFinite,
AsList(gens),id,
FamilyPcgs,pcgs,HomePcgs,pcgs,GeneralizedPcgs,pcgs);
return G;
end );
InstallOtherMethod( GroupWithGenerators,
"method for pc collection and identity element",
IsCollsElms, [ IsCollection and
IsMultiplicativeElementWithInverseByPolycyclicCollectorCollection
and IsFinite,
IsMultiplicativeElementWithInverseByPolycyclicCollector] ,
0,
function( gens, id )
local G,fam,pcgs;
fam:=FamilyObj(gens);
pcgs:=DefiningPcgs(ElementsFamily(fam));
# pc groups are always finite and gens is finite.
G:=MakeGroupyObj(fam, IsSolvableGroup and IsFinite,
AsList(gens),id,
FamilyPcgs,pcgs,HomePcgs,pcgs,GeneralizedPcgs,pcgs);
return G;
end );
InstallOtherMethod( GroupWithGenerators,
"method for empty pc collection and identity element",
true, [ IsList and IsEmpty,
IsMultiplicativeElementWithInverseByPolycyclicCollector] ,
# override methods for `IsList' or `IsEmpty'.
10,
function( empty, id )
local G,fam,pcgs;
fam:= CollectionsFamily( FamilyObj( id ) );
pcgs:=DefiningPcgs(ElementsFamily(fam));
# pc groups are always finite and gens is finite.
G:=MakeGroupyObj(fam, IsSolvableGroup and IsFinite,
empty,id,
FamilyPcgs,pcgs,HomePcgs,pcgs,GeneralizedPcgs,pcgs);
return G;
end );
#############################################################################
##
#M <elm> in <pcgrp>
##
InstallMethod( \in,
"for pc group",
IsElmsColls,
[ IsMultiplicativeElementWithInverse,
IsGroup and HasFamilyPcgs and CanEasilyComputePcgs
],
2, # rank this method higher than the following one
function( elm, grp )
return SiftedPcElement(InducedPcgsWrtFamilyPcgs(grp),elm) = One(grp);
end );
#############################################################################
##
#M <elm> in <pcgrp>
##
InstallMethod( \in,
"for pcgs computable groups with home pcgs",
IsElmsColls,
[ IsMultiplicativeElementWithInverse,
IsGroup and HasInducedPcgsWrtHomePcgs and CanEasilyComputePcgs
],
1, # rank this method higher than the following one
function( elm, grp )
local pcgs, ppcgs;
pcgs := InducedPcgsWrtHomePcgs (grp);
ppcgs := ParentPcgs (pcgs);
if Length (pcgs) = Length (ppcgs) or not CanEasilyTestMembership (GroupOfPcgs(ppcgs)) then
TryNextMethod();
fi;
if elm in GroupOfPcgs (ppcgs) then
return SiftedPcElement(InducedPcgsWrtHomePcgs(grp),elm) = One(grp);
else
return false;
fi;
end );
#############################################################################
##
#M <elm> in <pcgrp>
##
InstallMethod( \in,
"for pcgs computable groups with induced pcgs",
IsElmsColls,
[ IsMultiplicativeElementWithInverse,
IsGroup and HasComputedInducedPcgses and CanEasilyComputePcgs
],
0,
function( elm, grp )
local pcgs, ppcgs;
for pcgs in ComputedInducedPcgses(grp) do
ppcgs := ParentPcgs (pcgs);
if Length (pcgs) < Length (ppcgs) and CanEasilyTestMembership (GroupOfPcgs(ppcgs)) then
if elm in GroupOfPcgs (ppcgs) then
return SiftedPcElement(pcgs, elm) = One(grp);
else
return false;
fi;
fi;
od;
TryNextMethod();
end );
#############################################################################
##
#M <pcgrp1> = <pcgrp2>
##
InstallMethod( \=,
"pcgs computable groups using home pcgs",
IsIdenticalObj,
[ IsGroup and HasHomePcgs and HasCanonicalPcgsWrtHomePcgs,
IsGroup and HasHomePcgs and HasCanonicalPcgsWrtHomePcgs ],
0,
function( left, right )
if HomePcgs(left) <> HomePcgs(right) then
TryNextMethod();
fi;
return CanonicalPcgsWrtHomePcgs(left) = CanonicalPcgsWrtHomePcgs(right);
end );
#############################################################################
##
#M <pcgrp1> = <pcgrp2>
##
InstallMethod( \=,
"pcgs computable groups using family pcgs",
IsIdenticalObj,
[ IsGroup and HasFamilyPcgs and HasCanonicalPcgsWrtFamilyPcgs,
IsGroup and HasFamilyPcgs and HasCanonicalPcgsWrtFamilyPcgs ],
0,
function( left, right )
if FamilyPcgs(left) <> FamilyPcgs(right) then
TryNextMethod();
fi;
return CanonicalPcgsWrtFamilyPcgs(left)
= CanonicalPcgsWrtFamilyPcgs(right);
end );
#############################################################################
##
#M IsSubset( <pcgrp>, <pcsub> )
##
## This method is better than calling `\in' for all generators,
## since one has to fetch the pcgs only once.
##
InstallMethod( IsSubset,
"pcgs computable groups",
IsIdenticalObj,
[ IsGroup and HasFamilyPcgs and CanEasilyComputePcgs,
IsGroup ],
0,
function( grp, sub )
local pcgs, id, g;
pcgs := InducedPcgsWrtFamilyPcgs(grp);
id := One(grp);
for g in GeneratorsOfGroup(sub) do
if SiftedPcElement( pcgs, g ) <> id then
return false;
fi;
od;
return true;
end );
#############################################################################
##
#M SubgroupByPcgs( <G>, <pcgs> )
##
InstallMethod( SubgroupByPcgs, "subgroup with pcgs",
true, [IsGroup, IsPcgs], 0,
function( G, pcgs )
local U;
U := SubgroupNC( G, AsList( pcgs ) );
SetSize(U,Product(RelativeOrders(pcgs)));
SetPcgs( U, pcgs );
SetGroupOfPcgs (pcgs, U);
# home pcgs will be inherited
if HasHomePcgs(U) and IsIdenticalObj(HomePcgs(U),ParentPcgs(pcgs)) then
SetInducedPcgsWrtHomePcgs(U,pcgs);
fi;
if HasIsInducedPcgsWrtSpecialPcgs( pcgs ) and
IsInducedPcgsWrtSpecialPcgs( pcgs ) and
HasSpecialPcgs( G ) then
SetInducedPcgsWrtSpecialPcgs( U, pcgs );
fi;
return U;
end);
#############################################################################
##
#F VectorSpaceByPcgsOfElementaryAbelianGroup( <pcgs>, <f> )
##
InstallGlobalFunction( VectorSpaceByPcgsOfElementaryAbelianGroup,
function( arg )
local pcgs, dim, field;
pcgs := arg[1];
dim := Length( pcgs );
if IsBound( arg[2] ) then
field := arg[2];
elif dim > 0 then
field := GF( RelativeOrderOfPcElement( pcgs, pcgs[1] ) );
else
Error("trivial vectorspace, need field \n");
fi;
return VectorSpace( field, Immutable( IdentityMat( dim, field ) ) );
end );
#############################################################################
##
#F LinearActionLayer( <G>, <gens>, <pcgs> )
##
InstallGlobalFunction( LinearActionLayer, function( arg )
local gens, pcgs, field, m,mat,i,j;
# catch arguments
if Length( arg ) = 2 then
if IsGroup( arg[1] ) then
gens := GeneratorsOfGroup( arg[1] );
elif IsPcgs( arg[1] ) then
gens := AsList( arg[1] );
else
gens := arg[1];
fi;
pcgs := arg[2];
elif Length( arg ) = 3 then
gens := arg[2];
pcgs := arg[3];
fi;
# in case the layer is trivial
if Length( pcgs ) = 0 then
Error("pcgs is trivial - no field defined ");
fi;
# construct matrix rep
field := GF( RelativeOrderOfPcElement( pcgs, pcgs[1] ) );
# the following code takes too much time, as it has to create obvious pc
# elements again from vectors with 1 nonzero entry.
# V := Immutable( IdentityMat(Length(pcgs),field) );
# linear := function( x, g )
# return ExponentsOfPcElement( pcgs,
# PcElementByExponentsNC( pcgs, x )^g ) * One(field);
# end;
# return LinearAction( gens, V, linear );
#this is done much quicker by the following direct code:
m:=[];
for i in gens do
mat:=[];
for j in pcgs do
Add(mat,ExponentsConjugateLayer(pcgs,j,i)*One(field));
od;
mat:=ImmutableMatrix(field,mat,true);
Add(m,mat);
od;
return m;
end );
#############################################################################
##
#F AffineActionLayer( <G>, <pcgs>, <transl> )
##
InstallGlobalFunction( AffineActionLayer, function( arg )
local gens, pcgs, transl, V, field, linear;
# catch arguments
if Length( arg ) = 3 then
if IsPcgs( arg[1] ) then
gens := AsList( arg[1] );
elif IsGroup( arg[1] ) then
gens := GeneratorsOfGroup( arg[1] );
else
gens := arg[1];
fi;
pcgs := arg[2];
transl := arg[3];
elif Length( arg ) = 4 then
gens := arg[2];
pcgs := arg[3];
transl := arg[4];
fi;
# in the trivial case we cannot do anything
if Length( pcgs ) = 0 then
Error("layer is trivial . . . field is not defined \n");
fi;
# construct matrix rep
field := GF( RelativeOrderOfPcElement( pcgs, pcgs[1] ) );
V:= Immutable( IdentityMat(Length(pcgs),field) );
linear := function( x, g )
return ExponentsConjugateLayer(pcgs,
PcElementByExponentsNC( pcgs, x ),g ) * One(field);
end;
return AffineAction( gens, V, linear, transl );
end );
#############################################################################
##
#M AffineAction( <gens>, <V>, <linear>, <transl> )
##
InstallMethod( AffineAction,"generators",
true,
[ IsList,
IsMatrix,
IsFunction,
IsFunction ],
0,
function( Ggens, V, linear, transl )
local mats, gens, zero,one, g, mat, i, vec;
mats := [];
gens:=V;
zero:=Zero(V[1][1]);
one:=One(zero);
for g in Ggens do
mat := List( gens, x -> linear( x, g ) );
vec := ShallowCopy( transl(g) );
for i in [ 1 .. Length(mat) ] do
mat[i] := ShallowCopy( mat[i] );
Add( mat[i], zero );
od;
Add( vec, one );
Add( mat, vec );
mat:=ImmutableMatrix(Characteristic(one),mat,true);
Add( mats, mat );
od;
return mats;
end );
InstallOtherMethod( AffineAction,"group",
true,
[ IsGroup,
IsMatrix,
IsFunction,
IsFunction ],
0,
function( G, V, linear, transl )
return AffineAction( GeneratorsOfGroup(G), V, linear, transl );
end );
InstallOtherMethod( AffineAction,"group2",
true,
[ IsGroup,
IsList,
IsMatrix,
IsFunction,
IsFunction ],
0,
function( G, gens, V, linear, transl )
return AffineAction( gens, V, linear, transl );
end );
InstallOtherMethod( AffineAction,"pcgs",
true,
[ IsPcgs,
IsMatrix,
IsFunction,
IsFunction ],
0,
function( pcgsG, V, linear, transl )
return AffineAction( AsList( pcgsG ), V, linear, transl );
end );
#############################################################################
##
#M ClosureGroup( <U>, <H> )
##
## use home pcgs
##
InstallMethod( ClosureGroup,
"groups with home pcgs",
IsIdenticalObj,
[ IsGroup and HasHomePcgs,
IsGroup and HasHomePcgs ],
0,
function( U, H )
local home, pcgsU, pcgsH, new, N;
home := HomePcgs( U );
if home <> HomePcgs( H ) then
TryNextMethod();
fi;
pcgsU := InducedPcgs(home,U);
pcgsH := InducedPcgs(home,H);
if Length( pcgsU ) < Length( pcgsH ) then
new := InducedPcgsByPcSequenceAndGenerators( home, pcgsH,
GeneratorsOfGroup( U ) );
else
new := InducedPcgsByPcSequenceAndGenerators( home, pcgsU,
GeneratorsOfGroup( H ) );
fi;
N := SubgroupByPcgs( GroupOfPcgs( home ), new );
# SetHomePcgs( N, home );
# SetInducedPcgsWrtHomePcgs( N, new );
return N;
end );
#############################################################################
##
#M ClosureGroup( <U>, <g> )
##
## use home pcgs
##
InstallMethod( ClosureGroup,
"groups with home pcgs",
IsCollsElms,
[ IsGroup and HasHomePcgs,
IsMultiplicativeElementWithInverse ],
0,
function( U, g )
local home, pcgsU, new, N;
home := HomePcgs( U );
pcgsU := InducedPcgsWrtHomePcgs( U );
if not g in GroupOfPcgs( home ) then
TryNextMethod();
fi;
if g in U then
return U;
else
new := InducedPcgsByPcSequenceAndGenerators( home, pcgsU, [g] );
N := SubgroupByPcgs( GroupOfPcgs(home), new );
# SetHomePcgs( N, home );
# SetInducedPcgsWrtHomePcgs( N, new );
return N;
fi;
end );
#############################################################################
##
#M CommutatorSubgroup( <U>, <V> )
##
InstallMethod( CommutatorSubgroup,
"groups with home pcgs",
true,
[ IsGroup and HasHomePcgs,
IsGroup and HasHomePcgs ],
0,
function( U, V )
local pcgsU, pcgsV, home, C, u, v;
# check
home := HomePcgs(U);
if home <> HomePcgs( V ) then
TryNextMethod();
fi;
pcgsU := InducedPcgsWrtHomePcgs(U);
pcgsV := InducedPcgsWrtHomePcgs(V);
# catch trivial cases
if Length(pcgsU) = 0 or Length(pcgsV) = 0 then
return TrivialSubgroup( GroupOfPcgs(home) );
fi;
if U = V then
return DerivedSubgroup(U);
fi;
# compute commutators
C := [];
for u in pcgsU do
for v in pcgsV do
AddSet( C, Comm( v, u ) );
od;
od;
C := Subgroup( GroupOfPcgs( home ), C );
C := NormalClosure( ClosureGroup(U,V), C );
# that's it
return C;
end );
#############################################################################
##
#M ConjugateGroup( <U>, <g> )
##
InstallMethod( ConjugateGroup,
"groups with home pcgs",
IsCollsElms,
[ IsGroup and HasHomePcgs,
IsMultiplicativeElementWithInverse ],
0,
function( U, g )
local home, pcgs, id, pag, h, d, N;
# <g> must lie in the home
home := HomePcgs(U);
if not g in GroupOfPcgs(home) then
TryNextMethod();
fi;
# shift <g> through <U>
pcgs := InducedPcgsWrtHomePcgs( U );
id := Identity( U );
g := SiftedPcElement( pcgs, g );
# catch trivial case
if IsEmpty(pcgs) or g = id then
return U;
fi;
# conjugate generators
pag := [];
for h in Reversed( pcgs ) do
h := h ^ g;
d := DepthOfPcElement( home, h );
while h <> id and IsBound( pag[d] ) do
h := ReducedPcElement( home, h, pag[d] );
d := DepthOfPcElement( home, h );
od;
if h <> id then
pag[d] := h;
fi;
od;
# <pag> is an induced system
pag := Compacted( pag );
N := Subgroup( GroupOfPcgs(home), pag );
SetHomePcgs( N, home );
pag := InducedPcgsByPcSequenceNC( home, pag );
SetGroupOfPcgs (pag, N);
SetInducedPcgsWrtHomePcgs( N, pag );
# maintain useful information
UseIsomorphismRelation( U, N );
return N;
end );
#############################################################################
##
#M ConjugateSubgroups( <G>, <U> )
##
InstallMethod( ConjugateSubgroups,
"groups with home pcgs",
IsIdenticalObj,
[ IsGroup and HasHomePcgs,
IsGroup and HasHomePcgs ],
0,
function( G, U )
local pcgs, home, f, orb, i, L, res, H,ip;
# check the home pcgs are compatible
home := HomePcgs(U);
if home <> HomePcgs(G) then
TryNextMethod();
fi;
H := GroupOfPcgs( home );
# get a canonical pcgs for <U>
pcgs := CanonicalPcgsWrtHomePcgs(U);
# <G> acts on this <pcgs> via conjugation
f := function( c, g )
#was: CanonicalPcgs( HomomorphicInducedPcgs( home, c, g ) );
return CorrespondingGeneratorsByModuloPcgs(home,List(c,i->i^g));
end;
# compute the orbit of <G> on <pcgs>
orb := Orbit( G, pcgs, f );
res := List( orb, ReturnFalse );
for i in [1..Length(orb)] do
L := Subgroup( H, orb[i] );
SetHomePcgs( L, home );
if not(IsPcgs(orb[i])) then
ip:=InducedPcgsByPcSequenceNC(home,orb[i]);
else
ip:=orb[i];
fi;
SetInducedPcgsWrtHomePcgs( L, ip );
SetGroupOfPcgs (ip, L);
res[i] := L;
od;
return res;
end );
#############################################################################
##
#M Core( <U>, <V> )
##
InstallMethod( CoreOp,
"pcgs computable groups",
true,
[ IsGroup and CanEasilyComputePcgs,
IsGroup ],
0,
function( V, U )
local pcgsV, C, v, N;
# catch trivial cases
pcgsV := Pcgs(V);
if IsSubset( U, V ) or IsTrivial(U) or IsTrivial(V) then
return U;
fi;
# start with <U>.
C := U;
# now compute intersection with all conjugate subgroups, conjugate with
# all generators of V and its powers
for v in Reversed(pcgsV) do
repeat
N := ConjugateGroup( C, v );
if C <> N then
C := Intersection( C, N );
fi;
until C = N;
if IsTrivial(C) then
return C;
fi;
od;
return C;
end );
#############################################################################
##
#M EulerianFunction( <G>, <n> )
##
InstallMethod( EulerianFunction,
"pcgs computable groups using special pcgs",
true,
[ IsGroup and CanEasilyComputePcgs,
IsPosInt ],
0,
function( G, n )
local spec, first, weights, m, i, phi, start,
next, p, d, j, pcgsS, pcgsN, pcgsL, mats,
modu, max, series, comps, sub, new, index, order;
spec := SpecialPcgs( G );
if Length( spec ) = 0 then return 1; fi;
first := LGFirst( spec );
weights := LGWeights( spec );
m := Length( spec );
# the first head
i := 1;
phi := 1;
while i <= Length(first)-1 and
weights[first[i]][1] = 1 and weights[first[i]][2] = 1 do
start := first[i];
next := first[i+1];
p := weights[start][3];
d := next - start;
for j in [0..d-1] do
phi := phi * (p^n - p^j);
od;
if phi = 0 then return 0; fi;
i := i + 1;
od;
# the rest
while i <= Length( first ) - 1 do
start := first[i];
next := first[i+1];
p := weights[start][3];
d := next - start;
if weights[start][2] = 1 then
pcgsS := InducedPcgsByPcSequenceNC( spec, spec{[start..m]} );
pcgsN := InducedPcgsByPcSequenceNC( spec, spec{[next..m]} );
pcgsL := pcgsS mod pcgsN;
mats := LinearActionLayer( spec, pcgsL );
modu := GModuleByMats( mats, GF(p) );
max := MTX.BasesMaximalSubmodules( modu );
# compute series
series := [ Immutable( IdentityMat(d, GF(p)) ) ];
comps := [];
sub := series[1];
while Length( max ) > 0 do
sub := SumIntersectionMat( sub, max[1] )[2];
if Length( sub ) = 0 then
new := max;
else
new := Filtered( max, x ->
RankMat( Concatenation( x, sub ) ) < d );
fi;
Add( comps, Sum( List( new, x -> p^(d - Length(x)) ) ) );
Add( series, sub );
max := Difference( max, new );
od;
# run down series
for j in [1..Length( series )-1] do
index := Length( series[j] ) - Length( series[j+1] );
order := p^index;
phi := phi * ( order^n - comps[j] );
if phi = 0 then return phi; fi;
od;
# only the radical is missing now
index := Length( Last(series) );
order := p^index;
phi := phi * (order^n);
if phi = 0 then return 0; fi;
else
order := p^d;
phi := phi * ( order^n );
if phi = 0 then return 0; fi;
fi;
i := i + 1;
od;
return phi;
end );
RedispatchOnCondition(EulerianFunction,true,[IsGroup,IsPosInt],
[IsSolvableGroup,IsPosInt],
1 # make the priority higher than the default method computing
# the table of marks
);
#############################################################################
##
#M LinearAction( <gens>, <basisvectors>, <linear> )
##
InstallMethod( LinearAction,
true,
[ IsList,
IsMatrix,
IsFunction ],
0,
function( gens, base, linear )
local i,mats;
# catch trivial cases
if Length( gens ) = 0 then
return [];
fi;
# compute matrices
if Length(base)>0 then
mats := List( gens, x -> ImmutableMatrix(Characteristic(base),
List( base, y -> linear( y, x ) ),true ));
else
mats:=List(gens,i->[]);
fi;
MakeImmutable(mats);
return mats;
end );
InstallOtherMethod( LinearAction,
true,
[ IsGroup,
IsMatrix,
IsFunction ],
0,
function( G, base, linear )
return LinearAction( GeneratorsOfGroup( G ), base, linear );
end );
InstallOtherMethod( LinearAction,
true,
[ IsPcgs,
IsMatrix,
IsFunction ],
0,
function( pcgs, base, linear )
return LinearAction( pcgs, base, linear );
end );
InstallOtherMethod( LinearAction,
true,
[ IsGroup,
IsList,
IsMatrix,
IsFunction ],
0,
function( G, gens, base, linear )
return LinearAction( gens, base, linear );
end );
#############################################################################
##
#M NormalClosure( <G>, <U> )
##
InstallMethod( NormalClosureOp,
"groups with home pcgs",
true,
[ IsGroup and HasHomePcgs,
IsGroup and HasHomePcgs ],
0,
function( G, U )
local pcgs, home, gens, subg, id, K, M, g, u, tmp;
# catch trivial case
pcgs := InducedPcgsWrtHomePcgs(U);
if Length(pcgs) = 0 then
return U;
fi;
home := HomePcgs(U);
if home <> HomePcgs(G) then
TryNextMethod();
fi;
# get operating elements
gens := GeneratorsOfGroup( G );
gens := Set( gens, x -> SiftedPcElement( pcgs, x ) );
subg := GeneratorsOfGroup( U );
id := Identity( G );
K := ShallowCopy( pcgs );
repeat
M := [];
for g in gens do
for u in subg do
tmp := Comm( g, u );
if tmp <> id then
AddSet( M, tmp );
fi;
od;
od;
tmp := InducedPcgsByPcSequenceAndGenerators( home, K, M );
tmp := CanonicalPcgs( tmp );
subg := Filtered( tmp, x -> not x in K );
K := tmp;
until 0 = Length(subg);
K := SubgroupByPcgs( GroupOfPcgs(home), tmp );
# SetHomePcgs( K, home );
# SetInducedPcgsWrtHomePcgs( K, tmp );
return K;
end );
#############################################################################
##
#M Random( <pcgrp> )
##
InstallMethodWithRandomSource( Random,
"for a random source and a pcgs computable groups",
[ IsRandomSource, IsGroup and CanEasilyComputePcgs and IsFinite ],
function(rs, grp)
local p;
p := Pcgs(grp);
if Length( p ) = 0 then
return One( grp );
else
return Product( p, x -> x^Random(rs, 1, RelativeOrderOfPcElement(p,x)) );
fi;
end );
BindGlobal( "CentralizerSolvableGroup", function(H,U,elm)
local G, home, # the supergroup (of <H> and <U>), the home pcgs
Hp, # a pcgs for <H>
inequal, # G<>H flag
eas, # elementary abelian series in <G> through <U>
step, # counter looping over <eas>
L, # members of <eas>
Kp,Lp, # induced and modulo pcgs's
KcapH,LcapH, # pcgs's of intersections with <H>
N, cent, # elementary abelian factor, for affine action
cls, # classes in range/source of homomorphism
opr, # (elm^opr)=cls.representative
nexpo,indstep,Ldep,allcent;
# Treat the case of a trivial group.
if IsTrivial( U ) then
return H;
fi;
if IsSubgroup(H,U) then
G:=H;
inequal:=false;
else
G:=ClosureGroup( H, U );
inequal:=true;
fi;
home:=HomePcgs(G);
if not HasIndicesEANormalSteps(home) then
home:=PcgsElementaryAbelianSeries(G);
fi;
# Calculate a (central) elementary abelian series with all pcgs induced
# w.r.t. <home>.
if IsPGroup( G ) then
home:=PcgsCentralSeries(G);
eas:=CentralNormalSeriesByPcgs(home);
cent:=ReturnTrue;
else
home:=PcgsElementaryAbelianSeries(G);
eas:=EANormalSeriesByPcgs(home);
cent:=PcClassFactorCentralityTest;
fi;
indstep:=IndicesEANormalSteps(home);
Hp:=InducedPcgs(home,H);
# Initialize the algorithm for the trivial group.
step:=1;
while IsSubset( eas[ step + 1 ], U ) do
step:=step + 1;
od;
L :=eas[ step ];
Ldep:=indstep[step];
Lp:=InducedPcgs(home,L);
if inequal then
LcapH:=NormalIntersectionPcgs( home, Hp, Lp );
fi;
cls:=[rec( representative:=elm,centralizer:=H,
centralizerpcgs:=InducedPcgs(home,H) )];
opr:=One( U );
# Now go back through the factors by all groups in the elementary abelian
# series.
for step in [ step + 1 .. Length( eas ) ] do
# We apply the homomorphism principle to the homomorphism G/L -> G/K.
# The actual computations are all done in <G>, factors are
# represented by modulo pcgs.
Kp:=Lp;
L :=eas[ step ];
Ldep:=indstep[step];
Lp:=InducedPcgs(home,L );
N :=Kp mod Lp; # modulo pcgs representing the kernel
allcent:=cent(home,home,N,Ldep);
if allcent=false then
nexpo:=LinearActionLayer(home{[1..indstep[step-1]-1]},N);
fi;
# #T What is this? Obviously it is needed somewhere, but it is
# #T certainly not good programming style. AH
# SetFilterObj( N, IsPcgs );
if inequal then
KcapH :=LcapH;
LcapH :=NormalIntersectionPcgs( home, Hp, Lp );
N!.capH:=KcapH mod LcapH;
#T See above
# SetFilterObj( N!.capH, IsPcgs );
else
N!.capH:=N;
fi;
cls[ 1 ].candidates:=cls[ 1 ].representative;
if allcent
or cent(home, cls[ 1 ].centralizerpcgs, N, Ldep ) then
cls:=CentralStepClEANS( home,H, U, N, cls[ 1 ],false );
else
cls:=GeneralStepClEANS( home,H, U, N, nexpo,cls[ 1 ],false );
fi;
opr:=opr * cls[ 1 ].operator;
if IsModuloPcgs(cls[1].cengen) then
cls[1].centralizerpcgs:=cls[1].cengen;
else
cls[1].centralizerpcgs:=InducedPcgsByPcSequenceNC(home,cls[1].cengen);
fi;
od;
if not IsBound(cls[1].centralizer) then
cls[1].centralizer:=SubgroupByPcgs(G,cls[1].centralizerpcgs);
fi;
cls:=ConjugateSubgroup( cls[ 1 ].centralizer, opr ^ -1 );
return cls;
end );
#############################################################################
##
#M Centralizer( <G>, <g> ) . . . . . . . . . . . . . . using affine methods
##
InstallMethod( CentralizerOp,
"pcgs computable group and element",
IsCollsElms,
[ IsGroup and CanEasilyComputePcgs and IsFinite,
IsMultiplicativeElementWithInverse ],
0, # in solvable permutation groups, backtrack seems preferable
function( G, g )
return CentralizerSolvableGroup( G, GroupByGenerators( [ g ] ), g );
end );
InstallMethod( CentralizerOp,
"pcgs computable groups",
IsIdenticalObj,
[ IsGroup and CanEasilyComputePcgs and IsFinite,
IsGroup and CanEasilyComputePcgs and IsFinite ],
0, # in solvable permutation groups, backtrack seems preferable
function( G, H )
local h,P;
P:=Parent(G);
for h in MinimalGeneratingSet( H ) do
G := CentralizerSolvableGroup( G,H, h );
od;
G:=AsSubgroup(P,G);
Assert(2,ForAll(GeneratorsOfGroup(G),i->ForAll(GeneratorsOfGroup(H),
j->Comm(i,j)=One(G))));
return G;
end );
#############################################################################
##
#M RepresentativeAction( <G>, <d>, <e>, OnPoints ) using affine methods
##
InstallOtherMethod( RepresentativeActionOp,
"element conjugacy in pcgs computable groups", IsCollsElmsElmsX,
[ IsGroup and CanEasilyComputePcgs and IsFinite,
IsMultiplicativeElementWithInverse,
IsMultiplicativeElementWithInverse,
IsFunction ],
0,
function( G, d, e, opr )
if opr <> OnPoints or not (IsPcGroup(G) or (d in G and e in G)) or
not (d in G and e in G) then
TryNextMethod();
fi;
return ClassesSolvableGroup( G, 4,rec(candidates:= [ d, e ] ));
end );
#############################################################################
##
#M CentralizerModulo(<H>,<N>,<elm>) full preimage of C_(H/N)(elm.N)
##
InstallMethod(CentralizerModulo,"pcgs computable groups, for elm",
IsCollsCollsElms,[IsGroup and CanEasilyComputePcgs, IsGroup and
CanEasilyComputePcgs, IsMultiplicativeElementWithInverse],0,
function(H,NT,elm)
local G, # common parent
home,Hp, # the home pcgs, induced pcgs
eas, step, # elementary abelian series in <G> through <U>
ea2, # used for factor series
L, # members of <eas>
Kp,Lp, # induced and modulo pcgs's
KcapH,LcapH, # pcgs's of intersections with <H>
N, cent, # elementary abelian factor, for affine action
tra, # transversal for candidates
nexpo,indstep,Ldep,allcent,
cl, i; # loop variables
# Treat trivial cases.
if Index(H,NT)=1 or (HasAbelianFactorGroup(H,NT) and elm in H)
or elm in NT then
return H;
fi;
if elm in H then
G:=H;
else
G:=ClosureGroup(H,elm);
# is the subgroup still normal
if not IsNormal(G,NT) then
Error("subgroup not normal!");
fi;
fi;
home := HomePcgs( G );
if not HasIndicesEANormalSteps(home) then
home:=PcgsElementaryAbelianSeries(G);
fi;
# Calculate a (central) elementary abelian series.
eas:=fail;
if IsPGroup( G ) then
home:=PcgsPCentralSeriesPGroup(G);
eas:=PCentralNormalSeriesByPcgsPGroup(home);
if NT in eas then
cent := ReturnTrue;
else
eas:=fail; # useless
fi;
fi;
if eas=fail then
home:=PcgsElementaryAbelianSeries([G,NT]);
eas:=EANormalSeriesByPcgs(home);
cent:=PcClassFactorCentralityTest;
fi;
indstep:=IndicesEANormalSteps(home);
# series to NT
ea2:=List(eas,i->ClosureGroup(NT,i));
eas:=[];
for i in ea2 do
if not i in eas then
Add(eas,i);
fi;
od;
for i in eas do
if not HasHomePcgs(i) then
SetHomePcgs(i,ParentPcgs(home));
fi;
od;
Hp:=InducedPcgs(home,H);
# Initialize the algorithm for the trivial group.
step := 1;
while IsSubset( eas[ step + 1 ], H ) do
step := step + 1;
od;
L := eas[ step ];
Lp := InducedPcgs(home, L );
if not IsIdenticalObj( G, H ) then
LcapH := NormalIntersectionPcgs( home, Hp, Lp );
fi;
cl := rec( representative := elm,
centralizer := H,
centralizerpcgs := InducedPcgs(home,H ));
tra := One( H );
# cls := List( candidates, c -> cl );
# tra := List( candidates, c -> One( H ) );
tra:=One(H);
# Now go back through the factors by all groups in the elementary abelian
# series.
for step in [ step + 1 .. Length( eas ) ] do
Kp := Lp;
L := eas[ step ];
Ldep:=indstep[step];
Lp := InducedPcgs(home, L );
N := Kp mod Lp;
#SetFilterObj( N, IsPcgs );
allcent:=cent(home,home,N,Ldep);
if allcent=false then
nexpo:=LinearActionLayer(home{[1..indstep[step-1]-1]},N);
fi;
if not IsIdenticalObj( G, H ) then
KcapH := LcapH;
LcapH := NormalIntersectionPcgs( home, Hp, Lp );
N!.capH := KcapH mod LcapH;
else
N!.capH := N;
fi;
cl.candidates := cl.representative;
if allcent
or cent(home,cl.centralizerpcgs, N, Ldep) then
cl := CentralStepClEANS( home,G, H, N, cl,true )[1];
else
cl := GeneralStepClEANS( home,G, H, N,nexpo, cl,true )[1];
fi;
tra := tra * cl.operator;
if IsModuloPcgs(cl.cengen) then
cl.centralizerpcgs:=cl.cengen;
else
cl.centralizerpcgs:=InducedPcgsByPcSequenceNC(home,cl.cengen);
fi;
od;
if not IsBound(cl.centralizer) then
cl.centralizer:=SubgroupByPcgs(G,cl.centralizerpcgs);
fi;
cl:=ConjugateSubgroup( cl.centralizer, tra ^ -1 );
Assert(2,ForAll(GeneratorsOfGroup(cl),i->Comm(elm,i) in NT));
Assert(2,IsSubset(G,cl));
return cl;
end);
InstallMethod(CentralizerModulo,"group centralizer via generators",
IsFamFamFam,[IsGroup and CanEasilyComputePcgs, IsGroup and
CanEasilyComputePcgs, IsGroup],0,
function(G,NT,U)
local i,P;
P:=Parent(G);
for i in GeneratorsOfGroup(U) do
G:=CentralizerModulo(G,NT,i);
od;
G:=AsSubgroup(P,G);
return G;
end);
# enforce solvability check.
RedispatchOnCondition(CentralizerModulo,true,[IsGroup,IsGroup,IsObject],
[IsGroup and IsSolvableGroup,IsGroup and IsSolvableGroup,IsObject],0);
#############################################################################
##
#F ElementaryAbelianSeries( <list> )
##
InstallOtherMethod( ElementaryAbelianSeries,"list of pcgs computable groups",
true,[IsList and IsFinite],
1, # there is a generic groups function with value 0
function( S )
local home,i, N, O, I, E, L;
if Length(S)=0 or not CanEasilyComputePcgs(S[1]) then
TryNextMethod();
fi;
# typecheck arguments
if 1 < Size(Last(S)) then
S := ShallowCopy( S );
Add( S, TrivialSubgroup(S[1]) );
fi;
# start with the elementary series of the first group of <S>
L := ElementaryAbelianSeries( S[ 1 ] );
# enforce the same parent for 'HomePcgs' purposes.
home:=HomePcgs(S[1]);
N := [ S[ 1 ] ];
for i in [ 2 .. Length( S ) - 1 ] do
O := L;
L := [ S[ i ] ];
for E in O do
I := IntersectionSumPcgs(home, InducedPcgs(home,E),
InducedPcgs(home,S[ i ]) );
I.sum:=SubgroupByPcgs(S[1],I.sum);
I.intersection:=SubgroupByPcgs(S[1],I.intersection);
if not I.sum in N then
Add( N, I.sum );
fi;
if not I.intersection in L then
Add( L, I.intersection );
fi;
od;
od;
for E in L do
if not E in N then
Add( N, E );
fi;
od;
return N;
end);
#############################################################################
##
#M \<(G,H) . . . . . . . . . . . . . . . . . comparison of pc groups by CGS
##
InstallMethod(\<,"cgs comparison",IsIdenticalObj,[IsPcGroup,IsPcGroup],0,
function( G, H )
return Reversed( CanonicalPcgsWrtFamilyPcgs(G) )
< Reversed( CanonicalPcgsWrtFamilyPcgs(H) );
end);
#############################################################################
##
#F GapInputPcGroup( <U>, <name> ) . . . . . . . . . . . . gap input string
##
## Compute the pc-presentation for a finite polycyclic group as gap input.
## Return this input as string. The group will be named <name>,the
## generators "g<i>".
##
InstallGlobalFunction( GapInputPcGroup, function(U,name)
local gens,
wordString,
newLines,
lines,
ne,
i,j;
# <lines> will hold the various lines of the input for gap,they are
# concatenated later.
lines:=[];
# Get the generators for the group <U>.
gens:=InducedPcgsWrtHomePcgs(U);
# Initialize the group and the generators.
Add(lines,name);
Add(lines,":=function()\nlocal ");
for i in [1 .. Length(gens)] do
Add(lines,"g");
Add(lines,String(i));
Add(lines,",");
od;
Add(lines,"r,f,g,rws,x;\n");
Add(lines,"f:=FreeGroup(IsSyllableWordsFamily,");
Add(lines,String(Length(gens)));
Add(lines,");\ng:=GeneratorsOfGroup(f);\n");
for i in [1 .. Length(gens)] do
Add(lines,"g" );
Add(lines,String(i) );
Add(lines,":=g[");
Add(lines,String(i) );
Add(lines,"];\n" );
od;
Add(lines,"rws:=SingleCollector(f,");
Add(lines,String(List(gens,i->RelativeOrderOfPcElement(gens,i))));
Add(lines,");\n");
Add(lines,"r:=[\n");
# A function will yield the string for a word.
wordString:=function(a)
local k,l,list,str,count;
list:=ExponentsOfPcElement(gens,a);
k:=1;
while k <= Length(list) and list[k] = 0 do k:=k + 1; od;
if k > Length(list) then return "IdWord"; fi;
if list[k] <> 1 then
str:=Concatenation("g",String(k),"^",
String(list[k]));
else
str:=Concatenation("g",String(k));
fi;
count:=Length(str) + 15;
for l in [k + 1 .. Length(list)] do
if count > 60 then
str :=Concatenation(str,"\n ");
count:=4;
fi;
count:=count - Length(str);
if list[l] > 1 then
str:=Concatenation(str,"*g",String(l),"^",
String(list[l]));
elif list[l] = 1 then
str:=Concatenation(str,"*g",String(l));
fi;
count:=count + Length(str);
od;
return str;
end;
# Add the power presentation part.
for i in [1 .. Length(gens)] do
ne:=gens[i]^RelativeOrderOfPcElement(gens,gens[i]);
if ne<>One(U) then
Add(lines,Concatenation("[",String(i),",",
wordString(ne),"]"));
if i<Length(gens) then
Add(lines,",\n");
else
Add(lines,"\n");
fi;
fi;
od;
Add(lines,"];\nfor x in r do SetPower(rws,x[1],x[2]);od;\n");
Add(lines,"r:=[\n");
# Add the commutator presentation part.
for i in [1 .. Length(gens) - 1] do
for j in [i + 1 .. Length(gens)] do
ne:=Comm(gens[j],gens[i]);
if ne<>One(U) then
if i <> Length(gens) - 1 or j <> i + 1 then
Add(lines,Concatenation("[",String(j),",",String(i),",",
wordString(ne),"],\n"));
else
Add(lines,Concatenation("[",String(j),",",String(i),",",
wordString(ne),"]\n"));
fi;
fi;
od;
od;
Add(lines,"];\nfor x in r do SetCommutator(rws,x[1],x[2],x[3]);od;\n");
Add(lines,"return GroupByRwsNC(rws);\n");
Add(lines,"end;\n");
Add(lines,name);
Add(lines,":=");
Add(lines,name);
Add(lines,"();\n");
Add(lines,"Print(\"#I A group of order \",Size(");
Add(lines,name);
Add(lines,"),\" has been defined.\\n\");\n");
Add(lines,"Print(\"#I It is called ");
Add(lines,name);
Add(lines,"\\n\");\n");
# Concatenate all lines and return.
while Length(lines) > 1 do
if Length(lines) mod 2 = 1 then
Add(lines,"");
fi;
newLines:=[];
for i in [1 .. Length(lines) / 2] do
newLines[i]:=Concatenation(lines[2*i-1],lines[2*i]);
od;
lines:=newLines;
od;
IsString(lines[1]);
return lines[1];
end );
#############################################################################
##
#F PrintPcPresentation( <grp>, <commBool> )
##
## Display the pc relations of a pc group.
## If <commBool> is true, then the commutator presentation is printed,
## otherwise the power presentation.
## Trivial commutators / powers are not printed.
## The generators are named "g<i>".
## The returned boolean indicates if there are commuting generators.
##
InstallGlobalFunction( PrintPcPresentation, function(G, commBool)
local pcgs, n, F, gens, i, pis, exp, t, h, commPower, j, trivialCommutators;
pcgs:=Pcgs(G);
n:=Length(pcgs);
F := FreeGroup( n, "g" );
gens := GeneratorsOfGroup( F );
pis := RelativeOrders( pcgs );
# compute the orders of the pc-generators
for i in [1..n] do
exp := ExponentsOfRelativePower( pcgs, i ){[i+1..n]};
t := One( F );
for h in [i+1..n] do
t := t * gens[h]^exp[h-i];
od;
if IsOne( t ) then
t := "id";
fi;
Print(gens[i], "^", pis[i], " = ", t, "\n");
od;
# compute the commutators / conjugation
# of all pairs of pc-generators
trivialCommutators := false;
for i in [1..n] do
for j in [i+1..n] do
if pcgs[j] * pcgs[i] = pcgs[i] * pcgs[j] then
trivialCommutators := true;
continue;
fi;
if commBool then
commPower := Comm( pcgs[j], pcgs[i] );
else
commPower := pcgs[j]^pcgs[i];
fi;
exp := ExponentsOfPcElement( pcgs, commPower ){[i+1..n]};
t := One( F );
for h in [i+1..n] do
t := t * gens[h]^exp[h-i];
od;
if commBool then
Print("[", gens[j], ",", gens[i] , "]");
else
Print(gens[j], "^", gens[i]);
fi;
Print(" = ", t, "\n");
od;
od;
return trivialCommutators;
end );
#############################################################################
##
#M Display( <grp> )
##
InstallMethod( Display,
"for a pc group",
[ IsPcGroup ],
function( G )
local n, trivialCommutators;
if IsTrivial(G) then
Print("trivial pc-group\n");
return;
fi;
n := Size(Pcgs(G));
if IsOne(n) then
Print("cyclic pc-group with 1 pc-generator and the relation:\n");
else
Print("pc-group with ", Size(Pcgs(G)), " pc-generators and relations:\n");
fi;
trivialCommutators := PrintPcPresentation( G, false );
if IsAbelian(G) then
Print("all generators commute, the groups is abelian\n");
elif trivialCommutators then
Print("all other pairs of generators commute\n");
fi;
end );
#############################################################################
##
#M Enumerator( <G> ) . . . . . . . . . . . . . . . . . . enumerator by pcgs
##
InstallMethod( Enumerator,"finite pc computable groups",true,
[ IsGroup and CanEasilyComputePcgs and IsFinite ], 0,
G -> EnumeratorByPcgs( Pcgs( G ) ) );
#############################################################################
##
#M KnowsHowToDecompose( <G>, <gens> )
##
InstallMethod( KnowsHowToDecompose,
"pc group and generators: always true",
IsIdenticalObj,
[ IsPcGroup, IsList ], 0,
ReturnTrue);
#############################################################################
##
#F CanonicalSubgroupRepresentativePcGroup( <G>, <U> )
##
InstallGlobalFunction( CanonicalSubgroupRepresentativePcGroup,
function(G,U)
local e, # EAS
pcgs, # himself
iso, # isomorphism to EAS group
start, # index of largest abelian quotient
i, # loop
m, # e[i+1]
pcgsm, # pcgs(m)
mpcgs, # pcgs mod pcgsm
V, # canon. rep
fv, # <V,m>
fvgens, # gens(fv)
no, # its normalizer
orb, # orbit
o, # orb index
nno, # growing normalizer
min,
minrep, # minimum indicator
# p, # orbit pos.
one, # 1
abc, # abelian case indicator
nopcgs, #pcgs(no)
te, # transversal exponents
opfun, # operation function
ce; # conj. elm
if not IsSubgroup(G,U) then
Error("#W CSR Closure\n");
G:=Subgroup(Parent(G),Concatenation(GeneratorsOfGroup(G),
GeneratorsOfGroup(U)));
fi;
# compute a pcgs fitting the EAS
pcgs:=PcgsChiefSeries(G);
e:=ChiefNormalSeriesByPcgs(pcgs);
if not IsBound(G!.chiefSeriesPcgsIsFamilyInduced) then
# test whether pcgs is family induced
m:=List(pcgs,i->ExponentsOfPcElement(FamilyPcgs(G),i));
G!.chiefSeriesPcgsIsFamilyInduced:=
ForAll(m,i->Number(i,j->j<>0)=1) and ForAll(m,i->Number(i,j->j=1)=1)
and m=Reversed(Set(m));
if not G!.chiefSeriesPcgsIsFamilyInduced then
# compute isom. &c.
V:=PcGroupWithPcgs(pcgs);
iso:=GroupHomomorphismByImagesNC(G,V,pcgs,FamilyPcgs(V));
G!.isomorphismChiefSeries:=iso;
G!.isomorphismChiefSeriesPcgs:=FamilyPcgs(Image(iso));
G!.isomorphismChiefSeriesPcgsSeries:=List(e,i->Image(iso,i));
fi;
fi;
if not G!.chiefSeriesPcgsIsFamilyInduced then
iso:=G!.isomorphismChiefSeries;
pcgs:=G!.isomorphismChiefSeriesPcgs;
e:=G!.isomorphismChiefSeriesPcgsSeries;
U:=Image(iso,U);
G:=Image(iso);
else
iso:=false;
fi;
#pcgs:=Concatenation(List([1..Length(e)-1],i->
# InducedPcgs(home,e[i]) mod InducedPcgs(home,e[i+1])));
#pcgs:=PcgsByPcSequence(ElementsFamily(FamilyObj(G)),pcgs);
##AH evtl. noch neue Gruppe
# find the largest abelian quotient
start:=2;
while start<Length(e) and HasAbelianFactorGroup(G,e[start+1]) do
start:=start+1;
od;
#initialize
V:=U;
one:=One(G);
ce:=One(G);
no:=G;
for i in [start..Length(e)-1] do
# lift from G/e[i] to G/e[i+1]
m:=e[i+1];
pcgsm:=InducedPcgs(pcgs,m);
mpcgs:=pcgs mod pcgsm;
# map v,no
#fv:=ClosureGroup(m,V);
#img:=CanonicalPcgs(InducedPcgsByGenerators(pcgs,GeneratorsOfGroup(fv)));
# if true then
nopcgs:=InducedPcgs(pcgs,no);
fvgens:=GeneratorsOfGroup(V);
if true then
min:=CorrespondingGeneratorsByModuloPcgs(mpcgs,fvgens);
#UU:=ShallowCopy(min);
# NORMALIZE_IGS(mpcgs,min);
#if UU<>min then
# Error("hier1");
#fi;
# trim m-part
min:=List(min,i->CanonicalPcElement(pcgsm,i));
# operation function: operate on the cgs modulo m
opfun:=function(u,e)
u:=CorrespondingGeneratorsByModuloPcgs(mpcgs,List(u,j->j^e));
#UU:=ShallowCopy(u);
# NORMALIZE_IGS(mpcgs,u);
#if UU<>u then
# Error("hier2");
#fi;
# trim m-part
u:=List(u,i->CanonicalPcElement(pcgsm,i));
return u;
end;
else
min:=fv;
opfun:=OnPoints;
fi;
# this function computes the orbit in a well-defined order that permits
# to find a transversal cheaply
orb:=Pcgs_OrbitStabilizer(nopcgs,false,min,nopcgs,opfun);
nno:=orb.stabpcgs;
abc:=orb.lengths;
orb:=orb.orbit;
#if Length(orb)<>Index(no,Normalizer(no,fv)) then
# Error("len!");
#fi;
# determine minimal conjugate
minrep:=one;
for o in [2..Length(orb)] do
if orb[o]<min then
min:=orb[o];
minrep:=o;
fi;
od;
# compute representative
if IsInt(minrep) then
te:=ListWithIdenticalEntries(Length(nopcgs),0);
o:=2;
while minrep<>1 do
while abc[o]>=minrep do
o:=o+1;
od;
te[o-1]:=-QuoInt(minrep-1,abc[o]);
minrep:=(minrep-1) mod abc[o]+1;
od;
te:=LinearCombinationPcgs(nopcgs,te)^-1;
if opfun(orb[1],te)<>min then
Error("wrong repres!");
fi;
minrep:=te;
fi;
#
#
# nno:=Normalizer(no,fv);
#
# rep:=RightTransversal(no,nno);
# #orb:=List(rep,i->CanonicalPcgs(InducedPcgs(pcgs,fv^i)));
#
# # try to cope with action on vector space (long orbit)
## abc:=false;
## if Index(fv,m)>1 and HasElementaryAbelianFactorGroup(fv,m) then
## nocl:=NormalClosure(no,fv);
## if HasElementaryAbelianFactorGroup(nocl,m) then
### abc:=true; # try el. ab. case
## fi;;
## fi;
#
# if abc then
# nocl:=InducedPcgs(pcgs,nocl) mod pcgsm;
# nopcgs:=InducedPcgs(pcgs,no) mod pcgsm;
# lop:=LinearActionLayer(Group(nopcgs),nocl); #matrices for action
# fvgens:=List(fvgens,i->ShallowCopy(
# ExponentsOfPcElement(nocl,i)*Z(RelativeOrders(nocl)[1])^0));
# TriangulizeMat(fvgens); # canonize
# min:=fvgens;
# minrep:=one;
# for o in rep do
# if o<>one then
# # matrix image of rep
# orb:=ExponentsOfPcElement(nopcgs,o);
# orb:=Product([1..Length(orb)],i->lop[i]^orb[i]);
# orb:=List(fvgens*orb,ShallowCopy);
# TriangulizeMat(orb);
# if orb<min then
# min:=orb;
# minrep:=o;
# fi;
# fi;
# od;
#
# else
# min:=CorrespondingGeneratorsByModuloPcgs(mpcgs,fvgens);
# NORMALIZE_IGS(mpcgs,min);
# minrep:=one;
# for o in rep do
# if o<>one then
# if Length(fvgens)=1 then
# orb:=fvgens[1]^o;
# orb:=orb^(1/LeadingExponentOfPcElement(mpcgs,orb)
# mod RelativeOrderOfPcElement(mpcgs,orb));
# orb:=[orb];
# else
# orb:=CorrespondingGeneratorsByModuloPcgs(mpcgs,List(fvgens,j->j^o));
# NORMALIZE_IGS(mpcgs,orb);
# fi;
# if orb<min then
# min:=orb;
# minrep:=o;
# fi;
# fi;
# od;
# fi;
# conjugate normalizer to new minimal one
no:=ClosureGroup(m,List(nno,i->i^minrep));
ce:=ce*minrep;
V:=V^minrep;
od;
if iso<>false then
V:=PreImage(iso,V);
no:=PreImage(iso,no);
ce:=PreImagesRepresentative(iso,ce);
fi;
return [V,no,ce];
end );
#############################################################################
##
#M ConjugacyClassSubgroups(<G>,<g>) . . . . . . . constructor for pc groups
## This method installs 'CanonicalSubgroupRepresentativePcGroup' as
## CanonicalRepresentativeDeterminator
##
InstallMethod(ConjugacyClassSubgroups,IsIdenticalObj,[IsPcGroup,IsPcGroup],0,
function(G,U)
local cl;
cl:=Objectify(NewType(CollectionsFamily(FamilyObj(G)),
IsConjugacyClassSubgroupsByStabilizerRep),rec());
SetActingDomain(cl,G);
SetRepresentative(cl,U);
SetFunctionAction(cl,OnPoints);
SetCanonicalRepresentativeDeterminatorOfExternalSet(cl,
CanonicalSubgroupRepresentativePcGroup);
return cl;
end);
InstallOtherMethod(RepresentativeActionOp,"pc group on subgroups",true,
[IsPcGroup,IsPcGroup,IsPcGroup,IsFunction],0,
function(G,U,V,f)
local c1,c2;
if f<>OnPoints or not (IsSubset(G,U) and IsSubset(G,V)) then
TryNextMethod();
fi;
if Size(U)<>Size(V) then
return fail;
fi;
c1:=CanonicalSubgroupRepresentativePcGroup(G,U);
c2:=CanonicalSubgroupRepresentativePcGroup(G,V);
if c1[1]<>c2[1] then
return fail;
fi;
return c1[3]/c2[3];
end);
#############################################################################
##
#F ChiefSeriesUnderAction( <U>, <G> )
##
InstallMethod( ChiefSeriesUnderAction,
"method for a pcgs computable group",
IsIdenticalObj,
[ IsGroup, IsGroup and CanEasilyComputePcgs ], 0,
function( U, G )
local home,e,ser,i,j,k,pcgs,mpcgs,op,m,cs,n;
home:=HomePcgs(G);
e:=ElementaryAbelianSeriesLargeSteps(G);
# make the series U-invariant
ser:=ShallowCopy(e);
e:=[G];
n:=G;
for i in [2..Length(ser)] do
# check whether we actually stepped down (or did the intersection
# already do it?
if Size(ser[i])<Size(n) then
if not IsNormal(U,ser[i]) then
# assuming the last was normal we intersect the conjugates and get a
# new normal with still ea. factor
ser[i]:=Core(U,ser[i]);
# intersect the rest of the series.
for j in [i+1..Length(ser)-1] do
ser[j]:=Intersection(ser[i],ser[j]);
od;
fi;
Add(e,ser[i]);
n:=ser[i];
fi;
od;
ser:=[G];
for i in [2..Length(e)] do
Info(InfoPcGroup,1,"Step ",i,": ",Index(e[i-1],e[i]));
if IsPrimeInt(Index(e[i-1],e[i])) then
Add(ser,e[i]);
else
pcgs:=InducedPcgs(home,e[i-1]);
mpcgs:=pcgs mod InducedPcgs(home,e[i]);
op:=LinearActionLayer(U,GeneratorsOfGroup(U),mpcgs);
if ForAll(op,IsOne) then
m:=op[1]; # identity
cs:=List([0..Length(m)],x->m{[Length(m)+1-x..Length(m)]});
else
m:=GModuleByMats(op,GF(RelativeOrderOfPcElement(mpcgs,mpcgs[1])));
cs:=MTX.BasesCompositionSeries(m);
fi;
Sort(cs,function(a,b) return Length(a)>Length(b);end);
cs:=cs{[2..Length(cs)]};
Info(InfoPcGroup,2,Length(cs)-1," compositionFactors");
for j in cs do
n:=e[i];
for k in j do
n:=ClosureGroup(n,PcElementByExponentsNC(mpcgs,List(k,IntFFE)));
od;
Add(ser,n);
od;
fi;
od;
return ser;
end);
InstallMethod(IsSimpleGroup,"for solvable groups",true,
[IsSolvableGroup],
# this is also better for permutation groups, so we increase the value to
# be above the value for `IsPermGroup'.
{} -> Maximum(RankFilter(IsSolvableGroup),
RankFilter(IsPermGroup)+1)
-RankFilter(IsSolvableGroup),
function(G)
return IsInt(Size(G)) and IsPrimeInt(Size(G));
end);
#############################################################################
##
#M ViewObj(<G>)
##
InstallMethod(ViewObj,"pc group",true,[IsPcGroup],0,
function(G)
local nrgens;
nrgens := Length(GeneratorsOfGroup(G));
if (not HasParent(G)) or
nrgens*Length(GeneratorsOfGroup(Parent(G)))
/ GAPInfo.ViewLength > 50 then
Print("<pc group");
if HasSize(G) then
Print(" of size ",Size(G));
fi;
Print(" with ", Pluralize(nrgens, "generator"), ">");
else
Print("Group(");
ViewObj(GeneratorsOfGroup(G));
Print(")");
fi;
end);
#############################################################################
##
#M CanEasilyComputePcgs( <pcgrp> ) . . . . . . . . . . . . . . . . pc group
##
InstallTrueMethod( CanEasilyComputePcgs, IsPcGroup );
# InstallTrueMethod( CanEasilyComputePcgs, HasPcgs );
# we cannot guarantee that computations with any pcgs is efficient
InstallTrueMethod( CanEasilyComputePcgs, IsGroup and HasFamilyPcgs );
#############################################################################
##
#M CanEasilyTestMembership
##
# InstallTrueMethod(CanEasilyTestMembership,CanEasilyComputePcgs);
# we cannot test membership using a pcgs
# InstallTrueMethod(CanComputeSize, CanEasilyComputePcgs); #unnecessary
#############################################################################
##
#M IsSolvableGroup
##
InstallTrueMethod(IsSolvableGroup, CanEasilyComputePcgs);
#############################################################################
##
#M CanComputeSizeAnySubgroup
##
InstallTrueMethod( CanComputeSizeAnySubgroup, CanEasilyComputePcgs );
#############################################################################
##
#M CanEasilyComputePcgs( <grp> ) . . . . . . . . . subset or factor relation
##
## Since factor groups might be in a different representation,
## they should *not* inherit `CanEasilyComputePcgs' automatically.
##
#InstallSubsetMaintenance( CanEasilyComputePcgs,
# IsGroup and CanEasilyComputePcgs, IsGroup );
#############################################################################
##
#M IsConjugatorIsomorphism( <hom> )
##
InstallMethod( IsConjugatorIsomorphism,
"for a pc group general mapping",
true,
[ IsGroupGeneralMapping ], 1,
# There is no filter to test whether source and range of a homomorphism
# are pc groups.
# So we have to test explicitly and make this method
# higher ranking than the default one in `ghom.gi'.
function( hom )
local s, r, G, genss, rep;
s:= Source( hom );
if not IsPcGroup( s ) then
TryNextMethod();
elif not ( IsGroupHomomorphism( hom ) and IsBijective( hom ) ) then
return false;
elif IsEndoGeneralMapping( hom ) and IsInnerAutomorphism( hom ) then
return true;
fi;
r:= Range( hom );
# Check whether source and range are in the same family.
if FamilyObj( s ) <> FamilyObj( r ) then
--> --------------------
--> maximum size reached
--> --------------------
[ Original von:0.72Diese Quellcodebibliothek enthält Beispiele in vielen Programmiersprachen.
Man kann per Verzeichnistruktur darin navigieren.
Der Code wird farblich markiert angezeigt.
Datei übertragen
]
|
