Free Pre-Lie Algebras¶

AUTHORS:

Florent Hivert, Frédéric Chapoton (2011)

class sage.combinat.free_prelie_algebra.FreePreLieAlgebra(R, names=None)[source]¶

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

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

Python

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

Sage Live

F = algebras.FreePreLie(ZZ, 'xyz')
x,y,z = F.gens()
(x * y) * z
(x * y) * z - x * (y * z) == (x * z) * y - x * (z * y)

The free pre-Lie algebra is non-associative:

Sage

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

Python

>>> from sage.all import *
>>> x * (y * z) == (x * y) * z
False

Sage Live

x * (y * z) == (x * y) * z

The default product is with left parentheses:

Sage

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

Python

>>> from sage.all import *
>>> x * y * z == (x * y) * z
True
>>> x * y * z * x == ((x * y) * z) * x
True

Sage Live

x * y * z == (x * y) * z
x * y * z * x == ((x * y) * z) * x

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

Sage

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

Python

>>> from sage.all import *
>>> N = F.nap_product
>>> N(x*y,z*z)
B[x[y[], z[z[]]]]

Sage Live

N = F.nap_product
N(x*y,z*z)

When None is given as input, unlabelled trees are used instead:

Sage

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

Python

>>> from sage.all import *
>>> F1 = algebras.FreePreLie(QQ, None)
>>> w = F1.gen(Integer(0)); w
B[[]]
>>> w * w * w * w
B[[[[[]]]]] + B[[[[], []]]] + 3*B[[[], [[]]]] + B[[[], [], []]]

Sage Live

F1 = algebras.FreePreLie(QQ, None)
w = F1.gen(0); w
w * w * w * w

However, it is equally possible to use labelled trees instead:

Sage

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

Python

>>> from sage.all import *
>>> F1 = algebras.FreePreLie(QQ, 'q')
>>> w = F1.gen(Integer(0)); w
B[q[]]
>>> w * w * w * w
B[q[q[q[q[]]]]] + B[q[q[q[], q[]]]] + 3*B[q[q[], q[q[]]]] + B[q[q[], q[], q[]]]

Sage Live

F1 = algebras.FreePreLie(QQ, 'q')
w = F1.gen(0); w
w * w * w * w

The set \(E\) can be infinite:

Sage

sage: F = algebras.FreePreLie(QQ, ZZ)
sage: w = F.gen(1); w
B[1[]]
sage: x = F.gen(2); x
B[-1[]]
sage: y = F.gen(3); y
B[2[]]
sage: w*x
B[1[-1[]]]
sage: (w*x)*y
B[1[-1[2[]]]] + B[1[-1[], 2[]]]
sage: w*(x*y)
B[1[-1[2[]]]]

Python

>>> from sage.all import *
>>> F = algebras.FreePreLie(QQ, ZZ)
>>> w = F.gen(Integer(1)); w
B[1[]]
>>> x = F.gen(Integer(2)); x
B[-1[]]
>>> y = F.gen(Integer(3)); y
B[2[]]
>>> w*x
B[1[-1[]]]
>>> (w*x)*y
B[1[-1[2[]]]] + B[1[-1[], 2[]]]
>>> w*(x*y)
B[1[-1[2[]]]]

Sage Live

F = algebras.FreePreLie(QQ, ZZ)
w = F.gen(1); w
x = F.gen(2); x
y = F.gen(3); y
w*x
(w*x)*y
w*(x*y)

Elements of a free pre-Lie algebra can be lifted to the universal enveloping algebra of the associated Lie algebra. The universal enveloping algebra is the Grossman-Larson Hopf algebra:

Sage

