[GAP Forum] automorphisms of "large" 2-groups

[Max Horn]

Dear Benjamin, dear All,

On 10.02.2014, at 20:02, Benjamin Sambale <benjamin.sambale at gmail.com> wrote:

> Thank you for several replies!
> Heiko Dietrich pointed out that the computation can be done with Magma in a matter of seconds. Also Eamonn O'Brien provided a concrete automorphism of order 7.
> I like to add that I had no problems with GAP computing automorphism groups of very similar groups (of order 2^9).

I had a closer look at the cause for this slowdown. Since I've been working (jointly with Bettina Eick) on somewhat related code dealing with arbitrary finite solvable groups, I am more or less familiar with what's going on there, and after a quick glance, the issue seemed rather familiar... :-)

Indeed, the problem is that autpgrp tries to compute a stabilizer via a "naive" orbit-stabilizer computation; but the orbit involved has size 119,992,320 which means it would take a lot of time and memory to actually compute it. This is made worse by the fact that orbit-stabilizer implementation in autpgrp is not running in time linear in the orbit size (as it should), but rather quadratic... so there is no chance for it to complete in the foreseeable future. :-). 

At first I only fixed the autpgrp to work linear instead of quadratic, but after computing an estimate for the orbit size, I realized this wouldn't be enough (at least not if you are impatient and on a train ride like me ;-). So I did some heart surgery on my local copy of autpgrp, and changed it to use the genss package to compute this stabilizer. For now, this means using a probabilistic algorithm, but I asked it to compute the result with an error probability below 1/2^30, so I am quite hopeful the result is correct. (It should be possible to turn this back into an exact computation, but I didn't bother for this experiment).

With that change, GAP + autpgrp + genss also take only a few seconds to compute the automorphism group, which seems to be of size 2^18*7 -- does that match the result Magma gives you?

Finally, a concrete automorphism of order 7 is given by

Pcgs([ f1, f2, f3, f4, f5, f6, f7, f8, f9 ])
-> [ f1*f2*f5*f7*f8*f9, f3*f8, f1*f7*f8*f9, f4*f5, f5*f6, f4, f9, f7*f9, f8 ]


Cheers,
Max