The Art Gallery Guardian

Garside Normal Form and Summit Sets


Note: This is just some notes I organized after reading the survey on computational problems in the braid group by Jonathan Boiser.

1 The Garside Normal Form

Definition1The Positive Braid Monoid

The positive braid monoid of nn strands is denoted as Bn+B_n^+. Such that Bn+BnB_n^+\in B_n and Bn+B_n^+ contain only word in the form σa1σal\sigma_{a_1}\ldots\sigma_{a_l}.

Definition2The order relation
  • aba\leq b if ac=bac = b, where a,b,cBn+a,b,c \in B_n^+. aa is called the left divisor of bb.
  • gcd(a,b)=c\gcd(a,b) = c, if cw=acw = a and cv=bcv = b, such that c|c| is maximized, where a,b,c,w,vBn+a,b,c,w,v\in B_n^+. cc is called the greatest common divisor of aa and bb.
Definition3The Fundamental Braid

The fundamental braid, or half-twist, on nn strands Δn=(σ1σn1)(σ1σn2)(σ1σ2)σ1 \Delta_n = (\sigma_1\ldots \sigma_{n-1})(\sigma_1\ldots\sigma_{n-2})\ldots(\sigma_1\sigma_2)\sigma_1 .

Δ\Delta is used for Δn\Delta_n if nn is obvious from the context.

σiΔ=Δσni\sigma_i\Delta = \Delta\sigma_{n-i} and σi1=xiΔ1\sigma_i^{-1} = x_i\Delta^{-1} for some positive word xix_i are two important theorems the reader should check. Define a function RR, such that wΔ=ΔR(w)w\Delta = \Delta R(w) is true for all wBnw\in B_n.

Definition4The Garside Normal Form

The Garside normal form of a word wBnw\in B_n is w=Δnmpw = \Delta_n^m p. pBn+p\in B^+_n, and Δ\Delta is not a factor of pp. We define inf(w)=m\inf(w)=m.

If wBn+w\in B^+_n, find the largest kk, such that Δkw\Delta^k \leq w, then w=Δkpw = \Delta^k p', and it’s a unique form.

If wBnw\in B_n, first rewrite every σik\sigma_i^{-k} in ww by (xi)kΔk(x_i)^k\Delta^{-k}, move all the Δ\Delta to the front, and we will have w=Δnpw = \Delta^{-n} p, where pp is a positive word. Then pp must have a normal form, let it be Δmq\Delta^{m}q. w=Δmnqw = \Delta^{m-n}q, and it is uniquely determined.

Note the length of the positive word pp in the garside normal form is a constant, because all equivalent elements in Bn+B^+_n have the same length.

Definition5Simple elements

A positive braid pp is simple if pD={xxΔ}p\in\mathcal{D} = \{x | x \leq \Delta\}.

Note D\mathcal{D} generates the braid group.

Definition6

ww has the Garside normal form Δmp\Delta^m p, then we define the following functions. - The infimum, or the delta exponent, of ww, inf(w)=m\inf(w) = m - The index of ww, λ(w)=p+mΔ\lambda(w) = |p| + m|\Delta|.

The index of ww is also hgh-g, where h,gh,g are the number of positive and negative generators respectively. No matter how ww is presented, the index is a constant. This is obvious because all braid relations doesn’t change the index.

2 The Summit Set

Let [w][w] be the conjugacy class of ww, in other words, w[w]w'\in[w] if and only if w=c1wcw = c^{-1}w'c for some cBnc\in B_n. One write www\sim w' if w[w]w'\in[w]

How can one check if www\sim w'? This is the conjugacy problem. Note [w][w] is not finite unless w=1w=1. Search through the entire set is impossible. The solution is similar to the word problem, it’s also about finding a ``normal form’’ for [w][w]. There are special subsets of [w][w], such that there exist an algorithm with input ww'. The algorithm output the subset if and only if w[w]w'\in [w].

One of the first set with this property is the summit set.

Define inf[w]=sup{inf(x)x[w]}\inf[w] = \sup \{\inf(x) | x \in [w]\}.

Definition7The Summit Set

The summit set of ww is written as SS(w)SS(w). SS(w)={xinf(x)=inf[w],x[w]} SS(w) = \{x | \inf(x) = \inf[w], x\in [w] \}

The summit set exists if there is an upper bound on mm. Manipulate the index formula, we have m=λ(w)pΔm = \frac{\lambda(w) - |p|}{|\Delta|}. mλ(w)Δm \leq \frac{\lambda(w)}{|\Delta|}, therefore mm is bounded above.

The summit set of ww is finite, and the size is bounded by nλ(w)Δinf[w]n^{\lambda(w) - |\Delta|\inf[w]}. inf[w]=λ(w)pΔ\inf[w] = \frac{\lambda(w) - |p|}{|\Delta|}, or p=λ(w)Δinf[w]|p| = \lambda(w) - |\Delta|\inf[w]. There are only finite many positive words with length p|p|.

Theorem8

www\sim w', w,wBnw,w'\in B_n, then there exist a cBn+c\in B_n^+, such that w=c1wcw=c^{-1}w'c.

w=(Δmp)1w(Δmp)w=(\Delta^m p)^{-1} w' (\Delta^m p), which means w=q1wqw=q^{-1} w' q, where q=ΔR(p)q = \Delta R(p) or pp, both are positive.

Theorem9

wBnw\in B_n and xBn+x\in B_n^+. For aSS(w)a \in SS(w), if x1axSS(w)x^{-1}ax\in SS(w), then c1acSS(w)c^{-1}ac \in SS(w), where c=gcd(x,Δ)c=\gcd(x,\Delta).

The theorem implies that every word in the conjugacy class can be reached by repeat conjugation of simple elements.

Theorem10

For w,wBnw,w'\in B_n, www\sim w' if and only if SS(w)=SS(w)SS(w) = SS(w')

3 Complexity

3.1 Complexity of the word problem

To solve the word problem with Garside normal form, one can always put it in the Δkp\Delta^{-k}p form in linear time. Then factor out the Δ\Delta divisors in pp, and test if the resulting word is 1.

Factoring out the divisors can be done in quadratic time with respect to the word length by using a refined version of the Garside normal form, Thurston’s left greedy normal form.

3.2 Complexity of the conjugacy problem

Given the theorems, one can devise the following algorithm to solve the conjugacy problem:

  1. Input ww and ww', present them in Garside normal form.
  2. Find SS(w)SS(w) and SS(w)SS(w').
  3. Test if SS(w)=SS(w)SS(w) = SS(w')

The algorithm to find SS(w)SS(w)

  1. conjugate the input ww with every simple element.
  2. Pick the set of produced elements, such that the Δ\Delta exponent is the largest.
  3. For each one of those elements, go though 1 again.
  4. If the process doesn’t produce more elements with larger Δ\Delta exponent, the summit set has been found.

The main complexity depend on the size of SS(w)SS(w). It is known SS(w)SS(w) could be exponential in ll and nn.

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