$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 $Δ^{m} σ_{a_{1}}^{e_{1}} \dots σ_{a_{k}}^{e_{k}}$ , such that $a_{i} \neq = a_{i + 1}$ , $e_{1}, e_{k} \geq 1$ and $e_{2}, \dots, e_{k - 1} \geq 2$ .

Proof

For any word $w \in B_{n}$ , the Garside normal form $Δ^{m} p$ is unique up to elements $p$ in $B_{n}^{+}$ and $p$ does not have a factor of $Δ$ . 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} Δ a_{i + 1}^{e_{i + 1} - 1}$ , which is a contradiction because $p$ doesn’t have a factor of $Δ$ .

Every word in that form is also in $B_{n}^{+}$ , and without $Δ$ factor.

It’s impossible to rewrite any word in this form with the relations $σ_{1} σ_{2} σ_{1} = σ_{2} σ_{1} σ_{2}$ . Therefore this form is unique.

Theorem2

The Garside normal form of $B_{3}$ is regular.

Proof

Let $A = {Δ, Δ^{- 1}, σ_{1}, σ_{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 = (Δ^{*} \cup (Δ^{- 1 *})) (X \cup X^{'})$ where $X = σ_{1}^{*} (σ_{2} σ_{2} σ_{2}^{*} σ_{1} σ_{1} σ_{1}^{*})^{*} ((σ_{2} σ_{2} σ_{2}^{*} σ_{1}^{*}) \cup σ_{2}^{*}))$ and $X^{'}$ is the same except the $σ_{2}$ and $σ_{1}$ are switched.

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

$M_{ϵ}$ exists, because the Garside normal form is unique, then $M_{ϵ}$ 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 (σ_{a_{1}} \dots σ_{a_{k}}) = σ_{3 - a_{1}} \dots σ_{3 - a_{k}}$ .

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

Consider $x$ case by case:

$Δ$ : The words differ in 1 $Δ$ are $Δ^{m} p$ and $Δ^{m + 1} R (p)$ .Assume $m$ is non-negative. At time $∣ m ∣ + 1$ , one encounters $Δ^{m} σ_{a_{1}}$ and $Δ^{m + 1}$ , which has a distance of $2$ . At time $∣ m ∣ + 2$ , $Δ^{m} σ_{a_{1}} σ_{a_{2}}$ and $Δ^{m + 1} σ_{3 - a_{1}} = Δ^{m} σ_{a_{1}} Δ$ , which also has distance 2. By induction, the distance is 2 till the end, where one has $Δ^{m} σ_{a_{1}} \dots σ_{a_{k}}$ and $Δ^{m} σ_{a_{1}} \dots σ_{a_{k - 1}} Δ$ . With one more step, it decrease the distance to $1$ . When $m$ is negative, it’s similar.
$Δ^{- 1}$ : Similar to $Δ$ case.
$σ_{1}$ : There are two cases. If the word end with $σ_{1}$ , or end with $σ_{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 $σ_{2}$ , then the words are $Δ^{m} p σ_{1}^{k} σ_{2}$ and $Δ^{m} p σ_{1}^{k} σ_{2} σ_{1}$ . The second word in normal form is $Δ^{m + 1} R (p σ_{1}^{k - 1})$ . Note the first word is $Δ^{m} p σ_{1}^{k - 1} \cdot σ_{1} σ_{2}$ We can use the fact that adding the $Δ$ have fellow traveler property to prove this also have that property.
$σ_{2}$ : Similar to $σ_{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 2011-07-11.

Tags: automatic group, braid group, BSU REU.

B3​ is automatic, a simple proof

$B_{3}$ is automatic, a simple proof