Free Lie Algebras

AUTHORS:

• Travis Scrimshaw (2013-05-03): Initial version

REFERENCES:

• [Bou1989]

• [Reu2003]

class sage.algebras.lie_algebras.free_lie_algebra.FreeLieAlgebra(R, names, index_set)

Bases: Parent, UniqueRepresentation

The free Lie algebra of a set $X$.

The free Lie algebra ${\mathfrak{g}}_X$ of a set $X$ is the Lie algebra with generators $\{g_x{\}}_{x\in X}$ where there are no other relations beyond the defining relations. This can be constructed as the free magmatic algebra $M_X$ quotiented by the ideal generated by $(xx,xy+yx,x(yz)+y(zx)+z(xy))$.

EXAMPLES:

We first construct the free Lie algebra in the Hall basis:

Sage

sage: L = LieAlgebra(QQ, 'x,y,z')
sage: H = L.Hall()
sage: x,y,z = H.gens()
sage: h_elt = H([x, [y, z]]) + H([x - H([y, x]), H([x, z])]); h_elt
[x, [x, z]] + [y, [x, z]] - [z, [x, y]] + [[x, y], [x, z]]

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, 'x,y,z')
>>> H = L.Hall()
>>> x,y,z = H.gens()
>>> h_elt = H([x, [y, z]]) + H([x - H([y, x]), H([x, z])]); h_elt
[x, [x, z]] + [y, [x, z]] - [z, [x, y]] + [[x, y], [x, z]]

Sage Live

L = LieAlgebra(QQ, 'x,y,z')
H = L.Hall()
x,y,z = H.gens()
h_elt = H([x, [y, z]]) + H([x - H([y, x]), H([x, z])]); h_elt

We can also use the Lyndon basis and go between the two:

Sage

sage: Lyn = L.Lyndon()
sage: l_elt = Lyn([x, [y, z]]) + Lyn([x - Lyn([y, x]), Lyn([x, z])]); l_elt
[x, [x, z]] + [[x, y], [x, z]] + [x, [y, z]]
sage: Lyn(h_elt) == l_elt
True
sage: H(l_elt) == h_elt
True

Python

>>> from sage.all import *
>>> Lyn = L.Lyndon()
>>> l_elt = Lyn([x, [y, z]]) + Lyn([x - Lyn([y, x]), Lyn([x, z])]); l_elt
[x, [x, z]] + [[x, y], [x, z]] + [x, [y, z]]
>>> Lyn(h_elt) == l_elt
True
>>> H(l_elt) == h_elt
True

Sage Live

Lyn = L.Lyndon()
l_elt = Lyn([x, [y, z]]) + Lyn([x - Lyn([y, x]), Lyn([x, z])]); l_elt
Lyn(h_elt) == l_elt
H(l_elt) == h_elt

class Hall(lie)

Bases: FreeLieBasis_abstract

The free Lie algebra in the Hall basis.

The basis keys are objects of class LieObject, each of which is either a LieGenerator (in degree $1$) or a GradedLieBracket (in degree $>1$).

graded_basis(k)

Return the basis for the k-th graded piece of self.

EXAMPLES:

Sage

sage: L = LieAlgebra(QQ, 'x,y,z')
sage: H = L.Hall()
sage: H.graded_basis(2)
([x, y], [x, z], [y, z])
sage: H.graded_basis(4)
([x, [x, [x, y]]], [x, [x, [x, z]]],
 [y, [x, [x, y]]], [y, [x, [x, z]]],
 [y, [y, [x, y]]], [y, [y, [x, z]]],
 [y, [y, [y, z]]], [z, [x, [x, y]]],
 [z, [x, [x, z]]], [z, [y, [x, y]]],
 [z, [y, [x, z]]], [z, [y, [y, z]]],
 [z, [z, [x, y]]], [z, [z, [x, z]]],
 [z, [z, [y, z]]], [[x, y], [x, z]],
 [[x, y], [y, z]], [[x, z], [y, z]])

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, 'x,y,z')
>>> H = L.Hall()
>>> H.graded_basis(Integer(2))
([x, y], [x, z], [y, z])
>>> H.graded_basis(Integer(4))
([x, [x, [x, y]]], [x, [x, [x, z]]],
 [y, [x, [x, y]]], [y, [x, [x, z]]],
 [y, [y, [x, y]]], [y, [y, [x, z]]],
 [y, [y, [y, z]]], [z, [x, [x, y]]],
 [z, [x, [x, z]]], [z, [y, [x, y]]],
 [z, [y, [x, z]]], [z, [y, [y, z]]],
 [z, [z, [x, y]]], [z, [z, [x, z]]],
 [z, [z, [y, z]]], [[x, y], [x, z]],
 [[x, y], [y, z]], [[x, z], [y, z]])

