|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Volkmar Felsch, Alexander Hulpke.
##
## 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 finitely presented groups (fp groups).
## Methods for subgroups of fp groups can also be found in `sgpres.gi'.
##
## 1. methods for elements of f.p. groups
## 2. methods for f.p. groups
##
#############################################################################
##
## 1. methods for elements of f.p. groups
##
#############################################################################
##
#M ElementOfFpGroup( <fam>, <elm> )
##
InstallMethod( ElementOfFpGroup,
"for a family of f.p. group elements, and an assoc. word",
true,
[ IsElementOfFpGroupFamily, IsAssocWordWithInverse ],
0,
function( fam, elm )
return Objectify( fam!.defaultType, [ Immutable( elm ) ] );
end );
#############################################################################
##
#M PrintObj( <elm> ) . . . . . . . for packed word in default representation
##
InstallMethod( PrintObj,"for an element of an f.p. group (default repres.)",
true, [ IsElementOfFpGroup and IsPackedElementDefaultRep ], 0,
function( obj )
Print( obj![1] );
end );
#############################################################################
##
#M ViewObj( <elm> ) . . . . . . . for packed word in default representation
##
InstallMethod( ViewObj,"for an element of an f.p. group (default repres.)",
true, [ IsElementOfFpGroup and IsPackedElementDefaultRep ],0,
function( obj )
View( obj![1] );
end );
#############################################################################
##
#M String( <elm> ) . . . . . . . for packed word in default representation
##
InstallMethod( String,"for an element of an f.p. group (default repres.)",
true, [ IsElementOfFpGroup and IsPackedElementDefaultRep ],0,
function( obj )
return String( obj![1] );
end );
#############################################################################
##
#M UnderlyingElement( <elm> ) . . . . . . . . . . for element of f.p. group
##
InstallMethod( UnderlyingElement,
"for an element of an f.p. group (default repres.)",
true,
[ IsElementOfFpGroup and IsPackedElementDefaultRep ],
0,
obj -> obj![1] );
#############################################################################
##
#M ExtRepOfObj( <elm> ) . . . . . . . . . . . . . for element of f.p. group
##
InstallMethod( ExtRepOfObj,
"for an element of an f.p. group (default repres.)",
true,
[ IsElementOfFpGroup and IsPackedElementDefaultRep ],
0,
obj -> ExtRepOfObj( obj![1] ) );
InstallOtherMethod( Length,
"for an element of an f.p. group (default repres.)", true,
[ IsElementOfFpGroup and IsPackedElementDefaultRep ],0,
x->Length(UnderlyingElement(x)));
InstallOtherMethod(Subword,"for an element of an f.p. group (default repres.)",true,
[ IsElementOfFpGroup and IsPackedElementDefaultRep, IsInt, IsInt ],0,
function(word,a,b)
return ElementOfFpGroup(FamilyObj(word),Subword(UnderlyingElement(word),a,b));
end);
#############################################################################
##
#M InverseOp( <elm> ) . . . . . . . . . . . . . . for element of f.p. group
##
InstallMethod( InverseOp, "for an element of an f.p. group", true,
[ IsElementOfFpGroup ],0,
function(obj)
local fam,w;
fam:= FamilyObj( obj );
w:=Inverse(UnderlyingElement(obj));
if HasFpElementNFFunction(fam) and
IsBound(fam!.reduce) and fam!.reduce=true then
w:=FpElementNFFunction(fam)(w);
fi;
return ElementOfFpGroup( fam,w);
end );
#############################################################################
##
#M One( <fam> ) . . . . . . . . . . . . . for family of f.p. group elements
##
InstallOtherMethod( One,
"for a family of f.p. group elements",
true,
[ IsElementOfFpGroupFamily ],
0,
fam -> ElementOfFpGroup( fam, One( fam!.freeGroup ) ) );
#############################################################################
##
#M One( <elm> ) . . . . . . . . . . . . . . . . . for element of f.p. group
##
InstallMethod( One, "for an f.p. group element", true, [ IsElementOfFpGroup ],
0, obj -> One( FamilyObj( obj ) ) );
# a^0 calls OneOp, so we have to catch this as well.
InstallMethod( OneOp, "for an f.p. group element", true,[IsElementOfFpGroup ],
0, obj -> One( FamilyObj( obj ) ) );
#############################################################################
##
#M \*( <elm1>, <elm2> ) . . . . . . . . . for two elements of a f.p. group
##
InstallMethod( \*, "for two f.p. group elements",
IsIdenticalObj, [ IsElementOfFpGroup, IsElementOfFpGroup ], 0,
function( left, right )
local fam,w;
fam:= FamilyObj( left );
w:=UnderlyingElement(left)*UnderlyingElement(right);
if HasFpElementNFFunction(fam) and
IsBound(fam!.reduce) and fam!.reduce=true then
w:=FpElementNFFunction(fam)(w);
fi;
return ElementOfFpGroup( fam,w);
end );
#############################################################################
##
#M \=( <elm1>, <elm2> ) . . . . . . . . . for two elements of a f.p. group
##
InstallMethod( \=, "for two f.p. group elements", IsIdenticalObj,
[ IsElementOfFpGroup, IsElementOfFpGroup ],0,
# this is the only method that may ever be called!
function( left, right )
if UnderlyingElement(left)=UnderlyingElement(right) then
return true;
fi;
return FpElmEqualityMethod(FamilyObj(left))(left,right);
end );
#############################################################################
##
#M \<( <elm1>, <elm2> ) . . . . . . . . . for two elements of a f.p. group
##
InstallMethod( \<, "for two f.p. group elements", IsIdenticalObj,
[ IsElementOfFpGroup, IsElementOfFpGroup ],0,
# this is the only method that may ever be called!
function( left, right )
return FpElmComparisonMethod(FamilyObj(left))(left,right);
end );
InstallMethod(FPFaithHom,"try perm or pc hom",true,[IsFamily],0,
function( fam )
local hom,gp,f;
gp:=CollectionsFamily(fam)!.wholeGroup;
if HasIsFinite(gp) and not IsFinite(gp) then
return fail;
fi;
if HasIsomorphismPermGroup(gp) then return IsomorphismPermGroup(gp); fi;
if HasIsomorphismPcGroup(gp) then return IsomorphismPcGroup(gp); fi;
if HasSize(gp) then
f:=Factors(Size(gp));
if Length(Set(f))=1 then
SetIsPGroup(gp,true);
SetPrimePGroup(gp,f[1]);
elif Length(Set(f))=2 then
SetIsSolvableGroup(gp,true);
fi;
fi;
if HasIsPGroup(gp) and IsPGroup(gp) then
if Size(gp)=1 then
# special case trivial group
hom:=GroupHomomorphismByImagesNC(gp,Group(()),
GeneratorsOfGroup(gp),
List(GeneratorsOfGroup(gp),x->()));
SetEpimorphismFromFreeGroup(Image(hom),
GroupHomomorphismByImagesNC(FreeGroupOfFpGroup(gp),Image(hom),
FreeGeneratorsOfFpGroup(gp),
List(GeneratorsOfGroup(gp),x->Image(hom,x))));
return hom;
fi;
# nilpotent
f:=Factors(Size(gp));
hom:=EpimorphismPGroup(gp,f[1],Length(f));
elif HasIsSolvableGroup(gp) and IsSolvableGroup(gp) and
not (HasSize(gp) and Size(gp)=infinity) then
# solvable
hom:=EpimorphismSolvableQuotient(gp,Size(gp));
if Size(Image(hom))<>Size(gp) then
hom:=IsomorphismPermGroup(gp);
fi;
elif HasSize(gp) and Size(gp)<=10000 then
hom:=IsomorphismPermGroup(gp);
else
hom:=IsomorphismPermGroupOrFailFpGroup(gp);
fi;
if hom<>fail then
SetEpimorphismFromFreeGroup(Image(hom),
GroupHomomorphismByImagesNC(FreeGroupOfFpGroup(gp),Image(hom),
FreeGeneratorsOfFpGroup(gp),
List(GeneratorsOfGroup(gp),x->Image(hom,x))));
fi;
return hom;
end);
# the heuristics about what comparison methods to use for < and = are all
# concentrated in the following function to make the decision tree clear
# without having to rely on method ranking and to ensure that both < and =
# are treated the same way.
# Note that the total ordering used may depend on what is known about the
# group at the time of the first comparison. (See manual) (See manual) (See
# manual) (See manual)
BindGlobal( "MakeFpGroupCompMethod", function(CMP)
return function(fam)
local hom,f,com;
# if a normal form method is known, and it is not known to be crummy
if HasFpElementNFFunction(fam) and not IsBound(fam!.hascrudeFPENFF) then
f:=FpElementNFFunction(fam);
com:=x->f(UnderlyingElement(x));
# if we know a faithful representation, use it
elif HasFPFaithHom(fam) and
FPFaithHom(fam)<>fail then
hom:=FPFaithHom(fam);
com:=x->Image(hom,x);
# if neither is known, try a faithful representation (forcing its
# computation)
else
hom:= AttributeValueNotSet( FPFaithHom, fam );
if hom <> fail then
SetFPFaithHom( fam, hom );
com:=x->Image(hom,x);
#T Here one could try more elaborate things first
# otherwise force computation of a normal form.
else
f:=FpElementNFFunction(fam : CallFromMakeFpGroupCompMethod:= true);
com:=x->f(UnderlyingElement(x));
# Set the attribute value only *after* we are sure
# that the user has not interrupted the 'FpElementNFFunction' call.
SetFPFaithHom(fam, fail);
fi;
fi;
SetCanEasilyCompareElements(fam,true);
SetCanEasilySortElements(fam,true);
# now build the comparison function
return function(left,right)
return CMP(com(left),com(right));
end;
end;
end );
InstallMethod( FpElmEqualityMethod, "generic dispatcher",
true,[IsElementOfFpGroupFamily],0,MakeFpGroupCompMethod(\=));
InstallMethod( FpElmComparisonMethod, "generic dispatcher", true,
[IsElementOfFpGroupFamily],0,MakeFpGroupCompMethod(\<));
#############################################################################
##
#M Order <elm> )
##
InstallMethod( Order,"fp group element", [ IsElementOfFpGroup ],0,
function( elm )
local fam;
fam:=FamilyObj(elm);
if not HasFPFaithHom(fam) or FPFaithHom(fam)=fail then
TryNextMethod(); # don't try the hard way
fi;
return Order(Image(FPFaithHom(fam),elm));
end );
#############################################################################
##
#M Random <gp> )
##
InstallMethodWithRandomSource( Random,
"for a random source and an fp group",
[ IsRandomSource, IsSubgroupFpGroup and IsFinite],
function( rs, gp )
local fam,hom;
fam:=ElementsFamily(FamilyObj(gp));
hom:=FPFaithHom(fam);
if hom=fail then
TryNextMethod();
fi;
return PreImagesRepresentative(hom,Random(rs, Image(hom,gp)));
end );
#############################################################################
##
#M MappedWord( <x>, <gens1>, <gens2> )
##
InstallOtherMethod( MappedWord,"for fp group element",IsElmsCollsX,
[ IsPackedElementDefaultRep, IsElementOfFpGroupCollection and IsList,
IsList ],
0,
function(w,g,i)
# just defer to the underlying elements, then use the good method there
return MappedWord(UnderlyingElement(w),List(g,UnderlyingElement),i);
end);
#############################################################################
##
#M FpGrpMonSmgOfFpGrpMonSmgElement(<elm>)
##
InstallMethod(FpGrpMonSmgOfFpGrpMonSmgElement,
"for an element of an fp group", true,
[IsElementOfFpGroup], 0,
x -> CollectionsFamily(FamilyObj(x))!.wholeGroup);
#############################################################################
##
## 2. methods for f.p. groups
##
InstallGlobalFunction(IndexCosetTab,function(t)
if Length(t)=0 then
return 1;
else
return Length(t[1]);
fi;
end);
InstallMethod( PseudoRandom,"subgroups fp group: force generators",true,
[IsSubgroupFpGroup],0,
function( grp )
local gens, lim, n, r, l, w, a,la,f,up;
gens:=GeneratorsOfGroup(grp);
lim:=ValueOption("radius");
if lim=fail then
return Group_PseudoRandom(grp);
else
n:=2*Length(gens)-1;
if not IsBound(grp!.randomrange) or lim<>grp!.randlim then
# there are 1+(n+1)(1+n+n^2+...+n^(lim-1))=(n^lim*(n+1)-2)/(n-1)
# words of length up to lim in the free group on |gens| generators
if n=1 then
grp!.randomrange:=[1..Minimum(lim,2^28-1)];
f:=1;
else
up:=(n^lim*(n+1)-2)/(n-1);
if up>=2^28 then
f:=Int(up/2^28+1);
grp!.randomrange:=[1..2^28-1];
else
grp!.randomrange:=[1..up];
f:=1;
fi;
fi;
l:=[Int(1/f),Int((n+2)/f)];
a:=n+1;
for r in [2..lim+1] do
a:=a*n;
l[r+1]:=l[r]+Maximum(1,Int(a/f));
od;
grp!.randdist:=l;
grp!.randlim:=lim;
fi;
r:=Random(grp!.randomrange); # equal distribution of uncancelled words
l:=1;
while r>grp!.randdist[l] do
l:=l+1;
od;
l:=l-1;
# we multiply a lot here, but multiplication is cheap
w:=One(grp);
la:=false;
n:=n+1;
for r in [1..l] do
repeat
a:=Random(1,n);
until a<>la;
if a>Length(gens) then
la:=a-Length(gens);
w:=w/gens[la];
else
w:=w*gens[a];
la:=a+Length(gens);
fi;
od;
return w;
fi;
end);
#############################################################################
##
#M SubgroupOfWholeGroupByCosetTable(<fpfam>,<tab>)
##
InstallGlobalFunction(SubgroupOfWholeGroupByCosetTable,function(fam,tab)
local S;
S := Objectify(NewType(fam,IsGroup and IsAttributeStoringRep ),
rec() );
SetParent(S,fam!.wholeGroup);
SetCosetTableInWholeGroup(S,tab);
SetIndexInWholeGroup(S,IndexCosetTab(tab));
return S;
end);
#############################################################################
##
#M SubgroupOfWholeGroupByQuotientSubgroup(<fpfam>,<Q>,<U>)
##
InstallGlobalFunction(SubgroupOfWholeGroupByQuotientSubgroup,function(fam,Q,U)
local S;
# if (IsPermGroup(Q) or IsPcGroup(Q)) and Index(Q,U)=1 then
# # we get the full group
# S:=fam!.wholeGroup;
# if not IsBound(S!.quot) then # in case some algorithm wants it
# S!.quot:=GroupWithGenerators(List(GeneratorsOfGroup(S),i->()));
# S!.sub:=S!.quot;
# fi;
# return S;
# fi;
Assert(1,Length(GeneratorsOfGroup(Q))=Length(GeneratorsOfGroup(fam!.wholeGroup)));
S := Objectify(NewType(fam, IsGroup and
IsSubgroupOfWholeGroupByQuotientRep and IsAttributeStoringRep ),
rec(quot:=Q,sub:=U) );
SetParent(S,fam!.wholeGroup);
if CanComputeIndex(Q,U) and HasSize(Q) then
SetIndexInWholeGroup(S,IndexNC(Q,U));
if IndexNC(Q,U)<infinity then
SetIsFinitelyGeneratedGroup(S,true);
fi;
elif HasIsFinite(Q) and IsFinite(Q) then
SetIsFinitelyGeneratedGroup(S,true);
fi;
# transfer normality information
if (HasIsNormalInParent(U) and Q=Parent(U)) or
(HasGeneratorsOfGroup(U) and Length(GeneratorsOfGroup(U))=0) or
(CanComputeSize(U) and Size(U)=1) then
SetIsNormalInParent(S,true);
fi;
return S;
end);
BindGlobal("MakeNiceDirectQuots",function(G,H)
local hom, a, b;
if not ((IsPermGroup(G!.quot) and IsPermGroup(H!.quot)) or
(IsPcGroup(G!.quot) and IsPcGroup(H!.quot))) then
# force permrep
if not IsPermGroup(G!.quot) then
hom:=IsomorphismPermGroup(G!.quot);
a:=GroupWithGenerators(
List(GeneratorsOfGroup(G!.quot),i->Image(hom,i)),());
b:=Image(hom,G!.sub);
G:=SubgroupOfWholeGroupByQuotientSubgroup(FamilyObj(G),a,b);
fi;
if not IsPermGroup(H!.quot) then
hom:=IsomorphismPermGroup(H!.quot);
a:=GroupWithGenerators(
List(GeneratorsOfGroup(H!.quot),i->Image(hom,i)),());
b:=Image(hom,H!.sub);
H:=SubgroupOfWholeGroupByQuotientSubgroup(FamilyObj(H),a,b);
fi;
fi;
return [G,H];
end);
InstallGlobalFunction(TracedCosetFpGroup,function(t,elm,p)
local i,j,e,pos,ex;
ex:=ExtRepOfObj(elm);
for i in [1,3..(Length(ex)-1)] do
e:=ex[i+1];
if e<0 then
pos:=2*ex[i];
e:=-e;
else
pos:=2*ex[i]-1;
fi;
for j in [1..e] do
p:=t[pos][p];
od;
od;
return p;
end);
#############################################################################
##
#M \in ( <elm>, <U> ) in subgroup of fp group
##
InstallMethod( \in, "subgroup of fp group", IsElmsColls,
[ IsMultiplicativeElementWithInverse, IsSubgroupFpGroup ], 0,
function(elm,U)
return TracedCosetFpGroup(CosetTableInWholeGroup(U),
UnderlyingElement(elm),1)=1;
end);
InstallMethod( \in, "subgroup of fp group by quotient rep", IsElmsColls,
[ IsMultiplicativeElementWithInverse,
IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep], 0,
function(elm,U)
# transfer elm in factor
elm:=UnderlyingElement(elm);
elm:=MappedWord(elm,FreeGeneratorsOfWholeGroup(U),
GeneratorsOfGroup(U!.quot));
return elm in U!.sub;
end);
#############################################################################
##
#M \=( <U>, <V> ) . . . . . . . . . for two subgroups of a f.p. group
##
InstallMethod( \=, "subgroups of fp group", IsIdenticalObj,
[ IsSubgroupFpGroup, IsSubgroupFpGroup ], 0,
function( left, right )
return IndexInWholeGroup(left)=IndexInWholeGroup(right)
and IsSubset(left,right) and IsSubset(right,left);
end );
#############################################################################
##
#M IsSubset( <U>, <V> ) . . . . . . . . . for two subgroups of a f.p. group
##
InstallMethod( IsSubset, "subgroups of fp group: test generators",
IsIdenticalObj,
[ IsSubgroupFpGroup, # don't use the `CanEasilyTestMembership' filter here
# as the generator list may be empty.
IsSubgroupFpGroup and HasGeneratorsOfGroup], 0,
function(left,right)
if Length(GeneratorsOfGroup(right))>0
and not CanEasilyTestMembership(left) then
TryNextMethod();
fi;
return ForAll(GeneratorsOfGroup(right),i->i in left);
end);
InstallMethod(IsSubset,"subgroups of fp group by quot. rep",IsIdenticalObj,
[ IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep,
IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep], 0,
function(G,H)
local A,B,U,V,W,E,F,map;
# trivial plausibility
if HasIndexInWholeGroup(G) and HasIndexInWholeGroup(H) and
IndexInWholeGroup(G)>IndexInWholeGroup(H) then
return false;
fi;
A:=G!.quot;
B:=H!.quot;
U:=G!.sub;
V:=H!.sub;
# are we represented in the same quotient?
if GeneratorsOfGroup(A)=GeneratorsOfGroup(B) then
# we are, compare simply in the quotient
return IsSubset(U,V);
fi;
# now we have to test ``subsetness'' in the subdirect product defined by
# the quotients. WLOG the whole group is this subdirect product S
# A | |S | B Let E<A and F<B be the normal subgroups
# | | | whose factors are glued together. We have
# E / / \ \ F E=(ker(S->B))->A
# / / \ \ F=(ker(S->A))->B
# \ /
# \ /
# Then G>H if and only if the following two conditions hold:
# 1) The image of G in B contains V.
# 2) G contains ker(S->B) (so with 1 it is sufficient, this is trivially
# necessary as H contains this kernel).
# This condition is fulfilled, if U>E
# To compute this, first note that F is generated (as normal subgroup) by
# the relators of A evaluated in the generators of B. This is the
# coKernel of a mapping A->B
if not IsTrivial(V) then
map:=GroupGeneralMappingByImagesNC(A,B,GeneratorsOfGroup(A),
GeneratorsOfGroup(B));
F:=CoKernelOfMultiplicativeGeneralMapping(map);
W:=ClosureGroup(F,
List(GeneratorsOfGroup(U),i->ImagesRepresentative(map,i)));
if not IsSubset(W,V) then
return false; # condition 1
fi;
fi;
map:=GroupGeneralMappingByImagesNC(B,A,GeneratorsOfGroup(B),
GeneratorsOfGroup(A));
E:=CoKernelOfMultiplicativeGeneralMapping(map);
return IsSubset(U,E);
end);
InstallMethod( IsSubset, "subgp fp group: via quotient rep", IsIdenticalObj,
[ IsSubgroupFpGroup, IsSubgroupFpGroup ], 0,
function(left,right)
return IsSubset(AsSubgroupOfWholeGroupByQuotient(left),
AsSubgroupOfWholeGroupByQuotient(right));
end);
InstallMethod( CanComputeIsSubset, "whole fp family group", IsIdenticalObj,
[ IsSubgroupFpGroup and IsWholeFamily, IsSubgroupFpGroup ], 0,
ReturnTrue);
InstallMethod(IsNormalOp,"subgroups of fp group by quot. rep in full fp grp.",
IsIdenticalObj, [ IsSubgroupFpGroup and IsWholeFamily,
IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep], 0,
function(G,H)
return IsNormal(H!.quot,H!.sub);
end);
InstallMethod(IsFinitelyGeneratedGroup,"subgroups of fp group",true,
[IsSubgroupFpGroup],0,
function(U)
local G;
G:=FamilyObj(U)!.wholeGroup;
if not IsFinitelyGeneratedGroup(G) then
TryNextMethod();
fi;
if CanComputeIndex(G,U) and Index(G,U)<infinity then
return true;
fi;
Info(InfoWarning,1,
"Forcing index computation to test whether subgroup is finitely generated"
);
if Index(G,U)<infinity then
return true;
fi;
TryNextMethod(); # give up
end);
#############################################################################
##
#M GeneratorsOfGroup( <F> ) . . . . . . . . . . . . . . . for a f.p. group
##
InstallMethod( GeneratorsOfGroup, "for whole family f.p. group", true,
[ IsSubgroupFpGroup and IsGroupOfFamily ], 0,
function( F )
local Fam;
Fam:= ElementsFamily( FamilyObj( F ) );
return List( FreeGeneratorsOfFpGroup( F ), g -> ElementOfFpGroup( Fam, g ) );
end );
#############################################################################
##
#M AbelianInvariants( <G> ) . . . . . . . . . . . . . . . . . for a fp group
##
InstallMethod( AbelianInvariants,
"for a finitely presented group",
true,
[ IsSubgroupFpGroup and IsGroupOfFamily ],
0,
function( G )
local mat, # relator matrix of <G>
gens, # generators of free group
genind, # their indices
row, # a row of <mat>
rel, # a relator of <G>
p, # position of <g> or its inverse in <gens>
i, # loop variable
word,
inv;
gens := FreeGeneratorsOfFpGroup( G );
genind:=List(gens,i->AbsInt(LetterRepAssocWord(i)[1]));
# handle groups with no relators
if IsEmpty( RelatorsOfFpGroup( G ) ) then
return [ 1 .. Length( gens ) ] * 0;
fi;
# make the relator matrix
mat := [];
for rel in RelatorsOfFpGroup( G ) do
row := [];
for i in [ 1 .. Length( gens ) ] do
row[i] := 0;
od;
#for i in [ 1 .. NrSyllables( rel ) ] do
# p := Position( genind, GeneratorSyllable(rel,i));
# row[p]:=row[p]+ExponentSyllable(rel,i);
#od;
word:=LetterRepAssocWord(rel);
for i in [1..Length(rel)] do
p:=Position(genind,AbsInt(word[i]));
row[p]:=row[p]+SignInt(word[i]);
od;
Add( mat, row );
od;
# diagonalize the matrix
DiagonalizeMat( Integers, mat );
# return the abelian invariants
inv:=AbelianInvariantsOfList( DiagonalOfMat( mat ) );
if 0 in inv then
SetSize(G,infinity);
elif Length(gens)=1 or (HasIsAbelian(G) and IsAbelian(G)) then
# abelian
SetSize(G,Product(inv));
fi;
return inv;
end );
#############################################################################
##
#M AbelianInvariants( <H> ) . . . . . . . . . . for a subgroup of a fp group
##
InstallMethod( AbelianInvariants,
"for a subgroup of a finitely presented group", true,
[ IsSubgroupFpGroup ], 0,
function(H)
local G,inv;
if IsGroupOfFamily(H) then
TryNextMethod();
fi;
# Get the whole group `G' of `H'.
G:= FamilyObj(H)!.wholeGroup;
# Call the global function for subgroups of f.p. groups.
inv:=AbelianInvariantsSubgroupFpGroup( G, H );
if 0 in inv then
SetSize(H,infinity);
elif HasIsAbelian(H) and IsAbelian(H) then
# abelian
SetSize(H,Product(inv));
fi;
return inv;
end );
#############################################################################
##
#M IsInfiniteAbelianizationGroup( <G> ) . . . . . . . . . . . for a fp group
##
BindGlobal("HasFullColumnRankIntMatDestructive",function( mat )
local n, rb, next, primes, mp, r, pm, ns, nns, j, p, i;
n:=Length(mat[1]);
if Length(mat)<n then
return false;
fi;
# first check modulo some primes
rb:=0;
next:=7;
primes:=[2,7,251];
for p in primes do
mp:=ImmutableMatrix(p,mat*Z(p)^0);
r:=RankMat(mp);
if rb>0 and r<>rb and next<250 then
next:=NextPrimeInt(next);
Add(primes,next);
fi;
rb:=Maximum(r,rb);
Info(InfoMatrix,2,"Rank modulo ",p,":",r);
if rb=n then
return true;
fi;
if p=251 then
pm:=125;
ns:=NullspaceMat(TransposedMat(mp));
nns:=[];
for i in ns do
r:=List(i,Int);
for j in [1..Length(r)] do
if r[j]>pm then r[j]:=r[j]-p;fi;
od;
if IsZero(mat*r) then
Info(InfoMatrix,2,"Kernel element modulo lifts!");
return false;
fi;
Add(nns,r);
od;
fi;
od;
if rb<n-1 then
# the modulo calculation gesses rank `rb'. If this is the rank, then rb+1
# columns should be dependent!
r:=[1..rb+1];
mp:=List(mat,x->x{r});
TriangulizeIntegerMat(mp);
if Number(mp,x->not IsZero(x))<=rb then
# we are missing full rank already in the first rb+1 columns
return false;
fi;
fi;
# it failed -- hard work
Info(InfoMatrix,2,"reduced calculation failed");
TriangulizeIntegerMat(mat);
return Number(mat,x->not IsZero(x))=n;
end);
InstallMethod( IsInfiniteAbelianizationGroup,
"for a finitely presented group",
true,
[ IsSubgroupFpGroup and IsGroupOfFamily ],
0,
function( G )
local mat, # relator matrix of <G>
gens, # generators of free group
genind, # their indices
row, # a row of <mat>
rel, # a relator of <G>
p, # position of <g> or its inverse in <gens>
i, # loop variable
word;
gens := FreeGeneratorsOfFpGroup( G );
genind:=List(gens,i->AbsInt(LetterRepAssocWord(i)[1]));
# handle groups with no relators
if IsEmpty( RelatorsOfFpGroup( G ) ) then
return Length(gens)>0;
fi;
# make the relator matrix
mat := [];
for rel in RelatorsOfFpGroup( G ) do
row := [];
for i in [ 1 .. Length( gens ) ] do
row[i] := 0;
od;
#for i in [ 1 .. NrSyllables( rel ) ] do
# p := Position( genind, GeneratorSyllable(rel,i));
# row[p]:=row[p]+ExponentSyllable(rel,i);
#od;
word:=LetterRepAssocWord(rel);
for i in [1..Length(rel)] do
p:=Position(genind,AbsInt(word[i]));
row[p]:=row[p]+SignInt(word[i]);
od;
Add( mat, row );
od;
if Length(mat)=0 then
return false;
fi;
if Length(mat)>=Length(mat[1]) then
if HasFullColumnRankIntMatDestructive(mat) then
return false;
fi;
fi;
SetSize(G,infinity);
return true;
end );
#############################################################################
##
#M IsInfiniteAbelianizationGroup( <H> ) . . . . for a subgroup of a fp group
##
InstallMethod( IsInfiniteAbelianizationGroup,
"for a subgroup of a finitely presented group", true,
[ IsSubgroupFpGroup ], 0,
function(H)
local G,mat;
if IsGroupOfFamily(H) then
TryNextMethod();
fi;
# Get the whole group `G' of `H'.
G:= FamilyObj(H)!.wholeGroup;
# Call the global function for subgroups of f.p. groups.
mat:=RelatorMatrixAbelianizedSubgroupRrs(G,H);
if Length(mat)=0 then
return false;
fi;
if Length(mat)>=Length(mat[1]) then
if HasFullColumnRankIntMatDestructive(mat) then
return false;
fi;
fi;
SetSize(G,infinity);
return true;
end);
# a free group has infinite abelianization if and only if it is non-trivial
InstallTrueMethod( IsInfiniteAbelianizationGroup, IsFreeGroup and IsNonTrivial );
InstallTrueMethod( HasIsInfiniteAbelianizationGroup, IsFreeGroup and IsTrivial );
#############################################################################
##
#M IsPerfectGroup( <H> )
##
InstallMethod( IsPerfectGroup,
"for a (subgroup of a) finitely presented group", true,
[ IsSubgroupFpGroup ], 0,
# for fp groups `AbelianInvariants' works.
G -> IsEmpty( AbelianInvariants( G ) ) );
#############################################################################
##
#M DerivedSubgroup( <G> ) . . . . . . . . . . . . . . . . . for a fp group
##
InstallMethod( DerivedSubgroup, "for a finitely presented group", true,
[ IsSubgroupFpGroup and IsGroupOfFamily ], 0,
function(G)
local hom,u;
hom:=MaximalAbelianQuotient(G);
if Size(Range(hom))=1 then
return G; # this is needed because the trivial quotient is represented
# as fp group on no generators
fi;
u:=PreImage(hom,TrivialSubgroup(Range(hom)));
SetIndexInWholeGroup(u,Size(Range(hom)));
if IsFreeGroup(G) and not IsAbelian(G) then
SetIsFinite(u,false);
SetIsFinitelyGeneratedGroup(u,false);
fi;
return u;
end);
InstallMethod( DerivedSubgroup, "subgroup of a finitely presented group", true,
[ IsSubgroupFpGroup ], 0,
function(G)
local iso,hom,u;
iso:=IsomorphismFpGroup(G);
hom:=MaximalAbelianQuotient(Range(iso));
if HasAbelianInvariants(Range(iso)) then
SetAbelianInvariants(G,AbelianInvariants(Range(iso)));
fi;
if HasIsAbelian(G) and IsAbelian(G) then
return TrivialSubgroup(G);
elif Size(Image(hom))=infinity then
# test a special case -- one generator
if Length(GeneratorsOfGroup(G))=1 then
SetIsAbelian(G,true);
return TrivialSubgroup(G);
fi;
Error("Derived subgroup has infinite index, cannot represent");
elif Size(Range(hom))=1 then
return G; # this is needed because the trivial quotient is represented
# as fp group on no generators
fi;
hom:=CompositionMapping(hom,iso);
u:=PreImage(hom,TrivialSubgroup(Range(hom)));
if HasIndexInWholeGroup(G) then
SetIndexInWholeGroup(u,IndexInWholeGroup(G)*Size(Range(hom)));
fi;
return u;
end);
#############################################################################
##
#M CosetTable( <G>, <H> ) . . . . coset table of a finitely presented group
##
InstallMethod( CosetTable,
"for finitely presented groups",
true,
[ IsSubgroupFpGroup and IsGroupOfFamily, IsSubgroupFpGroup ],
0,
function( G, H );
if G <> FamilyObj(H)!.wholeGroup then
Error( "<H> must be a subgroup of <G>" );
fi;
return CosetTableInWholeGroup(H);
end );
#############################################################################
##
#M CosetTableNormalClosure( <G>, <H> ) . . coset table of the normal closure
#M of a subgroup in a finitely presented group
##
InstallMethod( CosetTableNormalClosure,
"for finitely presented groups",
true,
[ IsSubgroupFpGroup and IsGroupOfFamily, IsSubgroupFpGroup ],
0,
function( G, H );
if G <> FamilyObj( H )!.wholeGroup then
Error( "<H> must be a subgroup of <G>" );
fi;
return CosetTableNormalClosureInWholeGroup( H );
end );
#############################################################################
##
#M CosetTableFromGensAndRels( <fgens>, <grels>, <fsgens> ) . . . . . . . . .
#M do a coset enumeration
##
## 'CosetTableFromGensAndRels' is the workhorse for computing a coset
## table of H in G where G is a finitley presented group, H is a subgroup of
## G, and G is the whole group of H. It applies a Felsch strategy Todd-
## Coxeter coset enumeration. The expected parameters are
##
## \beginitems
## fgens & generators of the free group F associated to G,
##
## grels & relators of G,
##
## fsgens & preimages of the subgroup generators of H in F.
## \enditems
##
## `CosetTableFromGensAndRels' processes two options (see
## chapter~"Options"):
## \beginitems
## `max' & The limit of the number of cosets to be defined. If the
## enumeration does not finish with this number of cosets, an error is
## raised and the user is asked whether she wants to continue
##
## `silent' & if set to `true' the algorithm will not rais the error
## mentioned under option `max' but silently return `fail'. This can be
## useful if an enumeration is only wanted unless it becomes too big.
## \enditems
InstallGlobalFunction( CosetTableFromGensAndRels,
function ( fgens, grels, fsgens )
Info( InfoFpGroup, 3, "CosetTableFromGensAndRels called:" );
# catch trivial subgroup generators
if ForAny(fsgens,i->Length(i)=0) then
fsgens:=Filtered(fsgens,i->Length(i)>0);
fi;
if Length(fgens)=0 then
return [];
fi;
# call the TC plugin. Option ensures no factorization takes place in printing
# (which can confuse the ACE interface).
return TCENUM.CosetTableFromGensAndRels(fgens,grels,fsgens:printnopowers:=true);
end);
# this function implements the library version of the Todd-Coxeter routine.
BindGlobal("GTC_CosetTableFromGensAndRels",function(arg)
local fgens,grels,fsgens,
next, prev, # next and previous coset on lists
firstFree, lastFree, # first and last free coset
firstDef, lastDef, # first and last defined coset
table, # columns in the table for gens
rels, # representatives of the relators
relsGen, # relators sorted by start generator
subgroup, # rows for the subgroup gens
i, gen, inv, # loop variables for generator
g, # loop variable for generator col
rel, # loop variables for relation
p, p1, p2, # generator position numbers
app, # arguments list for 'MakeConsequences'
limit, # limit of the table
maxlimit, # maximal size of the table
j, # integer variable
length, length2, # length of relator (times 2)
cols,
nums,
l,
nrdef, # number of defined cosets
nrmax, # maximal value of the above
nrdel, # number of deleted cosets
nrinf, # number for next information message
infstep,
silent, # do we want the algorithm to silently
# return `fail' if the algorithm did not
# finish in the permitted size?
TCEOnBreakMessage, # to provide a local OnBreakMessage
SavedOnBreakMessage; # the value of OnBreakMessage before
# this function was called
fgens:=arg[1];
grels:=arg[2];
fsgens:=arg[3];
# give some information
Info( InfoFpGroup, 2, " defined deleted alive maximal");
nrdef := 1;
nrmax := 1;
nrdel := 0;
# to give tidy instructions if one enters a break-loop
SavedOnBreakMessage := OnBreakMessage;
TCEOnBreakMessage := function(n)
Print( "type 'return;' if you want to continue with a new limit of ",
n, " cosets,\n",
"type 'quit;' if you want to quit the coset enumeration,\n",
"type 'maxlimit := 0; return;' in order to continue without a ",
"limit\n" );
OnBreakMessage := SavedOnBreakMessage;
end;
# initialize size of the table
maxlimit := ValueOption("max");
if maxlimit = fail or not (IsInt(maxlimit) or maxlimit=infinity) then
maxlimit := CosetTableDefaultMaxLimit;
fi;
infstep:=QuoInt(maxlimit,10);
nrinf := infstep;
limit := CosetTableDefaultLimit;
if limit > maxlimit and maxlimit > 0 then
limit := maxlimit;
fi;
silent := ValueOption("silent") = true;
# define one coset (1)
firstDef := 1; lastDef := 1;
firstFree := 2; lastFree := limit;
# make the lists that link together all the cosets
next := [ 2 .. limit + 1 ]; next[1] := 0; next[limit] := 0;
prev := [ 0 .. limit - 1 ]; prev[2] := 0;
# compute the representatives for the relators
rels := RelatorRepresentatives( grels );
# make the columns for the generators
table := [];
for gen in fgens do
g := ListWithIdenticalEntries( limit, 0 );
Add( table, g );
if not ( gen^2 in rels or gen^-2 in rels ) then
g := ListWithIdenticalEntries( limit, 0 );
fi;
Add( table, g );
od;
# make the rows for the relators and distribute over relsGen
relsGen := RelsSortedByStartGen( fgens, rels, table, true );
# make the rows for the subgroup generators
subgroup := [];
for rel in fsgens do
#T this code should use ExtRepOfObj -- its faster
# cope with SLP elms
if IsStraightLineProgElm(rel) then
rel:=EvalStraightLineProgElm(rel);
fi;
length := Length( rel );
if length>0 then
length2 := 2 * length;
nums := [ ]; nums[length2] := 0;
cols := [ ]; cols[length2] := 0;
# compute the lists.
i := 0; j := 0;
while i < length do
i := i + 1; j := j + 2;
gen := Subword( rel, i, i );
p := Position( fgens, gen );
if p = fail then
p := Position( fgens, gen^-1 );
p1 := 2 * p;
p2 := 2 * p - 1;
else
p1 := 2 * p - 1;
p2 := 2 * p;
fi;
nums[j] := p1; cols[j] := table[p1];
nums[j-1] := p2; cols[j-1] := table[p2];
od;
Add( subgroup, [ nums, cols ] );
fi;
od;
# make the structure that is passed to 'MakeConsequences'
app := [ table, next, prev, relsGen, subgroup ];
# we do not want minimal gaps to be marked in the coset table
app[12] := 0;
# run over all the cosets
while firstDef <> 0 do
# run through all the rows and look for undefined entries
for i in [ 1 .. Length( table ) ] do
gen := table[i];
if gen[firstDef] <= 0 then
inv := table[i + 2*(i mod 2) - 1];
# if necessary expand the table
if firstFree = 0 then
if 0 < maxlimit and maxlimit <= limit then
if silent then
if ValueOption("returntable")=true then
return table;
else
return fail;
fi;
fi;
maxlimit := Maximum(maxlimit*2,limit*2);
OnBreakMessage := function()
TCEOnBreakMessage(maxlimit);
end;
Error( "the coset enumeration has defined more ",
"than ", limit, " cosets\n");
fi;
next[2*limit] := 0;
prev[2*limit] := 2*limit-1;
for g in table do g[2*limit] := 0; od;
for l in [ limit+2 .. 2*limit-1 ] do
next[l] := l+1;
prev[l] := l-1;
for g in table do g[l] := 0; od;
od;
next[limit+1] := limit+2;
prev[limit+1] := 0;
for g in table do g[limit+1] := 0; od;
firstFree := limit+1;
limit := 2*limit;
lastFree := limit;
fi;
# update the debugging information
nrdef := nrdef + 1;
if nrmax <= firstFree then
nrmax := firstFree;
fi;
# define a new coset
gen[firstDef] := firstFree;
inv[firstFree] := firstDef;
next[lastDef] := firstFree;
prev[firstFree] := lastDef;
lastDef := firstFree;
firstFree := next[firstFree];
next[lastDef] := 0;
# set up the deduction queue and run over it until it's empty
app[6] := firstFree;
app[7] := lastFree;
app[8] := firstDef;
app[9] := lastDef;
app[10] := i;
app[11] := firstDef;
nrdel := nrdel + MakeConsequences( app );
firstFree := app[6];
lastFree := app[7];
firstDef := app[8];
lastDef := app[9];
# give some information
if nrinf <= nrdef+nrdel then
Info( InfoFpGroup, 3, "\t", nrdef, "\t", nrinf-nrdef,
"\t", 2*nrdef-nrinf, "\t", nrmax );
nrinf := ( Int(nrdef+nrdel)/infstep + 1 ) * infstep;
fi;
fi;
od;
firstDef := next[firstDef];
od;
Info( InfoFpGroup, 2, "\t", nrdef, "\t", nrdel, "\t", nrdef-nrdel, "\t",
nrmax );
# separate pairs of identical table columns.
for i in [ 1 .. Length( fgens ) ] do
if IsIdenticalObj( table[2*i-1], table[2*i] ) then
table[2*i] := StructuralCopy( table[2*i-1] );
fi;
od;
# standardize the table
StandardizeTable( table );
# return the table
return table;
end);
GAPTCENUM.CosetTableFromGensAndRels := GTC_CosetTableFromGensAndRels;
if IsHPCGAP then
MakeReadOnlyObj( GAPTCENUM );
fi;
#############################################################################
##
#M CosetTableInWholeGroup( <H> ) . . . . . . coset table of an fp subgroup
#M in its whole group
##
## is equivalent to `CosetTable( <G>, <H> )' where <G> is the (unique)
## finitely presented group such that <H> is a subgroup of <G>.
##
InstallMethod( TryCosetTableInWholeGroup,"for finitely presented groups",
true, [ IsSubgroupFpGroup ], 0,
function( H )
local G, # whole group of <H>
fgens, # generators of the free group F associated to G
grels, # relators of G
sgens, # subgroup generators of H
fsgens, # preimages of subgroup generators in F
T; # coset table
# do we know it already?
if HasCosetTableInWholeGroup(H) then
return CosetTableInWholeGroup(H);
fi;
# Get whole group <G> of <H>.
G := FamilyObj( H )!.wholeGroup;
# get some variables
fgens := FreeGeneratorsOfFpGroup( G );
grels := RelatorsOfFpGroup( G );
sgens := GeneratorsOfGroup( H );
fsgens := List( sgens, gen -> UnderlyingElement( gen ) );
# Construct the coset table of <G> by <H>.
T := CosetTableFromGensAndRels( fgens, grels, fsgens );
if T<>fail then
SetCosetTableInWholeGroup(H,T);
fi;
return T;
end );
InstallMethod( CosetTableInWholeGroup,"for finitely presented groups",
true, [ IsSubgroupFpGroup ], 0,
function( H )
# don't get trapped by a `silent' option lingering around.
return TryCosetTableInWholeGroup(H:silent:=false);
end );
InstallMethod( CosetTableInWholeGroup,"from augmented table Rrs",
true, [ IsSubgroupFpGroup and HasAugmentedCosetTableRrsInWholeGroup], 0,
function( H )
return AugmentedCosetTableRrsInWholeGroup(H).cosetTable;
end );
InstallMethod(CosetTableInWholeGroup,"ByQuoSubRep",true,
[IsSubgroupOfWholeGroupByQuotientRep],0,
function(G)
# construct coset table
return CosetTableBySubgroup(G!.quot,G!.sub);
end);
#############################################################################
##
#M CosetTableNormalClosureInWholeGroup( <H> ) . . . . . coset table of the
#M normal closure of an fp subgroup in its whole group
##
## is equivalent to `CosetTableNormalClosure( <G>, <H> )' where <G> is the
## (unique) finitely presented group such that <H> is a subgroup of <G>.
##
InstallMethod( CosetTableNormalClosureInWholeGroup,
"for finitely presented groups",
true, [ IsSubgroupFpGroup ], 0,
function( H )
local G, # whole group of H
F, # associated free group
grels, # relators of G
sgens, # subgroup generators of H
fsgens, # preimages of subgroup generators in F
krels, # relators of the normal closure N of H in G
K, # factor group of F isomorphic to G/N
T; # coset table
# do we know it already?
if HasCosetTableNormalClosureInWholeGroup( H ) then
T := CosetTableNormalClosureInWholeGroup( H );
else
# Get whole group G of H.
G := FamilyObj( H )!.wholeGroup;
# get some variables
F := FreeGroupOfFpGroup( G );
grels := RelatorsOfFpGroup( G );
sgens := GeneratorsOfGroup( H );
fsgens := List( sgens, gen -> UnderlyingElement( gen ) );
# construct a factor group K of F isomorphic to the factor group of G
# by the normal closure N of H.
krels := Concatenation( grels, fsgens );
K := F / krels;
# get the coset table of N in G by constructing the coset table of
# the trivial subgroup in K.
T := CosetTable( K, TrivialSubgroup( K ) );
Info( InfoFpGroup, 1, "index is ", IndexCosetTab(T) );
fi;
return T;
end );
#############################################################################
##
#F StandardizeTable( <table> [, <standard>] ) . . . standardize coset table
##
## standardizes a coset table.
##
InstallGlobalFunction( StandardizeTable, function( arg )
local standard, table;
# get the arguments
table := arg[1];
if Length( arg ) > 1 then
standard := arg[2];
else
standard := CosetTableStandard;
fi;
if standard <> "lenlex" and standard <> "semilenlex" then
Error( "unknown coset table standard" );
fi;
if standard = "lenlex" then
standard := 0;
else
standard := 1;
fi;
# call an appropriate kernel function which does the job
StandardizeTableC( table, standard );
end );
#############################################################################
##
#F StandardizeTable2( <table>, <table2> [, <standard>] ) . standardize ACT
##
## standardizes an augmented coset table.
##
InstallGlobalFunction( StandardizeTable2, function( arg )
local standard, table, table2;
# get the arguments
table := arg[1];
table2 := arg[2];
if Length( arg ) > 2 then
standard := arg[3];
else
standard := CosetTableStandard;
fi;
if standard <> "lenlex" and standard <> "semilenlex" then
Error( "unknown coset table standard" );
fi;
if standard = "lenlex" then
standard := 0;
else
standard := 1;
fi;
# call an appropriate kernel function which does the job
StandardizeTable2C( table, table2, standard );
end );
#############################################################################
##
#M Display( <G> ) . . . . . . . . . . . . . . . . . . . display an fp group
##
InstallMethod( Display,
"for finitely presented groups",
true,
[ IsSubgroupFpGroup and IsGroupOfFamily ],
0,
function( G )
local gens, # generators o the free group
rels, # relators of <G>
nrels, # number of relators
i; # loop variable
gens := FreeGeneratorsOfFpGroup( G );
rels := RelatorsOfFpGroup( G );
Print( "generators = ", gens, "\n" );
nrels := Length( rels );
Print( "relators = [" );
if nrels > 0 then
Print( "\n ", rels[1] );
for i in [ 2 .. nrels ] do
Print( ",\n ", rels[i] );
od;
fi;
Print( " ]\n" );
end );
#############################################################################
##
#F FactorGroupFpGroupByRels( <G>, <elts> )
##
## Returns the factor group G/N of G by the normal closure N of <elts> where
## <elts> is expected to be a list of elements of G.
##
InstallGlobalFunction( FactorGroupFpGroupByRels,
function( G, elts )
local F, # free group associated to G and to G/N
grels, # relators of G
words, # representative words in F for the elements in elts
rels; # relators of G/N
# get some local variables
F := FreeGroupOfFpGroup( G );
grels := RelatorsOfFpGroup( G );
words := List( elts, g -> UnderlyingElement( g ) );
# get relators for G/N
rels := Concatenation( grels, words );
# return the resulting factor group G/N
return F / rels;
end );
#############################################################################
##
#M FactorFreeGroupByRelators(<F>,<rels>) . factor of free group by relators
##
BindGlobal( "FactorFreeGroupByRelators", function( F, rels )
local G, fam, gens,typ;
# Create a new family.
fam := NewFamily( "FamilyElementsFpGroup", IsElementOfFpGroup );
# Create the default type for the elements.
fam!.defaultType := NewType( fam, IsPackedElementDefaultRep );
fam!.freeGroup := F;
fam!.relators := Immutable( rels );
typ:=IsSubgroupFpGroup and IsWholeFamily and IsAttributeStoringRep;
if IsFinitelyGeneratedGroup(F) then
typ:=typ and IsFinitelyGeneratedGroup;
fi;
# Create the group.
G := Objectify(
NewType( CollectionsFamily( fam ), typ ), rec() );
# Mark <G> to be the 'whole group' of its later subgroups.
FamilyObj( G )!.wholeGroup := G;
SetFilterObj(G,IsGroupOfFamily);
# Create generators of the group.
gens:= List( GeneratorsOfGroup( F ), g -> ElementOfFpGroup( fam, g ) );
SetGeneratorsOfGroup( G, gens );
if IsEmpty( gens ) then
SetOne( G, ElementOfFpGroup( fam, One( F ) ) );
fi;
# trivial infinity deduction
if Length(gens)>Length(rels) then
SetSize(G,infinity);
SetIsFinite(G,false);
fi;
return G;
end );
#############################################################################
##
#M \/( <F>, <rels> ) . . . . . . . . . . for free group and list of relators
##
InstallOtherMethod( \/,
"for full free group and relators",
IsIdenticalObj,
[ IsFreeGroup and IsWholeFamily, IsCollection ],
FactorFreeGroupByRelators );
InstallOtherMethod( \/,
"for free group and relators",
IsIdenticalObj,
[ IsFreeGroup, IsCollection ],
function( G, rels )
if not HasIsWholeFamily( G ) and
IsSubset( FreeGeneratorsOfWholeGroup( G ), GeneratorsOfGroup( G ) ) then
SetIsWholeFamily( G, true );
return FactorFreeGroupByRelators( G, rels );
fi;
# If somebody thinks that it is worth the effort to support proper
# subgroups of full free groups then this method is the right place
# to add code for that.
Error( "currently quotients of a free group are supported only if the ",
"group knows to contain all generators of its parent group" );
end );
InstallOtherMethod( \/,
"for fp groups and relators",
IsIdenticalObj,
[ IsFpGroup, IsCollection ],
0,
FactorGroupFpGroupByRels );
InstallOtherMethod( \/,
"for free groups and a list of equations",
IsElmsColls,
[ IsFreeGroup, IsCollection ],
0,
{F, rels} -> FactorFreeGroupByRelators(F, List(rels, r -> r[1] / r[2])));
InstallOtherMethod( \/,
"for fp groups and a list of equations",
IsElmsColls,
[ IsFpGroup, IsCollection ],
0,
{F, rels} -> FactorGroupFpGroupByRels(F, List(rels, r -> r[1] / r[2])));
#############################################################################
##
#M \/( <F>, <rels> ) . . . . . . . for free group and empty list of relators
##
InstallOtherMethod( \/,
"for a free group and an empty list of relators",
true,
[ IsFreeGroup, IsEmpty ],
0,
FactorFreeGroupByRelators );
#############################################################################
##
#M FreeGeneratorsOfFpGroup( F ) . . generators of the underlying free group
##
InstallMethod( FreeGeneratorsOfFpGroup, "for a finitely presented group",
true,
[ IsSubgroupFpGroup and IsGroupOfFamily ], 0,
G -> GeneratorsOfGroup( FreeGroupOfFpGroup( G ) ) );
#############################################################################
##
#M FreeGeneratorsOfWholeGroup( U ) . . generators of the underlying free group
##
InstallMethod( FreeGeneratorsOfWholeGroup,
"for a finitely presented group",
true,
[ IsSubgroupFpGroup ], 0,
G -> GeneratorsOfGroup( ElementsFamily(FamilyObj( G ))!.freeGroup ) );
#############################################################################
##
#M FreeGroupOfFpGroup( F ) . . . . . . underlying free group of an fp group
##
InstallMethod( FreeGroupOfFpGroup, "for a finitely presented group", true,
[ IsSubgroupFpGroup and IsGroupOfFamily ], 0,
G -> ElementsFamily( FamilyObj( G ) )!.freeGroup );
#############################################################################
##
#M IndexNC( <G>, <H> )
##
InstallMethod( IndexNC,
"for finitely presented groups",
[ IsSubgroupFpGroup, IsSubgroupFpGroup ],
function(G,H)
# catch a stupid case
if IsIdenticalObj(G,H) then
return 1;
fi;
return IndexInWholeGroup(H)/IndexInWholeGroup(G);
end);
#############################################################################
##
#M IndexOp( <G>, <H> ) . . . . . . . . . . . for whole family and f.p. group
##
## We can avoid the `IsSubset' check of the default `IndexOp' method,
## and also the division of the `IndexNC' method.
##
InstallMethod( IndexOp,
"for finitely presented group in whole group",
IsIdenticalObj,
[ IsSubgroupFpGroup and IsWholeFamily, IsSubgroupFpGroup ],
function(G,H)
return IndexInWholeGroup(H);
end);
InstallMethod( CanComputeIndex,"subgroups fp groups",IsIdenticalObj,
[IsGroup and HasIndexInWholeGroup,IsGroup and HasIndexInWholeGroup],
ReturnTrue);
InstallMethod( CanComputeIndex,"subgroup of full fp groups",IsIdenticalObj,
[IsGroup and IsWholeFamily,IsGroup and HasIndexInWholeGroup],
ReturnTrue);
InstallMethod( CanComputeIndex,"subgroup of full fp groups",IsIdenticalObj,
[IsGroup and IsWholeFamily,IsGroup and HasCosetTableInWholeGroup],
ReturnTrue);
#############################################################################
##
#M IndexInWholeGroup( <H> ) . . . . . . index of a subgroup in an fp group
##
InstallMethod(IndexInWholeGroup,"subgroup fp",true,[IsSubgroupFpGroup],0,
function( H )
local T,i;
# Get the coset table of <H> in its whole group.
T := CosetTableInWholeGroup( H );
i:=IndexCosetTab( T );
if HasGeneratorsOfGroup(H) and Length(GeneratorsOfGroup(H))=0 then
SetSize(FamilyObj(H)!.wholeGroup,i);
fi;
return i;
end );
InstallMethod(IndexInWholeGroup,"subgroup fp by quotient",true,
[IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep],0,
function(U)
return Index(U!.quot,U!.sub);
end);
InstallMethod( IndexInWholeGroup, "for full fp group",
[ IsSubgroupFpGroup and IsWholeFamily ], a->1);
#############################################################################
##
#M ConjugateGroup(<U>,<g>) U^g
##
InstallMethod(ConjugateGroup,"subgroups of fp group with coset table",
IsCollsElms, [IsSubgroupFpGroup and HasCosetTableInWholeGroup,
IsMultiplicativeElementWithInverse],0,
function(U,g)
local t, w, wi, word, pos, V, i;
t:=CosetTableInWholeGroup(U);
if Length(t)<2 then
return U; # the whole group
fi;
# the image of g in the permutation group
w:=UnderlyingElement(g);
wi:=[1..IndexCosetTab(t)];
# for i in [1..NumberSyllables(w)] do
# e:=ExponentSyllable(w,i);
# if e<0 then
# pos:=2*GeneratorSyllable(w,i);
# e:=-e;
# else
# pos:=2*GeneratorSyllable(w,i)-1;
# fi;
# for j in [1..e] do
# wi:=t[pos]{wi}; # multiply permutations
# od;
# od;
word:=LetterRepAssocWord(w);
for i in [1..Length(word)] do
if word[i]<0 then
pos:=-2*word[i];
else
pos:=2*word[i]-1;
fi;
wi:=t[pos]{wi}; # multiply permutations
od;
w:=PermList(wi)^-1;
t:=List(t,i->OnTuples(i{wi},w));
StandardizeTable(t);
V:=SubgroupOfWholeGroupByCosetTable(FamilyObj(U),t);
if HasGeneratorsOfGroup(U) then
SetGeneratorsOfGroup(V,List(GeneratorsOfGroup(U),i->i^g));
fi;
return V;
end);
InstallMethod(ConjugateGroup,"subgroups of fp group by quotient",
IsCollsElms, [ IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep,
IsMultiplicativeElementWithInverse],0,
function(U,elm)
# transfer elm in factor
elm:=UnderlyingElement(elm);
elm:=MappedWord(elm,FreeGeneratorsOfWholeGroup(U),
GeneratorsOfGroup(U!.quot));
return SubgroupOfWholeGroupByQuotientSubgroup(FamilyObj(U),U!.quot,
ConjugateGroup(U!.sub,elm));
end);
InstallMethod(AsSubgroupOfWholeGroupByQuotient,"create",true,
[IsSubgroupFpGroup],0,
function(U)
local tab,Q,A;
tab:=CosetTableInWholeGroup(U);
Q:=GroupWithGenerators(List(tab{[1,3..Length(tab)-1]},PermList));
#T: try to improve via blocks
A:=Stabilizer(Q,1);
U:=SubgroupOfWholeGroupByQuotientSubgroup(FamilyObj(U),Q,A);
return U;
end);
InstallMethod(AsSubgroupOfWholeGroupByQuotient,"is already",true,
[IsSubgroupOfWholeGroupByQuotientRep],0,x->x);
#############################################################################
##
#F DefiningQuotientHomomorphism(<U>)
##
InstallGlobalFunction(DefiningQuotientHomomorphism,function(U)
local hom;
if not IsSubgroupOfWholeGroupByQuotientRep(U) then
Error("<U> must be in quotient representation");
fi;
hom:=GroupHomomorphismByImagesNC(FamilyObj(U)!.wholeGroup,
U!.quot,
GeneratorsOfGroup(FamilyObj(U)!.wholeGroup),
GeneratorsOfGroup(U!.quot));
SetIsSurjective(hom,true);
return hom;
end);
#############################################################################
##
#M CoreOp(<U>,<V>) . intersection of two fin. pres. groups
##
InstallMethod(CoreOp,"subgroups of fp group: use quotient rep",IsIdenticalObj,
[IsSubgroupFpGroup,IsSubgroupFpGroup],0,
function(V,U)
return Core(V,AsSubgroupOfWholeGroupByQuotient(U));
end);
InstallMethod(CoreOp,"subgroups of fp group by quotient",IsIdenticalObj,
[IsSubgroupFpGroup,
IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep],0,
function(V,U)
local q,gens;
# map the generators of V in the quotient
gens:=GeneratorsOfGroup(V);
gens:=List(gens,UnderlyingElement);
q:=U!.quot;
gens:=List(gens,i->MappedWord(i,FreeGeneratorsOfWholeGroup(U),
GeneratorsOfGroup(q)));
return SubgroupOfWholeGroupByQuotientSubgroup(FamilyObj(U),q,
Core(SubgroupNC(q,gens),U!.sub));
end);
#############################################################################
##
#M Intersection2(<G>,<H>) . intersection of two fin. pres. groups
##
InstallMethod(Intersection2,"subgroups of fp group",IsIdenticalObj,
[IsSubgroupFpGroup,IsSubgroupFpGroup],0,
function ( G, H )
local
Fam, # group family
table, # coset table for <I> in its parent
nrcos, # number of cosets of <I>
tableG, # coset table of <G>
nrcosG, # number of cosets of <G>
tableH, # coset table of <H>
nrcosH, # number of cosets of <H>
freegens, # free generators of Parent(G)
nrgens, # number of generators of the parent of <G> and <H>
ren, # if 'ren[<i>]' is 'nrcosH * <iG> + <iH>' then the
# coset <i> of <I> corresponds to the intersection
# of the pair of cosets <iG> of <G> and <iH> of <H>
ner, # the inverse mapping of 'ren'
cos, # coset loop variable
gen, # generator loop variable
img; # image of <cos> under <gen>
Fam:=FamilyObj(G);
# handle trivial cases
if IsIdenticalObj(G,Fam!.wholeGroup) then
return H;
elif IsIdenticalObj(H,Fam!.wholeGroup) then
return G;
fi;
# its worth to check inclusion first
if IndexInWholeGroup(G)<=IndexInWholeGroup(H) and IsSubset(G,H) then
return H;
elif IndexInWholeGroup(H)<=IndexInWholeGroup(G) and IsSubset(H,G) then
return G;
fi;
tableG := CosetTableInWholeGroup(G);
nrcosG := IndexCosetTab( tableG ) + 1;
tableH := CosetTableInWholeGroup(H);
nrcosH := IndexCosetTab( tableH ) + 1;
if nrcosH<=nrcosG and HasGeneratorsOfGroup(G) then
if ForAll(GeneratorsOfGroup(G),i->i in H) then
return G;
fi;
elif nrcosG<=nrcosH and HasGeneratorsOfGroup(H) then
if ForAll(GeneratorsOfGroup(H),i->i in G) then
return H;
fi;
fi;
freegens:=FreeGeneratorsOfFpGroup(Fam!.wholeGroup);
# initialize the table for the intersection
nrgens := Length(freegens);
table := [];
for gen in [ 1 .. nrgens ] do
table[ 2*gen-1 ] := [];
table[ 2*gen ] := [];
od;
# set up the renumbering
ren := ListWithIdenticalEntries(nrcosG*nrcosH,0);
ner := ListWithIdenticalEntries(nrcosG*nrcosH,0);
ren[ 1*nrcosH + 1 ] := 1;
ner[ 1 ] := 1*nrcosH + 1;
nrcos := 1;
# the coset table for the intersection is the transitive component of 1
# in the *tensored* permutation representation
cos := 1;
while cos <= nrcos do
# loop over all entries in this row
for gen in [ 1 .. nrgens ] do
# get the coset pair
img := nrcosH * tableG[ 2*gen-1 ][ QuoInt( ner[ cos ], nrcosH ) ]
+ tableH[ 2*gen-1 ][ ner[ cos ] mod nrcosH ];
# if this pair is new give it the next available coset number
if ren[ img ] = 0 then
nrcos := nrcos + 1;
ren[ img ] := nrcos;
ner[ nrcos ] := img;
fi;
# and enter it into the coset table
table[ 2*gen-1 ][ cos ] := ren[ img ];
table[ 2*gen ][ ren[ img ] ] := cos;
od;
cos := cos + 1;
od;
return SubgroupOfWholeGroupByCosetTable(Fam,table);
end);
InstallMethod(Intersection2,"subgroups of fp group by quotient",IsIdenticalObj,
[IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep,
IsSubgroupFpGroup and IsSubgroupOfWholeGroupByQuotientRep],0,
function ( G, H )
local d,A,B,e1,e2,Ag,Bg,s,sg,u,v,map,sz;
# it is not worth to check inclusion first since we're reducing afterwards
#if IndexInWholeGroup(G)<=IndexInWholeGroup(H) and IsSubset(G,H) then
# return H;
#elif IndexInWholeGroup(H)<=IndexInWholeGroup(G) and IsSubset(H,G) then
# return G;
#fi;
if Size(G!.quot)<Size(H!.quot) then
# make G the one with larger quot
A:=G; G:=H;H:=A;
fi;
A:=MakeNiceDirectQuots(G,H);
G:=A[1];
H:=A[2];
A:=G!.quot;
B:=H!.quot;
Ag:=GeneratorsOfGroup(A);
Bg:=GeneratorsOfGroup(B);
# form the sdp
# use map to determine common subdirect factor
map:=GroupGeneralMappingByImages(A,B,Ag,Bg);
sz:=Size(A)*Size(CoKernelOfMultiplicativeGeneralMapping(map));
# is the image obtained all in A?
if sz=Size(A) then
if ForAll(GeneratorsOfGroup(G!.sub),
x->ImagesRepresentative(map,x) in H!.sub) then
# G!.sub maps into H!.sub, thus contained in preimage
u:=G!.sub;
else
u:=PreImage(map,H!.sub);
u:=Intersection(G!.sub,u);
fi;
return SubgroupOfWholeGroupByQuotientSubgroup(FamilyObj(G),A,u);
fi;
d:=DirectProduct(A,B);
e1:=Embedding(d,1);
e2:=Embedding(d,2);
sg:=List([1..Length(Ag)],
i->ImagesRepresentative(e1,Ag[i])*ImagesRepresentative(e2,Bg[i]));
s:=SubgroupNC(d,sg);
SetSize(s,sz);
#if HasSize(A) and HasSize(B) and IsPermGroup(s) then
# StabChainOptions(s).limit:=Size(d);
#fi;
# get both subgroups in the direct product via the projections
# instead of intersecting both preimages with s we only intersect the
# intersection
u:=PreImagesSet(Projection(d,1),G!.sub);
if HasSize(B) then
SetSize(u,Size(G!.sub)*Size(B));
fi;
v:=PreImagesSet(Projection(d,2),H!.sub);
if HasSize(A) then
SetSize(v,Size(H!.sub)*Size(A));
fi;
u:=Intersection(u,v);
if Size(u)>1 and Size(s)<Size(d) then
u:=Intersection(u,s);
fi;
if IsPermGroup(A) and IsPermGroup(s) then
# reduce
e1:=Length(Orbits(A,MovedPoints(A)));
e2:=Length(Orbits(s,MovedPoints(s)));
d:=ValueOption("reduce");
if (d<>false and HasSize(s) and
# test proportiopnal to how much orbits added
--> --------------------
--> maximum size reached
--> --------------------
[ Verzeichnis aufwärts0.72unsichere Verbindung
Übersetzung europäischer Sprachen durch Browser
]
|
