0
$\begingroup$

Is there an algorithm to compute automorphism group of a finite group?

GAP has a function to do this, but while perusing their GitHub repo, I could not find an implementation. I'm struggling to find anything else related to this online. Any clues?

Note: I am trying to write my own group theory library (for fun and learning). So I need an actual algorithm.

$\endgroup$
9
  • $\begingroup$ Do you mean "of a finite group"? or "of a group given by a finite presentation"? as such "group" the question makes little sense. $\endgroup$ – YCor Apr 9 at 17:52
  • $\begingroup$ Good point - I meant of a finite group. $\endgroup$ – Jerry Halisberry Apr 9 at 17:58
  • 3
    $\begingroup$ Yes, there is an algorithm: Run through all permutations of G and check for homomorphisms. Presumably you mean an efficient algorithm? $\endgroup$ – Thomas Browning Apr 9 at 18:22
  • 4
    $\begingroup$ Find a generating set for $G$ of size at most $\log_2|G|$ try all possible images of the generators in the group and check which of these extends to an isomorphism. This has complexity something like $|G|^{O(\log |G|)}$, and there is no known algorithm that has been proved to have better theoretical complexity. It is an open problem whether it can be done in time polynomial in $|G|$. I could say a lot more about this, but not without going into a lot of technical and theoretical detail. Incidentally, what input for your algorithm do you envisage? How is the group to be input? $\endgroup$ – Derek Holt Apr 9 at 18:50
  • 1
    $\begingroup$ @JerryHalisberry see also math.stackexchange.com/questions/947945 for finding where certain things are implemented in GAP. $\endgroup$ – Alexander Konovalov Apr 9 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.