Groupe de Grigorchuk

Le groupe a été construit par Grigorchuk en 1980[2], et il a prouvé qu'il est de croissance intermédiaire en 1984[3] ; ceci répond à une question posée par John Milnor en 1968[4]. Le groupe de Grigorchuk continue à être un objet clé en théorie géométrique des groupes, en particulier en relation avec les groupes automatiques, et a aussi des connexions avec les groupes de monodromie itérée[5].

Le taux de croissance d'un groupe finiment engendré est le nombre b(n) d'éléments du groupe qui sont produits d'au plus n éléments de l'ensemble de générateurs. Grigorchuk a prouvé que b(n) croît plus vite que ${\displaystyle \exp({\sqrt {n}})}$ mais moins vite que ${\displaystyle \exp(n^{s})}$ où ${\displaystyle s=\log _{32}31\approx 0.991}$.

La borne supérieure a été améliorée par Laurent Bartholdi[6] qui obtient :

${\displaystyle s={\frac {\log 2}{\log 2-\log \eta }}\approx 0.7675}$,

où ${\displaystyle \eta }$ vérifie ${\displaystyle \eta ^{3}+\eta ^{2}+\eta =2.}$ Une meilleure borne inférieure ${\displaystyle \exp(n^{0.504})}$ a été démontrée par Yurii Leonov[7].

Un résultat lié est le théorème de Gromov sur les groupes à croissance polynomiale, obtenu par Mikhaïl Gromov en 1981, qui montre qu'un groupe finiment engendré a croissance polynomiale si et seulement si ce groupe a un sous-groupe nilpotent d'index fini. Avant l'exemple de Grigorchuk, plusieurs résultats ont décrit des classes de groupes dont la croissance est soit polynomiale soit exponentielle, comme les groupes linéaires ou les groupes résolubles[8]^,[9] etc.

Des extensions et généralisations ont été proposées par divers auteurs[10]^,[11]^,[12]^,[13].

Arbre binaire ${\displaystyle T_{2}}$.

Le groupe de Grigorchuk est défini comme un groupe d'automorphismes de l’arbre binaire infini. L'arbre, noté ${\displaystyle T}$ (on rencontre aussi la notation ${\displaystyle T^{(2)}}$ ou ${\displaystyle T_{2}}$), est vu comme l'ensemble ${\displaystyle \Sigma ^{*}}$ des mots finis sur l'alphabet ${\displaystyle \Sigma =\{0,1\}}$, y compris le mot vide ${\displaystyle \varepsilon }$ (ou ${\displaystyle \varnothing }$) qui est la racine de l’arbre. Pour tout nœud ${\displaystyle x}$ de l’arbre ${\displaystyle T}$, le mot ${\displaystyle x0}$ est le fils gauche de ${\displaystyle x}$ et le mot ${\displaystyle x1}$ est le fils droit de ${\displaystyle x}$ dans ${\displaystyle T}$. Le groupe ${\displaystyle {\text{Aut}}(T)}$ peut alors être vu comme le groupe de toutes les bijections ${\displaystyle \sigma }$ de ${\displaystyle \Sigma ^{*}}$ qui préservent les longueurs, donc qui sont des permutations sur les mots de même longueur, et qui respectent les préfixes ; en d'autres termes, si ${\displaystyle y}$ est préfixe de ${\displaystyle x}$, alors ${\displaystyle \sigma (y)}$ est préfixe de ${\displaystyle \sigma (x)}$.

Le groupe de Grigorchuk ${\displaystyle G}$ est le sous-groupe du groupe d'automorphisme ${\displaystyle {\text{Aut}}(T)}$ engendré par quatre éléments particuliers de ${\displaystyle {\text{Aut}}(T)}$, notés ${\displaystyle a,b,c,d}$, soit

${\displaystyle G=\langle a,b,c,d\rangle }$,

où les automorphismes ${\displaystyle a,b,c,d}$ sont définis par les relations suivantes :

${\displaystyle {\begin{aligned}&a(0x)=1x\\&a(1x)=0x\\\end{aligned}}\qquad {\begin{aligned}&b(0x)=0a(x)\\&b(1x)=1c(x)\\\end{aligned}}\qquad {\begin{aligned}&c(0x)=0a(x)\\&c(1x)=1d(x)\\\end{aligned}}\qquad {\begin{aligned}&d(0x)=0x\\&d(1x)=1b(x).\\\end{aligned}}}$

Dans ces formules, ${\displaystyle x}$ est un mot de ${\displaystyle \Sigma ^{*}}$, y compris le mot vide. Pour ${\displaystyle x=\varepsilon }$, les formules se réduisent à

${\displaystyle a(0)=1,\ a(1)=0,\ b(0)=c(0)=d(0)=0,\ b(1)=c(1)=d(1)=1,}$

puisque l'image du mot vide par un automorphisme est toujours le mot vide. Seule l'automorphisme ${\displaystyle a}$ est défini explicitement, les autres le sont par récurrence sur la longueur de l'argument, qui correspond à la hauteur de l'élément dans l'arbre. Par exemple, l'évaluation de ${\displaystyle b(1011)}$ donne

