ELIMINATION DE GENERATEURS

DANS LES STRUCTURES

PARTIELLEMENT COMMUTATIVES

par

Gérard Duchamp

LITP/LIR, Institut Blaise Pascal Université Paris 7 2, place Jussieu, 75251 Paris Cedex 05

Introduction

Les procédés d’élimination se retrouvent en algèbre dans de nombreuses structures différentes. Eliminer un générateur x_{n} c’est typiquement écrire, pour une structure ST RUCT (selon une formulation à la Zeilberger [Z]) :

ST RUCT ⟨x_{1}, x_{2}, …, x_{n}⟩ ≅ NICE⟨x_{1}, x_{2}, …, x_{n}⟩ ⋄ ST RUCT_{1}⟨x_{1}, x_{2}, …, x_{n−1}⟩,

où NICE et ST RUCT_{1} désignent des structures algébriques engendrées par les générateurs x_{1}. Le losange, selon les cas, est un produit tensoriel, un produit semidirect ou une simple factorisation. On peut ainsi écrire pour le groupe symétrique 𝔖_{n} et le groupe des tresses pures P_{n} [Bi] :

𝔖_{n} ≅ ℤ/nℤ ⋄ 𝔖_{n−1} et P_{n} ≅ F_{n−1} ⋄ P_{n−1}.

Dans la première de ces factorisations le losange est un simple produit et la décomposition itérée peut servir à montrer que le groupe symétrique est un groupe de Coxeter ou bien à donner une base du groupe symétrique particulièrement bien adaptée au développement du projecteur de Dynkin [D1], dans la seconde c’est un produit semidirect et F_{n−1} est le groupe libre sur n − 1 générateurs.

Les structures libres se prêtent bien à l’élimination de générateurs. Par exemple, la formule k[X_{1}, X_{2}, …, X_{n}] ≅ k[X_{1}] ⊗_{k} k[X_{2}, …, X_{n}] qui est si utile en algèbre commutative, provient de l’élimination de X_{1} dans le monoïde libre commutatif ℕ^{{X_{1},X_{2},...,X_{n}}}. De même, lorsqu’on partage un alphabet donné A en A = B + Z on peut écrire, por le monoïde libre, le groupe libre et l’algèbre de Lie libre :

A^{∗} = (B^{∗}Z)^{∗}B^{∗}, F (A) ≅ F (F (B)Z) ⋄ F (B), L(A) ≅ L((B^{∗}Z)) ⋄ L(B).

Les deux derniers losanges sont des produits semi-directs et constituent l’élimination de M. Lazard [Laz] à proprement parler. Ces décompositions sont étendues au cas partiellement commutatif et nous devons maintenant en dire quelques mots.

Les structures partiellement commutatives sont intermédiaires entre les structures commutatives et non commutatives libres. On a, par exemple, pour un alphabet donné A, le tableau :

commutatif  noncommutatif
monoïde  ℕ^{A}  A^{∗}
groupe  ℤ^{A}  F (A)
k-alg. de Lie  k^{A}  L_{k}(A)
k-alg. assoc.  k[A]  k⟨A⟩

(polynômes)

La première structure partiellement commutative présentée telle est certainement le monoïde de réarrangements que P. Cartier et D. Foata ont défini en 1969 à des fins combinatoires, statistiques et probabilistes [CF].

Depuis, l’histoire de ces structures est à lire parallèlement sur les trois pistes que sont l’algèbre, la combinatoire (algébrique et énumérative) et la théorie des langages.

Pour ce qui est de la combinatoire, signalons que le monoïde partiellement commutatif libre a reçu une représentation géométrique suggestive en terms d’empilements [Vi] qui se prête bien à l’adjonction de structures supplémentaires sur l’alphabet des indéterminées. Cette représentation, essentiellement équivalente à la notion de monoïde partiellement commutatif ([Vi, prop 4.5]), a déjà fait ses preuves dans la résolution de plusieurs problèmes combinatoires tels que les hexagones durs de Baxter, les polynômes orthogonaux et l’énumération des tresses simples.

En théorie des langages, le monoïde partiellement commutatif a été essentiellement employé comme modèle du paralléllisme. En effet, de même qu’une suite d’actions a_{1}, a_{2}, …, a_{n} peut se représenter par le mot w = a_{1}a_{2} ⋯ a_{n} et la juxtaposition (dans le temps) de deux telles suites, par leur concaténation dans le monoïde libre, de même des actions dont certaines se traitent “en paralléle” ou “indépendamment” peuvent être représentées par des éléments du monoïde partiellement commutatif (ou “traces”) et leur composition. Cette théorie des langages, toute jeune, s’interesse donc à ce qui est parfois appellé “langage trace”. On peut citer les travaux fondateurs de Arnold, Cori, Mazurkiewicz, Perrin, Métivier, Olchanski et Zielonka [Du][CP][HK].

Dans une note à T.C.S., Jean-Yves Thibon [T] montre que l’algèbre des polynômes partiellement commutatifs (c’est à dire l’algèbre du monoïde partiellement commutatif) est intègre dès que l’anneau des coefficients l’est. Ce fait est relié à la propriété que k⟨A, ϑ⟩ est l’algèbre enveloppante de L_{k}(A, ϑ); mais la liberté de k⟨A, ϑ⟩ (c’est à dire l’existence de bases) n’implique nullement celle de L_{k}(A, ϑ) ni la construction de bases combinatoires de celle-ci. La résolution de cette question d’apparence purement esthétique devait d’ailleurs (en 1990) avoir quelque utilité en théorie des langages [DK2] et [Va]. En fait, c’est une version partiellement commutative du procédé d’élemination de M. Lazard qui perment une démonstration constructive de l’existence da bases^{1}.

Nous devons maintenant dire quelques mots du procédé lui-même dans le cas partiellement commutatif et, bien qu’il soit apparu pour la première fois (par la nécessité combinatoire du probléme) pour l’algèbre de Lie il est plus suggestif de le voir dans le monoïde.

