# Adding a formal inverse of an element to a free monoid

Let $FM_2=\langle a,b\rangle$ be the free monoid of rank 2. If we add a formal inverse to the word $aba$, we get the free group $F_2$ (because both $a$ and $b$ will have inverses).

Question: For which other words $w=w(a,b)$, adding a formal inverse to $w$ turns the free monoid into the free group?

I need a complete description, not just examples.

Update question: The same question for $FM_k$, the free monoid of rank $k\ge 3$.

Edit I moved my answer from here to the answer box below.

-
Mark, why don't you answer in an answer box and use the question box for the question? :) –  Mariano Suárez-Alvarez Nov 17 '10 at 1:34
@Mariano: That is because I still hope somebody gives a better answer. This is just an algorithm, not a "closed formula". Something like what Chad was trying to do would be better. My "answer" does clarify the situation with such words as $a^2b^3a^2bab^2$ in Chad's comment below. My algorithm says that this is not a "good" word meaning if we add its inverse, we do not get a group. Indeed this word does not have any prefix which is also a suffix. So perhaps now Chad or somebody else can finish what he was doing. –  Mark Sapir Nov 17 '10 at 3:00
@ Mark: I am a bit confused by how the algorithm begins; in each step you take two words from $S_n$, but $S_0$ contains only one word. –  ADL Mar 9 '11 at 13:45
@Alan: the words may be equal. They will be equal on the first step. –  Mark Sapir Mar 9 '11 at 14:34

Let $z$ be a word, and let $M=FM(a,b)/z^{-1}$. If we wish $a$ and $b$ to be invertible in $M$, then $z$ must contain both $a$ and $b$ at least once. (For example, $FM_2[a^{-n}]=FM_2[a^{-1}]\cong F(a)\ast FM(b)$ by the canonical maps.)

Suppose $z = a^nwa^m$ with $n, m>0$. If $z^{-1}$ exists, then $a$ has a right inverse $r = a^{n-1}wa^mz^{-1}$ and a left inverse $l = z^{-1}a^nwa^{m-1}$, and in fact these two are equal by the standard argument ($l = lar = r$); so just say $l=r=a^{-1}$. Then $z^{-1}a^nwa^m = e$ implies $z^{-1}a^nw = a^{-m}$ implies $a^mz^{-1}a^nw = e$ ($w$ has a left inverse), and similarly $w$ has a right inverse which is the same. If $z$ contains any occurrences of $b$, then we choose $w$ to begin and end with $b$; by the earlier argument applied to $w$, $b$ is invertible.

Symmetrically, if $z$ begins and ends with $b$ but contains an occurrence of $a$, then $z^{-1}$ exists implies $a^{-1}$, $b^{-1}$ exists.

