We saw in the first chapter a way to describe the braid group:
we specified some elementary braids, the generators
and then we found the relations, moves that can transform a word without changing the braid it describes
But we still don't know all about this group!
For example, the relations don't say how to check if two words are equivalent
Here we have two words and we construct a sequence of relations that connect them
At each stage we just replace the part of the word inside the yellow box with an equivalent one
We use the two kinds of relations and the insertion or deletion of a generator and its inverse
In each level we change the word, but the braid it represents remains the same
It is not so easy to note immediately, just looking at the two words, that they are equivalent
This becomes evident when we construct the sequence
What about these two words? We try to construct a sequence as before to connect them
It can be a hard job to construct such a sequence of words using the relations
We could spend our whole life looking for one, without ever finding it
we will never know whether no sequence exists or we haven't been lucky enough to find it
That's why we need another way to handle the question
More precisely, we wish to construct a machinery that takes two arbitrary words as input,
makes some operations and computations
and gives as output the answer "yes" if the two words are equivalent
Following the same procedure, the answer will be "no" if the two words represent different braids
Such a procedure is called an algorithm
We are lucky: for braids we have such an algorithm Let's look inside it
First of all we simplify the problem:
two words represent the same braid if and only if one, composed with the inverse of the other, is equivalent to the trivial braid
Therefore, we can reformulate our problem: given an arbitrary word, decide if it is equivalent to the identity
Or in other words: is there a way to transform the given word into "1"?
Look at this braid: the color of the bubbles is enough to know where each strand ends
If the bubbles at the same level, on the left and on the right, have the same colors, then the braid is called pure
Of course two equivalent braids will have the bubbles with the same color arrangement
So a braid that is equivalent to the trivial one has to be pure That's why we consider only pure braids in this chapter
Each pure braid can be decomposed into blocks in this way:
in the first block, all the strands but the last are straight. The green strand can link to the others
In the second block, all the strands but the second-to-last are straight. The yellow strand can link only to the strands below
And so on until the last block, in which the second strand can link to the first one
We know that for each braid there are lots of representatives
We would like to choose a specific one of them to describe the braid It will be called the normal form
Now, we need an algorithm that puts any arbitrary word in its normal form Artin's braid combing is such an algorithm
Here we show it on a non trivial braid:
first copy the braid
and delete the last strand, replacing it with a trivial one
Compose this braid with its inverse, getting the identity braid
So, composing the original braid with it, we don't change the braid
On the left side we have a braid that can be put into the desired form, with all the strands straight except the top one
This is the first block
We deform the strands so that the green one encircles a strand passing behind the others,
goes back to the initial position, encircles another strand, and so on
This piece is combed
Do the same procedure on the right side: copy the braid,
replace the yellow strand with a trivial one,
compose this braid with its inverse getting a trivial braid
compose this trivial braid with the original one
and tidy up the second block
We put it in a form such that the yellow strand links only with the blue one and the red one
We have combed the second block
Now the last block is easy to rearrange
We have put the braid in its normal form
Artin proved that a braid is trivial if and only if, once it is combed, every block is trivial,
meaning that it can be represented with no crossings at all
So our braid is not trivial
And we have an algorithm to check it:
We start with a pure braid Comb it into blocks
If one of the blocks is not trivial, terminate, answering "no"
Otherwise continue with the next block
If all the blocks are trivial, we get the trivial braid and the answer is "yes, the input word is equivalent to the identity"
This algorithm works but Artin himself was not satisfied with it
In his paper "Theory of braids" he writes:
Why did he write so? Combing is an extremely slow method
The complexity of the algorithm is very high:
if we draw a graph showing the mean time needed to comb a braid as a function of the number of crossings, the curve is very steep
Increasing the input size by a small amount the time grows very fast and may be too long even for a computer
This is why mathematicians look for other, quick, algorithms
The fastest found so far is probably the one proposed about 15 years ago by Dehornoy, a French mathematician
It is based on manipulating braids and is called handle reduction
This is a handle: he red strand passes in front of the other strand just above and then in front of the strand just below
A handle can also pass twice behind the other strands: this is another handle
This is not a handle because it faces downwards
Neither this is a handle: the blue strand passes once in front of the strand below and once behind
Reducing handles means to move these pieces of string
In this way we change the word but the braid it represents remains the same
A theorem of Dehornoy ensures that a word with no handles is either empty or it represents a nontrivial braid
Let's sketch the handle reduction algorithm: take a pure braid
If there are no handles and the braid has at least one crossing, terminate, answering "no"
Otherwise, if there are handles, find the one that ends first and reduce it
Continue like this until there are no more handles:
if the braid is not trivial, the answer is "no"
If after reducing all the handles, the braid is trivial, then the answer will be "yes"
But there is a problem: what if the algorithm does not end?
It could maybe go into a loop: if it comes back to a word that it has already met,
the steps after that one will always be the same and the algorithm will never stop
In fact this is never the case: it has been shown that the algorithm always terminates
We don't yet know the complexity of this algorithm but we have some experimental estimates
and it seems much faster than the other known algorithms
Combing, handles: the formalization of braids in terms of words is really powerful!