Sage Live

L = LieAlgebra(QQ, 'x,y,z')
H = L.Hall()
H.graded_basis(2)
H.graded_basis(4)

class Lyndon(lie)

Bases: FreeLieBasis_abstract

The free Lie algebra in the Lyndon basis.

The basis keys are objects of class LieObject, each of which is either a LieGenerator (in degree $1$) or a LyndonBracket (in degree $>1$).

graded_basis(k)

Return the basis for the k-th graded piece of self.

EXAMPLES:

Sage

sage: L = LieAlgebra(QQ, 'x', 3)
sage: Lyn = L.Lyndon()
sage: Lyn.graded_basis(1)
(x0, x1, x2)
sage: Lyn.graded_basis(2)
([x0, x1], [x0, x2], [x1, x2])
sage: Lyn.graded_basis(4)
([x0, [x0, [x0, x1]]],
 [x0, [x0, [x0, x2]]],
 [x0, [[x0, x1], x1]],
 [x0, [x0, [x1, x2]]],
 [x0, [[x0, x2], x1]],
 [x0, [[x0, x2], x2]],
 [[x0, x1], [x0, x2]],
 [[[x0, x1], x1], x1],
 [x0, [x1, [x1, x2]]],
 [[x0, [x1, x2]], x1],
 [x0, [[x1, x2], x2]],
 [[[x0, x2], x1], x1],
 [[x0, x2], [x1, x2]],
 [[[x0, x2], x2], x1],
 [[[x0, x2], x2], x2],
 [x1, [x1, [x1, x2]]],
 [x1, [[x1, x2], x2]],
 [[[x1, x2], x2], x2])

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, 'x', Integer(3))
>>> Lyn = L.Lyndon()
>>> Lyn.graded_basis(Integer(1))
(x0, x1, x2)
>>> Lyn.graded_basis(Integer(2))
([x0, x1], [x0, x2], [x1, x2])
>>> Lyn.graded_basis(Integer(4))
([x0, [x0, [x0, x1]]],
 [x0, [x0, [x0, x2]]],
 [x0, [[x0, x1], x1]],
 [x0, [x0, [x1, x2]]],
 [x0, [[x0, x2], x1]],
 [x0, [[x0, x2], x2]],
 [[x0, x1], [x0, x2]],
 [[[x0, x1], x1], x1],
 [x0, [x1, [x1, x2]]],
 [[x0, [x1, x2]], x1],
 [x0, [[x1, x2], x2]],
 [[[x0, x2], x1], x1],
 [[x0, x2], [x1, x2]],
 [[[x0, x2], x2], x1],
 [[[x0, x2], x2], x2],
 [x1, [x1, [x1, x2]]],
 [x1, [[x1, x2], x2]],
 [[[x1, x2], x2], x2])

Sage Live

L = LieAlgebra(QQ, 'x', 3)
Lyn = L.Lyndon()
Lyn.graded_basis(1)
Lyn.graded_basis(2)
Lyn.graded_basis(4)

pbw_basis(**kwds)

Return the Poincare-Birkhoff-Witt basis corresponding to self.

EXAMPLES:

Sage

sage: L = LieAlgebra(QQ, 'x,y,z', 3)
sage: Lyn = L.Lyndon()
sage: Lyn.pbw_basis()
The Poincare-Birkhoff-Witt basis of Free Algebra on 3 generators (x, y, z) over Rational Field

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, 'x,y,z', Integer(3))
>>> Lyn = L.Lyndon()
>>> Lyn.pbw_basis()
The Poincare-Birkhoff-Witt basis of Free Algebra on 3 generators (x, y, z) over Rational Field

Sage Live

L = LieAlgebra(QQ, 'x,y,z', 3)
Lyn = L.Lyndon()
Lyn.pbw_basis()

poincare_birkhoff_witt_basis(**kwds)

Return the Poincare-Birkhoff-Witt basis corresponding to self.

EXAMPLES:

Sage

sage: L = LieAlgebra(QQ, 'x,y,z', 3)
sage: Lyn = L.Lyndon()
sage: Lyn.pbw_basis()
The Poincare-Birkhoff-Witt basis of Free Algebra on 3 generators (x, y, z) over Rational Field

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, 'x,y,z', Integer(3))
>>> Lyn = L.Lyndon()
>>> Lyn.pbw_basis()
The Poincare-Birkhoff-Witt basis of Free Algebra on 3 generators (x, y, z) over Rational Field

