[GAP Forum] Automorphism order computation via cycle lengths?

[Bors Alexander Hermann]

Dear GAP Forum,

This question, like the one that I asked a few months ago (https://mail.gap-system.org/pipermail/forum/2017/005596.html), concerns the computation of orders of automorphisms of finite pc groups with GAP (I did all the computations in GAP 4.8.9).

By playing around, I noticed the following curious phenomenon: For certain finite pc groups G (at the end of this message, I give an example with G:=SmallGroup(251^3,3)), when picking an automorphism alpha1 as well as an element g of G at random using the ProductReplacer method from the package orb (https://www.gap-system.org/Packages/orb.html), 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 (on my computer, it ran into memory problems for G:=SmallGroup(281^3,3)), but once this computation has finished, the computation of the cycle length of any element of G under another randomly chosen automorphism alpha2 of G is very fast, allowing for a fast computation of the order of alpha2 as the least common multiple of the cycle lengths of the generators of G under alpha2, and this may outspeed the default order computation called with Order(alpha2).

This may save computation time if one is interested in computing the orders of many automorphisms of G when G is not too large (to avoid the above mentioned memory problems), and I would like to better understand the reason for this phenomenon (and whether it can be expected that it is a common phenomenon). I would be very grateful if someone who is knowledgeable about the precise implementation of OrbitLength in GAP could please elaborate.

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?

Many thanks in advance and best wishes,
Alexander


Example 1: Comparison of order computations (assuming that the package "orb" has been loaded)

gap> G:=SmallGroup(251^3,3);
<pc group of size 15813251 with 3 generators>
gap> A:=AutomorphismGroup(G);
<group of size 249058703250000 with 8 generators>
gap> pr1:=ProductReplacer(G);
<product replacer gens=3 slots=8 scramble=30 maxdepth=infinity
steps=0 (rattle accus=5, with accelator)>
gap> pr2:=ProductReplacer(A);
<product replacer gens=8 slots=13 scramble=32 maxdepth=infinity
steps=0 (rattle accus=5, with accelator)>
gap> g:=Next(pr1);
f1^234*f2^62*f3^215
gap> alpha1:=Next(pr2);
Pcgs([f1, f2, f3 ]) -> [ f1^124*f2^214*f3^229, f1^57*f2^173*f3^90, f3^218 ]
gap> OrbitLength(Group(alpha1),G,g);
125
gap> time;
129375
gap> alpha2:=Next(pr2);
Pcgs([ f1, f2, f3 ]) -> [ f1^103*f2^91*f3^81, f1^247*f2^2*f3^116, f3^68 ]
gap> Lcm(OrbitLength(Group(alpha2),G,GeneratorsOfGroup(G)[1]),OrbitLength(Group(alpha2),G,GeneratorsOfGroup(G)[2]),OrbitLength(Group(alpha2),G,GeneratorsOfGroup(G)[3]));
250
gap> time;
234
gap> Order(alpha2);
250
gap> time;
578


Example 2: Trying to call ApplicableMethod for OrbitLength (with variable values as defined in Example 1)

gap> ApplicableMethod(OrbitLength,[Group(alpha2),G,GeneratorsOfGroup(G)[1]]);
Error, <oper> must be an operation in
methods := METHODS_OPERATION( oper, l ); at /proc/cygdrive/C/gap4r8/lib/methwhy.g:167 called from
CallFuncList( ApplicableMethodTypes, arg ) at /proc/cygdrive/C/gap4r8/lib/methwhy.g:253 called from
<function "ApplicableMethod">( <arguments> )
called from read-eval loop at line 15 of *stdin*

[Hulpke,Alexander]

Dear Forum, Dear Alexander Bors,

Post by Bors Alexander Hermann
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.

Post by Bors Alexander Hermann
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.

Post by Bors Alexander Hermann
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.

Post by Bors Alexander Hermann
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: ***@colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke