Let X be a set. Recall the construction of the free magma M(X) constructed on X (Algebra, Chapter I, § 7, no. 1). By induction on the integer n⩾1, we define the sets Xn by writing X1=X and taking Xn to be the sum set of the sets Xp×Xn−p where p=1,2,…,n−1; if X is finite, so is each Xn. The sum set of the family (Xn)n⩾1 is denoted by M(X); each of the sets Xn (and in particular X) is identified with a subset of M(X). Let w and w′ be in M(X); let p and q denote the integers such that w∈Xp and w′∈Xq and let n=p+q; the image of the ordered pair (w,w′) under the canonical injection of Xp×Xn−p into Xn is denoted by w.w′ and called the product of w and w′. Every mapping of X into a magma M can be extended in a unique way to a magma homomorphism of M(X) into M.
Let w be in M(X); the unique integer n such that w∈Xn is called the length of w and denoted by l(w). Then l(w.w′)=l(w)+l(w′) for w, w′ in M(X). The set X is the subset of M(X) consisting of the elements of length 1. Every element w of length ⩾2 can be written uniquely in the form w=w′.w′′.
The algebra of the magma M(X) with coefficients in the ring K is denoted by Lib(X), or Lib_K(X) when it is necessary to indicate the ring K. The set M(X) is a basis of the K-module Lib(X) and X will therefore be identified with a subset of Lib(X). If A is an algebra, every mapping of X into A can be extended uniquely to a homomorphism of Lib(X) into A (Algebra, Chapter III, § 2, no. 7, Proposition 7).
2. Construction of the free Lie algebra
Definition 1
The free Lie algebra over the set X is the quotient algebra*
L(X)=Lib(X)/a,
where a is the two-sided ideal of Lib(X) generated by the elements of one of the forms (1)
Q(a)=a.afor a in Lib(X),
(2)
J(a,b,c)=a.(b.c)+b.(c.a)+c.(a.b)
for a,b,c in Lib(X).
Clearly L(X) is a Lie K-algebra; the composition of two elements u,v of L(X) will be denoted by [u,v]. When it is necessary to indicate the ring K, we write LK(X) for L(X).
The following proposition justifies the name free Lie algebra given to L(X).
Proposition 1
Let ψ be the canonical mapping of Lib(X) onto L(X) and ϕ the restriction of ψ to X. For every mapping f of X into a Lie algebra g, there exists one and only one homomorphism F: L(X)→g such that f=F∘ϕ.
(a) Existence of F: let h be the homomorphism of Lib(X) into g extending f (no. 1). For all a in Lib(X), h(Q(a))=h(a.a)=[h(a),h(a)]=0; similarly, the Jacobi identity satisfied by g implies that h(J(a,b,c))=0 for a,b,c in Lib(X). It follows that h(a)=0, whence there is a homomorphism F of L(X) into g such that h=F∘ψ. By restricting to X, we obtain f=F∘ϕ.
(b) Uniqueness of F: let F′:L(X)→g be a homomorphism such that f=F′∘ϕ. The homomorphisms F∘ψ and F′∘ψ of Lib(X) into g coincide on X and hence are equal; as ψ is surjective, F=F′.
Corollary 1
The family (ϕ(x))x∈X is free over K in L(X).
Let x1,x2,…,xn be distinct elements of X and λ1,…,λn be elements of K such that
λ1⋅ϕ(x1)+⋯+λn⋅ϕ(xn)=0.
Let g be the commutative Lie algebra with K as underlying module. For i=1,2,…,n, there exists a homomorphism Fi of L(X) into g such that Fi(ϕ(xi))=1 and Fi(ϕ(x))=0 for x=xi (Proposition 1); applying Fi to relation (3), we obtain λi=0.
Corollary 2
Let a be a Lie algebra. Every extension of L(X) by a is inessential.
Let aλgμL(X) be such an extension (Chapter I, § 1, no. 7). As μ is surjective, there exists a mapping f of X into g such that ϕ=μ∘f. Let F be the homomorphism of L(X) into g such that f=F∘ϕ (Proposition 1). Then (μ∘F)∘ϕ=μ∘f=ϕ and Proposition 1 shows that μ∘F is the identity automorphism of L(X). The given extension is therefore inessential (Chapter I, § 1, no. 7, Proposition 6 and Definition 6).
As the ring K is non-zero, Corollary 1 to Proposition 1 shows that ϕ is injective. Hence the set X can be identified by means of ϕ with its image in L(X); with this convention, X generates L(X) and every mapping of X into a Lie algebra gcan be extended to a Lie algebra homomorphism of L(X) into g.
Remark
When X is empty, M(X) is empty and hence L(X)={0}. If X consists of a single element x, the submodule K.x of L(X) is a Lie subalgebra of
L(X); as X generates L(X), Corollary 1 to Proposition 1 shows that L(X) is a free module with basis {x}.
3. Presentations of a Lie algebra
Let g be a Lie algebra and a=(ai)i∈I a family of elements of g. Let fa be the homomorphism of L(I) into g mapping each i∈I to ai. The image of fa is the subalgebra of g generated by a; the elements of the kernel of fa are called the relators of the family a. The family a is called generating (resp. free, basic) if fa is surjective (resp. injective, bijective).
Let g be a Lie algebra. A presentation of g is an ordered pair (a,r) consisting of a generating family a=(ai)i∈I and a family r=(rj)j∈J of relators of a generating the ideal of L(I) the kernel of fa. We also say that g is presented by the family a related by the relators rj (j∈J).
Let I be a set and r=(rj)j∈J be a family of elements of the free Lie algebra L(I); let ar be the ideal of L(I) generated by r. The quotient algebra L(I,r)=L(I)/ar is called the Lie algebra defined by I and the family of relators (rj)j∈J; we also say that L(I,r) is defined by the presentation (I, r), or also by (I;(rj=0)j∈J). When the family r is empty, L(I,r)=L(I).
Let I and r be as above; let ξi denote the image of i in L(I,r). The generating family ξ=(ξi)i∈I and the family of relators r constitute a presentation of L(I,r). Conversely, if g is a Lie algebra and (a,r), where a=(ai)i∈I, is a presentation of g, there exists a unique isomorphism u:L(I,r)→g such that u(ξi)=ai for all i∈I.
4. Lie polynomials and substitutions
Let I be a set. Let Ti denote the canonical image of the element i of I in L(I) (which is also sometimes denoted by L((Ti)i∈I)); the elements of L(I) are called Lie polynomials in the indeterminates (Ti)i∈I.
Let g be a Lie algebra. If t=(ti)i∈I is a family of elements of g, let ft denote the homomorphism of L(I) into g such that ft(Ti)=ti for i∈I (no. 2, Proposition 1). The image under ft of the element P of L(I) is denoted by P((ti)i∈I). In particular, P((Ti)i∈I)=P; the above element P((ti)i∈I) is sometimes called the element of g obtained by substituting the ti for the Ti in the Lie polynomial P((Ti)i∈I).
Let σ:g→g′ be a Lie algebra homomorphism. For every family t=(ti)i∈I of elements of g and all P∈L(I),
σ(P((ti)i∈I))=P((σ(ti))i∈I),
for σ∘ft maps Ti to σ(ti) for i∈I.
Let (Qj)j∈J be a family of elements of L(I) and let P∈L(J). By substituting the Q_j for the T_j in P, we obtain a Lie polynomial R = P((Q_j)_{j \in J}) \in L(I). Then
(5)
R((ti)i∈I)=P((Qj((ti)i∈I))j∈J)
for every family t=(ti)i∈I of elements of a Lie algebra g, as is seen by operating by the homomorphism ft on the equation R=P((Qj)j∈J) and using (4).
Let g be a Lie algebra, I a finite set and P∈L(I). Suppose that g is a free K-module. The mapping
P~:gI→g
defined by P~((ti)i∈I)=P((ti)i∈I) is then polynomial.† For the set F of mappings of gI into g is a Lie algebra with the bracket defined by
[ϕ,ψ](t)=[ϕ(t),ψ(t)];
the set F' of polynomial mappings of gI into g is a Lie subalgebra of F by the bilinearity of the bracket. Our assertion then follows from the fact that the mapping P↦P~ is a Lie algebra homomorphism and T~i=pri∈F′ for all i.
5. Functorial properties
Proposition 2
Let X and Y be two sets. Every mapping u:X→Y can be extended uniquely to a Lie algebra homomorphism L(u):L(X)→L(Y). For every mapping v:Y→Z, L(v∘u)=L(v)∘L(u).
The existence and uniqueness of L(u) follow from Proposition 1 of no. 2. The homomorphisms L(v∘u) and L(v)∘L(u) have the same restriction to X and hence are equal (Proposition 1).
Corollary
If u is injective (resp. surjective, bijective), so is L(u).
Since the assertion is trivial for X=∅, we assume X=∅. If u is injective there exists a mapping v of Y into X such that v∘u is the identity mapping of X; by Proposition 2, L(v)∘L(u) is the identity of automorphism of L(X) and hence L(u) is injective. When u is surjective, there exists a mapping w of Y into X such that u∘w is the identity mapping of Y; then L(u)∘L(w) is the identity mapping of L(Y), which proves that L(u) is surjective.
† Recall (Algebra, Chapter IV, § 5, no. 10) the definition of polynomial mappings of a free module M into a module N: if q is an integer ≥0, a mapping f:M→N is called homogeneous polynomial of degree q if there exists a multilinear mapping u of Mq into N such that
f(x)=u(x,…,x)for all x∈M.
A mapping of M into N is called polynomial if it is a finite sum of homogeneous polynomial mappings of suitable degrees.
Let X be a set and S a subset of X. The above corollary shows that the canonical injection of S into X can be extended to an isomorphism α of L(S) onto the Lie subalgebra L′(S) of L(X) generated by S; we shall identifyL(S)andL′(S)by means ofα.
Let (Sα)α∈I be a right directed family of subsets of X with union S. The relation Sα⊂Sβ implies L(Sα)⊂L(Sβ) and hence the family of Lie subalgebras L(Sα) of L(X) is right directed. Therefore g=⋃α∈IL(Sα) is a Lie subalgebra of L(X); then S⊂g, whence L(S)⊂g, and, as L(Sα)⊂L(S) for all α∈I, g⊂L(S). Hence
L(α∈I⋃Sα)=α∈I⋃L(Sα)
for every right directed family (Sα)α∈I of subsets of X.
Applying the above to the family of finite subsets of X, we see that every element of L(X) is of the form P(x1,…,xn) where P is a Lie polynomial in n indeterminates and x1,…,xn are elements of X.
Proposition 3
Let K′ be a non-zero commutative ring and u:K→K′ a ring homomorphism. For every set X there exists one and only one Lie K′-algebra homomorphism
v:LK(X)⊗K′→LK′(X)
such thatv(x⊗1)=xforx∈X. Further, v is an isomorphism.
Applying Proposition 1 to g=LK′(X) considered as a Lie K-algebra and the mapping x↦x of X into g, we obtain a K-homomorphism LK(X)→LK′(X), whence there is a K′-homomorphism v:LK(X)⊗K′→LK′(X). The fact that v is unique and is an isomorphism follows from the fact that the ordered pair (LK(X)⊗K′,x↦x⊗1) is a solution of the same universal mapping problem as the ordered pair (LK′(X),x↦x).
Remark
Let h′ be a Lie K′-algebra and h the Lie K-algebra derived from h′ by restricting the ring of scalars. If P∈LK(X), we can define P~:hX→h (no. 4). We see immediately that
P~=(v(P⊗1))−.
6. Graduations
Let Δ be a commutative monoid, written additively. Let ϕ0 denote a mapping of X into Δ and ϕ the homomorphism of the free magma M(X) into Δ which extends ϕ0. For all δ∈Δ, let Libδ(X) be the submodule of Lib(X) with basis the subset ϕ−1(δ) of M(X). The family (Libδ(X))δ∈Δ is a graduation of the algebra Lib(X), that is
Lib(X)=δ∈Δ⨁Libδ(X)
Libδ(X)⋅Libδ′(X)⊂Libδ+δ′(X)for δ,δ′ in Δ
Lemma 1
The ideal a of Definition 1 is graded. For a,b in Lib(X), let B(a,b)=a.b+b.a. The formulae
for w1,…,wn in M(X) and λ1,…,λn in K, show that the families (Q(a))a∈Lib(X) and (Q(w),B(w,w′))w,w′∈M(X) generate the same submodule of Lib(X). As J is trilinear the ideal a is generated by the homogeneous elements Q(w),B(w,w′) and J(w,w′,w′′), where w,w′,w′′ are in M(X), and hence is graded (Algebra, Chapter III, § 3, no. 3, Proposition 1).
Let the Lie algebra L(X)=Lib(X)/a be given the quotient graduation. The homogeneous component of L(X) of degree δ is denoted by Lδ(X); it is the submodule of L(X) generated by the images of the elements w∈M(X) such that ϕ(w)=δ.
We shall make special use of the following two cases: (a) Total graduation: we take Δ=N and ϕ0(x)=1 for all x∈X, whence ϕ(w)=l(w) for w in M(X). The K-module Ln(X) is generated by the images of the elements of length n in M(X), which we shall call alternants of degree n. We shall see later that the module Ln(X) is free and admits a basis consisting of alternants of degree n (no. 11, Theorem 1). Then L(X)=⨁n≥1Ln(X) and L1(X) admits X as basis (no. 2, Corollary 1 to Proposition 1). By the construction of M(X),
(12)Ln(X)=p=1∑n−1[Lp(X),Ln−p(X)]
and in particular
(13)[Lm(X),Ln(X)]⊂Lm+n(X).
(b) Multigraduation: we take Δ to be the free commutative monoid N(X) constructed on X. The mapping ϕ0 of X into Δ is defined by (ϕ0(x))(x′)=δxx′, where δxx′ is the Kronecker symbol. For w∈M(X) and x∈X, the integer (ϕ(w))(x) is "the number of occurrences of the letter x in w". For α in N(X), we write ∣α∣=∑x∈Xα(x), whence ∣ϕ(w)∣=l(w) for all w in M(X). It follows that
(14)Ln(X)=∣α∣=n⨁Lα(X);
obviously
(15)[Lα(X),Lβ(X)]⊂Lα+β(X)for α,β in N(X).
Proposition 4
Let S be a subset of X. If N(S) is identified with its canonical image in N(X) (Algebra, Chapter I, § 7, no. 7), then L(S)=∑α∈N(S)Lα(X). Further, for all α∈N(S), the homogeneous component of degree α under the multigraduation on L(S) is equal to Lα(X).
Let α∈N(S). The module Lα(S) is generated by the images in L(X) of the elements w in M(S) such that ϕ(w)=α, that is (Algebra, § 7, no. 9, formulae (23) and (24)) the set of w in M(X) such that ϕ(w)=α. Hence Lα(S)=Lα(X).
The proposition follows from this and the relation L(S)=∑α∈N(S)Lα(S).
Corollary
For every family (Si)i∈I of subsets of X,
L(i∈I⋂Si)=i∈I⋂L(Si).
This follows from Proposition 4 and the obvious formula
N(S)=i∈I⋂N(Si)
where we have written S=⋂i∈ISi.
7. Lower central series
Proposition 5
Let g be a Lie algebra and P a submodule of g. We define the submodules Pn of g by the formulae P1=P and Pn+1=[P,Pn] for n≥1. Then
[Pm,Pn]⊂Pm+n,
Pn=p=1∑n−1[Pp,Pn−p]for n≥2.
We prove (18) by induction on m. The case m=1 is obvious. By the Jacobi identity,
[[P,Pm],Pn]⊂[Pm,[P,Pn]]+[P,[Pm,Pn]],
that is
[Pm+1,Pn]⊂[Pm,Pn+1]+[P,[Pm,Pn]].
The induction hypothesis implies that [Pm,Pn+1]⊂Pm+n+1 and [Pm,Pn]⊂Pm+n, whence
[Pm+1,Pn]⊂Pm+n+1+[P,Pm+n]=Pm+n+1.
By formula (18), Pn⊃∑p=1n−1[Pp,Pn−p]⊃[P1,Pn−1]=Pn, whence (19).
When we take P=g, the sequence (Pn) is the lower central series (Cng) of g (Chapter I, § 1, no. 5). Hence:
Proposition 6
Let g be a Lie algebra and (Cng)n≥1 the lower central series of g. Then
[Cmg,Cng]⊂Cm+ngfor m≥1 and n≥1.
Generalizing Definition 1 of Chapter I, § 4, no. 1, we shall say that a Lie algebra g is nilpotent if Cng={0} for n sufficiently large. The nilpotency class of a nilpotent Lie algebra g is the smallest integer n such that Cn+1g={0}.
Proposition 7
Let X be a set and n an integer ≥1. (a) Ln+1(X)=[L1(X),Ln(X)]. (b) The moduleLn(X)is generated by the elements[x1,[x2,…,[xn−1,xn]…]]where(x1,…,xn)runs through the set of sequences ofnelements ofX. (c) The lower central series ofL(X)is given byCn(L(X))=∑p≥nLp(X).
(a) We apply Proposition 5 with g=L(X) and P=L1(X). By induction on n, we deduce from (12) (no. 6) and (19) the equality Pn=Ln(X). The desired relation is then equivalent to the definition [P,Pn]=Pn+1. (b) This follows from (a) by induction on n. (c) Let g=L(X) and gn=∑p≥nLp(X). Then g=g1 and formula (13) of no. 6 implies [gn,gm]⊂gn+m and in particular [g,gn]⊂gn+1. By induction on n, Cng⊂gn. On the other hand, from (a) we deduce that Ln(X)⊂Cng by induction on n. As Cng is an ideal of g, the relation Lp(X)⊂Cng implies that
Lp+1(X)=[L1(X),Lp(X)]⊂Cng
by (a). Hence Lp(X)⊂Cng for p≥n, whence gn⊂Cng.
Corollary
Let g be a Lie algebra and (xi)i∈I a generating family of g. The n-th term Cng of the lower central series of g is the module generated by the iterated brackets [xi1,[xi2,…,[xip−1,xip]…]] for p≥n, and i1,…,ip in I. Let f be the homomorphism of L(I) into g such that f(i)=xi for all i∈I. As (xi)i∈I generates g, g=f(L(I)), whence Cng=f(Cn(L(I))) by Proposition 4 of Chapter I, § 1, no. 5. The corollary then follows from assertions (b) and (c) of Proposition 7.
8. Derivations of free Lie algebras
Proposition 8
Let X be a set, let M be an L(X)-module and let d be a mapping of X into M. There exists one and only one linear mapping D of L(X) into M extending d and satisfying the relation:
D([a,a′])=a.D(a′)−a′.D(a)for a,a′ in L(X).
We define a Lie algebra g with underlying module M×L(X) by means of the bracket
[(m,a),(m′,a′)]=(a.m′−a′.m,[a,a′]),
for a,a′ in L(X) and m,m′ in M (Chapter I, § 1, no. 8). Let f be the homomorphism of L(X) into g such that f(x)=(d(x),x) for all x in X; let f(a)=(D(a),u(a)) for all a in L(X). By formula (21), u is a homomorphism of L(X) into itself; as u(x)=x for x in X, u(a)=a for all a in L(X), whence
(22)
f(a)=(D(a),a).
By (21) and (22), relation (20) then follows from f([a,a′])=[f(a),f(a′)].
Conversely, let D′ be a mapping of L(X) into M satisfying relation (20') analogous to (20) and extending d. Let f′(a)=(D′(a),a) for a∈L(X); by (20') and (21), f′ is a homomorphism of L(X) into g, coinciding with f on X, whence f′=f and D′=D.
Corollary
Every mapping of X into L(X) can be extended uniquely to a derivation of L(X)*.
When M is equal to L(X) with the adjoint representation, relation (20) means that D is a derivation.
9. Elimination theorem
Proposition 9
Let S1 and S2 be two disjoint sets and d a mapping of S1×S2 into L(S2). Let g be the quotient Lie algebra of L(S1∪S2) by the ideal generated by the elements [s1,s2]−d(s1,s2) with s1∈S1,s2∈S2; let ψ be the canonical mapping of L(S1∪S2) onto g.
(a) *For i=1,2, the restriction ϕi of ψ to Si can be extended to an isomorphism of L(Si) onto a subalgebra ai of g.
(b) g=a1+a2,a1∩a2={0} and a2 is an ideal of g.
For i=1,2, let ψi denote the homomorphism of L(Si) into g which extends ϕi and ai its image. Clearly ϕi(Si) generates ai.
Let s1∈S1; we write D=adϕ1(s1). The derivation D of g maps ϕ2(S2) into a2 by the relation
[ϕ1(s1),ϕ2(s2)]=ψ2(d(s1,s2))for s2∈S2;
as the subalgebra a2 of g is generated by ϕ2(S2), therefore D(a2)⊂a2. The set of x∈g such that adx leaves a2 invariant is a Lie subalgebra of g which contains ϕ1(S1) by the above and hence also a1. Hence
(23)
[a1,a2]⊂a2.
Therefore a1+a2 is a Lie subalgebra of g and, as it contains the generating set ϕ1(S1)∪ϕ2(S2),
(24)
a1+a2=g.
For all s1∈S1 there exists a derivation Ds1 of L(S2) such that
Ds1(s2)=d(s1,s2)
for all s2 in S2 (no. 8, Corollary to Proposition 8). The mapping s1↦Ds1 can be extended to a homomorphism D of L(S1) into the Lie algebra of derivations of L(S2). Let h be the semi-direct product of L(S1) by L(S2) corresponding to D (Chapter I, § 1, no. 8). As a module h is equal to L(S1)×L(S2) and in particular
[(s1,0),(0,s2)]=(0,d(s1,s2))
for s1∈S1 and s2∈S2.
From (25) we deduce the existence of a homomorphism f of g into h such that f(ϕ1(s1))=(s1,0) and f(ϕ2(s2))=(0,s2) for s1∈S1 and s2∈S2. We deduce immediately the relation
f(ψ1(a1)+ψ2(a2))=(a1,a2)
for a1∈L(S1) and a2∈L(S2).
Relation (26) shows that ψ1 and ψ2 are injective and that a1∩a2={0}. Formulae (23) and (24) then imply the proposition.
Proposition 10 (elimination theorem)
Let X be a set, S a subset of X and T the set of sequences (s1,…,sn,x) with n≥0,s1,…,sn in S and x in X −S.*†
(a) *The module L(X) is the direct sum of the subalgebra L(S) of L(X) and the ideal a of L(X) generated by X−S.
(b) There exists a Lie algebra isomorphism ϕ of L(T) onto a which maps (s1,…,sn,x) to (ads1∘⋯∘adsn)(x).
Let g be the Lie algebra constructed as in Proposition 9 given
S1=S,S2=T,d(s,t)=(s,s1,…,sn,x)∈T⊂L(T)
for t=(s1,…,sn,x) in T and s∈S1. We identify L(S) and L(T) with their canonical images in g (Proposition 9 (a)).
Let ψ be the mapping (s1,…,sn,x)↦(ads1∘⋯∘adsn)(x) of T into L(X). Obviously ψ(d(s,t))=[s,ψ(t)] for s∈S and t∈T and hence there exists a homomorphism α:g→L(X) whose restriction to S is the identity and whose restriction to T is ψ. Now X−S⊂T, whence there is a homomorphism β:L(X)→g whose restriction to X=S∪(X−S) is the identity.
We show that α is an isomorphism and β the inverse isomorphism. As ψ(x)=x for x in X−S, we see that α∘β coincides with the identity on X, whence α∘β=IdL(X). On the other hand, [s,t]=d(s,t) in g for s∈S,t∈T by construction; it follows that t=(s1,…,sn,x) is equal in g to (ads1∘⋯∘ads2)(x) whence t=β(α(t)). As β(α(s))=s for s∈S and S∪T generates g, β∘α=Idg.
As α is an isomorphism of g onto L(X), Proposition 9 shows that the restric-
† For n=0, we obtain the elements of X−S, whence X−S⊂T.
tion of α to L(T) is an isomorphism ϕ of L(T) onto an ideal b of L(X) such that the module L(X) is the direct sum of L(S) and b. Obviously
ϕ(s1,…,sn,x)=(ads1∘⋯∘adsn)(x)
for (s1,…,sn,x) in T.
Hence ϕ(T)⊂a, whereas b⊂a since ϕ(T) generates the subalgebra b of L(X). But b is an ideal and X−S⊂ϕ(T)⊂b, whence a⊂b.
Corollary
Let y∈X. The free Lie algebra L(X) is the direct sum of the free submodule K.y and the Lie subalgebra admitting as basic family the family of ((ady)n,z) where n⩾0 and z∈X−{y}.
It suffices to put S={y} in Proposition 10.
10. Hall sets in a free magma
Let X be a set, M(X) the free magma constructed on X and Mn(X), where n∈N∗, the set of elements of M(X) of length n (no. 1). If w∈M(X) and l(w)⩾2, let α(w) and β(w) denote the elements of M(X) determined by the relation w=α(w)β(w); then l(α(w))<l(w), l(β(w))<l(w). Finally, for u,v in M(X), let umv denote the element defined by induction on the integer m⩾0 by u0v=v and um+1v=u(umv).
Definition 2
A Hall set relative to X is any totally ordered subset H of M(X) satisfying the following conditions:* (A) If u∈H,v∈H and l(u)<l(v), then u<v. (B) X⊂H and H∩M2(X) consists of the products xy with x,y in X and x<y. (C) *An element w of M(X) of length ⩾3 belongs to H if and only if it is of the form a(bc) with a,b,c in H, bc∈H, b⩽a<bc and b<c.
Proposition 11
There exists a Hall set relative to X.
We shall construct by induction on the integer n sets Hn⊂Mn(X) and a total ordering on these sets: (a) We write H1=X and give it a total ordering. (b) The set H2 consists of the products xy with x,y in X and x<y. We give it a total ordering. (c) Let n⩾3 be such that the totally ordered sets H1,…,Hn−1 are already defined. The set Hn−1′=H1∪⋯∪Hn−1 has a total ordering which induces the given relations on H1,…,Hn−1 and is such that w<w′ if l(w)<l(w′). We define Hn to be the set of products a(bc)∈Mn(X) with a,b,c in Hn−1′ satisfying the relations bc∈Hn−1′, b⩽a<bc, b<c and give Hn a total ordering.
We write H=⋃n⩾1Hn; we give H the total ordering defined thus: w⩽w′ if and only if l(w)<l(w′) or l(w)=l(w′)=n and w⩽w′ in the set Hn. It is immediate that H is a Hall set relative to X.
For every subset S of X, we identify the free magma M(S) with its canonical image in M(X).
Proposition 12
Let H be a Hall set relative to X and let x, y be in X. (a) H∩M({x})={x}. (b) Suppose that x<y and let dy be the homomorphism of M(X) into N such that dy(y)=1 and dy(z)=0 for z∈X,z=y. The set of elements w∈H∩M({x,y}) such that dy(w)=1 consists of the elements xny with n an integer ≥0.
By Definition 2 (B), x∈H and H∩M2({x})=∅. If w∈H∩M({x}), where n=l(w)≥3, the elements α(w) and β(w) also belong to H∩M({x}) by Definition 2 (C). It immediately follows by induction on n that H∩Mn({x})=∅ for n≥2, whence (a).
We now prove (b). By Definition 2 (B), y∈H and xy∈H. We show by induction on n that xny∈H for n an integer ≥2. Now xny=x(x(xn−2y)) and the induction hypothesis implies that xn−2y∈H. Now l(x)<l(xn−2y) for n>2 and x<y, whence x<xn−2y in any case; condition (C) of Definition 2 shows that xny∈H. On the other hand, certainly dy(xny)=1. Conversely, let w∈H∩M({x,y}), with dy(w)=1. If l(w)=1, then w=y; if l(w)=2, then w=xy by Definition 2 (B). If l(w)≥3, then w=a(bc), with a,b,c,bc in H∩M({x,y}) (Definition 2 (C)). dy(bc)=0 is impossible, since this would imply bc∈M({x}), which is impossible by (a). Hence dy(bc)=1 and dy(a)=0, whence a=x by (a). It follows immediately by induction on n=l(w) that w=xn−1y, which completes the proof of (b).
Corollary
If Card X ≥2, then H∩Mn(X)=∅ for every integer n≥1.
Proposition 13
Let X be a finite set with at least two elements. Let H denote a Hall set relative to X. Then there exist a strictly increasing bijection p↦wp of N onto H and a sequence (Pp)p∈N of subsets of H with the following properties: (a) P0=X. (b) For every integer p≥0, wp∈Pp. (c) For every integer n≥1, there exists an integer p(n) such that every element of Pp is of length >n for all p≥p(n). (d) For every integer p≥0, the set Pp+1 consists of the elements of the form wpiw, where i≥0, w∈Pp and w=wp.
As X is finite, each of the sets Mn(X) is finite. Let Hn=H∩Mn(X) for all n≥1. The Corollary to Proposition 12 shows that the finite set Hn is non-empty. Let un be the cardinal of Hn; let v0=0 and vn=u1+⋯+un for n≥1. As Hn is a totally ordered finite set, there exists a strictly increasing bijection p↦wp of the interval [vn−1,vn−1] of N onto Hn. It is immediate that p↦wp is a strictly increasing bijection of N onto H.
Let P0=X and for every integer p≥1 let Pp be the set of elements w of H such that w≥wp, and, either w∈X, or α(w)<wp (note that if w is of length ≥2 the relation w∈H implies α(w)∈H by condition (C) of Definition 2). Then wp∈Pp; this is clear if wp∈X and follows from the inequality l(α(wp))<l(wp) and condition (A) of Definition 2 when wp∈/X.
Hence conditions (a) and (b) are satisfied.
Let n be an integer ≥1 and let p≥vn. For all w∈Pp,l(w)≥l(wp)>n by the very definition of the mapping p↦wp. This establishes (c).
We now show that every element of the form u=wpiw with i≥0,w∈Pp and w=wp belongs to Pp+1. If i=0, then l(u)>l(wp), whence u>wp and u≥wp+1; then u∈/X and α(u)=wp<wp+1, whence u∈Pp+1. If i=0, then u∈Pp and u=wp; then u>wp, whence u≥wp+1; if u does not belong to X, then α(w)<wp, whence α(w)<wp+1; then again u∈Pp+1.
Conversely, let u∈Pp+1. We distinguish two cases:
(α) There exists no element v of M(X) such that u=wpv. By definition of Pp+1, u>wp. Further, if u∈/X, then α(u)=wp by the given hypothesis and α(u)<wp+1 since u∈Pp+1; hence α(u)<wp. Hence u∈Pp and u=wp.
(β) There exists v in M(X) such that u=wpv. By Definition 2, of necessity, either wp∈X,v∈X and wp<v, or v∈/X and α(v)≤wp<v. In either case, v∈Pp+1.
Then there exist an integer i≥0 and an element w of M(X) such that u=wpiw, and either w∈X or w∈/X and α(w)=wp. If i=0, we have case (α) above, whence w∈Pp and w=wp. If i>0, the proof of (β) above establishes, by induction on i, the relations w∈Pp+1 and w=wp. Suppose w∈/X; from w∈Pp+1 it follows that α(w)≤wp and as α(w)=wp, we conclude that w∈Pp. This completes the proof of (d).
Example
Suppose that X has two elements x,y; let X be ordered such that x<y. The construction given in the proof of Proposition 11 gives a set H with 14 elements of length ≤5 given in the following table:
(The elements of H have been numbered according to the total ordering chosen on each Hn.)
11. Hall bases of a free Lie algebra
We preserve the notation of the preceding no.
Theorem 1
Let H be a Hall set relative to X and Ψ the canonical mapping of M(X) into the free Lie algebra L(X). The restriction of Ψ to H is a basis of the module L(X).
For every element w of H we write wˉ=Ψ(w).
(A) The case where X is finite.
If X is empty, so are M(X) and therefore H and L(X) is zero. If X has a single element x, H∩Mn(X) is empty for n≥2 (Proposition 12 (a)). Therefore, H={x}; we know also (no. 2, Remark) that the module L(X) is free and has basis {xˉ}. The theorem is therefore true when X has at most one element.
Suppose henceforth that X has at least two elements; choose sequences (wp) and (Pp) with the properties stated in Proposition 13. For every integer p≥0, let Lp denote the submodule of L(X) generated by the elements wˉi with 0≤i<p and gp the Lie subalgebra of L(X) generated by the family (uˉ)u∈Pp.
Lemma 2
For every integer p≥0, the module Lp admits the family (wˉi)0≤i<p as basis, the Lie algebra gp admits (uˉ)u∈Pp as basic family and the module L(X) is the direct sum of Lp and gp.
L0={0} and g0=L(X) and the lemma is true for p=0. We argue by induction on p. Suppose then that the lemma is true for some integer p≥0. Let ui,w=(adwˉp)i.wˉ=Ψ(wpiw) for i≥0,w∈Pp,w=wp. By the Corollary to Proposition 10 of no. 9, the free Lie algebra gp is the direct sum of the module Tp of basis {wˉp} and a Lie subalgebra hp admitting
F=(ui,w)i≥0,w∈Pp,w=wp
as basic family. By Proposition 13 (d), the family (uˉ)u∈Pp+1 is equal to F and hence is a basic family of hp=gp+1. Hence L(X)=Lp⊕Tp⊕gp+1 and, as Lp+1=Lp+Tp, L(X)=Lp+1⊕gp+1 and (wˉ0,wˉ1,…,wˉp−1,wˉp) is a basis of the module Lp+1.
Let n be a positive integer. By Proposition 13 (c) there exists an integer p(n) such that Pp has only elements of length >n for p≥p(n). For p≥p(n), the Lie subalgebra gp of L(X) is generated by elements of degree >n and hence Ln(X)∩gp={0}. On the other hand, the elements wˉi of L(X) are homogeneous and the family (wi)0≤i<p is a basis of a supplementary module of gp. It follows immediately that the family of elements wˉi of degree n is a basis of the module Ln(X) and that the sequence (wˉi)i≥0 is a basis of the module L(X).
(B) General case.
If S is a subset of X, recall that M(S) is identified with the submagna of M(X) generated by S and L(S) is identified with the Lie subalgebra of L(X) generated by S; we have seen that if w∈M(S) is of length ≥2 then α(w)∈M(S) and β(w)∈M(S). It follows immediately that H∩M(S) is a Hall set relative to S.
For every finite subset Φ of H there exists a finite subset S of X such that
Φ ⊂ M(S). Case (A) then shows that the elements wˉ with w∈Φ are linearly independent in L(S) and hence in L(X). Therefore the family (wˉ)w∈H is free.
For every element a of L(X) there exists a finite subset S of X such that a∈L(S). By case (A), the subset Ψ′(H∩M(S)) of Ψ′(H) generates the module L(S) and hence a is a linear combination of elements of Ψ′(H). Hence Ψ′(H) generates the module L(X), which completes the proof.
Corollary
The module* L(X)is free and so is each of the submodulesLα(X)whereα∈N(X)andLn(X)wheren∈N. The modulesLα(X)are of finite rank and so are the modulesLn(X)ifXis finite.
There exists a Hall set H relative to X (Proposition 11). For all w∈H, the element Ψ′(w) of L(X) belongs to one of the modules Lα(X) (with α∈N(X)) and the module L(X) is the direct sum of the submodules Lα(X). Further, for all α∈N(X), the set of elements of M(X) whose canonical image in N(X) is equal to α is finite; this shows that each of the modules Lα(X) is free and of finite rank and that L(X) is free. Now Ln(X)=∑∣α∣=nLα(X) and hence Ln(X) is free; when X is finite, the set of α∈N(X) such that ∣α∣=n is finite and hence Ln(X) is then of finite rank.
Definition 3
A Hall basis of a free Lie algebra* L(X)is any basis ofL(X)which is the canonical image of a Hall set relative toX.
Remark
Suppose that X consists of two distinct elements x and y and let L(⋅,1) be the submodule of L(X) the sum of the Lα(X) where α∈NX and α(y)=1. It follows immediately from Theorem 1 and Proposition 12 of no. 10 that the elements of (adx)n.y where n is an integer ⩾0 form a basis of the submodule L(⋅,1). It follows that the restriction toL(⋅,1)of the mapping adxis injective.