Free Quasi-symmetric functions¶
AUTHORS:
- Frédéric Chapoton, Darij Grinberg (2017)
-
sage.combinat.fqsym.
FQSymBases
¶ The category of graded bases of \(FQSym\) indexed by permutations.
-
sage.combinat.fqsym.
FQSymBasis_abstract
¶ Abstract base class for bases of FQSym.
This must define two attributes:
_prefix
– the basis prefix_basis_name
– the name of the basis and must match one of the names that the basis can be constructed from FQSym
-
sage.combinat.fqsym.
FreeQuasisymmetricFunctions
¶ The free quasi-symmetric functions.
The Hopf algebra \(FQSym\) of free quasi-symmetric functions over a commutative ring \(R\) is the free \(R\)-module with basis indexed by all permutations (i.e., the indexing set is the disjoint union of all symmetric groups). Its product is determined by the shifted shuffles of two permutations, whereas its coproduct is given by splitting a permutation (regarded as a word) into two (at every possible point) and standardizing the two pieces. This Hopf algebra was introduced in [MR]. See [GriRei18] (Chapter 8) for a treatment using modern notations.
In more detail: For each \(n \geq 0\), consider the symmetric group \(S_n\). Let \(S\) be the disjoint union of the \(S_n\) over all \(n \geq 0\). Then, \(FQSym\) is the free \(R\)-module with basis \((F_w)_{w \in S}\). This \(R\)-module is graded, with the \(n\)-th graded component being spanned by all \(F_w\) for \(w \in S_n\). A multiplication is defined on \(FQSym\) as follows: For any two permutations \(u \in S_k\) and \(v \in S_l\), we set
\[F_u F_v = \sum F_w ,\]where the sum is over all shuffles of \(u\) with \(v[k]\). Here, the permutations \(u\) and \(v\) are regarded as words (by writing them in one-line notation), and \(v[k]\) means the word obtained from \(v\) by increasing each letter by \(k\) (for example, \((1,4,2,3)[5] = (6,9,7,8)\)); and the shuffles \(w\) are translated back into permutations. This defines an associative multiplication on \(FQSym\); its unity is \(F_e\), where \(e\) is the identity permutation in \(S_0\).
In Section 1.3 of [AguSot05], Aguiar and Sottile construct a different basis of \(FQSym\). Their basis, called the monomial basis and denoted by \((\mathcal{M}_u)\), is also indexed by permutations. It is connected to the above F-basis by the relation
\[F_u = \sum_v \mathcal{M}_v ,\]where the sum ranges over all permutations \(v\) such that each inversion of \(u\) is an inversion of \(v\). (An inversion of a permutation \(w\) means a pair \((i, j)\) of positions satisfying \(i < j\) and \(w(i) > w(j)\).) The above relation yields a unitriangular change-of-basis matrix, and thus can be used to compute the \(\mathcal{M}_u\) by Mobius inversion.
Another classical basis of \(FQSym\) is \((G_w)_{w \in S}\), where \(G_w = F_{w^{-1}}\). This is just a relabeling of the basis \((F_w)_{w \in S}\), but is a more natural choice from some viewpoints.
The algebra \(FQSym\) is often identified with (“realized 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. Consider the \(R\)-linear map that sends each \(G_u\) to the sum of all words whose standardization (also known as “standard permutation”; see
standard_permutation()
) is \(u\). This map is an injective \(R\)-algebra homomorphism, and thus embeds \(FQSym\) into the latter ring.As an associative algebra, \(FQSym\) has the richer structure of a dendriform algebra. This means that the associative product
*
is decomposed as a sum of two binary operations\[x y = x \succ y + x \prec y\]that satisfy the axioms:
\[(x \succ y) \prec z = x \succ (y \prec z),\]\[(x \prec y) \prec z = x \prec (y z),\]\[(x y) \succ z = x \succ (y \succ z).\]These two binary operations are defined similarly to the (associative) product above: We set
\[F_u \prec F_v = \sum F_w ,\]where the sum is now over all shuffles of \(u\) with \(v[k]\) whose first letter is taken from \(u\) (rather than from \(v[k]\)). Similarly,
\[F_u \succ F_v = \sum F_w ,\]where the sum is over all remaining shuffles of \(u\) with \(v[k]\).
Todo
Decide what \(1 \prec 1\) and \(1 \succ 1\) are.
Note
The usual binary operator
*
is used for the associative product.EXAMPLES:
sage: F = algebras.FQSym(ZZ).F() sage: x,y,z = F([1]), F([1,2]), F([1,3,2]) sage: (x * y) * z F[1, 2, 3, 4, 6, 5] + ...
The product of \(FQSym\) is associative:
sage: x * (y * z) == (x * y) * z True
The associative product decomposes into two parts:
sage: x * y == F.prec(x, y) + F.succ(x, y) True
The axioms of a dendriform algebra hold:
sage: F.prec(F.succ(x, y), z) == F.succ(x, F.prec(y, z)) True sage: F.prec(F.prec(x, y), z) == F.prec(x, y * z) True sage: F.succ(x * y, z) == F.succ(x, F.succ(y, z)) True
\(FQSym\) is also known as the Malvenuto-Reutenauer algebra:
sage: algebras.MalvenutoReutenauer(ZZ) Free Quasi-symmetric functions over Integer Ring
REFERENCES: