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

Reply via email to