Sage Live

L = LieAlgebra(QQ, 'x,y,z', 3)
Lyn = L.Lyndon()
Lyn.pbw_basis()

a_realization()

Return a particular realization of self (the Lyndon basis).

EXAMPLES:

Sage

sage: L.<x, y> = LieAlgebra(QQ)
sage: L.a_realization()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, names=('x', 'y',)); (x, y,) = L._first_ngens(2)
>>> L.a_realization()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis

Sage Live

L.<x, y> = LieAlgebra(QQ)
L.a_realization()

gen(i)

Return the i-th generator of self in the Lyndon basis.

EXAMPLES:

Sage

sage: L.<x, y> = LieAlgebra(QQ)
sage: L.gen(0)
x
sage: L.gen(1)
y
sage: L.gen(0).parent()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, names=('x', 'y',)); (x, y,) = L._first_ngens(2)
>>> L.gen(Integer(0))
x
>>> L.gen(Integer(1))
y
>>> L.gen(Integer(0)).parent()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis

Sage Live

L.<x, y> = LieAlgebra(QQ)
L.gen(0)
L.gen(1)
L.gen(0).parent()

gens()

Return the generators of self in the Lyndon basis.

EXAMPLES:

Sage

sage: L.<x, y> = LieAlgebra(QQ)
sage: L.gens()
(x, y)
sage: L.gens()[0].parent()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, names=('x', 'y',)); (x, y,) = L._first_ngens(2)
>>> L.gens()
(x, y)
>>> L.gens()[Integer(0)].parent()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis

Sage Live

L.<x, y> = LieAlgebra(QQ)
L.gens()
L.gens()[0].parent()

lie_algebra_generators()

Return the Lie algebra generators of self in the Lyndon basis.

EXAMPLES:

Sage

sage: L.<x, y> = LieAlgebra(QQ)
sage: L.lie_algebra_generators()
Finite family {'x': x, 'y': y}
sage: L.lie_algebra_generators()['x'].parent()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, names=('x', 'y',)); (x, y,) = L._first_ngens(2)
>>> L.lie_algebra_generators()
Finite family {'x': x, 'y': y}
>>> L.lie_algebra_generators()['x'].parent()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis

Sage Live

L.<x, y> = LieAlgebra(QQ)
L.lie_algebra_generators()
L.lie_algebra_generators()['x'].parent()

class sage.algebras.lie_algebras.free_lie_algebra.FreeLieAlgebraBases(base)

Bases: Category_realization_of_parent

The category of bases of a free Lie algebra.

super_categories()

The super categories of self.

EXAMPLES:

Sage

sage: from sage.algebras.lie_algebras.free_lie_algebra import FreeLieAlgebraBases
sage: L.<x, y> = LieAlgebra(QQ)
sage: bases = FreeLieAlgebraBases(L)
sage: bases.super_categories()
[Category of Lie algebras with basis over Rational Field,
 Category of realizations of Free Lie algebra generated by (x, y) over Rational Field]

Python

>>> from sage.all import *
>>> from sage.algebras.lie_algebras.free_lie_algebra import FreeLieAlgebraBases
>>> L = LieAlgebra(QQ, names=('x', 'y',)); (x, y,) = L._first_ngens(2)
>>> bases = FreeLieAlgebraBases(L)
>>> bases.super_categories()
[Category of Lie algebras with basis over Rational Field,
 Category of realizations of Free Lie algebra generated by (x, y) over Rational Field]

Sage Live

from sage.algebras.lie_algebras.free_lie_algebra import FreeLieAlgebraBases
L.<x, y> = LieAlgebra(QQ)
bases = FreeLieAlgebraBases(L)
bases.super_categories()

class sage.algebras.lie_algebras.free_lie_algebra.FreeLieBasis_abstract(lie, basis_name)

Bases: FinitelyGeneratedLieAlgebra, IndexedGenerators, BindableClass

Abstract base class for all bases of a free Lie algebra.

Element

alias of FreeLieAlgebraElement

basis()

Return the basis of self.

EXAMPLES:

Sage

sage: L = LieAlgebra(QQ, 3, 'x')
sage: L.Hall().basis()
Disjoint union of Lazy family (graded basis(i))_{i in Positive integers}

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, Integer(3), 'x')
>>> L.Hall().basis()
Disjoint union of Lazy family (graded basis(i))_{i in Positive integers}

