9
$\begingroup$

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?

$\endgroup$
  • $\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 '17 at 17:43
  • $\begingroup$ Not enough: $abca^{-1}b^{-1}$ is not "positive". $\endgroup$ – YCor Jul 10 '17 at 20:52
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you give more detail in the crucial paragraph that begins "To see this, just rewrite..."? $\endgroup$ – HJRW Jul 11 '17 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$ – Christian Remling Jul 11 '17 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 '17 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$ – Christian Remling Jul 12 '17 at 16:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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