sage: F = algebras.FreePreLie(QQ,'abc')
sage: a,b,c = F.gens()
sage: (a*b+b*c).lift()
B[#[a[b[]]]] + B[#[b[c[]]]]

Python

>>> from sage.all import *
>>> F = algebras.FreePreLie(QQ,'abc')
>>> a,b,c = F.gens()
>>> (a*b+b*c).lift()
B[#[a[b[]]]] + B[#[b[c[]]]]

Sage Live

F = algebras.FreePreLie(QQ,'abc')
a,b,c = F.gens()
(a*b+b*c).lift()

Note

Variables names can be None, a list of strings, a string or an integer. When None is given, unlabelled rooted trees are used. When a single string is given, each letter is taken as a variable. See sage.combinat.words.alphabet.build_alphabet().

Warning

Beware that the underlying combinatorial free module is based either on RootedTrees or on LabelledRootedTrees, with no restriction on the labellings. This means that all code calling the basis() method would not give meaningful results, since basis() returns many “chaff” elements that do not belong to the algebra.

REFERENCES:

class Element[source]¶

Bases: IndexedFreeModuleElement

lift()[source]¶

Lift element to the Grossman-Larson algebra.

EXAMPLES:

Sage

sage: F = algebras.FreePreLie(QQ,'abc')
sage: elt = F.an_element().lift(); elt
B[#[a[a[a[a[]]]]]] + B[#[a[a[], a[a[]]]]]
sage: parent(elt)
Grossman-Larson Hopf algebra on 3 generators ['a', 'b', 'c']
over Rational Field

Python

>>> from sage.all import *
>>> F = algebras.FreePreLie(QQ,'abc')
>>> elt = F.an_element().lift(); elt
B[#[a[a[a[a[]]]]]] + B[#[a[a[], a[a[]]]]]
>>> parent(elt)
Grossman-Larson Hopf algebra on 3 generators ['a', 'b', 'c']
over Rational Field

Sage Live

F = algebras.FreePreLie(QQ,'abc')
elt = F.an_element().lift(); elt
parent(elt)

valuation()[source]¶

Return the valuation of self.

EXAMPLES:

Sage

sage: a = algebras.FreePreLie(QQ).gen(0)
sage: a.valuation()
1
sage: (a*a).valuation()
2

sage: a, b = algebras.FreePreLie(QQ,'ab').gens()
sage: (a+b).valuation()
1
sage: (a*b).valuation()
2
sage: (a*b+a).valuation()
1

Python

>>> from sage.all import *
>>> a = algebras.FreePreLie(QQ).gen(Integer(0))
>>> a.valuation()
1
>>> (a*a).valuation()
2

>>> a, b = algebras.FreePreLie(QQ,'ab').gens()
>>> (a+b).valuation()
1
>>> (a*b).valuation()
2
>>> (a*b+a).valuation()
1

Sage Live

a = algebras.FreePreLie(QQ).gen(0)
a.valuation()
(a*a).valuation()
a, b = algebras.FreePreLie(QQ,'ab').gens()
(a+b).valuation()
(a*b).valuation()
(a*b+a).valuation()

algebra_generators()[source]¶

Return the generators of this algebra.

These are the rooted trees with just one vertex.

EXAMPLES:

Sage

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

Python

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

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

Sage Live

A = algebras.FreePreLie(ZZ, 'fgh'); A
list(A.algebra_generators())
A = algebras.FreePreLie(QQ, ['x1','x2'])
list(A.algebra_generators())

an_element()[source]¶

Return an element of self.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, 'xy')
>>> A.an_element()
B[x[x[x[x[]]]]] + B[x[x[], x[x[]]]]

Sage Live

A = algebras.FreePreLie(QQ, 'xy')
A.an_element()

bracket_on_basis(x, y)[source]¶

Return the Lie bracket of two trees.

This is the commutator \([x, y] = x * y - y * x\) of the pre-Lie product.

See also

pre_Lie_product_on_basis()

EXAMPLES:

Sage

sage: A = algebras.FreePreLie(QQ, None)
sage: RT = A.basis().keys()
sage: x = RT([RT([])])
sage: y = RT([x])
sage: A.bracket_on_basis(x, y)
-B[[[[], [[]]]]] + B[[[], [[[]]]]] - B[[[[]], [[]]]]

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, None)
>>> RT = A.basis().keys()
>>> x = RT([RT([])])
>>> y = RT([x])
>>> A.bracket_on_basis(x, y)
-B[[[[], [[]]]]] + B[[[], [[[]]]]] - B[[[[]], [[]]]]

Sage Live

A = algebras.FreePreLie(QQ, None)
RT = A.basis().keys()
x = RT([RT([])])
y = RT([x])
A.bracket_on_basis(x, y)

change_ring(R)[source]¶

Return the free pre-Lie algebra in the same variables over \(R\).

INPUT:

R – a ring

EXAMPLES:

Sage

sage: A = algebras.FreePreLie(ZZ, 'fgh')
sage: A.change_ring(QQ)
Free PreLie algebra on 3 generators ['f', 'g', 'h'] over
Rational Field

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(ZZ, 'fgh')
>>> A.change_ring(QQ)
Free PreLie algebra on 3 generators ['f', 'g', 'h'] over
Rational Field

Sage Live

A = algebras.FreePreLie(ZZ, 'fgh')
A.change_ring(QQ)

construction()[source]¶

Return a pair (F, R), where F is a PreLieFunctor and \(R\) is a ring, such that F(R) returns self.

EXAMPLES:

Sage

sage: P = algebras.FreePreLie(ZZ, 'x,y')
sage: x,y = P.gens()
sage: F, R = P.construction()
sage: F
PreLie[x,y]
sage: R
Integer Ring
sage: F(ZZ) is P
True
sage: F(QQ)
Free PreLie algebra on 2 generators ['x', 'y'] over Rational Field

Python

>>> from sage.all import *
>>> P = algebras.FreePreLie(ZZ, 'x,y')
>>> x,y = P.gens()
>>> F, R = P.construction()
>>> F
PreLie[x,y]
>>> R
Integer Ring
>>> F(ZZ) is P
True
>>> F(QQ)
Free PreLie algebra on 2 generators ['x', 'y'] over Rational Field

Sage Live

P = algebras.FreePreLie(ZZ, 'x,y')
x,y = P.gens()
F, R = P.construction()
F
R
F(ZZ) is P
F(QQ)

corolla(x, y, n, N)[source]¶

Return the corolla obtained with x as root and y as leaves.

INPUT:

x, y – two elements
n – integer; width of the corolla
N – integer; truncation order (up to order N included)

OUTPUT:

the sum over all possible ways to graft n copies of y on top of x (with at most N vertices in total)

This operation can be defined by induction starting from the pre-Lie product.

EXAMPLES:

Sage

sage: A = algebras.FreePreLie(QQ)
sage: a = A.gen(0)
sage: b = A.corolla(a,a,1,4); b
B[[[]]]
sage: A.corolla(b,b,2,7)
B[[[[[]], [[]]]]] + 2*B[[[[]], [[[]]]]] + B[[[], [[]], [[]]]]

sage: A = algebras.FreePreLie(QQ, 'o')
sage: a = A.gen(0)
sage: b = A.corolla(a,a,1,4)

sage: A = algebras.FreePreLie(QQ,'ab')
sage: a, b = A.gens()
sage: A.corolla(a,b,1,4)
B[a[b[]]]
sage: A.corolla(b,a,3,4)
B[b[a[], a[], a[]]]

sage: A.corolla(a+b,a+b,2,4)
B[a[a[], a[]]] + 2*B[a[a[], b[]]] + B[a[b[], b[]]] + B[b[a[], a[]]] +
2*B[b[a[], b[]]] + B[b[b[], b[]]]

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ)
>>> a = A.gen(Integer(0))
>>> b = A.corolla(a,a,Integer(1),Integer(4)); b
B[[[]]]
>>> A.corolla(b,b,Integer(2),Integer(7))
B[[[[[]], [[]]]]] + 2*B[[[[]], [[[]]]]] + B[[[], [[]], [[]]]]

>>> A = algebras.FreePreLie(QQ, 'o')
>>> a = A.gen(Integer(0))
>>> b = A.corolla(a,a,Integer(1),Integer(4))

>>> A = algebras.FreePreLie(QQ,'ab')
>>> a, b = A.gens()
>>> A.corolla(a,b,Integer(1),Integer(4))
B[a[b[]]]
>>> A.corolla(b,a,Integer(3),Integer(4))
B[b[a[], a[], a[]]]

>>> A.corolla(a+b,a+b,Integer(2),Integer(4))
B[a[a[], a[]]] + 2*B[a[a[], b[]]] + B[a[b[], b[]]] + B[b[a[], a[]]] +
2*B[b[a[], b[]]] + B[b[b[], b[]]]

Sage Live

A = algebras.FreePreLie(QQ)
a = A.gen(0)
b = A.corolla(a,a,1,4); b
A.corolla(b,b,2,7)
A = algebras.FreePreLie(QQ, 'o')
a = A.gen(0)
b = A.corolla(a,a,1,4)
A = algebras.FreePreLie(QQ,'ab')
a, b = A.gens()
A.corolla(a,b,1,4)
A.corolla(b,a,3,4)
A.corolla(a+b,a+b,2,4)

degree_on_basis(t)[source]¶

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

This is the number of vertices.

EXAMPLES:

Sage

sage: A = algebras.FreePreLie(QQ, None)
sage: RT = A.basis().keys()
sage: A.degree_on_basis(RT([RT([])]))
2

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, None)
>>> RT = A.basis().keys()
>>> A.degree_on_basis(RT([RT([])]))
2

Sage Live

A = algebras.FreePreLie(QQ, None)
RT = A.basis().keys()
A.degree_on_basis(RT([RT([])]))

gen(i)[source]¶

Return the i-th generator of the algebra.

INPUT:

i – integer

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> F = algebras.FreePreLie(ZZ, 'xyz')
>>> F.gen(Integer(0))
B[x[]]

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

Sage Live

F = algebras.FreePreLie(ZZ, 'xyz')
F.gen(0)
F.gen(4)

gens()[source]¶

Return the generators of self (as an algebra).

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(ZZ, 'fgh')
>>> A.gens()
(B[f[]], B[g[]], B[h[]])

Sage Live

A = algebras.FreePreLie(ZZ, 'fgh')
A.gens()

group_product(x, y, n, N=10)[source]¶

Return the truncated group product of x and y.

This is a weighted sum of all corollas with up to n leaves, with x as root and y as leaves.

The result is computed up to order N (included).

When considered with infinitely many terms and infinite precision, this is an analogue of the Baker-Campbell-Hausdorff formula: it defines an associative product on the completed free pre-Lie algebra.

INPUT:

x, y – two elements
n – integer; the maximal width of corollas
N – integer (default: 10); truncation order

EXAMPLES:

In the free pre-Lie algebra with one generator:

