Métrique des mots

Cet article ne cite pas suffisamment ses sources (juin 2017).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Dans la théorie des groupes, une branche des mathématiques, une métrique des mots sur un groupe G est une distance sur G, liée au choix préalable d'une partie génératrice S de G : la distance entre deux éléments g, h de G mesure l'efficacité avec laquelle leur « différence » g⁻¹h peut être exprimée comme un mot sur S. La métrique des mots sur G est très étroitement liée au graphe de Cayley de (G, S) : la distance d(g, h) est la longueur du plus court chemin dans le graphe de Cayley entre g et h.

Différents choix de parties génératrices donneront en général des métriques différentes. Bien que cela semble à première vue être une faiblesse dans le concept de la métrique des mots, cela peut être exploité afin de prouver des théorèmes sur les propriétés géométriques des groupes, comme cela se fait dans la théorie géométrique des groupes.

Le groupe ${\displaystyle \mathbb {Z} }$ des entiers est engendré par l'ensemble ${\displaystyle \{-1,1\}}$. L'entier ${\displaystyle -3}$ peut être exprimé comme ${\displaystyle -1-1-1+1-1}$ un mot de longueur 5 sur ces générateurs. Mais le mot qui exprime ${\displaystyle -3}$ plus efficacement est ${\displaystyle -1-1-1}$ un mot de longueur 3. La distance entre 0 et -3 dans la métrique des mots associée à cette partie génératrice est donc égale à 3. Plus généralement, la distance entre deux nombres entiers ${\displaystyle m}$ et ${\displaystyle n}$ dans cette métrique des mots est égale à ${\displaystyle |m-n|}$, parce que le plus court mot représentant la différence ${\displaystyle m-n}$ est de longueur égale à ${\displaystyle |m-n|}$.

Pour un exemple plus visuel, les éléments du groupe ${\displaystyle \mathbb {Z} \oplus \mathbb {Z} }$ peuvent être vus comme des vecteurs dans le plan cartésien avec des coordonnées entières. Le groupe ${\displaystyle \mathbb {Z} \oplus \mathbb {Z} }$ est engendré par les vecteurs unité usuels ${\displaystyle e_{1}=\langle 1,0\rangle }$, ${\displaystyle e_{2}=\langle 0,1\rangle }$ et leurs opposés respectifs ${\displaystyle -e_{1}=\langle -1,0\rangle }$, ${\displaystyle -e_{2}=\langle 0,-1\rangle }$. Le graphe de Cayley de ${\displaystyle \mathbb {Z} \oplus \mathbb {Z} }$ peut être vu dans le plan comme une grille infinie de rues d'une ville, où chaque ligne verticale ou horizontale avec des coordonnées entières est une rue, et chaque point de <${\displaystyle \mathbb {Z} \oplus \mathbb {Z} }$. Chaque segment horizontal entre deux sommets représente le vecteur ${\displaystyle e_{1}}$ ou ${\displaystyle -e_{1}}$, selon que le segment est traversé dans un sens ou dans l'autre, et chaque segment vertical représente ${\displaystyle e_{2}}$ ou ${\displaystyle -e_{2}}$. Une voiture démarrant en  ${\displaystyle \langle 1,2\rangle }$ et voyageant dans les rues jusqu'à  ${\displaystyle \langle -2,4\rangle }$ peut faire le trajet de différentes manières. Mais peu importe le trajet suivi, la voiture doit traverser au moins ${\displaystyle |1-(-2)|=3}$ blocs horizontaux et au moins ${\displaystyle |2-4|=2}$ blocs verticaux, pour une distance totale d'au moins 3 + 2 = 5. Si la voiture change de chemin, le trajet peut être plus long, mais la distance minimale parcourue par la voiture, égale à la distance pour la métrique des mots entre ${\displaystyle \langle 1,2\rangle }$ et ${\displaystyle \langle -2,4\rangle }$ est donc égale à 5.

Plus généralement, étant donnés deux éléments ${\displaystyle \langle i,j\rangle }$ et ${\displaystyle \langle k,l\rangle }$ de ${\displaystyle \mathbb {Z} \oplus \mathbb {Z} }$, la distance entre ${\displaystyle \langle i,j\rangle }$ et ${\displaystyle \langle k,l\rangle }$ dans la métrique des mots associée à cette partie génératrice est égale à ${\displaystyle |i-k|+|j-l|}$.

Soit ${\displaystyle G}$ un groupe, soit ${\displaystyle S}$ une partie génératrice de ${\displaystyle G}$, et supposons que ${\displaystyle S}$ est stable par inversion. Un mot sur l'ensemble ${\displaystyle S}$ est simplement une suite finie ${\displaystyle w=s_{1}...s_{L}}$ dont les coordonnées ${\displaystyle s_{1},...,s_{L}}$ sont des éléments de ${\displaystyle S}$. L'entier ${\displaystyle L}$ est appelée la longueur du mot ${\displaystyle w}$. En appliquant la multiplication de ${\displaystyle G}$, les coordonnées d'un mot ${\displaystyle w=s_{1}...s_{L}}$ peuvent être multipliées dans l'ordre. Le résultat de cette multiplication est un élément ${\displaystyle {\overline {w}}}$ dans le groupe ${\displaystyle G}$, qui est appelé à l' évaluation du mot ${\displaystyle w}$. Un cas particulier, le mot vide ${\displaystyle \emptyset }$ a pour longueur zéro, et son évaluation est le neutre de ${\displaystyle G}$.

Étant donné un élément ${\displaystyle g}$ de ${\displaystyle G}$, sa norme ${\displaystyle |g|}$ par rapport à l'ensemble ${\displaystyle S}$ est définie comme étant la plus courte longueur d'un mot ${\displaystyle w}$ sur ${\displaystyle S}$, dont l'évaluation ${\displaystyle {\overline {w}}}$ est égale à ${\displaystyle g}$. Pour deux éléments ${\displaystyle g,h}$ de ${\displaystyle G}$, la distance ${\displaystyle d(g,h)}$ dans la métrique des mots par rapport à ${\displaystyle S}$ est définie par ${\displaystyle |g^{-1}h|}$. De manière équivalente, ${\displaystyle d(g,h)}$ est la plus courte longueur d'un mot ${\displaystyle w}$ sur ${\displaystyle S}$ tel que ${\displaystyle g{\overline {w}}=h}$.

La métrique des mots par rapport à une partie génératrice ${\displaystyle S}$ de ${\displaystyle G}$ satisfait les axiomes d'une distance.

La métrique des mots a une définition équivalente formulée en termes plus géométriques en utilisant le graphe de Cayley de ${\displaystyle G}$ par rapport à une partie génératrice ${\displaystyle S}$. On assigne à chaque arête du graphe de Cayley une métrique de longueur 1, et alors la distance entre deux éléments ${\displaystyle g,h}$ de ${\displaystyle G}$ est égale à la plus petite longueur d'un chemin du graphe du sommet ${\displaystyle g}$ au sommet ${\displaystyle h}$ (qui peut être paramétrisée pour en faire une géodésique).

La métrique des mots sur ${\displaystyle G}$ peut également être définie sans supposer que la partie génératrice ${\displaystyle S}$ est stable par inversion. Pour ce faire, on commence par symétriser ${\displaystyle S}$, en le remplaçant par une plus grande partie génératrice consistant en chaque élément ${\displaystyle s}$ de ${\displaystyle S}$ ainsi que son inverse ${\displaystyle s^{-1}}$. Ensuite on définit la métrique des mots par rapport à ${\displaystyle S}$ comme la métrique des mots par rapport à sa symétrisation.

Supposons que ${\displaystyle F}$ est le groupe libre sur l'ensemble à deux éléments  ${\displaystyle \{a,b\}}$. Un mot ${\displaystyle w}$ sur la partie génératrice symétrique ${\displaystyle \{a,b,a^{-1},b^{-1}\}}$ est dit réduit si les lettres ${\displaystyle a,a^{-1}}$ ne se suivent pas dans ${\displaystyle w}$, et de même pour les lettres ${\displaystyle b,b^{-1}}$. Chaque élément ${\displaystyle g\in F}$ est représenté par un unique mot réduit, et ce mot réduit est le plus court mot représentant ${\displaystyle g}$. Par exemple, puisque le mot ${\displaystyle w=b^{-1}a}$ est réduit et est de longueur 2, la norme ${\displaystyle |{\overline {w}}|}$ est égale à 2, de sorte que la distance entre ${\displaystyle b}$ et ${\displaystyle a}$ est égale à 2 dans la métrique des mots. Cela peut être visualisé en termes de graphe de Cayley, où le chemin le plus court entre ${\displaystyle a}$ et ${\displaystyle b}$ est de longueur 2.

Le groupe ${\displaystyle G}$ agit sur lui-même par multiplication à gauche: l'action de ${\displaystyle k\in G}$ envoie chaque ${\displaystyle g\in G}$ sur ${\displaystyle kg}$. Cette action est une isométrie pour la métrique des mots. En effet, la distance entre ${\displaystyle kg}$ et ${\displaystyle kh}$ est égale à ${\displaystyle |(kg)^{-1}(kh)|=|g^{-1}h|}$, qui est la distance entre ${\displaystyle g}$ et ${\displaystyle h}$.

La métrique des mots sur un groupe ${\displaystyle G}$ n'est pas unique, car différentes parties génératrices symétriques peuvent donner des métriques différentes. Cependant, les métriques de mots sur un groupe de type fini, par rapport à des parties génératrices finies sont Lipschitz-équivalentes : si ${\displaystyle S,T}$ sont deux parties génératrices symétriques finies de ${\displaystyle G}$ avec les métriques des mots respectives associées ${\displaystyle d_{S},d_{T}}$, alors il existe une constante ${\displaystyle K}$ tels que, pour tout ${\displaystyle g,h\in G}$,

${\displaystyle {\frac {1}{K}}d_{T}(g,h)\leq d_{S}(g,h)\leq Kd_{T}(g,h)}$.

Cette constante ${\displaystyle K}$ est simplement le maximum de la norme pour la partie génératrice ${\displaystyle S}$ des éléments de ${\displaystyle T}$ et de la norme pour la partie génératrice ${\displaystyle T}$ des éléments de ${\displaystyle S}$. Cette preuve est également facile : n'importe quel mot sur ${\displaystyle S}$ peut être converti par substitution en un mot sur ${\displaystyle T}$ de même évaluation, augmentant la longueur du mot d'un facteur au plus ${\displaystyle K}$, et de même pour la conversion de mots sur ${\displaystyle T}$ en mots sur ${\displaystyle S}$ de même évaluation.

L'équivalence lipschitzienne des métriques des mots implique à son tour que le taux de croissance (en) d'un groupe de type fini est un invariant d'isomorphisme du groupe, indépendant du choix d'une partie génératrice finie. Cela implique à son tour que les différentes propriétés de croissance, telles que la croissance polynomiale, le degré de la croissance polynomiale, et la croissance exponentielle, sont des invariants d'isomorphisme.

En théorie géométrique des groupes, les groupes sont étudiés à travers leurs actions sur des espaces métriques. Un principe qui généralise l'invariance lipschitzienne des métriques des mots sur ${\displaystyle G}$ est que toute métrique des mots finiment générée sur ${\displaystyle G}$ est quasi-isométrique (en) à tout espace métrique géodésique propre sur lequel ${\displaystyle G}$ agit proprement discontinument et cocompactement. Il s'agit du lemme de Svarc-Milnor (en).

Il s'ensuit que toute propriété invariante par quasi-isométrie satisfaite par la métrique des mots sur ${\displaystyle G}$ ou par un tel espace métrique est un invariant d'isomorphisme de ${\displaystyle G}$. La théorie géométrique des groupes moderne est en grande partie destinée à l'étude des invariants par quasi-isométrie.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Word metric » (voir la liste des auteurs).
• (en) J. W. Cannon, « Geometric group theory », Handbook of Geometric Topology, North-Holland, Amsterdam, 2002 (ISBN 0-444-82432-4), p. 261-305

• Portail de la géométrie