1
00:00:19,500 --> 00:00:23,500
We saw in the first chapter a way to describe the braid group: 

2
00:00:24,000 --> 00:00:28,000
we specified some elementary braids, the generators

3
00:00:28,200 --> 00:00:34,800
and then we found the relations,
moves that can transform a word without changing the braid it describes

4
00:00:35,000 --> 00:00:38,000
But we still don't know all about this group!

5
00:00:38,500 --> 00:00:44,500
For example, the relations don't say how
to check if two words are equivalent

6
00:00:45,000 --> 00:00:50,500
Here we have two words and we construct
a sequence of relations that connect them

7
00:00:51,000 --> 00:00:59,000
At each stage we just replace
the part of the word inside the yellow box with an equivalent one

8
00:00:59,500 --> 00:01:08,000
We use the two kinds of relations
and the insertion or deletion of a generator and its inverse

9
00:01:12,000 --> 00:01:18,000
In each level we change the word,
but the braid it represents remains the same

10
00:01:26,000 --> 00:01:32,000
It is not so easy to note immediately, just looking at the two words,
that they are equivalent

11
00:01:32,200 --> 00:01:36,200
This becomes evident when we construct the sequence

12
00:01:47,000 --> 00:01:53,000
What about these two words?
We try to construct a sequence as before to connect them

13
00:01:57,000 --> 00:02:04,000
It can be a hard job to construct such a sequence of words using the relations

14
00:02:05,000 --> 00:02:10,000
We could spend our whole life looking for one, without ever finding it

15
00:02:10,200 --> 00:02:18,200
we will never know whether no sequence exists 
or we haven't been lucky enough to find it

16
00:02:22,000 --> 00:02:28,000
That's why we need another way to handle the question

17
00:02:42,000 --> 00:02:51,000
More precisely, we wish to construct a machinery
that takes two arbitrary words as input,

18
00:02:51,200 --> 00:02:54,800
makes some operations and computations

19
00:02:55,000 --> 00:03:02,000
and gives as output the answer "yes"
if the two words are equivalent

20
00:03:04,000 --> 00:03:15,000
Following the same procedure, the answer will be "no"
if the two words represent different braids

21
00:03:16,000 --> 00:03:20,000
Such a procedure is called an algorithm

22
00:03:24,000 --> 00:03:30,000
We are lucky: for braids we have such an algorithm
Let's look inside it

23
00:03:37,000 --> 00:03:40,000
First of all we simplify the problem:

24
00:03:40,200 --> 00:03:54,000
two words represent the same braid if and only if one,
composed with the inverse of the other, is equivalent to the trivial braid

25
00:03:55,500 --> 00:04:03,000
Therefore, we can reformulate our problem:
given an arbitrary word, decide if it is equivalent to the identity

26
00:04:03,500 --> 00:04:08,500
Or in other words: is there a way to transform the given word into "1"?

27
00:04:11,000 --> 00:04:17,000
Look at this braid: the color of the bubbles is enough to know where each strand ends

28
00:04:18,000 --> 00:04:24,000
If the bubbles at the same level, on the left and on the right,
have the same colors, then the braid is called pure

29
00:04:27,000 --> 00:04:32,000
Of course two equivalent braids will have
the bubbles with the same color arrangement

30
00:04:32,500 --> 00:04:40,000
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

31
00:04:43,000 --> 00:04:47,000
Each pure braid can be decomposed into blocks in this way:

32
00:04:47,200 --> 00:04:56,500
in the first block, all the strands but the last are straight.
The green strand can link to the others

33
00:04:56,700 --> 00:05:05,000
In the second block, all the strands but the second-to-last are straight.
The yellow strand can link only to the strands below

34
00:05:05,200 --> 00:05:12,000
And so on
until the last block, in which the second strand can link to the first one

35
00:05:13,000 --> 00:05:17,000
We know that for each braid there are lots of representatives

36
00:05:17,200 --> 00:05:28,200
We would like to choose a specific one of them to describe the braid
It will be called the normal form

37
00:05:30,000 --> 00:05:40,600
Now, we need an algorithm that puts any arbitrary word in its normal form
Artin's braid combing is such an algorithm

38
00:05:40,800 --> 00:05:43,000
Here we show it on a non trivial braid:

39
00:05:43,200 --> 00:05:45,000
first copy the braid

40
00:05:45,200 --> 00:05:52,000
and delete the last strand, replacing it with a trivial one

41
00:05:53,000 --> 00:05:57,500
Compose this braid with its inverse, getting the identity braid

42
00:05:57,700 --> 00:06:02,000
So, composing the original braid with it, we don't change the braid

43
00:06:03,000 --> 00:06:13,000
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

44
00:06:13,200 --> 00:06:15,200
This is the first block

45
00:06:17,000 --> 00:06:23,000
We deform the strands so that the green one encircles a strand
passing behind the others,

46
00:06:23,200 --> 00:06:28,000
goes back to the initial position, encircles another strand, and so on

