ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Demi-groupe libre, groupe libre, présentation d'un groupe        
    
Structure de groupe, sous-groupes | Groupes particuliers & groupes finis

Le concept de groupe libre est apparu implicitement en 1882 avec les travaux du mathématicien allemand Walther von Dyck. On parlait alors de théorie combinatoire des groupes et il semble être le premier à avoir défini un groupe (à un isomorphisme près) au moyen d'un système générateur et de relations de définition : on parle de présentation d'un groupe (à distinguer de la représentation d'un groupe). Dans les années 1920, le mathématicien danois Jakob Nielsen s'empara du sujet en définissant le concept de groupe libre (Die Isomorphismengruppe der freien Gruppen, réf.2). Il en donne là une première et simple définition :

Un groupe est dit simple lorsqu'il peut être défini par un système générateur d'éléments indépendants

et ce, dans le but d'étudier plus facilement les groupes infinis dénombrables. Ces nouveaux outils voient aujourd'hui leur application en algorithmique et en théorie de l'information.

  Schützenberger , P. Novikov

  Walther F. A. von Dyck : mathématicien allemand (1856-1934) qui fut un étudiant de Klein à Munich, sa ville natale où il enseignera durant la majeure partie de sa carrière. Il contribua grandement à la théorie des groupes abstraits. Il fut également un pionnier en matière d'algorithmique et théorie des langages.

Jakob Nielsen (1890-1959), mathématicien danois, professeur à Copenhague. Il étudia à l'université de Kiel et obtint son doctorat (Réseaux de courbes sur les surfaces, 1913) sous la direction de Dehn. Ses travaux ont porté sur théorie des groupes, la topologie algébrique (appliquée en particulier à celle des surfaces). Il fut le premier conférencier du premier congrès international des mathématiciens qui se tint à Oslo en 1936.

  Turing , Babbage , Post    |   Fields, Les médaillés Fields depuis 1936

1. Le concept de demi-groupe libre :    

Soit Λ un ensemble fini appelé alphabet. Ses éléments sont appelés lettres (ou caractères). Appelons mot toute écriture juxtaposée a1a2...ap, dans cet ordre, d'un p-uplet (a1,a2, ...,ap) d'éléments de Λ, p quelconque dans N. L'entier p est la longueur du mot. On définit le mot vide ϖ comme étant l'unique mot de longueur 0 : il ne contient aucun caractère. Notons Ω l'ensemble des mots.

Le mot vide est à distinguer du caractère d'espacement (celui qui sépare les mots de cette parenthèse) dont la longueur est 1 et qui fait partie de l'ensemble des caractères de notre langage utilisant l'alphabet latin augmenté de tous les signes de ponctuation y compris l'espacement (signes typographiques). En informatique, un mot correspond à une chaîne de caractères (string) souvent écrite entre guillemets : "chat", "ton", "" (chaîne vide), " " (espacement).  JavaScript et les chaînes

Munissons Ω de la concaténation (du latin cum = ensemble et catena = chaîne : écrire ensemble à la chaîne). C'est une loi de composition interne dans Ω définie par :         

Si A = a1a2...ap et B = b1b2...bq sont deux mots de Ω, alors A B est le mot a1a2...apb1b2...bq

La loi est associative dans Ω et le mot vide ϖ en est l'élément neutre : muni de la concaténation, Ω est donc un demi-groupe (monoïde) unifère. On parle de demi-groupe libre de base Λ ou engendré par Λ.

libre pour exprimer, à l'instar des systèmes libres d'un espace vectoriel, que tout mot s'écrit d'une façon unique au moyen des lettres de L.

2. Construction d'un groupe libre :    

Soit Λ' un second alphabet de même cardinal que Λ. à tout élément α de Λ, on peut faire correspondre bijectivement un élément α' de Λ'. Posons conventionnellement α α' = α' α = ϖ. C'est dire que les mots αα' et α'α sont vides et que α' est le symétrique de α pour la loi de concaténation.

On a écrit ci-dessus le symétrique car la loi de concaténation étant associative, un symétrique, s'il existe, est unique.

Notons alors l'ensemble des mots écrits au moyen de l'alphabet = ΛΛ'. Un mot de peut avoir plusieurs écritures du fait de la présence des symétriques.

On voit que tout mot A de peut être réduit à une unique écriture de longueur minimale. Notons A* l'écriture minimale de A et soit la relation binaire définie dans par :

A B A* = B*

est une relation d'équivalence et on peut munir le demi-groupe quotient / des classes d'équivalence de la loi de concaténation induite par celle de : on obtient ainsi un groupe, dit groupe libre engendré par . Notons ce groupe . Le cardinal de (éventuellement infini) est le rang du groupe libre.

Comme dans tout groupe, le symétrique dans d'un mot comme ab est b'a' (et non pas a'b'), celui ab'c est c'ba', ... : d'une façon générale, le symétrique d'un mot de longueur p sera le mot de même longueur constitué, en ordre inverse, des symétriques des lettres qui le composent.

Exemple élémentaire : 

On peut construire Z de la manière suivante : considérons un alphabet réduit à un unique élément abstrait u et étudions  le groupe libre u. Ses éléments sont les mots composés de u et de u' qui se réduisent nécessairement à des formes uuu..u ou u'u'u'...u' car uu' = ϖ. Convenons de noter n* le composé de n éléments u (nN, n 2) et -n* le composé de n éléments u'. Décidons aussi de rebaptiser 1* notre générateur u et 0* le mot vide ϖ, neutre pour la concaténation.

On l'a compris, le groupe libre u = 1* muni de sa loi de concaténation s'interprète comme (Z,+), c'est à dire n'est autre que Z à un isomorphisme près : on peut retirer les étoiles et remplacer la concaténation par l'addition +... Groupe libre de rang 1 : c'est un groupe monogène engendré par l'unité.

Groupe libre sur un ensemble :    

Etant donné un groupe (G,*) et un sous-ensemble non vide de G. S'il s'avère que tout élément de G peut s'écrire de  manière unique comme un mot composé d'éléments de , on dit que G est libre sur .

Sous-groupe engendré par une partie d'un groupe :

Théorème 1 (Nielsen,1921) :     

Tout sous-groupe H d'un groupe libre G est libre

Théorème 2 :   

Entre les groupes, quels qu'ils soient, et les groupes libres, on a ce résultat remarquable :

Tout groupe est isomorphe à un groupe quotient d'un groupe libre.

Preuve (empruntée à Paul Dubreil, réf. 5) : Soit (G,•) un groupe d'élément neutre e et SG un système générateurs de G. Construisons un groupe libre engendré par un ensemble SL en associant bijectivement un élément de SLà un élément de SG. Notons φ la bijection en question de SL sur SG. Tout élément de L est un composé fini de la forme a = a1α1 a2α2... apαp. (un élément comme x3 désigne le composé x x x). Posons alors :

Φ(a) = φ(a1)α1 φ(a2)α2... φ(ap)αp

On définit ainsi une application Φ surjective de L sur G puisque φ est surjective dont la restriction à SL est φ. De plus, si a et b sont dans L, a = a1α1 a2α2... apαp  et b = b1β1 b2β2... bqβq, alors :

 Φ(a b) = Φ(a1α1 a2α2... apαp b1β1 b2β2... bqβq) = φ(a1)α1 ... φ(ap)αp φ(b1)β1 ... φ(bq)βq = Φ(a) Φ(b)

Φ réalise donc un homomorphisme surjectif de L sur G et l'application du théorème 4 relatif à l'image homomorphe d'un groupe montre que G est isomorphe au groupe quotient L/N, N désignant le noyau de Φ, ensemble des éléments a de L tels que Φ(a) = e.

3. Présentation d'un groupe :   

Avec les notations précédentes, pour tout n du noyau de Φ appliquant L sur G, on a Φ(n) = e. Notons S un système générateur minimal (irréductible) de N et n = n1α1 n2α2... npαp, niS. En posant φ(ni) = gi, on a :

g1α1 g2α2...gpαp = e

c'est une relation entre les générateurs de S, donc de G. L'ensemble R de ces relations lorsque n décrit N est appelé système de relations de définition (ou relateurs) de G. Lorsque  R et S sont de cardinal fini on dit que G est de présentation finie ou que g est de type fini.

Théorème (von Dyck) :   

à un isomorphisme près, un ensemble de générateurs S et un système R de relations entre les éléments de S définissent un unique groupe noté S;R ou <S|R> que l'on dit être présenté par S et R.

De plus, étant donnés deux groupes S;R et S';R', si R' R, alors S';R' est isomorphe à un groupe quotient de S;R.

Le théorème d'isomorphie précédent et la notion de présentation d'un groupe trouvent leur intérêt dans le cadre de l'étude du problème des mots :

             Le problème des mots (Word problem) :


 Pour en savoir plus :

  1. Groupes libres :
     a/ Leçons d'algèbre moderne, par Paul Dubreil et Marie-Louise Dubreil-Jacotin - Éd. Dunod, Paris -1961
     b/ Groupes libres et présentation de groupes, par Kathryn Hess Bellwald (École polytechnique de Lausanne : http://sma.epfl.ch/~hessbell/topo_alg/PresGrpe.pdf
    c/ Éléments de mathématique, Algèbre, Ch. 1, N. Bourbaki.
  2. L'article de Nielsen définissant les groupes libres (en allemand) in Math. Annalen, 1924 :
    Die Isomorphismengruppe der freien Gruppen, sur le site GDZ de textes numérisés de Göttingen :
    http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PID=GDZPPN002269813&physid=PHYS_0175
  3. Generating sets of certain automorphisme groups par chander K. Gupta (univ. São Paulo):
    http://www.revistas.usp.br/resenhasimeusp/article/viewFile/74819/78389
  4. Génération d'une présentation de groupe finie (algorithmique) sur le site GAP (Groups, Algorithms, Programming) :
    http://www.gap-system.org/Manuals/doc/ref/chap47.html
  5. Une application inattendue : le semi-groupe libre des carrés magiques, par Lionel Cozar, univ. Bordeaux :
    http://archive.numdam.org/article/JTNB_1996__8_1_243_0.pdf

Les carrés magiques sur ChronoMath :


© Serge Mehl - www.chronomath.com