Handle Reduction
This project was partially supported by ANR TheoGar. 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 nstrand 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:
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 nstrand 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. 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:
One says that two braid words are equivalent if one can be obtained from the other by a finite sequence of the following moves:
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: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: 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: 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: 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 nstrand 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 shandle 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 Shandle 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 chandles. We say that a braid word w contains a handle if some subword of w is a s or a Shandle. 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 chandle 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 chandle cbAC and the Ahandle 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 shandle 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:
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
The applet in this page can help you to visualise the algorithm. Why does Handle Reduction work?This is the hard point. A priori, it might very well happen that we continue reducing handles and creating new ones for ever, or that a word containing no handle be equivalent to the empty word.Actually, this can not happen, so the Handle Reduction algorithm always converges and solves the Braid Triviality Problem. But this is a rather difficult result whose only proof known so far requires sophisticated mathematical methods. The main reason behind the correctness of the Handle Reduction algorithm is the existence of a certain braid ordering. For more details and explanations, see
