# Re: [GAP Forum] Details on order computation with GAP

```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

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: hul...@colostate.edu<mailto:hul...@colostate.edu>, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke

_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
```