another problem with finitely presented groups

[ThomasBreuer]

(The problem was found by @thofma, see oscar-system/Oscar.jl/issues/4167.)

Consider the following input.

F:= FreeGroup( "x", "y" );
gens:= GeneratorsOfGroup( F );
x:= gens[1];
y:= gens[2];
rels:= [ y^-2*x^-4*y^-2*x^4, y^4*x^-1*y*x^5*y^-5*x^-4*y^4*x ];
G:= F / rels;

In GAP 4.13.1, we get the following.

gap> Size( G );
36
gap> time;
35220
gap> Elements( G );
Error, the coset enumeration has defined more than 4096000 cosets
[...]

Creating the group G again and asking for Elements( G ) without first computing the order runs for a long time without result.

In the master branch, the situation is different. We get the same error message if we first compute the group order, but if we don't then the following happens.

gap> Elements(G);
[ <identity ...>, x^7, x^5, x^3, x, x^8, x^6, x^4, x^2, y, x^2*y, x^4*y, 
  x^6*y, x^8*y, x*y, x^3*y, x^5*y, x^7*y, y^3, x^2*y^3, x^4*y^3, x^6*y^3, 
  x^8*y^3, x*y^3, x^3*y^3, x^5*y^3, x^7*y^3, y^2, x^7*y^2, x^5*y^2, x^3*y^2, 
  x*y^2, x^8*y^2, x^6*y^2, x^4*y^2, x^2*y^2 ]
gap> time;
41718

Concerning the error, one finds that it happens when GAP tries to compute a right transversal in a cyclic group of known order, w.r.t. its trivial subgroup. If we install a special RightTransversal method for this case (and if we modify the code of the function SIZE_FP_FROM_CYCLIC_INDEX such that the IsCyclic flag gets set for the stored CyclicSubgroupFpGroup) then we get the following.

gap> G:= F/rels;
<fp group on the generators [ x, y ]>
gap> Size( G );
36
gap> time;
34456
gap> Elements( G );
[ <identity ...>, y, y^2, x, x^6, y^-1, x^8*y, x^3*y, x*y^2, x^6*y^2, x^2, 
  x^7, x^3, x^8*y^-1, x^3*y^-1, x^7*y, x^2*y, x^6*y, x^2*y^2, x^7*y^2, 
  x^3*y^2, x^8, x^4, x^7*y^-1, x^2*y^-1, x^6*y^-1, x*y, x^5*y, x^8*y^2, 
  x^4*y^2, x^5, x*y^-1, x^5*y^-1, x^4*y, x^5*y^2, x^4*y^-1 ]
gap> time;
3582

I am not sure whether this change would be a good idea. Apparently GAP uses two different strategies, depending on whether the group order (and some nice cyclic subgroup) is known or not, and one of them is successful already now. Perhaps it would be better to change the decision about the choice of the strategy.

For those who want to play with the example, here is the RightTransversal method in question.

InstallMethod( RightTransversal,
    IsIdenticalObj,
    [ IsGroup and IsCyclic and HasSize, IsGroup and IsTrivial ], 100,
    function( G, T )
      local gens, gen, x, res, i;

      gens:= GeneratorsOfGroup( G );
      if Length( gens ) <> 1 then
        TryNextMethod();
      fi;
      gen:= gens[1];
      x:= One( G );
      res:= [ x ];
      for i in [ 2 .. Size( G ) ] do
        x:= x * gen;
        Add( res, x );
      od;
      return res;
    end );

[hulpke]

I am still puzzled why people want to calculate element lists of fp groups, rather than go to a permutation representation. Certainly this peripheral use should not direct how we implement routines for finitely presented groups. But I digress.

In my view it is not a good ideas to introduce a special RightTransversal method, just to make Elements work, as it will interfere in more elaborate calculations. Rather, change the special Elements method so that it uses for H_mod_1 an explicit element list, in the way as your method computes.

[ThomasBreuer]

@hulpke Thanks for your comments. I do not catch the point: The documentation of RightTransversal states already that the result may be a plain list if the subgroup in question is trivial, thus I would regard the proposed new method as a shortcut, also independent of the fact that it makes the given example for finitely presented groups work.

[hulpke]

@ThomasBreuer My concern is that there migth be some calculation that assumes the right transversal in a cyclic group by the trivial subgroup being not a list, but a fancy object -- for example if the group is infinite (or very large). I worry that a method as proposed will interfere. Since this is catering to only one place of call (namely the Elements method, why not put the code directly there?

[ThomasBreuer]

@hulpke Of course I can put the additional code locally into the Elements method in question, but I still do not catch the point: Don't we usually want to write code in such a way that improvements get used where they make sense, even in places we do not know about?

(If some code "assumes the right transversal in a cyclic group by the trivial subgroup being not a list" then this is a bug, according to the documentation.)