On se souvient de la factorisation A^{∗} = (B^{∗}Z)^{∗}B^{∗} où A = B + Z) qui consiste à dire que, Z étant un sous alphabet de A, tout mot de A^{∗} est “rythmé” par des lettres de Z et donc doit s’écrire de façon unique : w = w_{1}z_{1}w_{2}z_{2} ⋯ w_{n}z_{n}w_{n+1} où w_{i} ∈ B^{∗} et z_{i} ∈ Z. On observe alors facilement que les éléments w_{i}z_{i} forment un code [Lo][BP]. La factorisation de M(A, ϑ) par élimination est l’analogue parfait de ce qui précède, moyennant quelques précautions techniques nécessaires. D’ailleurs l’élimination est toujours possible et fournit une méthode de descente dans les structures partiellement commutatives.^{2}

Ceci perment aussitôt de montrer que le monoïde partiellement commutatif libre admet une factorisation en monoïdes libres et donc une factorisation complète [DK3][DK5]. Les codes de ces monoïdes sont les analogues de (BZ)^{∗}, ils sont apériodiques [D3], et dans le cas d’un alphabet ordonné, l’élimination successive des lettres de poids croissant permet de montrer que la forme normale lexicographique est une section rationelle. Ces codes seront appellés “codes Z”. Par example pour l’alphabet A = {a, b, c, d}, l’ordre a < b < c < d, et le graphe de commutation a—-b—-c—-d on a :

A^{∗} = ((d^{∗}b)^{∗}(cc^{∗}d^{∗} + dd^{∗})a)^{∗}(d^{∗}b)^{∗}c^{∗}d^{∗}

L’algèbre de Lie (partiellement commutative) admet une décomposition homogène (pour l’évaluation) en somme directe d’algèbres de Lie libres dont les codes sont précisément les codes Z, cette décomposition permet alors de montrer la liberté de L(A, ϑ) pour tous les anneaux de coefficients, de donner des algorithmes de calcul des bases et est compatibles avec toutes les bases multihomogènes, comme par exemple la base de Lyndon partiellement commutative (cf. [La]).^{3} Ces bases sont “universelles” (c’est à dire indépendantes de l’anneau des coefficients) de l’algèbre de Lie partiellement commutative libre. Des cas particuliers d’élimination et de calcul de Witt [DK1] avaient d’ailleurs été traités quelque temps avant par –Doković (cf. [Do1] et [Do2]).

I. Préliminaires

Au cours de ce texte, nous ferons appel à la notion de structure présentée pour les quatre catégories suivantes : monoïdes (Mon), groupes (Grp), k-algèbres de Lie libres (k-Lie Alg) et k-algèbres associatives avec élément unité (k-Alg).

1J’avais donné quelque temps avant une preuve de l’existence de bases [D2]. Mais cette preuve a deux défauts : d’abord elle n’est pas constructive et ensuite elle ne peut être généralisée telle quelle à d’autre présentations, même par des mots de Lie, car celles-ci peuvent introduire de la torsion (cf.

Remarque III.5).

2Pour une mise en scène des méthodes d’élimination partiellement commutatives on pourra se reporter à leur exposé sous forme d’une piéce de théâtre dans [K].

3La décomposition de l’algèbre de Lie correspondant à la suite centrale descendante de P_{n} [Ca] en algèbres de Lie libres est une image de l’élimination partiellement commutative que nous construisons en III.3.

Soit X un ensemble (un alphabet) et X^{∗} le monoïde libre, F (X) le groupe libre, L_{k}(X) l’algèbre de Lie libre, k⟨X⟩ l’algèbre libre c’est à dire les structures librement engendrées par X dans les catégories précédentes. Chacun de ces objects, de façon évidente sera noté Lib_{j}(X) où j ∈ {Mon, Grp, k-Lie Alg, k-Alg}. Appellons relateur une famille de couples R= (u_{i}, v_{i})_{i∈I} ∈ (Lib_{j}(X) × Lib_{j}(X))^{I}, on peut alors se poser la question de la factorisation des morphismes qui coïncident sur les éléments de R. Plus précisément : Existe-t-il un couple (α, A) avec A ∈ Ob(j) et α ∈ Mor_{j}(Lib_{j}(X), A) qui vérifie les conditions suivantes ?

SP1) (∀i ∈ I)(α(u_{i}) = α(v_{i}))

SP2) Pour tout Φ ∈ Mor_{j}(Lib_{j}(X), Y) tel que (∀i ∈ I)(Φ(u_{i}) = Φ(v_{i})) il existe Φ̄ ∈ Mor_{j}(A, Y) tel que le diagramme suivant soit commutatif :

\begin{matrix}Lib_{j}(X) & ⟶^{Φ} & Y \\ α & ↓ \\ A \end{matrix} ↗_{Φ̄}

Figure 1

La réponse est positive dans chacune des catégories considérées, on a :

Proposition I.1. Pour chacune des catégories j ∈ {Mon, Grp, k-Lie Alg, k-Alg} et relateur R, il existe un objet ⟨X; R⟩_{j}, unique à un isomorphisme prés, qui résout le problème précédent.

Preuve. Ces résultats sont classiques.

Dans le cas des monoïdes on montre que ⟨X; R⟩_{Mon} = X^{∗}/ ≡_{R} où ≡_{R} est la congruence la plus fine telle que (∀i ∈ I)(u_{i} ≡ v_{i}).

Pour les groupes c’est F (X)/H_{R} qui résout la question, où H_{R} est le sous-groupe distingué (normal) engendré par la famille (u_{i}v_{i}^{−1})_{i∈I}.

Dans le cas des algèbres (resp. algèbres de Lie) c’est k⟨X⟩/J (resp. L_{k}(X)/J) où J est l’idéal bilatère (resp. l’idéal de Lie) engendré par les différences (u_{i} − v_{i})_{i∈I} qui est solution du probléme. □

Remarques I.2. 1) Un morphisme qui vérifie la condition (SP2) ((∀i ∈ I)(Φ(u_{i}) = Φ(v_{i}))) est dit compatible avec le relateur R ou qu’il respecte les relations de R.

2) Soit ϕ une application X → M où M est un objet donné de la catégorie C_{j} et Φ : Lib_{j}(X) → Mson extension à Lib_{j}(X). Si Φ respecte les relateurs de R et que Φ̄ : ⟨X; R⟩_{j} → M est un isomorphisme. On dira que M admet la présentation ⟨(ϕ(x))_{x∈X}; R⟩_{j}.

II. Examples d’élimination

1. Mots et autres structures libres

a) Monoïde libre

Soit A, un alphabet, Z, un sous-alphabet de A, et B = A − Z. Tout w ∈ A, peut se factoriser de façon unique :

w = w_{1}z_{1}w_{2}z_{2} ⋯ w_{n}z_{n}w_{n+1}

avec w_{i} ∈ B^{∗} et z_{i} ∈ Z. Ce qui revient à écrire :

(II.1.1)  A^{∗} = (B^{∗}Z)^{∗}B^{∗}.

b) Groupe et algèbre de Lie

Pour le groupe libre sur A, on a un analogue de (II.1.1) :

F (A) ≅ F (F B)Z × F (B).

Et pour l’algèbre de Lie :

L(A) ≅ L(B^{∗}Z) × L(B)

Les deux éliminations précédentes sont dues à M. Lazard [Laz].

c) Groupe symétrique

Si c désigne n’importe quel cycle de longueur maximale dans le groupe symétrique 𝔖_{n} on a :

𝔖_{n} = ⟨c⟩ · 𝔖_{n−1},

où ⟨c⟩ désigne le sous-groupe (d’ordre n) engendré par c. Ce fait est partiquement évident mais nous le mentionnons parce qu’il ne s’agit pas d’un produit semi-direct. L’égalité précédente montre que, si on se donne des cycles (c_{k})_{k∈{2,...,n}} chacun de longueur k tel que supp(c_{k}) ⊆ supp(c_{k+1}) (“supports emboités”) tout élément σ ∈ 𝔖_{n} s’écrit de façon unique :

σ = c_{2}^{α_{2}} ⋯ c_{n}^{α_{n}} avec α_{i} < i,

ceci fournit une base de l’algèbre ℚ[𝔖_{n}] bien adaptée qu développement de l’idempotent de Dynkin [D1] qui est doneé par la formule :

nD(x_{1}x_{2}x_{3} ⋯ x_{n}) = [⋯ [[x_{1}, x_{2}], x_{3}], ⋯ x_{n}]

2. Tresses pures

Le groupe des tresses à n brins B_{n} a été introduit par E. Artin [Ar] en 1925 dans une construction topologique. En fait, le groupe de tresses à n brins, B_{n}(M), d’une variété connexe M est tout simplement le groupe fondamental de la variété des parties de M à n points distincts (cf. [Ca]). Le groupe des tresses classiques est B_{n}(ℝ^{2}). On peut représenter graphiquement une tresse par un diagramme plan formé de n chemins réguliers joignant n points A_{1}, …, A_{n} sur une même verticale à n autres points B_{1}, …, B_{n} aussi alignés verticalement et à droite des A_{i}, les points A_{i} et B_{i} étant sur une même horizontale, pour chaque i. Les chemins se coupent transversalement en des points distincts et, à chaque croisement on doit indiquer le brin qui est “au-dessus” et celui qui est “en-dessous” [fig. 2]. Deux tresses se composent par juxtaposition et “oublier” des points intermédiaires [fig. 3]. Deux tresses sont équivalentes si l’on peut passer de l’une à l’autre par des opérations qui reproduisent, par projection les isotopies de l’espace [fig. 4]. Les intuitions que l’on peut avoir sur ce genre de diagramme sont en général confirmées par le calcul.^{4}

B_{n} est engendré par les tresses élémentaires (t_{i})_{1≤i≤n−1} où t_{i} désigne la tresse obtenue en joignant par des segments de droite les points A_{j} à B_{j} pour j ∉ {i, i + 1} ainsi que A_{i} à B_{i+1} et A_{i+1} à B_{i} ce dernier brin passant sous le précédent [fig. 2]. Ces générateurs vérifient le systéme (Σ) suivant, qui constitue, comme l’a montré E. Artin une présentation de B_{n} [Ar].

(Σ_{B})  \{ \begin{matrix}t_{i}t_{j} & = t_{j}t_{i} & pour |i − j| ≥ 2, \\ t_{i}t_{i+1}t_{i} & = t_{i+1}t_{i}t_{i+1} & pour i ≤ n − 2. \end{matrix}

De même on peut montrer que le groupe symétrique 𝔊_{n} adment la présentation

(Σ_{𝔖})  \{ \begin{matrix}σ_{i}σ_{j} & = σ_{j}σ_{i} & pour |i − j| ≥ 2, \\ σ_{i}σ_{i+1}σ_{i} & = σ_{i+1}σ_{i}σ_{i+1} & pour i ≤ n − 2, \\ σ_{i}^{2} & = 1 & pour tout i, \end{matrix}

où, pour i ≤ n − 1, σ_{i} est la transposition (i, i + 1). Le fait que la famille (σ_{i}) vérifie (Σ_{B}) entraine, l’existence d’un morphisme ϕ : B_{n} → 𝔖_{n} tel que (∀i ∈ I)(ϕ(σ_{i}) = t_{i}). Ce morphisme a un sens géométrique très simple :

dans une tresse τ, le chemin qui part du point A_{i}^{(0)} aboutit à un point A_{π(i)}^{(1)} où π ∈ 𝔖_{n} est justement la permutation ϕ(τ).

Le noyau de ϕ est donc formé des tresses qui partent et aboutissent aux points de même indice, on le notera P_{n}. C’est le groupe des tresses pures.

Comme la présentation de 𝔖_{n} s’obtient à partir de celle de P_{n} en ajoutant les relateurs (t_{i}^{2} = 1), P_{n} est le sous-groupe distingué engendré par les (t_{i}^{2}). On se convainc assez facilement géométriquement que P_{n} est engendré par les tresses suivantes [cf. fig. 6] :

g_{ij} = t_{j−1}^{−1}t_{j−2}^{−1} ⋯ t_{i}^{2}t_{i−1}^{−1} ⋯ t_{j−1} avec i < j.

Proposition II.1. i) P_{n} = ⟨g_{ij}⟩_{i<j≤n} et plus précisémént

ii) P_{n} = ⟨g_{i,n}⟩_{i<n} × ⟨g_{i,j}⟩_{j<n−1} le produit étant semi-direct. Le premier facteur (⟨g_{i,n}⟩_{i<n}) est isomorphe à F_{n−1} et le second (⟨g_{i,j}⟩_{j<n−1}) à P_{n−1}

Preuve. Ces résultats sont classiques et on en trouvera une démonstration topologique dans [Bir]. Une démonstration combinatoire peut se faire par une méthode analogue à celle de prop. III.15 (“recomposition semi-directe”).

4On en verra un exemple en avec l’élimination dans le groupe des tresses pures [cf. fig. 5].

1): On montre les formules :

\begin{aligned}t_{i}^{−1}g_{r,s}t_{i} & = g_{r,s} si i ∉ \{r − 1, s − 1, s\} \\ t_{r−1}^{−1}g_{r,s}t_{r−1} & = g_{r,s}g_{r−1,s}g_{r,s}^{−1} \\ t_{r−1}g_{r,s}t_{r−1}^{−1} & = g_{r−1,s} \\ t_{s−1}g_{r,s}t_{s−1}^{−1} & = g_{r,s−1} \\ t_{s−1}^{−1}g_{r,s}t_{s−1}^{−1} & = g_{s−1,s}^{−1}g_{r,s−1}g_{s−1,s} \\ t_{s}^{−1}g_{r,s}t_{s} & = g_{r,s+1} \\ t_{s}g_{r,s}t_{s}^{−1} & = g_{s,s+1}g_{r,s+1}g_{s,s+1}^{−1} \end{aligned}

ce qui prouve (i).

2): Les formules précédentes permettent de définir une action de F (g_{i,j}, i < j < n) sur F_{n−1} = F (g_{i,n}, i < n) c’est à dire un homomorphisme α : F (g_{ij}, i < j < n) → Aut(F (g_{i,n}, i < n). On vérifie que cet homomorphisme est compatible avec les relateurs de P_{n−1} (cf. Remarques I.2.2) et on a donc ainsi une action de P_{n−1} sur F_{n−1}. Ceci permet de définir le produit semi-direct F_{n−1} × P_{n−1} puis de montrer qu’il est isomorphe à P_{n} grâce à la présentation de celui-ci [MKS]. □

III. Élimination dans le cas partiellement commutatif

1. L’algèbre de Lie partiellement commutative

La notion d’algèbre de Lie est historiquement liée à celle de dérivation.

Définition III.1. Soit k un anneau et A, une k-algèbre (non nécessairement associative [Bo2]). Une dérivation est un élément D ∈ End_{k}(A) vérifiant identiquement :

D(xy) = D(x)y + xD(y).

Remarques III.2. 1) La composée de deux dérivations n’est en général pas une dérivation.

2) Par contre le crochet (de Lie) de deux dérivations

[D_{1}, D_{2}] = D_{1}D_{2} − D_{2}D_{1}

est une dérivation. L’ensemble des dérivations de A est donc une sous-algèbre de Lie de End_{k}(A) qui sera notée 𝔇𝔢𝔯(A).

3) Dans un anneau (ou une algèbre associative) l’application ; x → ax−xa = ad_{a}(x) est une dérivation pour les opérations • et [ , ]. Cette dernière (le crochet de Lie) étant définie par la formule [x, y] = xy − yx. On a donc, dans ce cas, les identités :

(JAC)  [x, [y, z]] = [[x, y] , z] + [y, [x, z]] ,
(ALT)  [x, x] = 0.

4) La première de ces identités s’appelle identité de Jacobi et la seconde exprime que l’application bilinéaire définie par [ , ] est alternée.^{5}

Ceci conduit à la définition suivante :

5Contrairement à ce que l’on pourrait croire, cette identité est essentielle. On pourra consulter par exemple [Cu] pour ce rendre compte de ce qui advient lorsqu’on la supprime.

Définition III.3. On appelle k-algèbre de Lie une k-algèbre qui vérifie identiquement (JAC) et (ALT).

Il résulte des travaux de Hall, Witt et Magnus [Bo1][Lo] que l’algèbre de Lie libre peut se réaliser come une algèbre de Lie de polynômes non commutatifs.

Proposition III.4. Soit A, un alphabet et k un anneau. On considère k⟨A⟩ (= k [A^{∗}]) muni de sa structure d’algèbre de Lie pour [P, Q] = P Q − QP. Alors :

La sous-algèbre de Lie L_{k}(A) de k⟨A⟩ engendrée par A est libre en tant qu’algèbre de Lie. C’est à dire que toute application Φ : A → 𝔤 (où 𝔤 est une algèbre de Lie) se prolonge à L_{k}(A) de façon que le diagramme suivant soit commutatif :

\begin{matrix}A & ⟶^{Φ} & 𝔤 \\ nat & ↓ \\ L_{k}(A) \end{matrix} ↗_{Φ̄}

Figure 7

Conformément à la preuve de prop. I.1, on peut réaliser une algèbre de Lie présentée ⟨A; R⟩_{Lie} comme un quotient de l’algèbre de Lie libre. Comme cas particulier on a

L_{k}(A, ϑ) =^{def} ⟨A; ([a, b] = 0)_{(a,b)∈ϑ}⟩_{Lie},

l’algèbre de Lie partiellement commutative libre associée à un alphabet à commutation (A, ϑ). On peut alors se poser les questions suivantes :

Question 1: L’algèbre de Lie L_{ℤ}(A, ϑ) est-elle libre (en tant que ℤ-module) ? Question 2: Si “oui” comment en constuire des bases ? Question 3: Quelle est l’utilité de résoudre Q1 et Q2 ? Reponse 3: Le groupe partiellement commutatif libre est

F (A, ϑ) =^{def} ⟨A; (ab = ba)_{(a,b)∈ϑ}⟩_{Grp}.

Si L_{ℤ}(A, ϑ) est sans torsion, F (A, ϑ) est ordonnable (cf. [DK2]) ce qui permet de montrer la décidabilité de l’équivalence des séries partiellement commutatives rationnelles (cf. [Va]).

Remarques III.5. 1) Certaines relateurs, même composés uniquement de mots de Lie, introduisent de la torsion. Par example :

