[GAP Forum] Unexpected Behaviour in Size()

[Derek Holt]

Dear GAP-Forum,

On Sun, Feb 26, 2006 at 11:21:56AM -0700, Alexander Hulpke wrote:
> Dear GAP-Forum,
> 
> Nilo de Roock wrote:
> 
> On Feb 26, 2006, at 9:39 AM, Nilo de Roock wrote:
> 
> >Hello GAP forum,
> >
> >I created the free group ( i got this spec. for the group from a  
> >textbook-exercise ):
> >gap> F:=FreeGroup(3);
> ><free group on the generators [ f1, f2, f3 ]>
> >gap> x:=F.1;
> >f1
> >gap> y:=F.2;
> >f2
> >gap> z:=F.3;
> >f3
> >gap> G:=F/[y^3*z^15,x^4*y^7*z^3,x^8,y^14,z^18];
> ><fp group on the generators [ f1, f2, f3 ]>
> >
> >Then when I wanted to now the size of the group, GAP became a bit  
> >of erratic.
> 
> I would not call this erratic.
> 
> This is the expected behaviour, as there are fundamental difficulties  
> on algorithmic methods for finitely presented groups. (The so-called  
> ``word problem''.)
> You might want to read the AMS notices article by 'Akos Seress  
> (notices.ps on the page http://www.math.ohio-state.edu/~akos/ )
> or the recent ``Handbook of Computational Group Theory'' by Holt et.  
> al. for methods used and some of the fundamental problems arising.
> 
> GAP issues warnings that it is performing a lot (probably more than  
> you expected) work, and still does not have a result. This is an  
> indication that you might needs lots of memory or would be on the way  
> of overloading your computer without ever getting a result -- GAP is  
> trying to stop you doing something you don't really want.
> 
> In your case, GAP tries to compute the size of an fp group by  
> calculating the index of a cyclic subgroup and rewriting the  
> presentation. However an easy calculation (abelian invariants of G')  
> shows that your group is infinite and cannot have any cyclic subgroup  
> of finite index.

Another way to show that the group is infinite is to use rewriting systems.
The MakeConfluent command succeeds quickly, and by inspecting the rules
in the confluent system, we find that
G = < x,y,z | z^3=y, y^2=1, x^4=1, yz=zy >,
so G is the free product of the cyclic groups <z> and <x> or orders 6 and 4.
In fact it is not difficult to establish that with a hand calculation,
which was probably what was intended in the textbook exercise!

I guess in a perfect world, asking whether a finitely presented group was
finite or infinite would automatically trigger these types of calculations
(coset enumeration, abelian invariants of finite index subgroups, rewriting
systems) each being tried in succession (or perhaps in parallel) for
progressively longer times.

Derek Holt.