Algèbre et géomét!

de la rééc!ture

Yv" Lafont

Ecole Jeun" Chercheurs en Informatique Ma%ématique

CIRM 2'8

Leçon 1. Rééc!ture de mots

Présentations de monoïd"

Présentation #andard

Réductions et dé!vations

Termina$on et confluence

Complétion de Knu%-Ben&x

Problèm" de déc$ion
2
 Présentations de monoïdes
générateurs relations monoïde
a a2 = 1 !2 (entiers modulo 2)
a a2 = a "2 (idempotent libre)
a, a# aa# = 1, a#a = 1 F1 = ! (groupe libre)
a, b ab = ba "2 = " $ "
aa# = 1, a#a = 1,
a, a#, b, b# F2 = ! ! ! (groupe libre)
bb# = 1, b#b = 1
a2 = 1, b2 = 1,
a, b S3 (groupe symétrique)
aba = bab
a, b aba = bab B3+ (tresses positives)

Exercice : Donner une présentation pour !2 et pour B3.

3

Présentation standard
Remarque : Tout monoïde (fini) a une présentation (finie).

Soit M un monoïde quelconque.

présentation générateurs relations

axay = axy,
standard ax (x M)
a1 = 1
axay = axy (xy % 1),
standard réduite ax (x M, x % 1)
axay = 1 (xy = 1)

Exercice : Expliciter la présentation standard

et la présentation standard réduite de !2.

4
 Réductions et dérivations
notion notation définition
alphabet & ensemble de symboles
mot x suite de symboles x &*
règle ':x!y couple ' = (x,y) &* $ &*
réduction avec ' : x ! y
u'v : uxv !R uyv
élémentaire dans R &* $ &*
réduction x !*R y chaîne x !R ! !R y
dérivation
x Ry x !R y ou y !R x
élémentaire
dérivation x *R y chaîne x R ! R y

Définition : Une présentation de M est la donnée d#un

alphabet & et de R &* $ &* tels que M &*/ *R.
5

Terminaison
Définition : Un ordre de terminaison sur &*
est un bon ordre compatible avec le produit.
Théorème : Pour une présentation (&,R),
les conditions suivantes sont équivalentes :
Il n#existe pas de réduction infinie :
x0 !R x1 !R ! !R xn !R xn+1 !R !

Il existe un ordre de terminaison sur &* tel que

x > y pour chaque règle ' : x ! y dans R.

(&,R) satisfait le principe de récurrence noetherienne :

( x ( y x !R y P(y)) P(x)) x P(x)

On dit alors que la présentation (&,R) est noetherienne.

6
 Confluence
Théorème : Pour une présentation noetherienne,
les quatre conditions suivantes sont équivalentes :
Unicité de la Church- Confluence Confluence
forme réduite Rosser (globale) locale
x *z x x
y * *
* * y z y z
y = z
* t *
y et z réduits * t * * t *
Démonstration : 1 2 3 4 (évident)
x 4 1 (par récurrence noetherienne)
y z
Exercice : Les règles suivantes vérifient la
* t * confluence locale, mais pas la confluence :
* *u = w*= v* * a!b, b!a, a!a#, b!b#.
7

Confluence des pics critiques

Théorème : Pour vérifier la confluence locale,
il suffit de tester la confluence des pics critiques.
A B C
Exemple : aa ! 1, bb ! 1, aba ! bab
aaa bbb
Aa aA Bb bB
a = a b = b

aaba abaa ababa

aC Ca Cba abC
abab baba babba abbab
Aba Cb bC abA baBa aBab
babb bbab baa aab
baB Bab bA b Ab
ba ab

Exercice : La présentation standard est confluente.

8
 Présentations convergentes
présentation propriétés
convergente terminaison + confluence
générateurs réduits
réduite + membres gauches minimaux
+ membres droits réduits
orthogonale pas de pics critiques

Remarque : Toute présentation convergente (finie) est

équivalente à une présentation convergente réduite (finie).
Exercice : Toute présentation orthogonale est confluente.
Exercice : Les groupes (non triviaux) n#ont pas
de présentation convergente orthogonale.
9

Complétion de Knuth-Bendix
Remarque : Il existe un ordre de terminaison total sur &*.

Algorithme : Réduire les 2 côtés de chaque pic critique :

x • si u = v, le pic est confluent
y z • si u > v, ajouter la règle u ! v
* * • si u < v, ajouter la règle v ! u
u v
• éliminer les règles superflues
Exercice : Appliquer cet algorithme aux règles suivantes :
aa# ! 1, a#a ! 1, bb# ! 1, b#b ! 1, ba ! ab
Exercice : Appliquer cet algorithme à la règle bab ! aba.
Idem en ajoutant le générateur c avec la règle ab ! c.
10
 Problèmes de décision