(R)  \{ \begin{matrix}[[[x_{1}, x_{2}] , x_{3}] , x_{3}] & = 0 \\ [[[x_{1}, x_{3}] , x_{3}] , x_{2}] & = 0 \\ [x_{1}, [[x_{2}, x_{3}] , x_{3}]] & = 0 \end{matrix}

En effet, on montre que, dans l’algèbre de Lie ⟨x_{1}, x_{2}, x_{3}; R⟩_{ℤ−Lie Alg} on a P = [[x_{1}, x_{3}] , [x_{2}, x_{3}]] ≠ 0 mains 2P = 0.

La solution de Q2 (et donc de Q1) s’obtient grâce à une adaptation du procédé d’élimination de M. LAZARD au cas partiellement commutatif.

2. Elimination dans M(A, ϑ)

Soit A, un alphabet, on a muni A d’un graphe ϑ, irréflexif et symétrique (ϑ ⊆ A^{2} − Δ_{A} et ϑ = ϑ^{−1}), un tel couple (A, ϑ) sera appellé alphabet à commutations. On pose :

M(A, ϑ) =^{def} ⟨A; (xy = yx)_{(x,y)∈ϑ}⟩_{Mon}

M(A, ϑ) est le monoïde partiellement commutatif librement engendré par (A, ϑ), ses éléments seront appellés “mots”, “monômes” ou “traces”. On note ≡_{ϑ}, la congruence (sur A^{∗}) engendrée par le relateur (xy = yx)_{(x,y)∈ϑ}. Par exemple, pour ϑ = {(a, b), (b, a), (c, d), (d, c)} (soit graphiquement a—-b c—-d) on a cabacd ≡_{ϑ} ca^{2}bdc. De même que les tresses, les mots partiellement commutatifs admettent une représentation graphique qui permet des intuitions justes, ce sont les empilements développés par G. X. Viennot et son école [Vi].

L’élimination dans M(A, ϑ) est l’analogue de la formule (II.1.1) et fait appel à la notion de sous-alphabet non-commutatif et d’alphabet terminal.

Définition III.6. i) On dira que Z ⊆ A est un sous-alphabet non-commutatif si

(x, y) ∈ Z^{2} ⟹ (x, y) ∉ ϑ.

ii) Soit w ∈ M(A, ϑ), le sous-alphabet ; AT (w) = {a ∈ A | w ∈ M(A, ϑ)a} sera appellé alphabet terminal de w.

iii) Soit Z un sous-alphabet non-commutatif de A et B telle que B ∩ Z = ∅. On appelle code “Z” la partie : C_{Z}(B) = {wz | w ∈ ⟨B⟩, z ∈ Z et AT (wz) = {z}}.

On a alors la décomposition suivante de M(A, ϑ).

Théorème III.7. Si A = B + Z, et que Z est une partie non-commutative de A, tout mot w ∈ M(A, ϑ) s’écrit de façon unique :

w = w_{1}z_{1}w_{2}z_{2} ⋯ w_{n}z_{n}w_{n+1}

avec w_{i} ∈ ⟨B⟩ pour 1 ≤ i ≤ n + 1 et w_{i}z_{i} ∈ C_{Z}(B).

Preuve. On peut la trouver, par exemple dans [DK3] ou [DK5]. □

Remarques III.8. 1): On voit facilement que pour toute partie B ⊆ A on a ⟨B⟩ ≅ M(B, ϑ_{B}) où ϑ_{B} désigne le sous-graphe ϑ ∩ B^{2}.

2): Le théorème précédent entraine l’égalité M(A, ϑ) = C_{Z}(B)^{∗}⟨B⟩ ce qui, compte tenu de la remarque précédente, revient à M(A, ϑ) = C_{Z}(B)^{∗}M(B, ϑ_{B}). Nous sommes donc dans le cadre de la formulation de l’introduction avec ST RUCT = ST RUCT_{1}.

3): En considérant une partition chromatique (Z_{i})_{i∈I} de A (c’est à dire en parties non-commutatives) on voit que, dans le cas où I est fini, (ce qui est toujours possible si A l’est) on a :

M(A, ϑ) = C_{Z_{i_{1}}} (B_{i_{1}})^{∗}C_{Z_{i_{2}}} (B_{i_{2}})^{∗} ⋯ C_{Z_{in}} (B_{i_{n}})^{∗}

avec I = {i_{1}, i_{2}, …, i_{n}} et B_{i_{k}} = ⋃_{j>k} Z_{i_{j}}.

3. Application à l’algèbre de Lie L_{k}(A, ϑ) 1^{ère} Etape: Soit (A, ϑ), un alphabet à commutations et Z une partie non-commu-

tative de A (on posera B = A − Z).

Si wz ∈ C_{Z}(B) on vérifie que, pour toute écriture wz = b_{1}b_{2} ⋯ b_{p}z, le mot de Lie [b_{1}, …, [b_{p−1}, [b_{p}, z]]] a la même valeur dans L_{k}(A, ϑ). Ce mot sera noté α(wz).

On a donc une factorisation de α :

\begin{matrix}C_{Z}(B) & ⟶^{α} & L_{k}(A, ϑ) \\ nat & ↓ \\ L_{k}(C_{Z}(B)) \end{matrix} ↗_{ᾱ} Figure 8

2^{ème} Etape: L’application naturelle β : B → L_{k}(A, ϑ) respecte les commutations de ϑ_{B} d’où une factorisation :

\begin{matrix}B & ⟶^{β} & L_{k}(A, ϑ) \\ nat & ↓ \\ L_{k}(B, ϑ_{B}) \end{matrix} ↗_{β̄} Figure 9

3^{ème} Etape: (Action de L_{k}(B, ϑ_{B}) sur L_{k}(A, ϑ)). On définit des dérivations par les formules suivantes :

