Manipulating AutomorphismGroup of FpGroups makes the system hang

[szoferi]

Observed behaviour

The following four commands, given consecutively (or as a 1-liner), makes the GAP interface hang.

G:=SmallGroup(14,2);
H:=SimplifiedFpGroup(Image(IsomorphismFpGroup(G)));
A:=AutomorphismGroup(H);
Size(A);

Changing A:=AutomorphismGroup(H); to A:=AutomorphismGroup(G); seems to be working fine. There is a related, similar issue:

G:=SmallGroup(10,2);
H:=SimplifiedFpGroup(Image(IsomorphismFpGroup(G)));
Elements(H);
A:=AutomorphismGroup(H);
Size(A);

The issue demonstrated in the second case does not arise if the line Elements(H); is removed. Also, for most other groups both code shown above just work fine.

Expected behaviour

Regarding the first case, I could imagine that some methods are not implemented. Here a warning/error could be appropriate. Regarding the second case, I am puzzled, to what extent removing Elemets(H); helps. Is this something related to issue #874?

Copy and paste GAP banner (to tell us about your setup)

GAP 4.8.6, 12-Nov-2016, build of 2016-11-12 16:12:02 (GMTST)
Architecture: i686-pc-cygwin-gcc-default32
(Same issue with 4.8.8 on x86_64-pc-linux-gnu-gcc-default64)

[fingolfin]

This has nothing to do with #874.

The first group G is a pc group, and thus very efficient methods for computing the automorphism groups are used. The groups H on the other hand are fp groups, and for those, roughly speaking things are much harder (and in general undecidable).

However, H here is abelian, and then a special case kicks in, which is meant to help in general for abelian groups, but it hurts here. Specifically, in AssignNiceMonomorphismAutomorphismGroup, we do this (where g=H and au=A):

  elif IsAbelian(g) then

    SetIsFinite(au,true);
    gens:=IndependentGeneratorsOfAbelianGroup(g);
    c:=[];
    for i in gens do
      c:=Union(c,Orbit(au,i));    # <- this is where the problem is!
    od;
    hom:=NiceMonomorphismAutomGroup(au,c,gens);

The problem is in that innocent orbit computation: we end up comparing words in an fp-group, which is hard, if one does not use some underlying information

gap> IsAbelian(g);
true
gap> au;
<group with 2 generators>
gap> IsOne(au.1);
true
gap> au.2;
[ (F1^-1*F2)^7, (F1^-1*F2)^2 ] -> [ (F1^-1*F2)^7, (F1^-1*F2)^6 ]
gap> gens[2];
(F1^-1*F2)^2
gap> gens[2]^au.2;
(F1^-1*F2)^6
gap> (gens[2]^au.2)^au.2;
(F2^-1*F1)^1326
gap> ((gens[2]^au.2)^au.2)^au.2;
(F1^-1*F2)^293046

Oops! That's bad. Esp. when you consider that IsOne(gens[2]^7) = true.

There are various ways that come to mind to work around this. But the first thing I'd like to understand is why those exponents grow so big... This involves using the modified Todd-Coxeter code. I wonder if we can somehow get that to produce "minimal" expressions?

Anyway, the person most qualified to comment on all this is @hulpke, so I hope he has time to chime in.

[hulpke]

As @fingolfin already wrote, basically any calculation in a finite fp group goes through a faithful representation. If you use only IsomorphismFpGroup, this function is clever enough to store the inverse map as a faithful representation. But currently the SimplifiedFpGroup step does not do so. The obvious fix is for SimplifiedFpGroup or IsomorphismSimplifiedFpGroup pulling through a known faithful representation.
I can easily add it if there is a desire to have it in the system.

[hulpke]

@fingolfin Multiplication in an fp group will only do the free cancellation, even if a faithful representation is known. You can set SetReducedMultiplication(g); and all elements created from that point will be reduced nicely.
The reason for not doing so by default is that it can be expensive in larger groups -- the lesson is basically that fp groups are not really the tool to work with small finite groups.

The multiplication happens in the MTC code, but ultimately it is an issue with multiplication alone.