Associaèdre

Hors piste Le 4 mars 2010  - Ecrit par  Jean-Louis Loday Voir les commentaires

Les associaèdres sont des objets géométriques qui codent les diverses façons de placer les parenthèses et généralisent, en dimension quelconque, le pentagone.

Il y a cinq ans le Centre International de Rencontres Mathématiques de Luminy a envoyé ses vœux avec la carte ci-dessous.

JPEG

L’illustration choisie par Robert Coquereaux, directeur du CIRM à cette époque là, était tout à fait adaptée pour l’an 5 du nouveau millénaire puisque ce polyèdre comporte plusieurs pentagones parmi ses faces.

Mais intéressons-nous d’abord à des polygones et des polyèdres plus simples comme le triangle et le tétraèdre :

JPEG

Ils font partie d’une famille infinie de « polytopes » (les analogues des polygones et polyèdres en dimensions supérieures) appelés les simplexes standards. Le $n$-simplexe standard ${\mathcal{T}}^{n}$ peut être décrit de la manière suivante. Considérons les $n+1$ points de l’espace de dimension
$n+1$ dont les coordonnées sont de la forme $(0, \ldots , 0,1,0, \ldots , 0)$ ; plus précisément, on demande que chaque coordonnée soit nulle, sauf exactement une qui est égale à $1.$ Ces points appartiennent à un même hyperplan, dont l’équation est $x_1+x_2+...+x_{n+1}=1.$ Par exemple, lorsque $n=2,$ les
trois points sont $(1,0,0),$ $(0,1,0)$ et $(0,0,1),$ et ils sont tous situés sur le
plan formé des points $(x_1,x_2,x_3)$ satisfaisant $x_1+x_2+x_3=1.$
Ces points sont les sommets du simplexe standard ${\mathcal{T}}^{n}$,
et celui-ci est l’enveloppe convexe de ses $n+1$ sommets. Pour obtenir
une description agréable des coordonnées des
sommets de ${\mathcal{T}}^{n},$ il nous a donc fallu représenter ce
polytope en dimension $n+1$ au lieu de $n.$

De même le carré et le cube

JPEG

sont le polygone et le polyèdre d’une famille infinie de polytopes : les hypercubes. Les $2^{n}$ sommets de l’hypercube de dimension $n$ sont les points $(x_{1}, \ldots , x_{n})$ de ${\mathbf{R}}^{n}$ où chaque coordonnée $x_{i}$ vaut soit $0$ soit $1$.

Si l’on part d’un hexagone, la famille infinie est moins connue, mais tout aussi facile à construire :

JPEG

Ce sont les permutoèdres. Il y a un sommet pour chaque permutation de l’ensemble $\{1,2, \ldots , n\}$. En fait les coordonnées du point de ${\mathbf{R}}^{n}$ associé à une permutation sont justement données par la permutation de $(1,2, \ldots , n)$. Le nombre de permutations, et donc de sommets, est égal à
\[ n!=1 . 2 . 3 . ... . n, \]
le produit des $n$ premiers entiers. Par exemple, lorsque $n=4,$ la permutation
qui réarrange $(1,2,3,4)$ en $(2,3,1,4)$ correspond au sommet de coordonnées
$(2,3,1,4)$ ; il y a $24$ sommets en tout. Ces points sont évidemment dans l’hyperplan d’équation
\[ x_{1}+ \cdots + x_{n}= \frac{n(n+1)}{2} \]
et leur enveloppe convexe est le permutoèdre ${\mathcal{P}}^{n-1}$ de dimension $n-1$. Là encore, les
coordonnées des sommets sont plus faciles à décrire en ajoutant une dimension.
Ainsi, le polytope de dimension $2$ est l’hexagone régulier, mais vu dans
l’espace, avec ses six sommets $(1,2,3),$ $(2,3,1),$ $(3,2,1),$ $(2,1,3),$ $(3,2,1)$ et $(1,3,2),$ qui sont tous situés dans le plan $x_1+x_2+x_3=6.$
Le permutoèdre tri-dimensionnel ci-dessus était déjà connu d’Albrecht Dürer (1471—1528) [1]. Il est aussi connu sous le nom de polytope de Birkhoff.

Mais quid du pentagone ? A-t-il un analogue en dimension 3 ? Appartient-il à une famille infinie ? Le polyèdre de la carte de vœux est précisément le polytope de dimension 3 qui permet de débuter une famille infinie :

JPEG

C’est la famille des associaèdres. Leur histoire commence en 1962 lorsque Jim Stasheff, un mathématicien américain, construit, à partir des parenthésages d’un mot à $n+1$ lettres, un certain espace topologique de dimension $n-1$, qui lui permet de résoudre des problèmes importants en topologie algébrique. En 1979 on s’aperçoit que l’on peut construire ces espaces comme des enveloppes convexes de points (polytopes), mais ce n’est qu’en 2002 qu’une construction explicite et simple apparaît.

