Word Quasi-symmetric functions¶
AUTHORS:
- Travis Scrimshaw (2018-04-09): initial implementation
- Darij Grinberg and Amy Pang (2018-04-12): further bases and methods
-
sage.combinat.chas.wqsym.
WQSymBases
¶ The category of bases of \(WQSym\).
-
sage.combinat.chas.wqsym.
WQSymBasis_abstract
¶ Abstract base class for bases of \(WQSym\).
This must define two attributes:
_prefix
– the basis prefix_basis_name
– the name of the basis (must match one of the names that the basis can be constructed from \(WQSym\))
-
sage.combinat.chas.wqsym.
WordQuasiSymmetricFunctions
¶ The word quasi-symmetric functions.
The ring of word quasi-symmetric functions can be defined as a subring of the ring of all bounded-degree noncommutative power series in countably many indeterminates (i.e., elements in \(R \langle \langle x_1, x_2, x_3, \ldots \rangle \rangle\) of bounded degree). Namely, consider words over the alphabet \(\{1, 2, 3, \ldots\}\); every noncommutative power series is an infinite \(R\)-linear combination of these words. For each such word \(w\), we define the packing of \(w\) to be the word \(\operatorname{pack}(w)\) that is obtained from \(w\) by replacing the smallest letter that appears in \(w\) by \(1\), the second-smallest letter that appears in \(w\) by \(2\), etc. (for example, \(\operatorname{pack}(4112774) = 3112443\)). A word \(w\) is said to be packed if \(\operatorname{pack}(w) = w\). For each packed word \(u\), we define the noncommutative power series \(\mathbf{M}_u = \sum w\), where the sum ranges over all words \(w\) satisfying \(\operatorname{pack}(w) = u\). The span of these power series \(\mathbf{M}_u\) is a subring of the ring of all noncommutative power series; it is called the ring of word quasi-symmetric functions, and is denoted by \(WQSym\).
For each nonnegative integer \(n\), there is a bijection between packed words of length \(n\) and ordered set partitions of \(\{1, 2, \ldots, n\}\). Under this bijection, a packed word \(u = (u_1, u_2, \ldots, u_n)\) of length \(n\) corresponds to the ordered set partition \(P = (P_1, P_2, \ldots, P_k)\) of \(\{1, 2, \ldots, n\}\) whose \(i\)-th part \(P_i\) (for each \(i\)) is the set of all \(j \in \{1, 2, \ldots, n\}\) such that \(u_j = i\).
The basis element \(\mathbf{M}_u\) is also denoted as \(\mathbf{M}_P\) in this situation. The basis \((\mathbf{M}_P)_P\) is called the Monomial basis and is implemented as
Monomial
.Other bases are the cone basis (aka C basis), the characteristic basis (aka X basis), the Q basis and the Phi basis.
Bases of \(WQSym\) are implemented (internally) using ordered set partitions. However, the user may access specific basis vectors using either packed words or ordered set partitions. See the examples below, noting especially the section on ambiguities.
\(WQSym\) is endowed with a connected graded Hopf algebra structure (see Section 2.2 of [NoThWi08], Section 1.1 of [FoiMal14] and Section 4.3.2 of [MeNoTh11]) given by
\[\Delta(\mathbf{M}_{(P_1,\ldots,P_{\ell})}) = \sum_{i=0}^{\ell} \mathbf{M}_{\operatorname{st}(P_1, \ldots, P_i)} \otimes \mathbf{M}_{\operatorname{st}(P_{i+1}, \ldots, P_{\ell})}.\]Here, for any ordered set partition \((Q_1, \ldots, Q_k)\) of a finite set \(Z\) of integers, we let \(\operatorname{st}(Q_1, \ldots, Q_k)\) denote the set partition obtained from \(Z\) by replacing the smallest element appearing in it by \(1\), the second-smallest element by \(2\), and so on.
A rule for multiplying elements of the monomial basis relies on the quasi-shuffle product of two ordered set partitions. The quasi-shuffle product \(\Box\) is given by
ShuffleProduct_overlapping
with the+
operation in the overlapping of the shuffles being the union of the sets. The product \(\mathbf{M}_P \mathbf{M}_Q\) for two ordered set partitions \(P\) and \(Q\) of \([n]\) and \([m]\) is then given by\[\mathbf{M}_P \mathbf{M}_Q = \sum_{R \in P \Box Q^+} \mathbf{M}_R ,\]where \(Q^+\) means \(Q\) with all numbers shifted upwards by \(n\).
Sometimes, \(WQSym\) is also denoted as \(NCQSym\).
REFERENCES:
EXAMPLES:
Constructing the algebra and its Monomial basis:
sage: WQSym = algebras.WQSym(ZZ) sage: WQSym Word Quasi-symmetric functions over Integer Ring sage: M = WQSym.M() sage: M Word Quasi-symmetric functions over Integer Ring in the Monomial basis sage: M[[]] M[]
Calling basis elements using packed words:
sage: x = M[1,2,1]; x M[{1, 3}, {2}] sage: x == M[[1,2,1]] == M[Word([1,2,1])] True sage: y = M[1,1,2] - M[1,2,2]; y -M[{1}, {2, 3}] + M[{1, 2}, {3}]
Calling basis elements using ordered set partitions:
sage: z = M[[1,2,3],]; z M[{1, 2, 3}] sage: z == M[[[1,2,3]]] == M[OrderedSetPartition([[1,2,3]])] True sage: M[[1,2],[3]] M[{1, 2}, {3}]
Note that expressions above are output in terms of ordered set partitions, even when input as packed words. Output as packed words can be achieved by modifying the global options. (See
OrderedSetPartitions.options()
for further details.):sage: M.options.objects = "words" sage: y -M[1, 2, 2] + M[1, 1, 2] sage: M.options.display = "compact" sage: y -M[122] + M[112] sage: z M[111]
The options should be reset to display as ordered set partitions:
sage: M.options._reset() sage: z M[{1, 2, 3}]
Illustration of the Hopf algebra structure:
sage: M[[2, 3], [5], [6], [4], [1]].coproduct() M[] # M[{2, 3}, {5}, {6}, {4}, {1}] + M[{1, 2}] # M[{3}, {4}, {2}, {1}] + M[{1, 2}, {3}] # M[{3}, {2}, {1}] + M[{1, 2}, {3}, {4}] # M[{2}, {1}] + M[{1, 2}, {4}, {5}, {3}] # M[{1}] + M[{2, 3}, {5}, {6}, {4}, {1}] # M[] sage: _ == M[5,1,1,4,2,3].coproduct() True sage: M[[1,1,1]] * M[[1,1,2]] # packed words M[{1, 2, 3}, {4, 5}, {6}] + M[{1, 2, 3, 4, 5}, {6}] + M[{4, 5}, {1, 2, 3}, {6}] + M[{4, 5}, {1, 2, 3, 6}] + M[{4, 5}, {6}, {1, 2, 3}] sage: M[[1,2,3],].antipode() # ordered set partition -M[{1, 2, 3}] sage: M[[1], [2], [3]].antipode() -M[{1, 2, 3}] - M[{2, 3}, {1}] - M[{3}, {1, 2}] - M[{3}, {2}, {1}] sage: x = M[[1],[2],[3]] + 3*M[[2],[1]] sage: x.counit() 0 sage: x.antipode() 3*M[{1}, {2}] + 3*M[{1, 2}] - M[{1, 2, 3}] - M[{2, 3}, {1}] - M[{3}, {1, 2}] - M[{3}, {2}, {1}]
Ambiguities
Some ambiguity arises when accessing basis vectors with the dictionary syntax, i.e.,
M[...]
. A common example is when referencing an ordered set partition with one part. For example, in the expressionM[[1,2]]
, does[[1,2]]
refer to an ordered set partition or does[1,2]
refer to a packed word? We choose the latter: if the received arguments do not behave like a tuple of iterables, then view them as describing a packed word. (In the running example, one argument is received, which behaves as a tuple of integers.) Here are a variety of ways to get the same basis vector:sage: x = M[1,1]; x M[{1, 2}] sage: x == M[[1,1]] # treated as word True sage: x == M[[1,2],] == M[[[1,2]]] # treated as ordered set partitions True sage: M[[1,3],[2]] # treat as ordered set partition M[{1, 3}, {2}] sage: M[[1,3],[2]] == M[1,2,1] # treat as word True
Todo
- Dendriform structure.