∂_{b}(α(wz)) = \{ \begin{matrix}α(bwz) & si bwz ≠ wzb, \\ 0 & sinon. \end{matrix}

L’application ∂_{b} s’étend en une dérivation de L_{k}(C_{Z}(B)) qui vérifie :

(b, b′) ∈ ϑ ⟹ ∂_{b}∂_{b′} = ∂_{b′}∂_{b}

et, à cause de la présentation de L_{k}(B, ϑ_{B}) (qui est donnée par ⟨B; ([b, b′] = 0)_{(b,b′)∈ϑ_{B}}⟩, on a une factorisation :

\begin{matrix}B & ⟶ & 𝔇𝔢𝔯(L_{k}(C_{Z}(B))) \\ nat & ↓ \\ L_{k}(B, ϑ_{B}) \end{matrix} ↗_{∂} Figure 10

4^{ème} Etape: On définit alors sur 𝔤 = L_{k}(C_{Z}(B)) ⊕ L_{k}(B, ϑ_{B}) le crochet suivant^{6} (produit semi-direct) :

6Cette formule est, comme en théorie des groupes, une imitation des égalités que l’on obtient lorsque l’on a un produit semi-direct interne c’est à dire que 𝔤 = 𝔥 ⊕ 𝔤′ où 𝔥 est un idéal de 𝔤.

[P + Q, P′ + Q′] = [P, P′] + ∂_{Q}(P′) − ∂_{Q′}(P) + [Q, Q′] .

Théorème III.9 [DK1]. L’application γ : 𝔤 → L_{k}(A, ϑ) définie par γ(P + Q) = ᾱ(P) + β̄(Q) est un isomorphisme d’algèbres de Lie.

Preuve. On pourra trouver, dans [DK1], une preuve qui consiste à examiner le noyau du morphisme naturel L(A) → L_{k}(A, ϑ), et une autre dans [DK4] proche dans son esprit de celle qui est évoquée à la proposition II.1. □

4. Quelques conséquences

Corollaire III.10. Pour tout anneau k, L_{k}(A, ϑ) se plonge naturellement dans k [M(A, ϑ)] = k⟨A, ϑ⟩ (polynômes partiellement commutatifs), et s’identifie à la sousalgèbre de Lie engendrée par les lettres.

Remarque III.11. L_{k}(A, ϑ) est graduée. En effet, si on pose :

L_{k}^{ν}(A, ϑ) = L_{k}(A, ϑ) ∩ k^{ν}⟨A, ϑ⟩

pour tout ν ∈ ℕ^{A} on a facilement que :

Im(ᾱ) = ⨁_{z∈alph(ν)} L_{k}^{ν}(A, ϑ)

Im(β̄) = ⨁_{z∉alph(ν)} L_{k}^{ν}(A, ϑ)

ceci premet de construire facilement des bases de L_{k}(A, ϑ), par éliminations successives puisque Im(ᾱ) est libre et que Im(β̄) ≅ L_{k}(B, ϑ_{B}).

Corollaire III.12. F (A, ϑ) = ⟨A; (ab = ba)_{(a,b)∈ϑ}⟩, le groupe partiellement commutatif libre, est ordonnable^{7}.

Preuve. On forme la suite centrale descendante définie par

F_{1} = F et F_{n+1} = (F_{n}, F)

où (H, K) désigne le sous-groupe engendré par les commutateurs

(hkh^{−1}k^{−1})_{(h,k)∈H×K}.

Le ℤ-module gradué Gr(F) = ⨁_{n≥1} F_{n}/F_{n+1} peut être muni d’un crochet de Lie qui “linéarise” l’opération commutateur [MKS] et on peut montrer qu’on a un isomorphisme d’algèbres de Lie graduées Gr(F) ≅ L_{ℤ}(A, ϑ). Ce qui prouve que les quotients F_{n}/F_{n+1} sont des groupes abéliens libres (donc ordonnables). On en déduit alors que F (A, ϑ) est ordonnable comme dans [Neu]. □

7C’est à dire peut être muni d’un ordre total compatible avec sa loi [Bo3][Mu][Neu]

Remarque III.13. On peut ordonner F (A, ϑ) par une méthode plus directe [DT].

On a dim(k^{ν}⟨A, ϑ⟩) = |M^{ν}(A, ϑ)|. Il résulte donc du travail de P. Cartier et D. Foata [CF] que la série de Hilbert da l’algèbre graduée k⟨A, ϑ⟩ = ⨁_{ν∈ℕ^{A}} k^{ν}⟨A, ϑ⟩ s’exprime simplement :

∑_{ν∈ℕ^{A}} dim(k^{ν}⟨A, ϑ⟩) T^{ν} = ( ∑_{w∈Cℓ(ϑ)}(−1)^{|w|}T_{w})^{−1} ,

où T= ((T_{a})_{a∈A}) désigne une famille d’indéterminées commutatives, Cℓ(ϑ) est l’ensemble des mots complètement commutatifs sans multiplicité soit :

Cℓ(ϑ) = {a_{1}a_{2} ⋯ a_{n} ∈ M(A, ϑ) | i < j ⟹ (a_{i}, a_{j}) ∈ ϑ}

et T_{a_{1}a_{2}···a_{n}} = T_{a_{1}}T_{a_{2}} ⋯ T_{a_{n}}. D’autre part, on a l’isomorphisme gradué k⟨A, ϑ⟩ ≅^{k-alg.} U(L_{k}(A, ϑ)) et donc grâce au théorème de Poincaré–Birkhoff–Witt [Bo1] aussi

l’isomorphisme gradué k⟨A, ϑ⟩ ≅^{k-mod.} S((L_{k}(A, ϑ)). On en déduit :

Corollaire III.14 (Rangs). Soit l(ν) = dim(L_{k}^{ν}(A, ϑ)) pour tout ν ∈ ℕ^{A}. Alors :

∑_{ν∈ℕ^{A}} dim(k^{ν}⟨A, ϑ⟩)T^{ν} = ( ∑_{w∈Cℓ(ϑ)}(−1)^{|w|}T_{w})^{−1} = ∏_{ν≠0}(1 − T^{ν})^{−l(ν)}.

Preuve. Cf. [DK1]. □

On déduit de ce qui précède des formules pour le calcul des rangs qui généralisent celles de Witt.

4. Le groupe partiellement commutatif libre

a) Éliminiation

On a, là aussi, une formule d’élimination dans F (A, ϑ) = ⟨A; (ab = ba)_{(a,b)∈ϑ}⟩_{Grp}. Soit, comme en III.2, Z ⊆ A un sous-alphabet non-commutatif et B une partie disjointe de Z. On notera D_{Z}(B) l’orbite {wzw^{−1}}_{w∈⟨B⟩} de Z par les conjugaisons de B.

Proposition III.15. i) F (A, ϑ) = ⟨D_{Z}(B)⟩ × ⟨B⟩, le produit étant semi-direct. ii) ⟨D_{Z}(B)⟩ ≅ F (D_{Z}(B)) et ⟨B⟩ ≅ F (B, ϑ_{B}⟩.

Preuve. La démonstration est analogue à celle de l’algébre de Lie libre en remplaçant les dérivations par des automorphismes intérieurs. □

Remarque III.16. Avec les notations de II.2, si l’on considère l’alphabet à commutations A = (g_{ij})_{i<j≤n} et le sous-alphabet Z = (g_{in})_{i<n} on voit que l’élimination dans le groupe des tresse pures est une image de celle qui précède. b) Transformation de Magnus On peut définir l’algèbre large du monoïde partiellement commutatif libre puisque

