Artin right complements and word reversing

Let $n\in \mathbb{N}$, with the positive braid monoid $B_n^{+}$ of Positive braid monoid, its alphabet ${\mathrm{\Sigma }}_n=\{{\sigma }_1,\dots ,{\sigma }_{n-1}\}$, and its defining pairs $R_n$. Throughout, $s,t$ range over letters of ${\mathrm{\Sigma }}_n$ and $u,v,w$ over positive words.

The syntactic right complement. Define a function $\theta$ on pairs of letters by

$\theta (s,s):=\epsilon ,\theta ({\sigma }_i,{\sigma }_j):={\sigma }_j{\sigma }_i(\mathrm{\mid }i-j\mathrm{\mid }=1),\theta ({\sigma }_i,{\sigma }_j):={\sigma }_j(\mathrm{\mid }i-j\mathrm{\mid }\ge 2)\mathrm{.}$

Then $s\theta (s,t)$ and $t\theta (t,s)$ are the two sides of a defining pair of $R_n$ when $s\mathrm{\ne }t$, and are equal words when $s=t$. Indeed: if $s=t$ both words are the one-letter word $s$; if $s={\sigma }_i$, $t={\sigma }_j$ with $\mathrm{\mid }i-j\mathrm{\mid }=1$ they are ${\sigma }_i{\sigma }_j{\sigma }_i$ and ${\sigma }_j{\sigma }_i{\sigma }_j$, the two sides of the braid pair; if $\mathrm{\mid }i-j\mathrm{\mid }\ge 2$ they are ${\sigma }_i{\sigma }_j$ and ${\sigma }_j{\sigma }_i$, the two sides of the commutation pair. Consequently

$[s\theta (s,t)]=[t\theta (t,s)]\text{in }{B}_n^{+}\text{ for all letters }s,t,$

and for $s\mathrm{\ne }t$ the pair $\{s\theta (s,t),t\theta (t,s)\}$ is the unique pair of $R_n$ whose two sides begin with $s$ and with $t$ respectively. In the terminology of the source, the presentation of $B_n^{+}$ is right-complemented with syntactic right complement $\theta$.

The complement recursion. $\theta$ is extended to a map $\mathrm{\Theta }$ on pairs of positive words, written $\mathrm{\Theta }(u,v)$, by evaluating the following recursion in the order described. For a letter $s$ and a word $v$:

$\mathrm{\Theta }(s,\epsilon )=\epsilon ,\mathrm{\Theta }(s,tv)=\theta (s,t)\mathrm{\Theta }(\theta (t,s),v)(t\in {\mathrm{\Sigma }}_n,v\in {\mathrm{\Sigma }}_n^{\ast });$

and for words $u,v$:

$\mathrm{\Theta }(\epsilon ,v)=v,\mathrm{\Theta }(u,\epsilon )=\epsilon ,\mathrm{\Theta }(s{u}^{\mathrm{\prime }},v)=\mathrm{\Theta }(u^{\mathrm{\prime }},\mathrm{\Theta }(s,v))\mathrm{.}$

These rules are not a description by induction on the pair: the rule $\mathrm{\Theta }(s,tv)=\theta (s,t)\mathrm{\Theta }(\theta (t,s),v)$ expresses $\mathrm{\Theta }$ at $(s,tv)$ through its value at $(\theta (t,s),v)$, whose first entry $\theta (t,s)$ may itself be a two-letter word and is therefore not smaller. The rules are the recursion rules of the source, whose well-definedness is the content of its Lemma 4.32: in the right-complemented case the squares of the grid are filled in a unique way, the reversing procedure terminates or not independently of the order in which the steps are enumerated, and the rules above describe the resulting terminal pair. We therefore take $\mathrm{\Theta }(u,v)$ to be the partial map so defined, exactly as in the source, its agreement with the recursion rules being read off from the terminal pair by induction on the number of reversing steps (The principle of mathematical induction): $\mathrm{\Theta }(u,v)$ is defined if and only if the reversing of the negative--positive signed path $u^{-1}v$ (the letters of $u$ read negatively, then those of $v$ positively) reaches a terminal pair of blocks, and it is then the first block of that pair, while $\mathrm{\Theta }(v,u)$ is the second. Its four defining rules, and the fact that it is the least extension of $\theta$ satisfying them, are established as part (a) of Artin positive word reversing is complete ↗; the same item shows that $\mathrm{\Theta }$ is undefined exactly on those pairs of words that admit no common right multiple in $B_n^{+}$, so it is defined on every pair as soon as $\mathrm{\Delta }$-power divisibility is available (Every positive braid divides a power of the half twist on both sides): the totality of $\mathrm{\Theta }$ is a theorem, not part of the definition. The defining rules of the source are recovered as $\mathrm{\Theta }({\sigma }_i,{\sigma }_j)=\theta ({\sigma }_i,{\sigma }_j)$, $\mathrm{\Theta }(u_1{u}_2,v)=\mathrm{\Theta }(u_2,\mathrm{\Theta }(u_1,v))$ for $u_1$ nonempty, $\mathrm{\Theta }(u,{\epsilon }_x)=\epsilon$ and $\mathrm{\Theta }({\epsilon }_x,u)=u$.

