Identity automorphism acting nontrivially

[mfarrokhidg]

The following code shows a bug when working with the automorphism c. Here G=C32 x C4 x C2 is an abelian 2-group, a,b are commuting automorphisms of G and c=[a,b] is the identity automorphism. The last command shows the problem!

gap> f:=FreeGroup(3);;
gap> G:=f/[f.1^32,f.2^4,f.3^2,Comm(f.1,f.2),Comm(f.2,f.3),Comm(f.3,f.1)];;
gap> gens:=GeneratorsOfGroup(AutomorphismGroup(G));;
gap> a:=gens[6];;
gap> b:=gens[9];;
gap> c:=Comm(a,b);;
gap> Order(c)=1;
true
gap> G.2^c=G.2;
false

The codes are implemented in GAP 4.7.8 windows edition.

[olexandr-konovalov]

Thank you for reporting this - I can reproduce this in the current master branch too.

I've changed F to FreeGroup in the 1st line - probably it's your local shortcut to call it, but it doesn't work elsewhere.

[fingolfin]

Seems Comm is returning nonsense. Compare with this:

gap> d := a^-1*b^-1*a*b;   # Should be equivalent to Comm(a,b)
[ f2, (f3*f1^-1)^16*f3, f1^-1*f3 ] -> [ f2, (f3^-1*f1^-1)^16*f3^-1, f1^-1*f3 ]
gap> Order(d);
1
gap> GeneratorsOfGroup(G) = List(GeneratorsOfGroup(G), x -> x^d);
true
gap> GeneratorsOfGroup(G) = List(GeneratorsOfGroup(G), x -> x^c);
false

[fingolfin]

So while trying to find out what goes wrong here, I noticed that something really fishy is going on here. Various methods related to automorphisms of fp-groups seem to be broken. For example:

gap> redo:=hom -> GroupHomomorphismByImages(Source(how),Range(how),mapi[1],mapi[2]);;
gap> how := redo(gens[1]);;
gap> IsInjective(how);
false
gap> Elements(Kernel(hom));
[ <identity ...> ]

In the end, this boils down to a bug in IsomorphismFpGroupByGeneratorsNC. Here is a short way to reproduce it:

gap> f:=FreeGroup(3);;
gap> G:=f/[f.1^32,f.2^4,f.3^2,Comm(f.1,f.2),Comm(f.2,f.3),Comm(f.3,f.1)];;
gap> AssignGeneratorVariables(G);
gap> iso:=IsomorphismPcGroup(G);;
gap> gens:=[ (f3*f1^-1)^16*f3, f2*(((f3^-1*f1)^15*f3^-1)^2*f1*f3^-1)^16, f1^-1*f3 ];;
gap> Size(Group(List(gens,x->x^iso)));
256
gap> Size(Group(gens));
256
gap> fp:=IsomorphismFpGroupByGenerators(G,gens);;
gap> Size(Image(fp));
8

So, we pick a set of three generators, which generate the whole group G. But IsomorphismFpGroupByGenerators produces an fp group of order 8. Ouch.

At this point, I am not sure whether the bug in IsomorphismFpGroupByGenerators is the cause of the issue reported here, but debugging that lead me to it. We really need a bunch of tests in our test suite for computations like this!

[olexandr-konovalov]

Just to note - if the group is a p-group, AutPGrp package may be involved. This may be the case even if GAP is started with -A option, because morpheus.gi tries to load this package if it exists (even though AutPGrp is not listed as needed package for GAP).

[fingolfin]

@alex-konovalov That's a red herring: This group is abelian, and thus, AutomorphismGroupAbelianGroup is used. This happens before it even checks whether the group is a p-group.

[hulpke]

What IsomorphismFpGroupByGenerators does for fp groups is essentially a call to the MTC. If we do this call on its own the error also shows up:

gap> pres:=PresentationSubgroupMtc(G,Subgroup(G,gens));
<presentation with 3 gens and 4 rels of total length 12>
gap> f1:=FpGroupPresentation(pres);
<fp group on the generators [ _x1, _x2, _x3 ]>
gap> Size(f1);
8

Thus I'm inclined to blame the MTC.

This is old code, written by Volkmar Felsch and (because it is very FORTRANy never really touched by anyone else).

