Given a finitely presented group $<x_1,x_2,...,x_n|R_1,R_2,...,R_n>$, one specifies an automorphism $\phi$ by its action on the generators, i.e. $\phi(x_i)=w_i$ for some (reduced) words $w_i$ in the group. What are the known algorithms for finding such a presentation for $\phi^{-1}$?
$\begingroup$
$\endgroup$
9
-
$\begingroup$ Here something is incorrect. 1. "the known algorithms for finding such a presentation" - have you an algorithm for $\phi$? 2. Denote $\psi=\phi^{-1}$ and apply your algorithm to $\psi$. $\endgroup$– Boris NovikovCommented Mar 11, 2013 at 20:20
-
2$\begingroup$ Assuming that it is truly known that $\phi$ is an automorphism, and assuming that the group has a solvable word problem, this is straightforward (if computationally tedious): enumerate words, and test the $\phi$ image of each word for equality to each of the generators. Eventually you will find words mapping to each of the generators. Did you have something more in mind? $\endgroup$– Lee MosherCommented Mar 11, 2013 at 20:32
-
1$\begingroup$ @Boris, I suspect the author is referring to the situation where $\phi$ is specified on the generators (referencing a fixed presentation). The question is to determine how $\phi^{-1}$ evaluates on the generators of the group. $\endgroup$– Ryan BudneyCommented Mar 11, 2013 at 20:33
-
3$\begingroup$ @quantum coffeemug: in practice what I do is find a generating set for the automorphism group of the given finitely-presented group. I then compute the inverses of the generators of the automorphism group (although in principle tedious frequently this is not too bad, for example, with free groups or hyperbolic groups) and then one can compute inverses of general elements of the automorphism group by multiplication of generators. $\endgroup$– Ryan BudneyCommented Mar 11, 2013 at 20:36
-
1$\begingroup$ The question is interesting. As Lee Mosher pointed out, if the word problem is solvable, there is an obvious algorithm. It would be interesting to investigate the complexity of the problem in general, and, say, for nilpotent groups in particular. $\endgroup$– user6976Commented Mar 12, 2013 at 2:19
|
Show 4 more comments