Word reversing. A signed path is a finite word whose letters are signed copies $s^{+}$ or $s^{-}$ of letters $s\in {\mathrm{\Sigma }}_n$. These are formal words in the signed alphabet of Words in an alphabet with formal inverses, elementary cancellation, and reduced words, with concatenation as the word operation; negative letters are not morphisms of the positive monoid. For $u=s_1\cdots s_k$, the notation $u^{-1}$ means the formal word $s_k^{-1}\cdots s_1^{-1}$, in reversed order. A right-reversing step replaces a negative--positive subpath $s^{-1}t$ by $\theta (s,t)\theta (t,s{)}^{-1}$, using the defining relation $s\theta (s,t)=t\theta (t,s)$, and deletes $s^{-1}s$. This is the source's syntactic transformation on signed words, not an equality in $B_n^{+}$; it preserves the represented element in the presented group, although the number of signed letters may change. In the source's convention the pattern is a negative--positive pair: right-reversing acts on the signed path $u^{-1}v$, in which all letters of $u$ are read negatively and all letters of $v$ positively, and, when it terminates, it reaches a terminal positive--negative path $v^{\mathrm{\prime }}(u^{\mathrm{\prime }}{)}^{-1}$ whose two positive blocks satisfy $u{v}^{\mathrm{\prime }}{\equiv }^{+}v{u}^{\mathrm{\prime }}$. (Feeding the opposite orientation $u{v}^{-1}$ instead would already be terminal: it is the negative--positive path $u^{-1}v$ that encodes the comparison of the two positive words.)

The intended use. The pair $(\mathrm{\Theta }(u,v),\mathrm{\Theta }(v,u))$ is the pair that reversing is meant to compute: the source's Lemma II.4.32 identifies the terminal blocks of the reversing of $u^{-1}v$ with $v^{\mathrm{\prime }}=\mathrm{\Theta }(u,v)$ and $u^{\mathrm{\prime }}=\mathrm{\Theta }(v,u)$, and consequently $u\mathrm{\Theta }(u,v){\equiv }^{+}v\mathrm{\Theta }(v,u)$: the common word $u\mathrm{\Theta }(u,v)=v\mathrm{\Theta }(v,u)$ in $B_n^{+}$ is a common right multiple of $[u]$ and $[v]$, and it is their least common right multiple whenever a common right multiple exists. Both statements, together with the coherence of the recursion rules under the other evaluation order, are the content of Artin positive word reversing is complete ↗; no lcm property is used in this definition.

A worked value. By the recursion,

$\mathrm{\Theta }({\sigma }_2{\sigma }_1,{\sigma }_3)=\mathrm{\Theta }({\sigma }_1,\mathrm{\Theta }({\sigma }_2,{\sigma }_3))=\mathrm{\Theta }({\sigma }_1,{\sigma }_3{\sigma }_2)=\theta ({\sigma }_1,{\sigma }_3)\mathrm{\Theta }(\theta ({\sigma }_3,{\sigma }_1),{\sigma }_2)={\sigma }_3\mathrm{\Theta }({\sigma }_1,{\sigma }_2)={\sigma }_3{\sigma }_2{\sigma }_1,$

and likewise $\mathrm{\Theta }({\sigma }_1{\sigma }_2,{\sigma }_3{\sigma }_2)={\sigma }_3{\sigma }_2{\sigma }_1$ by the source's Example 4.11. Both values are used on the companion examples page.

• Only the two words $\mathrm{\Theta }(u,v)$ and $\mathrm{\Theta }(v,u)$ are needed on this page; they are the "two sides" of a rectangle whose vertical side carries $u$ and whose horizontal side carries $v$. Each of the two words records how far the other side has to be extended so that the two extensions match.
• The recursion rules are the algebraic transcription of the square-filling process of the source: the square on the letters $s,t$ has lower side $\theta (s,t)$ and right side $\theta (t,s)$, and the identity $s\theta (s,t)=t\theta (t,s)$ in $B_n^{+}$ is the commutativity of that square. The coherence of the two evaluation orders ("first the first letter of $u$, then the rest" versus "split the second argument") is the technical content of the source's Lemma II.4.32 and is established in Artin positive word reversing is complete ↗.
• No choice principle occurs: $\mathrm{\Theta }$ is computed on positive words by the four recursion rules above, and every verification below is a finite computation. Negative letters occur only in the signed paths that witness the reversing, and they are not elements of $B_n^{+}$; the recursion is partial in general, and its totality for the Artin presentation is the theorem of Every positive braid divides a power of the half twist on both sides together with Artin positive word reversing is complete ↗.