2
$\begingroup$

If one takes a group presentation then one can ask various questions of it, such as "is this element equal to the identity", "are these elements conjugate" etc. I was wondering if the solution to such a problem in a representation of a group always yields a solution to the problem with respect to the presentation.

For example, if $G$ is a finitely generated group with soluble word problem then one can use the word problem for $G$ to work out if two elements of $\operatorname{Aut}(G)$ are different in finite time (if $\phi: x_i\mapsto X_i$ and $\varphi: x_i\mapsto Y_i$ then $\phi=\varphi$ if and only if $X_i=Y_i$ for all $i\in I$, $|I|<\infty$). However, I am unsure whether this amounts to a solution to the word problem for $\operatorname{Aut}(G)$. This is because in order to solve the word problem for $\operatorname{Aut}(G)\cong\langle X; R\rangle$ this way one would need to know in what way the given presentation is $\operatorname{Aut}(G)$; one would need to first know the isomorphism between $\operatorname{Aut}(G)$ and $\langle X; R\rangle$, but...can this always be done?

I am expecting the answer to be "yes, of course, don't be stupid!" but I just can't see how this would hold (although obviously it should)!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I am unsure as to how your first paragraph is illustrated by the second. To me you seem to be asking two different questions. The first paragraph sounds like it's asking "If I can solve a representation's word problem, then can I solve $G$'s word problem?" The second paragraph seems like it's asking "If I can solve $G$'s word problem, can I also solve $\mathrm{Aut}(G)$'s word problem?" $\endgroup$
    – Bill Cook
    Commented Sep 19, 2011 at 20:01
  • $\begingroup$ I was taking Aut(G) to be a representation for the abstract group Aut(G). I am not meaning linear representations, just representations in a more general sense (realisations?). $\endgroup$
    – ADL
    Commented Sep 20, 2011 at 8:54

1 Answer 1

Reset to default
4
$\begingroup$

Decidability of the word problem for a finitely generated group has nothing to do with a presentation of the group. It is not part of the input. If G is a finitely generated group with solvable word problem and H is a finitely generated group of automorphisms of G, then H has decidable word problem. There exists a Turing machine that knows how the generators of H act on the generators of G (don't ask me which Turing Machine). This machine can implement the algorithm you give.

It is a common misconception that decidability involves something effective. It merely asserts the existence of a Turing machine. This is why a problem with only finitely many inputs is always decidable even though I may not know which Turing machine is the one that says yes in the right cases.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ah, okay, thanks for clearing up my misconceptions! $\endgroup$
    – ADL
    Commented Sep 20, 2011 at 8:59
  • $\begingroup$ The strange thing about Turing machines is you can assume they know any finite amount information which is independent of the input even if we ourselves don't know this information. This is why the word problem doesn't depend on the choice of finite generating set. I may not know how to write the generators from one set as a word in the generators in the other set, but since there are only finitely many generators, there is a Turing machine that does. Knowing this fixed finite information it can algorithmically rewrite any input word in the other generating set and use its word problem TM. $\endgroup$
    – Benjamin Steinberg
    Commented Sep 20, 2011 at 18:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .