Last time we looked at the descending tree morphism between the combinatorial Hopf algebras SSym and YSym with fundamental bases consisting of (indexed by) permutations and binary trees respectively. We previously also looked at a Hopf algebra QSym with a basis consisting of compositions.
There are also morphisms between SSym/YSym and QSym. However, before we look at these, we need to look at an alternative basis for QSym.
When I introduced QSym, I defined a type QSymM for the basis, without explaining what the M stands for. It actually stands for "monomial" (but I'm not going to explain why quite yet). Now, of course it is possible to construct any number of alternative bases for QSym, by taking linear combinations of the QSymM basis elements. However, most of these alternative bases are not likely to be very mathematically useful. (By mathematically useful, I mean, for example, that it leads to a simple expression for the multiplication rule.) When looking at the relation between QSym and SSym/YSym, there is another basis for QSym that leads to a clearer picture of their relationship, called the fundamental basis.
We will represent the fundamental basis by a new type:
newtype QSymF = QSymF [Int] deriving (Eq) instance Ord QSymF where compare (QSymF xs) (QSymF ys) = compare (sum xs, xs) (sum ys, ys) instance Show QSymF where show (QSymF xs) = "F " ++ show xs qsymF :: [Int] -> Vect Q QSymF qsymF xs | all (>0) xs = return (QSymF xs) | otherwise = error "qsymF: not a composition"
In a moment, I'll describe the relationship between the monomial and fundamental bases, but first, there's something I need to explain.
If the monomial and fundamental bases are bases for the same Hopf algebra (QSym), how can they be different types? So I think what it comes down to is that if we have different types then we get to have different Show instances. So we will be able to choose whether to view an element of QSym in terms of the monomial or the fundamental basis.
We could have achieved this in other ways, say by designating the monomial basis as the "true" basis, and then providing functions to input and output using the fundamental basis. Giving the fundamental basis its own type is more egalitarian: it puts the two bases on an equal footing.
Okay then, so in order to make this all work, we need to define the relationship between the two bases, and provide functions to convert between them. Let's take a look.
A (proper) refinement of a composition is any composition which can be obtained from the first composition by splitting one or more of the parts of the first composition.
refinements (x:xs) = [y++ys | y <- compositions x, ys <- refinements xs] refinements [] = [[]] > refinements [1,3] [[1,1,1,1],[1,1,2],[1,2,1],[1,3]]
Then the fundamental basis can be expressed in terms of the monomial basis, as follows:
qsymFtoM :: (Eq k, Num k) => Vect k QSymF -> Vect k QSymM qsymFtoM = linear qsymFtoM' where qsymFtoM' (QSymF alpha) = sumv [return (QSymM beta) | beta <- refinements alpha]
For example:
> qsymFtoM (qsymF [1,3]) M [1,1,1,1]+M [1,1,2]+M [1,2,1]+M [1,3]
Conversely, elements of the monomial basis can be expressed as sums of elements of the fundamental basis, as follows:
qsymMtoF :: (Eq k, Num k) => Vect k QSymM -> Vect k QSymF qsymMtoF = linear qsymMtoF' where qsymMtoF' (QSymM alpha) = sumv [(-1) ^ (length beta - length alpha) *> return (QSymF beta) | beta <- refinements alpha] > qsymMtoF (qsymM [1,3]) F [1,1,1,1]-F [1,1,2]-F [1,2,1]+F [1,3]
So we can input elements of QSym using either the monomial or fundamental basis (using the qsymM and qsymF constructors). Shortly, we'll define Algebra and Coalgebra instances for QSymF, so that we can perform arithmetic in either basis. Finally, we can output in either basis, by using the conversion functions if necessary.
How do we know that QSymF is a basis? How do we know that its elements are linearly independent, and span the space? In Vect Q QSymF, this is guaranteed by the free vector space construction. But what the question is really asking is, how do we know that the image of the "basis" QSymF in Vect Q QSymM (via qsymFtoM) is a basis?
Well, it will be linearly independent if qsymFtoM is injective, and spanning if qsymFtoM is surjective. So we require that qsymFtoM is bijective. This follows if we can show that qsymFtoM and qsymMtoF are mutual inverses. Well, quickCheck seems to think so:
> quickCheck (\x -> x == (qsymMtoF . qsymFtoM) x) +++ OK, passed 100 tests. > quickCheck (\x -> x == (qsymFtoM . qsymMtoF) x) +++ OK, passed 100 tests.
(For the cognoscenti: The reason this works is that qsymMtoF' is the Mobius inversion of qsymFtoM' in the poset of compositions ordered by refinement.)
Okay, so we have an alternative basis for QSym as a vector space. What do the multiplication and comultiplication look like relative to this new basis? Now, it is possible to define the algebra, coalgebra and Hopf algebra structures explicitly in terms of the QSymF basis, but I'm going to cheat, and just round-trip via QSymM:
instance (Eq k, Num k) => Algebra k QSymF where
unit x = x *> return (QSymF [])
mult = qsymMtoF . mult . (qsymFtoM `tf` qsymFtoM)
instance (Eq k, Num k) => Coalgebra k QSymF where
counit = unwrap . linear counit' where counit' (QSymF xs) = if null xs then 1 else 0
comult = (qsymMtoF `tf` qsymMtoF) . comult . qsymFtoM
instance (Eq k, Num k) => Bialgebra k QSymF where {}
instance (Eq k, Num k) => HopfAlgebra k QSymF where
antipode = qsymMtoF . antipode . qsymFtoM
(Recall that `tf` is the tensor product of linear maps.)
It's kind of obvious from the definitions that the algebra, coalgebra and Hopf algebra laws will be satisfied. (It's obvious because we already know that these laws are satisfied in Vect Q QSymM, and the definitions for Vect Q QSymF are just the same, but under the change of basis.) However, for additional confidence, we can for example:
> quickCheck (prop_Algebra :: (Q, Vect Q QSymF, Vect Q QSymF, Vect Q QSymF) -> Bool) +++ OK, passed 100 tests.
Okay, so the reason for introducing the fundamental basis for QSym is that there is a Hopf algebra morphism from SSym to QSym, which is easiest to express in terms of their respective fundamental bases. Specifically, we can define a map between the bases, SSymF -> QSymF, which lifts (using fmap, ie using the free vector space functor) to a map between the Hopf algebras.
Given a permutation p of [1..n], a descent is an index i such that p(i) > p(i+1). For example, the permutation [2,3,5,1,6,4] has descents from the 5 to the 1 and from the 6 to the 4. We can think of the descents as splitting the permutation into segments, each of which is strictly ascending. Thus 235164 splits into 235-16-4. If we count the lengths of these segments, we get a composition, which I call the descent composition. Here's the code:
descentComposition [] = [] descentComposition xs = descComp 0 xs where descComp c (x1:x2:xs) = if x1 < x2 then descComp (c+1) (x2:xs) else (c+1) : descComp 0 (x2:xs) descComp c [x] = [c+1] > descentComposition [2,3,5,1,6,4] [3,2,1]
We can lift this map between the bases to a map between the Hopf algebras.
descentMap :: (Eq k, Num k) => Vect k SSymF -> Vect k QSymF descentMap = nf . fmap (\(SSymF xs) -> QSymF (descentComposition xs))
Now, it turns out that this is a Hopf algebra morphism. That is, it commutes with the algebra, coalgebra and Hopf algebra structures.
> quickCheck (prop_AlgebraMorphism descentMap) +++ OK, passed 100 tests. > quickCheck (prop_CoalgebraMorphism descentMap) +++ OK, passed 100 tests. > quickCheck (prop_HopfAlgebraMorphism descentMap) +++ OK, passed 100 tests.
Why does this work? Well, let's work through an example, for comultiplication. (In the following I omit brackets and commas for brevity.) If we do the descent map before the comultiplication, we get:
2341 (SSymF) -> (descentMap) 31 (QSymF) -> (qsymFtoM - sum of refinements) 31+211+121+1111 (QSymM) -> (comult - deconcatenations) []⊗31 + 3⊗1 + 31⊗[] + []⊗211 + 2⊗11 + 21⊗1 + 211⊗[] + []⊗121 + 1⊗21 + 12⊗1 + 121⊗[] + []⊗1111 + 1⊗111 + 11⊗11 + 111⊗1 + 1111⊗[] (QSymM⊗QSymM)
(We convert to QSymM at the second step because it's in QSymM that we know how to comultiply. It is possible to give an explicit expression for the comultiplication in terms of the QSymF basis, but I wanted to keep things simple.)
Conversely, if we do the comultiplication before the descent map:
2341 (SSymF) -> (comult - flattened deconcatenations) []⊗2341 + 1⊗231 + 12⊗21 + 123⊗1 + 2341⊗[] (SSymF⊗SSymF) -> (descentMap⊗descentMap) []⊗31 + 1⊗21 + 2⊗11 + 3⊗1 + 31⊗[] (QSymF⊗QSymF) -> (qsymFtoM⊗qsymFtoM - sum of refinements) []⊗(31+211+121+1111) + 1⊗(21+111) + (2+11)⊗11 + (3+21+12+111)⊗1 + (31+211+121+1111)⊗[] (QSymM⊗QSymM)
The result comes out the same, whichever way round you go, as required. But why does it work? Well, you can imagine the inventor going through the following thought process:
- Comult in SSymF is by flattened deconcatenations (of permutations), and in QSymM is by deconcatenations (of compositions). If we split a permutation at a descent, the descents on either side are preserved. So we could try sending a permutation in SSymF to its descent composition in QSymM. For example, ssymF [2,3,4,1] -> qsymM [3,1], which deconcatenates to [2,3,4]⊗[1] -> [3]⊗[1].
- However, a deconcatenation in SSymF might split a permutation partway through an ascending segment. For example, [2,3,4,1] -> [2,3]⊗[4,1] (which flattens to [1,2]⊗[2,1]). Taking this to descent compositions would give [2]⊗[1,1]. This is not a deconcatenation of qsymM [3,1] - it is however a deconcatenation of [2,1,1], which is a one-step refinement of [3,1].
- So we could try sending a permutation in SSymF to its descent composition in QSymM, and its one-step refinements. For example, ssymF [2,3,4,1] -> qsymM [3,1] + qsymM [2,1,1] + qsymM [1,2,1].
- But now that means that [2,3]⊗[4,1] (flattening omitted for clarity) -> [2]⊗[1,1] + [1,1]⊗[1,1]. The second term is a deconcatenation of [1,1,1,1], a two-step refinement of [3,1].
- It's pretty obvious that the way to make it all work out is to send a permutation in SSymF to its descent composition in QSymM, and all its proper refinements.
- But this sum, of a composition and all its refinements (in QSymM) is just exactly how we defined the QSymF basis.
Exercise: Explain why descentMap commutes with mult.
Exercise: Last time we looked at a descendingTreeMap : SSym -> YSym. Show that the descentMap : SSym -> QSym factors through the descendingTreeMap, and describe the other factor f : YSym -> QSym.
No comments:
Post a Comment