1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @BabakS. Can you give an example of a free group with finite order (apart from the trivial group)? $\endgroup$ – Najib Idrissi Dec 15 '15 at 9:10
  • $\begingroup$ Thanks - it's a development type of question, which sounds more appropriate to be asked at the GAP GitHub issue tracker where it will be seen by a larger number of developers and may lead to improvements in GAP or to a documented explanation of design choices having which will be useful for the future. $\endgroup$ – Alexander Konovalov Dec 15 '15 at 9:34
  • $\begingroup$ @BabakS. $D_{2n}$ is not a free group. $\endgroup$ – Najib Idrissi Dec 15 '15 at 9:51
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks @moonlight. Ya, i it seems easy to say that it would have an Infinite order. $\endgroup$ – gxyd Dec 15 '15 at 9:57
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ > If you find a bug of this type, it is probably best to submit it to our issue tracker. The point is since i am new to GAP and GroupTheory both, i am following along a learning and applying path. So i can not just go ahead and think things like this to be bug. I feel rather more +ve to first ask and then rather submit them as bugs. Thanks though. $\endgroup$ – gxyd Dec 15 '15 at 12:17
  • 1
    $\begingroup$ I do realise that MSE is a common place to ask this kind of question (and probably not the worst one to do so!). Can I also point you towards the various GAP related mailing lists, support@gap-system.org, for support as the name says, forum@gap-system.org for discussion of mathematical questions and potential solutions in GAP, and gap@gap-system.org, the development mailing list, just in case. $\endgroup$ – Markus Pfeiffer Dec 15 '15 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.