Free Pre-Lie Algebras

AUTHORS:

  • Florent Hivert, Frédéric Chapoton (2011)
class sage.combinat.free_prelie_algebra.FreePreLieAlgebra(R, names=None)

Bases: sage.combinat.free_module.CombinatorialFreeModule

The free pre-Lie algebra.

Pre-Lie algebras are non-associative algebras, where the product * satisfies

(x * y) * z - x * (y * z) = (x * z) * y - x * (z * y).

We use here the convention where the associator

(x, y, z) := (x * y) * z - x * (y * z)

is symmetric in its two rightmost arguments. This is sometimes called a right pre-Lie algebra.

They have appeared in numerical analysis and deformation theory.

The free Pre-Lie algebra on a given set E has an explicit description using rooted trees, just as the free associative algebra can be described using words. The underlying vector space has a basis indexed by finite rooted trees endowed with a map from their vertices to E. In this basis, the product of two (decorated) rooted trees S
* T is the sum over vertices of S of the rooted tree obtained by adding one edge from the root of T to the given vertex of S. The root of these trees is taken to be the root of S. The free pre-Lie algebra can also be considered as the free algebra over the PreLie operad.

Warning

The usual binary operator * can be used for the pre-Lie product. Beware that it but must be parenthesized properly, as the pre-Lie product is not associative. By default, a multiple product will be taken with left parentheses.

EXAMPLES:

sage: F = algebras.FreePreLie(ZZ, 'xyz')
sage: x,y,z = F.gens()
sage: (x * y) * z
B[x[y[z[]]]] + B[x[y[], z[]]]
sage: (x * y) * z - x * (y * z) == (x * z) * y - x * (z * y)
True

The free pre-Lie algebra is non-associative:

sage: x * (y * z) == (x * y) * z
False

The default product is with left parentheses:

sage: x * y * z == (x * y) * z
True
sage: x * y * z * x == ((x * y) * z) * x
True

The NAP product as defined in [Liv] is also implemented on the same vector space:

sage: N = F.nap_product
sage: N(x*y,z*z)
B[x[y[], z[z[]]]]

When there is only one generator, unlabelled trees are used instead:

sage: F1 = algebras.FreePreLie(QQ, 'w')
sage: w = F1.gen(0); w
B[[]]
sage: w * w * w * w
B[[[[[]]]]] + B[[[[], []]]] + 3*B[[[], [[]]]] + B[[[], [], []]]

REFERENCES:

[ChLi]F. Chapoton and M. Livernet, Pre-Lie algebras and the rooted trees operad, International Math. Research Notices (2001) no 8, pages 395-408.
[Liv]M. Livernet, A rigidity theorem for pre-Lie algebras, J. Pure Appl. Algebra 207 (2006), no 1, pages 1-18.
algebra_generators()

Return the generators of this algebra.

These are the rooted trees with just one vertex.

EXAMPLES:

sage: A = algebras.FreePreLie(ZZ, 'fgh'); A
Free PreLie algebra on 3 generators ['f', 'g', 'h']
 over Integer Ring
sage: list(A.algebra_generators())
[B[f[]], B[g[]], B[h[]]]

sage: A = algebras.FreePreLie(QQ, ['x1','x2'])
sage: list(A.algebra_generators())
[B[x1[]], B[x2[]]]
an_element()

Return an element of self.

EXAMPLES:

sage: A = algebras.FreePreLie(QQ, 'xy')
sage: A.an_element()
B[x[x[x[x[]]]]] + B[x[x[], x[x[]]]]
degree_on_basis(t)

Return the degree of a rooted tree in the free Pre-Lie algebra.

This is the number of vertices.

EXAMPLES:

sage: A = algebras.FreePreLie(QQ,'@')
sage: RT = A.basis().keys()
sage: A.degree_on_basis(RT([RT([])]))
2
gen(i)

Return the i-th generator of the algebra.

INPUT:

  • i – an integer

EXAMPLES:

sage: F = algebras.FreePreLie(ZZ, 'xyz')
sage: F.gen(0)
B[x[]]

sage: F.gen(4)
Traceback (most recent call last):
...
IndexError: argument i (= 4) must be between 0 and 2
gens()

Return the generators of self (as an algebra).

EXAMPLES:

sage: A = algebras.FreePreLie(ZZ, 'fgh')
sage: A.gens()
(B[f[]], B[g[]], B[h[]])
nap_product()

Return the NAP product.

EXAMPLES:

sage: A = algebras.FreePreLie(QQ, '@')
sage: RT = A.basis().keys()
sage: x = A(RT([RT([])]))
sage: A.nap_product(x, x)
B[[[], [[]]]]
nap_product_on_basis(x, y)

Return the NAP product of two trees.

This is the grafting of the root of y over the root of x. The root of the resulting tree is the root of x.

See also

nap_product()

EXAMPLES:

sage: A = algebras.FreePreLie(QQ, '@')
sage: RT = A.basis().keys()
sage: x = RT([RT([])])
sage: A.nap_product_on_basis(x, x)
B[[[], [[]]]]
pre_Lie_product()

Return the pre-Lie product.

EXAMPLES:

sage: A = algebras.FreePreLie(QQ, '@')
sage: RT = A.basis().keys()
sage: x = A(RT([RT([])]))
sage: A.pre_Lie_product(x, x)
B[[[[[]]]]] + B[[[], [[]]]]
pre_Lie_product_on_basis(x, y)

Return the pre-Lie product of two trees.

This is the sum over all graftings of the root of y over a vertex of x. The root of the resulting trees is the root of x.

EXAMPLES:

sage: A = algebras.FreePreLie(QQ, '@')
sage: RT = A.basis().keys()
sage: x = RT([RT([])])
sage: A.product_on_basis(x, x)
B[[[[[]]]]] + B[[[], [[]]]]
product_on_basis(x, y)

Return the pre-Lie product of two trees.

This is the sum over all graftings of the root of y over a vertex of x. The root of the resulting trees is the root of x.

EXAMPLES:

sage: A = algebras.FreePreLie(QQ, '@')
sage: RT = A.basis().keys()
sage: x = RT([RT([])])
sage: A.product_on_basis(x, x)
B[[[[[]]]]] + B[[[], [[]]]]
some_elements()

Return some elements of the free pre-Lie algebra.

EXAMPLES:

sage: A = algebras.FreePreLie(QQ,'@')
sage: A.some_elements()
[B[[]], B[[[]]], B[[[[[]]]]] + B[[[], [[]]]], B[[[[]]]] + B[[[], []]], B[[[]]]]

With several generators:

sage: A = algebras.FreePreLie(QQ, 'xy')
sage: A.some_elements()
[B[x[]],
 B[x[x[]]],
 B[x[x[x[x[]]]]] + B[x[x[], x[x[]]]],
 B[x[x[x[]]]] + B[x[x[], x[]]],
 B[x[x[y[]]]] + B[x[x[], y[]]]]
variable_names()

Return the names of the variables.

EXAMPLES:

sage: R = algebras.FreePreLie(QQ, 'xy')
sage: R.variable_names()
{'x', 'y'}