Shortest equivalent word for FPG Given a finitely presented group $G$ and a word $w$ in $G$, is there always an efficient algorithm to find the set of shortest words equivalent to $w$?
I am guessing that the problem of finding the shortest words is undecideable if the group is infinite, but possibly efficient if the group is finite.
 A: The word problem for a group $G$ given by a finite presentation $\langle \mathbf{x}\mid\mathbf{r}\rangle$ is the problem of determining whether a word $W\in(\mathbf{x}^{\pm1})^*$, i.e. a word over the generators $\mathbf{x}$ and their formal inverses, defines the trivial element of $G$. This problem is undecidable in general.
Theorem.
Fix a group $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$.
There exists an algorithm with input a word $W\in(\mathbf{x}^{\pm1})^*$ and output the set of shortest words equivalent to $W$ if and only if $G$ has decidable word problem.
Proof.
The word problem in $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ reduces to the problem here, as a word defines the trivial element if and only if the set of shortest words equivalent to $W$ is precisely $\{\epsilon\}$ (here $\epsilon$ denotes the empty word, the unique word of length $0$). Hence, there is no algorithm to solve your problem in groups with undecidable word problem.
Suppose on the other hand that $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ has decidable word problem. Then enumerate all words $U\in(\mathbf{x}^{\pm1})^*$ such that $|U|\leq|W|$. By applying the word problem to $U^{-1}W$, we can find all such words which are additionally equal to $W$ in $G$. Hence, we have found the set $\mathcal{S}$ of all words $U$ which are no longer than $W$ and which are equal to $W$ in $G$. The set we are seeking is the set of shortest elements in $\mathcal{S}$, which is now easily computable. QED

In particular, there are infinite groups where this problem can be solved (e.g. finitely generated abelian groups and free groups).