47
00:06:32,000 --> 00:06:35,000
This piece is combed

48
00:06:38,000 --> 00:06:42,000
Do the same procedure on the right side:
copy the braid,

49
00:06:43,000 --> 00:06:47,000
replace the yellow strand with a trivial one,

50
00:06:51,000 --> 00:06:56,000
compose this braid with its inverse
getting a trivial braid

51
00:06:57,000 --> 00:07:01,000
compose this trivial braid with the original one

52
00:07:03,000 --> 00:07:07,000
and tidy up the second block

53
00:07:13,000 --> 00:07:20,000
We put it in a form such that
the yellow strand links only with the blue one and the red one

54
00:07:41,000 --> 00:07:45,000
We have combed the second block

55
00:07:47,000 --> 00:07:52,000
Now the last block is easy to rearrange

56
00:07:53,000 --> 00:07:57,000
We have put the braid in its normal form

57
00:07:58,000 --> 00:08:05,000
Artin proved that a braid is trivial if and only if,
once it is combed, every block is trivial,

58
00:08:05,200 --> 00:08:09,000
meaning that it can be represented with no crossings at all

59
00:08:09,200 --> 00:08:13,000
So our braid is not trivial

60
00:08:14,500 --> 00:08:17,500
And we have an algorithm to check it:

61
00:08:18,500 --> 00:08:25,500
We start with a pure braid
Comb it into blocks

62
00:08:25,700 --> 00:08:31,000
If one of the blocks is not trivial, terminate, answering "no"

63
00:08:31,200 --> 00:08:34,000
Otherwise continue with the next block

64
00:08:34,200 --> 00:08:44,000
If all the blocks are trivial, we get the trivial braid and the answer is
"yes, the input word is equivalent to the identity"

65
00:08:55,000 --> 00:09:01,000
This algorithm works but Artin himself was not satisfied with it

66
00:09:05,000 --> 00:09:08,000
In his paper "Theory of braids" he writes:

67
00:09:19,000 --> 00:09:24,000
Why did he write so?
Combing is an extremely slow method

68
00:09:24,200 --> 00:09:27,000
The complexity of the algorithm is very high:

69
00:09:34,000 --> 00:09:44,000
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

70
00:09:46,000 --> 00:09:55,000
Increasing the input size by a small amount
the time grows very fast and may be too long even for a computer

71
00:09:55,200 --> 00:10:01,000
This is why mathematicians look for other, quick, algorithms

72
00:10:04,000 --> 00:10:14,000
The fastest found so far is probably the one proposed
about 15 years ago by Dehornoy, a French mathematician

73
00:10:16,000 --> 00:10:21,000
It is based on manipulating braids and is called handle reduction

74
00:10:25,000 --> 00:10:32,000
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

75
00:10:32,700 --> 00:10:39,000
A handle can also pass twice behind the other strands:
this is another handle

76
00:10:44,000 --> 00:10:48,000
This is not a handle because it faces downwards

77
00:10:52,000 --> 00:10:57,000
Neither this is a handle:
the blue strand passes once in front of the strand below and once behind

78
00:10:59,000 --> 00:11:06,000
Reducing handles means to move these pieces of string

79
00:11:07,000 --> 00:11:15,000
In this way we change the word
but the braid it represents remains the same

80
00:11:34,000 --> 00:11:44,000
A theorem of Dehornoy ensures that a word with no handles is
either empty or it represents a nontrivial braid

81
00:11:51,000 --> 00:12:00,000
Let's sketch the handle reduction algorithm:
take a pure braid

82
00:12:01,000 --> 00:12:09,000
If there are no handles and the braid has at least one crossing,
terminate, answering "no"

83
00:12:10,000 --> 00:12:16,000
Otherwise, if there are handles,
find the one that ends first and reduce it

84
00:12:20,000 --> 00:12:24,000
Continue like this until there are no more handles:

85
00:12:24,200 --> 00:12:28,000
if the braid is not trivial, the answer is "no"

86
00:12:28,200 --> 00:12:35,000
If after reducing all the handles, the braid is trivial, 
then the answer will be "yes"

87
00:12:40,000 --> 00:12:45,800
But there is a problem: what if the algorithm does not end?

88
00:12:46,000 --> 00:12:52,000
It could maybe go into a loop:
if it comes back to a word that it has already met,

89
00:12:52,000 --> 00:12:59,500
the steps after that one will always be the same
and the algorithm will never stop

90
00:13:01,000 --> 00:13:09,000
In fact this is never the case:
it has been shown that the algorithm always terminates

91
00:13:21,000 --> 00:13:28,000
We don't yet know the complexity of this algorithm
but we have some experimental estimates

92
00:13:28,200 --> 00:13:33,000
and it seems much faster than the other known algorithms

93
00:13:50,000 --> 00:13:58,000
Combing, handles:
the formalization of braids in terms of words is really powerful!