MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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}$).)

share|cite|improve this answer
@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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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