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 $n$ strands is denoted as $B_{n}^{+}$ . Such that $B_{n}^{+} \in B_{n}$ and $B_{n}^{+}$ contain only word in the form $σ_{a_{1}} \dots σ_{a_{l}}$ .

Definition2The order relation

$a \leq b$ if $a c = b$ , where $a, b, c \in B_{n}^{+}$ . $a$ is called the left divisor of $b$ .
$g cd (a, b) = c$ , if $c w = a$ and $c v = b$ , such that $∣ c ∣$ is maximized, where $a, b, c, w, v \in B_{n}^{+}$ . $c$ is called the greatest common divisor of $a$ and $b$ .

Definition3The Fundamental Braid

The fundamental braid, or half-twist, on $n$ strands $Δ_{n} = (σ_{1} \dots σ_{n - 1}) (σ_{1} \dots σ_{n - 2}) \dots (σ_{1} σ_{2}) σ_{1}$ .

$Δ$ is used for $Δ_{n}$ if $n$ is obvious from the context.

$σ_{i} Δ = Δ σ_{n - i}$ and $σ_{i}^{- 1} = x_{i} Δ^{- 1}$ for some positive word $x_{i}$ are two important theorems the reader should check. Define a function $R$ , such that $w Δ = Δ R (w)$ is true for all $w \in B_{n}$ .

Definition4The Garside Normal Form

The Garside normal form of a word $w \in B_{n}$ is $w = Δ_{n}^{m} p$ . $p \in B_{n}^{+}$ , and $Δ$ is not a factor of $p$ . We define $in f (w) = m$ .

If $w \in B_{n}^{+}$ , find the largest $k$ , such that $Δ^{k} \leq w$ , then $w = Δ^{k} p^{'}$ , and it’s a unique form.

If $w \in B_{n}$ , first rewrite every $σ_{i}^{- k}$ in $w$ by $(x_{i})^{k} Δ^{- k}$ , move all the $Δ$ to the front, and we will have $w = Δ^{- n} p$ , where $p$ is a positive word. Then $p$ must have a normal form, let it be $Δ^{m} q$ . $w = Δ^{m - n} q$ , and it is uniquely determined.

Note the length of the positive word $p$ in the garside normal form is a constant, because all equivalent elements in $B_{n}^{+}$ have the same length.

Definition5Simple elements

A positive braid $p$ is simple if $p \in D = {x ∣ x \leq Δ}$ .

Note $D$ generates the braid group.

Definition6

$w$ has the Garside normal form $Δ^{m} p$ , then we define the following functions. - The infimum, or the delta exponent, of $w$ , $in f (w) = m$ - The index of $w$ , $λ (w) = ∣ p ∣ + m ∣Δ∣$ .

The index of $w$ is also $h - g$ , where $h, g$ are the number of positive and negative generators respectively. No matter how $w$ 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]$ be the conjugacy class of $w$ , in other words, $w^{'} \in [w]$ if and only if $w = c^{- 1} w^{'} c$ for some $c \in B_{n}$ . One write $w \sim w^{'}$ if $w^{'} \in [w]$

How can one check if $w \sim w^{'}$ ? This is the conjugacy problem. Note $[w]$ is not finite unless $w = 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]$ . There are special subsets of $[w]$ , such that there exist an algorithm with input $w^{'}$ . The algorithm output the subset if and only if $w^{'} \in [w]$ .

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

Define $in f [w] = sup {in f (x) ∣ x \in [w]}$ .

Definition7The Summit Set

The summit set of $w$ is written as $SS (w)$ . $SS (w) = {x ∣ in f (x) = in f [w], x \in [w]}$

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

The summit set of $w$ is finite, and the size is bounded by $n^{λ (w) - ∣Δ∣ i n f [w]}$ . $in f [w] = \frac{λ ( w ) - ∣ p ∣}{∣Δ∣}$ , or $∣ p ∣ = λ (w) - ∣Δ∣ in f [w]$ . There are only finite many positive words with length $∣ p ∣$ .

Theorem8

$w \sim w^{'}$ , $w, w^{'} \in B_{n}$ , then there exist a $c \in B_{n}^{+}$ , such that $w = c^{- 1} w^{'} c$ .

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

Theorem9

$w \in B_{n}$ and $x \in B_{n}^{+}$ . For $a \in SS (w)$ , if $x^{- 1} a x \in SS (w)$ , then $c^{- 1} a c \in SS (w)$ , where $c = g cd (x, Δ)$ .

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

Theorem10

For $w, w^{'} \in B_{n}$ , $w \sim w^{'}$ if and only if $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 $Δ^{- k} p$ form in linear time. Then factor out the $Δ$ divisors in $p$ , 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 $w$ and $w^{'}$ , present them in Garside normal form.
Find $SS (w)$ and $SS (w^{'})$ .
Test if $SS (w) = SS (w^{'})$

The algorithm to find $SS (w)$

conjugate the input $w$ 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 $SS (w)$ . It is known $SS (w)$ could be exponential in $l$ and $n$ .

Posted by Chao Xu on 2011-07-05.

Tags: braid group, BSU REU.