membership test for groups of automorphisms

[ThomasBreuer]

The following happens in GAP 4.12.2 as well as in the current master branch.

gap> F:= FreeGroup( 2 );;
gap> gens:= GeneratorsOfGroup( F );;
gap> x:= gens[1];;  y:= gens[2];;
gap> rels:= [ x^-3*y^-3*x^-1*y*x^-2,
>             x*y^-1*x^-1*y*x^-1*y^-1*x^3*y^-1,
>             x*y^-1*x^-1*y^2*x^-2*y^-1*x^2 ];;
gap> G:= F / rels;;
gap> A:= AutomorphismGroup( G );
<group with 5 generators>
gap> elms:= AsList(A);;
gap> Size( A );
16
gap> x:= elms[4];
[ f1*f2^-102, f2^35 ] -> [ f1, f2 ]
gap> x^-1 in A;
true
gap> time;
127
gap> x in A;
true
gap> time;
184758

(Well, I get about 55 seconds in the master branch for the computation of x in A, but that is also quite slow.)

As far as I see, the reason for this problem is as follows. The memberhsip test notices that NiceMonomorphism( A ) can be used, in the sense that computing the image of x under it and then the preimage of this element will yield the given x if and only if x is in A. NiceMonomorphism( A ) is an action homomorphism. Computing the image of x means to compute the induced permutation on the elements of G, and mapping an element g of G with x means to apply x to g. Apparently the words representing the group elements become very long this way, although G is very small.

When I modify the PermutationOp method in question such that the image pnt gets replaced by the stored element before mapping it, the runtime of the membership test in the master branch goes down to 8 seconds. (This is not really a solution for the problem, elms[14] in A is then still a problem --but elms[i]^-1 in A works for all i.)

By the way, why are the generators of the automorphism group not given as maps on the generators, since dealing with their inverses seems to be easier (see above)? And why do so large exponents occur in the words that define x, if it is known in advance that G has exponent 8?

[hulpke]

The issue is basically with working with a finitely presented group. When working with known finite groups, it is much more efficient to transition to a permutation or Pc representation.

Overall, I find it amazing that the automorphism group calculation actually works.

Part of what is hapening is that arithmetic in Fp groups by default accumulates products and does not reduce. This is done because reduction in Fp groups can be problematic in general. A user however can turn it on for a particular (known to be small) group by calling

SetReducedMultiplication(G);

With this command given after creating G, the calculation is instantaneous.

The nice monomorphism in this particular case might be a regular action. In general, it is a permutation action on the cosets of a subgroup, that can be shown to be faithful. The maybe strange generators on which the automorphisms are given are likely pre-images of generators chosen in the nice group. Maybe they are actually equal to the original generators, and this just happens through the pre-image (or inverse mapping) mechanism or permutation groups.

I strongly suspect that any attempt to make this more intelligent is likely to falter at larger examples, or will cause problems in other situations. Finitely presented groups are subtle.

[ThomasBreuer]

Thanks @ahulpke.

Yes, in general it is advisable to switch from a f. p. group to something better if one wants to do involved computations such as automorphism group or character table, and to map back to the f.p. group if necessary. And I think that it would be a bad idea to do this switch automatically, and to hide this from the user.

The hint to try SetReducedMultiplication is dangerous. You write that one should do this "after creating G", and strange things may happen if one calls the function later, see below. If there is no way to make this safer then we should at least add a warning to the documentation of SetReducedMultiplication.

Here is an example how things can go wrong.

1. Defining data.

gap> F:= FreeGroup( "x", "y" );;
gap> gens:= GeneratorsOfGroup( F );;
gap> x:= gens[1];; y:= gens[2];;
gap> rels:= [x^-3*y^-3*x^-1*y*x^-2,
>            x*y^-1*x^-1*y*x^-1*y^-1*x^3*y^-1,
>            x*y^-1*x^-1*y^2*x^-2*y^-1*x^2];;

2. Call SetReducedMultiplication early.

gap> G:= F / rels;;
gap> SetReducedMultiplication( G );  # set this *immediately after creating G*
gap> iso:= IsomorphismPermGroup( G );;
gap> PG:= Range( iso );;
gap> PA:= AutomorphismGroup( PG );;
gap> gen1:= GeneratorsOfGroup( G )[1]^iso;
(3,4,6,8,10,9,7,5)
gap> PreImage( iso, gen1^One( PA ) );
x

3. Call SetReducedMultiplication too late.

gap> G:= F / rels;;
gap> iso:= IsomorphismPermGroup( G );;
gap> PG:= Range( iso );;
gap> PA:= AutomorphismGroup( PG );;
gap> gen1:= GeneratorsOfGroup( G )[1]^iso;
(3,4,6,8,10,9,7,5)
gap> PreImage( iso, gen1^One( PA ) );
x
gap> SetReducedMultiplication( G );  # set this *too late*
gap> PreImage( iso, gen1^One( PA ) );
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `MappedWord' on 3 arguments at /.../lib/methsel2.g:249 called from
[...]

[hulpke]

@ThomasBreuer Yes, that is why it is not done automatically. I think the question is ultimately one of user interface: How does a user indicate that they want to have an Fp group as just a smallish finite group, rather than investigating a potentially infinite beast.