Quelle grpfp.gi Sprache: unbekannt

#############################################################################
##
## 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>,)
##
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>, ) 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 \=( , <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( , <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 FB))->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(,<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()
##
InstallGlobalFunction(DefiningQuotientHomomorphism,function(U)
local hom;
 if not IsSubgroupOfWholeGroupByQuotientRep(U) then
 Error(" 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(,<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 in its parent
 nrcos, # number of cosets of 
 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[]' is 'nrcosH * <iG> + <iH>' then the
 # coset of 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

--> --------------------

Quelle grpfp.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.28 Sekunden (vorverarbeitet) ]