Les sommets de l’associaèdre sont en bijection avec les parenthésages d’un mot à $n+1$ lettres. Par exemple pour $n=2$ il y a deux parenthésages possibles :
\[(({\color{blue}x}{\color{red}x}){\color{green}x})\quad \textrm{et}\quad ({\color{blue}x}({\color{red}x}{\color{green}x})).\]
Pour $n=3$ il y en a cinq :
\[((({\color{blue}x}{\color{red}x}){\color{green}x}){x}),\quad ((({\color{blue}x}({\color{red}x}{\color{green}x})){x}), \quad(({\color{blue}x}{\color{red}x})({\color{green}x}{x})), \quad({\color{blue}x}(({\color{red}x}{\color{green}x}){x})), \quad ({\color{blue}x}({\color{red}x}({\color{green}x}{ x}))).\]
Il est, dans notre cas, plus visuel de remplacer les parenthésages par des arbres binaires planaires enracinés (on dira simplement « arbre ») :

Ici nous avons représenté deux arbres à $3$ feuilles, et cinq arbres à
$4$ feuilles, qui codent les parenthésages listés précédemment.
Pour construire l’associaèdre, on va associer à tout arbre $t$ à $n$ sommets internes (donc à $n+1$ feuilles), un point $M(t)$ de ${\mathbf{R}}^{n}$. Ses coordonnées explicites sont les suivantes :
\[ M(t) := (a_{1}b_{1}, \ldots , a_{n}b_{n})\]
où les entiers $a_{i}$ et $b_{i}$ sont déterminés comme suit. Tout d’abord on numérote les sommets internes de $1$ à $n$. On numérote les feuilles de 1 à n+1 de gauche à droite et le sommet interne numéro $i$ est celui correspondant au creux où atterrit une bille qu’on lâcherait au-dessus de l’arbre entre les feuilles numéro $i$ et $i+1$. Le sommet numéro $i$ possède une branche de gauche et une branche de droite. Sur sa branche de gauche il y a $a_{i}$ feuilles et sur sa branche de droite il y a $b_{i}$ feuilles. Cette recette (on dit plutot algorithme) définit les entiers $a_{i}$ et $b_{i}$. Le produit $a_{i}b_{i}$ est la $i$-ème coordonnée du point $M(t)$. Lorsque $t$ parcourt les arbres à $n+1$ feuilles on obtient alors
\[ c(n)=\frac{(2n)!}{n!(n+1)!} \]
points de ${\mathbf{R}}^{n},$ où l’on a utilisé la notation $n!$ définie plus haut ; ces nombres sont bien connus des mathématiciens professionnels : ce sont les fameux nombres de Catalan [2]. On a donc $c(1)= 1, c(2)=2, c(3)= 5, c(4)= 14$. Bien que ce ne soit pas immédiatement perceptible, ces points appartiennent à un même hyperplan car la somme de leurs coordonnées est constante (démonstration facile par récurrence) :
\[a_{1}b_{1}+ \cdots + a_{n}b_{n}= \frac{n(n+1)}{2}.\]
On démontre [3] que l’enveloppe convexe des points $M(t)$ est le polytope de Stasheff ${\mathcal{K}}^{n-1}$ de dimension $n-1$, appelé aussi associaèdre.

Voici ${\mathcal{K}}^{2}$ et ses coordonnées dans ${\mathbf{R}}^{3}$ :

JPEG

On remarquera que ce n’est pas le pentagone régulier, mais que, par contre, il contient l’hexagone régulier.

Voici ${\mathcal{K}}^{3}$ et ses coordonnées dans ${\mathbf{R}}^{4}$ :

JPEG

On remarque que certaines des coordonnées de ${\mathcal{K}}^{3}$ sont des permutations de $1234$. Cette remarque est la trace du fait suivant, déjà mentionné pour la dimension $2$ : le permutoèdre est contenu dans l’associaèdre, comme on le voit sur cette photo :

JPEG

En fait c’est un résultat général valable pour tout entier $n$.

Regardé comme un ovni dans le monde mathématique lors de son apparition dans les années soixante, l’associaèdre est devenu un objet incontournable dans de nombreux problèmes : en topologie algébrique (espaces de lacets, algèbres à homotopie près), en algèbre ($A_{\infty}$-algèbres, algèbres amassées, groupes de Thompson, compactification d’espaces de modules), en physique théorique (algèbres dendriformes, renormalisation), en informatique théorique (fonctions parking). Mais en fait ce n’est pas si surprenant car il touche à une notion fondamentale en mathématiques : l’associativité. Plus précisément il mesure le défaut d’associativité de certaines structures. Vous trouverez à cette adresse la petite histoire de la découverte évoquée ci-dessus, ainsi que le lien avec l’artiste-mathématicien Albrecht Dürer.

JPEG

Notes

[1voir l’article « Comment j’ai trouvé l’associaèdre » sur la page web de l’auteur, ou directement
la gravure melancholia

[2voir la page de wikipedia

[3voir l’article suivant : J.-L. Loday, Realization of the Stasheff polytope. Arch. Math. (Basel) 83 (2004), no. 3, 267—278.

Partager cet article

Pour citer cet article :

Jean-Louis Loday — «Associaèdre» — Images des Mathématiques, CNRS, 2010

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM