[GAP Forum] Details on order computation with GAP

[Hulpke,Alexander]

Dear Forum, Dear Alexander Bors,

For theoretical complexity considerations/comparisons, I would be interested to know how GAP's built-in algorithm for order computation, called via Order (discussed in Subsection 31.10-10 in the manual), proceeds to compute the order of an automorphism alpha of a finite pc group G, where alpha is defined via its images on the presentation generators of G (through a call of GroupHomomorphismByImages).

Since the manual does not seem to give details on this, is there any way to find out other than diving into GAP's source code? Thank you very much for your answers.

Basically you need to look at the source code, but `ApplicableMethod’ can be used to find this method easily:

gap> g:=SmallGroup(96,100);
<pc group of size 96 with 6 generators>
gap> a:=AutomorphismGroup(g);
<group of size 768 with 7 generators>
gap> me:=ApplicableMethod(Order,[a.7],1);
#I  Searching Method for Order with 1 arguments:
#I  Total: 20 entries
#I  Method
9
 : ``Order: for automorphisms'' at /Users/hulpke/gap4/lib/morpheus.gi:20 , valu\
e: 17
function( hom ) ... end
gap> Print(me);
function ( hom )
    local map, phi, o, lo, i, start, img;
    o := 1;
    phi := hom;
    map := MappingGeneratorsImages( phi );
[…]

You’ll see that the method iteratively maps generators of the group through the automorphism, until they are back at the start again.

This is a very general method that works OK if only a few orders are computed. If order computation was time critical ,there are some obvious improvements, e.g. (this comes to mind first, there is no claim that this is best complexity):

Choose a pc presentation that refines a characteristic series G=C_0>C_1>….. Remember at which levels the characteristic subgroups sit.
Then compute the order modulo C_1 and replace the automorphism by that power. Then order modulo C_1, and so on. The order is the product of these orders.

The problem with implementing this as a default method is that further preprocessing is needed, which can be costly if ever only one element order is of interest. As so far nobody ever mentioned that for them the order of automorphisms was critical we did not look into this further.

Best,

   Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at colostate.edu<mailto:hulpke at colostate.edu>, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke