Adding a formal inverse of an element to a free monoid - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T09:02:00Z http://mathoverflow.net/feeds/question/46168 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46168/adding-a-formal-inverse-of-an-element-to-a-free-monoid Adding a formal inverse of an element to a free monoid Mark Sapir 2010-11-16T00:46:11Z 2011-03-14T03:47:49Z <p>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). </p> <p><b>Question:</b> For which other words $w=w(a,b)$, adding a formal inverse to $w$ turns the free monoid into the free group? </p> <p>I need a complete description, not just examples.</p> <p><b> Update question:</b> The same question for $FM_k$, the free monoid of rank $k\ge 3$. </p> <p><b> Edit </b> I moved my answer from here to the answer box below. </p> http://mathoverflow.net/questions/46168/adding-a-formal-inverse-of-an-element-to-a-free-monoid/46171#46171 Answer by Chad Groft for Adding a formal inverse of an element to a free monoid Chad Groft 2010-11-16T01:35:11Z 2010-11-16T02:19:14Z <p>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.)</p> <p>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.</p> <p>Symmetrically, if $z$ begins and ends with $b$ but contains an occurrence of $a$, then $z^{-1}$ exists implies $a^{-1}$, $b^{-1}$ exists.</p> <p>I suspect these are the only cases which work (<em>i.e.</em>, inverting a word of the form $awb$ or $bwa$ would not invert $a$ or $b$) but cannot yet prove it. (<strong>EDIT:</strong> This is false, see Mark's comment below.)</p> <p><strong>EDIT:</strong> Partial result! Consider the structure $M$ whose underlying set is</p> <p><code>$\{(m,e) \in \mathbb{N}\times\mathbb{Z} : m\ge e\}$</code></p> <p>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)$.</p> <p>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$.</p> <p>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}]$, <em>i.e.</em>, inverting $z$ does not invert $a$.</p> <p>(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}$).)</p> http://mathoverflow.net/questions/46168/adding-a-formal-inverse-of-an-element-to-a-free-monoid/58382#58382 Answer by Mark Sapir for Adding a formal inverse of an element to a free monoid Mark Sapir 2011-03-14T03:47:49Z 2011-03-14T03:47:49Z <p>OK, I will move my partial answer here as an answer to my question. If anybody can improve that answer, it would be good. </p> <p><b> A possible solution. </b> 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.</p> <p><b> Claim. </b> Inverting $w$ gives us a group iff the last set $S_n$ contains all the generators. </p> <p><b> Proof. </b> 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.</p>