The error has been there in GAP4.4 already (that's the oldest version I have installed), I'm inclined to think it will go back to the earliest versions, maybe even GAP3.

Does someone have a version of GAP3 running and could check whether the bug occurs even there?

[frankluebeck]

@hulpke Yes, looks the same in GAP 3.4.4

[hulpke]

@frankluebeck Thank you very much! I think this is the oldest bug I've ever encountered in GAP, easily 20 years old.
The bad news is that this s a combination of library and kernel code, and I'm not sure if anyone understands what it does.

[markuspf]

On Tue, Oct 27, 2015 at 07:12:13PM -0700, Alexander Hulpke wrote:

@frankluebeck Thank you very much! I think this is the oldest bug I've ever encountered in GAP, easily 20 years old.
The bad news is that this s a combination of library and kernel code, and I'm not sure if anyone understands what it does.

How deep is this problem embedded in, say, the modified Todd-Coxeter
implementation (which I am assuming you are referring to when you say MTC)?

Maybe it's time to drag this code into the 21st century and rewrite it.

(I'll note though that I am not promising anything right now).

[markuspf]

I probably wanted to ask a different question here, namely, how entangled is the MTC implementation in other things in the library, and how huge a project would it be dragging parts of it into the 21st century.

[fingolfin]

Heh, I just had a look at the code, and found a function New_AugmentedCosetTableMtc, 500 lines, and completely unused. It is also the only place using GTC_GoodDefinitionSequence -- another 423 lines of effectively unused code. I think that by itself already says something about the state of the code ;-).

[frankluebeck]

Maybe this is an example where we should remove unmaintainable code, even if we loose some functionality (or mis-functionality)?

[hulpke]

@fingolfin This was a prior (unsuccessful) attempt of mine to start replacing the code. (I agree, it should not have made commits.)

[fingolfin]

@hulpke Ahhhh, OK, I see. Well, I did not even attempt to find out which code was added when, though that would have been easy enough. Using git log -G GTC_GoodDefinitionSequence on the old repository (which I am accessing via git, even though it is mercurial), it turns out you added that code 2010-06-01. Ah well :).

@frankluebeck Well, but the MTC is used by a lot of FP code, so we can't just remove it without breaking a lot of code, can we? (Maybe I am overestimating how much it is used). That said, MTC is not the most complicated of tasks... I wouldn't discount the possibility of understanding the code and fixing. I'd like to give this at least a try. After all, it can't be that bad, as it clearly gets correct results in many instances

[hulpke]

A smaller example seems to be:

  f:=FreeGroup(3);;
  G:=f/[f.1^4,f.2,f.1^2*f.3];;
  gens:=[ G.3*G.1^-1, G.2*(((G.3^-1*G.1)^15*G.3^-1)^2*G.1*G.3^-1)^16 ];;
  pres:=PresentationSubgroupMtc(G,Subgroup(G,gens));
  f1:=FpGroupPresentation(pres);

[hulpke]

@fingolfin @frankluebeck
I agree with Max that this is something we need to investigate. While the MTC itself is only used for group order and homomorphism on nonstandard generators, it interacts with coset table code that underlies much of the fp group functionality.
I tried to find a smaller example, which I just posted. I also noted that the second generator has length 1025 = 2^10+1.

Indeed, if I replace the subgroup generators in my reduced example by

gens:=[ G.3*G.1^-1, G.2*(((G.3^-1*G.1)^15*G.3^-1)^2*G.1*G.3^-1)^32 ];;

(i.e. replacing 16 by 32) the error changes to be order 2 (instead of 1 before versus a correct 4), while replacing 16 with 24 makes the bug go away makes me believe this is a powers-of-2 issue.

[Stefan-Kohl]

Continuing the original example, I get (in 4.8.2):

gap> f:=FreeGroup(3);;
gap> G:=f/[f.1^32,f.2^4,f.3^2,Comm(f.1,f.2),Comm(f.2,f.3),Comm(f.3,f.1)];;
gap> gens:=GeneratorsOfGroup(AutomorphismGroup(G));;
gap> a:=gens[6];;
gap> b:=gens[9];;
gap> c:=Comm(a,b);;
gap> Order(c)=1;
true
gap> G.2^c=G.2;
false
gap> q := G.2/G.2^c;
f2*f3^-1*f1
gap> Order(q); # here G.2/G.2^c seems to have order 32
32
gap> IsOne(c); # this test changes the order of G.2/G.2^c from 32 to 1
true
gap> q := G.2/G.2^c;
<identity ...>
gap> Order(q);
1

If this bug cannot be fixed before the next release, is it at least documented somewhere where users will read it?

[olexandr-konovalov]

It is documented here, together with other known bugs. I've assigned this to GAP 4.9.0 milestone to raise its priority (it doesn't look doable in a minor release).

[hulpke]

This problem is fixed in PR #843.