The Art Gallery Guardian

B3B_3 is automatic, a simple proof

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


The Garside normal form is unique in B3B_3, and is in the form Δmσa1e1σakek\Delta^m\sigma_{a_1}^{e_1}\ldots\sigma_{a_k}^{e_k}, such that aiai+1a_i \neq a_{i+1}, e1,ek1e_1,e_k\geq 1 and e2,,ek12e_2,\ldots,e_{k-1} \geq 2.


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

Every pp must be in this form. If for some k>i>1k>i>1, ei=1e_i=1, then ai1ei1aieiai+1ei+1=ai1ei11Δai+1ei+11a_{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 pp doesn’t have a factor of Δ\Delta.

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

It’s impossible to rewrite any word in this form with the relations σ1σ2σ1=σ2σ1σ2\sigma_1\sigma_2\sigma_1 = \sigma_2\sigma_1\sigma_2. Therefore this form is unique.


The Garside normal form of B3B_3 is regular.


Let A={Δ,Δ1,σ1,σ2}A=\{\Delta,\Delta^{-1},\sigma_1,\sigma_2\}, then AA generates GG. The Garside normal form is a regular language over AA because they exist an explicit regular expression RR that matches it.

R=(Δ(Δ1))(XX)R = (\Delta^*\cup(\Delta^{-1*}))(X\cup X') where X=σ1(σ2σ2σ2σ1σ1σ1)((σ2σ2σ2σ1)σ2))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 XX' is the same except the σ2\sigma_2 and σ1\sigma_1 are switched.

Let WW be a FSA generated by the regular expression RR.

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

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

Define R(σa1σak)=σ3a1σ3akR(\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 xx case by case:

  • Δ\Delta: The words differ in 1 Δ\Delta are Δmp\Delta^mp and Δm+1R(p)\Delta^{m+1}R(p).Assume mm is non-negative. At time m+1|m|+1, one encounters Δmσa1\Delta^m\sigma_{a_1} and Δm+1\Delta^{m+1}, which has a distance of 22. At time m+2|m|+2, Δmσa1σa2\Delta^m\sigma_{a_1}\sigma_{a_2} and Δm+1σ3a1=Δmσa1Δ\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 Δmσa1σak\Delta^m\sigma_{a_1}\ldots\sigma_{a_k} and Δmσa1σak1Δ\Delta^m\sigma_{a_1}\ldots\sigma_{a_{k-1}}\Delta. With one more step, it decrease the distance to 11. When mm is negative, it’s similar.
  • Δ1\Delta^{-1}: Similar to Δ\Delta case.
  • σ1\sigma_1: There are two cases. If the word end with σ1\sigma_1, or end with σ2b\sigma_2^b, where b2b\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\sigma_2, then the words are Δmpσ1kσ2\Delta^mp\sigma_1^k\sigma_2 and Δmpσ1kσ2σ1\Delta^mp\sigma_1^k\sigma_2\sigma_1. The second word in normal form is Δm+1R(pσ1k1)\Delta^{m+1}R(p\sigma_1^{k-1}). Note the first word is Δmpσ1k1σ1σ2\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.
  • σ2\sigma_2: Similar to σ2\sigma_2 case.

The fellow traveler property is true for each generator.

We now have the theorem


B3B_3 is automatic.

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