Séminaire Lotharingien de Combinatoire 61A (2010), Article B61Aj

HYPEROCTAHEDRAL SPECIES

N. BERGERON AND P. CHOQUETTE

J’ai descendu avec Pierre plusieurs rapides. Parfois c’étais sur l’eau, parfois c’étais en concepts. Merci, Nantel

Abstract. We introduce hyperoctahedral species (H-species) or species of type B, which are analogous to the classical tensor species, but on which we consider the action of the groups of signed permutations. We give a bistrong monoidal functor, a functor which preserves Hopf monoids, between the monoidal categories of species and H-species. We also define bilax monoidal functors (functors which preserve the structure of bimonoids) between the category of H-species and the category of graded vector spaces. Using these functors, the combinatorial Hopf algebra DQSym is shown to arise from the cofree comonoid on the exponential species.

1. Introduction

The theory of species of Joyal [9] has open a lot of interesting problems in combinatorics. In particular, Bergeron [6] used species to find a combinatorial explanation of plethystic substitution and Mendez and Nava [16] studied colored species. Others were interested in generalizing species for modules of other groups. Hetyei et al.

[13] were motivated by various enumerative questions on the n-dimensional cube and defined cubical species, modules for the hyperoctahedral groups. In [12], Henderson generalized Joyal’s species, called B_{r}-modules, to study characters of the representations of W (r, n), the wreath product of the cyclic group of order r and the symmetric group S_{n}, on cohomology of De Concini–Procesi compactifications. Others have been interested in finding relationships between species and well-known algebras such as the descent algebra [17] or combinatorial Hopf algebras [2].

In [2], Aguiar and Mahajan have introduced bilax monoidal functors (functors preserving bimonoids) from the category of species (Sp) to the category of graded vector spaces (gVec). In particular, they showed that many different graded Hopf algebras can arise from one Hopf monoid in species. In this paper, we make an analogous study with hyperoctahedral species as done by Aguiar and Mahajan [2] in the case of species. Hyperoctahedral species, or H-species, which are given in terms of H-sets, are modules of the hyperoctahedral groups. Therefore, the role played by the symmetric groups in species is played by the groups of signed permutations in this setting. We denote by Sp^{H} the category of H-species. Endowed with a symmetric tensor product, it turns into a monoidal category and therefore Hopf monoids can be defined. We construct H-species from usual species by way of a bistrong monoidal functor S sending the regular representation of !S_{n} to the regular representation of B_{n}. We also introduce bilax monoidal functors K^{H} and K̃^{H} to generate graded vector spaces from H-species. Composing these functors (K^{H}S, K̃^{H}S), we get new graded Hopf algebras from usual species. We also give a natural transformation which links our work and the work of Aguiar and Mahajan [2]. We finally discuss an interesting example: the graded Hopf algebra DQSym of diagonally symmetric functions, see [3], arises from the cofree comonoid on the exponential species.

2000 Mathematics Subject Classification. 16W30; 18D10; 05E10.

Many constructions we use are very similar to the ones of Aguiar and Mahajan [2]. In particular, the tensor product on H-species and the functors from H-species to graded vector spaces parallel the same notions for species. The advantage of a similar setting and similar constructions is that as many as four (based on the functors defined in this paper) graded Hopf algebras arise from a a single species. Therefore, natural transformations between our functors and Aguiar and Mahajan’s functors, for example

(1.1)  [figure: Sp^{H}; K̃^{H}; α̃^{S}; Sp; \overline{K}; S; gVec,]

given here by α̃^{S}, give morphisms of graded Hopf algebras in the same family. For example, Aguiar and Mahajan proved that the Hopf algebra of set compositions and the Hopf algebra QSym of quasi-symmetric functions arise from a particular Hopf monoid. Using the functors defined in this paper, we prove that DQSym is in the same family (see Theorem 35) as is the Hopf algebra of H_{S}-set compositions (see Example 29). Furthermore, the natural transformation α̃^{S} yields the morphism of Hopf algebras DQSym → QSym sending a bicomposition to the composition obtained by adding each component of each bipart (see Example 36). This paper is only the starting point of the study of H-species. Further exploration is done in [8], but a lot of interesting problems remain to be done.

Acknowledgements. We would like to thank Marcelo Aguiar for his many suggestions and interesting problems regarding H-species. We also thank the anonymous referee for his numerous and judicious suggestions.

2. Preliminaries

We begin by a brief introduction on monoidal categories and morphisms of such categories, given by lax, colax and bilax monoidal functors. For these notions, see [2, 4, 5, 14]. We then give two examples: the monoidal categories of graded vector spaces and of species. We recall the construction of the cofree comonoid on a species, as done by Aguiar and Mahajan [2]. For more details on species, see [2, 7, 9, 13].

2.1. Monoidal categories. For a definition of monoidal category, see MacLane [15]. For the definitions of monoids, comonoids, bimonoids and Hopf monoids in monoidal categories, see Aguiar and Mahajan [2].

Definition 1 (Bénadou [4] and Aguiar and Mahajan [2]). Let (C, •, e) and (D, ⋄, e′) be two monoidal categories.

(1) A lax monoidal functor (F, ϕ, ϕ_{0}) between (C, •, e) and (D, ⋄, e′) is a functor F: C → D with a morphism ϕ_{a,b}: F a ⋄ F b → F (a • b) in D, natural in a and b for each pair a, b of objects in C, and a morphism ϕ_{0} : e′ → F e in D such that ϕ is associative and left and right unital in the usual sense.

(2) A colax monoidal functor (F, ψ, ψ_{0}) is a functor F: C → D with a morphism ϕ_{a,b}: F (a • b) → F a ⋄ F b in D, natural in a and b for each pair of objects a, b in C, and a morphism ψ_{0} : F e → e′ in D such that ψ is coassociative and left and right counital in the usual sense.

(3) A bilax monoidal functor (F, ϕ, ϕ_{0}, ψ, ψ_{0}) between two braided monoidal categories (C, •, e, β) and (D, ⋄, e′, β) is a lax monoidal functor (F, ϕ, ϕ_{0}) and a colax monoidal functor (F, ψ, ψ_{0}) satisfying the braiding condition and unitality conditions.

(4) A bilax monoidal functor with ϕ, ϕ_{0}, ψ and ψ_{0} invertible is a bistrong monoidal functor.

The composites of lax, colax, bilax and bistrong monoidal functors are lax, colax, bilax and bistrong monoidal functors respectively. A morphism of bilax monoidal functors between (F, ϕ, ψ) and (G, γ, δ) is a natural transformation α: F → G which commutes with ϕ, ψ, γ and δ. See [2] for more details.

Proposition 2 (Bénabou [5] and Aguiar and Mahajan [2]). (1) If F is a lax (colax, bilax) monoidal functor from (C, •) to (D, ⋄) and h is a monoid (comonoid, bimonoid) in C then F h is a monoid (comonoid, bimonoid) in D. Furthermore, a morphism of lax (colax, bilax) monoidal functors Θ: F → G yields a morphism of monoids (comonoids, bimonoids) Θ_{h}: F h → Gh if h is a monoid (comonoid, bimonoid) in C.

(2) If F is a bistrong monoidal functor from (C, •) to (D, ⋄) and h is a Hopf monoid in C with antipode S then F h is a Hopf monoid in D with antipode F S. Moreover, a morphism Θ: F → G of bistrong monoidal functors yields a morphism Θ_{h}: F h → Gh of Hopf monoids if h is a Hopf monoid in C.

For example, the category gVec of graded vector spaces is monoidal. Objects and morphisms of this category are as follow. A vector space V over 𝕂 is said to be graded if it is a sequence V = (V_{n})_{n≥0} of vector spaces over 𝕂. In that case, we often write V = ⨁_{n≥0} V_{n}, where V_{n} is the homogeneous component of degree n in V. A morphism of graded vector spaces f: V → W is a sequence of linear maps (f_{n}: V_{n} → W_{n})_{n≥0}. We often write f = ⨁_{n≥0} f_{n}. This category is monoidal with tensor product defined on the component of degree n by

(V · W)_{n} = ⨁_{i=0}^{n} V_{i} ⊗ W_{n−i}.

2.2. Species. We first recall the definitions of decomposition, set composition and set partition of finite sets and some operations on set compositions. Let I be a finite set. A decomposition of I is an ordered sequence G = (G_{1}, …, G_{k}) of disjoint subsets of I such that G_{1} ∪ G_{2} ∪ ⋯ ∪ G_{k} = I. We write I = G_{1} ⊔ ⋯ ⊔ G_{k}. A set composition of I is a decomposition G = (G_{1}, G_{2}, …, G_{k}) of I in which each G_{i}, 1 ≤ i ≤ k, is nonempty. We write G ⊧ I or G = G_{1}|G_{2}| … |G_{k}. A set partition F = {F_{1}, F_{2}, …, F_{l}} of I is an unordered collection of disjoint nonempty subsets of I such that F_{1} ∪ ⋯ ∪ F_{l} = I. We write F ⊢ I. The subsets G_{i} (F_{i}) are the parts of the composition (partition). For example, 34|1|25 is a set composition of [5] and {15, 234} is a set partition of [5]. We omit brackets around each part for clarity. There is one (empty) set composition (set partition) of the empty set, denoted by ∅.

Let F = F_{1}| … |F_{k} and G = G_{1}| … |G_{l} be two set compositions on disjoint sets S and T, respectively. Note that S ⊔ T denotes the disjoint union of S and T. The restriction of F to a set S′ ⊆ S is the set composition

F |_{S′} = F_{1} ∩ S′| … |F_{k} ∩ S′,

where we delete any empty parts.

The concatenation of F and G is the set composition of S ⊔ T defined by

F |G = F_{1}| … |F_{k}|G_{1}| … |G_{l}.

A shuffle of F and G is a set composition of S ⊔T whose parts are parts of F and G and whose restriction to S is F and whose restriction to T is G. Let F ⊔⊔G denote the set of all shuffles of F and G. For example, 12|3⊔⊔45 = {12|3|45, 12|45|3, 45|12|3}.

A quasishuffle of F and G is a set composition of S ⊔ T whose restriction to S is F and whose restriction to T is G. In other words a quasishuffle is a shuffle such that two adjacent parts F_{i}|G_{j} can be replaced by F_{i} ⊔ G_{j}. Let F G denote the set of all quasishuffles of F and G. For example,

12|3 45 = {12|3|45, 12|45|3, 45|12|3, 12|345, 1245|3}.

Definition 3. A species p with values in Vec_{𝕂}, the category of vector spaces over a field 𝕂 of characteristic zero, is a functor

p: B → Vec_{𝕂},

where B is the category of finite sets with bijections. A morphism of species is a natural transformation α: p → q. Let Sp denote the category of species.

A species is a family of vector spaces p[I], one for each finite set I, together with linear maps p[f]: p[I] → p[J], one for each bijection f: I → J. A morphism of species α: p → q is a family of linear maps α_{I}: p[I] → q[I], one for each finite set I, such that for each bijection f: I → J, the following diagram commutes

(2.1)  \begin{matrix}p[I] & ⟶^{α_{I}} & q[I] \\ ^{p[f]}↓ & & ↓^{q[f]} \\ p[J] & ⟶_{α_{J}} & q[J]. \end{matrix}

We denote by p[n] the vector space p[{1, 2, …, n}], n ≥ 0.

Each permutation σ ∈ S_{n} induces a map

p[σ]: p[n] → p[n],

which turns p[n] into an S_{n}-module. A species p can then equivalently be defined by a sequence of S_{n}-modules.

The category of species is monoidal with tensor product defined by

(p · q)[I] = ⨁_{S⊔T =I} p[S] ⊗ q[T],

and with unit

o[I] = \begin{cases}𝕂 & if I = ∅, \\ 0 & otherwise. \end{cases}

Descriptions of monoids, comonoids, bimonoids and Hopf monoids are found in [2]. They are the same as the ones for H-species in Section 4, by omitting the involution.

Example 4. Two Hopf monoids in (Sp, ·) will be considered in this paper. We give their definitions along with their products and coproducts.

(1) Exponential species.

e[I] := 𝕂, for each finite set I.

Let I denote the only basis element of e[I]. The components μ_{S,T} and Δ_{S,T} of the product and the coproduct are given by

(2.2)  \begin{matrix}e[S] ⊗ e[T] & → e[I] & e[I] & → e[S] ⊗ e[T] \\ S ⊗ T & ↦ S ⊔ T, & I & ↦ S ⊗ T. \end{matrix}

It is a commutative and a cocommutative Hopf monoid. Its antipode is given for any finite I by

(2.3)  S(I) = (−1)^{|I|}I.

(2) Linear order species.

ℓ^{∗}[I] := 𝕂-span of all linear orders on I.

The components μ_{S,T} and Δ_{S,T} of the product and coproduct are

(2.4)

ℓ^{∗}[S] ⊗ ℓ^{∗}[T] → ℓ^{∗}[I]  ℓ^{∗}[I] → ℓ^{∗}[S] ⊗ ℓ^{∗}[T]
l_{1} ⊗ l_{2} ↦ ∑_{l∈l_{1}⊔⊔l_{2}} l,  l ↦ \begin{cases}l|_{S} ⊗ l|_{T} & if S is an initial segment of l, \\ 0 & otherwise. \end{cases}

The direct sum of the product is over all shuffles l of l_{1} and l_{2}.

Note that we use here the dual of the linear order species. For more details, see [2].

A positive species is a species p such that p[∅] = 0. Denote by Sp_{+} the subcategory of positive species. Let

(−)_{+} : Sp → Sp_{+},

be the functor defined by

p_{+}[I] = \begin{cases}p[I] & if I ≠ ∅, \\ 0 & otherwise. \end{cases}

Remark 5 (Aguiar and Mahajan [2]). Any positive species has a monoid structure. Since the functor (−)_{+} preserves monoids, if p is a monoid then p_{+} is a (nonunital) monoid. Any other positive species q can be endowed with the trivial product (the zero map).

The substitution of a species p and a positive species q is defined by

(2.5)  (p ∘ q)[I] := ⨁_{X⊢I} p[X] ⊗ (⨂_{S∈X} q[S]).

For any positive species p,

(2.6)  ℓ^{∗} ∘ p = ⨁_{n≥0} p^{·n},

where p^{·0} = o. Furthermore, for any finite set I,

(ℓ^{∗} ∘ p)[I] = ⨁_{F ⊧I} p(F),

where for a composition F = F_{1}| … |F_{l}, p(F) = p[F_{1}] ⊗ ⋯ ⊗ p[F_{l}].

Proposition 6 (Aguiar and Mahajan [2]). The species ℓ^{∗} ∘ q is the cofree comonoid on a positive species q.

The component Δ_{S,T} of the coproduct of ℓ^{∗} ∘ q is the direct sum of the following maps. For each set composition F_{1}| … |F_{k} ⊧ I for which S is the union of the first i parts, take the identity map

(2.7)  q(F_{1}| … |F_{k}) → q(F_{1}| … |F_{i}) ⊗ q(F_{i+1}| … |F_{k}).

The comonoid ℓ^{∗} ∘ q also carries a canonical Hopf monoid structure. The product is quasishuffle. Fix a decomposition I = S ⊔ T, compositions F ⊧ S, G ⊧ T and a quasishuffle H of F and G. There is a unique map

q(F) ⊗ q(G) → q(H)

obtained by reordering the factors according to the shuffle and then taking the tensor product of the following maps:

(2.8)  q[H_{k}] ← \begin{cases}q[H_{k}] & if H_{k} is a block of F or of G, \\ q[F_{i}] ⊗ q[G_{j}] & if H_{k} = F_{i} ⊔ G_{j}. \end{cases}

If H_{k} is a block of F or of G, use the identity map and if H_{k} = F_{i} ⊔ G_{j}, use the appropriate component of the product of q. Since every positive species is a monoid, see Remark 5, this map is well-defined. In the case that q is the trivial monoid, the product is the shuffle.

Example 7. Consider the Hopf monoid e. Let e_{+} be the positive Hopf monoid defined by

(2.9)  e_{+}[I] = \begin{cases}e[I] & if I ≠ ∅, \\ 0 & otherwise. \end{cases}

