Timeline for Algorithm to compute automorphism group of a finite group
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2021 at 20:46 | comment | added | Olexandr Konovalov | @JerryHalisberry see also math.stackexchange.com/questions/947945 for finding where certain things are implemented in GAP. | |
| Apr 9, 2021 at 19:01 | comment | added | Jerry Halisberry | @DerekHolt Unfortunately that is the only optimization I could come up with. I am certainly missing a lot of the ideas I need to do this right. Where should I look? | |
| Apr 9, 2021 at 18:57 | comment | added | Derek Holt | 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. | |
| Apr 9, 2021 at 18:53 | comment | added | Jerry Halisberry | @DerekHolt The group is input as a group of elements, and there is an abstract compose function. You can just assume it is a Cayley table. | |
| Apr 9, 2021 at 18:52 | comment | added | Jerry Halisberry | @DerekHolt Thank you, this is helpful. My idea at the moment was basically that, but I wanted to optimize it, or find something better. I am wondering if some kind of backtracking with smart pruning is helpful? | |
| Apr 9, 2021 at 18:50 | comment | added | Derek Holt | 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? | |
| Apr 9, 2021 at 18:22 | comment | added | Thomas Browning | Yes, there is an algorithm: Run through all permutations of G and check for homomorphisms. Presumably you mean an efficient algorithm? | |
| Apr 9, 2021 at 17:59 | history | edited | YCor | CC BY-SA 4.0 |
fixed question, added tags
|
| Apr 9, 2021 at 17:58 | history | edited | Jerry Halisberry | CC BY-SA 4.0 |
added 17 characters in body
|
| Apr 9, 2021 at 17:58 | comment | added | Jerry Halisberry | Good point - I meant of a finite group. | |
| Apr 9, 2021 at 17:53 | history | edited | YCor | CC BY-SA 4.0 |
moved main object of question to text
|
| Apr 9, 2021 at 17:52 | comment | added | YCor | Do you mean "of a finite group"? or "of a group given by a finite presentation"? as such "group" the question makes little sense. | |
| Apr 9, 2021 at 17:20 | review | First posts | |||
| Apr 9, 2021 at 17:56 | |||||
| Apr 9, 2021 at 17:17 | history | asked | Jerry Halisberry | CC BY-SA 4.0 |