pour tout w ∈ M(A, ϑ) l’ensemble des solutions de w = uv est fini [Bo2]. Elle a pour support le module k^{M(A,ϑ)} et son produit est :

(f ∗ g)(w) = ∑_{uv=w} f(u)g(v).

Notons k⟨⟨A, ϑ⟩⟩ cette algèbre. Pour un anneau de coefficients k donné (“séries formelles pariellement commutatives”) et 𝔐_{k}⟨⟨A, ϑ⟩⟩ l’idéal {S ∈ k⟨⟨A, ϑ⟩⟩ | S(1)) = 0}. L’application a ⟶ 1 + a prend ses valeurs dans le groupe 1 + 𝔐_{k}⟨⟨A, ϑ⟩⟩ des séries de terme constant 1, cette application respecte les relateurs de F (A, ϑ) si bien qu’on a une factorisation :

\begin{matrix}A & ⟶ & 1 + 𝔐_{k}⟨⟨A, ϑ⟩⟩ \\ nat & ↓ \\ F (A, ϑ) \end{matrix} ↗_{μ} Figure 11

On peut montrer que μ est injective. C’est la transformation de Magnus. On dira qu’une congruence ≡ sur A^{∗} est compatible avec la transformation de Magnus si et seulement si :

u ≡ v ⟹ μ(u) ≡_{k} μ(v)

où μ est la transformation de Magnus de A^{∗}(μ(a_{1}a_{2} ⋯ a_{n} = (1+a_{1})(1+a_{2}) ⋯ (1+a_{n})) et ≡_{k} l’extension par linéarité de ≡ à k⟨A⟩. On peut alors préciser les congruences qui, en caractéristique zéro, sont compatibles avec la transformation de Magnus.

Proposition III.17 (Duchamp 1991). Soit k, un anneau de caractéristique zéro, A un alphabet et ≡ une congruence sur A^{∗}. Les conditions suivantes sont équivalentes :

(1) ≡ est compatible avec la transformation de Magnus.

(2) ≡ est engendrée par des différences du type a − b ou ab − ba où a et b sont des lettres.

Preuve. Remarquons d’abord qu’on se ramène aussitôt à k = ℤ puisque les images de la transformation de Magnus sont des polynômes à coefficients dans ℤ.1_{k}. Montrons alors le sens :

compatible → relateurs du type (a_{i} = b_{i}) et (a_{j}b_{j} = b_{j}a_{j})

(la réciproque étant une simple vérification) et plaçons nous sous l’hypothèse où ≡ est compatible avec la transformation de Magnus.

La démonstration comprend 6 étapes.

1): La congruence ≡ est homogéne.

En effet, si u ≡ v alors μ_{k}(u) ≡ μ_{k}(v) et donc π_{≡}^{k}(μ_{k}(u)) = π_{≡}^{k}(μ_{k}(v)) et, en spécialisant tous les mots de A^{∗}/ ≡ en 1_{ℤ}, 2^{|u|} = 2^{|v|} c’est à dire |u| = |v|.

La congruence étant homogène on notara ≡^{n} la relation d’équivalence induite sur A^{n} et ≡^{≤n} la congruence engendrée par les relations u ≡ v pour |u|, |v| ≤ n.

2): Réduction du problème

Considérons un sous-alphabet S ⊆ A qui soit une section de la relation d’équivalence ≡^{1} on a alors un isomorphisme naturel S^{∗}/ ≡_{S}⟶ A^{∗}/ ≡ (≡_{S} désigne la congruence induite sur S^{∗}) et on vérifie facilement que ≡_{S} est aussi compatible avec la transformation de Magnus. Le résultat sera donc prouvé si on démontre que ≡_{S} est un congruence partiellement commmutative.

3): ≡_{S} est multihomogène.

En effet μ_{ℤ}(u) = 1+∑_{a∈S} |u|_{a}a+∑ termes de longueur ≥ 2 où | |_{a} désigne le degré partiel en la lettre a. La comparaison avec μ_{ℤ}(v) montre que ∑_{a∈S} |u|_{a}a = ∑_{a∈S} |v|_{a}a ce qui, en raison de l’indépendance linéaire des lettres entraine, la propriété :

u ≡_{S} v ⟹ (∀a ∈ A)(|u|_{a} = |v|_{a}).

Une telle congruence est dite multihomogène.

Dans la suite on notera ≡ au lieu de ≡_{S}.

4): ≡ est simplifiable.

En fait, on a la propriété plus forte que S^{∗}/ ≡ se plonge dans un groupe, puisque le fait que ≡ soit compatible avec la transformation de Magnus entraine que S^{∗}/ ≡ se plonge, via cette transformation dans le groupe des éléments f de son algèbre large tels que f(1) = 1.

5): Contradiction

Il suffit maintenant de montrer que ≡=≡^{≤2}. Supposons que ce ne soit pas le cas, on aurait alors un contrexemple de longueur minimale u ≡ v tel que l’on ait pas u ≡^{≤2} v et donc |u| ≥ 3. On peut écrire u = u_{1}a_{n} avec a_{n} ∈ A et v = v_{1}a_{n}w avec a_{n} ∉ Alph(w). On ne peut avoir w = 1 sans quoi, comme ≡ est simplifiable, ceci entrainerait u_{1} ≡ v_{1} puis u_{1} ≡^{≤2} v_{1} en raison de la minimalité du contrexemple et enfin u ≡^{≤2} v, contredisant l’hypothèse. En (6) on va montrer qu’on peut toujours se ramener à ce cas, ce qui entrainera l’impossibilité d’un contrexemple minimal, démontrant ainsi la proposition.

6) a_{n} commute avec w.

Posons d = |u|_{a_{n}} = |v|_{a_{n}} et w = w_{1}w_{2} ⋯ w_{k}. Pour toute lettre w_{i}, le monôme a_{n}^{d}w_{i} qui figure dans μ(v) figure aussi dans μ(u). On a donc, en raison de la multihomogénéïté, a_{n}^{d}w_{i} ≡ a_{n}^{d−j}w_{i}a_{n}^{j} et j ≥ 1 à cause de la forme de u. Ceci entraine w_{i}a_{n}^{j} ≡ a_{n}^{j}w_{i}. En prenant les logarithmes des transformés dans 1 + 𝔐_{ℚ} [[S^{∗}/ ≡]], on en déduit que w_{i}a_{n} ≡ a_{n}w_{i}.

Conclusion

Les structures partiellement commutatives sont étroitement liées les unes aux autres. Par exemple on a :

k⟨A, ϑ⟩ = k [M(A, ϑ)] ≅ U(L_{k}(A, ϑ))

cela tient à ce que les commutations partielles sont à la fois des relations monoïdales (ab = ba) et des relations de Lie ([a, b] = 0) et, d’une certaine façon, en caractéristique zéro, ce sont les seules. En fait, on a le théorème suivant :

Théorème de limitation [DK3][DK4]. Soit A, un alphabet et k un anneau de caractéristique zéro^{8}. On suppose qu’un idéal bilatère ℑ est engendré (en tant qu’idéal bilatère) par des polynômes de Lie et aussi par des différences de mots. Alors il existe deux familles doubles de lettres (a_{i}, b_{i})_{i∈I} et (a_{j}, b_{j})_{j∈J} tel que 𝔍 soit aussi engendré par les polynômes (a_{i} − b_{i})_{i∈I} et (a_{j}b_{j} − b_{j}a_{j})_{j∈J}.

Ceci implique que k⟨A⟩/ℑ est une algèbre de polynômes partiellement commutatifs et montre le caractère très particulier de ces algèbres.

References

[Ar] ARTIN, E., Theorie der Zöpfe, Collected papers (S. Lang et J. Tate, eds.), Addison–Wesley, 1965.

[BP] BERSTEL, J., PERRIN, D., Theory of codes, Academic Press, 1985.

[Bir] BIRMAN, J.S., Recent developments in braid and link theory, Math. Intelligencer 13 (1991), 51–60.

[Bo1] BOURBAKI, N., Groupes et algèbres de Lie, Ch. 2 et 3, Hermann, 1972.

[Bo2] BOURBAKI, N., Algèbres, Ch. 1 à 3, Hermann, 1970.

[Bo3] BOURBAKI, N., Algèbre, Ch. 6.1, Masson, 1981.

[Ca] CARTIER, P., Developpements récents sur les groupes de tresses. Applications à la topologie et à l’algèbre, Séminaire Bourbaki, Vol. 1989/90, Astérisque No. 189-190, Exp. No. 716, 1990, pp. 17–67.

[CF] CARTIER, P., FOATA, D., Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, No. 85, Springer-Verlag, Berlin–New York, 1969.

[CP] CORI, R., PERRIN, D., Automates et commutations partielles, RAIRO Inform. Theor. 19 (1985), 21–32.

[Cu] CUVIER, C., Homologie des algèbres de Leibniz, Thèse Univ. de Strasbourg, 1991.

[Do1] –DOKOVIĆ, D.Z., A generalization of Witt’s formulae, J. Algebra 111 (1987), 262–278.

[Do2] –DOKOVIĆ, D.Z., On some inner derivations of free Lie algebras over commutative rings, J. Algebra 119 (1988), 233–245.

[Du] DUBOC, C., Commutations dans les monoïdes libres, Thèse Univ. de Rouen, 1986.

[D1] DUCHAMP, G., Orthogonal projection onto the free Lie algebra, Theoret. Comput. Sci. 79 (1991), 227–239.

[D2] DUCHAMP, G., On the partially comutative free Lie algebra, Rapport LITP 89.74.

[D3] DUCHAMP, G., Factorisations partiellement commutativs et apériodicité, Rapport LITP 91.08 et actes des journées Montoises 1990, pp. 42–48.

[DK1] DUCHAMP, G., KROB, D., The free partially commutative Lie algebra: bases and ranks, Adv. Math. 95 (1992), 92–126.

[DK2] DUCHAMP, G., KROB, D., The lower central series of the free partially commutative group, Semigroup Forum 45 (1992), 385–394.

[DK3] DUCHAMP, G., KROB, D., Factorisations dans le monoïde partiellement commutatif libre, C. R. Acad. Sci. Paris Sér. I Math. 312 (1991), 189–192.

[DK4] DUCHAMP, G., KROB, D., Free partially commutative structures, J. Algebra 156 (1993), 318–361.

[DK5] DUCHAMP, G., KROB, D., Lazard’s factorizations of free partially commutative monoids, Automata, languages and programming (Madrid, 1991), Lecture Notes in Comput. Sci., 510,, Springer, Berlin, 1991, pp. 242–253.

[DT] DUCHAMP, G., THIBON, J.-Y., Decidable orderings for free groups, manuscrit, 1991.

[HK] HARJU, T., KARHUMÄKI, J., The equivalence problem of multitape finite automata, Theoret. Comput. Sci. 78 (1991), 347–355.

[K] KROB, D., L’algèbre de Lie partiellement commutative libre, Rapport LITP 90.74.

8Le théorème ne vaut plus en caractéristique p.

[laz] LAZARD, M., Groupes, anneaux de Lie et problème de Burnside, Inst. Math. dell. Univ. Roma, 1960.

[La] LALONDE, P., Contributions à l’étude des empilements, Publications du LACIM 4, UQAM Montréal, 1991.

[Lo] LOTHAIRE, M., Combinatorics on words, Addison–Wesley, 1983.

[MKS] MAGNUS, W., KARRASS, A., SOLITAR, D., Combinatorial group theory, Second revised edition, Dover Publications, Inc., New York, 1976.

[Mu] MURA, R.B., RHEMTULLA, A., Orderable groups, Marcel Dekker, 1977.

[Neu] NEUMANN, B.H., On ordered division rings, Trans. Amer. Math. Soc. 66 (1949), 202–252.

[T] THIBON, J.-Y., Integrité des algèbres de séries formelles sur un alphabet partiellement commutatif, Theoret. Comput. Sci. 41 (1985), 109–112.

[Va] VARRICCHIO, S., On the decidability of the equivalence problem for partially commutative rational power series, Theoret. Comput. Sci. 99 (1992), 291–299.

[Vi] VIENNOT, G.X., Heaps of pieces. I. Basic definitions and combinatorial lemmas, Graph theory and its applications: East and West (Jinan, 1986), Ann. New York Acad. Sci., 576, New York Acad. Sci., New York, 1989, pp. 542–570.

[Z] ZEILBERGER, D., Identities in search of identity, Theoret. Comput. Sci. 117 (1993), 23–38.