Then (ℓ^{∗}∘e_{+})[I] = ⨁_{F ⊧I} e_{+}(F), and denote by F_{1}|F_{2}| … |F_{k} the only basis element in e_{+}(F) = e_{+}[F_{1}]⊗⋯⊗e_{+}[F_{k}]. Therefore, ℓ^{∗}∘e_{+} has a basis given by set compositions.

The product and the coproduct are given by quasishuffle and deconcatenation of set compositions. For example,

μ(1|2, 3) = 1|2|3 + 1|3|2 + 3|1|2 + 1|23 + 13|2,
Δ(4|13|2) = 4|13|2 ⊗ ∅ + 4|13 ⊗ 2 + 4 ⊗ 13|2 + ∅ ⊗ 4|13|2.
3. H-Species

We introduce the category of H-sets along with set compositions of H-sets. We then define hyperoctahedral species, H-species, which are sequences of modules for the hyperoctahedral groups.

Definition 8. An H-set (A, σ) is a finite set A together with an involution σ on A, where σ is without fixed points. A bijection of H-sets between (A, σ) and (B, τ), called an H-bijection, is a bijection f: A → B of finite sets such that this diagram commutes

(3.1)  \begin{matrix}A & ⟶^{f} & B \\ ^{σ}↓ & & ↓^{τ} \\ A & ⟶_{f} & B. \end{matrix}

We write f: (A, σ) → (B, τ) for such an H-bijection.

Let B^{H} be the category of H-sets. There is a natural involution σ_{0} : ℕ∪\overline{ℕ} → ℕ∪\overline{ℕ}, where \overline{ℕ} = \{¯1, ¯2, … \}, defined for i ∈ ℕ and ī ∈ \overline{ℕ} by σ_{0}(i) = ī and σ_{0}(ī) = i. Each time we consider a set S = \{s_{1}, …, s_{k}\} ⊂ ℕ and its negative \overline{S} = \{\overline{s_{1}}, …, \overline{s_{k}}\}, we endow it with the natural involution σ_{0}. In particular, we use σ_{0} for the sets

[n̄, n] = {n̄, …, ¯1, 1, …, n},

n ≥ 0, and for the sets

[±(a, b)] = \{b̄, \overline{b − 1}, …, ā, a, a + 1, … b\},

for a, b ∈ ℕ and a ≤ b. We omit the involution when using σ_{0}. For example, \overline{S} ⊔ S := (\overline{S} ∪ S, σ_{0}) and [n̄, n] := ([n̄, n], σ_{0}).

Consider the quotient set of A by σ:

(3.2)  A/σ = {[a] : a ∈ A}.

A section is a map

s: A/σ → A

which is a right inverse for the projection A → A/σ. In particular, s([a]) ∈ {a, σ(a)}. For the sets [n̄, n], we identify [n̄, n]/σ_{0} with [n], for each n ≥ 0, and we denote a section s by the list of its images (s(1), s(2), …, s(n)) or equivalently by omitting commas and brackets: s(1)s(2) … s(n).

We define next two order-preserving H-bijections on H-sets of integers of the form S̄ ⊔ S for S ⊂ ℕ. The natural order on the sets [n̄, n] is

n̄ < ⋯ < ¯1 < 1 < ⋯ < n,

and any subset S of [n] inherits this order.

The canonical map, can, and the standardization map, st, are defined to be the only order-preserving maps between sets of same cardinality. Explicitly, if S, T ⊂ ℕ with |S| = |T | = n then

(3.3)  st_{S}: S̄ ⊔ S → [n̄, n] and can: S̄ ⊔ S → T̄ ⊔ T.

We denote by can_{s} the map can_{s}: [n̄, n] → [±(s + 1, s + n)].

We define next two analogous notions of set partitions on H-sets. The first one is a set partition for which each part of the partition is an H-set and the second is a set partition on particular subsets of an H-set. For the following definitions, let (A, σ) be an H-set.

Definition 9. An H-subset (S, σ_{S}) of (A, σ) is a set S, such that

S ⊂ A and σ_{S}(S) = S,

where σ_{S}: S → S is the restriction of σ to the set S and is defined by σ_{S}(s) = σ(s), for all s ∈ S. If S is an H-subset of [n̄, n], we use σ_{0} for the restriction.

Definition 10. (1) An H-decomposition F of (A, σ) is an ordered sequence F = (F_{1}, …, F_{l}) of disjoint H-subsets of (A, σ) such that ⋃_{i=1}^{l} F_{i} = A. We write F_{1} ⊔ ⋯ ⊔ F_{l} = A.

(2) An H-set composition F of (A, σ) is an H-decomposition F = (F_{1}, …, F_{l}) of (A, σ) in which each F_{i} is nonempty. We write F = F_{1}|F_{2}| … |F_{l} or F ⊧ A. The H-subsets F_{i} are the parts of the H-set composition.

(3) An H-set partition P of (A, σ) is an unordered collection of disjoint nonempty H-subsets of (A, σ) such that ⋃_{S∈P} S = A. We write P ⊢ A. The H-subsets S are the parts of the H-set partition.

There is one (empty) H-set composition (H-set partition) of the empty set, denoted by ∅.

Remark 11. The H-decompositions of H-sets of the form [n̄, n] are in bijection with decompositions of the finite sets [n], n ≥ 0.

Definition 12. (1) An H_{S}-set composition F of (A, σ) is a set composition of

s(A/σ), for any section s. We write F ⊧_{S} (A, σ).

(2) An H_{S}-set partition P of (A, σ) is a set partition of s(A/σ) for any section s. We write P ⊢_{S} (A, σ).

Definition 13. A hyperoctahedral species, or species of type B (H-species), with values in Vec_{𝕂}, the category of vector spaces over a field 𝕂 of characteristic zero with linear maps, is a functor

p : B^{H} → Vec_{𝕂}.

A morphism of H-species is a natural transformation α: p → q. Let Sp^{H} denote the category of H-species.

An H-species consists of a family of vector spaces p[A, σ], one for each H-set (A, σ), and a family of linear maps

p[f]: p[A, σ] → p[B, τ],

one for each H-bijection f: (A, σ) → (B, τ). The space p[A, σ] is the space of pstructures on (A, σ). For the sets [n̄, n], n ≥ 0, we write p[n̄, n] instead of p[([n̄, n], σ_{0})].

A morphism of H-species consists of a family of linear maps

α_{A,σ}: p[A, σ] → q[A, σ],

one for each H-set (A, σ), such that for each H-bijection f: (A, σ) → (B, τ), this diagram

(3.4)  \begin{matrix}p[A, σ] & ⟶^{α_{A,σ}} & q[A, σ] \\ ^{p[f]}↓ & & ↓^{q[f]} \\ p[B, τ] & ⟶_{α_{B,τ}} & q[B, τ] \end{matrix}

commutes. We may abbreviate α_{[n̄,n]} by α_{n} or α_{S̄⊔S}: p[S̄ ⊔ S] → q[S̄ ⊔ S] by α_{S}. Also, the identity 1_{n} may either denote the identity linear map 1_{n}: p[n̄, n] → p[n̄, n] or the identity H-bijection 1_{n}: [n̄, n] → [n̄, n].

Remark 14. The group of automorphisms of the H-set [n̄, n] is the hyperoctahedral group or the group of signed permutations, B_{n}. More generally, the group of Hbijections taking (A, σ) to itself is denoted by B_{A,σ}, and it is isomorphic to B_{n}, if |A| = 2n.

Proposition 15. An H-species p can be defined as a sequence

V_{0}, V_{1}, V_{2}, …

of modules of the hyperoctahedral groups, and morphisms of H-species are degree preserving maps of B_{n}-modules.

Proof. Since p is a functor, each π ∈ B_{n} induces a map

p[π]: p[n̄, n] → p[n̄, n]

of vector spaces, which turns p[n̄, n] into a B_{n}-module. A morphism of H-species α: p → q gives rise to degree-preserving maps α_{n}: p[n̄, n] → q[n̄, n], n ≥ 0, of B_{n}- modules.

Conversely, let V_{0}, V_{1}, V_{2}, … be a sequence of modules of the hyperoctahedral groups, with action π.V_{n}, π ∈ B_{n}. Define an H-species p as p[A, σ] = V_{n}, for any H-set (A, σ) of cardinality 2n. For any H-bijection f: (A, σ) → (B, τ), consider the composite g = st_{B} ∘ f ∘ st_{A}^{−1}, where st_{A} and st_{B} are any bijections (A, σ) → [n̄, n] and (B, τ) → [n̄, n] respectively. Then g ∈ B_{n} and let p[f] := g.V_{n}. □

Remark 16. The category of cubical species, defined by Hetyei et al. in [13], is equivalent to the category of H-species. See [8] for more details.

Example 17. (1) Exponential H-species.

e_{H}[A, σ] := 𝕂, for each H-set (A, σ).

Let A denote the only basis element of e_{H}[A, σ]. This is the trivial representation.

(2) H-species of linear orders.

ℓ_{H}[A, σ] = 𝕂-span of linear orders on s(A/σ), for all sections s: A/σ → A

= ⨁_{s: A/σ→A} ℓ[s(A/σ)],

where ℓ is the usual species of linear order. It is the regular representation. For example,

ℓ_{H}[¯2, 2] = ℓ[{1, 2}] ⊕ ℓ[{¯1, 2}] ⊕ ℓ[{1, ¯2}] ⊕ ℓ[{¯1, ¯2}].

(3) H-species of sections.

s[A, σ] = 𝕂[s(A/σ) | s: A/σ → A].

(4) H-species of sets of sections. F[A, σ] is the 𝕂-span of the following sets of sections: for each H-subset (T, σ_{T}) of (A, σ), let S = {s_{1}, …, s_{k}} be the set of sections on A/σ with s_{i}(T/σ_{T}) fixed, 1 ≤ i ≤ k, where k = 2^{|(A\T)/σ|}. Each H-subset (T, σ_{T}) give rise to 2^{|T/σ_{T} |} basis elements. For example,

(3.5)  \begin{matrix}F[¯2, 2] = 𝕂[ & \{12\}, \{¯12\}, \{1¯2\}, \{¯1¯2\}, \{12, 1¯2\}, \\ \{¯12, ¯1¯2\}, \{¯12, 12\}, \{¯1¯2, 1¯2\}, \{12, ¯12, 1¯2, ¯1¯2\}]. \end{matrix}

4. Tensor product and Hopf monoids

We set the definitions for monoids, comonoids, bimonoids and Hopf monoids in the monoidal category of H-species.

Proposition 18. (Sp^{H}, ·, o, β) is a symmetric monoidal category, with tensor product

(4.1)  (p · q)[A, σ] = ⨁_{S⊔T =A} p[S, σ_{S}] ⊗ q[T, σ_{T}],

where the direct sum is over H-decompositions, see Definition 10. The unit for this product is

o[A, σ] = \begin{cases}𝕂 & if A = ∅, \\ 0 & otherwise. \end{cases}

The braiding β_{p,q}: p · q → q · p has components given by

(4.2)  \begin{matrix}p[S, σ_{S}] ⊗ q[T, σ_{T}] & → q[T, σ_{T}] ⊗ p[S, σ_{S}] \\ x ⊗ y & ↦ y ⊗ x. \end{matrix}

The axioms, found in [15], are straightforward to check.

A monoid (p, μ, η) in Sp^{H} is an H-species p with product μ and unit η,

μ: p · p → p, η: o → p,

associative and unital in the usual sense. There is one linear map μ_{A,σ} for each H-set (A, σ) and let

μ_{S,T} : p[S, σ_{S}] ⊗ p[T, σ_{T}] → p[A, σ]

be the components of the product, one for each H-decomposition S ⊔ T = A. There is one linear map for the unit

η_{∅}: 𝕂 → p[∅].

A comonoid (p, Δ, ϵ) in Sp^{H} is an H-species p with a coproduct Δ and counit ϵ,

Δ: p → p · p, ϵ: p → o,

coassociative and counital in the usual sense. There is one map Δ_{A,σ} for each H-set (A, σ) and let

Δ_{S,T} : p[A, σ] → p[S, σ_{S}] ⊗ p[T, σ_{T}]

be the components of the coproduct, one for each H-decomposition S ⊔ T = A. Only one map is non-trivial for the counit, namely when A = ∅:

ϵ_{∅}: p[∅] → 𝕂.

A bimonoid (h, μ, η, Δ, ϵ) is a monoid (h, μ, η) and a comonoid (h, Δ, ϵ) such that Δ and ϵ are morphisms of monoids. A Hopf monoid (h, μ, η, Δ, ϵ, s) is a bimonoid (h, μ, η, Δ, ϵ) with an H-species morphism s: h → h, the antipode, such that for each nonzero H-set (A, σ), the composites

(4.3) \xymatrix{h[A, σ] \ar[r]^{⊕Δ_{S,T}} & ⨁ h[S, σ_{S}] ⊗ h[T, σ_{T}] \ar[r]^{1_{S}⊗s_{T}} & ⨁ h[S, σ_{S}] ⊗ h[T, σ_{T}] \ar[r]^{⊕μ_{S,T}} & h[A, σ], \\ h[A, σ] \ar[r]^{⊕Δ_{S,T}} & ⨁ h[S, σ_{S}] ⊗ h[T, σ_{T}] \ar[r]^{s_{S}⊗1_{T}} & ⨁ h[S, σ_{S}] ⊗ h[T, σ_{T}] \ar[r]^{⊕μ_{S,T}} & h[A, σ]}

are zero, where the direct sums are over H-decompositions S ⊔ T = A, and such that the following equation for the empty set is satisfied:

(4.4)  μ_{∅,∅} ∘ (1 ⊗ s_{∅}) ∘ Δ_{∅,∅} = η_{∅} ∘ ϵ_{∅} = μ_{∅,∅} ∘ (s_{∅} ⊗ 1) ∘ Δ_{∅,∅}.

As is the case for graded bialgebras, if a bimonoid h is connected, i.e., h[∅] = 𝕂, then h is a Hopf monoid. See [2] for details.

Example 19. (1) The H-species e_{H} is a Hopf monoid. Recall that A denotes the only basis element in e_{H}[A, σ]. The components of the product and the coproduct are given by

\begin{matrix}e_{H}[S, σ_{S}] ⊗ e_{H}[T, σ_{T}] & → e_{H}[S ⊔ T] & e_{H}[A, σ] & → e_{H}[S, σ_{S}] ⊗ e_{H}[T, σ_{T}] \\ S ⊗ T & ↦ S ⊔ T, & A & ↦ S ⊗ T. \end{matrix}

Solving (4.3) recursively, the antipode is found to be

(4.5)  S(A) = (−1)^{|A/σ|}A.

(2) The H-species ℓ_{H} is a Hopf monoid. The components of the product are

(4.6)  \begin{matrix}ℓ_{H}[S, σ_{S}] ⊗ ℓ_{H}[T, σ_{T}] & → ℓ_{H}[A, σ] \\ l_{1} ⊗ l_{2} & ↦ l_{1}l_{2}, \end{matrix}

where for l_{1} = l_{1}^{1} … l_{1}^{i} a linear order on s(S/σ_{S}) and l_{2} = l_{2}^{1} … l_{2}^{j} a linear order on s′(T/σ_{T}) for some sections s and s′,

l_{1}l_{2} = l_{1}^{1} … l_{1}^{i}l_{2}^{1} … l_{2}^{j}

is the concatenation. Then l_{1}l_{2} is a linear order on s′′(A/σ) where

s′′([a]) = \begin{cases}s([a]) & if [a] ∈ S/σ_{S}, \\ s′([a]) & if [a] ∈ T/σ_{T}. \end{cases}

The components of the coproduct are given by deshuffling:

(4.7)  \begin{matrix}ℓ_{H}[A, σ] & → ℓ_{H}[S, σ_{S}] ⊗ ℓ_{H}[T, σ_{T}] \\ l & ↦ l_{S} ⊗ l_{T} , \end{matrix}

where for l = l_{1} … l_{k} a linear order on s(A/σ), for some section s, l_{S} is the sublist of l consisting of elements of S. Then l_{S} and l_{T} are linear orders on s′(S/σ_{S}) and s′′(T/σ_{T}) respectively, where s′ = s|_{S/σ_{S}} and s′′ = s|_{T/σ_{T}}.

Since this species is connected, it is a Hopf monoid. By solving recursively (4.3), one can compute the antipode S: ℓ_{H} → ℓ_{H} for any linear order l on s(A/σ) to be

S(l) = (−1)^{|l|}l̃,

where |l| is the length of l and if l = l_{1} … l_{k} then l̃= l_{k} … l_{2}l_{1}.

(3) The H-species F of faces of sections (see Example 17(4)) is a Hopf monoid. Let F = {s_{1}, …, s_{k}} and G = {s′_{1}, …, s′_{l}} be two sets of sections on S and T, where S ⊔ T = A. Each s_{i} and s′_{j}, for 1 ≤ i ≤ k and 1 ≤ j ≤ l, is a set. The components of the product are given by

(4.8)  μ_{S,T} ({s_{1}, …, s_{k}}, {s′_{1}, …, s′_{l}}) = {s_{i} ⊔ s′_{j} : 1 ≤ i ≤ k, 1 ≤ j ≤ l}.

Let H = {s_{1}, …, s_{m}} be a set of sections of (A, σ). The components of the coproduct are given by

(4.9)  Δ_{S,T} (H) = H|_{S} ⊗ H|_{T} ,

where H|_{S} = {s_{1} ∩ S, …, s_{k} ∩ S}. We delete any empty sets. For example,

μ({13, ¯13}, {¯2}) = {1¯23, ¯1¯23},

Δ({12, 1¯2}) = {12, 1¯2} ⊗ ∅ + {1} ⊗ {2, ¯2} + {2, ¯2} ⊗ {1} + ∅ ⊗ {12, 1¯2}.

5. Functors

In this section, we define a functor S: Sp → Sp^{H} and two functors

K^{H}, K̃^{H}: Sp^{H} → gVec.

We also make explicit the natural transformation α̃^{S} of (1.1).

Definition 20. The functor

S : Sp → Sp^{H}

is defined, for a species p, an H-set (A, σ) and an H-bijection f: (A, σ) → (B, τ) by

(5.1)  \begin{aligned}Sp[A, σ] & = ⨁_{s: A/σ→A} p[s(A/σ)], \\ Sp[f] & = ⨁_{s: A/σ→A} p[f|_{s(A/σ)}]. \end{aligned}

Proposition 21. S is a bistrong monoidal functor.

Verifying the axioms is straightforward in this case. See [8] for details.

Example 22. The H-species S(ℓ^{∗} ∘e_{+}) has a basis given by the set of H_{S}-set compositions, see Definition 10. Since ℓ^{∗} ∘ e_{+} is a Hopf monoid by the discussion following Proposition 6 and S is bistrong, S(ℓ^{∗}∘e_{+}) is a Hopf monoid. The coproduct of an H_{S}- set composition is the deconcatenation and the product of two H_{S}-set compositions is the quasishuffle, as defined by the maps (2.7) and (2.8).

Let G be a group and V be a G-module. Then V_{G} := V/{x − gx : g ∈ G, x ∈ V } is the space of G-coinvariants of V.

Proposition 23 (Aguiar and Mahajan [2]). The functors K, \overline{K}: Sp → gVec defined by

(5.2)  Kp = ⨁_{n≥0} p[n] and \overline{K}p = ⨁_{n≥0} p[n]_{S_{n}}

are such that K is bilax monoidal and \overline{K} is bistrong monoidal.

The analogous functors Sp^{H} → gVec for H-species are as follows.

Definition 24. Let

K^{H}, K̃^{H}: Sp^{H} → gVec

be defined, for p ∈ Sp^{H}, by

(5.3)  \begin{aligned}K^{H}p & = ⨁_{n≥0} p[n̄, n], \\ K̃^{H}p & = ⨁_{n≥0} p[n̄, n]_{S_{n}}. \end{aligned}

Proposition 25. K^{H} is a bilax monoidal functor with natural transformations ϕ and ψ:

(5.4)  \xymatrix{K^{H}p · K^{H}q \ar[r]^{ϕ_{p,q}} & K^{H}(p · q), \ar[l]^{ψ_{p,q}}}

defined respectively by the direct sums over s + t = n and S ⊔ T = A of these maps:

(5.5)

1_{s} ⊗ q[can_{s}]: p[s̄, s] ⊗ q[t̄, t] → p[s̄, s] ⊗ q[±(s + 1, s + t)],
p[st_{S}] ⊗ q[st_{T}]: p[S̄ ⊔ S] ⊗ q[T̄ ⊔ T] → p[\overline{|S|}, |S|] ⊗ q[\overline{|T |}, |T |].

Proof. We give an idea of the proof for ϕ and the same can be done for ψ using the dual axioms. For a detailed proof, see [8]. First, we verify that ϕ is a natural transformation. Let α: p → p′ and β: q → q′ be two morphisms of H-species. Then, by fixing s and t, we have

(5.6)

p[s̄, s] ⊗ q[t̄, t] ⟶^{1_{s}⊗q[can_{s}]} p[s̄, s] ⊗ q[±(s + 1, s + t)]
α_{s}⊗β_{t}↓  ↓^{α_{s}⊗β_{[±(s+1,s+t)]}}
p′[s̄, s] ⊗ q′[t̄, t] ⟶^{1_{s}⊗q′[can_{s}]} p′[s̄, s] ⊗ q′[±(s + 1, s + t)].

The diagram commutes since α and β are natural transformations and can_{s} is an Hbijection. We check next that ϕ is associative and that ϕ and ψ satisfy the braiding condition. All the unitality conditions follow, since the maps involved are isomorphisms.

Associativity. The map ϕ leads to an unambiguous map

\xymatrix{K^{H}p · K^{H}q · K^{H}r \ar[r] & K^{H}(p · q · r)}

defined, by fixing s, t and u, by

p[s̄, s] ⊗ q[t̄, t] ⊗ r[ū, u]
1_{s}⊗q[can_{s}]⊗r[can_{s+t}]
p[s̄, s] ⊗ q[±(s + 1, s + t)] ⊗ r[±(s + t + 1, s + t + u)].

Braiding. The following equality must be satisfied, for all H-species p, q, r, s,

(5.7)  (ϕ_{p,r} · ϕ_{q,s}) ∘ (1 · β · 1) ∘ (ψ_{p,q} · ψ_{r,s}) = ψ_{p·r,q·s} ∘ K^{H}(1 · β · 1) ∘ ϕ_{p·q,r·s},

which are two maps

(5.8)  K^{H}(p · q) · K^{H}(r · s) → K^{H}(p · r) · K^{H}(q · s).

Fix degrees n and m along with decompositions S ⊔ T = [n] and A ⊔ B = [m] on the left-hand side of (5.8). Then the left-hand side of (5.7) can be written as

(5.9) (ϕ_{p,r}·ϕ_{q,s})∘(1·β·1)∘(ψ_{p,q}·ψ_{r,s}) = p[st_{S}]⊗β(q[st_{T}]⊗r[can_{|S|}∘st_{A}])∘s[can_{|T |}∘st_{B}].

Let

(5.10)  S = {s_{1}, …, s_{p}} and A = {a_{1}, …, a_{r}}

be ordered. Then

st_{S}: \overline{S} ⊔ S → [|\overline{S}|, |S|]

is such that st_{S}(s_{i}) = i and st_{S}(\overline{s_{i}}) = ī. Also,

\xymatrix{\overline{A} ⊔ A \ar[r]^{^{st^{A}}} & [|\overline{A}|, |A|] \ar[r]^{^{can^{|S|}}} & [±(|S| + 1, |S| + |A|)],}

is such that (can_{|S|} ∘ st_{A})(a_{i}) = can_{|S|}(i) = i + |S| and (can_{|S|} ∘ st_{A})(\overline{a_{i}}) = can_{|S|}(ī) = \overline{i + |S|}. A similar description can be made for the sets T and B. The right-hand side of (5.7) can be written as

