# Free Pre-Lie Algebras¶

AUTHORS:

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

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$$.

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'}