Free Dendriform Algebras

AUTHORS:

Frédéric Chapoton (2017)

class sage.combinat.free_dendriform_algebra.DendriformFunctor(vars)[source]

Bases: 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[., .]]

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

>>> A = GF(Integer(5))['a,b']
>>> a, b = A.gens()
>>> F(A)
Free Dendriform 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 Dendriform 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[., .]]
merge(other)[source]

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]

>>> from sage.all import *
>>> F = sage.combinat.free_dendriform_algebra.DendriformFunctor(['x','y'])
>>> G = sage.combinat.free_dendriform_algebra.DendriformFunctor(['t'])
>>> F.merge(G)
Dendriform[x,y,t]
>>> 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

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

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

Bases: 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[., .], .], .]]

>>> from sage.all import *
>>> F = algebras.FreeDendriform(ZZ, 'xyz')
>>> x,y,z = F.gens()
>>> (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

>>> from sage.all import *
>>> 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

>>> from sage.all import *
>>> 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

>>> from sage.all import *
>>> F.prec(F.succ(x, y), z) == F.succ(x, F.prec(y, z))
True
>>> F.prec(F.prec(x, y), z) == F.prec(x, y * z)
True
>>> 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[[[[., .], .], .]]

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

The set \(E\) can be infinite:

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

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

REFERENCES:

algebra_generators()[source]

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

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

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

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ, 'xy')
>>> A.an_element()
B[x[., .]] + 2*B[x[., x[., .]]] + 2*B[x[x[., .], .]]
change_ring(R)[source]

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

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

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

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

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ)
>>> x = A.gen(Integer(0))
>>> ascii_art(A.coproduct(A.one()))  # indirect doctest
1 # 1

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

>>> A = algebras.FreeDendriform(QQ, 'xyz')
>>> x, y, z = A.gens()
>>> w = A.under(z,A.over(x,y))
>>> A.coproduct(z)
B[.] # B[z[., .]] + B[z[., .]] # B[.]
>>> 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)[source]

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ,'@')
>>> RT = A.basis().keys()
>>> u = RT([], '@')
>>> A.degree_on_basis(u.over(u))
2
gen(i)[source]

Return the \(i\)-th generator of the algebra.

INPUT:

  • i – 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

>>> from sage.all import *
>>> F = algebras.FreeDendriform(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
gens()[source]

Return the generators of self (as an algebra).

EXAMPLES:

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

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

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ, '@')
>>> A.one_basis()
.
>>> A = algebras.FreeDendriform(QQ, 'xy')
>>> A.one_basis()
.
over()[source]

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ)
>>> RT = A.basis().keys()
>>> x = A.gen(Integer(0))
>>> A.over(x, x)
B[[., [., .]]]
prec()[source]

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ)
>>> RT = A.basis().keys()
>>> x = A.gen(Integer(0))
>>> A.prec(x, x)
B[[., [., .]]]
prec_product_on_basis(x, y)[source]

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ)
>>> RT = A.basis().keys()
>>> x = RT([])
>>> A.prec_product_on_basis(x, x)
B[[., [., .]]]
product_on_basis(x, y)[source]

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

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

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

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ, 'xy')
>>> A.some_elements()
[B[.],
 B[x[., .]],
 B[x[., x[., .]]] + B[x[x[., .], .]],
 B[.] + B[x[., x[., .]]] + B[x[x[., .], .]]]
succ()[source]

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ)
>>> RT = A.basis().keys()
>>> x = A.gen(Integer(0))
>>> A.succ(x, x)
B[[[., .], .]]
succ_product_on_basis(x, y)[source]

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ)
>>> RT = A.basis().keys()
>>> x = RT([])
>>> A.succ_product_on_basis(x, x)
B[[[., .], .]]
under()[source]

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

>>> from sage.all import *
>>> A = algebras.FreeDendriform(QQ)
>>> RT = A.basis().keys()
>>> x = A.gen(Integer(0))
>>> A.under(x, x)
B[[[., .], .]]
variable_names()[source]

Return the names of the variables.

EXAMPLES:

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

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