# Detecting/Characterising positive elements in free groups

Let $X$ be a set, and let $F(X)$ be the free group generated by $X$.

I will say that an element of $F(X)$ is positive if it is in the monoid generated by all the conjugates in $F(X)$ of every member of $X$.

For example, if $X=\left\{a,b\right\}$ then $a, b, a^2 b a^{-1}$ are positive, but $aba^{-1}b^{-1}$ is not positive.

Is there any algorithm that can detect, given an element of $F(X)$, whether is it positive?

• Perhaps the total sum of exponents for every generator should be non-negative, and at least one of these sums should be positive. – Wlod AA Jul 10 '17 at 17:43
• Not enough: $abca^{-1}b^{-1}$ is not "positive". – YCor Jul 10 '17 at 20:52

Yes, there is an algorithm. This is based on the following simple fact: Any positive element can be reached (but in non-reduced form usually) by only applying the operations right multiplication by a generator $R_g(x)=xg$ and conjugation by a generator $C_g^{\pm}(x)=g^{\pm 1}xg^{\mp 1}$.

To see this, just rewrite $$xax^{-1}yby^{-1} \ldots wpw^{-1}zqz^{-1} = zz^{-1}ww^{-1} \ldots yy^{-1} xax^{-1}yby^{-1} \ldots wpw^{-1}zqz^{-1}$$ (here $a,b, \ldots ,p,q\in X$, while $x,y,\ldots$ are general elements of $F(X)$). Note that this at most doubles the length of our word.

Conversely, it's easy to see that any word reached by a combination of these operations will be positive.

This gives the following procedure: (1) Given a word $W$, list all non-reduced words of length $\le 2|W|$ that represent the same element; (2) for each such word $W'$, find all $W''$ (if any) with $W'=O(W'')$, with $O$ one of the operations from above; (3) repeat with these new words $W''$ etc.

$W$ is positive precisely if the empty word ever shows up in this list. The algorithm terminates because undoing a multiplication or conjugation reduces the length of a word.

• Could you give more detail in the crucial paragraph that begins "To see this, just rewrite..."? – HJRW Jul 11 '17 at 5:21
• @HJRW: The RHS is obtained by performing these operations, in reverse order: conjugate by $z$, right-multiply by $q$, conjugate by $z^{-1}$, conjugate by $w$, right-multiply by $p$, etc. ("conjugate by $z$" of course could mean many individual conjugations by generators). – Christian Remling Jul 11 '17 at 5:33
• Thanks. I now see that the equation wasn't displaying properly on my phone, which was why I found it puzzling. – HJRW Jul 11 '17 at 8:47
• @HJRW: Actually, there is one detail I overlooked originally: part of the $x,y,z,\ldots$ could have disappeared due to reductions. For example, the original word could look like $wxax^{-1}yby^{-1}w^{-1} \ldots zqz^{-1}$. It's not a problem, though, I can still do the same thing as before (in fact, $w$ is now "un-conjugated" earlier than it would have been without the cancellation). – Christian Remling Jul 12 '17 at 16:39