|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Volkmar Felsch.
##
## 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 subgroup presentations in finitely
## presented groups (fp groups).
##
#############################################################################
##
#M AbelianInvariantsNormalClosureFpGroupRrs( <G>, <H> ) . . . . . . . . . .
#M . . . . . abelian invariants of the normal closure of the subgroup H of G
##
## uses the Reduced Reidemeister-Schreier method to compute the abelian
## invariants of the normal closure of a subgroup <H> of a finitely
## presented group <G>.
##
InstallGlobalFunction( AbelianInvariantsNormalClosureFpGroupRrs,
function ( G, H )
local M;
M:=RelatorMatrixAbelianizedNormalClosureRrs( G, H );
if Length(M)=0 then
return [];
else
M:=ReducedRelationMat(M);
DiagonalizeMat( Integers, M );
return AbelianInvariantsOfList(DiagonalOfMat(M));
fi;
end );
#############################################################################
##
#M AbelianInvariantsSubgroupFpGroupMtc( <G>, <H> ) . . . . . . . . . . . . .
#M . . . . . abelian invariants of the normal closure of the subgroup H of G
##
## uses the Modified Todd-Coxeter method to compute the abelian
## invariants of a subgroup <H> of a finitely presented group <G>.
##
InstallGlobalFunction( AbelianInvariantsSubgroupFpGroupMtc,
function ( G, H )
local M;
M:=RelatorMatrixAbelianizedSubgroupMtc( G, H );
if Length(M)=0 then
return [];
else
M:=ReducedRelationMat(M);
DiagonalizeMat( Integers, M );
return AbelianInvariantsOfList(DiagonalOfMat(M));
fi;
end );
#############################################################################
##
#M AbelianInvariantsSubgroupFpGroupRrs( <G>, <H> ) . . . . . . . . . . . . .
#M AbelianInvariantsSubgroupFpGroupRrs( <G>, <costab> ) . . . . . . . . . .
#M . . . . . abelian invariants of the normal closure of the subgroup H of G
##
## uses the Reduced Reidemeister-Schreier method to compute the abelian
## invariants of a subgroup <H> of a finitely presented group <G>.
##
## Alternatively to the subgroup <H>, its coset table <table> in <G> may be
## given as second argument.
##
InstallGlobalFunction( AbelianInvariantsSubgroupFpGroupRrs,
function ( G, H )
local M;
M:=RelatorMatrixAbelianizedSubgroupRrs( G, H );
if M=fail then
if ValueOption("cheap")=true then return fail;fi;
Info(InfoWarning,1,
"exponent too large, abelianized coset enumeration aborted");
Info(InfoWarning,1,"calculation will be slow");
M:=MaximalAbelianQuotient(H); # this is in the library, so no overflow
return AbelianInvariants(Range(M));
elif Length(M)=0 then
return [];
else
M:=ReducedRelationMat(M);
DiagonalizeMat( Integers, M );
return AbelianInvariantsOfList(DiagonalOfMat(M));
fi;
end );
#############################################################################
##
#M AugmentedCosetTableInWholeGroup
##
InstallGlobalFunction(AugmentedCosetTableInWholeGroup,
function(arg)
local aug,H,wor,w;
H:=arg[1];
if Length(arg)=1 then
return AugmentedCosetTableRrsInWholeGroup(H);
fi;
wor:=List(arg[2],UnderlyingElement); # words for given elements
# is there an MTc table we can use?
if HasAugmentedCosetTableMtcInWholeGroup(H) then
aug := AugmentedCosetTableMtcInWholeGroup( H );
if IsSubset(aug.primaryGeneratorWords,wor) or
IsSubset(SecondaryGeneratorWordsAugmentedCosetTable(aug),wor) then
return aug;
fi;
fi;
# try the Rrs table
aug := AugmentedCosetTableRrsInWholeGroup( H );
if IsSubset(aug.primaryGeneratorWords,wor) or
IsSubset(SecondaryGeneratorWordsAugmentedCosetTable(aug),wor) then
return aug;
fi;
# still not: need completely new table
w:=FamilyObj(H)!.wholeGroup;
aug:=AugmentedCosetTableMtc(w,SubgroupNC(w,arg[2]),2,"y" );
return aug;
end);
#############################################################################
##
#M AugmentedCosetTableMtcInWholeGroup
##
InstallMethod( AugmentedCosetTableMtcInWholeGroup,
"subgroup of fp group", true, [IsSubgroupFpGroup], 0,
function( H )
local G, aug;
G := FamilyObj( H )!.wholeGroup;
aug := AugmentedCosetTableMtc( G, H, 2, "y" );
return aug;
end);
#############################################################################
##
#M AugmentedCosetTableRrsInWholeGroup
##
InstallMethod( AugmentedCosetTableRrsInWholeGroup,
"subgroup of fp group", true, [IsSubgroupFpGroup], 0,
function( H )
local G, costab, fam, aug, gens;
G := FamilyObj( H )!.wholeGroup;
costab := CosetTableInWholeGroup( H );
aug := AugmentedCosetTableRrs( G, costab, 2, "y" );
# if H has not yet any generators, we store them (and then also can store
# the coset table as Mtc table)
if not (HasGeneratorsOfGroup(H)
or HasAugmentedCosetTableMtcInWholeGroup(H)) then
SetAugmentedCosetTableMtcInWholeGroup(H,aug);
gens := aug.primaryGeneratorWords;
# do we need to wrap?
if not IsFreeGroup( G ) then
fam := ElementsFamily( FamilyObj( H ) );
gens := List( gens, i -> ElementOfFpGroup( fam, i ) );
fi;
SetGeneratorsOfGroup( H, gens );
fi;
return aug;
end);
#############################################################################
##
#M AugmentedCosetTableNormalClosureInWholeGroup( <H> ) . . . augmented coset
#M table of the normal closure of an fp subgroup in its whole group
##
## is equivalent to `AugmentedCosetTableNormalClosure( <G>, <H> )' where <G>
## is the (unique) finitely presented group such that <H> is a subgroup of
## <G>.
##
InstallMethod( AugmentedCosetTableNormalClosureInWholeGroup,
"subgroup of fp group", true, [IsSubgroupFpGroup], 0,
function( H )
local G, costab, aug;
# get the whole group G of H
G := FamilyObj( H )!.wholeGroup;
# compute a coset table of the normal closure N of H in G
costab := CosetTableNormalClosureInWholeGroup( H );
# apply the Reduced Reidemeister-Schreier method to construct an
# augmented coset table of N in G
aug := AugmentedCosetTableRrs( G, costab, 2, "%" );
return aug;
end );
#############################################################################
##
#M AugmentedCosetTableMtc( <G>, <H>, <type>, <string> ) . . . . . . . . . .
#M . . . . . . . . . . . . . do an MTC and return the augmented coset table
##
## is an internal function used by the subgroup presentation functions
## described in "Subgroup Presentations". It applies a Modified Todd-Coxeter
## coset representative enumeration to construct an augmented coset table
## (see "Subgroup presentations") for the given subgroup <H> of <G>. The
## subgroup generators will be named <string>1, <string>2, ... .
##
## Valid types are 1 (for the one generator case), 0 (for the abelianized
## case), and 2 (for the general case). A type value of -1 is handled in
## the same way as the case type = 1, but the function will just return the
## the exponent <aug>.exponent of the given cyclic subgroup <H> and its
## index <aug>.index in <G> as the only components of the resulting record
## <aug>.
##
InstallGlobalFunction( AugmentedCosetTableMtc,
function ( G, H, ttype, string )
# check the arguments
if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then
Error( "<G> must be a finitely presented group" );
fi;
if FamilyObj( H ) <> FamilyObj( G ) then
Error( "<H> must be a subgroup of <G>" );
fi;
return NEWTC_CosetEnumerator(FreeGeneratorsOfFpGroup(G),
RelatorsOfFpGroup(G),GeneratorsOfGroup(H),true);
end );
#############################################################################
##
#M AugmentedCosetTableRrs( <G>, <coset table>, <type>, <string> ) . . . . .
#M do a RRS and return the augmented coset table
##
## 'AugmentedCosetTableRrs' applies the Reduced Reidemeister-Schreier method
## to construct an augmented coset table for the subgroup of G which is
## defined by the given coset table. The new subgroup generators will be
## named <string>1, <string>2, ... .
##
InstallGlobalFunction( AugmentedCosetTableRrs,
function ( G, table, type, string )
local fgens, # generators of associated free group
grels, # relators of G
involutions, # indices of involutory gens of G
index, # index of the group in the parent group
cosTable, # coset table
negTable, # coset table to be built up
coFacTable, # coset factor table
numcols, # number of columns in the tables
numgens, # number of generators
F, # a new free group
span, # spanning tree
ggens, # parent group gens prallel to columns
gens, # new generators
ngens, # number of new generators
defs, # definitions of primary subgroup gens
tree, # tree of generators
tree1, tree2, # components of tree of generators
treelength, # number of gens (primary + secondary)
rels, # representatives for the relators
relsGen, # relators beginning with a gen
deductions, # deduction queue
ded, # index of current deduction in above
nrdeds, # current number of deductions in above
i, ii, gen, inv, # loop variables for generator
triple, # loop variable for relators as triples
word, factors, # words defining subgroup generators
app, # application stack for 'ApplyRel'
app2, # application stack for 'ApplyRel2'
j, k, # loop variables
fac, # tree entry
count, # number of negative table entries
next, #
numoccs, # number of gens which occur in the table
occur, #
treeNums, #
convert, # conversion list for subgroup generators
aug, # augmented coset table
field, # loop variable for record field names
EnterDeduction, # subroutine
LoopOverAllCosets; # subroutine
EnterDeduction := function ( )
# a deduction has been found, check the current coset table entry.
# if triple[2][app[1]][app[2]] <> -app[4] or
# triple[2][app[3]][app[4]] <> -app[2] then
# Error( "unexpected coset table entry" );
# fi;
# compute the corresponding factors in "factors".
app2[1] := triple[3];
app2[2] := deductions[ded][2];
app2[3] := -1;
app2[4] := app2[2];
if not ApplyRel2( app2, triple[2], triple[1] ) then
return fail; # rewriting failed b/c too large exponent
fi;
factors := app2[7];
#if Length(factors)>0 then Print(Length(factors)," ",Maximum(factors)," ",Minimum(factors),"\n");fi;
# ensure that the scan provided a deduction.
# if app2[1] - 1 <> app2[3]
# or triple[2][app2[1]][app2[2]] <> - app2[4]
# or triple[2][app2[3]][app2[4]] <> - app2[2]
# then
# Error( "the given scan does not provide a deduction" );
# fi;
# extend the tree to define a proper factor, if necessary.
fac := TreeEntry( tree, factors );
# now enter the deduction to the tables.
triple[2][app2[1]][app2[2]] := app2[4];
coFacTable[triple[1][app2[1]]][app2[2]] := fac;
triple[2][app2[3]][app2[4]] := app2[2];
coFacTable[triple[1][app2[3]]][app2[4]] := - fac;
nrdeds := nrdeds + 1;
deductions[nrdeds] := [ triple[1][app2[1]], app2[2] ];
treelength := tree[3];
count := count - 2;
end;
LoopOverAllCosets:=function()
# loop over all the cosets
for j in [ 1 .. index ] do
CompletionBar(InfoFpGroup,2,"Coset Loop: ",j/index);
# run through all the rows and look for negative entries
for i in [ 1 .. numcols ] do
gen := negTable[i];
if gen[j] < 0 then
# add the current Schreier generator to the set of new
# subgroup generators, and add the definition as deduction.
k := - gen[j];
word := ggens[i];
while k > 1 do
word := word * ggens[span[2][k]]^-1; k := span[1][k];
od;
k := j;
while k > 1 do
word := ggens[span[2][k]] * word; k := span[1][k];
od;
numgens := numgens + 1;
defs[numgens] := word;
treelength := treelength + 1;
tree[3] := treelength;
tree[4] := numgens;
if type = 0 then
tree1[treelength] :=
ListWithIdenticalEntries( numgens, 0 );
tree1[treelength][numgens] := 1;
tree2[numgens] := 0;
else
tree1[treelength] := 0;
tree2[treelength] := 0;
fi;
# add the definition as deduction.
inv := negTable[i + 2*(i mod 2) - 1];
k := - gen[j];
gen[j] := k;
coFacTable[i][j] := treelength;
if inv[k] < 0 then
inv[k] := j;
ii := i + 2*(i mod 2) - 1;
coFacTable[ii][k] := - treelength;
fi;
count := count - 2;
# set up the deduction queue and run over it until it's empty
deductions:=[];
deductions[1] := [i,j];
nrdeds := 1;
ded := 1;
while ded <= nrdeds do
# apply all relators that start with this generator
for triple in relsGen[deductions[ded][1]] do
app[1] := triple[3];
app[2] := deductions[ded][2];
app[3] := -1;
app[4] := app[2];
if ApplyRel( app, triple[2] ) and
triple[2][app[1]][app[2]] < 0 and
triple[2][app[3]][app[4]] < 0 then
# a deduction has been found: compute the
# corresponding factor and enter the deduction to
# the tables and to the deductions lists.
EnterDeduction( );
if count <= 0 then
return;
fi;
fi;
od;
ded := ded + 1;
od;
fi;
od;
od;
end;
# check G to be a finitely presented group.
if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then
Error( "<G> must be a finitely presented group" );
fi;
# check the type for being 0 or 2.
if type <> 0 and type <> 2 then
Error( "invalid type; it should be 0 or 2" );
fi;
# get some local variables
fgens := FreeGeneratorsOfFpGroup( G );
grels := RelatorsOfFpGroup( G );
# check the number of columns of the given coset table to be twice the
# number of generators of the parent group G.
numcols := Length( table );
if numcols <> 2 * Length( fgens ) then
Error( "parent group and coset table are inconsistent" );
fi;
index := IndexCosetTab( table );
# get a negative copy of the coset table, and initialize the coset factor
# table (parallel to it) by zeros.
involutions := IndicesInvolutaryGenerators( G );
if Length( involutions ) = 0 then
cosTable := table;
else
cosTable := [ ];
for i in [ 1 .. Length( fgens ) ] do
cosTable[2*i-1] := table[2*i-1];
if i in involutions then
cosTable[2*i] := table[2*i-1];
else
cosTable[2*i] := table[2*i];
fi;
od;
fi;
negTable := [ ];
coFacTable := [ ];
for i in [ 1 .. Length( fgens ) ] do
negTable[2*i-1] := List( cosTable[2*i-1], x -> -x );
coFacTable[2*i-1] := ListWithIdenticalEntries( index, 0 );
if i in involutions then
negTable[2*i] := negTable[2*i-1];
coFacTable[2*i] := coFacTable[2*i-1];
else
negTable[2*i] := List( cosTable[2*i], x -> -x );
coFacTable[2*i] := ListWithIdenticalEntries( index, 0 );
fi;
od;
count := index * ( numcols - 2 ) + 2;
# construct the list relsGen which for each generator or inverse
# generator contains a list of all cyclically reduced relators,
# starting with that element, which can be obtained by conjugating or
# inverting given relators. The relators in relsGen are represented as
# lists of the coset table columns corresponding to the generators and,
# in addition, as lists of the respective column numbers.
rels := RelatorRepresentatives( grels );
relsGen := RelsSortedByStartGen( fgens, rels, negTable, true );
SortRelsSortedByStartGen( relsGen );
# check the number of columns to be twice the number of generators of
# the parent group G.
if numcols <> 2 * Length( fgens ) then
Error( "parent group and coset table are inconsistent" );
fi;
# initialize the tree of secondary generators.
tree1 := ListWithIdenticalEntries( 100, 0 );
if type = 0 then
tree2 := [ ];
else
tree2 := ListWithIdenticalEntries( 100, 0 );
fi;
treelength := 0;
tree := [ tree1, tree2, treelength, 0, type ];
# initialize an empty deduction list
deductions := [ ]; deductions[index] := 0;
nrdeds := 0;
# get a spanning tree for the cosets
span := SpanningTree( cosTable );
# enter the coset definitions into the coset table.
for k in [ 2 .. index ] do
j := span[1][k];
i := span[2][k];
ii := i + 2*(i mod 2) - 1;
# check the current table entry.
if negTable[i][j] <> - k or negTable[ii][k] <> -j then
Error( "coset table and spanning tree are inconsistent" );
fi;
# enter the deduction.
negTable[i][j] := k;
if negTable[ii][k] < 0 then negTable[ii][k] := j; fi;
nrdeds := nrdeds + 1;
deductions[nrdeds] := [i,j];
od;
# make the local structures that are passed to 'ApplyRel' or, via
# EnterDeduction, to 'ApplyRel2".
app := ListWithIdenticalEntries( 4, 0 );
app2 := ListWithIdenticalEntries( 9, 0 );
if type = 0 then
factors := tree2;
else
factors := [ ];
fi;
# set those arguments of ApplyRel2 which are global with respect to the
# following loops.
app2[5] := type;
app2[6] := coFacTable;
app2[7] := factors;
if type = 0 then
app2[8] := tree;
fi;
# set up the deduction queue and run over it until it's empty
ded := 1;
while ded <= nrdeds do
if ded mod 50=0 then
CompletionBar(InfoFpGroup,2,"Queue: ",ded/nrdeds);
fi;
# apply all relators that start with this generator
for triple in relsGen[deductions[ded][1]] do
app[1] := triple[3];
app[2] := deductions[ded][2];
app[3] := -1;
app[4] := app[2];
if ApplyRel( app, triple[2] ) and triple[2][app[1]][app[2]] < 0
and triple[2][app[3]][app[4]] < 0 then
# a deduction has been found: compute the corresponding
# factor and enter the deduction to the tables and to the
# deductions lists.
EnterDeduction( );
fi;
od;
ded := ded + 1;
od;
CompletionBar(InfoFpGroup,2,"Queue: ",false);
# get a list of the parent group generators parallel to the table
# columns.
ggens := [ ];
for i in [ 1 .. numcols/2 ] do
ggens[2*i-1] := fgens[i];
ggens[2*i] := fgens[i]^-1;
od;
# initialize the list of new subgroup generators
numgens := 0;
defs := [ ];
# loop over cosets
LoopOverAllCosets();
CompletionBar(InfoFpGroup,2,"Coset Loop: ",false);
# save the number of primary subgroup generators and the number of all
# subgroup generators in the tree.
tree[3] := treelength;
# get an immutable coset table with no two columns identical.
if IsMutable( table ) then
cosTable := Immutable( table );
else
cosTable := table;
fi;
# separate pairs of identical columns in the coset factor table.
for i in [ 1 .. Length( fgens ) ] do
if i in involutions then
coFacTable[2*i] := StructuralCopy( coFacTable[2*i-1] );
fi;
od;
# create the augmented coset table record.
aug := rec( );
aug.isAugmentedCosetTable := true;
aug.type := type;
aug.tableType := TABLE_TYPE_RRS;
aug.groupGenerators := fgens;
aug.groupRelators := grels;
aug.cosetTable := cosTable;
aug.cosetFactorTable := coFacTable;
aug.primaryGeneratorWords := defs;
aug.tree := tree;
# renumber the generators such that the primary ones precede the
# secondary ones, and sort the tree and the factor table accordingly.
if type = 2 then
RenumberTree( aug );
# determine which generators occur in the augmented table.
occur := ListWithIdenticalEntries( treelength, 0 );
for i in [ 1 .. numgens ] do
occur[i] := 1;
od;
numcols := Length( coFacTable );
numoccs := numgens;
i := 1;
while i < numcols do
for next in coFacTable[i] do
if next <> 0 then
j := AbsInt( next );
if occur[j] = 0 then
occur[j] := 1; numoccs := numoccs + 1;
fi;
fi;
od;
i := i + 2;
od;
# build up a list of pointers from the occurring generators to the
# tree, and define names for the occurring secondary generators.
ngens := numgens;
treeNums := [ 1 .. numoccs ];
for j in [ numgens+1 .. treelength ] do
if occur[j] <> 0 then
ngens := ngens + 1;
treeNums[ngens] := j;
fi;
od;
aug.treeNumbers := treeNums;
# get ngens new generators
F := FreeGroup( ngens, string );
gens := GeneratorsOfGroup( F );
# prepare a conversion list for the subgroup generator numbers if
# they do not all occur in the subgroup relators.
numgens := Length( gens );
if numgens < treelength then
convert := ListWithIdenticalEntries( treelength, 0 );
for i in [ 1 .. numgens ] do
convert[treeNums[i]] := i;
od;
aug.conversionList := convert;
fi;
aug.numberOfSubgroupGenerators := ngens;
aug.nameOfSubgroupGenerators := Immutable( string );
aug.subgroupGenerators := gens;
fi;
# ensure that all components of the augmented coset table are immutable.
for field in RecNames( aug ) do
MakeImmutable( aug.(field) );
od;
# display a message
numgens := Length( defs );
Info( InfoFpGroup, 1, "RRS defined ", numgens, " primary and ",
treelength - numgens, " secondary subgroup generators" );
# return the augmented coset table.
return aug;
end );
#############################################################################
##
#M AugmentedCosetTableNormalClosure( <G>, <H> ) . . . augmented coset table
#M of the normal closure of a subgroup in a finitely presented group
##
InstallMethod( AugmentedCosetTableNormalClosure,
"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 AugmentedCosetTableNormalClosureInWholeGroup( H );
end );
#############################################################################
##
#M CosetTableBySubgroup(<G>,<H>)
##
## returns a coset table for the action of <G> on the cosets of <H>. The
## columns of the table correspond to the `GeneratorsOfGroup(<G>)'.
##
InstallMethod(CosetTableBySubgroup,"coset action",IsIdenticalObj,
[IsGroup,IsGroup],0,
function ( G, H )
local column, gens, i, range, table, transversal;
# construct a permutations representation of G on the cosets of H.
gens := GeneratorsOfGroup(G);
if not (IsPermGroup(G) and IsPermGroup(H) and
IsEqualSet(Orbit(G,1),[1..NrMovedPoints(G)]) and H=Stabilizer(G,1)) then
transversal := RightTransversal( G, H );
gens := List( gens, gen -> Permutation( gen, transversal,OnRight ) );
range := [ 1 .. Length( transversal ) ];
else
range := [ 1 .. NrMovedPoints(G) ];
fi;
# initialize the coset table.
table := [];
# construct the columns of the table from the permutations.
for i in gens do
column := OnTuples( range, i );
Add( table, column );
column:=OnTuples(range,i^-1);
Add( table, column );
od;
# standardize the table and return it.
StandardizeTable( table );
return table;
end);
InstallMethod(CosetTableBySubgroup,"use `CosetTableInWholeGroup",
IsIdenticalObj, [IsSubgroupFpGroup,IsSubgroupFpGroup],0,
function(G,H)
if IndexInWholeGroup(G)>1 or not IsIdenticalObj(G,Parent(G))
or List(GeneratorsOfGroup(G),UnderlyingElement)
<>FreeGeneratorsOfFpGroup(Parent(G)) then
TryNextMethod();
fi;
return CosetTableInWholeGroup(H);
end);
#############################################################################
##
#M CanonicalRelator( <relator> ) . . . . . . . . . . . . canonical relator
##
## 'CanonicalRelator' returns the canonical representative of the given
## relator.
##
InstallGlobalFunction( CanonicalRelator, function ( Rel )
local i, i1, ii, j, j1, jj, k, k1, kk, length, max, min, rel;
rel := Rel;
length := Length( rel );
max := Maximum( rel );
min := Minimum( rel );
if max < - min then
i := 0;
else
i := Position( rel, max, 0 );
k := i;
while k <> false do
k := Position( rel, max, k );
if k <> false then
ii := i; kk := k; k1 := k - 1;
while kk <> k1 do
if ii = length then ii := 1; else ii := ii + 1; fi;
if kk = length then kk := 1; else kk := kk + 1; fi;
if rel[kk] > rel[ii] then i := k; kk := k1;
elif rel[kk] < rel[ii] then kk := k1;
elif kk = k1 then k := false; fi;
od;
fi;
od;
fi;
if - min < max then
j := 0;
else
j := Position( rel, min, 0 );
k := j;
while k <> false do
k := Position( rel, min, k );
if k <> false then
jj := j; kk := k; j1 := j + 1;
while jj <> j1 do
if jj = 1 then jj := length; else jj := jj - 1; fi;
if kk = 1 then kk := length; else kk := kk - 1; fi;
if rel[kk] < rel[jj] then j := k; jj := j1;
elif rel[kk] > rel[jj] then jj := j1;
elif jj = j1 then k := false; fi;
od;
fi;
od;
fi;
if - min = max then
if i = 1 then i1 := length; else i1 := i - 1; fi;
ii := i; jj := j;
while ii <> i1 do
if ii = length then ii := 1; else ii := ii + 1; fi;
if jj = 1 then jj := length; else jj := jj - 1; fi;
if - rel[jj] < rel[ii] then j := 0; ii := i1;
elif - rel[jj] > rel[ii] then i := 0; ii := i1; fi;
od;
fi;
if i = 0 then rel := - Reversed( rel ); i := length + 1 - j; fi;
if i > 1 then rel := Concatenation(
rel{ [i..length] }, rel{ [1..i-1] } );
fi;
return( rel );
end );
#############################################################################
##
#M CheckCosetTableFpGroup( <G>, <table> ) . . . . . . . checks a coset table
##
## 'CheckCosetTableFpGroup' checks whether table is a legal coset table of
## the finitely presented group G.
##
InstallGlobalFunction( CheckCosetTableFpGroup, function ( G, table )
local fgens, grels, i, id, index, ngens, perms;
# check G to be a finitely presented group.
if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then
Error( "<G> must be a finitely presented group" );
fi;
# check table to be a list of lists.
if not ( IsList( table ) and ForAll( table, IsList ) ) then
Error( "<table> must be a coset table" );
fi;
# get some local variables
fgens := FreeGeneratorsOfFpGroup( G );
grels := RelatorsOfFpGroup( G );
# check the number of columns against the number of group generators.
ngens := Length( fgens );
if Length( table ) <> 2 * ngens then
Error( "inconsistent number of group generators and table columns" );
fi;
# check the columns to be permutations of equal degree.
index := IndexCosetTab( table );
perms := [ ]; perms[ngens] := 0;
for i in [ 1 .. ngens ] do
if Length( table[2*i-1] ) <> index then
Error( "table has columns of different length" );
fi;
perms[i] := PermList( table[2*i-1] );
if PermList( table[2*i] ) <> perms[i]^-1 then
Error( "table has inconsistent inverse columns" );
fi;
od;
# check the permutations to act transitively.
id := perms[1]^0;
if not IsTransitive( GroupByGenerators( perms, id ), [ 1 .. index ] ) then
Error( "table does not act transitively" );
fi;
# check the permutations to satisfy the group relators.
if not ForAll( grels, rel -> MappedWord( rel, fgens, perms )
= id ) then
Error( "table columns do not satisfy the group relators" );
fi;
end );
#############################################################################
##
#M IsStandardized( <costab> ) . . . . . test if coset table is standardized
##
InstallGlobalFunction( IsStandardized, function ( table )
local i, index, j, next;
index := IndexCosetTab( table );
j := 1;
next := 2;
while next < index do
for i in [ 1, 3 .. Length( table ) - 1 ] do
if table[i][j] >= next then
if table[i][j] > next then return false; fi;
next := next + 1;
fi;
od;
j := j + 1;
od;
return true;
end );
#############################################################################
##
#R IsPresentationDefaultRep( <pres> )
##
## is the default representation of presentations.
## `IsPresentationDefaultRep' is a subrepresentation of
## `IsComponentObjectRep'.
##
DeclareRepresentation( "IsPresentationDefaultRep",
IsComponentObjectRep and IsAttributeStoringRep, [] );
#T eventually the admissible component names should be listed here
#############################################################################
##
#M \.( <pres>, <nam> ) . . . . . . . . . . . . . . . . . for a presentation
##
InstallMethod( \.,
"for a presentation in default representation",
true,
[ IsPresentation and IsPresentationDefaultRep, IsPosInt ], 0,
function( pres, nam )
Error("still record access");
return pres!.( NameRNam( nam ) );
end );
#############################################################################
##
#M IsBound\.( <pres>, <nam> ) . . . . . . . . . . . . . . for a presentation
##
InstallMethod( IsBound\.,
"for a presentation in default representation",
true,
[ IsPresentation and IsPresentationDefaultRep, IsPosInt ], 0,
function( pres, nam )
Error("still record access");
return IsBound( pres!.( NameRNam( nam ) ) );
end );
#############################################################################
##
#M \.\:\=( <pres>, <nam>, <val> ) . . . . . . . . . . . . for a presentation
##
InstallMethod( \.\:\=,
"for a mutable presentation in default representation",
true,
[ IsPresentation and IsPresentationDefaultRep and IsMutable,
IsPosInt, IsObject ], 0,
function( pres, nam, val )
Error("still record access");
pres!.( NameRNam( nam ) ):= val;
end );
#############################################################################
##
#M Unbind\.( <pres>, <nam> ) . . . . . . . . . . . . . . for a presentation
##
InstallMethod( Unbind\.,
"for a mutable presentation in default representation",
true,
[ IsPresentation and IsPresentationDefaultRep and IsMutable,
IsPosInt ], 0,
function( pres, nam )
Error("still record access");
Unbind( pres!.( NameRNam( nam ) ) );
end );
#############################################################################
##
#M PresentationAugmentedCosetTable( <aug>, <string> [,<print level>] ) . . .
#M create a Tietze record
##
## 'PresentationAugmentedCosetTable' creates a presentation, i.e. a Tietze
## record, from the given augmented coset table. It assumes that <aug> is an
## augmented coset table of type 2. The generators will be named <string>1,
## <string>2, ... .
##
InstallGlobalFunction( PresentationAugmentedCosetTable,
function ( arg )
local aug, coFacTable, comps, F, fgens, gens, i, invs, lengths, numgens,
numrels, pointers, printlevel, rels, string, T, tietze, total,
tree, treelength, treeNums;
# check the first argument to be an augmented coset table.
aug := arg[1];
if not ( IsRecord( aug ) and IsBound( aug.isAugmentedCosetTable ) and
aug.isAugmentedCosetTable ) then
Error( "first argument must be an augmented coset table" );
fi;
# get the generators name.
string := arg[2];
if not IsString( string ) then
Error( "second argument must be a string" );
fi;
# check the third argument to be an integer.
printlevel := 1;
if Length( arg ) >= 3 then printlevel := arg[3]; fi;
if not IsInt( printlevel ) then
Error ("third argument must be an integer" );
fi;
# initialize some local variables.
coFacTable := aug.cosetFactorTable;
tree := ShallowCopy( aug.tree );
treeNums := ShallowCopy( aug.treeNumbers );
treelength := Length( tree[1] );
F := FreeGroup(IsLetterWordsFamily, infinity, string );
fgens := GeneratorsOfGroup( F );
gens := ShallowCopy(aug.subgroupGenerators);
rels := List(aug.subgroupRelators,ShallowCopy);
numrels := Length( rels );
numgens := Length( gens );
# create the Tietze object.
T := Objectify( NewType( PresentationsFamily,
IsPresentationDefaultRep
and IsPresentation
and IsMutable ),
rec() );
# construct the relator lengths list.
lengths := List( [ 1 .. numrels ], i -> Length( rels[i] ) );
total := Sum( lengths );
# initialize the Tietze stack.
tietze := ListWithIdenticalEntries( TZ_LENGTHTIETZE, 0 );
tietze[TZ_NUMRELS] := numrels;
tietze[TZ_RELATORS] := rels;
tietze[TZ_LENGTHS] := lengths;
tietze[TZ_FLAGS] := ListWithIdenticalEntries( numrels, 1 );
tietze[TZ_TOTAL] := total;
# construct the generators and the inverses list, and save the generators
# as components of the Tietze record.
invs := [ ]; invs[2*numgens+1] := 0;
pointers := [ 1 .. treelength ];
for i in [ 1 .. numgens ] do
invs[numgens+1-i] := i;
invs[numgens+1+i] := - i;
T!.(String( i )) := fgens[i];
pointers[treeNums[i]] := treelength + i;
od;
invs[numgens+1] := 0;
comps := [ 1 .. numgens ];
# define the remaining Tietze stack entries.
tietze[TZ_FREEGENS] := fgens;
tietze[TZ_NUMGENS] := numgens;
tietze[TZ_GENERATORS] := List( [ 1 .. numgens ], i -> fgens[i] );
tietze[TZ_INVERSES] := invs;
tietze[TZ_NUMREDUNDS] := 0;
tietze[TZ_STATUS] := [ 0, 0, -1 ];
tietze[TZ_MODIFIED] := false;
# define some Tietze record components.
T!.generators := tietze[TZ_GENERATORS];
T!.tietze := tietze;
T!.components := comps;
T!.nextFree := numgens + 1;
T!.identity := One( fgens[1] );
SetOne(T,One( fgens[1] ));
# save the tree as component of the Tietze record.
tree[TR_TREENUMS] := treeNums;
tree[TR_TREEPOINTERS] := pointers;
tree[TR_TREELAST] := treelength;
T!.tree := tree;
# save the definitions of the primary generators as words in the original
# group generators.
SetPrimaryGeneratorWords(T,aug.primaryGeneratorWords);
# Since T is mutable, we must set this attribite "manually"
SetTzOptions(T, TzOptions(T));
# handle relators of length 1 or 2, but do not eliminate any primary
# generators.
TzOptions(T).protected := tree[TR_PRIMARY];
TzOptions(T).printLevel := printlevel;
if Length(arg)>3 and arg[4]=true then
# the stupid Length1or2 convention might mess up the connection to the
# coset table.
TzInitGeneratorImages(T);
fi;
if numgens>0 then
TzHandleLength1Or2Relators( T );
fi;
T!.hasRun1Or2:=true;
TzOptions(T).protected := 0;
# sort the relators.
TzSort( T );
TzOptions(T).printLevel := printlevel;
# return the Tietze record.
return T;
end );
#############################################################################
##
#M PresentationNormalClosureRrs( <G>, <H> [,<string>] ) . . . Tietze record
#M for the normal closure of a subgroup
##
## 'PresentationNormalClosureRrs' uses the Reduced Reidemeister-Schreier
## method to compute a presentation (i.e. a presentation record) for the
## normal closure N of a subgroup H of a finitely presented group G.
## The generators in the resulting presentation will be named <string>1,
## <string>2, ... , the default string is `\"_x\"'.
##
InstallGlobalFunction( PresentationNormalClosureRrs,
function ( arg )
local G, # given group
H, # given subgroup
string, # given string
F, # associated free group
fgens, # generators of <F>
hgens, # generators of <H>
fhgens, # their preimages in <F>
grels, # relators of <G>
krels, # relators of normal closure <N>
K, # factor group of F isomorphic to G/N
cosTable, # coset table of <G> by <N>
i, # loop variable
aug, # auxiliary coset table of <G> by <N>
T; # resulting Tietze record
# check the first two arguments to be a finitely presented group and a
# subgroup of that group.
G := arg[1];
if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then
Error( "<G> must be a finitely presented group" );
fi;
H := arg[2];
if not IsSubgroupFpGroup( H ) or FamilyObj( H ) <> FamilyObj( G ) then
Error( "<H> must be a subgroup of <G>" );
fi;
# get the generators name.
if Length( arg ) = 2 then
string := "_x";
else
string := arg[3];
if not IsString( string ) then
Error( "third argument must be a string" );
fi;
fi;
# get some local variables
F := FreeGroupOfFpGroup( G );
fgens := GeneratorsOfGroup( F );
grels := RelatorsOfFpGroup( G );
hgens := GeneratorsOfGroup( H );
fhgens := List( hgens, 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, fhgens );
K := F / krels;
# get the coset table of N in G by constructing the coset table of the
# trivial subgroup in K.
cosTable := CosetTable( K, TrivialSubgroup( K ) );
Info( InfoFpGroup, 1, "index is ", Length( cosTable[1] ) );
# # obsolete: No columns should be equal!
# for i in [ 1 .. Length( fgens ) ] do
# if IsIdenticalObj( cosTable[2*i-1], cosTable[2*i] ) then
# Error( "there is a bug in PresentationNormalClosureRrs" ); fi; od;
# apply the Reduced Reidemeister-Schreier method to construct a coset
# table presentation of N.
aug := AugmentedCosetTableRrs( G, cosTable, 2, string );
# determine a set of subgroup relators.
aug.subgroupRelators := RewriteSubgroupRelators( aug, aug.groupRelators);
# create a Tietze record for the resulting presentation.
T := PresentationAugmentedCosetTable( aug, string );
# handle relators of length 1 or 2, but do not eliminate any primary
# generators.
TzOptions(T).protected := T!.tree[TR_PRIMARY];
TzHandleLength1Or2Relators( T );
T!.hasRun1Or2:=true;
TzOptions(T).protected := 0;
# sort the relators.
TzSort( T );
return T;
end );
#############################################################################
##
#M PresentationSubgroupRrs( <G>, <H> [,<string>] ) . . . . . . Tietze record
#M PresentationSubgroupRrs( <G>, <costab> [,<string>] ) . . for a subgroup
##
## 'PresentationSubgroupRrs' uses the Reduced Reidemeister-Schreier method
## to compute a presentation (i.e. a presentation record) for a subgroup H
## of a finitely presented group G. The generators in the resulting
## presentation will be named <string>1, <string>2, ... , the default
## string is "_x".
##
## Alternatively to a finitely presented group, the subgroup H may be given
## by its coset table.
##
InstallGlobalFunction( PresentationSubgroupRrs, function ( arg )
local aug, G, gens, H, ngens, string, T, table;
# check G to be a finitely presented group.
G := arg[1];
if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then
Error( "<group> must be a finitely presented group" );
fi;
# get the generators name.
if Length( arg ) = 2 then
string := "_x";
else
string := arg[3];
if not IsString( string ) then
Error( "third argument must be a string" );
fi;
fi;
# check the second argument to be a subgroup or a coset table of G, and
# get the coset table in either case.
H := arg[2];
if not IsSubgroupFpGroup( H ) or FamilyObj( H ) <> FamilyObj( G ) then
# check the given table to be a legal coset table.
table := H;
CheckCosetTableFpGroup( G, table );
# ensure that it is standardized.
if not IsStandardized( table) then Print(
"#I Warning: the given coset table is not standardized,\n",
"#I a standardized copy will be used instead.\n" );
StandardizeTable( StructuralCopy( table ) );
fi;
# apply the Reduced Reidemeister-Schreier method to construct an
# augmented RRS coset table of H.
aug := AugmentedCosetTableRrs( G, table, 2, string );
else
# get a copy of an augmented RRS coset table of H in G.
aug := CopiedAugmentedCosetTable(
AugmentedCosetTableRrsInWholeGroup( H ) );
# insert the required subgroup generator names if necessary.
if aug.nameOfSubgroupGenerators <> string then
aug.nameOfSubgroupGenerators := string;
ngens := aug.numberOfSubgroupGenerators;
gens := GeneratorsOfGroup( FreeGroup( ngens, string ) );
aug.subgroupGenerators := gens;
fi;
fi;
# determine a set of subgroup relators.
aug.subgroupRelators := RewriteSubgroupRelators( aug, aug.groupRelators);
# create a Tietze record for the resulting presentation.
T := PresentationAugmentedCosetTable( aug, string );
return T;
end );
#############################################################################
##
#M ReducedRrsWord( <word> ) . . . . . . . . . . . . . . freely reduce a word
##
## 'ReducedRrsWord' freely reduces the given RRS word and returns the result.
##
InstallGlobalFunction( ReducedRrsWord, function ( word )
local i, j, reduced;
# initialize the result.
reduced := [];
# run through the factors of the given word and cancel or add them.
j := 0;
for i in [ 1 .. Length( word ) ] do
if word[i] <> 0 then
if j > 0 and word[i] = - reduced[j] then j := j-1;
else j := j+1; reduced[j] := word[i]; fi;
fi;
od;
if j < Length( reduced ) then
reduced := reduced{ [1..j] };
fi;
return( reduced );
end );
#############################################################################
##
#M RelatorMatrixAbelianizedNormalClosureRrs( <G>, <H> ) . . relator matrix
#M . . . . . . . . . . . . for the abelianized normal closure of a subgroup
##
## 'RelatorMatrixAbelianizedNormalClosureRrs' uses the Reduced Reidemeister-
## Schreier method to compute a matrix of abelianized defining relators for
## the normal closure of a subgroup H of a finitely presented group G.
##
InstallGlobalFunction( RelatorMatrixAbelianizedNormalClosureRrs,
function ( G, H )
local F, # associated free group
fgens, # generators of <F>
hgens, # generators of <H>
fhgens, # their preimages in <F>
grels, # relators of <G>
krels, # relators of normal closure <N>
K, # factor group of F isomorphic to G/N
cosTable, # coset table of <G> by <N>
i, # loop variable
aug; # auxiliary coset table of <G> by <N>
# check the arguments to be a finitely presented group and a subgroup of
# that group.
if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then
Error( "<G> must be a finitely presented group" );
fi;
if not IsSubgroupFpGroup( H ) or FamilyObj( H ) <> FamilyObj( G ) then
Error( "<H> must be a subgroup of <G>" );
fi;
# get some local variables
F := FreeGroupOfFpGroup( G );
fgens := GeneratorsOfGroup( F );
grels := RelatorsOfFpGroup( G );
hgens := GeneratorsOfGroup( H );
fhgens := List( hgens, 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, fhgens );
K := F / krels;
# get the coset table of N in G by constructing the coset table of the
# trivial subgroup in K.
cosTable := CosetTable( K, TrivialSubgroup( K ) );
Info( InfoFpGroup, 1, "index is ", Length( cosTable[1] ) );
# # obsolete: No columns should be equal!
# for i in [ 1 .. Length( fgens ) ] do
# if IsIdenticalObj( cosTable[2*i-1], cosTable[2*i] ) then
# Error( "there is a bug in RelatorMatrixAbelianizedNormalClosureRrs" );
# fi; od;
# apply the Reduced Reidemeister-Schreier method to construct a coset
# table presentation of N.
aug := AugmentedCosetTableRrs( G, cosTable, 0, "_x" );
# determine a set of abelianized subgroup relators.
aug.subgroupRelators := RewriteAbelianizedSubgroupRelators( aug,
aug.groupRelators);
return aug.subgroupRelators;
end );
RelatorMatrixAbelianizedNormalClosure :=
RelatorMatrixAbelianizedNormalClosureRrs;
#############################################################################
##
#M RelatorMatrixAbelianizedSubgroupRrs( <G>, <H> ) . . . relator matrix for
#M RelatorMatrixAbelianizedSubgroupRrs( <G>, <costab> ) . . an abelianized
#M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . subgroup
##
## 'RelatorMatrixAbelianizedSubgroupRrs' uses the Reduced Reidemeister-
## Schreier method to compute a matrix of abelianized defining relators for
## a subgroup H of a finitely presented group G.
##
## Alternatively to a finitely presented group, the subgroup H may be given
## by its coset table.
##
InstallGlobalFunction( RelatorMatrixAbelianizedSubgroupRrs, function ( G, H )
local aug, table,i,j,vec,pres;
# check G to be a finitely presented group.
if not ( IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) ) then
Error( "<group> must be a finitely presented group" );
fi;
# check the second argument to be a subgroup or a coset table of G, and
# get the coset table in either case.
if not IsSubgroupFpGroup( H ) or FamilyObj( H ) <> FamilyObj( G ) then
# check the given table to be a legal coset table.
table := H;
CheckCosetTableFpGroup( G, table );
# ensure that it is standardized.
if not IsStandardized( table) then Print(
"#I Warning: the given coset table is not standardized,\n",
"#I a standardized copy will be used instead.\n" );
StandardizeTable( StructuralCopy( table ) );
fi;
else
# construct the coset table of H in G if it is not yet available.
if not HasCosetTableInWholeGroup( H ) then
Info( InfoFpGroup, 1, "index is ", IndexInWholeGroup( H ) );
fi;
table := CosetTableInWholeGroup( H );
fi;
# apply the Reduced Reidemeister-Schreier method to construct an
# augmented coset table of H.
aug := AugmentedCosetTableRrs( G, table, 0, "_x" );
# determine a set of abelianized subgroup relators.
aug.subgroupRelators := RewriteAbelianizedSubgroupRelators( aug,
aug.groupRelators);
if aug.subgroupRelators=fail then
# the abelianized rewriting in the kernel failed because the
# coefficients were to large.
return fail;
fi;
return aug.subgroupRelators;
end );
#############################################################################
##
#M RenumberTree( <augmented coset table> ) . . . . . renumber generators in
#M augmented coset table
##
## 'RenumberTree' is a subroutine of the Reduced Reidemeister-Schreier
## routines. It renumbers the generators such that the primary generators
## precede the secondary ones.
##
InstallGlobalFunction( RenumberTree, function ( aug )
local coFacTable, column, convert, defs, i, index, j, k, null, numcols,
numgens, tree, tree1, tree2, treelength, treesize;
# get factor table, generators, and tree.
coFacTable := aug.cosetFactorTable;
defs := aug.primaryGeneratorWords;
tree := aug.tree;
# truncate the tree, if necessary.
treelength := tree[3];
treesize := Length( tree[1] );
if treelength < treesize then
tree[1] := tree[1]{ [ 1 .. treelength ] };
tree[2] := tree[2]{ [ 1 .. treelength ] };
fi;
# initialize some local variables.
numcols := Length( coFacTable );
index := Length( coFacTable[1] );
numgens := Length( defs );
# establish a local renumbering list.
convert := ListWithIdenticalEntries( 2 * treelength + 1, 0 );
null := treelength + 1;
j := treelength + 1; k := numgens + 1;
i := treelength;
while i >= 1 do
if tree[1][i] = 0 then
k := k - 1; convert[null+i] := k; convert[null-i] := - k;
else
j := j - 1; convert[null+i] := j; convert[null-i] := - j;
tree[1][j] := tree[1][i]; tree[2][j] := tree[2][i];
fi;
i := i - 1;
od;
if convert[null+numgens] <> numgens then
# change the tree entries accordingly.
for i in [1..numgens] do
tree[1][i] := 0; tree[2][i] := 0;
od;
tree1 := tree[1]; tree2 := tree[2];
for j in [numgens+1..treelength] do
tree1[j] := convert[null+tree1[j]];
tree2[j] := convert[null+tree2[j]];
od;
# change the factor table entries accordingly.
for i in [1..numcols] do
# --------------
# obsolete condition: columns should never be equal.
# if i mod 2 = 1 or
# not IsIdenticalObj( coFacTable[i], coFacTable[i-1] ) then
if i > 1 and IsIdenticalObj( coFacTable[i], coFacTable[i-1] ) then
Error( "there is a bug in RenumberTree" ); fi;
# --------------
column := coFacTable[i];
for j in [1..index] do
column[j] := convert[null+column[j]];
od;
od;
fi;
end );
#############################################################################
##
#M RewriteAbelianizedSubgroupRelators( <aug>,<prels> ) . rewrite abelianized
#M . . . . . . . . . . . . . subgroup relators from an augmented coset table
##
## 'RewriteAbelianizedSubgroupRelators' is a subroutine of the Reduced
## Reidemeister-Schreier and the Modified Todd-Coxeter routines. It computes
## a set of subgroup relators from the coset factor table of an augmented
## coset table of type 0 and the relators <prels> of the parent group.
##
InstallGlobalFunction( RewriteAbelianizedSubgroupRelators,
function ( aug,prels )
local app2, coFacTable, cols, cosTable, factor, ggensi, grel,greli, i,
index, j, length, nums, numgens, numrels, p, rels, total, tree,
treelength, type,si,ei,nneg,word;
# check the type for being zero.
type := aug.type;
if type <> 0 then
Error( "type of augmented coset table is not zero" );
fi;
# initialize some local variables.
ggensi := List(aug.groupGenerators,i->AbsInt(LetterRepAssocWord(i)[1]));
cosTable := aug.cosetTable;
coFacTable := aug.cosetFactorTable;
index := Length( cosTable[1] );
tree := aug.tree;
treelength := tree[3];
numgens := tree[4];
total := numgens;
rels := List( [ 1 .. total ],
i -> ListWithIdenticalEntries( numgens, 0 ) );
numrels := 0;
# display some information.
Info( InfoFpGroup, 2, "index is ", index );
Info( InfoFpGroup, 2, "number of generators is ", numgens );
Info( InfoFpGroup, 2, "tree length is ", treelength );
# initialize the structure that is passed to 'ApplyRel2'
app2 := ListWithIdenticalEntries( 9, 0 );
app2[5] := type;
app2[6] := coFacTable;
app2[8] := tree;
# loop over all group relators
for greli in [1..Length(prels)] do
CompletionBar(InfoFpGroup,2,"Relator Loop:",greli/Length(prels));
grel:=prels[greli];
# get two copies of the group relator, one as a list of words in the
# factor table columns and one as a list of words in the coset table
# column numbers.
length := Length( grel );
if length>0 then
nums := [ ]; nums[2*length] := 0;
cols := [ ]; cols[2*length] := 0;
i:=0;
# for si in [ 1 .. NrSyllables(grel) ] do
# p:=2*Position(ggensi,GeneratorSyllable(grel,si));
# nneg:=ExponentSyllable(grel,si)>0;
# for ei in [1..AbsInt(ExponentSyllable(grel,si))] do
# i:=i+1;
# if nneg then
# nums[2*i] := p-1;
# nums[2*i-1] := p;
# cols[2*i] := cosTable[p-1];
# cols[2*i-1] := cosTable[p];
# else
# nums[2*i] := p;
# nums[2*i-1] := p-1;
# cols[2*i] := cosTable[p];
# cols[2*i-1] := cosTable[p-1];
# fi;
# od;
# od;
word:=LetterRepAssocWord(grel);
for si in [1..Length(word)] do
p:=2*Position(ggensi,AbsInt(word[si]));
i:=i+1;
if word[si]>0 then
nums[2*i]:=p-1;
nums[2*i-1]:=p;
cols[2*i]:=cosTable[p-1];
cols[2*i-1]:=cosTable[p];
else
nums[2*i]:=p;
nums[2*i-1]:=p-1;
cols[2*i]:=cosTable[p];
cols[2*i-1]:=cosTable[p-1];
fi;
od;
# loop over all cosets and determine the subgroup relators which are
# induced by the current group relator.
for i in [ 1 .. index ] do
# scan the ith coset through the current group relator and
# collect the factors of its invers (!) in rel.
numrels := numrels + 1;
if numrels > total then
total := total + 1;
rels[total] := ListWithIdenticalEntries( numgens, 0 );
fi;
app2[7] := rels[numrels];
app2[1] := 2;
app2[2] := i;
app2[3] := 2 * length - 1;
app2[4] := i;
if not ApplyRel2( app2, cols, nums ) then
return fail;
fi;
# add the resulting subgroup relator to rels.
numrels := AddAbelianRelator( rels, numrels );
od;
fi;
od;
CompletionBar(InfoFpGroup,2,"Relator Loop:",false);
# loop over all primary subgroup generators.
for j in [ 1 .. numgens ] do
CompletionBar(InfoFpGroup,2,"Generator Loop:",j/numgens);
# get two copies of the subgroup generator, one as a list of words in
# the factor table columns and one as a list of words in the coset
# table column numbers.
grel := aug.primaryGeneratorWords[j];
length := Length( grel );
if length>0 then
nums := [ ]; nums[2*length] := 0;
cols := [ ]; cols[2*length] := 0;
i:=0;
# for si in [ 1 .. NrSyllables(grel) ] do
# p:=2*Position(ggensi,GeneratorSyllable(grel,si));
# nneg:=ExponentSyllable(grel,si)>0;
# for ei in [1..AbsInt(ExponentSyllable(grel,si))] do
# i:=i+1;
# if nneg then
# nums[2*i] := p-1;
# nums[2*i-1] := p;
# cols[2*i] := cosTable[p-1];
# cols[2*i-1] := cosTable[p];
# else
# nums[2*i] := p;
# nums[2*i-1] := p-1;
# cols[2*i] := cosTable[p];
# cols[2*i-1] := cosTable[p-1];
# fi;
# od;
# od;
word:=LetterRepAssocWord(grel);
for si in [1..Length(word)] do
p:=2*Position(ggensi,AbsInt(word[si]));
i:=i+1;
if word[si]>0 then
nums[2*i]:=p-1;
nums[2*i-1]:=p;
cols[2*i]:=cosTable[p-1];
cols[2*i-1]:=cosTable[p];
else
nums[2*i]:=p;
nums[2*i-1]:=p-1;
cols[2*i]:=cosTable[p];
cols[2*i-1]:=cosTable[p-1];
fi;
od;
# scan coset 1 through the current subgroup generator and collect the
# factors of its invers (!) in rel.
numrels := numrels + 1;
if numrels > total then
total := total + 1;
rels[total] := ListWithIdenticalEntries( numgens, 0 );
fi;
app2[7] := rels[numrels];
app2[1] := 2;
app2[2] := 1;
app2[3] := 2 * length - 1;
app2[4] := 1;
if not ApplyRel2( app2, cols, nums ) then
return fail;
fi;
else
# trivial generator
numrels := numrels + 1;
if numrels > total then
total := total + 1;
rels[total] := ListWithIdenticalEntries( numgens, 0 );
fi;
fi;
# add as last factor the generator number j.
rels[numrels][j] := rels[numrels][j] + 1;
# add the resulting subgroup relator to rels.
numrels := AddAbelianRelator( rels, numrels );
od;
# reduce the relator list to its proper size.
if numrels < numgens then
for i in [ numrels + 1 .. numgens ] do
rels[i] := ListWithIdenticalEntries( numgens, 0 );
od;
numrels := numgens;
fi;
for i in [ numrels + 1 .. total ] do
Unbind( rels[i] );
od;
CompletionBar(InfoFpGroup,2,"Generator Loop:",false);
return rels;
end );
#############################################################################
##
#M RewriteSubgroupRelators( <aug>, <prels> [,<indices>] )
##
## 'RewriteSubgroupRelators' is a subroutine of the Reduced Reidemeister-
## Schreier and the Modified Todd-Coxeter routines. It computes a set of
## subgroup relators from the coset factor table of an augmented coset table
## and the relators <prels> of the parent group. It assumes that <aug>
## is an augmented coset table of type 2.
## If <indices> are given only those cosets are used
##
InstallGlobalFunction( RewriteSubgroupRelators,
function (arg)
local app2, coFacTable, cols, convert, cosTable, factor, ggensi,
greli,grel, i, index, j, last, length, nums, numgens, p, rel, rels,
treelength, type,si,nneg,ei,word,aug,prels,indices;
aug:=arg[1];
prels:=arg[2];
# check the type.
type := aug.type;
if type <> 2 then Error( "invalid type; it should be 2" ); fi;
# initialize some local variables.
ggensi := List(aug.groupGenerators,i->AbsInt(LetterRepAssocWord(i)[1]));
cosTable := aug.cosetTable;
coFacTable := aug.cosetFactorTable;
index := Length( cosTable[1] );
if Length(arg)=2 then
indices:=[1..index];
else
indices:=arg[3];
fi;
rels := [ ];
# initialize the structure that is passed to 'ApplyRel2'
app2 := ListWithIdenticalEntries( 9, 0 );
app2[5] := type;
app2[6] := coFacTable;
app2[7] := [ ]; app2[7][100] := 0;
# loop over all group relators
for greli in [1..Length(prels)] do
CompletionBar(InfoFpGroup,2,"Relator Loop:",greli/Length(prels));
grel:=prels[greli];
length := Length( grel );
if length > 0 then
# get two copies of the group relator, one as a list of words in the
# factor table columns and one as a list of words in the coset table
# column numbers.
nums := [ ]; nums[2*length] := 0;
cols := [ ]; cols[2*length] := 0;
i:=0;
# for si in [ 1 .. NrSyllables(grel) ] do
# p:=2*Position(ggensi,GeneratorSyllable(grel,si));
# nneg:=ExponentSyllable(grel,si)>0;
# for ei in [1..AbsInt(ExponentSyllable(grel,si))] do
# i:=i+1;
# if nneg then
# nums[2*i] := p-1;
# nums[2*i-1] := p;
# cols[2*i] := cosTable[p-1];
# cols[2*i-1] := cosTable[p];
# else
# nums[2*i] := p;
# nums[2*i-1] := p-1;
# cols[2*i] := cosTable[p];
# cols[2*i-1] := cosTable[p-1];
# fi;
# od;
# od;
word:=LetterRepAssocWord(grel);
for si in [1..Length(word)] do
p:=2*Position(ggensi,AbsInt(word[si]));
i:=i+1;
if word[si]>0 then
nums[2*i]:=p-1;
nums[2*i-1]:=p;
cols[2*i]:=cosTable[p-1];
cols[2*i-1]:=cosTable[p];
else
nums[2*i]:=p;
nums[2*i-1]:=p-1;
cols[2*i]:=cosTable[p];
cols[2*i-1]:=cosTable[p-1];
fi;
od;
# loop over all cosets and determine the subgroup relators which are
# induced by the current group relator.
for i in indices do
# scan the ith coset through the current group relator and
# collect the factors of its inverse (!) in rel.
app2[1] := 2;
app2[2] := i;
app2[3] := 2 * length - 1;
app2[4] := i;
ApplyRel2( app2, cols, nums );
# add the resulting subgroup relator to rels.
rel := app2[7];
last := Length( rel );
if last > 0 then
MakeCanonical( rel );
if Length( rel ) > 0 and not rel in rels then
AddSet( rels, Immutable(CopyRel( rel ) ));
fi;
fi;
od;
fi;
od;
CompletionBar(InfoFpGroup,2,"Relator Loop:",false);
# loop over all primary subgroup generators.
numgens := Length( aug.primaryGeneratorWords );
for j in [ 1 .. numgens ] do
CompletionBar(InfoFpGroup,2,"Generator Loop:",j/numgens);
# get two copies of the subgroup generator, one as a list of words in
# the factor table columns and one as a list of words in the coset
# table column numbers.
grel := aug.primaryGeneratorWords[j];
length := Length( grel );
if length>0 then
nums := [ ]; nums[2*length] := 0;
cols := [ ]; cols[2*length] := 0;
i:=0;
# for si in [ 1 .. NrSyllables(grel) ] do
--> --------------------
--> maximum size reached
--> --------------------
[ Dauer der Verarbeitung: 0.51 Sekunden
(vorverarbeitet)
]
|
