# $B_3$ is automatic, a simple proof

$B_3$ is particularly nice to analyze due to the uniqueness of the Garside normal form.

Theorem1

The Garside normal form is unique in $B_3$, and is in the form $\Delta^m\sigma_{a_1}^{e_1}\ldots\sigma_{a_k}^{e_k}$, such that $a_i \neq a_{i+1}$, $e_1,e_k\geq 1$ and $e_2,\ldots,e_{k-1} \geq 2$.

Proof

For any word $w\in B_n$, the Garside normal form $\Delta^m p$ is unique up to elements $p$ in $B_n^+$ and $p$ does not have a factor of $\Delta$. Now we show that there is only one way to write $p$.

Every $p$ must be in this form. If for some $k>i>1$, $e_i=1$, then $a_{i-1}^{e_{i-1}}a_i^{e_i}a_{i+1}^{e_{i+1}} = a_{i-1}^{e_{i-1} -1}\Delta a_{i+1}^{e_{i+1}-1}$, which is a contradiction because $p$ doesn't have a factor of $\Delta$.

Every word in that form is also in $B_n^+$, and without $\Delta$ factor.

It's impossible to rewrite any word in this form with the relations $\sigma_1\sigma_2\sigma_1 = \sigma_2\sigma_1\sigma_2$. Therefore this form is unique.

Theorem2

The Garside normal form of $B_3$ is regular.

Proof

Let $A=\{\Delta,\Delta^{-1},\sigma_1,\sigma_2\}$, then $A$ generates $G$. The Garside normal form is a regular language over $A$ because they exist an explicit regular expression $R$ that matches it.

$R = (\Delta^*\cup(\Delta^{-1*}))(X\cup X')$ where $X = \sigma_1^*(\sigma_2\sigma_2\sigma_2^*\sigma_1\sigma_1\sigma_1^*)^* ((\sigma_2\sigma_2\sigma_2^*\sigma_1^*)\cup \sigma_2^*))$ and $X'$ is the same except the $\sigma_2$ and $\sigma_1$ are switched.

Let $W$ be a FSA generated by the regular expression $R$.

$M_\epsilon$ exists, because the Garside normal form is unique, then $M_\epsilon$ accepts all language of the form $\{(w,w)|w\in L(W)\}$. It have the complete same structure as $W$, but replacing every edge $x$ with $(x,x)$.

Instead of construct $M_x$ directly, we only need to prove the fellow traveler property is true. This can be done by checking it is true for every $M_x$ independently.

Define $R(\sigma_{a_1}\ldots\sigma_{a_k}) = \sigma_{3-a_1}\ldots\sigma_{3-a_k}$.

Note that every generator has a constant distance from another generator.

Consider $x$ case by case:

• $\Delta$: The words differ in 1 $\Delta$ are $\Delta^mp$ and $\Delta^{m+1}R(p)$.Assume $m$ is non-negative. At time $|m|+1$, one encounters $\Delta^m\sigma_{a_1}$ and $\Delta^{m+1}$, which has a distance of $2$. At time $|m|+2$, $\Delta^m\sigma_{a_1}\sigma_{a_2}$ and $\Delta^{m+1}\sigma_{3-a_1} = \Delta^m\sigma_{a_1}\Delta$, which also has distance 2. By induction, the distance is 2 till the end, where one has $\Delta^m\sigma_{a_1}\ldots\sigma_{a_k}$ and $\Delta^m\sigma_{a_1}\ldots\sigma_{a_{k-1}}\Delta$. With one more step, it decrease the distance to $1$. When $m$ is negative, it's similar.
• $\Delta^{-1}$: Similar to $\Delta$ case.
• $\sigma_1$: There are two cases. If the word end with $\sigma_1$, or end with $\sigma_2^b$, where $b\geq 2$, then the two words are exactly the same until the end. Thus implies the fellow traveler property. If the word end with a single $\sigma_2$, then the words are $\Delta^mp\sigma_1^k\sigma_2$ and $\Delta^mp\sigma_1^k\sigma_2\sigma_1$. The second word in normal form is $\Delta^{m+1}R(p\sigma_1^{k-1})$. Note the first word is $\Delta^mp\sigma_1^{k-1} \cdot \sigma_1\sigma_2$ We can use the fact that adding the $\Delta$ have fellow traveler property to prove this also have that property.
• $\sigma_2$: Similar to $\sigma_2$ case.

The fellow traveler property is true for each generator.

We now have the theorem

Theorem3

$B_3$ is automatic.

Posted by Chao Xu on .
Tags: automatic group, braid group, BSU REU.