Free Dendriform Algebras

AUTHORS:

Frédéric Chapoton (2017)

class sage.combinat.free_dendriform_algebra.DendriformFunctor(vars)

Bases: sage.categories.pushout.ConstructionFunctor

A constructor for dendriform algebras.

EXAMPLES:

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

sage: A = GF(5)['a,b']
sage: a, b = A.gens()
sage: F(A)
Free Dendriform 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 Dendriform 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_dendriform_algebra.DendriformFunctor(['x','y'])
sage: G = sage.combinat.free_dendriform_algebra.DendriformFunctor(['t'])
sage: F.merge(G)
Dendriform[x,y,t]
sage: F.merge(F)
Dendriform[x,y]

Now some actual use cases:

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

sage: S = algebras.FreeDendriform(QQ, 'zt')
sage: z,t = S.gens()
sage: x + t
B[t[., .]] + B[x[., .]]
sage: parent(x + t)
Free Dendriform algebra on 4 generators ['z', 't', 'x', 'y'] over Rational Field
class sage.combinat.free_dendriform_algebra.FreeDendriformAlgebra(R, names=None)

Bases: sage.combinat.free_module.CombinatorialFreeModule

The free dendriform algebra.

Dendriform algebras are associative algebras, where the associative product \(*\) is decomposed as a sum of two binary operations

\[x * y = x \succ y + x \prec y\]

that satisfy the axioms:

\[(x \succ y) \prec z = x \succ (y \prec z),\]
\[(x \prec y) \prec z = x \prec (y * z).\]
\[(x * y) \succ z = x \succ (y \succ z).\]

The free Dendriform algebra on a given set \(E\) has an explicit description using (planar) binary trees, just as the free associative algebra can be described using words. The underlying vector space has a basis indexed by finite binary trees endowed with a map from their vertices to \(E\). In this basis, the associative product of two (decorated) binary trees \(S * T\) is the sum over all possible ways of identifying (glueing) the rightmost path in \(S\) and the leftmost path in \(T\).

The decomposition of the associative product as the sum of two binary operations \(\succ\) and \(\prec\) is made by separating the terms according to the origin of the root vertex. For \(x \succ y\), one keeps the terms where the root vertex comes from \(y\), whereas for \(x \prec y\) one keeps the terms where the root vertex comes from \(x\).

The free dendriform algebra can also be considered as the free algebra over the Dendriform operad.

Note

The usual binary operator \(*\) is used for the associative product.

EXAMPLES:

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

The free dendriform algebra is associative:

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

The associative product decomposes in two parts:

sage: x * y == F.prec(x, y) + F.succ(x, y)
True

The axioms hold:

sage: F.prec(F.succ(x, y), z) == F.succ(x, F.prec(y, z))
True
sage: F.prec(F.prec(x, y), z) == F.prec(x, y * z)
True
sage: F.succ(x * y, z) == F.succ(x, F.succ(y, z))
True

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

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

REFERENCES:

algebra_generators()

Return the generators of this algebra.

These are the binary trees with just one vertex.

EXAMPLES:

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

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

Return an element of self.

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ, 'xy')
sage: A.an_element()
B[x[., .]] + 2*B[x[., x[., .]]] + 2*B[x[x[., .], .]]
change_ring(R)

Return the free dendriform algebra in the same variables over \(R\).

INPUT:

  • R – a ring

EXAMPLES:

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

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

EXAMPLES:

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

Return the coproduct of a binary tree.

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ)
sage: x = A.gen(0)
sage: ascii_art(A.coproduct(A.one()))  # indirect doctest
1 # 1

sage: ascii_art(A.coproduct(x))  # indirect doctest
1 # B  + B  # 1
     o    o

sage: A = algebras.FreeDendriform(QQ, 'xyz')
sage: x, y, z = A.gens()
sage: w = A.under(z,A.over(x,y))
sage: A.coproduct(z)
B[.] # B[z[., .]] + B[z[., .]] # B[.]
sage: A.coproduct(w)
B[.] # B[x[z[., .], y[., .]]] + B[x[., .]] # B[z[., y[., .]]] +
B[x[., .]] # B[y[z[., .], .]] + B[x[., y[., .]]] # B[z[., .]] +
B[x[z[., .], .]] # B[y[., .]] + B[x[z[., .], y[., .]]] # B[.]
degree_on_basis(t)

Return the degree of a binary tree in the free Dendriform algebra.

This is the number of vertices.

EXAMPLES:

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

Return the i-th generator of the algebra.

INPUT:

  • i – an integer

EXAMPLES:

sage: F = algebras.FreeDendriform(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.FreeDendriform(ZZ, 'fgh')
sage: A.gens()
(B[f[., .]], B[g[., .]], B[h[., .]])
one_basis()

Return the index of the unit.

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ, '@')
sage: A.one_basis()
.
sage: A = algebras.FreeDendriform(QQ, 'xy')
sage: A.one_basis()
.
over()

Return the over product.

The over product \(x/y\) is the binary tree obtained by grafting the root of \(y\) at the rightmost leaf of \(x\).

The usual symbol for this operation is \(/\).

See also

product(), succ(), prec(), under()

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ)
sage: RT = A.basis().keys()
sage: x = A.gen(0)
sage: A.over(x, x)
B[[., [., .]]]
prec()

Return the \(\prec\) dendriform product.

This is the sum over all possible ways to identify the rightmost path in \(x\) and the leftmost path in \(y\), with the additional condition that the root vertex of the result comes from \(x\).

The usual symbol for this operation is \(\prec\).

See also

product(), succ(), over(), under()

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ)
sage: RT = A.basis().keys()
sage: x = A.gen(0)
sage: A.prec(x, x)
B[[., [., .]]]
prec_product_on_basis(x, y)

Return the \(\prec\) dendriform product of two trees.

This is the sum over all possible ways of identifying the rightmost path in \(x\) and the leftmost path in \(y\), with the additional condition that the root vertex of the result comes from \(x\).

The usual symbol for this operation is \(\prec\).

See also

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ)
sage: RT = A.basis().keys()
sage: x = RT([])
sage: A.prec_product_on_basis(x, x)
B[[., [., .]]]
product_on_basis(x, y)

Return the \(*\) associative dendriform product of two trees.

This is the sum over all possible ways of identifying the rightmost path in \(x\) and the leftmost path in \(y\). Every term corresponds to a shuffle of the vertices on the rightmost path in \(x\) and the vertices on the leftmost path in \(y\).

See also

EXAMPLES:

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

Return some elements of the free dendriform algebra.

EXAMPLES:

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

With several generators:

sage: A = algebras.FreeDendriform(QQ, 'xy')
sage: A.some_elements()
[B[.],
 B[x[., .]],
 B[x[., x[., .]]] + B[x[x[., .], .]],
 B[.] + B[x[., x[., .]]] + B[x[x[., .], .]]]
succ()

Return the \(\succ\) dendriform product.

This is the sum over all possible ways of identifying the rightmost path in \(x\) and the leftmost path in \(y\), with the additional condition that the root vertex of the result comes from \(y\).

The usual symbol for this operation is \(\succ\).

See also

product(), prec(), over(), under()

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ)
sage: RT = A.basis().keys()
sage: x = A.gen(0)
sage: A.succ(x, x)
B[[[., .], .]]
succ_product_on_basis(x, y)

Return the \(\succ\) dendriform product of two trees.

This is the sum over all possible ways to identify the rightmost path in \(x\) and the leftmost path in \(y\), with the additional condition that the root vertex of the result comes from \(y\).

The usual symbol for this operation is \(\succ\).

See also

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ)
sage: RT = A.basis().keys()
sage: x = RT([])
sage: A.succ_product_on_basis(x, x)
B[[[., .], .]]
under()

Return the under product.

The over product \(x \backslash y\) is the binary tree obtained by grafting the root of \(x\) at the leftmost leaf of \(y\).

The usual symbol for this operation is \(\backslash\).

See also

product(), succ(), prec(), over()

EXAMPLES:

sage: A = algebras.FreeDendriform(QQ)
sage: RT = A.basis().keys()
sage: x = A.gen(0)
sage: A.under(x, x)
B[[[., .], .]]
variable_names()

Return the names of the variables.

EXAMPLES:

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