Sage Live

L = LieAlgebra(QQ, 3, 'x')
L.Hall().basis()

graded_basis(k)

Return the basis for the k-th graded piece of self.

EXAMPLES:

Sage

sage: H = LieAlgebra(QQ, 3, 'x').Hall()
sage: H.graded_basis(2)
([x0, x1], [x0, x2], [x1, x2])

Python

>>> from sage.all import *
>>> H = LieAlgebra(QQ, Integer(3), 'x').Hall()
>>> H.graded_basis(Integer(2))
([x0, x1], [x0, x2], [x1, x2])

Sage Live

H = LieAlgebra(QQ, 3, 'x').Hall()
H.graded_basis(2)

graded_dimension(k)

Return the dimension of the k-th graded piece of self.

The $k$-th graded part of a free Lie algebra on $n$ generators has dimension

$$\frac{1}{k}\sum _{d\mid k}\mu (d)n^{k/d},$$

where $\mu$ is the Mobius function.

REFERENCES:

[MKO1998]

EXAMPLES:

Sage

sage: L = LieAlgebra(QQ, 'x', 3)
sage: H = L.Hall()
sage: [H.graded_dimension(i) for i in range(1, 11)]
[3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880]
sage: H.graded_dimension(0)
0

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, 'x', Integer(3))
>>> H = L.Hall()
>>> [H.graded_dimension(i) for i in range(Integer(1), Integer(11))]
[3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880]
>>> H.graded_dimension(Integer(0))
0

Sage Live

L = LieAlgebra(QQ, 'x', 3)
H = L.Hall()
[H.graded_dimension(i) for i in range(1, 11)]
H.graded_dimension(0)

is_abelian()

Return True if this is an abelian Lie algebra.

EXAMPLES:

Sage

sage: L = LieAlgebra(QQ, 3, 'x')
sage: L.is_abelian()
False
sage: L = LieAlgebra(QQ, 1, 'x')
sage: L.is_abelian()
True

Python

>>> from sage.all import *
>>> L = LieAlgebra(QQ, Integer(3), 'x')
>>> L.is_abelian()
False
>>> L = LieAlgebra(QQ, Integer(1), 'x')
>>> L.is_abelian()
True

Sage Live

L = LieAlgebra(QQ, 3, 'x')
L.is_abelian()
L = LieAlgebra(QQ, 1, 'x')
L.is_abelian()

monomial(x)

Return the monomial indexed by x.

EXAMPLES:

Sage

sage: Lyn = LieAlgebra(QQ, 'x,y').Lyndon()
sage: x = Lyn.monomial('x'); x
x
sage: x.parent() is Lyn
True

Python

>>> from sage.all import *
>>> Lyn = LieAlgebra(QQ, 'x,y').Lyndon()
>>> x = Lyn.monomial('x'); x
x
>>> x.parent() is Lyn
True

Sage Live

Lyn = LieAlgebra(QQ, 'x,y').Lyndon()
x = Lyn.monomial('x'); x
x.parent() is Lyn

sage.algebras.lie_algebras.free_lie_algebra.is_lyndon(w)

Modified form of Word(w).is_lyndon() which uses the default order (this will either be the natural integer order or lex order) and assumes the input w behaves like a nonempty list.

This function here is designed for speed.

EXAMPLES:

Sage

sage: from sage.algebras.lie_algebras.free_lie_algebra import is_lyndon
sage: is_lyndon([1])
True
sage: is_lyndon([1,3,1])
False
sage: is_lyndon((2,2,3))
True
sage: all(is_lyndon(x) for x in LyndonWords(3, 5))
True
sage: all(is_lyndon(x) for x in LyndonWords(6, 4))
True

Python

>>> from sage.all import *
>>> from sage.algebras.lie_algebras.free_lie_algebra import is_lyndon
>>> is_lyndon([Integer(1)])
True
>>> is_lyndon([Integer(1),Integer(3),Integer(1)])
False
>>> is_lyndon((Integer(2),Integer(2),Integer(3)))
True
>>> all(is_lyndon(x) for x in LyndonWords(Integer(3), Integer(5)))
True
>>> all(is_lyndon(x) for x in LyndonWords(Integer(6), Integer(4)))
True

Sage Live

from sage.algebras.lie_algebras.free_lie_algebra import is_lyndon
is_lyndon([1])
is_lyndon([1,3,1])
is_lyndon((2,2,3))
all(is_lyndon(x) for x in LyndonWords(3, 5))
all(is_lyndon(x) for x in LyndonWords(6, 4))

Make live