Sage

sage: PL = algebras.FreePreLie(QQ)
sage: a = PL.gen(0)
sage: PL.group_product(a, a, 3, 3)
B[[]] + B[[[]]] + 1/2*B[[[], []]]

Python

>>> from sage.all import *
>>> PL = algebras.FreePreLie(QQ)
>>> a = PL.gen(Integer(0))
>>> PL.group_product(a, a, Integer(3), Integer(3))
B[[]] + B[[[]]] + 1/2*B[[[], []]]

Sage Live

PL = algebras.FreePreLie(QQ)
a = PL.gen(0)
PL.group_product(a, a, 3, 3)

In the free pre-Lie algebra with several generators:

Sage

sage: PL = algebras.FreePreLie(QQ,'@O')
sage: a, b = PL.gens()
sage: PL.group_product(a, b, 3, 3)
B[@[]] + B[@[O[]]] + 1/2*B[@[O[], O[]]]
sage: PL.group_product(a, b, 3, 10)
B[@[]] + B[@[O[]]] + 1/2*B[@[O[], O[]]] + 1/6*B[@[O[], O[], O[]]]

Python

>>> from sage.all import *
>>> PL = algebras.FreePreLie(QQ,'@O')
>>> a, b = PL.gens()
>>> PL.group_product(a, b, Integer(3), Integer(3))
B[@[]] + B[@[O[]]] + 1/2*B[@[O[], O[]]]
>>> PL.group_product(a, b, Integer(3), Integer(10))
B[@[]] + B[@[O[]]] + 1/2*B[@[O[], O[]]] + 1/6*B[@[O[], O[], O[]]]

Sage Live

PL = algebras.FreePreLie(QQ,'@O')
a, b = PL.gens()
PL.group_product(a, b, 3, 3)
PL.group_product(a, b, 3, 10)

nap_product()[source]¶

Return the NAP product.

See also

nap_product_on_basis()

EXAMPLES:

Sage

sage: A = algebras.FreePreLie(QQ, None)
sage: RT = A.basis().keys()
sage: x = A(RT([RT([])]))
sage: A.nap_product(x, x)
B[[[], [[]]]]

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, None)
>>> RT = A.basis().keys()
>>> x = A(RT([RT([])]))
>>> A.nap_product(x, x)
B[[[], [[]]]]

Sage Live

A = algebras.FreePreLie(QQ, None)
RT = A.basis().keys()
x = A(RT([RT([])]))
A.nap_product(x, x)

nap_product_on_basis(x, y)[source]¶

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

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

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, None)
>>> RT = A.basis().keys()
>>> x = RT([RT([])])
>>> A.nap_product_on_basis(x, x)
B[[[], [[]]]]

Sage Live

A = algebras.FreePreLie(QQ, None)
RT = A.basis().keys()
x = RT([RT([])])
A.nap_product_on_basis(x, x)

pre_Lie_product()[source]¶

Return the pre-Lie product.

See also

pre_Lie_product_on_basis()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, None)
>>> RT = A.basis().keys()
>>> x = A(RT([RT([])]))
>>> A.pre_Lie_product(x, x)
B[[[[[]]]]] + B[[[], [[]]]]

Sage Live

A = algebras.FreePreLie(QQ, None)
RT = A.basis().keys()
x = A(RT([RT([])]))
A.pre_Lie_product(x, x)

pre_Lie_product_on_basis(x, y)[source]¶

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\).

See also

pre_Lie_product()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, None)
>>> RT = A.basis().keys()
>>> x = RT([RT([])])
>>> A.product_on_basis(x, x)
B[[[[[]]]]] + B[[[], [[]]]]

Sage Live

A = algebras.FreePreLie(QQ, None)
RT = A.basis().keys()
x = RT([RT([])])
A.product_on_basis(x, x)

product_on_basis(x, y)[source]¶

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\).

See also

pre_Lie_product()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, None)
>>> RT = A.basis().keys()
>>> x = RT([RT([])])
>>> A.product_on_basis(x, x)
B[[[[[]]]]] + B[[[], [[]]]]

Sage Live

A = algebras.FreePreLie(QQ, None)
RT = A.basis().keys()
x = RT([RT([])])
A.product_on_basis(x, x)

some_elements()[source]¶

Return some elements of the free pre-Lie algebra.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, None)
>>> A.some_elements()
[B[[]], B[[[]]], B[[[[[]]]]] + B[[[], [[]]]], B[[[[]]]] + B[[[], []]], B[[[]]]]

Sage Live

A = algebras.FreePreLie(QQ, None)
A.some_elements()

With several generators:

Sage

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

Python

>>> from sage.all import *
>>> A = algebras.FreePreLie(QQ, 'xy')
>>> 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[]]]]

Sage Live

A = algebras.FreePreLie(QQ, 'xy')
A.some_elements()

variable_names()[source]¶

Return the names of the variables.

EXAMPLES:

Sage

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

sage: R = algebras.FreePreLie(QQ, None)
sage: R.variable_names()
{'o'}

Python

>>> from sage.all import *
>>> R = algebras.FreePreLie(QQ, 'xy')
>>> R.variable_names()
{'x', 'y'}

>>> R = algebras.FreePreLie(QQ, None)
>>> R.variable_names()
{'o'}

Sage Live

R = algebras.FreePreLie(QQ, 'xy')
R.variable_names()
R = algebras.FreePreLie(QQ, None)
R.variable_names()

class sage.combinat.free_prelie_algebra.PreLieFunctor(vars)[source]¶

Bases: ConstructionFunctor

A constructor for pre-Lie algebras.

EXAMPLES:

Sage

sage: P = algebras.FreePreLie(ZZ, 'x,y')
sage: x,y = P.gens()
sage: F = P.construction()[0]; F
PreLie[x,y]

sage: A = GF(5)['a,b']
sage: a, b = A.gens()
sage: F(A)
Free PreLie algebra on 2 generators ['x', 'y'] over Multivariate Polynomial Ring in a, b over Finite Field of size 5

