MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$?

share|cite|improve this question
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$. – Boris Novikov Mar 11 '13 at 20:20
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? – Lee Mosher Mar 11 '13 at 20:32
@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. – Ryan Budney Mar 11 '13 at 20:33
@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. – Ryan Budney Mar 11 '13 at 20:36
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. – Mark Sapir Mar 12 '13 at 2:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.