Figure 1 - Les neuf arbres enracinés à cinq sommets, en rouge les racines, en vert les feuilles.
Chargé de recherches
Laboratoire de Mathématiques, UMR 6620, CNRS-Université Blaise Pascal
Les mathématiciens s'intéressent à des collections d'objets qu'ils appellent 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 possède pas ces caractéristiques. Un arbre enraciné est donné par ses sommets et ses arêtes, avec les règles du jeu suivantes1 (voir la figure 1) :
Chaque arête part d'un sommet pour arriver sur un autre sommet.
Il arrive une seule arête sur chaque sommet, sauf sur un sommet particulier appelé la racine.
Il sort un nombre quelconque d'arêtes à partir de n'importe quel sommet. Un sommet d'où ne part aucune arête est appelé une feuille.
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).
|
|
|
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).
Figure 4 - La greffe est NAP : on peut remplacer mentalement la
racine par un arbre c quelconque.
Muni de la loi de greffe, l'ensemble des arbres enracinés
occupe une place particulière, « en amont » de tous les autres
ensembles munis d'une loi NAP. Les arbres sont particulièrement bien
adaptés à toutes les situations où l'on doit considérer plusieurs
échelles de temps ou d'espace simultanément, par exemple en
physique des particules élémentaires ou dans l'étude des équations
différentielles2.
On utilise le plus souvent 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.
J.C. Butcher, Coefficients for the study of Runge-Kutta integration processes, J. Austral. Math. Soc. 3, 185-201 (1963).
A. Cayley, On the theory of the analytical forms called trees, Phil. Mag. 13, 172--176 (1857).
M. Livernet, A rigidity theorem for pre-Lie algebras, J. Pure Appl. Alg. 207 (1), 1--18 (2006).
D. Manchon et A. Saidi, Lois pré-Lie en interaction, Comm. Alg. volume 39 No 10, 3662-3680 (2011).
1 Formellement, un arbre enraciné est une classe d'équivalence par isomorphismes de graphes finis sans boucles, orientés, possédant un unique sommet minimal.
2 Plus particulièrement les équations différentielles non-linéaires. Les équations différentielles linéaires, de structure plus simple, ne font intervenir que les arbres à une seule feuille, comme l'arbre le plus à gauche dans la figure 1.
