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.

Improve this question
$\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
    Commented Apr 9, 2021 at 17:52
  • 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
    Commented Apr 9, 2021 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
    Commented Apr 9, 2021 at 18:50
  • 1
    $\begingroup$ There are lots of obvious optimizations. For example you only need to try images in which the orders are the same as those of the generators. The problem with input by Cayley table is that is restricts the order of groups that you process too much for the sort of computations that we want to in practice. generally we work with groups of permutations or matrices, and input groups by generating sets. $\endgroup$
    – Derek Holt
    Commented Apr 9, 2021 at 18:57
  • 1
    $\begingroup$ @JerryHalisberry see also math.stackexchange.com/questions/947945 for finding where certain things are implemented in GAP. $\endgroup$
    – Olexandr Konovalov
    Commented Apr 9, 2021 at 20:46

0

Reset to default

You must log in to answer this question.