Chapitre 2 -- Le problème du mot
Dans le premier chapitre, nous avons vu que toute tresse peut être codée par un mot composé de tresses élémentaires, les générateurs.
Puis nous avons décrit toutes les relations, c'est-à-dire les transformations de mots qui ne changent pas la tresse correspondante.
Mais... cette description ne nous dit pas tout.
Par exemple, les relations ne nous disent pas comment vérifier si deux mots sont équivalents ou non.
Prenons deux mots. Ici, on peut trouver une suite de relations qui les relient entre eux.
A chaque étape, on remplace la partie du mot dans la boite jaune par une partie équivalente...
...obtenue en utilisant les relations du groupe de tresses, ou en insérant ou simplifiant un générateur et son inverse.
A chaque étape on change le mot, mais la tresse qu'il représente reste la même.
Il n'est pas si facile de voir immédiatement que les deux mots sont équivalents!
Cela ne devient évident qu'une fois qu'on a construit la suite de mots intermédiaires.
Et que dire de ces deux mots? Comme avant, on essaie de les relier par une suite.
Mais cette tentative est hasardeuse:
on pourrait passer toute notre vie à la chercher, sans jamais la trouver.
Même après nos innombrables essais, on ne saurait toujours pas si une telle suite existe ou non.
Peut être que nous n'avons simplement pas été assez chanceux pour la trouver?
C'est pourquoi on a besoin d'un autre moyen pour résoudre le problème de l'équivalence des mots.
Plus précisément, on aimerait construire une procédure qui, étant donnés deux mots quelconques...
...fait des calculs...
...et renvoie la réponse "oui" si les deux mots sont équivalents...
...ou la réponse "non" si les deux mots représentent deux tresses différentes.
Une telle procédure s'appelle un algorithme.
Nous avons de la chance: pour les tresses, il existe un tel algorithme. Regardons à l'intérieur...
Mais avant tout, simplifions un peu le problème:
Dire que deux mots représentent la même tresse revient à dire que si l'on compose le premier avec l'inverse du deuxième, on obtient la tresse triviale.
On peut donc reformuler notre problème: déterminer si un mot donné représente oui ou non la tresse triviale.
Autrement dit, si l'on peut, grâce aux relations, transformer notre mot en "1".
Regardons cette tresse. La disposition des couleurs aux extrêmités nous indique de quelle façon les points sont reliés entre eux.
Si cette disposition est exactement la même à gauche qu'à droite, on dit que la tresse est "pure".
Bien sûr, l'équivalence des tresses préserve l'ordre des couleurs aux extrêmités.
Donc une tresse équivalente à la tresse triviale est nécéssairement pure.
Toute tresse pure peut être décomposée en blocs de la façon suivante.
Dans le premier bloc, tous les brins sont droits sauf le dernier, le brin vert, qui peut s'emmêler avec les autres.
Dans le deuxième bloc, tous les brins sont droits sauf l'avant-dernier, le brin jaune, qui peut seulement s'emmêler avec les brins du dessous.
Et ainsi de suite... jusqu'au dernier bloc, dans lequel le deuxième brin peut seulement s'emmêler avec le premier.
On sait que chaque tresse peut être représentée par de nombreux mots différents.
Pour chaque tresse, on aimerait en choisir un en particulier, qu'on appellera sa forme normale.
Nous allons décrire un algorithme qui met chaque tresse sous sa forme normale.
Cette procédure, dûe à Artin, s'appelle le peignage des tresses.
Commençons par recopier la tresse...
...et supprimer le dernier brin, que l'on remplace par un brin horizontal.
En composant cette tresse avec son inverse, on obtient la tresse triviale.
Donc, en composant le tout avec la tresse originale, nous ne changeons pas celle-ci.
Du côté gauche, on peut dégager un premier bloc qui a bien la forme voulue:
tous les brins sont droits sauf le dernier.
On peut encore déformer les brins de telle façon que...
...le brin vert entoure successivement un seul brin à la fois, en remontant à sa position initiale entre chaque tour.
On dit alors que cette partie a été "peignée".
On répète la même procédure avec la partie restante à droite: on copie la tresse...
...remplace le brin jaune par un brin horizontal...
...compose la tresse avec son inverse...
...puis on compose la tresse triviale ainsi obtenue avec la tresse originale...
...ce qui nous permet d'arranger le deuxième bloc.
On peut en effet déformer cette partie pour la peigner comme précédemment, de façon à ce que le brin jaune s'emmêle seulement avec le bleu et le rouge.
Il ne reste plus qu'un dernier bloc, qui est facile à peigner.
Nous avons mis la tresse sous sa forme normale.
Artin a démontré qu'une tresse est triviale si et seulement si, une fois peignée, chacun de ses blocs est trivial...
...c'est-à-dire, tous les brins sont droits.
Ici, notre tresse n'est donc pas triviale.
Ainsi, l'algorithme d'Artin permet de décider si une tresse donnée est triviale ou non.
Bien sûr cette tresse doit être pure. On la peigne en suivant la méthode d'Artin.
Si on tombe sur un bloc non trivial, l'algorithme répond "non".
Sinon, on continue avec le bloc suivant.
Si tous les blocs sont triviaux, alors la tresse est triviale et l'algorithme répond "oui".
Mais bien que cet algorithme fonctionne, Artin lui-même n'en était pas très satisfait!
Dans son article "théorie des tresses", il écrit:
"L'auteur est convaincu que toute tentative de mise en pratique sur une personne vivante ne conduirait qu'à de violentes protestations et discriminations envers les mathématiques."
"Il dissuade donc de conduire une telle expérience."
En effet, le peignage des tresses peut être un travail extrêmement long!
La complexité de l'algorithme est très élvée:
si l'on trace un graphique représentant le temps moyen nécessaire pour peigner une tresse en fonction du nombre de croisements, la courbe croît très vite.
Augmenter un peu la taille de la tresse peut donc faire exploser le temps de calcul, qui peut devenir très long, même pour un ordinateur.
C'est porquoi les mathématiciens cherchent d'autres algorithmes plus rapides.
Le plus rapide que l'on connaisse actuellement est probablement celui qui a été introduit en 1995 par Dehornoy, un mathématicien Français.
Il s'agit de l'algorithme de "la réduction des poignées".
Voici une poignée: le brin rouge passe devant le brin qui est juste au-dessus, puis devant le brin juste en-dessous.
Une poignée peut aussi passer deux fois derrière les autres brins: voici une autre poignée.
Une poignée est toujours tournée vers le haut; ceci n'est donc pas une poignée.
Ceci non plus, car le brin bleu passe une fois par devant et une fois par derrière.
L'algorithme de réduction des poignées consiste à retourner les poignées pour les faire disparaître.
Ces transformations changent le mot, mais pas la tresse qu'il représente.
Un théorème de Dehornoy affirme qu'un mot sans poignée différent de "1" représente forcément une tresse non triviale.
Regardons comment fonctionne l'algorithme. Prenons une tresse pure.
Si elle n'a pas de poignées et au moins un croisement, alors la tresse n'est pas triviale et l'algorithme répond "non".
S'il y a des poignées, on trouve celle qui se termine en premier et on la réduit.
On continue ainsi jusqu'à avoir éliminé toutes les poignées:
si la tresse possède de croisement, l'algorithme répond "non".
Sinon, l'algorithme répond "oui".
Mais il y a un problème: comment savoir si l'algorithme se termine toujours?
En effet, si en réduisant une poignée on revient à un mot que l'on avait déjà obtenu auparavant...
...alors l'algorithme se mettra à tourner en boucle et ne donnera jamais de réponse.
Heureusement, ce ne sera jamais le cas: on peut démontrer que l'algorithme termine toujours.
On ne connait pas encore la complexité de cet algorithme...
...mais certaines estimations expérimentales semblent indiquer qu'il est plus rapide que les autres algorithmes connus.
Peignage, poignées... La formalisation des tresses en termes de manipulations de mots est vraiment fructueuse!