The Art Gallery Guardian

B_3 is automatic, a simple proof

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


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.


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.


The Garside normal form of B_3 is regular.


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


B_3 is automatic.

Posted by Chao Xu on 2011-07-11.
Tags: automatic group, braid group, BSU REU.