Left and right divisibility for positive braids

Let $n\in \mathbb{N}$, let $B_n^{+}$ be the positive braid monoid of Positive braid monoid with its homogeneous length $\mathrm{\ell }\text{\hspace{0.17em}⁣}:B_n^{+}\to \mathbb{N}$ of Positive artin relations preserve homogeneous length and its two cancellation laws of The positive braid monoid is left and right cancellative. For $a,b\in B_n^{+}$ put

$a{\preccurlyeq }_{L}b:⟺\mathrm{\exists }c\in B_n^{+}(b=ac),a{\preccurlyeq }_{R}b:⟺\mathrm{\exists }c\in B_n^{+}(b=ca)\mathrm{.}$

In words: $a$ is a left divisor (a prefix) of $b$, respectively a right divisor (a suffix) of $b$, if $b$ can be written as a product with $a$ on the left, respectively on the right. The corresponding strict relations are $a{\prec }_{L}b⟺a{\preccurlyeq }_{L}b$ and $a\mathrm{\ne }b$, and $a{\prec }_{R}b⟺a{\preccurlyeq }_{R}b$ and $a\mathrm{\ne }b$.

Basic properties. All of the following are immediate from the definition, the multiplicativity of $\mathrm{\ell }$ and the fact that $\mathrm{\ell }(x)=0$ forces $x=1$:

(i) ${\preccurlyeq }_L$ and ${\preccurlyeq }_R$ are partial orders on $B_n^{+}$. Reflexivity uses $b=b\cdot 1$; transitivity uses associativity: if $b=au$ and $c=bv$, then $c=a(uv)$, and if $b=ua$ and $c=vb$, then $c=(vu)a$; antisymmetry uses additivity of the length in $\mathbb{N}$: if $b=ac$ and $a=bd$ then $\mathrm{\ell }(b)=\mathrm{\ell }(a)+\mathrm{\ell }(c)$ and $\mathrm{\ell }(a)=\mathrm{\ell }(b)+\mathrm{\ell }(d)$, whence $\mathrm{\ell }(c)+\mathrm{\ell }(d)=0$ in $\mathbb{N}$, so $\mathrm{\ell }(c)=\mathrm{\ell }(d)=0$, hence $c=d=1$ and $a=b=ac=b$ (here $\mathrm{\ell }(x)=0$ happens only for $x=1$).

(ii) Each order is compatible with multiplication on its matching side: for every $x\in B_n^{+}$, $a{\preccurlyeq }_{L}b⟺xa{\preccurlyeq }_{L}xb,a{\preccurlyeq }_{R}b⟺ax{\preccurlyeq }_{R}bx\mathrm{.}$ For the forward implications, write $b=ac$ or $b=ca$ and use the same witness $c$ after multiplying on the left or right, respectively. The reverse implications follow by left or right cancellation, respectively. Left cancellation makes the witness $c$ in $b=ac$ unique, and right cancellation makes the witness in $b=ca$ unique.

(iii) Length is monotone for both orders: $a{\preccurlyeq }_{L}b$ or $a{\preccurlyeq }_{R}b$ implies $\mathrm{\ell }(a)\le \mathrm{\ell }(b)$, with equality if and only if $a=b$. Hence ${\prec }_L$ and ${\prec }_R$ are well founded by length, and the strict relations are exactly the relations $b=ac$ with $c\mathrm{\ne }1$, respectively $b=ca$ with $c\mathrm{\ne }1$.

(iv) Reversal exchanges the two orders. With $\rho$ the reversal anti-automorphism of The positive braid monoid is left and right cancellative, $b=ac⟺\rho (b)=\rho (c)\rho (a)$; hence $a{\preccurlyeq }_{L}b⟺\rho (a){\preccurlyeq }_R\rho (b)$ and $a{\preccurlyeq }_{R}b⟺\rho (a){\preccurlyeq }_L\rho (b)$. This is the only tool by which statements about ${\preccurlyeq }_L$ are transported to ${\preccurlyeq }_R$ below; the two orders are nevertheless distinct in general (the companion page computes a positive braid pair with different left and right meets), so neither order may be silently replaced by the other.

(v) Normalisation. Since $B_n^{+}$ has no nontrivial invertible element ($\mathrm{\ell }(x)=0$ only for $x=1$), the relation ${\preccurlyeq }_L$ has the "divisibility" reading fixed in the source: $a{\preccurlyeq }_{L}b$ means that $a$ occurs as a prefix of the positive braid $b$, and the set of left divisors of $b$ is finite — indeed contained in the classes of words of length at most $\mathrm{\ell }(b)$, and there are only finitely many such classes because there are finitely many words of any fixed length over the finite alphabet ${\mathrm{\Sigma }}_n$.

Least common multiples and greatest common divisors. For a nonempty subfamily $X\subseteq B_n^{+}$, a common left multiple of $X$ is an element $m$ with $x{\preccurlyeq }_{L}m$ for every $x\in X$, and a left-lcm of $X$ is a common left multiple $m$ such that $m{\preccurlyeq }_L{m}^{\mathrm{\prime }}$ for every common left multiple $m^{\mathrm{\prime }}$ of $X$; common right multiples and right-lcms are defined in the same way with ${\preccurlyeq }_R$. Dually, a common left divisor of $X$ is an element $d$ with $d{\preccurlyeq }_{L}x$ for every $x\in X$, and a left-gcd of $X$ is a common left divisor $d$ with $d^{\mathrm{\prime }}{\preccurlyeq }_{L}d$ for every common left divisor $d^{\mathrm{\prime }}$; the right-hand notions are analogous. Because both orders are antisymmetric, lcms and gcds are unique when they exist, and we then write ${\bigvee }_{L}X$, ${\bigwedge }_{L}X$, ${\bigvee }_{R}X$, ${\bigwedge }_{R}X$; for two elements we write $a{\vee }_{L}b$, $a{\wedge }_{L}b$, and so on.

Conventions. The letters $L$ and $R$ always refer to the side on which the smaller element is written: $a{\preccurlyeq }_{L}b$ if $b=ac$, and $a{\preccurlyeq }_{R}b$ if $b=ca$. For $n\le 1$ the monoid $B_n^{+}$ has one element and both orders are the equality relation. No choice principle is used: the witnesses $c$ are elements of a monoid of words, and uniqueness of the witnesses is proved by cancellation, not chosen.

• These are the orders of GM Section 4, printed pp. 26--27 ("a is a prefix of b"), restricted to the positive monoid. GM writes $\preccurlyeq$ for the prefix order and $\succcurlyeq$ for its mirror image; because this page also needs the right-hand version systematically, both orders are named here, and the letters $L,R$ record which side the smaller element sits on.
• Antisymmetry is proved without cancellation, from $\mathrm{\ell }\ge 0$ and $\mathrm{\ell }(x)=0\Rightarrow x=1$ alone; cancellation enters only through the uniqueness of the witness and the converse implications in (ii).
• Nothing here extends the orders to the braid group $B_n$; that extension is Left and right divisibility extend to lattice orders on the braid group and needs the Ore embedding (The group of fractions of the positive braid monoid is the Artin braid group).