Mots, réduction et action de van der Waerden

(i) La suite vide de mouvements donne $u \approx u$. Une suite lue à l'envers, où chaque mouvement est remplacé par le mouvement inverse, donne la symétrie ; deux suites mises bout à bout donnent la transitivité.

Un mouvement qui transforme $u$ en $u'$ porte sur un facteur $xx^{-1}$ de $u$, qui reste un facteur de $uv$ : le même mouvement transforme $uv$ en $u'v$. De même à droite, et donc $uv \approx u'v \approx u'v'$.

(ii) Par récurrence sur la longueur. Un mot qui n'est pas réduit s'écrit $u\,xx^{-1}\,v$ ; il est équivalent à $uv$, plus court de deux lettres, lui-même équivalent à un mot réduit par l'hypothèse de récurrence.

(iii) Le mot $\sigma_x(w)$ est réduit : si $w = x^{-1}w'$, le mot $w'$ est la fin d'un mot réduit ; sinon, $xw$ est réduit, puisque $w$ l'est et ne commence pas par $x^{-1}$.

Montrons que $\sigma_{x^{-1}} \circ \sigma_x$ est l'identité. Si $w = x^{-1}w'$, le mot $w'$ ne commence pas par $x$, puisque $w$ est réduit, et donc $\sigma_{x^{-1}}(w') = x^{-1}w' = w$. Sinon, $\sigma_x(w) = xw$ commence par $x = (x^{-1})^{-1}$, et $\sigma_{x^{-1}}(xw) = w$.

En échangeant les rôles de $x$ et de $x^{-1}$, on obtient aussi $\sigma_x \circ \sigma_{x^{-1}} = \mathrm{id}$.

(iv) Notons $\mathcal B$ l'ensemble des bijections de $\mathcal R$ et $\mathcal W_n$ celui des mots de longueur au plus $n$. Par récurrence sur $n$ (Définition par récurrence), à valeurs dans l'ensemble fixe des parties de $\mathcal W(S) \times \mathcal B$, on définit une suite d'applications $\Sigma_n : \mathcal W_n \to \mathcal B$ : $\Sigma_0(1) = \mathrm{id}$, et $\Sigma_{n+1}$ prolonge $\Sigma_n$ par $\Sigma_{n+1}(xw) = \sigma_x \circ \Sigma_n(w)$ pour $w$ de longueur $n$. Leur réunion est une application $\Sigma : \mathcal W(S) \to \mathcal B$, telle que $\Sigma(1) = \mathrm{id}$, $\Sigma(xw) = \sigma_x \circ \Sigma(w)$, et $$\Sigma(x_1 \cdots x_n) = \sigma_{x_1} \circ \cdots \circ \sigma_{x_n}.$$ Par récurrence sur la longueur de $u$, on a $\Sigma(uv) = \Sigma(u) \circ \Sigma(v)$.

Par (iii), il vient $$\begin{aligned} \Sigma(u\,xx^{-1}\,v) &= \Sigma(u) \circ \sigma_x \circ \sigma_{x^{-1}} \circ \Sigma(v) \\ &= \Sigma(uv) : \end{aligned}$$ $\Sigma$ est invariante par mouvement élémentaire, donc constante sur chaque classe.

Pour un mot réduit $w$, on a $\Sigma(w)(1) = w$, par récurrence sur la longueur : si $w = xw'$, le mot $w'$ est réduit et ne commence pas par $x^{-1}$, donc $\Sigma(w)(1) = \sigma_x(w') = xw' = w$.

Si $w$ et $w'$ sont réduits et équivalents, on a donc $w = \Sigma(w)(1) = \Sigma(w')(1) = w'$. Avec (ii), chaque classe contient exactement un mot réduit.