Adding a formal inverse of an element to a free monoid - MathOverflow

Adding a formal inverse of an element to a free monoid

2010-11-16T00:46:11Z

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.

Answer by Chad Groft for Adding a formal inverse of an element to a free monoid

2010-11-16T01:35:11Z

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}$).)

Answer by Mark Sapir for Adding a formal inverse of an element to a free monoid

2011-03-14T03:47:49Z

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.