|
|
|
|
Quelle sgpres.gi
Sprache: unbekannt
|
|
Spracherkennung für: .gi vermutete Sprache: Unknown {[0] [0] [0]} [Methode: Schwerpunktbildung, einfache Gewichte, sechs Dimensionen]
#############################################################################
##
## 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(fact ors),"\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
# 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 inverse (!) in rel.
app2[1] := 2;
app2[2] := 1;
app2[3] := 2 * length - 1;
app2[4] := 1;
ApplyRel2( app2, cols, nums );
# add as last factor the generator number j.
rel := app2[7];
last := Length( rel );
if last > 0 and rel[last] = - j then
last := last - 1;
rel := rel{ [1 .. last] };
else
last := last + 1;
rel[last] := j;
fi;
# add the resulting subgroup relator to rels.
if last > 0 then
MakeCanonical( rel );
if Length( rel ) > 0 and not rel in rels then
AddSet( rels, Immutable(CopyRel(rel)));
fi;
fi;
else
# trivial generator
AddSet(rels,[j]);
fi;
od;
CompletionBar(InfoFpGroup,2,"Generator Loop:",false);
# make mutable again to overwrite
rels:=List(rels,ShallowCopy);
# renumber the generators in the relators, if necessary.
numgens := Length( aug.subgroupGenerators );
treelength := Length( aug.tree[1] );
if numgens < treelength then
convert := aug.conversionList;
for rel in rels do
for i in [ 1 .. Length( rel ) ] do
if rel[i] > 0 then
rel[i] := convert[rel[i]];
else
rel[i] := - convert[-rel[i]];
fi;
od;
od;
fi;
return rels;
end );
#############################################################################
##
#M SortRelsSortedByStartGen(<relsGen>) sort the relators sorted by start gen
##
## 'SortRelsSortedByStartGen' sorts the relators lists sorted by starting
## generator to get better results of the Reduced Reidemeister-Schreier
## (this is not needed for the Felsch Todd-Coxeter).
##
InstallGlobalFunction( SortRelsSortedByStartGen,
function ( relsGen )
local less, list;
# 'less' defines an ordering on the triples [ nums, cols, startpos ]
less := function ( triple1, triple2 )
local diff, i, k, nums1, nums2;
if triple1[1][1] <> triple2[1][1] then
return triple1[1][1] < triple2[1][1];
fi;
nums1 := triple1[1]; nums2 := triple2[1];
i := triple1[3];
diff := triple2[3] - i;
k := i + nums1[1] + 2;
while i < k do
if nums1[i] <> nums2[i+diff] then
return nums1[i] < nums2[i+diff];
fi;
i := i + 2;
od;
return false;
end;
# sort the resulting lists
for list in relsGen do
Sort( list, less );
od;
end );
#############################################################################
##
#M SpanningTree( <coset table> ) . . . . . . . . . . . . . . . spanning tree
##
## 'SpanningTree' returns a spanning tree for the given coset table.
##
InstallGlobalFunction( SpanningTree, function ( cosTable )
local done, i, j, k, numcols, numrows, span1, span2;
# check the given argument to be a coset table.
if not ( IsList( cosTable ) and IsList( cosTable[1] ) ) then
Error( "argument must be a coset table" );
fi;
numcols := Length( cosTable );
numrows := Length( cosTable[1] );
for i in [ 2 .. numcols ] do
if not ( IsList( cosTable[i] ) and
Length( cosTable[i] ) = numrows ) then
Error( "argument must be a coset table" );
fi;
od;
# initialize the spanning tree.
span1 := [ -1, -2 .. -numrows ];
span2 := ListWithIdenticalEntries( numrows, 0 );
span1[1] := 0;
if numrows = 1 then return [ span1, span2 ]; fi;
# find the first occurrence in the table of each coset > 1.
done := [ 1 ];
for i in done do
for j in [ 1 .. numcols ] do
k := cosTable[j][i];
if span1[k] < 0 then
span1[k] := i; span2[k] := j;
Add( done, k );
if Length( done ) = numrows then
return [ span1, span2 ];
fi;
fi;
od;
od;
# you should never come here, the argument is not a valid coset table.
Error( "argument must be a coset table" );
end );
#############################################################################
##
## Extensions for rewriting and homomorphisms
##
#############################################################################
##
#F RewriteWord( <aug>, <word> )
##
InstallGlobalFunction(RewriteWord,function ( aug, word )
local cft, ct, w,l,c,i,g,ind;
# check the type.
Assert(1,aug.type=2);
# initialize some local variables.
ct := aug.cosetTable;
cft := aug.cosetFactorTable;
# translation table for group generators to numbers
if not IsBound(aug.transtab) then
# should do better, also cope with inverses
aug.transtab:=List(aug.groupGenerators,i->AbsInt(LetterRepAssocWord(i)[1]));
fi;
w:=[];
c:=1; # current coset
#for i in [1..NrSyllables(word)] do
# g:=GeneratorSyllable(word,i);
# e:=ExponentSyllable(word,i);
# if e<0 then
# ind:=2*aug.transtab[g];
# e:=-e;
# else
# ind:=2*aug.transtab[g]-1;
# fi;
# for j in [1..e] do
# # apply the generator, collect cofactor
# if cft[ind][c]<>0 then
# Add(w,cft[ind][c]); #cofactor
# fi;
# c:=ct[ind][c]; # new coset number
# od;
# od;
l:=LetterRepAssocWord(word);
for i in l do
g:=AbsInt(i);
if i<0 then
ind:=2*aug.transtab[g];
else
ind:=2*aug.transtab[g]-1;
fi;
# apply the generator, collect cofactor
if cft[ind][c]<>0 then
Add(w,cft[ind][c]); #cofactor
fi;
c:=ct[ind][c]; # new coset number
od;
# make sure we got back to start
if c<>1 then
return fail;
fi;
return w;
end);
#############################################################################
##
#F DecodedTreeEntry(<tree>,<imgs>,<nr>)
##
InstallGlobalFunction(DecodedTreeEntry,function(tree,imgs,nr)
local eval,t1,t2;
if IsBound(imgs[AbsInt(nr)]) then
if nr>0 then
return imgs[nr];
else
return imgs[-nr]^-1;
fi;
fi;
# as we might not want to construct the full tree, we'll be more specific
if not IsMutable(imgs) then
imgs:=ShallowCopy(imgs); # we will add locally
fi;
t1:=tree[1];
t2:=tree[2];
eval:=function(n)
if not IsBound(imgs[n]) then
imgs[n]:=eval(AbsInt(t1[n]))^SignInt(t1[n])
*eval(AbsInt(t2[n]))^SignInt(t2[n]);
fi;
return imgs[n];
end;
return eval(nr);
end);
#############################################################################
##
#F GeneratorTranslationAugmentedCosetTable(<aug>)
##
## decode the secondary generators as words in the primary generators, using
## the `.subgroupGenerators' and their subset `.primarySubgroupGenerators'.
InstallGlobalFunction(GeneratorTranslationAugmentedCosetTable,function(aug)
local tt,i,t1,t2,tn;
if not IsBound(aug.translationTable) then
if not IsBound(aug.primarySubgroupGenerators) then
aug.primarySubgroupGenerators:=
aug.subgroupGenerators{[1..Length(aug.primaryGeneratorWords)]};
fi;
# now expand the tree to get words for the secondary generators.
# the first elements are just the primary generators
tt:=ShallowCopy(aug.primarySubgroupGenerators);
t1:=aug.tree[1];
t2:=aug.tree[2];
tn:=aug.treeNumbers;
if Length(tn)>0 then
for i in [Length(tt)+1..Maximum(tn)] do
tt[i]:=tt[AbsInt(t1[i])]^SignInt(t1[i])
*tt[AbsInt(t2[i])]^SignInt(t2[i]);
od;
fi;
aug.translationTable:=Immutable(tt);
fi;
return aug.translationTable;
end);
#############################################################################
##
#F SecondaryGeneratorWordsAugmentedCosetTable(<aug>)
##
InstallGlobalFunction(SecondaryGeneratorWordsAugmentedCosetTable,function(aug)
if not IsBound(aug.secondaryWords) then
aug.secondaryWords:=Immutable(
List(GeneratorTranslationAugmentedCosetTable(aug),i->
MappedWord(i,aug.primarySubgroupGenerators,aug.primaryGeneratorWords)));
fi;
return aug.secondaryWords;
end);
#############################################################################
##
#F CopiedAugmentedCosetTable(<aug>)
##
## returns a new augmented coset table, equal to the old one. The
## components of this new table are immutable, but new components may be
## added.
## (This function is needed to have different homomorphisms share the same
## augmented coset table data. It must not be applied to augmented coset
## tables which are not of type 2.)
InstallGlobalFunction(CopiedAugmentedCosetTable,function(aug)
local t,j;
if IsBound(aug.isNewAugmentedTable) then
t:=rec(isNewAugmentedTable:=true);
for j in
[ "A", "aug", "ct", "defcount", "from", "homgenims", "homgens",
"index", "n", "offset", "primaryImages", "rels","one","useAddition",
"secondary", "secount", "secondaryImages", "subgens" ] do
if IsBound(aug.(j)) then
t.(j):=aug.(j);
fi;
od;
else
# old version
t:=rec(
isAugmentedCosetTable:=true,
type:=aug.type,
tableType:=aug.tableType,
groupGenerators:=aug.groupGenerators,
groupRelators:=aug.groupRelators,
cosetTable:=aug.cosetTable,
cosetFactorTable:=aug.cosetFactorTable,
primaryGeneratorWords:=aug.primaryGeneratorWords,
tree:=aug.tree,
treeNumbers:=aug.treeNumbers,
numberOfSubgroupGenerators:=aug.numberOfSubgroupGenerators,
nameOfSubgroupGenerators:=aug.nameOfSubgroupGenerators,
subgroupGenerators:=aug.subgroupGenerators
);
if IsBound(aug.secondaryWords) then
t.secondaryWords:=Immutable(aug.secondaryWords);
fi;
if IsBound(aug.conversionList) then
t.conversionList:=aug.conversionList;
fi;
if IsBound(aug.primarySubgroupGenerators) then
t.primarySubgroupGenerators:=Immutable(aug.primarySubgroupGenerators);
fi;
if IsBound(aug.subgroupRelators) then
t.subgroupRelators:=Immutable(aug.subgroupRelators);
fi;
if IsBound(aug.translationTable) then
t.translationTable:=Immutable(aug.translationTable);
fi;
fi;
return t;
end);
# New implementation of the Modified Todd-Coxeter (MTC) algorithm, based on
# Chapter 5 of the "Handbook of Computational Group Theory", by Derek F.
# Holt (referred # to as "Handbook" from here on). Function names after the
# NEWTC_ agree with those of sections 5.2, 5.3 of the Handbook.
BindGlobal( "NEWTC_AddDeduction", function(list,ded)
if not ded in list then
Add(list,ded);
fi;
end );
# the tables produced internally are indexed at rec.offset+k for generator
# number k, that is in the form ...,-2,-1,empty,1,2,...
# This avoids lots of even/od decisions and the cost of the empty list is
# neglegible.
BindGlobal( "NEWTC_Compress", function(DATA,purge)
local ct,c,a,b,offset,x,to,p,dw,doa,aug;
doa:=DATA.augmented;
dw:=IsBound(DATA.with);
ct:=DATA.ct;
if doa then
aug:=DATA.aug;
fi;
p:=DATA.p;
offset:=DATA.offset;
c:=0;
to:=[];
for a in [1..DATA.n] do
if p[a]=a then
c:=c+1;
to[a]:=c;
if c<>a then
for x in DATA.A do
if ct[x+offset][a]<>0 then;
b:=ct[x+offset][a];
if b=a then b:=c;fi;
ct[x+offset][c]:=b;
ct[-x+offset][b]:=c;
if doa then
# transfer augemented entry
aug[x+offset][c]:=aug[x+offset][a];
fi;
else
# clear out
ct[x+offset][c]:=0;
if doa then
Unbind(aug[x+offset][c]);
fi;
fi;
od;
if dw then
DATA.with[c]:=DATA.with[a];
b:=DATA.from[a];
while b<>to[b] do
b:=to[b];
od;
DATA.from[c]:=b;
fi;
fi;
else
b:=a;
while p[b]<>b do
b:=p[b];
od;
to[a]:=b;
fi;
od;
if purge then
for x in DATA.A do
for a in [Length(ct[x+offset]),Length(ct[x+offset])-1..c+1] do
Unbind(ct[x+offset][a]);
if doa then
Unbind(aug[x+offset][a]);
fi;
od;
od;
if dw then
for a in [Length(DATA.with),Length(DATA.with)-1..c+1] do
Unbind(DATA.with[a]);
Unbind(DATA.from[a]);
od;
fi;
fi;
if IsBound(DATA.ds) then
for x in DATA.ds do
a:=to[x[1]];
while x[1]<>a do
x[1]:=a;
a:=to[a];
od;
od;
Assert(2,Maximum(List(DATA.ds,x->x[1]))<=c);
fi;
DATA.n:=c;
DATA.p:=[1..DATA.n];
if doa then
DATA.pp:=ListWithIdenticalEntries(DATA.n,DATA.one);
fi;
DATA.dead:=0;
end );
BindGlobal( "NEWTC_Define", function(DATA,i,a)
# both augmented or not
local c,o,n,j,au;
n:=DATA.n;
o:=DATA.offset;
c:=DATA.ct;
n:=n+1;
DATA.n:=n;
if n>DATA.limit then
if ValueOption("quiet")=true then return fail;fi;
Error( "the coset enumeration has defined more ",
"than ", DATA.limit, " cosets\n");
DATA.limit:=DATA.limit*2;
DATA.limtrigger:=Int(9/10*DATA.limit);
fi;
DATA.p[n]:=n;
# clear out
for j in DATA.A do
c[j+o][n]:=0;
od;
c[o+a][i]:=n;
c[o-a][n]:=i;
if DATA.augmented then
DATA.aug[o+a][i]:=DATA.one;
DATA.aug[o-a][n]:=DATA.one;
DATA.pp[n]:=DATA.one;
fi;
NEWTC_AddDeduction(DATA.deductions,[i,a]);
#if IsBound(DATA.ds) then Add(DATA.ds,[i,a]); fi;
DATA.defcount:=DATA.defcount+1;
if IsBound(DATA.with) then
if DATA.with[i]=-a then Error("bleh!");fi;
DATA.with[n]:=a;
DATA.from[n]:=i;
fi;
#ForAny(DATA.A,x->ForAny([1..Length(c[x+o])],y->not
# IsBound(c[x+o][y]))) then
# Error("hehe");
#fi;
return true; # indicating no quiet fail
end );
BindGlobal( "NEWTC_Coincidence", function(DATA,a,b)
local Rep,Merge,ct,offset,l,q,i,c,x,d,p,mu,nu;
if a=b then return;fi;
Rep:=function(kappa)
local lambda,rho,mu;
lambda:=kappa;
rho:=p[lambda];
while rho<>lambda do
lambda:=rho;rho:=p[lambda];
od;
mu:=kappa;rho:=p[mu];
while rho<>lambda do
p[mu]:=lambda;mu:=rho;rho:=p[mu];
od;
return lambda;
end;
Merge:=function(k,a)
local phi,psi,mu,nu;
phi:=Rep(k);
psi:=Rep(a);
if phi<>psi then
mu:=Minimum(phi,psi);
nu:=Maximum(phi,psi);
p[nu]:=mu;
l:=l+1;
q[l]:=nu;
DATA.dead:=DATA.dead+1;
fi;
end;
ct:=DATA.ct;
offset:=DATA.offset;
p:=DATA.p;
l:=0;
q:=[];
Merge(a,b);i:=1;
while i<=l do
c:=q[i];
i:=i+1;
#RemoveSet(DATA.omega,c);
for x in DATA.A do
if ct[x+offset][c]<>0 then
d:=ct[x+offset][c];
ct[x+offset][c]:=0;
ct[-x+offset][d]:=0;
mu:=Rep(c);
nu:=Rep(d);
if ct[x+offset][mu]<>0 then
Merge(nu,ct[x+offset][mu]);
elif ct[-x+offset][nu]<>0 then
Merge(mu,ct[-x+offset][nu]);
else
ct[x+offset][mu]:=nu;
ct[-x+offset][nu]:=mu;
NEWTC_AddDeduction(DATA.deductions,[mu,x]);
fi;
fi;
od;
od;
end );
BindGlobal( "NEWTC_ModifiedCoincidence", function(DATA,a,b,w)
local MRep,MMerge,ct,offset,l,q,i,c,x,d,p,pp,mu,nu,aug,v,Sekundant;
# decide whether secondary generators will be introduced
Sekundant:=function(w)
local i,p,c,ws;
if Length(w)<=1 or DATA.useAddition then
return w;
fi;
ws:=Set(w);
repeat
c:=false;
for i in [Length(DATA.subgens)+1..DATA.secount] do
if ForAll(DATA.secondary[i],x->x in ws) then
p:=PositionSublist(w,DATA.secondary[i]);
while p<>fail do
w:=WordProductLetterRep(w{[1..p-1]},
[i],w{[p+Length(DATA.secondary[i])..Length(w)]});
ws:=Set(w);
c:=true;
p:=PositionSublist(w,DATA.secondary[i],Maximum(0,p-Length(DATA.secondary[i])));
od;
fi;
od;
until c=false;
DATA.secount:=DATA.secount+1;
DATA.secondary[DATA.secount]:=w;
return [DATA.secount];
end;
MRep:=function(kappa)
local lambda,rho,mu,s;
lambda:=kappa;
rho:=p[lambda];
if rho=lambda then return lambda; fi;
s:=DATA.s; # re-used array to trace back compression path
while rho<>lambda do
s[rho]:=lambda;
lambda:=rho;rho:=p[lambda];
od;
rho:=s[lambda];
while rho<>kappa do
mu:=rho;
rho:=s[mu];
p[rho]:=lambda;
if DATA.useAddition then
pp[rho]:=pp[rho]+pp[mu];
else
pp[rho]:=Sekundant(WordProductLetterRep(pp[rho],pp[mu]));
fi;
od;
return lambda;
end;
MMerge:=function(k,a,w)
local phi,psi;
phi:=MRep(k);
psi:=MRep(a);
if phi>psi then
p[phi]:=psi;
if DATA.useAddition then
pp[phi]:=-pp[k]+w+pp[a];
else
pp[phi]:=Sekundant(WordProductLetterRep(-Reversed(pp[k]),w,pp[a]));
fi;
l:=l+1;
q[l]:=phi;
DATA.dead:=DATA.dead+1;
elif psi>phi then
p[psi]:=phi;
if DATA.useAddition then
pp[psi]:=-pp[a]-w+pp[k];
else
pp[psi]:=Sekundant(WordProductLetterRep(-Reversed(pp[a]),-Reversed(w),pp[k]));
fi;
l:=l+1;
q[l]:=psi;
DATA.dead:=DATA.dead+1;
fi;
end;
ct:=DATA.ct;
aug:=DATA.aug;
offset:=DATA.offset;
p:=DATA.p;
pp:=DATA.pp;
l:=0;
q:=[];
MMerge(a,b,w);i:=1;
while i<=l do
c:=q[i];
i:=i+1;
for x in DATA.A do
if ct[x+offset][c]<>0 then
d:=ct[x+offset][c];
ct[-x+offset][d]:=0;
mu:=MRep(c);
nu:=MRep(d);
if ct[x+offset][mu]<>0 then
if DATA.useAddition then
v:=-pp[d]-aug[x+offset][c]+pp[c]+aug[x+offset][mu];
else
v:=WordProductLetterRep(-Reversed(pp[d]),-Reversed(aug[x+offset][c]),
pp[c],aug[x+offset][mu]);
fi;
MMerge(nu,ct[x+offset][mu],v);
elif ct[-x+offset][nu]<>0 then
if DATA.useAddition then
v:=-pp[c]+aug[x+offset][c]+pp[d]+aug[-x+offset][nu];
else
v:=WordProductLetterRep(-Reversed(pp[c]),aug[x+offset][c],
pp[d],aug[-x+offset][nu]);
fi;
MMerge(mu,ct[-x+offset][nu],v);
else
ct[x+offset][mu]:=nu;
ct[-x+offset][nu]:=mu;
if DATA.useAddition then
v:=-pp[c]+aug[x+offset][c]+pp[d];
aug[x+offset][mu]:=v;
aug[-x+offset][nu]:=-v;
else
v:=WordProductLetterRep(-Reversed(pp[c]),aug[x+offset][c],pp[d]);
aug[x+offset][mu]:=v;
aug[-x+offset][nu]:=-Reversed(v);
fi;
NEWTC_AddDeduction(DATA.deductions,[mu,x]);
fi;
fi;
od;
od;
# pp is not needed any longer
for i in q do
Unbind(pp[i]);
od;
end );
# superseded by kernel function TC_QUICK_SCAN, left here for debugging purposes.
BindGlobal( "NEWTC_QuickScanLibraryVersion", function(c,offset,alpha,w)
local f,b,r,i,j;
f:=alpha;i:=1;
r:=Length(w);
# forward scan
while i<=r and c[w[i]+offset][f]<>0 do
f:=c[w[i]+offset][f];
i:=i+1;
od;
if i>r then
if f<>alpha then
w[1]:=i;w[2]:=f;
return true;
fi;
return false;
fi;
#backward scan
b:=alpha;j:=r;
while j>=i and c[-w[j]+offset][b]<>0 do
b:=c[-w[j]+offset][b];
j:=j-1;
od;
if j<=i then
w[1]:=i;w[2]:=f;w[3]:=j;w[4]:=b;
return true;
fi;
return false;
end );
BindGlobal( "NEWTC_Scan", function(DATA,alpha,w)
local c,offset,f,b,r,i,j,t;
c:=DATA.ct;
offset:=DATA.offset;
t:=TC_QUICK_SCAN(c,offset,alpha,w,DATA.scandata);
if t=false then return; fi;
r:=Length(w);
i:=DATA.scandata[1]; # result of forward scan
f:=DATA.scandata[2];
if i>r then
if f<>alpha then
NEWTC_Coincidence(DATA,f,alpha);
fi;
return;
fi;
j:=DATA.scandata[3]; # result of backward scan
b:=DATA.scandata[4];
if j<i then
NEWTC_Coincidence(DATA,f,b);
elif j=i then
# deduction
c[w[i]+offset][f]:=b;
c[-w[i]+offset][b]:=f;
NEWTC_AddDeduction(DATA.deductions,[f,w[i]]);
fi;
return;
# the following is the original, old, code including loops. It is left here
# for debugging purposes
# f:=alpha;i:=1;
# r:=Length(w);
# # forward scan
# while i<=r and c[w[i]+offset][f]<>0 do
# f:=c[w[i]+offset][f];
# i:=i+1;
# od;
# if i>r then
# if f<>alpha then
# Coincidence(DATA,f,alpha);
# fi;
# return;
# fi;
#
# #backward scan
# b:=alpha;j:=r;
# while j>=i and c[-w[j]+offset][b]<>0 do
# b:=c[-w[j]+offset][b];
# j:=j-1;
# od;
# if j<i then
# Coincidence(DATA,f,b);
# elif j=i then
# # deduction
# c[w[i]+offset][f]:=b;
# c[-w[i]+offset][b]:=f;
# Add(DATA.deductions,[f,w[i]]);
# fi;
end );
BindGlobal( "NEWTC_ModifiedScan", function(DATA,alpha,w,y)
local c,offset,f,b,r,i,j,fp,bp,t;
#Info(InfoFpGroup,3,"MS",alpha,w,y,"\n");
c:=DATA.ct;
offset:=DATA.offset;
t:=TC_QUICK_SCAN(c,offset,alpha,w,DATA.scandata);
if t=false then return; fi;
f:=alpha;i:=1;
fp:=DATA.one;
r:=Length(w);
# forward scan
while i<=r and c[w[i]+offset][f]<>0 do
if DATA.useAddition then
fp:=fp+DATA.aug[w[i]+offset][f];
else
fp:=WordProductLetterRep(fp,DATA.aug[w[i]+offset][f]);
fi;
f:=c[w[i]+offset][f];
i:=i+1;
od;
if i>r then
if f<>alpha then
if DATA.useAddition then
NEWTC_ModifiedCoincidence(DATA,f,alpha,-fp+y);
else
NEWTC_ModifiedCoincidence(DATA,f,alpha,WordProductLetterRep(-Reversed(fp),y));
fi;
fi;
return;
fi;
#Info(InfoFpGroup,3,"MS2\n");
#backward scan
b:=alpha;j:=r;
bp:=y;
while j>=i and c[-w[j]+offset][b]<>0 do
if DATA.useAddition then
bp:=bp+DATA.aug[-w[j]+offset][b];
else
bp:=WordProductLetterRep(bp,DATA.aug[-w[j]+offset][b]);
fi;
b:=c[-w[j]+offset][b];
j:=j-1;
od;
if j<i then
if DATA.useAddition then
NEWTC_ModifiedCoincidence(DATA,f,b,-fp+bp);
else
NEWTC_ModifiedCoincidence(DATA,f,b,WordProductLetterRep(-Reversed(fp),bp));
fi;
elif j=i then
# deduction
c[w[i]+offset][f]:=b;
c[-w[i]+offset][b]:=f;
if DATA.useAddition then
DATA.aug[w[i]+offset][f]:=-fp+bp;
DATA.aug[-w[i]+offset][b]:=-bp+fp;
else
DATA.aug[w[i]+offset][f]:=WordProductLetterRep(-Reversed(fp),bp);
DATA.aug[-w[i]+offset][b]:=WordProductLetterRep(-Reversed(bp),fp);
fi;
NEWTC_AddDeduction(DATA.deductions,[f,w[i]]);
fi;
end );
BindGlobal( "NEWTC_ScanAndFill", function(DATA,alpha,w)
local c,offset,f,b,r,i,j;
c:=DATA.ct;
offset:=DATA.offset;
r:=Length(w);
f:=alpha;i:=1;
b:=alpha;j:=r;
while i<=j do
# forward scan
while i<=r and c[w[i]+offset][f]<>0 do
f:=c[w[i]+offset][f];
i:=i+1;
od;
if i>r then
if f<>alpha then
NEWTC_Coincidence(DATA,f,alpha);
fi;
return;
fi;
#backward scan
while j>=i and c[-w[j]+offset][b]<>0 do
b:=c[-w[j]+offset][b];
j:=j-1;
od;
if j<i then
NEWTC_Coincidence(DATA,f,b);
elif j=i then
# deduction
c[w[i]+offset][f]:=b;
c[-w[i]+offset][b]:=f;
NEWTC_AddDeduction(DATA.deductions,[f,w[i]]);
return;
else
NEWTC_Define(DATA,f,w[i]);
fi;
od;
end );
BindGlobal( "NEWTC_ModifiedScanAndFill", function(DATA,alpha,w,y)
local c,offset,f,b,r,i,j,fp,bp;
c:=DATA.ct;
offset:=DATA.offset;
f:=alpha;i:=1;
fp:=DATA.one;
r:=Length(w);
b:=alpha;j:=r;
bp:=y;
while i<=j do #N
# forward scan
while i<=r and c[w[i]+offset][f]<>0 do
if DATA.useAddition then
fp:=fp+DATA.aug[w[i]+offset][f];
else
fp:=WordProductLetterRep(fp,DATA.aug[w[i]+offset][f]);
fi;
f:=c[w[i]+offset][f];
i:=i+1;
od;
if i>r then
if f<>alpha then
if DATA.useAddition then
NEWTC_ModifiedCoincidence(DATA,f,alpha,-fp+y);
else
NEWTC_ModifiedCoincidence(DATA,f,alpha,
WordProductLetterRep(-Reversed(fp),y));
fi;
fi;
return;
fi;
#backward scan
while j>=i and c[-w[j]+offset][b]<>0 do
if DATA.useAddition then
bp:=bp+DATA.aug[-w[j]+offset][b];
else
bp:=WordProductLetterRep(bp,DATA.aug[-w[j]+offset][b]);
fi;
b:=c[-w[j]+offset][b];
j:=j-1;
od;
if j<i then
if DATA.useAddition then
NEWTC_ModifiedCoincidence(DATA,f,b,-fp+bp);
else
NEWTC_ModifiedCoincidence(DATA,f,b,WordProductLetterRep(-Reversed(fp),bp));
fi;
elif j=i then
# deduction
c[w[i]+offset][f]:=b;
c[-w[i]+offset][b]:=f;
if DATA.useAddition then
DATA.aug[w[i]+offset][f]:=-fp+bp;
DATA.aug[-w[i]+offset][b]:=-bp+fp;
else
DATA.aug[w[i]+offset][f]:=WordProductLetterRep(-Reversed(fp),bp);
DATA.aug[-w[i]+offset][b]:=WordProductLetterRep(-Reversed(bp),fp);
fi;
NEWTC_AddDeduction(DATA.deductions,[f,w[i]]);
return;
else
NEWTC_Define(DATA,f,w[i]);
fi;
od;
end );
BindGlobal( "NEWTC_ProcessDeductions", function(DATA)
# both augmented and not
local ded,offset,pair,alpha,x,p,w;
ded:=DATA.deductions;
offset:=DATA.offset;
p:=DATA.p;
while Length(ded)>0 do
pair:=Remove(ded);
alpha:=pair[1];x:=pair[2];
if p[alpha]=alpha then
for w in DATA.ccr[x+offset] do
if DATA.augmented then
NEWTC_ModifiedScan(DATA,alpha,w,DATA.one);
else
NEWTC_Scan(DATA,alpha,w);
fi;
if p[alpha]<alpha then
break; # coset has been eliminated
fi;
od;
fi;
# separate 'if' check, as the `break;` only ends innermost loop
if p[alpha]=alpha then
alpha:=DATA.ct[x+offset][alpha]; # beta
if p[alpha]=alpha then
# AH, 9/13/18: It's R^c_{x^-1}, so -x
for w in DATA.ccr[offset-x] do
if DATA.augmented then
NEWTC_ModifiedScan(DATA,alpha,w,DATA.one);
else
NEWTC_Scan(DATA,alpha,w);
fi;
if p[alpha]<alpha then
break; # coset has been eliminated
fi;
od;
fi;
fi;
od;
end );
BindGlobal( "NEWTC_DoCosetEnum", function(freegens,freerels,subgens,aug,trace)
local m,offset,rels,ri,ccr,i,r,ct,A,a,w,n,DATA,p,dr,
oldead,with,collapse,j,from,pp,PERCFACT,ap,ordertwo;
# indicate at what change threshold display of coset Nr. should happen
PERCFACT:=ValueOption("display");
if not IsInt(PERCFACT) then PERCFACT:=100; fi;
m:=Length(freegens);
A:=List(freegens,LetterRepAssocWord);
Assert(0,ForAll(A,x->Length(x)=1 and x[1]>0));
if List(A,x->x[1])<>[1..m] then
Error("noncanonical generator order not yet possible");
fi;
offset:=m+1;
rels:=ShallowCopy(freerels);
rels:=Filtered(freerels, x -> Length(x) > 0);
SortBy(rels,Length);
ri:=Union(rels,List(rels,x->x^-1));
ri:=List(ri,LetterRepAssocWord);
SortBy(ri,Length);
A:=Concatenation([1..m],-[1..m]);
# are generators known to be of order 2?
ordertwo:=[];
for i in [1..Length(ri)] do
w:=ri[i];
if Length(w)=2 and Length(Set(w))=1 then
Unbind(ri[i]); # not needed any longer
a:=AbsInt(w[1]);
if not a in ordertwo then
Info(InfoFpGroup,1,"Generator ",a," has order 2");
AddSet(ordertwo,a);
A:=Filtered(A,x->x<>-a);
fi;
fi;
od;
ri:=Compacted(ri);
# cyclic conjugates, sort by first letter
ccr:=List([1..2*m+1],x->[]);
for i in ri do
r:=i;
while not r in ccr[offset+r[1]] do
# replace order 2 gens
for j in [1..Length(r)] do
if -r[j] in ordertwo then r[j]:=-r[j];fi;
od;
AddSet(ccr[offset+r[1]],Immutable(r));
r:=Concatenation(r{[2..Length(r)]},r{[1]});
od;
od;
# coset table in slightly different format: row (offset+x) is for
# generator x
ct:=List([1..offset+m],x->[0]);Unbind(ct[offset]);
n:=1;
p:=[1];
collapse:=[];
DATA:=rec(ct:=ct,p:=p,ccr:=ccr,rels:=List(rels,LetterRepAssocWord),
subgens:=subgens,
subgword:=List(subgens,x->LetterRepAssocWord(UnderlyingElement(x))),
n:=n,offset:=offset,A:=A,limit:=2^23,
deductions:=[],dead:=0,defcount:=0,
ordertwo:=ordertwo,s:=[],
# a global list for the kernel scan function to return 4 variables
scandata:=[0,0,0,0]);
i:=ValueOption("limit");
if i<>fail and Int(i)<>fail then
DATA.limit:=i;
fi;
DATA.limtrigger:=Int(9/10*DATA.limit);
if aug<>false then
DATA.isCyclicMtcTable:=false;
DATA.useAddition:=false;
if ValueOption("cyclic")<>fail and Length(subgens)=1 then
DATA.isCyclicMtcTable:=true;
DATA.isAbelianizedMtcTable:=false;
DATA.useAddition:=true;
DATA.one:=0;
elif ValueOption("abelian")<>fail then
DATA.isAbelianizedMtcTable:=true;
DATA.one:=ListWithIdenticalEntries(Length(subgens),0);
DATA.useAddition:=true;
else
DATA.isAbelianizedMtcTable:=false;
DATA.one:=[];
fi;
aug:=List([1..offset+m],x->[]);Unbind(aug[offset]);
pp:=[DATA.one];
DATA.aug:=aug;
DATA.pp:=pp;
DATA.secondary:=[];
DATA.secount:=Length(subgens); # last to be used
DATA.augmented:=true;
else
DATA.augmented:=false;
fi;
for a in ordertwo do
DATA.ct[offset-a]:=DATA.ct[offset+a];
if DATA.augmented then
DATA.aug[offset-a]:=DATA.aug[offset+a];
fi;
od;
if trace<>false then
with:=[0]; # generator by which a coset was defined
DATA.with:=with;
from:=[0];
DATA.from:=from;
fi;
Info( InfoFpGroup, 2, " \t defined\t deleted\t alive\t\t maximal");
for w in [1..Length(subgens)] do
if DATA.augmented then
if DATA.isCyclicMtcTable then
NEWTC_ModifiedScanAndFill(DATA,1,DATA.subgword[w],1);
elif DATA.isAbelianizedMtcTable then
i:=ShallowCopy(DATA.one);
i[w]:=1;
NEWTC_ModifiedScanAndFill(DATA,1,DATA.subgword[w],i);
else
NEWTC_ModifiedScanAndFill(DATA,1,DATA.subgword[w],[w]);
fi;
else
NEWTC_ScanAndFill(DATA,1,DATA.subgword[w]);
fi;
od;
NEWTC_ProcessDeductions(DATA);
# words we want to trace early (as they might reduce the number of
# definitions
if trace<>false then
for w in trace do
if IsList(w[1]) then
w:=w[1]; # get word from value
fi;
repeat
i:=1;
ap:=1;
while ap<=Length(w) do
a:=w[ap];
if ct[a+offset][i]=0 then
dr:=NEWTC_Define(DATA,i,a);
if dr=fail then return fail;fi;
NEWTC_ProcessDeductions(DATA);
#i:=p[i]; # in case there is a change
ap:=Length(w)+10;
fi;
i:=ct[a+offset][i];
ap:=ap+1;
od;
until ap=Length(w)+1;
od;
fi;
i:=1;
while i<=DATA.n do
for a in A do
if p[i]=i then
if ct[a+offset][i]=0 then
dr:=NEWTC_Define(DATA,i,a);
if dr=fail then return fail;fi;
oldead:=DATA.dead;
NEWTC_ProcessDeductions(DATA);
if PERCFACT*(DATA.dead-oldead)>DATA.n then
if DATA.n>1000 then
Info( InfoFpGroup, 2, "\t", DATA.defcount, "\t\t", DATA.dead,
"\t\t", DATA.n-DATA.dead, "\t\t", DATA.n );
fi;
if IsBound(DATA.with) then
# collapse -- find collapse word
# in two different ways (as they can differ after compression)
# first trace through the coset table, this uses the prior
# reductions
j:=i;
while j<>p[j] do
j:=p[j];
od;
w:=[a]; # last letter added
while j<>1 do
Assert(2,j=p[j]);
Add(w,with[j]);
Assert(2,0<>ct[-with[j]+offset][j]);
j:=ct[-with[j]+offset][j]; # unapply this generator
od;
# free reduce -- partial collapse can lead to not free cancellation
# and fix order
w:=Reversed(FreelyReducedLetterRepWord(w));
#w1:=w;
j:=PositionProperty(collapse,x->x[1]=w);
if j=fail then
Add(collapse,[w,DATA.dead-oldead]); # word that caused a collapse
else
collapse[j][2]:=Maximum(collapse[j][2],DATA.dead-oldead);
fi;
# now use the `from' list (which does not collapse under
# coincidences, only under compression) and not the coset table,
# as it # keeps the old definition order, not yet using coincidence
j:=i;
w:=[a]; # last letter added
while j<>1 do
Add(w,with[j]);
j:=from[j];
od;
# free reduce -- partial collapse can lead to not free
# cancellation and fix order
w:=Reversed(FreelyReducedLetterRepWord(w));
j:=PositionProperty(collapse,x->x[1]=w);
if j=fail then
Add(collapse,[w,DATA.dead-oldead]); # word caused collapse
else
collapse[j][2]:=Maximum(collapse[j][2],DATA.dead-oldead);
fi;
Info(InfoFpGroup,3,"collapse ",DATA.dead-oldead);
fi;
fi;
fi;
fi;
od;
# conditions for compression: Over half the table used, and
if 2*DATA.n>DATA.limit and
# at least 33% trash (4=1+1/0.33)
( 4*DATA.dead>DATA.n or
# over limtrigger and at least 2% (55=1+1/0.02) trash
(51*DATA.dead>DATA.n and DATA.n>DATA.limtrigger) ) then
Info( InfoFpGroup, 2, "\t", DATA.defcount, "\t\t", DATA.dead,
"\t\t", DATA.n-DATA.dead, "\t\t", DATA.n );
i:=Number([1..i],x->p[x]=x);
NEWTC_Compress(DATA,false);
p:=DATA.p;
if DATA.augmented then
pp:=DATA.pp;
fi;
if DATA.n>DATA.limtrigger then
DATA.limtrigger:=Maximum(DATA.limit-1,DATA.n+2);
fi;
fi;
i:=i+1;
od;
NEWTC_Compress(DATA,true); # always compress at the end
DATA.index:=DATA.n;
Info(InfoFpGroup,3,"found index ",DATA.index);
if Length(collapse)>0 then
Info(InfoFpGroup,3,DATA.defcount," definitions");
# which collapses gave at least 1%
collapse:=Filtered(collapse,x->x[2]*PERCFACT>DATA.n and not x in trace and
# not prefix of any trace
not ForAny(trace,y->y[1]{[1..Minimum(Length(x),Length(y[1]))]}=x
# or proper prefix of another in collapse
and not ForAny(collapse,y->Length(y)>Length(x) and
y{[1..Length(x)]}=x)));
if Length(collapse)>0 then
# give list for improvement
# type is c_ollapse
return
rec(type:="c",collapse:=collapse,limit:=DATA.limit,defcount:=DATA.defcount,data:=DATA);
fi;
fi;
return rec(type:="t",limit:=DATA.limit,defcount:=DATA.defcount,data:=DATA);
end );
#freegens,fgreerels,subgens,doaugmented,trace
# Options: limit, quiet (return fail if run out of space)
# cyclic (if given and 1 generator do special case of cyclic rewriting)
InstallGlobalFunction(NEWTC_CosetEnumerator,function(arg)
local freegens,freerels,subgens,aug,trace,e,ldc,up,bastime,start,bl,bw,first,timerFunc,addtrace;
timerFunc := GET_TIMER_FROM_ReproducibleBehaviour();
freegens:=arg[1];
freerels:=arg[2];
subgens:=arg[3];
aug:=IsBound(arg[4]);
trace:=IsBound(arg[5]);
if aug<>false then
aug:=arg[4];
fi;
if aug<>false then
# if augmented, optimize by default
if trace=false then
trace:=[];
else
trace:=arg[5];
fi;
elif trace<>false then
trace:=arg[5];
fi;
start:=timerFunc();
if aug and trace=false then
e:=NEWTC_DoCosetEnum(freegens,freerels,subgens,aug,trace);
if e=fail then return fail;fi;
else
e:=NEWTC_DoCosetEnum(freegens,freerels,subgens,false,trace);
if e=fail then return fail;fi;
bastime:=timerFunc()-start;
bl:=e.defcount;
bw:=[];
ldc:=infinity;
up:=0;
start:=timerFunc();
first:=true;
while trace<>false and e.type="c" and (up<=2 or
2*(timerFunc()-start)<=bastime) do
#up<=2 do
ldc:=e.defcount;
if first=true then
first:=e.defcount;
Info(InfoFpGroup,1,"optimize definition sequence");
else
Info(InfoFpGroup,2,"Now ",e.defcount," defs");
fi;
addtrace:=Filtered(e.collapse,x->x[2]>2);
Append(trace,addtrace);
SortBy(trace,x->[Length(x[1]),-x[2]]);
e:=NEWTC_DoCosetEnum(freegens,freerels,subgens,false,trace:
# that's what we had last time -- no need to whine
limit:=e.limit);
if e=fail then return fail;fi;
if e.defcount/bl<98/100 then
bl:=e.defcount;
bw:=ShallowCopy(trace);
fi;
# 2% improvement threshold
if 102/100*e.defcount<=ldc then
up:=0;
start:=timerFunc();
else
up:=up+1;
fi;
od;
if first<>true then
Info(InfoFpGroup,1,"Reduced ",first," definitions to ",e.defcount);
fi;
if aug then
# finally do the augmented with best
e:=NEWTC_DoCosetEnum(freegens,freerels,subgens,true,bw:
# that's what we had last time -- no need to whine
limit:=e.limit);
if e=fail then return fail;fi;
fi;
fi;
if not aug then
# return the ordinary coset table in standard formatting
up:=[];
for start in [1..Length(freegens)] do
Add(up,start+e.data.offset);
Add(up,-start+e.data.offset);
od;
ldc:=e.data.ct{up};
StandardizeTable(ldc);
return ldc;
fi;
aug:=rec(isNewAugmentedTable:=true,
isCyclicMtcTable:=e.data.isCyclicMtcTable,
isAbelianizedMtcTable:=e.data.isAbelianizedMtcTable,
useAddition:=e.data.useAddition,
n:=e.data.n,
A:=e.data.A,
index:=e.data.index,
rels:=e.data.rels,
ct:=e.data.ct,
one:=e.data.one,
aug:=e.data.aug,
defcount:=e.data.defcount,
secount:=e.data.secount,
secondary:=e.data.secondary,
subgens:=e.data.subgens,
subgword:=e.data.subgword,
offset:=e.data.offset
);
if IsBound(e.data.from) then
aug.from:=e.data.from;
fi;
return aug;
end);
BindGlobal( "NEWTC_Rewrite", function(arg)
local DATA,start,w,offset,c,i,j;
DATA:=arg[1];
start:=arg[2];
w:=arg[3];
offset:=DATA.offset;
c:=DATA.one;
i:=start;
for j in w do
if DATA.useAddition then
c:=c+DATA.aug[j+offset][i];
else
c:=WordProductLetterRep(c,DATA.aug[j+offset][i]);
fi;
i:=DATA.ct[j+offset][i];
od;
if Length(arg)>3 and arg[4]<>i then
Error("Trace did not end at expected coset");
fi;
return c;
end );
DeclareGlobalName("NEWTC_ReplacedStringCyclic");
BindGlobal( "NEWTC_ReplacedStringCyclic", function(s,r,cyc)
local p,new,start,half;
if Length(s)<Length(r) or Length(r)=0 then
return s;
fi;
p:=PositionSublist(s,r);
if p<>fail then
new:=s{[1..p-1]};
start:=p+Length(r);
p:=PositionSublist(s,r,start);
while p<>fail do
if start>Length(s) or Length(new)=0 or Last(new)<>-s[start] then
Append(new,s{[start..p-1]});
else
new:=WordProductLetterRep(new,s{[start..p-1]});
fi;
start:=p+Length(r);
p:=PositionSublist(s,r,start);
od;
if start>Length(s) or Length(new)=0 or Last(new)<>-s[start] then
Append(new,s{[start..Length(s)]});
else
new:=WordProductLetterRep(new,s{[start..Length(s)]});
fi;
else
new:=s;
fi;
if Length(r)=1 or cyc=false then
return new; # no overlap or so possible
fi;
# Now cyclic reduction means that r overlaps tail to front. Thus either
# the second half of r occurs in the front or the front half of r occurs
# in the end of s.
half:=QuoInt(Length(r),2)+1;
p:=PositionSublist(new,r{[half..Length(r)]});
if p<>fail and p<half then
if new{[1..p-1]}=r{[half-p+1..half-1]}
and new{[Length(new)-half+p+1..Length(new)]}=r{[1..half-p]} then
new:=new{[Length(r)-half+p+1..Length(new)-half+p]};
fi;
elif p<>fail then
# second half arises later. Does also first half arise -- if so we need
# to go through once more
if new{[p-half+1..p-1]}=r{[1..half-1]} then
new:=NEWTC_ReplacedStringCyclic(new,r,cyc);
return new;
fi;
fi;
p:=PositionSublist(new,r{[1..half-1]});
if p<>fail and p>=Length(new)-Length(r)+1
and new{[p..Length(new)]}=r{[1..Length(new)-p+1]}
and p>Length(new)+p-1 and
new{[1..Length(r)-Length(new)+p-1]}=r{[Length(new)-p+2..Length(r)]} then
new:=new{[Length(r)-Length(new)+p..p-1]};
fi;
return new;
end );
InstallGlobalFunction(NEWTC_CyclicSubgroupOrder,function(DATA)
local rels,r,i,w;
rels:=0;
r:=NEWTC_Rewrite(DATA,1,DATA.subgword[1])-1;
rels:=Gcd(rels,r);
for i in [1..DATA.n] do
for w in DATA.rels do
r:=NEWTC_Rewrite(DATA,i,w);
rels:=Gcd(rels,r);
od;
od;
return rels;
end);
BindGlobal( "NEWTC_AbelianizedRelatorsSubgroup", function(DATA)
local rels,r,i,w,subnum;
subnum:=Length(DATA.subgens);
rels:=[];
for i in [1..subnum] do
r:=ShallowCopy(NEWTC_Rewrite(DATA,1,DATA.subgword[i]));
r[i]:=r[i]-1;
if not IsZero(r) and not r in rels and not -r in rels then
AddSet(rels,r);
fi;
od;
for i in [1..DATA.n] do
CompletionBar(InfoFpGroup,2,"Coset Loop: ",i/DATA.n);
for w in DATA.rels do
r:=NEWTC_Rewrite(DATA,i,w);
if not IsZero(r) and not r in rels and not -r in rels then
AddSet(rels,r);
fi;
od;
od;
CompletionBar(InfoFpGroup,2,"Coset Loop: ",false);
return rels;
end );
#############################################################################
##
#M RelatorMatrixAbelianizedSubgroupMtc( <G>, <H> ) . . . . . relator matrix
#M . . . . . . . . . . . . . . . . . . . . . . for an abelianized subgroup
##
## 'RelatorMatrixAbelianizedSubgroupMtc' uses the Modified Todd-Coxeter
## coset representative enumeration method to compute a matrix of abelian-
## ized defining relators for a subgroup H of a finitely presented group G.
##
InstallGlobalFunction( RelatorMatrixAbelianizedSubgroupMtc,
function ( G, H )
local aug,rels;
# 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;
# do a Modified Todd-Coxeter coset representative enumeration to
# construct an augmented coset table of H.
aug := NEWTC_CosetEnumerator(FreeGeneratorsOfFpGroup(G),RelatorsOfFpGroup(G),GeneratorsOfGroup(H),true,false:abelian:=true);
# determine a set of abelianized subgroup relators.
rels:=NEWTC_AbelianizedRelatorsSubgroup(aug);
return rels;
end );
# DATA, [parameter,string]
# parameter is:
# 0: Full reduction
# 1: Do a quick reduction without trying to eliminate all secondary gens.
# -1: No relators
InstallGlobalFunction(NEWTC_PresentationMTC,function(arg)
local DATA,rels,i,j,k,w,f,r,s,fam,ri,a,offset,rset,re,stack,pres,
subnum,parameter,str,wordefs;
DATA:=arg[1];
if Length(arg)=1 then
parameter:=0;
else
parameter:=arg[2];
fi;
if Length(arg)>2 then
str:=arg[3];
else
str:="%";
fi;
offset:=DATA.offset;
subnum:=Length(DATA.subgens);
rels:=[];
for i in [1..subnum] do
r:=WordProductLetterRep(NEWTC_Rewrite(DATA,1,DATA.subgword[i]),[-i]);
if Length(r)>0 then
Add(rels,r);
fi;
od;
stack:=[];
if parameter<>-1 then
for i in [1..DATA.n] do
CompletionBar(InfoFpGroup,2,"Coset Loop: ",i/DATA.n);
for w in DATA.rels do
r:=NEWTC_Rewrite(DATA,i,w);
MakeCanonical(r);
ri:=Length(r);
# reduce with others
for j in rels do
r:=NEWTC_ReplacedStringCyclic(r,j,true);
r:=NEWTC_ReplacedStringCyclic(r,-Reversed(j),true);
od;
Info(InfoFpGroup,3,"Relatorlen ",ri,"->",Length(r));
if Length(r)>0 then
Add(stack,r);
while Length(stack)>0 do
r:=Remove(stack);
ri:=-Reversed(r);
rset:=Set([r,ri]);
# reduce others
j:=1;
while j<=Length(rels) do
s:=rels[j];
for re in rset do;
s:=NEWTC_ReplacedStringCyclic(s,re,true);
od;
if not IsIdenticalObj(s,rels[j]) then
if Length(s)>0 then
Add(stack,s);
fi;
rels:=WordProductLetterRep(rels{[1..j-1]},rels{[j+1..Length(rels)]});
else
j:=j+1;
fi;
od;
Add(rels,r);
SortBy(rels,Length);
# does it occur in the augmented table?
for a in DATA.A do
for j in [1..DATA.n] do
s:=DATA.aug[a+offset][j];
if Length(s)>=Length(r) then
for re in rset do
# NOT cyclic replace!
s:=NEWTC_ReplacedStringCyclic(s,re,false);
od;
DATA.aug[a+offset][j]:=s;
fi;
od;
od;
od;
fi;
od;
od;
CompletionBar(InfoFpGroup,2,"Coset Loop: ",false);
fi;
# add definitions of secondary generators
wordefs:=[];
for i in [subnum+1..DATA.secount] do
r:=WordProductLetterRep(DATA.secondary[i],[-i]);
Add(rels,r);
wordefs[i]:=r;
od;
if ForAll(str,IsString) and DATA.secount >=Length(str) then
r:=ShallowCopy(str);
s:=0;
while Length(r)<DATA.secount do
s:=s+1;
Add(r,Concatenation("__xtra__",String(s)));
od;
f:=FreeGroup(r);
else
f:=FreeGroup(DATA.secount,str);
fi;
fam:=FamilyObj(One(f));
rels:=List(rels,x->AssocWordByLetterRep(fam,x));
pres:=PresentationFpGroup(f/rels);
TzInitGeneratorImages(pres);
TzOptions(pres).protected:=subnum;
TzOptions(pres).printLevel:=InfoLevel(InfoFpGroup);
if parameter=1 then
TzSearch(pres);
TzOptions(pres).lengthLimit:=pres!.tietze[TZ_TOTAL]+1;
fi;
TzOptions(pres).eliminationsLimit:=5;
# did any generators end up eliminated?
for i in Flat(Difference(List(GeneratorsOfGroup(f),LetterRepAssocWord),
List(pres!.generators,LetterRepAssocWord))) do
for j in [1..Length(wordefs)] do
k:=1;
while IsBound(wordefs[j]) and k<=Length(wordefs[j]) do
if wordefs[j][k]=i then
wordefs[j]:=Concatenation(wordefs[j]{[1..k-1]},
pres!.imagesOldGens[i],
wordefs[j]{[k+1..Length(wordefs[j])]});
elif wordefs[j][k]=-i then
wordefs[j]:=Concatenation(wordefs[j]{[1..k-1]},
-Reversed(pres!.imagesOldGens[i]),
wordefs[j]{[k+1..Length(wordefs[j])]});
fi;
k:=k+1;
od;
od;
od;
TzGoElim(pres,subnum,wordefs);
if IsEvenInt(parameter) and Length(GeneratorsOfPresentation(pres))>subnum then
Error("did not eliminate properly");
# warn:=true;
# # Help Tietze with elimination
# bad:=Reversed(List(GeneratorsOfPresentation(pres)
# {[subnum+1..Length(GeneratorsOfPresentation(pres))]},
# x->LetterRepAssocWord(x)[1]));
# for i in bad do
# r:=DATA.secondary[i];
# re:=true;
# while re do
# s:=[];
# re:=false;
# for j in r do
# if AbsInt(j)>subnum then
# re:=true;
# if j>0 then
# Append(s,DATA.secondary[j]);
# else
# Append(s,-Reversed(DATA.secondary[-j]));
# fi;
# else
# Add(s,j);
# fi;
# od;
# Info(InfoFpGroup,2,"Length =",Length(s));
# r:=s;
# if warn and Length(s)>100*Sum(rels,Length) then
# warn:=false;
# Error(
# "Trying to eliminate all auxiliary generators might cause the\n",
# "size of the presentation to explode. Proceed at risk!");
# fi;
# od;
# r:=AssocWordByLetterRep(fam,Concatenation(r,[-i]));
# AddRelator(pres,r);
# #TzSearch(pres); Do *not* search, as this might kill the relator we
# #just added.
# TzEliminate(pres,i);
# od;
# Assert(0,Length(GeneratorsOfPresentation(pres))=subnum);
fi;
r:=List(GeneratorsOfPresentation(pres){[1..subnum]},
x->LetterRepAssocWord(x)[1]);
pres!.primarywords:=r;
r:=List(GeneratorsOfPresentation(pres){
[subnum+1..Length(GeneratorsOfPresentation(pres))]},
x->LetterRepAssocWord(x)[1]);
pres!.secondarywords:=r;
return pres;
end);
#############################################################################
##
#M PresentationSubgroupMtc(<G>, <H> [,<string>] [,<print level>] ) . . . . .
#M Tietze record for a subgroup
##
## 'PresentationSubgroupMtc' uses the Modified Todd-Coxeter coset represent-
## ative enumeration 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\"'.
##
InstallGlobalFunction( PresentationSubgroupMtc,function ( arg )
local G,H,string,DATA,i;
# 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;
# initialize the generators name string and the print level.
string := "_x";
# get the optional parameters.
for i in [ 3 .. 4 ] do
if Length( arg ) >= i then
if IsString( arg[i] ) then string := arg[i];
else
Error( "optional parameter must be a string or an integer" );
fi;
fi;
od;
DATA:=NEWTC_CosetEnumerator(FreeGeneratorsOfFpGroup(G),
RelatorsOfFpGroup(G),
List(GeneratorsOfGroup(H),UnderlyingElement),true,
# for compatibility, do not try the optimization
false);
return NEWTC_PresentationMTC(DATA,0,string);
end);
#####################################
# The following code is not used any longer and is relics of the old Mtc
# implementation.
[Dauer der Verarbeitung: 0.67 Sekunden, vorverarbeitet 2026-05-06]
|
2026-05-26
|
|
|
|
|
