Algorithm to find the n-th root in the free group

Question

Given a word $w$ in the free group $F$, is there an algorithm to find it’s n-th root, if it exists? Thanks!

Answer 1

If $w$ has an $n$th root, then so does every conjugate of it. Among all pairs $(x,u)$ such that $w=u^{-1}x^nu$, pick one that minimizes first the length $|x|$ and then $|u|$.

If the first and last letter of $x$ are inverse of each other, i.e., $x=aya^{-1}$ for some letter $a$ and word $y$ with $|y|<|x|$, then $w=v^{-1}y^nv$ with $v=au$, contradicting minimality of $|x|$. Hence $x^n$ is really just concatenation (i.e., without any cancellation among the factors).

If the first letters of $u$ and $x$ are the same, i.e., $u=av$, $x=ay$ for some letter $a$ and words $v,y$ with $|v|<|u|$, $|y|<|x|$, then $w=v^{-1}a^{-1}(ay)^nav=v^{-1}(ya)^nv$, contradicting minimality (as $v|<|u|$ and $|ya|\le |x|$).

Similarly, if the first letter of $u$ and the last letter of $x$ are inverses, i.e., $u=av$, $x=ya^{-1}$ for some letter $a$ and words $v,y$ with $|v|<|u|$, $|y|<|x|$, then $w=v^{-1}a^{-1}(ya^{-1})^nav=v^{-1}(a^{-1}y)^nv$, contradicting minimality.

We conclude that no cancellation occurs when multiplying the factors $u^{-1},x,x,\ldots, x,u$.

This suggests the following algorithm:

1. Let $u\leftarrow\epsilon$, $v\leftarrow w$.
2. If $|v|$ is a multiple of $n$ and is the simple concatenation of $n$ copies of its length $|v|/n$ prefix $x$, then output "$uxu^{-1} $" and terminate. (Note that this condition also triggers when $v=\epsilon$, hence we may assume $v\ne\epsilon$ in the next step)
3. Let $a\leftarrow \operatorname{first}(v)$, $b\leftarrow \operatorname{last}(v)$.
4. If $a\ne b^{-1}$ output "NOT AN $n$TH POWER" and terminate.
5. (As $a=b^{-1}$, we have $a\ne b$, hence $|v|\ge 2$ and so $v=av'b$ for some shorter word $v'$) Let $v\leftarrow v'$, $u\leftarrow ua$, and go back to step 2.