Un peu d'algèbre sur les arbres

Par Dominique Manchon, chargé de recherche au CNRS

Les mathématiciens s'intéressent à des collections d'objets qu'ils appelent ensembles et aux opérations entre les objets de ces ensembles. Une loi interne est un procédé qui assemble deux éléments d'un ensemble pour en fabriquer un troisième. Par exemple, l'addition assemble 3 et 5 pour donner 8 et la multiplication assemble 4 et 7 pour donner 28. On dit que la loi interne est commutative si assembler un objet a avec un objet b équivaut à assembler l'objet b avec l'objet a. Par exemple 3+5 et 5+3 donnent le même objet 8. Pour assembler trois objets a, b et c dans cet ordre on peut procéder de deux façons : soit assembler a et b d'abord puis assembler le résultat avec c, ou bien assembler a avec le résultat de l'assemblage de b et c. Si ces deux façons conduisent au même objet, on dit que la loi est associative. Par exemple, 3+(5+6) et (3+5)+6 donnent le même objet 14. Ces propriétés peuvent sembler naturelles, pourtant, nous allons examiner une loi qui ne les a pas.

Un arbre enraciné est donné par ses sommets et ses arêtes, avec les règles du jeu suivantes (voir la figure 1) :

Les neuf arbres à 5 sommets
Figure 1 - Les neuf arbres enracinés à cinq sommets, en rouge les racines, en vert les feuilles.

Le mathématicien néo-zélandais John Butcher a défini en 1963 une loi interne (la greffe) sur les arbres : en greffant un premier arbre sur la racine d'un deuxième, on en obtient un troisième. La greffe n'est ni commutative ni associative (voir figures 2 et 3).
La greffe n'est pas commutative
Figure 2 - La greffe n'est pas commutative.
La greffe n'est pas associative
Figure 3 - La greffe n'est pas associative.



Cependant, greffer un arbre a à la greffe de l'arbre b sur c conduit au même résultat que greffer l'arbre b à la greffe de l'arbre a sur c. Autrement dit on peut greffer a et b sur la racine de c dans n'importe quel ordre. On dit que la greffe est « NAP », pour « Non-Associative Permutative » (voir la figure 4).
La greffe est NAP : on peut remplacer mentalement la racine par un arbre c quelconque
Figure 4 - La greffe est NAP : on peut remplacer mentalement la racine par un arbre c quelconque.

L'ensemble des arbres enracinés muni de la greffe occupe une place particulière, « en amont » de tous les autres ensembles munis d'une loi NAP. Dans la plupart des applications, parmi lesquelles on peut citer la physique des particules élémentaires ou l'étude des équations différentielles, on utilise les notions d'algèbre pré-Lie et d'opérade, qui sortent du cadre de cet article, mais dont la notion d'ensemble NAP nous a donné un premier aperçu.

Pour en savoir plus

Bibliographie