(5.11)  p[st_{|S|+|A|}] ⊗ β(q[st_{|T |+|B|}] ⊗ r[st_{|S|+|A|} ∘ can_{n}]) ⊗ s[st_{|T |+|B|} ∘ can_{n}].

Consider the same sets S and A of (5.10) and the following composites

\xymatrix{ & \overline{S} ⊔ S \ar[r]^{^{st^{|S|+|A|}}} & [\overline{(|S| + |A|)}, (|S| + |A|)], \\ \overline{A} ⊔ A \ar[r]^{_{can_{n}}} & \overline{A^{+n}} ⊔ A^{+n} \ar[r]^{_{st_{|S|+|A|}}} & [\overline{(|S| + |A|)}, (|S| + |A|)],}

where A^{+n} = \{a+n : a ∈ A\}. The domain of the bijection st_{|S|+|A|} is (\overline{S} ⊔S)⊔(\overline{A^{+n}} ⊔ A^{+n}) and it preserves the relative order. Since S ⊂ [n] and a+n > n for all a ∈ A, we have st_{|S|+|A|}(s_{i}) = i, st_{|S|+|A|}(\overline{s_{i}}) = ī, (st_{|S|+|A|} ∘ can_{n})(a_{i}) = st_{|S|+|A|}(a_{i} + n) = i + |S| and (st_{|S|+|A|} ∘ can_{n})(\overline{a_{i}}) = st_{|S|+|A|}(\overline{a_{i} + n}) = \overline{i + |S|}. A similar description can be made for the sets T and B. Hence, the two maps of (5.7) are indeed identical and the braiding condition is satisfied.

□

Proposition 26. K̃^{H} is a bistrong monoidal functor.

Proof. Define ϕ̃_{p,q} and ψ̃_{p,q} with the following commutative diagrams:

(5.12)  \xymatrix{K^{H}p · K^{H}q \ar[r]^{ϕ_{p,q}} \ar@{->>}[d] & K^{H}(p · q) \ar@{->>}[d] & K^{H}p · K^{H}q \ar@{->>}[d] & K^{H}(p · q) \ar[l]_{ψ_{p,q}} \ar@{->>}[d] \\ \overline{K^{H}}p · \overline{K^{H}}q \ar@{-->}[r]_{ϕ̃_{p,q}} & \overline{K^{H}}(p · q), & \overline{K^{H}}p · \overline{K^{H}}q & \overline{K^{H}}(p · q). \ar@{-->}[l]^{ψ̃_{p,q}}}

We prove that ψ is well-defined, and the same can be done for ϕ. For more details, see [8].

Consider the component of degree n of K^{H}(p · q), along with a decomposition S ⊔ T = [n] with |S| = s and |T | = t. Let τ ∈ S_{n} and suppose that τ(S) = U and that τ(T) = V. Then τ send S̄ to Ū and T̄ to V̄.

Let τ_{S} = τ|_{S̄⊔S}: S̄ ⊔ S → Ū ⊔ U and τ_{T} = τ|_{T̄⊔T} : T̄ ⊔ T → V̄ ⊔ V. These two Hbijections induce two other H-bijections on [s̄, s] and on [t̄, t]. Let τ_{s}: [s̄, s] → [s̄, s] be defined by τ_{s} = st_{U} ∘τ_{S} ∘st_{S}^{−1} and let τ_{t}: [t̄, t] → [t̄, t] be defined by τ_{t} = st_{V} ∘τ_{T} ∘st_{T}^{−1}. Since ψ is a natural transformation, the following diagram commutes

\xymatrix{p[S̄ ⊔ S] ⊗ q[T̄ ⊔ T] \ar[r]^{p[st_{S}]⊗q[st_{T}]} \ar[d]_{p[π_{S}]⊗q[π_{T}]} & p[s̄, s] ⊗ q[t̄, t] \ar[d]^{p[π_{s}]⊗q[π_{t}]} \\ p[Ū ⊔ U] ⊗ q[V̄ ⊔ V] \ar[r]_{p[st_{U}]⊗q[st_{V} ]} & p[s̄, s] ⊗ q[t̄, t]}

which means that ψ factors through the space of B_{n}-coinvariants of (p · q)[n̄, n].

Furthermore, since ϕ̃ and ψ̃ are invertible, K̃^{H} is a bistrong monoidal functor. □

Since K^{H} is a bilax monoidal functor, K^{H}h is a graded bialgebra for any bimonoid h in Sp^{H}, by Proposition 2. Furthermore, since K̃^{H} is bistrong, K̃^{H}h′ is a graded Hopf algebra for any Hopf monoid h′ in Sp^{H}, by Proposition 2.

Example 27. Consider K^{H}F, where F is the Hopf monoid of sets of sections of Example 19(3). Let F = {s_{1}, …, s_{k}} be a set of sections on [n]. So each s_{j} is a section [n] → [n̄, n]. Define

F^{+} := {i : s_{j}(i) = i, 1 ≤ j ≤ k}, F^{−} := {i : s_{j}(i) = ī, 1 ≤ j ≤ k}
and F^{∗} = [n]\(F^{+} ∪ F^{−}).

Now, encode F by a word w_{F} in letters a, b, c, where the i-th letter of w_{F} is

w_{F} (i) = \begin{cases}a & if i ∈ F^{+}, \\ b & if i ∈ F^{−}, \\ c & otherwise. \end{cases}

For example, the word associated to F = {(1, 2, ¯3, 4), (1, ¯2, ¯3, 4), (1, 2, ¯3, ¯4), (1, ¯2, ¯3, ¯4)} is w_{F} = acbc and the one for G = {(1, ¯2)} is w_{G} = ab. The product of K^{H}F is given by concatenation and the coproduct by deshuffle of words. Therefore, K^{H}F ≅ 𝕂⟨a, b, c⟩ as bialgebras.

Consider the composites K^{H}S and K̃^{H}S of the functors S: Sp → Sp^{H} and K^{H}, K̃^{H}: Sp^{H} → gVec. The composite K^{H}S is a bilax monoidal functor and the composite K̃^{H}S is a bistrong monoidal functor.

Example 28. The H-species Se has a basis given by sections. Since S is bistrong and e is a Hopf monoid, Se is a Hopf monoid. Therefore K̃^{H}Se is a graded Hopf algebra described as follow.

Each element of the basis of K̃^{H}Se is an equivalence class of sections under the action of S_{n}. Two sections are in the same class if the number of negative integers (and hence the number of positive integers) is the same. Such a class [s] can be represented as a polynomial p(x, y) = x^{s^{+}}y^{s^{−}}, where s^{+} and s^{−} are respectively the number of positive and negative integers in s. Furthermore, the product, coming from the product of e, is concatenation of polynomials, and the coproduct is deshuffle. As a Hopf algebra, K̃^{H}Se is isomorphic to 𝕂[x, y].

Example 29. Recall from Example 22 that S(ℓ^{∗}∘e_{+}) is the H-species of H_{S}-set compositions. Therefore, K^{H}S(ℓ^{∗}∘e_{+}) is the graded Hopf algebra of H_{S}-set compositions with quasishuffle product and deconcatenation coproduct.

The relation between the functor K^{H}S and the functor K, i.e., the natural transformation α^{S} in this diagram

(5.13)  [figure: Sp^{H}; α^{S}; K^{H}; Sp; S; K; gVec,]

is given in the next proposition.

Proposition 30. The map α^{S} : K^{H}S → K, defined, for any p ∈ Sp, by

(5.14)  α_{p}^{S} = _{⨁_{n≥0} ; s: [n]→[n̄,n]}p[s^{−1}],

where s^{−1} : s([n]) → [n] is the unique bijection s^{−1}(i) = |i|, i ∈ s([n]), where for j ∈ [n], |j| = |j̄| = j, is a morphism of bilax monoidal functors.

Proof. We prove that α^{S} is a natural transformation. The map α^{S} assigns a linear map α_{p}^{S} for each object p ∈ Sp. Furthermore, for each arrow β : p → q in Sp, by fixing n, we get the following diagram