${\displaystyle b(1011)=1c(011)=10a(11)=1001}$.

L'ensemble des mots de ${\displaystyle \Sigma ^{*}}$ s'écrit comme réunion disjointe

${\displaystyle \Sigma ^{*}=\{\varepsilon \}\cup 0\Sigma ^{*}\cup 1\Sigma ^{*}}$.

Les sommets de ${\displaystyle T}$ dénotés par ${\displaystyle 0\Sigma ^{*}}$ et ${\displaystyle 1\Sigma ^{*}}$ constituent respectivement le sous-arbre gauche et le sous-arbre droit de ${\displaystyle T}$, notés ${\displaystyle T_{L}}$ (parfois aussi ${\displaystyle T_{0}}$) et ${\displaystyle T_{R}}$ (ou ${\displaystyle T_{1}}$). On a alors

${\displaystyle a(T_{L})=T_{R},\quad a(T_{R})=T_{L}}$,

en d'autres termes ${\displaystyle a}$ échange les éléments des sous-arbres gauche et droit niveau par niveau. Les actions de ${\displaystyle b,c}$ et ${\displaystyle d}$ peuvent s'écrire aussi sous la forme :

${\displaystyle b=(a,c)\quad c=(a,d)\quad d=(e,b)}$

où ${\displaystyle e}$ est l'identité du groupe d'automorphisme, et où la première composante est l’action quand le mot est dans le sous-arbre gauche, la deuxième composante quand est dans le sous-arbre droit ; en d'autres termes :

${\displaystyle b(x)={\begin{cases}a(x)&x\in T_{L}\\c(x)&x\in T_{R}\end{cases}}\quad c(x)={\begin{cases}a(x)&x\in T_{L}\\d(x)&x\in T_{R}\end{cases}}\quad d(x)={\begin{cases}x&x\in T_{L}\\b(x)&x\in T_{R}\end{cases}}}$.

Plusieurs formules relient les éléments. Notamment la conjugaison par ${\displaystyle a}$ permet l'échange des composants :

${\displaystyle aba=(c,a),\quad aca=(d,a),\quad ada=(b,e).}$

La vérification est facile, ainsi

${\displaystyle aba(0x)=ab(1x)=a(1c(x))=0c(x),\ aba(1x)=ab(0x)=a(0a(x))=1a(x)}$.

Les éléments ${\displaystyle a,b,c}$, et ${\displaystyle d}$ sont des involutions ; la preuve est directe pour ${\displaystyle a}$, et par récurrence sur la longueur des mots pour les autres :

${\displaystyle {\begin{aligned}&a(a(0x))=a(1x)=0x,&&a(a(1x))=a(0x)=1x\\&b(b(0x))=b(0a(x))=0a^{2}(x)=0x,&&b(b(1x))=b(1c(x))=1c^{2}(x)\\&c(c(0x))=c(0a(x))=0a^{2}(x)=0x,&&c(c(1x))=c(1d(x))=1d^{2}(x)\\&d(d(0x))=d(0x)=0x,&&d(d(1x))=d(1b(x))=1b^{2}(x).\\\end{aligned}}}$

Les éléments ${\displaystyle b,c,d}$ commutent deux-à-deux et leur produit est égal au troisième :

${\displaystyle bc=cb=d,\ bd=db=c,\ dc=cd=b.}$[3]

de sorte que ${\displaystyle \langle b,c,d\rangle }$ est un groupe abélien d'ordre 4 isomorphe au produit direct de deux groupes cycliques d'ordre 2.

Il en résulte aussi que le groupe ${\displaystyle G}$ est aussi engendré par trois éléments, à savoir ${\displaystyle a}$ et deux quelconques parmi ${\displaystyle b,c,d}$. Ainsi, ${\displaystyle G=\langle a,b,c\rangle =\langle a,b,d\rangle =\langle a,c,d\rangle }$.

Mot réduit : Tout élément de ${\displaystyle G}$ s'écrit comme produit d'éléments de sorte qu'entre deux ${\displaystyle a}$, il y a exactement un des éléments b, c, ou d. Une telle écriture est dite réduite. Ainsi, l'écriture réduite de ${\displaystyle x=ab^{3}cda^{2}cdab}$ est ${\displaystyle r(ab^{3}cda^{2}cdab)=abab}$[14].

Voici des propriétés de base du groupe de Grigorchuk (des démonstrations sont données dans la monographie de Pierre de la Harpe[14]):

• Le groupe ${\displaystyle G}$ est infini[3].
• Le groupe ${\displaystyle G}$ est résiduellement fini[3]. Soit ${\displaystyle \rho _{n}:G\to {\text{Aut}}(T[n])}$ le morphisme qui envoie un élément de ${\displaystyle G}$ sur sa restriction à l'arbre fini ${\displaystyle T[n]}$ de hauteur ${\displaystyle n}$. Les groupes ${\displaystyle {\text{Aut}}(T[n])}$ sont finis et pour tout ${\displaystyle g\in G}$ non trivial, il existe un ${\displaystyle n}$ tel que ${\displaystyle \rho _{n}(g)\neq 1}$.
• Le groupe ${\displaystyle G}$ est un 2-groupe, c'est-à-dire tous ses éléments sont d'ordre fini qui de plus est une puissance de 2[2].
• Le groupe ${\displaystyle G}$ est de croissance intermédiaire[3].
• Le groupe ${\displaystyle G}$ est moyennable mais n'est pas un groupe élémentairement moyennable (en)[3].
• Le groupe ${\displaystyle G}$ est juste infini (en), c'est-à-dire qu'il est infini mais que tous ses groupes quotient sont finis.
• Le groupe ${\displaystyle G}$ a la congruence subgroup property : un sous-groupe H est d'indice fini dans G si et seulement si ${\displaystyle \ker(\rho _{n})\leqslant H.}$ pour un entier n.
• Le problème de l’appartenance à un sous-groupe est décidable dans le groupe G ; en d'autres termes, il existe un algorithme qui, étant donné des mots ${\displaystyle w,u_{1},\ldots ,u_{n}}$, décide si ${\displaystyle w}$ est un élément du sous-groupe engendré par ${\displaystyle u_{1},\ldots ,u_{n}}$[15].
• Le groupe ${\displaystyle G}$ est séparable (en), c'est-à-dire tout sous-groupe finiment engendré est fermé dans la topologie profinie sur ${\displaystyle G}$[15]
• Tout sous-groupe maximal de ${\displaystyle G}$ est d'indice fini dans ${\displaystyle G}$[16].
• Le groupe ${\displaystyle G}$ est finiment engendré mais n’a pas de présentation finie[3]^,[17].

• Le stabilisateur des sommets de niveau 1 de ${\displaystyle T}$ dans G (le sous-groupe des éléments qui opèrent comme identité sur 0 and 1), est le groupe :

${\displaystyle G_{\{0,1\}}=\langle b,c,d,aba,aca,ada\rangle .}$

${\displaystyle G_{\{0,1\}}}$ est un sous-groupe normal d'index 2 dans G et

${\displaystyle G=G_{\{0,1\}}\sqcup aG_{\{0,1\}}.}$

• Un mot réduit représente un élément de ${\displaystyle G_{\{0,1\}}}$ si et seulement s'il contient un nombre pair d'occurrences de a.
• Si w est un mot réduit de G avec un nombre pair positif d'occurrences de a, alors il existe des mots u, v pas nécessairement réduits tels que :

${\displaystyle w=(u,v)\quad }$ et ${\displaystyle \quad {\begin{cases}|u|,|v|\leqslant {\tfrac {1}{2}}|w|&|w|{\text{ impair}}\\|u|,|v|\leqslant {\tfrac {1}{2}}(|w|+1)&|w|{\text{ pair}}\end{cases}}}$

Ceci est parfois appelé la propriété de contraction. Elle joue un rôle majeur dans de nombreuses démonstrations car elle permet d'opérer par récurrence sur la longueur des mots.

• Le problème des mots et le problème de conjugaison sont décidables pour le groupe ${\displaystyle G}$. Ceci s'obtient comme conséquence de la propriété de contraction[14].

Automate de Mealy du groupe de Grigorchuk

L'usage d'automates finis, et notamment d'automates de Mealy, pour la représentation et l’étude du groupe Grigorchuk s'est révélée utile. Les automates considérés n'ont pas d'états initiaux ni terminaux. Les états sont en bijection avec les générateurs du groupe, augmentés de l'automorphisme identité, et les transitions sont les quadruplets ${\displaystyle (p,i,j,q)}$ tels que ${\displaystyle p(ix)=jq(x)}$, où ${\displaystyle i,j\in \{0,1\}}$ et ${\displaystyle p,q\in \{a,b,c,d,e\}}$. On voit qu'il existe un chemin de ${\displaystyle p}$ à ${\displaystyle q}$ d'étiquette d'entrée ${\displaystyle y}$ et d'étiquette de sortie ${\displaystyle z}$ si et seulement si ${\displaystyle p(yx)=zq(x)}$. Par exemple, il y a dans l’automate le chemin

${\displaystyle b\,{\xrightarrow {1|1}}\,c\,{\xrightarrow {0|0}}\,a\,{\xrightarrow {1|0}}\,e\,{\xrightarrow {1|1}}\,e}$

représentant le calcul

${\displaystyle b(1011)=1c(011)=10a(11)=1001}$.

L'étude des automates de Mealy et des groupes et demi-groupes de transformations qu'ils définissent a été développée par Laurent Bartholdi[18]^,[19] ou Thibault Godin, Inès Klimann, Matthieu Picantin[20].

• Théorie géométrique des groupes
• Growth rate of finitely generated groups
• Groupe moyennable
• Monodromie
• Automate de Mealy
• Groupe d'allumeur de réverbères

• Portail de l'informatique théorique
• Portail de l’algèbre