# Sur certaines pseudo-variétés de monoïdes finis

Marcel-Paul Schützenberger

► To cite this version:

Marcel-Paul Schützenberger. Sur certaines pseudo-variétés de monoïdes finis. [Rapport de recherche] IRIA-RR-062, IRIA. 1974, pp.14. hal-04715943

HAL Id: hal-04715943

https://inria.hal.science/hal-04715943v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

RIA
laboria

laboratoire de recherche
en informatique
et automatique

Sur certaines pseudo-variétés
de monoïdes finis

M.P Schutzenberger

<figure><img src="image_3.png" /></figure>

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 62

mars 1974
SUR CERTAINES PSEUDO-VARIÉTÉS DE MONOÏDES FINIS

M.P. Schutzenberger

**Résumé :**

On donne une condition nécessaire et suffisante pour que le monoïde syntactique d'un sous-monoïde appartienne à une pseudo-variété définie par une pseudo-variété de groupes donnée.

**Abstract :**

A necessary and sufficient condition is given for the syntactic monoid of a sub-monoid to belong to a certain pseudo-variety.
# SUR CERTAINES PSEUDO-VARIETES DE MONOIDES FINIS

M.P. SCHUTZENBERGER

I. Selon la théorie de S. Eilenberg, une pseudo-variété de semi-groupes (ou monoïdes, ou groupes) est une famille de telles structures contenant toute image homomorphe du produit sous direct de deux de ses membres. En particulier, étant donnée une pseudo-variété de groupes $\mathcal{U}$ on peut définir la pseudo-variété $\overline{\mathcal{U}}$ de monoïdes finis par la condition que $M \in \overline{\mathcal{U}}$ ssi chaque groupe dans M appartient à $\mathcal{U}$ et pour chaque alphabet $\Sigma$ la famille $\overline{\mathcal{U}}$-Rec des parties P de monoïde libre $\Sigma^*$ telles que leur monoïde syntactique appartienne à $\overline{\mathcal{U}}$.

On sait d'autre part que la pseudo-variété (de groupes) $\mathcal{U}$ associe à chaque groupe $G$ un plus petit sous-groupe normal $V_G$ (= le $\mathcal{U}$-noyau de $G$) tel que $G/V_G \in \mathcal{U}$. L'hypothèse que $\mathcal{U}$ est une pseudo-variété, équivaut à la condition que pour tout morphisme $\phi : G \to H$, on ait $V_{G\phi} \subset V_H$ si $\phi$ est injectif et $V_H \subset V_{G\phi}$ si $\phi$ est surjectif.

Le résultat principal de ce travail est la

## Propriété I.1.

Soit $A \in \overline{\mathcal{U}}$-Rec. On a $A^* \in \overline{\mathcal{U}}$-Rec ssi l'image $B=A^*\rho_{A^*}$ de $A^*$ dans son monoïde syntactique $S = \Sigma^* \rho_{A^*}$ satisfait la condition :
($\mathcal{U}$). B contient le $\mathcal{U}$-noyau de chacun des groupes qu'elle rencontre.

Il est trivial que cette condition est nécessaire : en effet, comme B est un sous semi groupe du monoïde fini : son intersection avec chaque groupe G dans S contient l'identpotent e de ce dernier qui est lui-même précisement le $\mathcal{U}$-noyau de G ssi $G \subset \mathcal{U}$.

Nous ne nous occuperons donc plus désormais que de l'implication inverse.

Dans la section III nous utilisons la propriété précédente pour retrouver divers résultats connus.

Nous terminons cette introduction en rappelant quelques propriétés du monoïde syntactique, elles aussi connues depuis les travaux de R. Croisot (Equivalences Principales Bâtères définies dans un demi-groupe. J. de Math. Pures et Appl. 36 (1957). pp. 373-417).
**Proposition I.2**

Soit $M'=M_{\rho_E}$ le monoïde syntactique de la partie E de M.
Le morphisme syntactique $\rho_E$, de la partie $E'=E_{\rho_E}$ de M'
est l'identité.

