[GAP Forum] "Knuth-Bendix Rewriting Confluent" hangs

[Robert Eckert]

Thank you for your quick reply.  I have tried with:
...
c2errs:=List(c2rels,i->ImageElm(c2fhom,i));
c2whom:=GroupHomomorphismByImages(c2full,c2weyl,GeneratorsOfGroup(c2full),GeneratorsOfGroup(c2weyl));
correct:=IsTrivial(c2errs);
c2real:= Kernel(c2whom);
c2phom:=GroupHomomorphismByImagesNC(c2pure,c2real,GeneratorsOfGroup(c2pure), List(c2gens,i->Image(c2fhom,i)));
c2gaps:=Kernel(c2phom);
complete:=IsTrivial(c2gaps);

and it ran until the evaluation of "complete":

gap> Read("a:\C2x.gap");time;correct;complete;
Error, the coset enumeration has defined more than 256000 cosets
 called from
TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
TryCosetTableInWholeGroup( H ) called from
CosetTableInWholeGroup( ImagesSet( iso, U ) ) called from
oper( super, sub ) called from
...
Entering break read-eval-print loop ...
type 'return;' if you want to continue with a new limit of 512000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit
brk> quit;
#I  Options stack has been reset
gap> correct;
false
gap> c2real;
Group(<fp, no generators known>)
gap> c2phom;
[ f1^2, f2^2, f2*f1^2*f2^-1, f1*f2^2*f1^-1 ] ->
[ f1^2, f2^2, f2*f1^2*f2^-1, f1*f2^2*f1^-1 ]
gap> c2gaps;
Group(<fp, no generators known>)
gap> complete;
Variable: 'complete' must have a value

gap> LogTo();


Here it is very disturbing that "correct" evaluated as "false" when I know
perfectly well it is "true".  Apparently, when it is asked if c2errs given
as a list is trivial, it doesn't check anything except whether the
word-spellings as given are null strings.  So I altered it to:

c2errs:=Subgroup(c2full,List(c2rels,i->ImageElm(c2fhom,i)));

and now it hangs on "correct:=IsTrivial(c2errs);" as before.

 On Mon, 26 Apr 2004, Alexander Hulpke wrote:
> The reason for this not just a shortcoming of GAP but there are fundamental
> algorithmic difficulties when working with finitely presented groups (the
> general unsolvability of the word problem).
Yes, I know this.  I gave up on using any general-purpose packages for
these groups a long time ago, and have written a monstrous special-purpose
program in C.  In any string of "letters" (of the free group) or
"generators" (of the pure) there are typically dozens of moves which look
simplifying (letter-switches via the braids, or applying known commutators
to the generators), all but one of which lead into cyclic futilities.
"Strait is the gate and narrow the way that leads to salvation":  I search
in every string for the one and only move that makes progress.  There is
no hope of avoiding cyclic futilities, only of recognizing when you are in
one and refusing to keep going around and around.

> GAP's algorithms for finitely presented groups mostly assume that subgroups
> are of finite index and might not terminate if subgroups have infinite
> index.
Is there any way to tell when the process simply requires a long time, or
if it is not guaranteed to terminate even in billions of years?  I know, I
know, this is Turing's Halting Problem.

> The recent 4.4 release comes with a new package FGA (free group algorithms)
> that provide some further functionality for subgroups of free groups that
> might help a bit, but I expect this package alone will not solve the
> problem.
Are there some useful new commands in there?  All I see written up is
"Centralizer".
>
> > c2gaps:=Kernel(c2phom);
>
> This again is unlikely to work. What might work is:
> - Compute a presentation for the kernel(c2whom) using
>   `IsomorphismFpGroupByGenerators'.
> - evaluate the relators in the generators of c2pure.
This gives for F4 a presentation with 1198 generators (the correct number
of independent generators is 24) and thousands of very long relations.  It
attempts to do Tietze reductions (purging the generator set of those where
a relation lets one be redefined in terms of the other):  this part only
takes my program seconds, but after 15 minutes GAP is nowhere near getting
down to the 24, and I am not sure if it would finish in a human lifespan.