Shuffle algebras¶

AUTHORS:

Frédéric Chapoton (2013-03): Initial version
Matthieu Deneufchatel (2013-07): Implemented dual PBW basis

class sage.algebras.shuffle_algebra.DualPBWBasis(R, names)¶

Bases: sage.combinat.free_module.CombinatorialFreeModule

The basis dual to the Poincare-Birkhoff-Witt basis of the free algebra.

We recursively define the dual PBW basis as the basis of the shuffle algebra given by

$S_w = \begin{cases} w & |w| = 1, \\ x S_u & w = xu \text{ and } w \in \mathrm{Lyn}(X), \\ \displaystyle \frac{S_{\ell_{i_1}}^{\ast \alpha_1} \ast \cdots \ast S_{\ell_{i_k}}^{\ast \alpha_k}}{\alpha_1! \cdots \alpha_k!} & w = \ell_{i_1}^{\alpha_1} \cdots \ell_{i_k}^{\alpha_k} \text{ with } \ell_1 > \cdots > \ell_k \in \mathrm{Lyn}(X). \end{cases}$

where $S \ast T$ denotes the shuffle product of $S$ and $T$ and $\mathrm{Lyn}(X)$ is the set of Lyndon words in the alphabet $X$ .

The definition may be found in Theorem 5.3 of [Reuten1993].

INPUT:

R – ring
names – names of the generators (string or an alphabet)

REFERENCES:

[Reuten1993]

C. Reutenauer. Free Lie Algebras. Number 7 in London Math. Soc. Monogr. (N.S.). Oxford University Press. (1993).

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: S
The dual Poincare-Birkhoff-Witt basis of Shuffle Algebra on 2 generators ['a', 'b'] over Rational Field
sage: S.one()
S[word: ]
sage: S.one_basis()
word:
sage: T = ShuffleAlgebra(QQ, 'abcd').dual_pbw_basis(); T
The dual Poincare-Birkhoff-Witt basis of Shuffle Algebra on 4 generators ['a', 'b', 'c', 'd'] over Rational Field
sage: T.algebra_generators()
(S[word: a], S[word: b], S[word: c], S[word: d])

TESTS:

We check conversion between the bases:

sage: A = ShuffleAlgebra(QQ, 'ab')
sage: S = A.dual_pbw_basis()
sage: W = Words('ab', 5)
sage: all(S(A(S(w))) == S(w) for w in W)
True
sage: all(A(S(A(w))) == A(w) for w in W)
True

class Element(M, x)¶

Bases: sage.combinat.free_module.CombinatorialFreeModuleElement

An element in the dual PBW basis.

expand()¶

Expand self in words of the shuffle algebra.

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: f = S('ab') + S('bab')
sage: f.expand()
B[word: ab] + 2*B[word: abb] + B[word: bab]

DualPBWBasis.algebra_generators()¶

Return the algebra generators of self.

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: S.algebra_generators()
(S[word: a], S[word: b])

DualPBWBasis.expansion()¶

Return the morphism corresponding to the expansion into words of the shuffle algebra.

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: f = S('ab') + S('aba')
sage: S.expansion(f)
2*B[word: aab] + B[word: ab] + B[word: aba]

DualPBWBasis.expansion_on_basis(w)¶

Return the expansion of $S_w$ in words of the shuffle algebra.

INPUT:

w – a word

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: S.expansion_on_basis(Word())
B[word: ]
sage: S.expansion_on_basis(Word()).parent()
Shuffle Algebra on 2 generators ['a', 'b'] over Rational Field
sage: S.expansion_on_basis(Word('abba'))
2*B[word: aabb] + B[word: abab] + B[word: abba]
sage: S.expansion_on_basis(Word())
B[word: ]
sage: S.expansion_on_basis(Word('abab'))
2*B[word: aabb] + B[word: abab]

DualPBWBasis.gen(i)¶

Return the i-th generator of self.

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: S.gen(0)
S[word: a]
sage: S.gen(1)
S[word: b]

DualPBWBasis.gens()¶

Return the algebra generators of self.

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: S.algebra_generators()
(S[word: a], S[word: b])

DualPBWBasis.one_basis()¶

Return the indexing element of the basis element $1$ .

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: S.one_basis()
word:

DualPBWBasis.product(u, v)¶

Return the product of two elements u and v.

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: a,b = S.gens()
sage: S.product(a, b)
S[word: ba]
sage: S.product(b, a)
S[word: ba]
sage: S.product(b^2*a, a*b*a)
36*S[word: bbbaaa]

TESTS:

Check that multiplication agrees with the multiplication in the shuffle algebra:

sage: A = ShuffleAlgebra(QQ, 'ab')
sage: S = A.dual_pbw_basis()
sage: a,b = S.gens()
sage: A(a*b)
B[word: ab] + B[word: ba]
sage: A(a*b*a)
2*B[word: aab] + 2*B[word: aba] + 2*B[word: baa]
sage: S(A(a)*A(b)*A(a)) == a*b*a
True