(5.15)  \begin{matrix}⨁ p[s([n])] & \underrightarrow{⨁ p[s^{−1}]} & p[n] \\ ^{⨁ β_{s([n])}}↓ & & ↓^{β_{n}} \\ ⨁ q[s([n])] & \overrightarrow{⨁ q[s^{−1}]} & q[n], \end{matrix}

where the direct sums are over sections s: [n] → [n̄, n]. Since β is a natural transformation and s^{−1} : s([n]) → [n] is a bijection, it commutes.

For the proof that α^{S} is a morphism of bilax monoidal functors, see [8]. □

The natural transformation α^{S} factors through the space of S_{n}-coinvariants of Sp[n̄, n]:

\xymatrix{⨁ p[s([n])] \ar[r]^{α_{p}^{S}} \ar@{->>}[d] & p[n] \ar@{->>}[d] \\ (⨁ p[s([n])])_{S_{n}} \ar@{-->}[r]_{α_{p}^{S}} & p[n]_{S_{n}}.}

Therefore, α̃^{S} : K̃^{H}S → \overline{K} is the map induced by α^{S} on the space of S_{n}-coinvariants.

Since α^{S} is a morphism of bilax monoidal functor and α̃^{S} is a morphism of bistrong monoidal functor, for any bimonoid h in Sp, α_{h}^{S} is a morphism of graded bialgebras and for any Hopf monoid h′ in Sp, α̃_{h′}^{S} is a morphism of graded Hopf algebras, by Proposition 2.

Example 31. Consider the linear order species ℓ^{∗}. On the one hand K^{H}Sℓ^{∗} is isomorphic to the graded bialgebra of signed permutations 𝕂B, and on the other hand Kℓ^{∗} is isomorphic to the graded bialgebra of Malvenuto and Reutenauer 𝕂S (see [2]). See [1] for details on these Hopf algebras.

In this case, α_{ℓ^{∗}}^{S}: 𝕂B → 𝕂S is the graded bialgebra morphism forgetting the signs of a signed permutation. It is defined by α^{S}(π) = |π|, where, if π = π_{1}π_{2} … π_{n} is a signed permutation, then |π| = |π_{1}||π_{2}| … |π_{n}|.

6. Hopf algebra of set compositions

As a final word, we study the species ℓ^{∗} ∘ e_{+} under the composite of functors

Sp ⟶^{S} Sp^{H} \underrightarrow{K̃^{H}} gVec,

and we give the Hopf algebra isomorphism K̃^{H}S(ℓ^{∗} ∘ e_{+}) ≃ DQSym. Let DQΛ = K̃^{H}S(ℓ^{∗} ∘ e_{+}). Explicitly,

(6.1)  DQΛ := ⨁_{n≥0}( ⨁_{s:[n]→[n̄,n]} ⨁_{F ⊧s([n])} e_{+}(F))_{S_{n}}.

Recall from Example 22 that S(ℓ^{∗} ∘ e_{+}) has a basis given by H_{S}-set compositions.

Definition 32. A bicomposition a = ( \begin{matrix}α_{1} \\ β_{1} \end{matrix} ⋯ \begin{matrix}α_{k} \\ β_{k} \end{matrix} ) of n ≠ 0 is an ordered list of 1 × 2

vectors ( \begin{matrix}α_{i} \\ β_{i} \end{matrix} ) ≠ ( \begin{matrix}0 \\ 0 \end{matrix} ), called biparts, such that ∑_{i=1}^{k}(α_{i} + β_{i}) = n. If n = 0, there is one (empty) bicomposition, denoted by 0 or (). The length of a bicomposition is the number of biparts, denoted by ℓ(a). Let a ⊧ n denote a bicomposition of n.

For example, the bicompositions of n = 2 are

(\begin{matrix}2 \\ 0 \end{matrix}), (\begin{matrix}1 \\ 0 \end{matrix} \begin{matrix}1 \\ 0 \end{matrix}), (\begin{matrix}1 \\ 1 \end{matrix}), (\begin{matrix}1 \\ 0 \end{matrix} \begin{matrix}0 \\ 1 \end{matrix}), (\begin{matrix}0 \\ 1 \end{matrix} \begin{matrix}1 \\ 0 \end{matrix}), (\begin{matrix}0 \\ 1 \end{matrix} \begin{matrix}0 \\ 1 \end{matrix}), (\begin{matrix}0 \\ 2 \end{matrix}).

Let a = ( \begin{matrix}α_{1} \\ β_{1} \end{matrix} ⋯ \begin{matrix}α_{k} \\ β_{k} \end{matrix} ) and b = ( \begin{matrix}α′_{1} \\ β′_{1} \end{matrix} ⋯ \begin{matrix}α′_{l} \\ β′_{l} \end{matrix} ) be two bicompositions. The concatenation a.b, the addition a + b and the quasishuffle a b are given respectively by

a.b = (\begin{matrix}α_{1} \\ β_{1} \end{matrix} ⋯ \begin{matrix}α_{k} \\ β_{k} \end{matrix} \begin{matrix}α′_{1} \\ β′_{1} \end{matrix} ⋯ \begin{matrix}α′_{l} \\ β′_{l} \end{matrix}),
a + b = (\begin{matrix}α_{1} \\ β_{1} \end{matrix} ⋯ \begin{matrix}α_{k} + α′_{1} \\ β_{k} + β′_{1} \end{matrix} ⋯ \begin{matrix}α′_{l} \\ β′_{l} \end{matrix}),

a b = \begin{cases}a & if b = 0, \\ b & if a = 0, \\ ⋃_{a_{1}.a_{2}=a} ⋃_{c∈a_{2} b_{2}}\{a_{1}.b_{1}.c, (a_{1} + b_{1}).c\} & otherwise, \end{cases}

where b = b_{1}.b_{2} is the unique factorization of b such that ℓ(b_{1}) = 1. In other words c ∈ a b if c can be obtained by shuffling the columns of a and b and two adjacent columns coming from different bicompositions can be added using ( \begin{matrix}α_{i} \\ β_{i} \end{matrix} ) + ( \begin{matrix}α′_{j} \\ β′_{j} \end{matrix} ) =

( \begin{matrix}α_{i}+α′_{j} \\ β_{i}+β′_{j} \end{matrix} ). For example,

(\begin{matrix}2 \\ 0 \end{matrix}) (\begin{matrix}1 \\ 0 \end{matrix} \begin{matrix}0 \\ 1 \end{matrix}) = \{(\begin{matrix}2 \\ 0 \end{matrix} {1 \atop 0} \begin{matrix}0 \\ 1 \end{matrix}), (\begin{matrix}1 \\ 0 \end{matrix} {2 \atop 0} \begin{matrix}0 \\ 1 \end{matrix}), (\begin{matrix}1 \\ 0 \end{matrix} {0 \atop 1} \begin{matrix}2 \\ 0 \end{matrix}), (\begin{matrix}3 \\ 0 \end{matrix} \begin{matrix}0 \\ 1 \end{matrix}), (\begin{matrix}1 \\ 0 \end{matrix} \begin{matrix}2 \\ 1 \end{matrix})\}.

Definition 33. DQSym is the Hopf algebra of diagonally quasisymmetric functions linearly spanned by

{M_{a} : a bicomposition},

where M_{a} are the bimonomial functions. The product and the coproduct are given respectively by quasishuffle and deconcatenation of bicompositions.

See [3] for more detailed information about this Hopf algebra.

Proposition 34. There is a bijection between basis elements of DQΛ and bicompositions.

Proof. Basis elements of DQΛ are classes of H_{S}-set compositions. For an H_{S}-set composition F, the number of positive integers in the i-th part will be denoted by |F_{i}|^{+} and the number of negative integers in the i-th part will denoted by |F_{i}|^{−}. Let F and G be two H_{S}-set compositions. Suppose that for all i, |F_{i}|^{+} = |G_{i}|^{+} and |F_{i}|^{−} = |G_{i}|^{−}. In particular |F_{i}| = |G_{i}| and ℓ(F) = ℓ(G). Build a permutation π by setting π(F_{i}^{+}) = G_{i}^{+} and π(F_{i}^{−}) = G_{i}^{−} for each i, 1 ≤ i ≤ ℓ(F). Therefore π(F) = G and F and G are in the same class. Form a bicomposition a = ( \begin{matrix}α_{1} \\ β_{1} \end{matrix} ⋯ \begin{matrix}α_{k} \\ β_{k} \end{matrix} ) from an H_{S}-set composition F of n integers, by setting α_{i} and β_{i} to be respectively |F_{i}|^{+} and |F_{i}|^{−}. It is a bicomposition as each vector is non-zero and the sum of its integers is n.

