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?

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

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .