Métrique des mots

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.