Timeline for Recursive presentability of outer automorphism group
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2013 at 0:54 | comment | added | Joel David Hamkins | Perhaps we can at least rule out the possibility that there would be a computable function mapping every fg group presentation to a presentation of its automorphism group? The idea here would be to create a devious fg group presentation, which had access (via the recursion theorem) to the computable presentation of its automorphism group; when information is added to the automorphism group, then we can add new relations to the original group so as to create problems, in such a way to diagonalize against it. | |
| Apr 4, 2013 at 14:42 | comment | added | Ashot Minasyan | @HW: actually, my previous comment shows that the set of automorphisms of $G$ represented as such $n$-tuples is not always recursive. However, if $G$ is finitely presented, then it probably is recursively enumerable, because in a finitely presented group there is a partial algorithm, which, given on input such an $n$-tuple of words $(w_1,\dots,w_n)$ terminates and outputs "yes" if the map $x_i \mapsto w_i$ defines an automorphism of $G$, and does not terminate otherwise. Hence Out(G) will indeed be recursively presented, as you observe above. But I do not know what to do if $G$ is not f.p. | |
| Apr 4, 2013 at 14:40 | comment | added | HJRW | Ashot - you're right, with just a recursive presentation one can't check that a putative automorphism is actually a homomorphism. (Unsolvable word problem is neither here nor there. The problem is that one needs to check infinitely many relations.) Hmmm... intriguing. I think with a finite presentation this is possible - you are just enumerating retractions that happen to be surjective. This is different to checking if an arbitrary set generates - an arbitrary generating set won't necessarily be the image of the 'standard' generators under an automorphism. | |
| Apr 4, 2013 at 14:12 | comment | added | Ashot Minasyan | @HW: the problem with this idea is, how do you enumerate the elements of $Aut(G)$? More precisely, if $G$ is generated by a finite subset $X=\{x_1,\dots,x_n\}$, you want to enumerate all the $n$-tuples $\{ (\phi(x_1),\dots,\phi(x_n))\in G^n \mid \phi \in Aut(G)\}$, is this correct? I do not see how this can be done, especially if $G$ has unsolvable word problem. But even if $G$ is finitely presented, with solvable word problem, this may not be possible to do as the problem whether a given set of elements generates $G$ may still be undecidable. | |
| Apr 4, 2013 at 13:40 | comment | added | HJRW | Now, doesn't it then follow that there is a finitely generated recursive presentation, just by general nonsense? (Though of course one can't necessarily compute the finitely generated, recursive presentation.) Indeed, the algorithm starts with the finite set $S$ of generators (which we know exists) and, for each generator in the infinitely generated presentation, tries to express it as a product of elements of $S$. We can then translate each relation from the infinitely generated presentation into a relation for the finitely generated presentation. Or have I missed something? | |
| Apr 4, 2013 at 13:37 | comment | added | HJRW | Fearful of being too glib a second time round, it seems to me that an easy argument shows that, if G is recursively presented, then Out(G) admits an infinitely generated recursive presentation. Indeed, you can enumerate elements of Aut(G), and also relations between them, since both of these just involve checking identities in G. But then you can add the inner automorphisms to your list of relations easily enough. | |
| Apr 4, 2013 at 9:44 | history | edited | ADL | CC BY-SA 3.0 |
added 63 characters in body; added 40 characters in body
|
| Apr 4, 2013 at 9:43 | comment | added | ADL | Sorry, you are right, I was assuming the groups $G$ were finitely generated. I have edited the question accordingly. | |
| Apr 3, 2013 at 16:59 | comment | added | Joel David Hamkins | For example, the free abelian group on countably many generators is computably presentable, but the outer automorphism group has size continuum, as it includes all those arising from any permutation of the generators, and is therefore not computably presentable. | |
| Apr 3, 2013 at 16:32 | comment | added | YCor | ... while I guess you allow Out(G) on the other hand to be infinitely generated. So in any case you should clarify. | |
| Apr 3, 2013 at 16:28 | comment | added | YCor | You should specify that your group is finitely generated (more precisely has a presentation with finitely many generators and a recursive family of relators), otherwise Out could be uncountable. | |
| Apr 3, 2013 at 14:37 | history | asked | ADL | CC BY-SA 3.0 |