DualPBWBasis.shuffle_algebra()¶

Return the associated shuffle algebra of self.

EXAMPLES:

sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis()
sage: S.shuffle_algebra()
Shuffle Algebra on 2 generators ['a', 'b'] over Rational Field

class sage.algebras.shuffle_algebra.ShuffleAlgebra(R, names)¶

Bases: sage.combinat.free_module.CombinatorialFreeModule

The shuffle algebra on some generators over a base ring.

Shuffle algebras are commutative and associative algebras, with a basis indexed by words. The product of two words $w_1 \cdot w_2$ is given by the sum over the shuffle product of $w_1$ and $w_2$ .

See also

For more on shuffle products, see shuffle_product and shuffle().

REFERENCES:

Wikipedia article Shuffle algebra

INPUT:

R – ring
names – generator names (string or an alphabet)

EXAMPLES:

sage: F = ShuffleAlgebra(QQ, 'xyz'); F
Shuffle Algebra on 3 generators ['x', 'y', 'z'] over Rational Field

sage: mul(F.gens())
B[word: xyz] + B[word: xzy] + B[word: yxz] + B[word: yzx] + B[word: zxy] + B[word: zyx]

sage: mul([ F.gen(i) for i in range(2) ]) + mul([ F.gen(i+1) for i in range(2) ])
B[word: xy] + B[word: yx] + B[word: yz] + B[word: zy]

sage: S = ShuffleAlgebra(ZZ, 'abcabc'); S
Shuffle Algebra on 3 generators ['a', 'b', 'c'] over Integer Ring
sage: S.base_ring()
Integer Ring

sage: G = ShuffleAlgebra(S, 'mn'); G
Shuffle Algebra on 2 generators ['m', 'n'] over Shuffle Algebra on 3 generators ['a', 'b', 'c'] over Integer Ring
sage: G.base_ring()
Shuffle Algebra on 3 generators ['a', 'b', 'c'] over Integer Ring

Shuffle algebras commute with their base ring:

sage: K = ShuffleAlgebra(QQ,'ab')
sage: a,b = K.gens()
sage: K.is_commutative()
True
sage: L = ShuffleAlgebra(K,'cd')
sage: c,d = L.gens()
sage: L.is_commutative()
True
sage: s = a*b^2 * c^3; s
(12*B[word:abb]+12*B[word:bab]+12*B[word:bba])*B[word: ccc]
sage: parent(s)
Shuffle Algebra on 2 generators ['c', 'd'] over Shuffle Algebra on 2 generators ['a', 'b'] over Rational Field
sage: c^3 * a * b^2
(12*B[word:abb]+12*B[word:bab]+12*B[word:bba])*B[word: ccc]

Shuffle algebras are commutative:

sage: c^3 * b * a * b == c * a * c * b^2 * c
True

We can also manipulate elements in the basis and coerce elements from our base field:

sage: F = ShuffleAlgebra(QQ, 'abc')
sage: B = F.basis()
sage: B[Word('bb')] * B[Word('ca')]
B[word: bbca] + B[word: bcab] + B[word: bcba] + B[word: cabb] + B[word: cbab] + B[word: cbba]
sage: 1 - B[Word('bb')] * B[Word('ca')] / 2
B[word: ] - 1/2*B[word: bbca] - 1/2*B[word: bcab] - 1/2*B[word: bcba] - 1/2*B[word: cabb] - 1/2*B[word: cbab] - 1/2*B[word: cbba]

algebra_generators()¶

Return the generators of this algebra.

EXAMPLES:

sage: A = ShuffleAlgebra(ZZ,'fgh'); A
Shuffle Algebra on 3 generators ['f', 'g', 'h'] over Integer Ring
sage: A.algebra_generators()
Family (B[word: f], B[word: g], B[word: h])

sage: A = ShuffleAlgebra(QQ, ['x1','x2'])
sage: A.algebra_generators()
Family (B[word: x1], B[word: x2])

coproduct(S)¶

Return the coproduct of the series S.

EXAMPLES:

sage: F = ShuffleAlgebra(QQ,'ab')
sage: S = F.an_element(); S
B[word: ] + 2*B[word: a] + 3*B[word: b] + B[word: bab]
sage: F.coproduct(S)
B[word: ] # B[word: ] + 2*B[word: ] # B[word: a]
+ 3*B[word: ] # B[word: b] + B[word: ] # B[word: bab]
+ 2*B[word: a] # B[word: ] + B[word: a] # B[word: bb]
+ B[word: ab] # B[word: b] + 3*B[word: b] # B[word: ]
+ B[word: b] # B[word: ab] + B[word: b] # B[word: ba]
+ B[word: ba] # B[word: b] + B[word: bab] # B[word: ]
+ B[word: bb] # B[word: a]
sage: F.coproduct(F.one())
B[word: ] # B[word: ]

coproduct_on_basis(w)¶

Return the coproduct of the element of the basis indexed by the word w.

INPUT:

w – a word

EXAMPLES:

