Free Pre-Lie Algebras

AUTHORS:

  • Florent Hivert, Frédéric Chapoton (2011)
sage.combinat.free_prelie_algebra.FreePreLieAlgebra

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 [Liv2006] 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 None is given as input, unlabelled trees are used instead:

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

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

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

The set \(E\) can be infinite:

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

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 sage.combinat.free_prelie_algebra.PreLieFunctor(vars)

Bases: sage.categories.pushout.ConstructionFunctor

A constructor for pre-Lie algebras.

EXAMPLES:

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[]]
merge(other)

Merge self with another construction functor, or return None.

EXAMPLES:

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]

Now some actual use cases:

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