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
where
denotes the shuffle product of
and
and
is the set of Lyndon words in the alphabet
.
The definition may be found in Theorem 5.3 of [Reuten1993].
INPUT:
R
– ringnames
– 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
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 ofself
.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
.
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
andv
.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
is given by the sum over the shuffle product of
and
.
See also
For more on shuffle products, see
shuffle_product
andshuffle()
.REFERENCES:
INPUT:
R
– ringnames
– 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
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
andw2
, as perAlgebrasWithBasis.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
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'}