Soit (&,R) un présentation finie.
problème données question
équivalence x, y &* x *R y ?
unité (par dérivation) x &* x *R 1 ?
unité (par réduction) x &* x !*R 1 ?
Remarque : Dans un groupe, x = y xy-1 = 1.
Remarque : Dans le cas d#une présentation
convergente, ces problèmes sont décidables.
Exercice : Il existe une présentation orthogonale telle que ces
problèmes soient indécidables. [Coder le problème de l’arrêt.]
Théorème (Novikov-Boone) : Il existe un groupe tel que
le problème de l#unité (par dérivation) soit indécidable.
11

Leçon 2. Homologie d" monoïd"

(éo!e d" gr)p" abeliens

Complex" de chaîn"

Homologie d" complex"

Homologie d" monoïd"

Résolutions libr"

Homologie d" réductions

12
 Théorie des groupes abeliens
1. Un sous-groupe de ! est de la forme :
0 ou k! ( !) avec k > 0.

2. Un groupe abelien à 1 générateur est de la forme :

! ou !k = !/k! avec k > 0.

3. Un sous-groupe de !n = ! ! ! est isomorphe à :

!p avec p ( n.

4. Un groupe abelien à n générateurs est de la forme :

!p !k1 ! !kq avec p + q ( n.
! classification des groupes abeliens (de type fini)

Exercice : Comparer !2 !2 avec !4, et !2 !3 avec !6.

13

Complexes de chaînes
Définition : Un complexe de chaînes est une suite infinie
*0 *1 *n *n+1
C : C0 " C1 " C2 " ! " Cn " Cn+1 " Cn+2 " !
de groupes abeliens, telle que *n *n+1 = 0 pour tout n.

Exemple : Le triangle (plein) )2

Q Q a b
a b *0 *1 )
" "
P c R P R c
* 0a = Q - P * 0b = R - Q * 0c = R - P * 1) = a + b - c
*0 3 *1
)2 : ! " ! " ! " 0 " 0 " !
3 *0 *1 = 0

Exercice : Décrire les complexes de chaînes associés

au triangle vide *)2, au carré "2, et au tétraèdre )3.
14
 Morphismes et homotopies
Définition : morphisme de complexes f : C ! D
*0 *1 *n *n+1
C0 " C1 " C2 " ! " Cn " Cn+1 " Cn+2 " !
#f0 #f1 #f2 #fn #fn+1 #fn+2 fn *n = *n fn+1
D0 " D1 " D2 " ! " Dn " Dn+1 " Dn+2 " !
*0 *1 *n *n+1
Définition : homotopie entre deux morphismes f,g : C ! D
*0 *1 *n *n+1
C0 " C1 " C2 " ! " Cn " Cn+1 " Cn+2 " !
## $h0##$h1 ## ## $hn ## $hn+1##
D0 " D1 " D2 " ! " Dn " Dn+1 " Dn+2 " !
*0 *1 *n *n+1
*0 h0 = g0 - f0 f0 x h0 *0 + *1 h1 = g1 - f1 f0 x f1 u f0 y
h0 x u h0 x h1 u h0 y
x x y
g0 x g0 x g1 u g0 y
plus généralement : hn *n + *n+1 hn+1 = gn+1 - fn+1
15

Homologie des complexes

*0 *1 *n *n+1
Soit C : C0 " C1 " C2 " ! " Cn " Cn+1 " Cn+2 " !
Remarque : *n *n+1 = 0 im *n+1 ker *n
*1 *0
" " 0
! tout bord est un cycle

Définition : C est exact si im *n+1 = ker *n pour tout n.

! tout cycle est un bord

Exemples : Le complexe )2 est exact, mais pas *)2.

Définition : Les groupes d’homologie de C sont
H0(C) = C0 / im *0 et Hn+1(C) = ker *n / im *n+1.
16
 Homologie des complexes
L#homologie des complexes est fonctorielle :
• f : C ! D donne Hn(f) : Hn(C) ! Hn(D) ;
• Hn(g f) = Hn(g) Hn(f) et Hn(id) = id.
Exercice : Si f,g : C ! D sont homotopes, alors Hn(f) = Hn(g).

Définition : C et D sont homotopiquement équivalents s#il

existe des morphismes f : C ! D et g : D ! C tels que :
• g f et idC sont homotopes; g f C f D f g
• f g et idD sont homotopes. g

Remarque : Dans ce cas, C et D ont la même homologie.

Exercice : )2, "2, )3 sont homotopiquement équivalents
au point )0 : ! " 0 " 0 " !, mais pas à *)2.
17

