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
The positive braid monoid of strands is denoted as . Such that and contain only word in the form .
- if , where . is called the left divisor of .
- , if and , such that is maximized, where . is called the greatest common divisor of and .
The fundamental braid, or half-twist, on strands .
is used for if is obvious from the context.
and for some positive word are two important theorems the reader should check. Define a function , such that is true for all .
The Garside normal form of a word is . , and is not a factor of . We define .
If , find the largest , such that , then , and it's a unique form.
If , first rewrite every in by , move all the to the front, and we will have , where is a positive word. Then must have a normal form, let it be . , and it is uniquely determined.
Note the length of the positive word in the garside normal form is a constant, because all equivalent elements in have the same length.
A positive braid is simple if .
Note generates the braid group.
has the Garside normal form , then we define the following functions. - The infimum, or the delta exponent, of , - The index of , .
The index of is also , where are the number of positive and negative generators respectively. No matter how is presented, the index is a constant. This is obvious because all braid relations doesn't change the index.
2 The Summit Set
Let be the conjugacy class of , in other words, if and only if for some . One write if
How can one check if ? This is the conjugacy problem. Note is not finite unless . Search through the entire set is impossible. The solution is similar to the word problem, it's also about finding a ``normal form'' for . There are special subsets of , such that there exist an algorithm with input . The algorithm output the subset if and only if .
One of the first set with this property is the summit set.
The summit set of is written as .
The summit set exists if there is an upper bound on . Manipulate the index formula, we have . , therefore is bounded above.
The summit set of is finite, and the size is bounded by . , or . There are only finite many positive words with length .
, , then there exist a , such that .
, which means , where or , both are positive.
and . For , if , then , where .
The theorem implies that every word in the conjugacy class can be reached by repeat conjugation of simple elements.
For , if and only if
3.1 Complexity of the word problem
To solve the word problem with Garside normal form, one can always put it in the form in linear time. Then factor out the divisors in , 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:
- Input and , present them in Garside normal form.
- Find and .
- Test if
The algorithm to find
- conjugate the input with every simple element.
- Pick the set of produced elements, such that the exponent is the largest.
- For each one of those elements, go though 1 again.
- If the process doesn't produce more elements with larger exponent, the summit set has been found.
The main complexity depend on the size of . It is known could be exponential in and .