Order of a generator element of Free Group in GAP

Question

I am using the FreeGroup function in GAP

gap> f:=FreeGroup(2);;
gap> Order(f);
infinity
gap> Order(f.1);
# GAP Hangs here with not output
# with Ctrl-c
^CError, user interrupt in
MakeImmutable( a ); called from 
pow * obj called from
<function "unknown">( <arguments> )
called from read-eval loop at line 18 of *stdin*
you can 'return;'
brk> 

I quote from Wikipedia here

On the other hand, any nontrivial finite group cannot be free, since the elements of a free generating set of a free group have infinite order.

Now shouldn't Order(f.1) should return Infinity as well (for free group not for any general group)? I know that mathematically it is possible that one of them has a finite order and other has infinite order (for general group). Shouldn't my statement be true for "Free Group" specifically?

Thanks

Answer 1

Just because the element of a group element is infinite does not necessarily mean that a computer program will be able to determine it. The documentation of Order states:

> Order( <elm> )                                                         A

is  the  multiplicative  order  of  <elm>.  This  is the smallest positive
integer  <n>  such  that  `<elm>^<n>  =  One(  <elm> )' if such an integer
exists.   If   the  order  is  infinite,  `Order'  may  return  the  value
`infinity',  but  it  also  might run into an infinite loop trying to test
the order.

An infinite loop may happen either if there is no [known] algorithm for the given group to determine whether or not an element has infinite order, or if such an algorithm simply has not been implemented.

As you point out, for the free group, it would be rather trivial to implement. So, my guess would be that nobody bothered to implement Order for free groups in a better way (e.g., as a special case). It's hardly necessary from a computational point of view, as Order is trivial anyway. You could try digging through to source code to see exactly what's going on.

Answer 2

In this special case you are right. If GAP knows that an object is an element of a free group, which it does for f.1:

gap> IsElementOfFreeGroup(f.1);
true

it should be able to tell you that its order is infinite. I just submitted a fix to GAP's github repository.

The infinite loop happened because GAP only operated on the assumption that it was trying to determine the order of an element that can be multiplied in a domain that contains a one and inverses:

gap> Print(ApplicableMethod(Order, [f.1]));
function ( obj )
    local  one, pow, ord;
    one := One( obj );
    if one = fail  then
        Error( "<obj> has not an identity" );
    fi;
    if Inverse( obj ) = fail  then
        Error( "<obj> is not invertible" );
    fi;
    pow := obj;
    ord := 1;
    while pow <> one  do
        ord := ord + 1;
        pow := pow * obj;
    od;
    return ord;
end

If you find a bug of this type, it is probably best to submit it to our issue tracker.

As a side note: The knowledge that is exploited here is obtained from the construction of the free group. Since it is undecidable whether an element of a finitely presented group is an element of a free group, there cannot be a general method to install and always terminate and give you an accurate answer.