**Preuve :** Par définition $M'$ est le plus petit quotient de M pout
lequel le morphisme correspondant $\phi$ de M satisfasse
$E=E_{\phi\phi}^{-1}$. L'énoncé en découle en vérifiant que cette der-
nière relation est satisfaite par $\phi=\rho_E^{\rho_E'}$.

Q.E.D.

Pour chaque $m_1 \in M$ nous posons
$$ E::m_1 = \{ (m,m') \in M \times M : mm_1 m' \in E \}. $$

**Proposition I.3**

Pour tout $m_1, m_2 \in M$ on a $m_1 \rho_E = m_2 \rho_E$ ssi $E::m_1 = E::m_2$.

**Preuve :** Il est clair que la relation $E$ ; $m_1=E::m_2$ définit une équivalence $\equiv$ sur M. Comme $E::(m_1 m_3) = \{ (m,m') \in E::m_1 : m' \in m_3 M\} = (E::m_1) \cap (M, m_3 M)$ pour tout $m_1, m_3 \in M$ puisque M contient un élément neutre 1, et comme une relation semblable vaut pour $m_3 m_1$, on voit que de fait, $\equiv$ est une congruence. Puisque (1,1) appartient à $E::m_1$ ssi $m_1 \in E$, elle sature E et elle contient toutes les congruences ayant cette propriété puisque $m_1 \not\in m_2$ implique l'existence d'une paire $(m_1 m')$ pour laquelle un seul des éléments $mm_1 m'$ et $mm_2 m'$ appartient à E.

Q.E.D.
Nous appliquons ceci au groupe G dans $S=\Sigma_{\rho}^*$ en désignant désormais par $\rho$ le morphisme syntactique $\rho_A^*$. Comme ci-dessus, e et V sont l'idempotent et le $U$-noyau de G.

**Lemme I.4.** Soit $b \in e\rho^{-1}$. Supposons que pour tout $f, f' \in \Sigma^*$ tels que $fbb^*f'cA^*$ et chaque $v \in V$ il existe un $c \in v\rho^{-1}$ pour lequel on ait

$$ (X) \quad fb^*cb^*f'nA^{n \neq \emptyset} $$

Alors $V=\{e\}$.

**Preuve :** Comme $b\rho=e=e^2$ on a $bb^*\rho=e$, et par conséquent $fbb^*f'cA^*$ implique $(f\rho)e(f'\rho)\in A^*\rho$. De même, comme $v=ev=ve=eve$ puisque $v\in V\subset G$, la relation $(X)$ implique $(f\rho)v(f'\rho)\in A^*$.

Maintenant d'après I.2 et I.3 ci-dessus avec $M=S$ et $E=A^*$ on a $e=v$ssi $A^*\rho::=e=A^*\rho::v$.

L'hypothèse du lemme équivaut à l'assertion que chaque $(s,s') \in A^*\rho::=e$ appartient à tous les $A^*\rho::v$ $(v\in V)$. En effet la première relation implique $(s\rho^{-1})(e\rho^{-1})(s'\rho^{-1})\subset A^*\rho\rho^{-1}=A^*$ donc $fbb^*f'cA^*$ pour tout $f\in s\rho^{-1}$, $f'\in s\rho^{-1}$ et la relation $(X)$. Ceci suffit pour entrainer l'égalité de $A^*\rho::=e$ et de chacun des $A^*\rho::v$ car si $(s,s')$ est dans ce dernier ensemble on a $(s,s'')\in A^*\rho::=e$ pour $s''=vs'$ donc $(s,s'')\in A^*\rho::v^{-1}$, ce qui équivaut à $(s,s')\in A^*\rho::=e$ puisque $sv^{-1}s''=sv^{-1}v's'=ses'$.

Q.E.D.
## II. Vérification de la proposition I.1.

Nous gardons les mêmes notations que dans le lemme I.4.
Dans le premier énoncé ci-dessous, nous choisissons un
mot $b \in \mathbb{P}^{-1}$. Dans les suivants nous vérifions que (X) est
vraie dans tous les cas. Dans les deux derniers, seul
intervient le fait que $\Sigma^*$ est un monoïde libre et plus
exactement que chaque mot $s \in \Sigma^*$ a une longueur $|s| \in \mathbb{N}$, (avec
$|s| > 0$ ssi $s \neq 1$). Dans les trois premiers on exploite l'hy-
pothèse $T \in \mathcal{U}$ où pour abréger $\tau: \Sigma^* \to T$ désigne le morphisme
syntactique de A.

II.1. Sous l'hypothèse $T \in \overline{\mathcal{U}}$, il existe un sous-ensemble fini $C$ de $\Sigma^*$ tel que $C_\rho = G$ et $C_\tau = u$ où $u$ est un idempotent de $T$.

*Preuve* : Comme $G_\rho^{-1}$ est un semi groupe et $T$ un ensemble fini, l'ensemble $G_\rho^{-1}_\tau$ est un semi groupe *fini*. D'après un théorème classique de Clifford (Am. J. of Math. **70** (1948) pp. 521-526) il contient un groupe $H$ tel que $H=H(G_\rho^{-1}_\tau)H$. Cette relation entraine que $P_\rho=G$ et $P_\tau=H$ où $P$ désigne l'intersection de $G_\rho^{-1}$ et $H\tau^{-1}$. Suit e l'idempotent de $G$.
Posons $g_\lambda=(g_\rho^{-1} \cap P)\tau$ pour chaque $g \in G$. On a identiquement

(2.1.) $(g_1\lambda)(g_2\lambda)\subset(g_1g_2)\lambda$
puisqu'une relation semblable vaut pour $\rho^{-1}$. Prenant en particulier $g_1= g_2=e$, on en déduit en utilisant la finitude de $H$ que $e\lambda$ est un sous groupe $K$ de $H$. Prenant successivement $g_1=e$ et $g_1=g_2^{-1}$, la même relation (2.1.) montre que $K$ est un sous groupe normal et que $\lambda$ induit un morphisme de $G$ sur $H/K$. De
façon symétrique, on trouve que le noyeau $L$ de $\lambda$ est
l'ensemble $C'_{\rho}$ où $C'=P_n u_{\tau}^{-1} (u=u^{2} \in H)$.

Faisons internener l'hypothèse $T \in \tilde{U}$. Comme $\tilde{U}$ est une
pseudo variété de groupes elle entraine que $H$ et $H/K$ appar-
tiennent à $\tilde{U}$ et nous en concluons que $L$ contient le
$\tilde{U}$-noyau $V$ de $G$ en raison de l'isomorphie de $G/L$ et $H/K$
et du caractère minimal de $V$. L'énoncé en résulte en prenant
pour $G$ une partie convenable de $C'_{nV_{\rho}}^{-1}$.

Q.E.D.

Corollaire II.2.

Soient $b, c \in C$. On a $xbx' \in A$ pour tout $x, x' \in \Sigma^*$ tels que $xbx' \in A$.

Preuve : Ceci résulte immédiatement de $C_{\tau}=u=u^2$ et de la définition de $\tau$ comme morphisme syntactique de $A$.

Q.E.D.

Dorénavant $b$ sera un mot fixe de $C_{nep}^{-1}$ et $f, f'$ une paire de
mots telle que $fbb^*f'cA^*$.

II.3. Supposons $fb^n f' \in (A\backslash 1)^k$ pour une paire d'entiers $n, k$ telle que $n \ge k+1$.
Pour chaque $c \in C$ on a la relation
$$ (X) \quad fb^*cb^*f^nA \ne \emptyset $$

Preuve : Soit $fb^n f' = a_1 a_2 \dots a_k$ où chaque $a_i \in A$.

On associe à chaque $m \le n$ le plus grand entier $i=i_m$ pour lequel
$a_1 \cdots a_i$ est un facteur gauche de $fb^m$. Comme $n \ge k+1$ il existe
un $m$ pour lequel $i_m=i_{m+1}$. Ceci permet de trouver des mots
$a', a'' \in A^*$ ; $a \in A$, $x, x' \in \Sigma^*$ satisfaisant les relations $fb^m=a'x$ ;
$xbx'=a$ ; $b^{m'}f'=x'a''$. Celles ci entrainent que pour tout mot
d le mot $w=fb^m db^{m'} f'$ soit égal à $a'd'a''$ où $d'=xbdx'$. D'après
le corollaire II.2. et xbx' ∈ A, on a donc w ∈ A* quand d=c ∈ C.

Q.E.D.

Nous n'utiliserons plus désormais l'hypothèse $T \in \overline{\mathbb{U}}$ mais nous supposerons toujours que la condition (U) est satisfaite.

II.4. Soient $t, t' \in S$ tels que $tt' = e$ et $t' \in A^*$. La condition (U) entraîne que V soit contenu dans $t(A^* \rho)t'$.

*Preuve* : Soit $g_\theta=t'gt$ pour chaque $g \in G$. On a
$$t(g_\theta)t' = tt'gt't' = ege = g \text{ et } (g_\theta)(g'_\theta) = tgt'tg't' =$$
$$tgeg't = tgg't' = (gg')_\theta \text{ pour tout } g' \in G. \text{ Par conséquent } \theta \text{ est un morphisme sur un groupe } G' \text{ et } V = tV_G, t'$. Maintenant nous avons$$e_\theta = t' \in A^* \rho \text{ par hypothèse, donc } V_G \subset A^* \rho \text{ d'après (U).}$$

Q.E.D.

II.5. Supposons que l'hypothèse de II.3. ne soit pas satisfaite par $b, f, f'$. Pour chaque $v \in V$, on peut trouver un $c \in v_\rho^{-1}$ pour lequel (X) est vérifiée.

*Preuve* : Soit $w=fb^n f'$ où $n=|f|+|f'|+2|b|^2$. Par l'hypothèse, $w$ est un produit $a_1 a_2 \dots a_k$ de mots de $A\setminus b$ où $k \ge n$. Soit $d$ le plus petit indice, lequel $p_0=a_1 \dots a_d$ ait $f$ comme facteur gauche et soit $d'$ le plus grand indice pour lequel $p_{|b|+1} = a_{d'+1} \dots a_k$ ait $f$ comme facteur droit. Comme tous les $a_i$ ont une longueur positive, on a $d \le |f|$ et $k-d \le |f'|$ et par conséquent $w=p_0 p_{|b|+1}$ ou $p$ est le produit d'au moins $2|b|^2$ mots de $A\setminus b$. On peut donc écrire $p=\bar{p}_1 \bar{p}_2 \dots \bar{p}_{|b|}$ où chaque $\bar{p}_i \in A^*$ à une longueur au moins égale à $2|b|$. Ceci définit pour chaque $j=0,1,\dots,|b|$ un facteur gauche $b_j \ne b$ de $b$ tel que $\bar{p}_0 \bar{p}_1 \dots \bar{p}_j \in fb^*b_j$.
Comme b a évidemment $|b|$ facteurs gauches propres, on a $b_j := b_j$
pour au moins une paire $0 \le j' < j \le |b|$. Définissant $b'$ par

$b=b_j, b'=b_j b'$.

$$
\bar{a}_1 = \bar{p}_0 \cdots \bar{p}_j = \text{fb}^m b_j
$$

$$
\bar{a}_2 = \bar{p}_{j+1} \cdots \bar{p}_j = b' b^q b_j
$$

$$
\bar{a}_3 = \bar{p}_{j+1} \cdots \bar{p}_{|b|+1} = b' b^{m'} f'
$$

où $q \ge 1$ en raison de $|\bar{p}_{j'+1} - \ge 2|b|$.

Les hypothèses de II.4 sont satisfaites par $t=b_j\rho=b_j\rho$ et $t'=b'\rho$
et nous pouvons donc trouver pour chaque $v\in V$ un mot $a\in A^*$ tel que
$c=b_jab'\epsilon v\rho^{-1}$. Considérons maintenant le mot $w'=\bar{a}_1\bar{a}_2\bar{a}_3\epsilon A^*$. Il est
égal au mot $fb^{m+1}bjab'b^{m'}f'$ qui appartient à $fb^*cb^*f'$.

Q.E.D.

Ceci achève de montrer que les hypothèses du lemme I.4. sont
satisfaites dans tous les cas et conclut la preuve de la proposi-
tion I.1.
### III. Exemples.

Dans ce qui suit, nous utiliserons le théorème suivant qui ne rassemble que des faits connus.

**Théorème III.1.** Soit $S$ un élément d'un monoïde ayant au plus $m<\infty$ éléments et soit $p \ge 1$ le plus petit commun multiple des entiers $\le m$.

(i) Soit $q \ge 0$ le plus petit entier tel que $s^{q} \in S$ et $s^{q+1} \in S$. L'ensemble $s^{q} *$ est un groupe cyclique $C_q$ dont l'ordre $\pi(s)$ divise $p$.

(ii) Pour chaque multiple $p' \ge q$ de $\pi(s)$, $s^{p'}$ est l'idempotent de $C_q$;

(iii) $s^{p-1} \in C_q$.

Nous examinons maintenant le cas particulier d'une pseudo-variété de groupes $U(\Pi)$ définie par un ensemble non vide $\Pi$ d'entiers positifs et la condition que l'ordre $\pi(g)$ de tout élément $g$ d'un groupe de $U$ soit dans $\Pi$. Comme $U$ contient tous les sous groupes de ses membres, $\Pi$ doit contenir les diviseurs de ses éléments et comme $U$ est fermée par produit direct, $\Pi$ doit l'être par rapport au p.p.c.m. Réciproquement, il est clair que tout $\Pi$ satisfaisant ces deux conditions définit une pseudo-variété. Le cas où $\Pi$ est formé de toutes les puissances d'un nombre premier donné a été étudié par Bret Tilson ("On the p-Length of p-solvable semi groups" in "Semi groups", K.W. Folley Ed. 1969). Le cas où $\Pi$ se réduit à $\{1\}$ donne la pseudo-variété des monoïdes finis dont tous les groupes sont triviaux qui sert dans la théorie des "Counter Free Automata" de R.Mc Naughton et S. Pappert (MII Press 1971).
Nous considérons maintenant une pseudo-variété $\mathcal{V} = \mathcal{V}(\Pi)$ fixe.

**Exemple III.2.** Soit $A \in \mathcal{V}(\Pi)$-Rec ; $A^*$ appartient à la même famille ssi pour chaque mot $h \in \Sigma^*$ et tout $n \in \mathbb{N}$ assez grand on a l'implication :
$$h^{n} \in A^{*} \Longrightarrow h^{n+m} \in A^{*} \text{ où}$$

$m=n \wedge \Pi$ désigne le plus grand diviseur de $n$ qui appartienne à $\Pi$.

*Preuve* : Supposons $h^{n} \in A^{*}$ pour un $n \ge 1$. D'après le Théorème III.1, il existe un entier $q \in \mathbb{N}$ tel que $(h^q h^*)_\rho$ soit un groupe cyclique $C$ et comme $A^*$ est un monoïde, $(h^q h^*)_{nA^*} \rho$ est un sous groupe $C'$ de $C$. Posant $r=\text{Card}(C)$, $r'=\text{Card}(C')$ on a que le $\mathcal{U}$noyau $V$ de $C$ est formé des éléments de la forme $C_\rho$ ($c \in C$) où $p=r \wedge \Pi$ et que pour chaque $n \ge q$ on a $h^{n} \in A^{*}$ ssi $n \in r'\mathbb{N}$. Par conséquent, la condition énoncée équivaut à $V \subset C'$ et le résultat découle de la Prop. III.1.

Q.E.D.

Une formulation plus élégante due aussi à S.Eilenberg est la suivante : Pour chaque $h \in \Sigma^*$, et $n \in \mathbb{N}$ tels que $(h^m)^* \setminus A^*$ est fini on a $(h^m)^* \setminus A^*$ fini, où $m=n \wedge \Pi$.

Nous laissons au lecteur d'en vérifier l'équivalence avec la précédente. On notera que comme $\text{Card}(A^*\rho)$ peut être borné à priori en fonction de $k=\text{Card}(A_\rho)$, il suffit de vérifier l'implication pour tous les mots h de longueur inférieure à une certaine fonction de k et tous les n appartenant à un interval fini qui est aussi fonction de k.

Nous revenons maintenant à des pseudo-variétés plus générales. Elles requièrent une construction assez pesante pour obtenir des ensembles d'éléments contenus dans un groupe.
Nous commençons par introduire un résultat technique en
utilisant les théorèmes classiques de Miller et Clifford
(Regular D-classes in Semi groups ; Trans Am. Math.Soc. 82
1956. 270-280).

Dans tout ce qui suit Ω_m désigne le segment initial {ω_1, ..., ω_m}
de l'alphabet infini Ω={ω_j : j≥1}.

**Définition :** Soit $\alpha_m$ l'endomorphisme de $\Omega^*$ défini par :

$$
\omega_j^{\alpha_m} = \omega_1^{p_1} \omega_2^{p_2} \cdots \omega_{j-1}^{p_{j-1}} \omega_j^{p_j+1} \cdots \omega_m^{p_m}
$$

(où p≥1 est le p.p.c.m des entiers ≥m) pour 1≤j≤m ;

$$
\omega_j^{\alpha_m} = 1 \text{ pour } j \ge m+1.
$$

Nous considérons maintenant les endomorphismes $\alpha_m^k$ ($k \in \mathbb{N}$) obtenus
en itérant $\alpha_m$ et pour abréger nous écrivons $\alpha$ au lieu de $\alpha_m$.

III.3. Soit $\phi$ un morphisme de $\Omega_m^*$ dans un monoïde $S$ ayant au plus $m$ éléments.

(i) $\alpha_k^\phi = \alpha^{k'} \phi$ pour tout $k' \ge k$ quand $S_k = \Omega_m \alpha_k^\phi$ est contenu dans un groupe ;

(ii) Cette dernière condition est satisfaite par au moins un $k \le m$.

**Preuve** : Nous posons $s_{j,k} = \omega_j \alpha^{k}_{\phi}$ et $e_{j,k} = (s_{j,k})^{p} = \omega_j^{p} \alpha^{k}_{\phi}$. Donc
$s_{j,0} = \omega_j^{\phi}$ et $s_{j,k+1} = e_{1,k} e_{2,k} \cdots e_{j,k} s_{j,k} e_{j+1,k} \cdots e_{m,k}$
identiquement.

D'après le théorème III.1. et notre choix de p, tous les $e_{j,k}$ sont
des idempotents. Donc quand $S_k = \Omega_m \alpha^{k}_{\phi} = \{s_{j,k} : 1 \le j \le m\}$ est contenu dans
un groupe, tous ces éléments sont égaux à l'idempotent e de ce dernier et l'on a identiquement $s_{j,k+1} = e_{s_{j,k}} = e_{s_{j,k}}$ ce qui établit (i).

Soit maintenant pour chaque $k \ge 0$, $J_k$ l'union des idéaux $S e_{j,k}^S$ ($1 \le j \le m$). Il est clair que chacun de ces derniers contient tous les $s_{i,k+1}$ ($1 \le i \le m$) et que par conséquent $J_k \supseteq J_{k+1}$. Si $l$ est la longueur maximum d'une chaine décroissante d'idéaux (non vides) de $S$, il existe donc un plus petit $k \le l$ pour lequel $J_k = J_{k+1}$. Or, comme on vient de le dire, $J_{k+1}$ est contenu dans l'intersection des idéaux $S e_{j,k}^S$ ($1 \le j \le m$) et l'on a la relation $J_{k+1} = J_k = J_{j,k}$ ($1 \le j \le m$) qui montre que $J_k$ est un idéal principal. Soit $D=\{s \in S : S \subsetneq S = J_k\}$. La relation précédente équivaut à l'assertion que $D$ contient tous les $e_{j,k}$ ($1 \le j \le m$) et au moins un $e_{i,k+1}$.

Posons $P=G_1G_2\cdots G_m$, où chaque $G_j$ est la $J_G$-classe de $e_{j,k}$.

Tous les $s_{j,k+1}$ ($1 \le j \le m$) sont contenus dans $P$. Par conséquent, l'existence d'au moins un $e_{i,k+1} \in D$ montre que $P \cap D \ne \emptyset$. Comme $P$ est par construction un produit de $J_G$-classes contenues dans la $J_G$-classe $D$, les résultats de Clifford et Miller impliquent $P$ soit elle une $J_G$-classe contenue dans $D$ et enfin que $P$ soit un groupe ssi $P^{+} \cap D \ne \emptyset$. Or cette dernière relation résulte immédiatement de l'existence de $e_{i,k+1} \in D$ et nous avons donc établi que $S_{k+1}$ est contenu dans un groupe.

Pour justifier que $k<m$, il suffit enfin d'observer que $l=m$ ssi $S=\{1,s,s^2,\dots,s^m=s^{l+m}\}$ où $s^j \ne s^m$ pour $j<m$ et que dans ce cas particulier, l'on a soit $S_0=S_1=\dots=\{1\}$, soit $S_1=\{s^m\}$.

Q.E.D.
On notera que si l'on suppose $S_k=S_{k+1}$ au lieu de $J_k=J_{k+1}'$ la première partie de l'argument montre que chaque $S_{j,k}$ est contenu dans le *groupe* $G_j$ et que $S_{k+1}^{cP}$ une $\mathbb{Z}_c$-classe dans D. On en conclut de même que P est un groupe d'après $G_j \subset P(1 \le j \le m)$.