Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# -*- coding: utf-8 -*- Shuffle algebras
AUTHORS:
- Frédéric Chapoton (2013-03): Initial version - Matthieu Deneufchatel (2013-07): Implemented dual PBW basis """
#***************************************************************************** # Copyright (C) 2013 Frédéric Chapoton <chapoton-math-univ-lyon1-fr> # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ #*****************************************************************************
r""" 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`.
.. SEEALSO::
For more on shuffle products, see :mod:`~sage.combinat.words.shuffle_product` and :meth:`~sage.combinat.words.finite_word.FiniteWord_class.shuffle()`.
REFERENCES:
- :wikipedia:`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] """ def __classcall_private__(cls, R, names): """ Normalize input to ensure a unique representation.
EXAMPLES::
sage: F1 = ShuffleAlgebra(QQ, 'xyz') sage: F2 = ShuffleAlgebra(QQ, ['x','y','z']) sage: F3 = ShuffleAlgebra(QQ, Alphabet('xyz')) sage: F1 is F2 and F1 is F3 True """
r""" Initialize ``self``.
EXAMPLES::
sage: F = ShuffleAlgebra(QQ, 'xyz'); F Shuffle Algebra on 3 generators ['x', 'y', 'z'] over Rational Field sage: TestSuite(F).run()
TESTS::
sage: ShuffleAlgebra(24, 'toto') Traceback (most recent call last): ... TypeError: argument R must be a ring """ latex_prefix="", category=(AlgebrasWithBasis(R), CommutativeAlgebras(R), CoalgebrasWithBasis(R)))
r""" Return the names of the variables.
EXAMPLES::
sage: R = ShuffleAlgebra(QQ,'xy') sage: R.variable_names() {'x', 'y'} """
r""" 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 """
r""" Text representation of this shuffle algebra.
EXAMPLES::
sage: F = ShuffleAlgebra(QQ,'xyz') sage: F # indirect doctest Shuffle Algebra on 3 generators ['x', 'y', 'z'] over Rational Field
sage: ShuffleAlgebra(ZZ,'a') Shuffle Algebra on one generator ['a'] over Integer Ring """ else: self._alphabet.list(), self.base_ring())
def one_basis(self): r""" Return the empty word, which index of `1` of this algebra, as per :meth:`AlgebrasWithBasis.ParentMethods.one_basis`.
EXAMPLES::
sage: A = ShuffleAlgebra(QQ,'a') sage: A.one_basis() word: sage: A.one() B[word: ] """
r""" Return the product of basis elements ``w1`` and ``w2``, as per :meth:`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] """
r""" 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 """
""" 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: ] """ ((w, self.one_basis()), 1), ((self.one_basis(), w), 1) ], distinct=True)
((Word(v1)*Word(u1), Word(v2)*Word(u2)), coeff1 * coeff2) for ((u1,u2),coeff1) in self.coproduct_on_basis(Word([i])) for ((v1,v2),coeff2) in result ])
""" 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: ] """ for i,c in S.monomial_coefficients().items()])
""" 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 """
def algebra_generators(self): r""" 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]) """ # FIXME: use this once the keys argument of FiniteFamily will be honoured # for the specifying the order of the elements in the family #return Family(self._alphabet, lambda a: self.term(self.basis().keys()(a)))
r""" Convert ``x`` into ``self``.
EXAMPLES::
sage: R = ShuffleAlgebra(QQ,'xy') sage: x, y = R.gens() sage: R(3) 3*B[word: ] sage: R(x) B[word: x] sage: R('xyy') B[word: xyy] sage: R(Word('xyx')) B[word: xyx] """
return x # ok, not a shuffle algebra element (or should not be viewed as one). if isinstance(x, six.string_types): from sage.misc.sage_eval import sage_eval return sage_eval(x,locals=self.gens_dict()) R = self.base_ring() # coercion via base ring x = R(x) if x == 0: return self.element_class(self,{}) else: return self.from_base_ring_from_one_basis(x)
r""" Canonical coercion of ``x`` into ``self``.
Here is what canonically coerces to ``self``:
- this shuffle algebra,
- anything that coerces to the base ring of this shuffle algebra,
- any shuffle algebra on the same variables, whose base ring coerces to the base ring of this shuffle algebra.
EXAMPLES::
sage: F = ShuffleAlgebra(GF(7), 'xyz'); F Shuffle Algebra on 3 generators ['x', 'y', 'z'] over Finite Field of size 7
Elements of the shuffle algebra canonically coerce in::
sage: x, y, z = F.gens() sage: F.coerce(x*y) # indirect doctest B[word: xy] + B[word: yx]
Elements of the integers coerce in, since there is a coerce map from `\ZZ` to GF(7)::
sage: F.coerce(1) # indirect doctest B[word: ]
There is no coerce map from `\QQ` to `\GF{7}`::
sage: F.coerce(2/3) # indirect doctest Traceback (most recent call last): ... TypeError: no canonical coercion from Rational Field to Shuffle Algebra on 3 generators ['x', 'y', 'z'] over Finite Field of size 7
Elements of the base ring coerce in::
sage: F.coerce(GF(7)(5)) 5*B[word: ]
The shuffle algebra over `\ZZ` on `x, y, z` coerces in, since `\ZZ` coerces to `\GF{7}`::
sage: G = ShuffleAlgebra(ZZ,'xyz') sage: Gx,Gy,Gz = G.gens() sage: z = F.coerce(Gx**2 * Gy);z 2*B[word: xxy] + 2*B[word: xyx] + 2*B[word: yxx] sage: z.parent() is F True
However, `\GF{7}` does not coerce to `\ZZ`, so the shuffle algebra over `\GF{7}` does not coerce to the one over `\ZZ`::
sage: G.coerce(x^3*y) Traceback (most recent call last): ... TypeError: no canonical coercion from Shuffle Algebra on 3 generators ['x', 'y', 'z'] over Finite Field of size 7 to Shuffle Algebra on 3 generators ['x', 'y', 'z'] over Integer Ring """ try: R = x.parent()
# shuffle algebras in the same variables over any base # that coerces in: if isinstance(R,ShuffleAlgebra): if R.variable_names() == self.variable_names(): if self.has_coerce_map_from(R.base_ring()): return self(x) else: raise TypeError("no natural map between bases of shuffle algebras")
if isinstance(R, DualPBWBasis): return self(R.expansion(x))
except AttributeError: pass
# any ring that coerces to the base ring of this shuffle algebra. return self._coerce_try(x, [self.base_ring()])
r""" Return ``True`` if there is a coercion from ``R`` into ``self`` and ``False`` otherwise.
The things that coerce into ``self`` are
- Shuffle Algebras in the same variables over a base with a coercion map into ``self.base_ring()``.
- Anything with a coercion into ``self.base_ring()``.
TESTS::
sage: F = ShuffleAlgebra(ZZ, 'xyz') sage: G = ShuffleAlgebra(QQ, 'xyz') sage: H = ShuffleAlgebra(ZZ, 'y') sage: F._coerce_map_from_(G) False sage: G._coerce_map_from_(F) True sage: F._coerce_map_from_(H) False sage: F._coerce_map_from_(QQ) False sage: G._coerce_map_from_(QQ) True sage: F.has_coerce_map_from(PolynomialRing(ZZ, 3, 'x,y,z')) False sage: F._coerce_map_from_(F.dual_pbw_basis()) True """ # shuffle algebras in the same variable over any base that coerces in: else:
""" 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 """
""" 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] """
r""" 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
.. MATH::
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 [Reu1993]_.
INPUT:
- ``R`` -- ring
- ``names`` -- 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])
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 """ def __classcall_private__(cls, R, names): """ Normalize input to ensure a unique representation.
EXAMPLES::
sage: from sage.algebras.shuffle_algebra import DualPBWBasis sage: D1 = DualPBWBasis(QQ, 'ab') sage: D2 = DualPBWBasis(QQ, Alphabet('ab')) sage: D1 is D2 True """
""" Initialize ``self``.
EXAMPLES::
sage: D = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis() sage: TestSuite(D).run() """ category=(AlgebrasWithBasis(R), CommutativeAlgebras(R), CoalgebrasWithBasis(R)))
""" Return a string representation of ``self``.
EXAMPLES::
sage: ShuffleAlgebra(QQ, 'ab').dual_pbw_basis() The dual Poincare-Birkhoff-Witt basis of Shuffle Algebra on 2 generators ['a', 'b'] over Rational Field """
""" Construct an element of ``self`` from ``x``.
EXAMPLES::
sage: A = ShuffleAlgebra(QQ, 'ab') sage: S = A.dual_pbw_basis() sage: S('abaab') S[word: abaab] sage: S(Word('aba')) S[word: aba] sage: S(A('ab')) S[word: ab] """
""" Return ``True`` if there is a coercion from ``R`` into ``self`` and ``False`` otherwise. The things that coerce into ``self`` are:
- Anything that coerces into the associated shuffle algebra of ``self``
TESTS::
sage: F = ShuffleAlgebra(ZZ, 'xyz').dual_pbw_basis() sage: G = ShuffleAlgebra(QQ, 'xyz').dual_pbw_basis() sage: H = ShuffleAlgebra(ZZ, 'y').dual_pbw_basis() sage: F._coerce_map_from_(G) False sage: G._coerce_map_from_(F) True sage: F._coerce_map_from_(H) False sage: F._coerce_map_from_(QQ) False sage: G._coerce_map_from_(QQ) True sage: F.has_coerce_map_from(PolynomialRing(ZZ, 3, 'x,y,z')) False sage: F._coerce_map_from_(F._alg) True """
""" Return the indexing element of the basis element `1`.
EXAMPLES::
sage: S = ShuffleAlgebra(QQ, 'ab').dual_pbw_basis() sage: S.one_basis() word: """
""" 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]) """
""" 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] """
""" 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 """
""" 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 """
def expansion(self): """ 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] """
def expansion_on_basis(self, w): r""" 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] """
""" An element in the dual PBW basis. """ """ 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] """
|