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

- $a≤b$ if $ac=b$, where $a,b,c∈B_{n}$. $a$ is called the left divisor of $b$.
- $g(a,b)=c$, if $cw=a$ and $cv=b$, such that $∣c∣$ is maximized, where $a,b,c,w,v∈B_{n}$. $c$ is called the greatest common divisor of $a$ and $b$.

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

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

$σ_{i}Δ=Δσ_{n−i}$ and $σ_{i}=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∈B_{n}$.

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

If $w∈B_{n}$, find the largest $k$, such that $Δ_{k}≤w$, then $w=Δ_{k}p_{′}$, and it’s a unique form.

If $w∈B_{n}$, first rewrite every $σ_{i}$ 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.

A positive braid $p$ is simple if $p∈D={x∣x≤Δ}$.

Note $D$ generates the braid group.

$w$ has the Garside normal form $Δ_{m}p$, then we define the following functions. - The infimum, or the delta exponent, of $w$, $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_{′}∈[w]$ if and only if $w=c_{−1}w_{′}c$ for some $c∈B_{n}$. One write $w∼w_{′}$ if $w_{′}∈[w]$

How can one check if $w∼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_{′}∈[w]$.

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

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

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

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

The summit set of $w$ is finite, and the size is bounded by $n_{λ(w)−∣Δ∣inf[w]}$. $f[w]=∣Δ∣λ(w)−∣p∣ $, or $∣p∣=λ(w)−∣Δ∣f[w]$. There are only finite many positive words with length $∣p∣$.

$w∼w_{′}$, $w,w_{′}∈B_{n}$, then there exist a $c∈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.

$w∈B_{n}$ and $x∈B_{n}$. For $a∈SS(w)$, if $x_{−1}ax∈SS(w)$, then $c_{−1}ac∈SS(w)$, where $c=g(x,Δ)$.

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

For $w,w_{′}∈B_{n}$, $w∼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$.