[GAP Forum] Order of a group presentation

[Derek Holt]

Dear Nick, Dear Forum,

I hope you would agree that it is not reasonable to expect GAP to decide
theoretically undecidable problems! I am afraid that finding a lower bound
greater than 1 on the order of a group defined by a finite presentation is
undecidable in general, and so you cannot expect GAP to decide whether the
order is less than 1000. In fact (except in a few special situations),
coset enumeration tells you virtually nothing for certain if it fails
to complete.

There are some other techniques for establishing lower bounds on group orders,
such as identifying a finite, abelian, or polycyclic quotient of G of
knwon order, but (as far as I know) asking for the order of the group in
GAP will not attemot to use those. You could however easily compute the
largest abelian quotient, and if that is infinite or very large then you
can choose to move on to the next example.

The other thing that you can do, and which I would recommend, is to set
an upper limit (perhaps 2000) on the number of cosets that are defined during
coset enumeration, and to abort the process if that is exceeded. That way,
if your presentations are not what we call pathological (which essentially
means difficult and possibly designed to defeat coset enumeration!), then
it is very likely that it will successfully compute the order of a group
on your list if it is less than 1000.

I am not a great GAP expert, so someone can correct me if I get the details
wrong, but I found the following worked for a finitely presented group G.

gap>  CosetTableDefaultMaxLimit:=2000;
gap>  BreakOnError := false;
gap>  ind := 2001;
gap>  ind := Index(G,Subgroup(G,[]));

Setting BreakOnError to be false means that GAP will not abort and go into
a break loop when the maximum number of cosets (2000) is exceeded, but it
will just give up and carry on - it will however print an error message
reporting that it is doing that.

The reason for setting ind to 2001 before trying to compute the group
order is that, if the process fails, then ind will still be equal to
2001, so you know what has happened. It it succeeds, then of course ind
will equal the group order (necessarily at most 2000) after the call.

I hope this helps.

Best wishes,
Derek


On Wed, Sep 01, 2021 at 08:25:08AM +0000, Nick Gill wrote:
> PUBLIC / CYHOEDDUS
> 
> Hi GAP people,
> 
> I'm doing some coding where I process a long list of group presentations. For each presentation I'd like to calculate the order.
> 
> My problem is that I'm not 100% sure if all of the presentations yield finite groups. I'd like to ask GAP to first check to see if the group has order less than a 1000 (say) and, if not, then skip this presentation and move onto the next one.
> 
> My problem is that the Order command seems to ask GAP to give a full coset enumeration and so the loop keeps hanging when it hits possibly infinite groups.
> 
> So... Is there a GAP command that can do a partial coset enumeration to work out lower bounds for the size of a finitely presented group?(Or is there another way around this problem?)
> 
> Thanks!
> Nick
> _______________________________________________
> Forum mailing list
> Forum at gap-system.org
> https://mail.gap-system.org/mailman/listinfo/forum