Handle Reduction

This project was partially supported by ANR TheoGar.
The content and the images are based on this text by Patrick Dehornoy.

What is Handle Reduction?

Handle Reduction is a method, better an algorithm, to manipulate braids. It solves the Braid Triviality Problem, i.e. applying it to a braid you can say whether the strands are in fact woven or if you can untie them by manipulating them.
Other algorithms are known which solve this problem, but this one is perhaps more efficient and faster than the other ones: when properly implemented, it can compare diagrams involving thousands of crossings in less than one second.
To explain it more clearly, let us introduce braids, diagrams, braid words, handles...

What is a braid?

A braid is a collection of curves, called strands, in the three dimensional space. Braids are the mathematical objects that encode the structure of physical braids, as the plaits you can tie in the hair. A braid can have an arbitrary number of strands, which can be interlaced and are fixed at the top and the bottom. The strands are imagined to ‘flow’ from top to bottom and can not turn upwards.

How can a braid be represented?

The most common way to represent a braid is to draw a diagram, a picture consisting of strands that cross, on the shape of the following image. Precisely, a diagram as above is called an n-strand braid diagram if it involves n strands. For instance, the above diagram is a 4 strand braid diagram.
A diagram can be seen as the plane projection of a braid and it must obey the following rules:
• the strands are imagined to “flow” from top to bottom: no U-turn allowed!
• the crossings are at different vertical levels
• at each crossing, one strand is interrupted. This means that the broken strand passes behind the continuous one in the three dimensional braid.

How to describe a braid diagram?

In order to describe a braid diagram, we can encode it using a braid word, i.e., a finite sequence of letters ‘a’, ‘A’, ‘b’, ‘B’, etc. When considered from top to bottom, a braid diagram consists of a finite sequence of crossings. In order to describe it, it sufficies to specify them, saying which strands cross, and which one passes over the other.
Traditionally, one numbers the positions from 1 to n in an n-strand braid diagram, and one calls a (or σ1) the crossing where the strand at position 2 crosses over the strand at position 1, then b (or σ2) the crossing where the strand at position 3 crosses over the strand at position 2, etc.
Symmetrically, we shall use A (or σ1-1) for the crossing where the strand at position 1 crosses over the strand at position 2, then B (or σ2-1) the crossing where the strand at position 2 crosses over the strand at position 3, etc.

a    →     σ1    → ,       A    →     σ1-1    → b    →     σ2    → ,       B    →     σ2-1    → For instance, the braid diagram in the figure below is encoded by the word BcbACb (or σ2-1 σ3 σ2 σ1-1 σ3-1 σ2). Viceversa, if a word is given, it is possible to draw a unique diagram corresponding to it. This ensures that diagrams and words contain the same amount of information.

When are two braids “equal”?

Two braids are said to be isotopic if one can be deformed into the other in a continuous manner, i.e. if it is possible to obtain a braid from the other by moving the strands without letting them intersect and keeping the ends fixed.
For instance, the following two images show diagrams associated to isotopic braids and a movement which transforms a braid into the other. = =  = = There are other two equivalent ways of describing the isotopy of braids, defined on diagrams and on braid words.

One says that two diagrams are equivalent if one can be obtained from the other by a finite sequence of the following moves:
• at contiguous levels introduce or delete two crossings that are inverse one of the other, as in the first row of the figure above;
• exchange two crossings at contiguous levels if the first crossing does not involve any of the strands that form the second one;
• suppose there are three contiguous levels with the same type of crossings, of which the first and the third one are in the same position and the second one is just on the right (or on the left). Then this last crossing can be brought to the left (or to the right) of the other two crossings. For instance, see the second row of the figure above.
It can be shown that two diagrams are equivalent if and only if the braids they encode are isotopic.

One says that two braid words are equivalent if one can be obtained from the other by a finite sequence of the following moves:
• introduce or delete two adjacent letters that are inverse one of the other; for instance it is possible to go from cABbab to cAab and viceversa;
• exchange two adjacent letters if they are not contiguous in the alphabetical order; for instance it is possible to go from cABbab to AcBbab and viceversa;
• if s and r are contiguous letters in the alphabetical order, substitute srs with rsr or viceversa; for instance it is possible to go from cABbab to cABaba and viceversa.
Note that these moves on words encode exactly the same changes described with the moves on diagrams. It is then easy to note that two words are equivalent if and only if the diagrams they describe are equivalent.
Thus we can translate the puzzling problem of isotopy of curves in the three dimensional space into a problem on diagrams or words which can be handled in an easier way.

What is the Braid Isotopy Problem?

The Braid Isotopy Problem is the algorithmic problem:

Given two braids, decide whether they are isotopic.

We described two equivalent ways of chacking the isotopy of braids, defined on diagrams and on braid words. Thus, the Braid Isotopy Problem can be rephrased in two ways:

Given two braid diagrams, decide whether they are equivalent.

Given two braid words, decide whether they are equivalent.

Is the Braid Isotopy Problem a difficult problem?

