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?

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

1 Answer 1


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.

  • $\begingroup$ Could you give more detail in the crucial paragraph that begins "To see this, just rewrite..."? $\endgroup$
    – HJRW
    Jul 11, 2017 at 5:21
  • $\begingroup$ @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). $\endgroup$ Jul 11, 2017 at 5:33
  • $\begingroup$ Thanks. I now see that the equation wasn't displaying properly on my phone, which was why I found it puzzling. $\endgroup$
    – HJRW
    Jul 11, 2017 at 8:47
  • 1
    $\begingroup$ @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). $\endgroup$ Jul 12, 2017 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.