sage: f = A.hom([a+b,a-b],A)
sage: F(f)
Generic endomorphism of Free PreLie algebra on 2 generators ['x', 'y']
over Multivariate Polynomial Ring in a, b over Finite Field of size 5

sage: F(f)(a * F(A)(x))
(a+b)*B[x[]]

Python

>>> from sage.all import *
>>> P = algebras.FreePreLie(ZZ, 'x,y')
>>> x,y = P.gens()
>>> F = P.construction()[Integer(0)]; F
PreLie[x,y]

>>> A = GF(Integer(5))['a,b']
>>> a, b = A.gens()
>>> F(A)
Free PreLie algebra on 2 generators ['x', 'y'] over Multivariate Polynomial Ring in a, b over Finite Field of size 5

>>> f = A.hom([a+b,a-b],A)
>>> F(f)
Generic endomorphism of Free PreLie algebra on 2 generators ['x', 'y']
over Multivariate Polynomial Ring in a, b over Finite Field of size 5

>>> F(f)(a * F(A)(x))
(a+b)*B[x[]]

Sage Live

P = algebras.FreePreLie(ZZ, 'x,y')
x,y = P.gens()
F = P.construction()[0]; F
A = GF(5)['a,b']
a, b = A.gens()
F(A)
f = A.hom([a+b,a-b],A)
F(f)
F(f)(a * F(A)(x))

merge(other)[source]¶

Merge self with another construction functor, or return None.

EXAMPLES:

Sage

sage: F = sage.combinat.free_prelie_algebra.PreLieFunctor(['x','y'])
sage: G = sage.combinat.free_prelie_algebra.PreLieFunctor(['t'])
sage: F.merge(G)
PreLie[x,y,t]
sage: F.merge(F)
PreLie[x,y]

Python

>>> from sage.all import *
>>> F = sage.combinat.free_prelie_algebra.PreLieFunctor(['x','y'])
>>> G = sage.combinat.free_prelie_algebra.PreLieFunctor(['t'])
>>> F.merge(G)
PreLie[x,y,t]
>>> F.merge(F)
PreLie[x,y]

Sage Live

F = sage.combinat.free_prelie_algebra.PreLieFunctor(['x','y'])
G = sage.combinat.free_prelie_algebra.PreLieFunctor(['t'])
F.merge(G)
F.merge(F)

Now some actual use cases:

Sage

sage: R = algebras.FreePreLie(ZZ, 'xyz')
sage: x,y,z = R.gens()
sage: 1/2 * x
1/2*B[x[]]
sage: parent(1/2 * x)
Free PreLie algebra on 3 generators ['x', 'y', 'z'] over Rational Field

sage: S = algebras.FreePreLie(QQ, 'zt')
sage: z,t = S.gens()
sage: x + t
B[t[]] + B[x[]]
sage: parent(x + t)
Free PreLie algebra on 4 generators ['z', 't', 'x', 'y'] over Rational Field

Python

>>> from sage.all import *
>>> R = algebras.FreePreLie(ZZ, 'xyz')
>>> x,y,z = R.gens()
>>> Integer(1)/Integer(2) * x
1/2*B[x[]]
>>> parent(Integer(1)/Integer(2) * x)
Free PreLie algebra on 3 generators ['x', 'y', 'z'] over Rational Field

>>> S = algebras.FreePreLie(QQ, 'zt')
>>> z,t = S.gens()
>>> x + t
B[t[]] + B[x[]]
>>> parent(x + t)
Free PreLie algebra on 4 generators ['z', 't', 'x', 'y'] over Rational Field

Sage Live

R = algebras.FreePreLie(ZZ, 'xyz')
x,y,z = R.gens()
1/2 * x
parent(1/2 * x)
S = algebras.FreePreLie(QQ, 'zt')
z,t = S.gens()
x + t
parent(x + t)

rank = 9¶

sage.combinat.free_prelie_algebra.corolla_gen(tx, list_ty, labels=True)[source]¶

Yield the terms in the corolla with given bottom tree and top trees.

These are the possible terms in the simultaneous grafting of the top trees on vertices of the bottom tree.

INPUT:

tx – a tree
list_ty – list of trees

EXAMPLES:

Sage

sage: from sage.combinat.free_prelie_algebra import corolla_gen
sage: a = algebras.FreePreLie(QQ).gen(0)
sage: ta = a.support()[0]
sage: list(corolla_gen(ta,[ta],False))
[[[]]]

sage: a, b = algebras.FreePreLie(QQ,'ab').gens()
sage: ta = a.support()[0]
sage: tb = b.support()[0]
sage: ab = (a*b).support()[0]
sage: list(corolla_gen(ta,[tb]))
[a[b[]]]
sage: list(corolla_gen(tb,[ta,ta]))
[b[a[], a[]]]
sage: list(corolla_gen(ab,[ab,ta]))
[a[a[], b[], a[b[]]], a[a[b[]], b[a[]]], a[a[], b[a[b[]]]],
a[b[a[], a[b[]]]]]

Python

>>> from sage.all import *
>>> from sage.combinat.free_prelie_algebra import corolla_gen
>>> a = algebras.FreePreLie(QQ).gen(Integer(0))
>>> ta = a.support()[Integer(0)]
>>> list(corolla_gen(ta,[ta],False))
[[[]]]

>>> a, b = algebras.FreePreLie(QQ,'ab').gens()
>>> ta = a.support()[Integer(0)]
>>> tb = b.support()[Integer(0)]
>>> ab = (a*b).support()[Integer(0)]
>>> list(corolla_gen(ta,[tb]))
[a[b[]]]
>>> list(corolla_gen(tb,[ta,ta]))
[b[a[], a[]]]
>>> list(corolla_gen(ab,[ab,ta]))
[a[a[], b[], a[b[]]], a[a[b[]], b[a[]]], a[a[], b[a[b[]]]],
a[b[a[], a[b[]]]]]

Sage Live

from sage.combinat.free_prelie_algebra import corolla_gen
a = algebras.FreePreLie(QQ).gen(0)
ta = a.support()[0]
list(corolla_gen(ta,[ta],False))
a, b = algebras.FreePreLie(QQ,'ab').gens()
ta = a.support()[0]
tb = b.support()[0]
ab = (a*b).support()[0]
list(corolla_gen(ta,[tb]))
list(corolla_gen(tb,[ta,ta]))
list(corolla_gen(ab,[ab,ta]))

sage.combinat.free_prelie_algebra.tree_from_sortkey(ch, labels=True)[source]¶

Transform a list of (valence, label) into a tree and a remainder.

This is like an inverse of the sort_key method.

INPUT:

ch – list of pairs (integer, label)
labels – boolean (default: True); whether to use labelled trees

OUTPUT:

a pair (tree, remainder of the input)

EXAMPLES:

Sage

sage: from sage.combinat.free_prelie_algebra import tree_from_sortkey
sage: a = algebras.FreePreLie(QQ).gen(0)
sage: t = (a*a*a*a).support()
sage: all(tree_from_sortkey(u.sort_key(), False)[0] == u for u in t)
True

sage: a, b = algebras.FreePreLie(QQ,'ab').gens()
sage: t = (a*b*a*b).support()
sage: all(tree_from_sortkey(u.sort_key())[0] == u for u in t)
True

Python

>>> from sage.all import *
>>> from sage.combinat.free_prelie_algebra import tree_from_sortkey
>>> a = algebras.FreePreLie(QQ).gen(Integer(0))
>>> t = (a*a*a*a).support()
>>> all(tree_from_sortkey(u.sort_key(), False)[Integer(0)] == u for u in t)
True

>>> a, b = algebras.FreePreLie(QQ,'ab').gens()
>>> t = (a*b*a*b).support()
>>> all(tree_from_sortkey(u.sort_key())[Integer(0)] == u for u in t)
True

Sage Live

from sage.combinat.free_prelie_algebra import tree_from_sortkey
a = algebras.FreePreLie(QQ).gen(0)
t = (a*a*a*a).support()
all(tree_from_sortkey(u.sort_key(), False)[0] == u for u in t)
a, b = algebras.FreePreLie(QQ,'ab').gens()
t = (a*b*a*b).support()
all(tree_from_sortkey(u.sort_key())[0] == u for u in t)