The Braid Isotopy Problem is neither very easy, nor very difficult. It has been solved for the first time by the mathematician Emil Artin in the 1930's. Today, many different solutions are known, actually more than a dozen. They rely on various approaches, but all require relatively sophisticated results about braids. We describe one of these methods, called handle reduction.

What is the Braid Triviality Problem?

We would like to know whether a braid can be untied by moving its strands. For instance, the braid you tie in the hair can not be untied, once you fix it with a band.
One says that a braid diagram is trivial if it is equivalent to a diagram with no crossing at all. The Braid Triviality Problem is the algorithmic problem:

Given a braid diagram, decide whether it is trivial.

The diagram with no crossing is encoded by the empty word (the word with no letter!), so the Braid Triviality Problem can be rephrased as:

Given a braid word, decide whether it is equivalent to the empty word.

Are the Braid Isotopy Problem and the Braid Triviality Problem connected?

Yes, they are indeed equivalent problems.
First, the Braid Triviality Problem is a special case of the Braid Isotopy Problem, where one of the braids is trivial (or equivalently one of the words is empty). So each solution to the latter problem automatically gives a solution to the former one.
Viceversa, if D and D' are n-strand braid diagrams, construct the diagram D'' by stacking the image of D' in a horizontal mirror over D. One can check that D and D' are equivalent if and only if D'' is trivial. Thus, any solution to the Braid Triviality Problem leads to a solution to the Braid Isotopy Problem.
If w and w' are the words corresponding to D and D' respectively, we can easily write the word w'' corresponding to D'': we write the letters of w' in reverse order exchanging uppercase with lowercase. To this word, which is called the inverse of w', we attach all the letters of w in their order. This is w''.
For instance, if w is bAcb and w' is aBAcA, the inverse of w' is aCabA and w is aCabAbAcb.

What is a handle?

A handle is a braid word of a special type.
Let s indicate any lower case letter (thus one of a, b, ...) and S the corresponding upper case letter. Let us define a s-handle to be a braid word of the form s...S, where all letters between s and S (if any) lie before s in alphabetical order.
Symmetrically, a S-handle is defined to be a braid word of the form S...s, where all letters between S and s (if any) lie before s in alphabetical order.
For instance, the words cbAC and cBAbC are both c-handles.
We say that a braid word w contains a handle if some subword of w is a s- or a S-handle. A handle can be recognized on the diagram representation: the first and the last crossing are in the same horizontal position and have different orientations, and all the intermediate crossings, if any, lie on the left of the two crossings.
For instance, the word BcbACb contains the c-handle cbAC. The figure shows the corresponding diagram, where the piece of the strand defining the handle is drawn in black. The name “handle” comes from the form of this piece of strand, resembling a handle: imagine to rotate the braid clockcounterwise by 90° and to grasp it like a suitcase. It is possible that a word contains more than one handle: as an example consider the word ABcbACbAab, which contains the c-handle cbAC and the A-handle Aa.
If a braid word w contains at least one handle, the leftmost subword of w that is a handle is called the first handle in w: we read w starting from the left, and the first handle is the one we first encounter.

What does reducing a handle mean?

The principle of Handle Reduction is to transform the braid word and try to get rid of handles. The basic step is an operation that transforms a handle into an equivalent word, called its reduction.
Assume that h is a s-handle and denote by r the letter that lies immediately before s in alphabetical order and by R the corresponding upper case letter. We define the reduction of h to be the braid word obtained from h in the following way:
• delete the initial letter s and the final letter S
• replace every r in h (if any) with Rsr and every R in h (if any) with RSr.
Symmetrically, if h is a S-handle, the reduction of h is the word obtained from h in the following way:
• delete the initial letter S and the final letter s
• replace every r in h (if any) with rsR and every R in h (if any) with rSR.
For instance, the reduction of the c-handle cbAC is BcbA, while the reduction of the A-handle Aa is the empty word.

Geometrically, the diagram encoded by the reduction of h is obtained from the diagram encoded by h by pushing to the left the strand that makes the handle, so that it passes to the left of all neighbouring crossings.
The following figures show a diagram with a handle and the diagram obtained by reducing the handle.  One can show that handle reduction is an equivalence, i.e., the braids associated with the diagrams (or the words) before and after the reduction are isotopic. We also see that, by reducing a handle, we get rid of it, but at the expense of possibly creating new handles on the left or on the right of the handle that has been deleted.

How does the Handle Reduction algorithm work?

We start with an arbitrary braid word w and look for the first handle in w. We reduce it, i.e., we replace the handle by its reduction, and we repeat the process with the new word obtained in the last step until no more handle exists. It can be shown that this process terminates, that means we obtain a word with no handles, and that at this point
• if we are left with the empty word, then the initial word w is equivalent to the empty word;
• if we are left with a nonempty word, then the initial word w is not equivalent to the empty word.
Thus we have got a solution to the Braid Triviality Problem. As explained above, this is equivalent to solve the Braid Isotopy Problem. However, note that the algorithm does not directly solve the latter problem: it is possible that, applying the algorithm to two equivalent words, it stops giving two different reductions.