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

[Alexander Hulpke]

Dear Robert Eckert,

> The problem I am attempting is verifying the correctness and completeness
> of free-mod-relations for the sporadic pure-braid groups:  here "full" is

> 
> c2:=FreeGroup(2);
> c2brds:=[c2.1*c2.2*c2.1*c2.2*c2.1^-1*c2.2^-1*c2.1^-1*c2.2^-1];
> The correctness question is whether c2rels is in the normal closure of
> c2brds.  Asking for NormalClosure(c2,c2brds) gives a Reidemeister-Schreier
> process with infinite coset traversal:  old versions crashed with "coset
> enumeration exceeds 256000" while 4.4 just refuses "No Method Found".  The

(I doubt that this command as given would have worked under 4.3), the version
NormalClosure(c2,Subgroup(c2,c2brds));
starts but similarly runs into memory problems.

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). One example of tyhis is the
error message after defining 256000 cosets, which is intended to keep a
program from running out of memory. (It is possible to continue the
calculation by typing `return'; however in this case, this is unlikely to
help).

GAP's algorithms for finitely presented groups mostly assume that subgroups
are of finite index and might not terminate if subgroups have infinite
index. 
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.

> c2sqrs:=[c2.1^2,c2.2^2];
>  a12:=c2.1*c2.1;
>  a23:=c2.2*c2.2;
>  a13:=c2.2*c2.1*c2.1*c2.2^-1;
>  b23:=c2.1*c2.2*c2.2*c2.1^-1;
> c2gens:=[a12,a23,a13,b23];
> r1:=Comm(a23,b23*a12*a13);
> r2:=Comm(a13,a23*b23*a12);
> r3:=Comm(a12,a13*a23*b23);
> c2rels:=[r1,r2,r3];
> c2full:=c2/c2brds;
> c2weyl:=c2/Union(c2brds,c2sqrs);
> c2pure:=Subgroup(c2,c2gens)/c2rels;
> c2fhom:=GroupHomomorphismByImages(c2,c2full,GeneratorsOfGroup(c2),GeneratorsOfGroup(c2full));
> c2errs:=Image(c2fhom,c2rels);

`Image' forms a set of the images of the elements and thus has to test
equality. This is what takes time. If you use:
  c2errs:=List(c2rels,i->ImageElm(c2fhom,i));
you will get a result in no time.

> correct:=IsTrivial(c2errs);

This is a very hard command. You ask for the fact whether elements given as
words are trivial. GAP will start a Knuth-Bendix (performance can be
improved using the `kbmag' package that uses an external binary), but again
(due to the fundamental difficulties mentioned above) one can only hope for,
but not necessarily guarantee termination in limited time/memory.

> c2whom:=GroupHomomorphismByImages(c2full,c2weyl,GeneratorsOfGroup(c2full),GeneratorsOfGroup(c2weyl));
> c2phom:=GroupHomomorphismByImages(c2pure,Kernel(c2whom),GeneratorsOfGroup(c2pure),Image(c2fhom,c2gens));

Again, here I would compute the image of the elements separately. Also
`GroupHomomorphismByImages' will test the homomorphism property which
requires knowledge of relators -- the NC version just assumes that the map
is a homomorphism:
c2phom:=GroupHomomorphismByImagesNC(c2pure,Kernel(c2whom),
  GeneratorsOfGroup(c2pure),List(c2gens,i->Image(c2fhom,i)));

> 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.

However then again you have a triviality test, which might run into the same
problems with the Knuth Bendix. You will likely have to involve some theory
or hand calculations.

Best wishes,

  Alexander Hulpke