Conversely, form an H_{S}-set composition F from a bicomposition a = ( \begin{matrix}α_{1} \\ β_{1} \end{matrix} ⋯ \begin{matrix}α_{k} \\ β_{k} \end{matrix} ) by building each part of F, where the i-th part is given by the positive integers:

α_{1} + β_{1} + ⋯ + α_{i−1} + β_{i−1} + 1, …, α_{1} + β_{1} + ⋯ + α_{i−1} + β_{i−1} + α_{i},

and the negative integers:

\overline{α_{1} + β_{1} + ⋯ + α_{i} + 1}, …, \overline{α_{1} + β_{1} + ⋯ + α_{i} + β_{i}}.

This H_{S}-set composition is a representative of a class of DQΛ with α_{i} negative integers and β_{i} positive integers in the i-th part, 1 ≤ i ≤ k. Hence for each bicomposition, there is a unique class of DQΛ associated to it. □

By Example 22, the product of S(ℓ^{∗} ∘ e_{+}) is the quasishuffle and the coproduct is deconcatenation of H_{S}-set compositions. Since K̃^{H} is bistrong by Proposition 26, the product and coproduct of DQΛ is given by quasishuffle and by deconcatenation of bicompositions. For example, using the product and coproduct of S(ℓ^{∗} ∘ e_{+}), the natural transformations (5.5) of the bistrong monoidal functor K̃^{H} and the bijection and representatives described in Proposition 34, we have

μ([¯1¯2], [can(¯1|2)]) = μ([¯1¯2], [¯3|4]) = [¯1¯2|¯3|4] + [¯3|¯1¯2|4] + [¯3|4|¯1¯2] + [¯1¯2¯3|4] + [¯3|¯1¯24]

= [¯1¯2|¯3|4] + [¯1|¯2¯3|4] + [¯1|2|¯3¯4] + [¯1¯2¯3|4] + [¯1|¯2¯34]

= (\begin{matrix}0 \\ 2 \end{matrix} {0 \atop 1} \begin{matrix}1 \\ 0 \end{matrix}) + (\begin{matrix}0 \\ 1 \end{matrix} {0 \atop 2} \begin{matrix}1 \\ 0 \end{matrix}) + (\begin{matrix}0 \\ 1 \end{matrix} {1 \atop 0} \begin{matrix}0 \\ 2 \end{matrix}) + (\begin{matrix}0 \\ 3 \end{matrix} \begin{matrix}1 \\ 0 \end{matrix}) + (\begin{matrix}0 \\ 1 \end{matrix} \begin{matrix}1 \\ 2 \end{matrix})

= (\begin{matrix}0 \\ 2 \end{matrix}) (\begin{matrix}0 \\ 1 \end{matrix}\begin{matrix}1 \\ 0 \end{matrix}),

Δ([¯1|¯23]) = [¯1|¯23] ⊗ [∅] + [¯1] ⊗ [st(¯23)] + [∅] ⊗ [¯1|¯23]

= [¯1|¯23] ⊗ [∅] + [¯1] ⊗ [¯12] + [∅] ⊗ [¯1|¯23]

= \binom{0 1}{1 1} ⊗ () + \binom{0}{1} ⊗ \binom{1}{1} + () ⊗ \binom{0 1}{1 1}

= Δ(\binom{1 1}{0 1}).

Theorem 35.

(6.2)  DQΛ ≃ DQSym as Hopf algebras.

Proof. The isomorphism sending a bicomposition a = ( \begin{matrix}α_{1} \\ β_{1} \end{matrix} \begin{matrix}α_{2} \\ β_{2} \end{matrix} ⋯ \begin{matrix}α_{k} \\ β_{k} \end{matrix} ) to the bimonomial basis M_{a} is one of bialgebras as it preserves product and coproduct. Since S(ℓ^{∗}∘e_{+}) is a Hopf monoid and by Proposition 26, K̃^{H} is a bistrong monoidal functor, the isomorphism is one of Hopf algebras. □

Example 36. Since K̃^{H}S(ℓ^{∗} ∘ e_{+}) ≅ DQSym and \overline{K}(ℓ^{∗} ∘ e_{+}) ≅ QSym, the Hopf algebra of quasisymmetric functions (see [2] for the isomorphism and [11] for QSym), the map α̃^{S}_{ℓ^{∗}∘e_{+}} is the morphism of graded Hopf algebras:

DQSym → QSym
M_{(\begin{matrix}α_{1} \\ β_{1} \end{matrix}\begin{matrix}α_{2} \\ β_{2} \end{matrix}_{···}\begin{matrix}α_{k} \\ β_{k} \end{matrix})} ↦ M_{(α_{1}+β_{1},α_{2}+β_{2},...,α_{k}+β_{k})}.

References

[1] M. Aguiar, N. Bergeron, K. Nyman, The peak algebra and the descent algebras of type B and D, Trans. Amer. Math. Soc. 356 (7) (2004), 2781–2824.

[2] M. Aguiar, S. Mahajan, Monoidal functors, species and Hopf algebras, in preparation,

    www.math.tamu.edu/~maguiar.

[3] J.-C. Aval, F. Bergeron, N. Bergeron, Diagonal Temperley–Lieb invariants and harmonics, Sém. Lothar. Combin. 54A (2005), Art. B54Aq.

[4] J. Bénabou, Catégories avec multiplication, C. R. Acad. Sci. Paris 256 (1963), 1887–1890.

[5] J. Bénabou, Introduction to bicategories, Reports of the Midwest Category Seminar, Springer, Berlin, 1967, 1–77.

[6] F. Bergeron, Une combinatoire du pléthysme, J. Comb. Th. Ser. A 46 (1987), 291–305.

[7] F. Bergeron, G. Labelle, P. Leroux, Théorie des espèces et combinatoire des structures arborescentes, Publ. LACIM 19, Montréal, 1994; English translation: Combinatorial species and tree-like structures, Cambridge University Press, Cambridge, 1998.

[8] P. Choquette, Species of type B and related graded Hopf algebras, Ph.D. Thesis, York University, 2010.

[9] A. Joyal, Foncteurs analytiques et espèces de structures, Lectures Notes in Math. 1234 (1986), Springer, Berlin, 126–159.

[10] A. Joyal, R. Street, The Category of representations of the general linear groups over a finite field, J. Algebra 176 (1995), 908–946.

[11] I. M. Gessel, Multipartite P -partitions and inner products of skew Schur functions, Combinatorics and Algebra (Boulder, Colo., 1983), Amer. Math. Soc., Providence, R.I., 1984, 289–317.

[12] A. Henderson, Representations of wreath products on cohomology of De Concini–Procesi compactifications, Int. Math. Res. Not. 20 (2004), 983–1021.

[13] G. Hetyei, G. Labelle, P. Leroux, Cubical species and nonassociative algebras, Adv. Appl. Math. 21 (1998), 499–546.

[14] T. Leinster, Higher operads, higher categories, London Math. Soc. Lecture Notes Series 298, Cambridge Univ. Press, Cambridge, 2004.

[15] S. Mac Lane, Categories for the working mathematician, 2nd edition, Grad. Texts in Math. 5, Springer, New York, 1998.

[16] M. Méndez, O. Nava, Colored species, c-monoids, and plethysm, J. Comb. Th. Ser. A 64 (1993), 102–129.

[17] F. Patras, C. Reutenauer, On descent algebras and twisted bialgebras, Moscow Math. J., 4(1) (2004), 199–216.

[18] M. E. Sweedler, Hopf algebras, Math. Lect. Notes Ser., W.A. Benjamin, Inc., New York, 1969.

Mathematics and Statistics, York University, 4700 Keele St., Toronto, ON, M5A 4T5, Canada

E-mail address: bergeron@mathstat.yorku.ca
E-mail address: philcho@mathstat.yorku.ca