sage: F = ShuffleAlgebra(QQ,'ab')
sage: F.coproduct_on_basis(Word('a'))
B[word: ] # B[word: a] + B[word: a] # B[word: ]
sage: F.coproduct_on_basis(Word('aba'))
B[word: ] # B[word: aba] + B[word: a] # B[word: ab] + B[word: a] # B[word: ba]
 + B[word: aa] # B[word: b] + B[word: ab] # B[word: a] + B[word: aba] # B[word: ]
 + B[word: b] # B[word: aa] + B[word: ba] # B[word: a]
sage: F.coproduct_on_basis(Word())
B[word: ] # B[word: ]

counit(S)¶

Return the counit of S.

EXAMPLES:

sage: F = ShuffleAlgebra(QQ,'ab')
sage: S = F.an_element(); S
B[word: ] + 2*B[word: a] + 3*B[word: b] + B[word: bab]
sage: F.counit(S)
1

dual_pbw_basis()¶

Return the dual PBW of self.

EXAMPLES:

sage: A = ShuffleAlgebra(QQ, 'ab')
sage: A.dual_pbw_basis()
The dual Poincare-Birkhoff-Witt basis of Shuffle Algebra on 2 generators ['a', 'b'] over Rational Field

gen(i)¶

The i-th generator of the algebra.

INPUT:

i – an integer

EXAMPLES:

sage: F = ShuffleAlgebra(ZZ,'xyz')
sage: F.gen(0)
B[word: 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 this algebra.

EXAMPLES:

sage: A = ShuffleAlgebra(ZZ,'fgh'); A
Shuffle Algebra on 3 generators ['f', 'g', 'h'] over Integer Ring
sage: A.algebra_generators()
Family (B[word: f], B[word: g], B[word: h])

sage: A = ShuffleAlgebra(QQ, ['x1','x2'])
sage: A.algebra_generators()
Family (B[word: x1], B[word: x2])

is_commutative()¶

Return True as the shuffle algebra is commutative.

EXAMPLES:

sage: R = ShuffleAlgebra(QQ,'x')
sage: R.is_commutative()
True
sage: R = ShuffleAlgebra(QQ,'xy')
sage: R.is_commutative()
True

one_basis()¶

Return the empty word, which index of $1$ of this algebra, as per AlgebrasWithBasis.ParentMethods.one_basis().

EXAMPLES:

sage: A = ShuffleAlgebra(QQ,'a')
sage: A.one_basis()
word:
sage: A.one()
B[word: ]

product_on_basis(w1, w2)¶

Return the product of basis elements w1 and w2, as per AlgebrasWithBasis.ParentMethods.product_on_basis().

INPUT:

w1, w2 – Basis elements

EXAMPLES:

sage: A = ShuffleAlgebra(QQ,'abc')
sage: W = A.basis().keys()
sage: A.product_on_basis(W("acb"), W("cba"))
B[word: acbacb] + B[word: acbcab] + 2*B[word: acbcba] + 2*B[word: accbab] + 4*B[word: accbba] + B[word: cabacb] + B[word: cabcab] + B[word: cabcba] + B[word: cacbab] + 2*B[word: cacbba] + 2*B[word: cbaacb] + B[word: cbacab] + B[word: cbacba]

sage: (a,b,c) = A.algebra_generators()
sage: a * (1-b)^2 * c
2*B[word: abbc] - 2*B[word: abc] + 2*B[word: abcb] + B[word: ac] - 2*B[word: acb] + 2*B[word: acbb] + 2*B[word: babc] - 2*B[word: bac] + 2*B[word: bacb] + 2*B[word: bbac] + 2*B[word: bbca] - 2*B[word: bca] + 2*B[word: bcab] + 2*B[word: bcba] + B[word: ca] - 2*B[word: cab] + 2*B[word: cabb] - 2*B[word: cba] + 2*B[word: cbab] + 2*B[word: cbba]

to_dual_pbw_element(w)¶

Return the element $w$ of self expressed in the dual PBW basis.

INPUT:

w – an element of the shuffle algebra

EXAMPLES:

sage: A = ShuffleAlgebra(QQ, 'ab')
sage: f = 2 * A(Word()) + A(Word('ab')); f
2*B[word: ] + B[word: ab]
sage: A.to_dual_pbw_element(f)
2*S[word: ] + S[word: ab]
sage: A.to_dual_pbw_element(A.one())
S[word: ]
sage: S = A.dual_pbw_basis()
sage: elt = S.expansion_on_basis(Word('abba')); elt
2*B[word: aabb] + B[word: abab] + B[word: abba]
sage: A.to_dual_pbw_element(elt)
S[word: abba]
sage: A.to_dual_pbw_element(2*A(Word('aabb')) + A(Word('abab')))
S[word: abab]
sage: S.expansion(S('abab'))
2*B[word: aabb] + B[word: abab]

variable_names()¶

Return the names of the variables.

EXAMPLES:

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

Shuffle algebras¶

Previous topic

Next topic

This Page