[GAP Forum] Automorphism order computation via cycle lengths?

[Hulpke,Alexander]

Dear Forum, Dear Alexander Bors,

I think it is easier to answer in reversed order:

> Finally, I would like to note that before posting this question, I did try to find this out myself by having the relevant GAP source code directly displayed using ApplicableMethod (following Alexander Hulpke's helpful advice in response to my last question linked to above), but unfortunately, it seems that this does not work for OrbitLength (see the second example below) - is this a bug?

No. What I described is for operations, but the group action functionality has ordinary functions (which deal with the variety of permitted and assumed arguments first. This is somewhat complicated, look into `OrbitishFO` in oprt.gd to see how this is done). The operation called (which will take further arguments supplied by the function) in your case is `OrbitLengthOp`.  What you could do is to call

TraceMethods(OrbitLengthOp);

before calling `OrbitLength`, which will point to the method in the library.

> the computation of the cycle length of g under alpha1 via calling OrbitLength(Group(alpha1),G,g) takes rather long and also seems to require a lot of memory
> gap> OrbitLength(Group(alpha1),G,g);

What you are telling GAP is that everything is in the domain G and that it should use G like a list to identify orbit elements with numbers. This causes GAP to enumerate the elements of G. (This is hardcoded in the function used for `OrbitLength`.)
This takes time and memory, but on a second call can just be used, explaining the time discrepancy.

Rather use
OrbitLength(Group(alpha1),g);

and the calculation will be much faster.

> concerns the computation of orders of automorphisms of finite pc groups with GAP 

The orbit length calculations you propose don’t really help because the fundamental issue is the long orbits of some group elements, as the automorphism order can be large. In such cases the best approach is to force shorter orbit lengths first, e.g. by working in suitable chief factors. If you are interested I can send you privately an improved routine for order of a group automorphism  that might make a future release of GAP.
In your example it should be significantly faster than the prior method used.

>  when picking an automorphism alpha1 as well as an element g of G at random using the ProductReplacer method

If you allow me the remark, I’m not sure what you hope to gain by this complication. As a PcGroup, G can easily be enumerated, so calling `Random` on G is working just fine and quickly.

For the automorphism group `A` indeed a call to `Random` would build expensive data structures, but you can call `PseudoRandom` to use a product replacement algorithm.

Regards,

   Alexander Hulpke

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