Free Lie Algebras

AUTHORS:

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

REFERENCES:

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

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 \(\bigl( xx, xy + yx, x(yz) + y(zx) + z(xy) \bigr)\).

EXAMPLES:

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

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]]
>>> 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]]

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

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
>>> 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
class Hall(lie)[source]

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)[source]

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

EXAMPLES:

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]])
>>> 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]])
class Lyndon(lie)[source]

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)[source]

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

EXAMPLES:

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])
>>> 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])
pbw_basis(**kwds)[source]

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

EXAMPLES:

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
>>> 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
poincare_birkhoff_witt_basis(**kwds)[source]

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

EXAMPLES:

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
>>> 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
a_realization()[source]

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

EXAMPLES:

sage: L.<x, y> = LieAlgebra(QQ)
sage: L.a_realization()
Free Lie algebra generated by (x, y) over Rational Field in the Lyndon basis
>>> 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
gen(i)[source]

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

EXAMPLES:

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
>>> 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
gens()[source]

Return the generators of self in the Lyndon basis.

EXAMPLES:

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
>>> 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
lie_algebra_generators()[source]

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

EXAMPLES:

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
>>> 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
class sage.algebras.lie_algebras.free_lie_algebra.FreeLieAlgebraBases(base)[source]

Bases: Category_realization_of_parent

The category of bases of a free Lie algebra.

super_categories()[source]

The super categories of self.

EXAMPLES:

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]
>>> 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]
class sage.algebras.lie_algebras.free_lie_algebra.FreeLieBasis_abstract(lie, basis_name)[source]

Bases: FinitelyGeneratedLieAlgebra, IndexedGenerators, BindableClass

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

Element[source]

alias of FreeLieAlgebraElement

basis()[source]

Return the basis of self.

EXAMPLES:

sage: L = LieAlgebra(QQ, 3, 'x')
sage: L.Hall().basis()
Disjoint union of Lazy family (graded basis(i))_{i in Positive integers}
>>> 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}
graded_basis(k)[source]

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

EXAMPLES:

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

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: 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
>>> 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
is_abelian()[source]

Return True if this is an abelian Lie algebra.

EXAMPLES:

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

Return the monomial indexed by x.

EXAMPLES:

sage: Lyn = LieAlgebra(QQ, 'x,y').Lyndon()
sage: x = Lyn.monomial('x'); x
x
sage: x.parent() is Lyn
True
>>> from sage.all import *
>>> Lyn = LieAlgebra(QQ, 'x,y').Lyndon()
>>> x = Lyn.monomial('x'); x
x
>>> x.parent() is Lyn
True
sage.algebras.lie_algebras.free_lie_algebra.is_lyndon(w)[source]

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: 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
>>> 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