I suspect these are the only cases which work (i.e., inverting a word of the form $awb$ or $bwa$ would not invert $a$ or $b$) but cannot yet prove it. (EDIT: This is false, see Mark's comment below.)

EDIT: Partial result! Consider the structure $M$ whose underlying set is

$\{(m,e) \in \mathbb{N}\times\mathbb{Z} : m\ge e\}$

with binary operation $(m,e)\ast(m',e') = (\max(m,e+m'), e+e')$. It is routine to check that this is a monoid. Let $z=awb$ contain $i$ copies of $a$ and $j$ copies of $b$, and consider the morphism $f\colon FM(a,b)\to M$ with $f(a) = (0,-j)$ and $f(b) = (i,i)$.

From counting it is clear that $f(z) = (m,0)$ for some $m\in\mathbb{N}$. If $m=0$ (as it will be for any word of the form $a^ib^j$, and many other words besides), then $f$ extends to a morphism $FM(a,b)[z^{-1}]\to M$.

But $f(a)$ has no left inverse; if $(m,e)\ast (0,-j) = (0,0)$, then $e=j$ and $\max(m,j)=0$, which is impossible ($j>0$ by assumption). Thus $a^{-1}$ cannot be a member of $FM(a,b)[z^{-1}]$, i.e., inverting $z$ does not invert $a$.

(Intuition: For each word in $FM(a,b)$, start at zero and read the word from left to right. For each $a$, descend $j$ steps; for each $b$, ascend $i$ steps; and track both your peak and your current position. If reading $z$ never gets you to the positive numbers, then adjoining $z^{-1}$ does not get you $a^{-1}$ (or similarly $b^{-1}$).)

-
@Chad: Your suspicion seems wrong. Indeed, if $w=abaab$ is invertible, then $ab$ is invertible ($w$ starts and ends with $ab$), hence $a$ is invertible (since $a$ is the product of $(ab)^{-1}$, $w$ and $(ab)^{-1}$, hence $b$ is invertible. Thus inverting $w$ turns the monoid into a group. –  Mark Sapir Nov 16 '10 at 2:12
Good point. I'll edit the answer to note this. –  Chad Groft Nov 16 '10 at 2:20
Note also that the criteria above don't cover the whole space of possibilities. $z=a^2b^3a^2bab^2$ is the simplest word I can find which isn't covered. –  Chad Groft Nov 16 '10 at 2:45
What is your guess for $z=a^2b^3a^2bab^2$? –  Mark Sapir Nov 16 '10 at 3:11
My guess is that adjoining $z^{-1}$ does not get you all the way to $F_2$, but it's not a very well-informed guess. –  Chad Groft Nov 16 '10 at 4:16

OK, I will move my partial answer here as an answer to my question. If anybody can improve that answer, it would be good.

A possible solution. I think I found a solution but it is not very explicit, so a more explicit description is welcome. Let $w$ be a word. Let $S_0=\{w\}$ . We shall construct sets of words $S_n$, $n=0,1,2,...$ by induction. Suppose $S$ is already constructed. If $S_n$ contains two words $u,v$ of the form $pu', v'p$, then we replace these pair of words ($u$ and $v$ may be the same) by the three words $p, u', v'$. Also if we have a pair of words $p, pu$ or $p,up$, then we replace it by $p,u$. This way we get a new set $S_{n+1}$. If we cannot do any changes, the process terminates. Clearly the process eventually terminates because the lengths of the words can only get smaller.

Claim. Inverting $w$ gives us a group iff the last set $S_n$ contains all the generators.

Proof. It is clear that if $S_n$ contains all generators, then the result is a group. Assume that a generator $x_1$ is not in the set. Then $x_1$ is either not the first letter of any word in $S_n$ or not the last letter of any of these words (otherwise $S_n$ is not the terminal set of words). Suppose the former holds (WLOG). Let $S_n=\{u_1,...,u_k\}$. Then adding inverse to $w$ implies adding inverses to $u_1,...,u_k$. Hence the resulting monoid is a quotient of the following monoid: $$G_t=\langle x_1,...,x_n, t_1,...,t_k\mid u_it_i=1, t_iu_i=1, i=1,...,k\rangle.$$ Moreover it is clear that $G_t$ is in fact islomorphic to the monoid obtained by adding the inverse to $w$. Now the fact that $S_n$ is terminal set means that the presentation of $G_t$ is complete" (i.e. confluent and terminating because there are no overlaps, see any book on string rewriting). Now suppose that $x_1$ has an inverse. Then $x_1v=1$ in $G_t$ for some $v$. But this relation cannot be deduced by applying the defining relations of $G_t$ from left to right since $x_1$ is not the first letter of any word in $S_n$, a contradiction.

-
I know you said you do not want examples, but the primitive pairs in $F(a, b)$ where $a$ and $b$ only occur with positive exponent work', as can be seen from your algorithm (i.e. if $<u, v> = F(a, b)$ and $u, v \in S_i$ for some $i$ then your word works). Thus, for example, $W=uvu$ works. The primitive pairs work because your algorithm can be used to unpick' the automorphisms $a\mapsto ab, b\mapsto b$, $a\mapsto ba, b\mapsto b$, and $a\mapsto b, b\mapsto a$ of $F(a, b)$. Also, I am unsure how one would gain a complete description; if $W$ works then so does, for example, $W^iUW^j$ for all $U$ –  ADL Mar 14 '11 at 14:43