Groupe de Grigorchuk

En mathématiques et notamment en théorie des groupes, le groupe de Grigorchuk, aussi appelé le premier groupe de Grigorchuk, est un groupe finiment engendré construit par Rostislav Grigorchuk et qui fournit le premier exemple d'un groupe finiment engendré de croissance intermédiaire, c'est-à-dire plus rapide qu'un polynôme et plus lent qu'une exponentielle. Le groupe de Grigorchuk est aussi le premier exemple d'un groupe moyennable qui n’est pas élémentairement moyennable, ce qui répond à une question de Mahlon Day posée en 1957[1].

Historique

modifier

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   mais moins vite que   .

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

 ,

  vérifie   Une meilleure borne inférieure   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].

Construction

modifier
 
Arbre binaire  .

Le groupe de Grigorchuk est défini comme un groupe d'automorphismes de l’arbre binaire infini. L'arbre, noté   (on rencontre aussi la notation   ou  ), est vu comme l'ensemble   des mots finis sur l'alphabet  , y compris le mot vide   (ou  ) qui est la racine de l’arbre. Pour tout nœud   de l’arbre  , le mot   est le fils gauche de   et le mot   est le fils droit de   dans  . Le groupe   peut alors être vu comme le groupe de toutes les bijections   de   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   est préfixe de  , alors   est préfixe de  .

Le groupe de Grigorchuk   est le sous-groupe du groupe d'automorphisme   engendré par quatre éléments particuliers de  , notés  , soit

 ,

où les automorphismes   sont définis par les relations suivantes :

 

Dans ces formules,   est un mot de  , y compris le mot vide. Pour  , les formules se réduisent à

 

puisque l'image du mot vide par un automorphisme est toujours le mot vide. Seule l'automorphisme   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   donne

 .

L'ensemble des mots de   s'écrit comme réunion disjointe

 .

Les sommets de   dénotés par   et   constituent respectivement le sous-arbre gauche et le sous-arbre droit de  , notés   (parfois aussi  ) et   (ou  ). On a alors

 ,

en d'autres termes   échange les éléments des sous-arbres gauche et droit niveau par niveau. Les actions de   et   peuvent s'écrire aussi sous la forme :

 

  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 :

 .

Relations

modifier

Plusieurs formules relient les éléments. Notamment la conjugaison par   permet l'échange des composants :

 

La vérification est facile, ainsi

 .

Les éléments  , et   sont des involutions ; la preuve est directe pour  , et par récurrence sur la longueur des mots pour les autres :

 

Les éléments   commutent deux-à-deux et leur produit est égal au troisième :

 [3]

de sorte que   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   est aussi engendré par trois éléments, à savoir   et deux quelconques parmi  . Ainsi,  .

Mot réduit : Tout élément de   s'écrit comme produit d'éléments de sorte qu'entre deux  , 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   est  [14].

Propriétés

modifier

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   est infini[3].
  • Le groupe   est résiduellement fini[3]. Soit   le morphisme qui envoie un élément de   sur sa restriction à l'arbre fini   de hauteur  . Les groupes   sont finis et pour tout   non trivial, il existe un   tel que  .
  • Le groupe   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   est de croissance intermédiaire[3].
  • Le groupe   est moyennable mais n'est pas un groupe élémentairement moyennable (en)[3].
  • Le groupe   est juste infini (en), c'est-à-dire qu'il est infini mais que tous ses groupes quotient sont finis.
  • Le groupe   a la congruence subgroup property : un sous-groupe H est d'indice fini dans G si et seulement si   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  , décide si   est un élément du sous-groupe engendré par  [15].
  • Le groupe   est séparable (en), c'est-à-dire tout sous-groupe finiment engendré est fermé dans la topologie profinie sur  [15]
  • Tout sous-groupe maximal de   est d'indice fini dans  [16].
  • Le groupe   est finiment engendré mais n’a pas de présentation finie[3],[17].

Décidabilité

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

 

  est un sous-groupe normal d'index 2 dans G et

 

  • Un mot réduit représente un élément de   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 :
  et  
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  . Ceci s'obtient comme conséquence de la propriété de contraction[14].

Automates

modifier
 
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   tels que  , où   et  . On voit qu'il existe un chemin de   à   d'étiquette d'entrée   et d'étiquette de sortie   si et seulement si  . Par exemple, il y a dans l’automate le chemin

 

représentant le calcul

 .

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].

Notes et références

modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Grigorchuk group » (voir la liste des auteurs).
  1. Mahlon M. Day. Amenable semigroups. Illinois Journal of Mathematics, vol. 1 (1957), p. 509–544.
  2. a et b Grigorchuk 1980.
  3. a b c d e f et g Grigorchuk 1984.
  4. John Milnor, Problem No. 5603, American Mathematical Monthly, vol. 75 (1968), p. 685–686.
  5. Volodymyr Nekrashevych. Self-similar groups. Mathematical Surveys and Monographs, 117. American Mathematical Society, Providence, RI, 2005. (ISBN 0-8218-3831-8).
  6. Laurent Bartholdi. Lower bounds on the growth of a group acting on the binary rooted tree. International Journal of Algebra and Computation, vol. 11 (2001), no. 1, p. 73–88.
  7. Yu. G. Leonov, On a lower bound for the growth of a 3-generator 2-group. Matematicheskii Sbornik, vol. 192 (2001), no. 11, p. 77–92; translation in: Sbornik Mathematics. vol. 192 (2001), no. 11–12, p. 1661–1676.
  8. John Milnor. Growth of finitely generated solvable groups. Journal of Differential Geometry. vol. 2 (1968), p. 447–449.
  9. Joseph Rosenblatt. Invariant Measures and Growth Conditions, Transactions of the American Mathematical Society, vol. 193 (1974), p. 33–53.
  10. Roman Muchnik, and Igor Pak. On growth of Grigorchuk groups. International Journal of Algebra and Computation, vol. 11 (2001), no. 1, p. 1–17.
  11. Laurent Bartholdi. The growth of Grigorchuk's torsion group. International Mathematics Research Notices, 1998, no. 20, p. 1049–1054.
  12. Anna Erschler. Critical constants for recurrence of random walks on G-spaces. Université de Grenoble. Annales de l'Institut Fourier, vol. 55 (2005), no. 2, p. 493–509.
  13. Jérémie Brieussel, Croissance et moyennabilité de certains groupes d’automorphismes d’un arbreenraciné, Thèse de doctorat, Université Denis Diderot Paris VII, 2008.
  14. a b et c Pierre de la Harpe 2000.
  15. a et b Grigorchuk et Wilson 2003.
  16. Pervova 2000.
  17. Lysenok 1985.
  18. Bartholdi, Reznykov et Sushchansky 2006
  19. Bartholdi 2017.
  20. Godin, Klimann et Picantin 2015.

Bibliographie

modifier
  • Laurent Bartholdi, « Decidability problems in automaton semigroups », preprint,‎ (arXiv 1705.04598v1)
  • Laurent Bartholdi, « The growth of Grigorchuk's torsion group », International Mathematics Research Notices, Oxford Academic, no 20,‎ , p. 1049-1054 (DOI 10.1155/S1073792898000622, arXiv math/0012108v1).
  • (en) L. Bartholdi, I.I. Reznykov et V.I. Sushchansky, « The smallest Mealy automaton of intermediate growth », Journal of Algebra, vol. 295, no 2,‎ , p. 387–414 (ISSN 0021-8693, DOI 10.1016/j.jalgebra.2004.08.040, arXiv math/0407312v1)
  • Tullio Ceccherini-Silberstein, Antonio Machì et Fabio Scarabotti, « The Grigorchuk group of intermediate growth », Rendiconti del Circolo Matematico di Palermo, Circolo Matematico di Palermo, 2e série, vol. 50, no 1,‎ , p. 67-102
  • Thibault Godin, Ines Klimann et Matthieu Picantin, « On torsion-free semigroups generated by invertible reversible Mealy automata », LATA 2015, Springer,‎ , p. 328–339 (DOI 10.1007/978-3-319-15579-1_25, MR 3344813, arXiv abs/1410.4488)
  • Rostislav I. Grigorchuk et Igor Pak, « Groups of intermediate growth: an introduction », L´Enseignement Mathématique, vol. 54,‎ , p. 251-272 (arXiv math/0607384, lire en ligne)
  • Rostislav I. Grigorchuk, « Complete growth functions of hyperbolic groups », Invent. Math., vol. 130, no 1,‎ , p. 159–188.
  • Rostislav I. Grigorchuk, « On growth in group theory », Proceedings of the International Congress of Mathematicians, Kyoto, Math. Soc. Japon, vol. I, II (Kyoto, 1990),‎ , p. 325–338.
  • Rostislav I. Grigorchuk, « Degrees of growth of finitely generated groups and the theory of invariant means. », Izv. Akad. Nauk SSSR Ser. Mat., vol. 48, no 5,‎ , p. 939–985.
  • Rostislav I. Grigorchuk, « On the Milnor problem of group growth », Dokl. Akad. Nauk SSSR, vol. 271, no 1,‎ , p. 30–33.
  • Rostislav I. Grigorchuk, « On Burnside's problem on periodic groups », Funktsional. Anal. i Prilozheniya, vol. 14, no 1,‎ , p. 53–54 (MR 0565099).
  • Rostislav I. Grigorchuk et J. S. Wilson, « A structural property concerning abstract commensurability of subgroups », Journal of the London Mathematical Society (2), vol. 68, no 3,‎ , p. 671–682 (lire en ligne).
  • (en) Pierre de la Harpe, Topics in geometric group theory, Chicago, University of Chicago Press, coll. « Chicago Lectures in Mathematics », , 310 p. (ISBN 0-226-31719-6, lire en ligne)
  • I. G. Lysenok, « A set of defining relations for the Grigorchuk group », Mathematical Notes of the Academy of Sciences of the USSR, vol. 38, no 4,‎ , p. 784–792 (DOI 10.1007/BF01158402).
  • (ru) Yu. G. Leonov, « On a lower bound for the growth function of the Grigorchuk group », Matematicheskie Zametki, vol. 67, no 3,‎ , p. 475-477 — Traduction dans Mathematical Notes, vol. 67, no 3-4 (2000) p. 403-405.
  • (ru) Ekaterina L. Pervova, « Everywhere dense subgroups of a group of tree automorphisms », Trudy Matematicheskogo Instituta Imeni V. A. Steklova, vol. 231,‎ , p. 356–367 — Traduction : Proceedings of the Steklov Institute of Mathematics, vol. 231, no 4, 2000, p. 339–350.
  • Roman Muchnik et Igor Pak, « Percolation on Grigorchuk groups », Communications in Algebra, vol. 29, no 2,‎ , p. 661-671.

Articles liés

modifier