Corrigé de l!exercice
Le triangle )2 est homotopiquement équivalent au point )0 :
Q * 0a = Q - P
f a b * 0b = R - Q
gf = P fg
g P R * 0c = R - P
)0 c
* 1) = a + b - c
)2
f0P = P g0P = g0Q = g0R = P g1a = g1b = g1c = 0 g2) = 0
*0 3 *1 *0 h0 = id0 - f0 g0
!3 "! "!"0
## $h0##$h1 ## h0 *0 + *1 h1 = id1 - f1 g1 = id1
!3 " !3 " ! " 0 h1 *1 + *2 h2 = id2 - f2 g2 = id2
*0 *1
h0P = 0 h0Q = a h0R = c h1a = h1c = 0 h1b = ) h2) = 0
Le triangle vide n#est pas homotopiquement équivalent à )0 :
H1(*)2) = ! H1()0) = 0
18
 Homologie des monoïdes
Définition : Complexe canonique C associé à un monoïde M :
• Cn est le groupe abelien libre engendré par l#ensemble Mn ;
• les générateurs de Cn sont notés [x1 ! xn] ;
• les *n : Cn+1 ! Cn sont donnés par les formules suivantes :
*0[x] = [] - [] (= 0) x
x y
*1[x y] = [y] - [xy] + [x]
xy
*2[x y z] = [y z] - [xy z] + [x yz] - [x y]
*3[x y z t] = [y z t] - [xy z t] + [x yz t] - [x y zt] + [x y z]
!
Exercice : Ecrire la formule générale pour *n[x1 ! xn+1].
Définition : L#homologie de M est celle du complexe C.
19

Homologie des monoïdes

Définition : Complexe canonique réduit + associé à M :
• +n est le groupe abelien libre engendré par (M \ {1})n ;
• les *n sont définis par les mêmes formules, en posant :
[x1 ! xi-1 1 xi+1 ! xn] = 0.

Exercice : Calculer les complexes C et + pour !2

et montrer qu#ils définissent la même homologie.
En fait, C et + ont toujours la même homologie.
Exercice : Construire une homotopie entre
id : C ! C et le morphisme p : C ! C défini par
p[x1 ! xn] = [x1 ! xn] si x1,…,xn % 1, 0 sinon.

Peut-on calculer l#homologie de M avec d#autres complexes ?

20
 "M-modules
Définition : !M est l#anneau de M, c#est-à-dire le groupe
abelien libre engendré par l#ensemble M, muni du produit
(&x M px x)(&y M qy y) = &x,y M pxqy xy.

Remarque : Un !M-module U est donné par une

action additive de M sur un groupe abelien U :
xy#u = x#(y#u), 1#u = u, x#(u + v) = x#u + x#v.
Un morphisme de !M-module f : U ! V est alors un
morphisme de groupes compatible avec cette action :
f (x#u) = x#f u.
Définition : Le !M-module libre !M#S engendré par
l#ensemble S est le groupe abelien libre engendré par
l#ensemble M#S = {x#s ; x M, s S}, muni de l#action
x#(&y M,s S py y#s) = &y M,s S py xy#s.
21

Résolutions libres
Définition : Une résolution libre est un complexe exact
- ,0 ,1 ,n ,n+1
! " C0 " C1 " C2 " ! " Cn " Cn+1 " Cn+2 " !
qui définit un complexe augmenté de !M-modules libres.
En trivialisant l’action de M, on obtient un complexe C˜.
Théorème : L#homologie du complexe C˜ ne dépend pas
du choix de la résolution libre : C#est l#homologie de M.
Exemple : Le complexe canonique s#obtient en trivialisant
la bar-résolution, qui est définie de la façon suivante :
,0[x] = x#[] - []
,1[x y] = x#[y] - [xy] + [x]
,2[x y z] = x#[y z] - [xy z] + [x yz] - [x y]
!
22
 Homologie des réductions
Toute présentation convergente (&,R) définit un complexe :
*0 *1 *2
! " !.& " !.R " !.P " ! avec *0 = 0
A B C
Exemple : aa ! 1, bb ! 1, aba ! bab *1A = -2a
aaa bbb *1B = -2b
Aa aA Bb bB * 1C = b - a
X
a = a Y
b = b

aaba abaa ababa

aC Ca Cba abC
abab baba babba abbab
Aba U Cb bC V abA baBa W aBab
babb bbab baa aab
ba baB Bab
ab
bA b Ab

*2X = *2Y = 0 *2U = 2C + B - A *2V = A - B - 2C * 2W = 0

23

Homologie des réductions

Théorème (Anick, Squier, Kobayashi) : L#homologie de
ce complexe est l#homologie du monoïde M = &*/ *R.

Corollaire : Si M a une présentation convergente finie,

alors le groupe abelien H3(M) est de type fini.

Application : Il existe un monoïde M tel que :

• M a une présentation finie (&,R) ;
• le problème des mots pour M est décidable ;
• M n#a aucune présentation convergente finie.
Il suffit de montrer que le groupe H3(M) n#est pas de type fini.
24