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 Poincaré-Birkhoff-Witt basis of the free algebra.
We recursively define the dual PBW basis as the basis of the shuffle algebra given by
\[\begin{split}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}\end{split}\]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 [Reu1993].
INPUT:
R
– ringnames
– names of the generators (string or an alphabet)
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])
-
class
Element
¶ Bases:
sage.modules.with_basis.indexed_element.IndexedFreeModuleElement
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]
-
-
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])
-
antipode
(elt)¶ Return the antipode of the element
elt
.EXAMPLES:
sage: A = ShuffleAlgebra(QQ, 'ab') sage: S = A.dual_pbw_basis() sage: w = S('abaab').antipode(); w S[word: abaab] - 2*S[word: ababa] - S[word: baaba] + 3*S[word: babaa] - 6*S[word: bbaaa] sage: w.antipode() S[word: abaab]
-
coproduct
(elt)¶ Return the coproduct of the element
elt
.EXAMPLES:
sage: A = ShuffleAlgebra(QQ, 'ab') sage: S = A.dual_pbw_basis() sage: S('ab').coproduct() S[word: ] # S[word: ab] + S[word: a] # S[word: b] + S[word: ab] # S[word: ] sage: S('ba').coproduct() S[word: ] # S[word: ba] + S[word: a] # S[word: b] + S[word: b] # S[word: a] + S[word: ba] # S[word: ]
-
counit
(S)¶ Return the counit of
S
.EXAMPLES:
sage: F = ShuffleAlgebra(QQ,'ab').dual_pbw_basis() sage: (3*F.gen(0)+5*F.gen(1)**2).counit() 0 sage: (4*F.one()).counit() 4
-
degree_on_basis
(w)¶ Return the degree of the element
w
.EXAMPLES:
sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis() sage: [S.degree_on_basis(x.leading_support()) for x in S.some_elements() if x != 0] [0, 1, 1, 2]
-
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]
-
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]
-
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]
-
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])
-
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:
-
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]
-
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
-
some_elements
()¶ Return some typical elements.
EXAMPLES:
sage: F = ShuffleAlgebra(QQ,'xyz').dual_pbw_basis() sage: F.some_elements() [0, S[word: ], S[word: x], S[word: y], S[word: z], S[word: zx]]
-
class
sage.algebras.shuffle_algebra.
ShuffleAlgebra
(R, names, prefix)¶ 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
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])
-
antipode_on_basis
(w)¶ Return the antipode on the basis element
w
.EXAMPLES:
sage: A = ShuffleAlgebra(QQ,'abc') sage: W = A.basis().keys() sage: A.antipode_on_basis(W("acb")) -B[word: bca]
-
coproduct_on_basis
(w)¶ Return the coproduct of the element of the basis indexed by the word
w
.The coproduct is given by deconcatenation.
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: ba] + B[word: ab] # B[word: a] + B[word: aba] # B[word: ] 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
-
degree_on_basis
(w)¶ Return the degree of the element
w
.EXAMPLES:
sage: A = ShuffleAlgebra(QQ, 'ab') sage: [A.degree_on_basis(x.leading_support()) for x in A.some_elements() if x != 0] [0, 1, 1, 2]
-
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)¶ Return 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])
-
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
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]
-
some_elements
()¶ Return some typical elements.
EXAMPLES:
sage: F = ShuffleAlgebra(ZZ,'xyz') sage: F.some_elements() [0, B[word: ], B[word: x], B[word: y], B[word: z], B[word: xz] + B[word: zx]]
-
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'}