# Lagrange's Theorem for Hopf Monoids in Species

Marcelo Aguiar<fnref n="1" />†and Aaron Lauve<fnref n="2" />‡

**Abstract.** We prove Lagrange's theorem for Hopf monoids in the category of connected species. We deduce necessary conditions for a given subspecies $k$ of a Hopf monoid $h$ to be a Hopf submonoid: each of the generating series of $k$ must divide the corresponding generating series of $k$ in $N[[x]]$. Among other corollaries we obtain necessary inequalities for a sequence of nonnegative integers to be the sequence of dimensions of a Hopf monoid. In the set-theoretic case the inequalities are linear and demand the non negativity of the binomial transform of the sequence.

**Résumé.** Nous prouvons le théorème de Lagrange pour les monoïdes de Hopf dans la catégorie des espèces connexes. Nous déduisons des conditions nécessaires pour qu'une sous-espèce $k$ d'un monoïde de Hopf $h$ soit un sous-monoïde de Hopf: chacune des séries génératrices de $k$ doit diviser la série génératrice correspondante de $h$ dans $N[[x]]$. Parmi d'autres corollaires nous trouvons des inégalités nécessaires pour qu'une suite d'entiers soit la suite des dimensions d'un monoïde de Hopf. Dans le cas ensembliste les inégalités sont linéaires et exigent que la transformée binomiale de la suite soit non négative.

**Keywords:** Hopf monoids, species, graded Hopf algebras, Lagrange's theorem, generating series

## Introduction

Lagrange's theorem states that for any subgroup $K$ of a group $H$, $H \cong K \times Q$ as (left) $K$-sets, where $Q = H/K$. In particular, if $H$ is finite, $|K|$ divides $|H|$. Passing to group algebras over a field $k$, we have that $kH \cong kK \otimes kQ$ as (left) $kK$-modules, or that $kH$ is free as a $kK$-module. Kaplansky [6] conjectured that the same statement holds for Hopf algebras (group algebras being principal examples). It turns out that the result does not hold in general, as shown by Oberst and Schneider [13, Proposition 10] and [11, Example 3.5.2]. On the other hand, the result does hold for large classes of Hopf algebras, including the finite dimensional ones by a theorem Nichols and Zoeller [12], and the pointed ones by a theorem of Radford [16]. More information can be found in Sommerhäuser's survey [15].

The main result of this paper (Theorem 7) is a version of Lagrange's theorem for Hopf monoids in the category of connected species. (Hopf algebras are Hopf monoids in the category of vector spaces.) An immediate application is a test for Hopf submonoids (Corollary 12): if any one of the generating series for

<footnote n="1">¹Department of Mathematics, Texas A&M University, College Station, TX, USA</footnote>

<footnote n="2">²Department of Mathematics and Statistics, Loyola University Chicago, Chicago, IL, USA</footnote>

<footnote>†Aguiar supported in part by NSF grant DMS-1001935. maguiar@math.tamu.edu</footnote>

<footnote>‡Lauve supported in part by NSA grant H98230-10-1-0362. lauve@math.luc.edu</footnote>
a subspecies k does not divide the corresponding generating series for the Hopf monoid h (in the sense that the quotient has negative coefficients), then k is not a Hopf submonoid of h. A similar test also holds for connected graded Hopf algebras (Corollary 4). The proof of Theorem 7 (for Hopf monoids in species) parallels Radford’s proof (for Hopf algebras).

This abstract is organized as follows. In Section 1, we recall Lagrange’s theorem for several classes of Hopf algebras. In Section 2, we recall the basics of Hopf monoids in species and prove Lagrange’s theorem in this setting. We conclude in Section 3 with some examples and applications involving the associated generating series. Among these, we derive necessary conditions for a sequence of nonnegative integers to be the sequence of dimensions of a connected Hopf monoid in species.

# 1 Lagrange's theorem for Hopf algebras

We begin by recalling a couple of versions of this theorem. (All vector spaces are over a fixed field $k$.)

**Theorem 1** Let $H$ be a finite dimensional Hopf algebra over a field $k$. If $K \subseteq H$ is any Hopf subalgebra, then $H$ is a free left (and right) $K$-module.

This is the Nichols-Zoeller theorem [12]; see also [11, Theorem 3.1.5]. We will not make direct use of this result, but rather the related results discussed below.

A Hopf algebra $H$ is *pointed* if all its simple subcoalgebras are one dimensional. Equivalently, the group-like elements of $H$ linearly span the coradical of $H$. Given a subspace $K$ of $H$, let

$$K_+ := K \cap \ker(\epsilon)$$

where $\epsilon: H \to k$ is the counit of $H$. Also, $K_+H$ denotes the right $H$-ideal generated by $K_+$.

**Theorem 2** Let $H$ be a pointed Hopf algebra. If $K \subseteq H$ is any Hopf subalgebra, then $H$ is a free left (and right) $K$-module. Moreover, $H \cong K \otimes (H/K_+H)$ as left $K$-modules.

The first statement is due to Radford [16, Section 4] and the second (stronger) statement is due to Schneider [14, Remark 4.14]. See Sommerhäuser’s survey [15] for further generalizations.

A Hopf algebra $H$ is *graded* if there is given a decomposition

$$H = \bigoplus_{n \ge 0} H_n$$

into linear subspaces that is preserved by all operations. It is *connected* if in addition $H_0$ is linearly spanned by the unit element.

**Theorem 3** Let $H$ be a graded connected Hopf algebra. If $K \subseteq H$ is a graded Hopf subalgebra, then $H$ is a free left (and right) $K$-module. Moreover,

$$H \cong K \otimes (H/K_+H)$$

as left $K$-modules and as graded vector spaces.
**Proof:** Since $H$ is connected graded, its coradical is $H_0 = \mathbb{k}$, so $H$ is pointed and Theorem 2 applies. Radford's proof shows that there exists a graded vector space $Q$ such that

$$H \cong K \otimes Q$$

as left $K$-modules and as graded vector spaces. (The argument we give in the parallel setting of Theorem 7 makes this clear.) Note that $K_+ = \bigoplus_{n \ge 1} K_n$, and $K_+H$ and $H/K_+H$ inherit the grading of $H$. To complete the proof, it suffices to show that $Q \cong H/K_+H$ as graded vector spaces. $\square$

Given a graded Hopf algebra $H$, let $\mathcal{P}_H(x) \in \mathbb{N}[x]$ denote its Poincaré series—the formal power series enumerating the dimensions of its graded components,

$$\mathcal{P}_H(x) := \sum_{n \ge 0} \dim H_n x^n.$$

Suppose $H$ is graded connected and $K$ is a graded Hopf subalgebra. In this case, their Poincaré series are of the form $1 + a_1x + a_2x^2 + \dots$ with $a_i \in \mathbb{N}$ and the quotient $\mathcal{P}_H(x)/\mathcal{P}_K(x)$ is a well-defined power series in $\mathbb{Z}[x]$.

**Corollary 4** Let $H$ be a connected graded Hopf algebra. If $K \subseteq H$ is any graded Hopf subalgebra, then the quotient $\mathcal{P}_H(x)/\mathcal{P}_K(x)$ of Poincaré series is nonnegative, i.e., belongs to $\mathbb{N}[x]$.

**Proof:** By Theorem 3, $H \cong K \otimes Q$ as graded vector spaces, where $Q = H/K_+H$. Hence $\mathcal{P}_H(x) = \mathcal{P}_K(x) \mathcal{P}_Q(x)$ and the result follows. $\square$

**Example 5** Consider the Hopf algebra $\mathcal{QSym}$ of quasisymmetric functions in countably many variables, and the Hopf subalgebra $\mathcal{Sym}$ of symmetric functions. They are graded connected, so by Theorem 3, $\mathcal{QSym}$ is a free module over $\mathcal{Sym}$. Garsia and Wallach prove this same fact for the algebras $\mathcal{QSym}_n$ and $\mathcal{Sym}_n$ of (quasi) symmetric functions in $n$ variables [4]. These are not Hopf algebras when $n$ is finite, so Theorem 3 does not yield the result of Garsia and Wallach. The papers [4] and [8] provide information on the space $Q_n$ entering in the decomposition $\mathcal{QSym}_n \cong \mathcal{Sym}_n \otimes Q_n$.

## 2 Lagrange's theorem for Hopf monoids in species

We first review the notion of Hopf monoid in the category of species, following [2], and then prove Lagrange's theorem in this setting. We restrict attention to the case of connected Hopf monoids.

### 2.1 Hopf monoids in species

The notion of species was introduced by Joyal [5]. It formalizes the notion of combinatorial structure and provides a framework for studying the generating functions which enumerate these structures. The book [3] by Bergeron, Labelle and Leroux expounds the theory of (set) species.

Joyal's work indicates that species may also be regarded as algebraic objects; this is the point of view adopted in [2] and in this work. To this end, it is convenient to work with vector species.

A (vector) species is a functor $\mathbf{q}$ from finite sets and bijections to vector spaces and linear maps. Specifically, it is a family of vector spaces $\mathbf{q}[I]$, one for each finite set $I$, together with linear maps $\mathbf{q}[\sigma] : \mathbf{q}[I] \to \mathbf{q}[J]$, one for each bijection $\sigma : I \to J$, satisfying

$$\mathbf{q}[\mathrm{id}_I] = \mathrm{id}_{\mathbf{q}[I]} \quad \text{and} \quad \mathbf{q}[\sigma \circ \tau] = \mathbf{q}[\sigma] \circ \mathbf{q}[\tau]$$
whenever $\sigma$ and $\tau$ are composable bijections. A species $\mathbf{q}$ is *finite dimensional* if each vector space $\mathbf{q}[I]$ is finite dimensional. In this paper, all species are finite dimensional. A morphism of species is a natural transformation of functors. Let $\mathfrak{Sp}$ denote the category of (finite dimensional) species.

We give two elementary examples that will be useful later.

**Example 6** Let $\mathbf{E}$ be the exponential species, defined by $\mathbf{E}[I] = \mathbb{k}\{*_I\}$ for all $I$. The symbol $*_I$ denotes an element canonically associated to the set $I$ (for definiteness, we may take $*_I = I$). Thus, $\mathbf{E}[I]$ is a one dimensional space with a distinguished basis element. A richer example is provided by the species $\mathbf{L}$ of linear orders, defined by $\mathbf{L}[I] = \mathbb{k}\{\text{linear orders on } I\}$ for all $I$ (a space of dimension $n!$ when $|I| = n$).

We use $\cdot$ to denote the *Cauchy product* of two species. Specifically,

$$ (\mathbf{p} \cdot \mathbf{q})[I] := \bigoplus_{S \sqcup T = I} \mathbf{p}[S] \otimes \mathbf{q}[T] \quad \text{for all finite sets } I. $$

The notation $S \sqcup T = I$ indicates that $S \cup T = I$ and $S \cap T = \emptyset$. The sum runs over all such *ordered decompositions* of $I$, or equivalently over all subsets $S$ of $I$: there is one term for $S \sqcup T$ and another for $T \sqcup S$. The Cauchy product turns $\mathfrak{Sp}$ into a symmetric monoidal category. The braiding simply switches the tensor factors. The unit object is the species **1** defined by

$$ \mathbf{1}[I] := \begin{cases} \mathbb{k} & \text{if } I \text{ is empty,} \\ 0 & \text{otherwise.} \end{cases} $$

A *monoid* in the category $(\mathfrak{Sp}, \cdot)$ is a species $\mathbf{m}$ together with a morphism of species $\mu: \mathbf{m} \cdot \mathbf{m} \to \mathbf{m}$, i.e., a family of maps

$$ \mu_{S,T}: \mathbf{m}[S] \otimes \mathbf{m}[T] \to \mathbf{m}[I], $$

one for each ordered decomposition $I = S \sqcup T$, satisfying appropriate associativity and unital conditions, and naturality with respect to bijections. Briefly, to each $\mathbf{m}$-structure on $S$ and $\mathbf{m}$-structure on $T$, there is assigned an $\mathbf{m}$-structure on $S \sqcup T$. The analogous object in the category $\mathfrak{gVec}$ of graded vector spaces is a graded algebra.

The species $\mathbf{E}$ has a monoid structure defined by sending the basis element $*_S \otimes*_T$ to the basis element $*_I$. For $\mathbf{L}$, a monoid structure is provided by concatenation of linear orders: $\mu_{S,T}(\ell_1 \otimes \ell_2) = (\ell_1, \ell_2)$.

A *comonoid* in the category $(\mathfrak{Sp}, \cdot)$ is a species $\mathbf{c}$ together with a morphism of species $\Delta: \mathbf{c} \to \mathbf{c} \cdot \mathbf{c}$, i.e., a family of maps

$$ \Delta_{S,T}: \mathbf{c}[I] \to \mathbf{c}[S] \otimes \mathbf{c}[T], $$

one for each ordered decomposition $I = S \sqcup T$, which are natural, coassociative and counital.

For $\mathbf{E}$, a comonoid structure is defined by sending the basis vector $*_I$ to the basis vector $*_S \otimes*_T$. For $\mathbf{L}$, a comonoid structure is provided by restricting a total order $\ell$ on $I$: $\Delta_{S,T}(\ell) = \ell|_S \otimes \ell|_T$.

We assume that our species $\mathbf{q}$ are *connected*, i.e., $\mathbf{q}[\emptyset] = \mathbb{k}$. In this case, the (co)unital conditions for a (co)monoid force the maps $\mu_{S,T}$ and $\Delta_{S,T}$ to be the canonical identifications if either $S$ or $T$ is empty.

A *Hopf monoid* in the category $(\mathfrak{Sp}, \cdot)$ is a monoid and comonoid whose two structures are compatible in an appropriate sense, and which carries an antipode. In this paper we only consider connected Hopf monoids. For such Hopf monoids, the existence of the antipode is guaranteed. The species $\mathbf{E}$ and $\mathbf{L}$, with the structures outlined above, are two important examples of (connected) Hopf monoids.

For further details on Hopf monoids in species, see Chapter 8 of [2]. The theory of Hopf monoids in species is developed in Part II of this reference; several examples are discussed in Chapters 12 and 13.
## 2.2 Lagrange's theorem for connected Hopf monoids

Given a connected Hopf monoid $k$ in species, we let $k_+$ denote the species defined by

$$k_+[I] = \begin{cases} k[I] & \text{if } I \neq \emptyset, \\ 0 & \text{if } I = \emptyset. \end{cases}$$

If $k$ is a submonoid of a monoid $h$, then $k_+h$ denotes the right ideal of $h$ generated by $k_+$. In other words,

$$(k_+h)[I] = \sum_{\substack{S \sqcup T = I \\ S \neq \emptyset}} \mu_{S,T}(k[S] \otimes h[T]).$$

**Theorem 7** Let $h$ be a connected Hopf monoid in the category of species. If $k$ is a Hopf submonoid of $h$, then $h$ is a free left $k$-module. Moreover,

$$h \cong k \cdot (h/k_+h)$$

as left $k$-modules (and as species).

The proof is given after a series of preparatory results. Our argument parallels Radford's proof of Theorem 2 [16, Section 4]. The main ingredient is a result of Larson and Sweedler [7] known as the fundamental theorem of Hopf modules [11, Thm. 1.9.4]. It states that if $(M, \rho)$ is a left Hopf module over $K$, then $M$ is free as a left $K$-module and in fact is isomorphic to the Hopf module $K \otimes Q$, where $Q$ is the space of coinvariants for the coaction $\rho$. Takeuchi extends this result to the context of Hopf monoids in a braided monoidal category with equalizers [19, Thm. 3.4]; a similar result (in a more restrictive setting) is given by Lyubashenko [9, Thm. 1.1]. As a special case of Takeuchi's result, we have the following.

**Proposition 8** Let $m$ be a left Hopf module over a connected Hopf monoid $k$ in species. There is an isomorphism $m \cong k \cdot q$ of left Hopf modules, where

$$q[I] := \{m \in m[I] \mid \rho_{S,T}(m) = 0 \text{ for } S \sqcup T = I, T \neq I\}.$$

In particular, $m$ is free as a left $k$-module.

Here $\rho : m \to k \cdot m$ denotes the comodule structure, which consists of maps

$$\rho_{S,T} : m[I] \to k[S] \otimes m[T],$$

one for each ordered decomposition $I = S \sqcup T$.

Given a comonoid $h$ and two subspecies $u, v \subseteq h$, their wedge is defined by

$$u \wedge v := \Delta^{-1}(u \cdot h + h \cdot v).$$

The remaining ingredients needed for the proof are supplied by the following lemmas.

**Lemma 9** Let $h$ be a comonoid in species. If $u$ and $v$ are subcomonoids of $h$, then: (i) $u \wedge v$ is a subcomonoid of $h$ and $u + v \subseteq u \wedge v$; (ii) $u \wedge v = \Delta^{-1}(u \cdot (u \wedge v) + (u \wedge v) \cdot v)$.
**Proof:** (i) Proofs of analogous statements for coalgebras, given in [1, Section 3.3], extend to this setting.

(ii) From the definition, $\Delta^{-1}(\mathbf{u} \cdot (\mathbf{u} \wedge \mathbf{v}) + (\mathbf{u} \wedge \mathbf{v}) \cdot \mathbf{v}) \subseteq \mathbf{u} \wedge \mathbf{v}$. Now, since $\mathbf{u} \wedge \mathbf{v}$ is a subcomonoid,

$$ \Delta(\mathbf{u} \wedge \mathbf{v}) \subseteq ((\mathbf{u} \wedge \mathbf{v}) \cdot (\mathbf{u} \wedge \mathbf{v})) \cap (\mathbf{u} \cdot \mathbf{h} + \mathbf{h} \cdot \mathbf{v}) = \mathbf{u} \cdot (\mathbf{u} \wedge \mathbf{v}) + (\mathbf{u} \wedge \mathbf{v}) \cdot \mathbf{v}, $$

since $\mathbf{u}, \mathbf{v} \subseteq \mathbf{u} \wedge \mathbf{v}$. This proves the converse inclusion. $\square$

**Lemma 10** Let $\mathbf{h}$ be a Hopf monoid in species and $\mathbf{k}$ a submonoid. Let $\mathbf{u}, \mathbf{v} \subseteq \mathbf{h}$ be subspecies which are left $\mathbf{k}$-submodules of $\mathbf{h}$. Then $\mathbf{u} \wedge \mathbf{v}$ is a left $\mathbf{k}$-submodule of $\mathbf{h}$.

**Proof:** Since $\mathbf{h}$ is a Hopf monoid, the coproduct $\Delta : \mathbf{h} \to \mathbf{h} \cdot \mathbf{h}$ is a morphism of left $\mathbf{h}$-modules, where $\mathbf{h}$ acts on $\mathbf{h} \cdot \mathbf{h}$ via $\Delta$. Hence it is also a morphism of left $\mathbf{k}$-modules. By hypothesis, $\mathbf{u} \cdot \mathbf{h} + \mathbf{h} \cdot \mathbf{v}$ is a left $\mathbf{k}$-submodule of $\mathbf{h} \cdot \mathbf{h}$. Hence, $\mathbf{u} \wedge \mathbf{v} = \Delta^{-1}(\mathbf{u} \cdot \mathbf{h} + \mathbf{h} \cdot \mathbf{v})$ is a left $\mathbf{k}$-submodule of $\mathbf{h}$. $\square$

**Lemma 11** Let $\mathbf{h}$ be a Hopf monoid in species and $\mathbf{k}$ a Hopf submonoid. Let $\mathbf{c}$ be a subcomonoid of $\mathbf{h}$ and a left $\mathbf{k}$-submodule of $\mathbf{h}$. Then $(\mathbf{k} \wedge \mathbf{c})/\mathbf{c}$ is a left $\mathbf{k}$-Hopf module. $\square$

We are nearly ready for the proof of the main result. First, recall the *coradical filtration* of a connected comonoid in species [2, §8.10]. Given a connected comonoid $\mathbf{c}$, define subspecies $\mathbf{c}_{(n)}$ by

$$ \mathbf{c}_{(0)} = \mathbf{1} \quad \text{and} \quad \mathbf{c}_{(n)} = \mathbf{c}_{(0)} \wedge \mathbf{c}_{(n-1)} \quad \text{for all } n \ge 1. $$

We then have

$$ \mathbf{c}_{(0)} \subseteq \mathbf{c}_{(1)} \subseteq \dots \subseteq \mathbf{c}_{(n)} \subseteq \dots \mathbf{c} \quad \text{and} \quad \mathbf{c} = \bigcup_{n \ge 0} \mathbf{c}_{(n)}. $$

**Proof of Theorem 7:** We show that there is a species $\mathbf{q}$ such that $\mathbf{h} \cong \mathbf{k} \cdot \mathbf{q}$ as left $\mathbf{k}$-modules. As in the proof of Theorem 3, one then argues that $\mathbf{q} \cong \mathbf{h}/\mathbf{k}_{+}\mathbf{h}$.

Define a sequence $\mathbf{k}^{(n)}$ of subspecies of $\mathbf{h}$ by

$$ \mathbf{k}^{(0)} = \mathbf{k} \quad \text{and} \quad \mathbf{k}^{(n)} = \mathbf{k} \wedge \mathbf{k}^{(n-1)} \quad \text{for all } n \ge 1. $$

Each $\mathbf{k}^{(n)}$ is a subcomonoid and a left $\mathbf{k}$-submodule of $\mathbf{h}$. This follows from Lemmas 9 and 10, by induction on $n$. Then, by Lemma 11, for all $n \ge 1$ the quotient species $\mathbf{k}^{(n)}/\mathbf{k}^{(n-1)}$ is a left Hopf $\mathbf{k}$-module. Therefore, by Proposition 8, each $\mathbf{k}^{(n)}/\mathbf{k}^{(n-1)}$ is a free left $\mathbf{k}$-module.

We claim that there exists a sequence of species $\mathbf{q}_n$ ($n \ge 0$) such that

$$ \mathbf{k}^{(n)} \cong \mathbf{k} \cdot \mathbf{q}_n $$

as left $\mathbf{k}$-modules (so that each $\mathbf{k}^{(n)}$ is a free left $\mathbf{k}$-module). Moreover, the $\mathbf{q}_n$ can be chosen so that

$$ \mathbf{q}_0 \subseteq \mathbf{q}_1 \subseteq \dots \subseteq \mathbf{q}_n \subseteq \dots $$

and the above isomorphisms are compatible with the inclusions $\mathbf{q}_{n-1} \subseteq \mathbf{q}_n$ and $\mathbf{k}^{(n-1)} \subseteq \mathbf{k}^{(n)}$. This may be proven by induction on $n$.

Finally, since $\mathbf{h}$ is connected, $\mathbf{h}_{(0)} = \mathbf{1} \subseteq \mathbf{k} = \mathbf{k}^{(0)}$, and by induction, $\mathbf{h}_{(n)} \subseteq \mathbf{k}^{(n)}$ for all $n \ge 0$. Hence,

$$ \mathbf{h} = \bigcup_{n \ge 0} \mathbf{h}_{(n)} = \bigcup_{n \ge 0} \mathbf{k}^{(n)} \cong \bigcup_{n \ge 0} \mathbf{k} \cdot \mathbf{q}_n \cong \mathbf{k} \cdot \mathbf{q} \quad \text{where} \quad \mathbf{q} = \bigcup_{n \ge 0} \mathbf{q}_n. $$

Thus, $\mathbf{h}$ is free as a left $\mathbf{k}$-module. $\square$
# 3 Applications and examples

## 3.1 A test for Hopf submonoids

Two important power series associated to a (finite dimensional) species $\mathbf{q}$ are its exponential generating series $\mathcal{E}_{\mathbf{q}}(x)$ and type generating series $\mathcal{T}_{\mathbf{q}}(x)$. They are given by

$$ \mathcal{E}_{\mathbf{q}}(x) = \sum_{n \ge 0} \dim \mathbf{q}[n] \frac{x^n}{n!} \quad \text{and} \quad \mathcal{T}_{\mathbf{q}}(x) = \sum_{n \ge 0} \dim \mathbf{q}[n]_{S_n} x^n, $$

where

$$ \mathbf{q}[n]_{S_n} = \mathbf{q}[n]/\mathbb{k}\{v - \sigma v \mid v \in \mathbf{q}[n], \sigma \in S_n\}. $$

Both are specializations of the cycle index series $\mathcal{Z}_{\mathbf{q}}(x_1, x_2, \dots)$; see [3, §1.2] for definitions. Specifically,

$$ \mathcal{E}_{\mathbf{q}}(x) = \mathcal{Z}_{\mathbf{q}}(x, 0, \dots) \quad \text{and} \quad \mathcal{T}_{\mathbf{q}}(x) = \mathcal{Z}_{\mathbf{q}}(x, x^2, \dots). $$

The cycle index series is multiplicative under Cauchy product: if $\mathbf{h} = \mathbf{k} \cdot \mathbf{q}$, then $\mathcal{Z}_{\mathbf{h}}(x_1, x_2, \dots) = \mathcal{Z}_{\mathbf{k}}(x_1, x_2, \dots) \mathcal{Z}_{\mathbf{q}}(x_1, x_2, \dots)$; see [3, §1.3]. Thus, the same is true for $\mathcal{E}_{\mathbf{q}}(x)$ and $\mathcal{T}_{\mathbf{q}}(x)$.

Let $\mathbb{Q}_{\ge 0}$ denote the nonnegative rational numbers. A consequence of Theorem 7 is the following.

**Corollary 12** Let $\mathbf{h}$ and $\mathbf{k}$ be connected Hopf monoids in species. If $\mathbf{k}$ is either a Hopf submonoid or a quotient Hopf monoid of $\mathbf{h}$, then the quotient $\mathcal{Z}_{\mathbf{h}}(x_1, x_2, \dots)/\mathcal{Z}_{\mathbf{k}}(x_1, x_2, \dots)$ of cycle index series is nonnegative, i.e., belongs to $\mathbb{Q}_{\ge 0}$ $[x_1, x_2, \dots]$. Likewise for the quotients $\mathcal{E}_{\mathbf{h}}(x)/\mathcal{E}_{\mathbf{k}}(x)$ and $\mathcal{T}_{\mathbf{h}}(x)/\mathcal{T}_{\mathbf{k}}(x)$.

Given a connected Hopf monoid $\mathbf{h}$ in species, we may use Corollary 12 to determine if a given species $\mathbf{k}$ may be a Hopf submonoid (or a quotient Hopf monoid).

**Example 13** A partition of a set $I$ is an unordered collection of disjoint nonempty subsets of $I$ whose union is $I$. The notation $ab c$ is shorthand for the partition $\{\{a, b\}, \{c\}\}$ of $\{a, b, c\}$.

Let $\Pi$ be the species of set partitions, i.e., $\Pi[I]$ is the vector space with basis the set of all partitions of $I$. Let $\Pi'$ denote the subspecies linearly spanned by set partitions with distinct block sizes. For example,

$$ \Pi[\{a, b, c\}] = \mathbb{k}\{abc, a\,bc, ab\,c, a\,bc, a\,b\,c\} \quad \text{and} \quad \Pi'[\{a, b, c\}] = \mathbb{k}\{abc, a\,bc, ab\,c, a\,bc\}. $$

The sequences $(\dim \Pi[n])_{n \ge 0}$ and $(\dim \Pi'[n])_{n \ge 0}$ appear in [17] as A000110 and A007837, respectively. We have

$$ \mathcal{E}_{\Pi}(x) = \exp(\exp(x) - 1) = 1 + x + x^2 + \frac{5}{6}x^3 + \frac{5}{8}x^4 + \dots $$

and

$$ \mathcal{E}_{\Pi'}(x) = \prod_{n \ge 1} \left(1 + \frac{x^n}{n!}\right) = 1 + x + \frac{1}{2}x^2 + \frac{2}{3}x^3 + \frac{5}{24}x^4 + \dots $$

If a Hopf monoid structure on $\Pi$ existed for which $\Pi'$ were a Hopf submonoid, then the quotient of their exponential generating series would be nonnegative, by Corollary 12. However, we have

$$ \mathcal{E}_{\Pi}(x)/\mathcal{E}_{\Pi'}(x) = 1 + \frac{1}{2}x^2 - \frac{1}{3}x^3 + \frac{1}{2}x^4 - \frac{11}{30}x^5 + \dots, $$
so no such structure exists. In [2, §12.6], a Hopf monoid structure on $\Pi$ is defined. By the above, there is no way to embed $\Pi'$ as a Hopf submonoid.

We remark that the type generating series quotient for the pair of species in Example 13 is positive:

$$ \mathcal{T}_{\Pi}(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + 11x^6 + 15x^7 + \dots, $$

$$ \mathcal{T}_{\Pi'}(x) = 1 + x + x^2 + 2x^3 + 2x^4 + 3x^5 + 4x^6 + 5x^7 + \dots, $$

$$ \mathcal{T}_{\Pi}(x)/\mathcal{T}_{\Pi'}(x) = 1 + x^2 + 2x^4 + 3x^6 + 5x^8 + 7x^{10} + \dots. $$

This can be understood by appealing to the Hopf algebra Sym. A basis for its nth graded piece is indexed by integer partitions, so $\mathcal{P}_{\text{Sym}}(x) = \mathcal{T}_{\Pi}(x)$. Moreover, $\mathcal{T}_{\Pi'}(x)$ enumerates the integer partitions with odd part sizes and Sym does indeed contain a Hopf subalgebra with this Poincaré series. It is the algebra of Schur-Q functions. See [10, III.8]. Thus $\mathcal{T}_{\Pi}(x)/\mathcal{T}_{\Pi'}(x)$ is nonnegative by Corollary 4.

## 3.2 A test for Hopf monoids

Let $(a_n)_{n \ge 0}$ be a sequence of nonnegative integers with $a_0 = 1$. Does there exist a connected Hopf monoid $h$ with $\dim h[n] = a_n$ for all $n$? The next result provides conditions that the sequence $(a_n)_{n \ge 0}$ must satisfy for this to be the case.

**Corollary 14 (The (ord/exp)-test)** For any connected Hopf monoid in species $h$,

$$ \left( \sum_{n \ge 0} \dim h[n] x^n \right) / \left( \sum_{n \ge 0} \frac{\dim h[n]}{n!} x^n \right) \in \mathbb{N}[x]. $$

**Proof:** We make use of the *Hadamard product* of Hopf monoids [2, Corollary 8.59]. The exponential species $E$ is the unit for this operation.

Consider the canonical morphism of Hopf monoids $L \to E$; it maps any linear order $\ell \in L[I]$ to the basis element $*_I \in E[I]$ [2, Section 8.5]. The Hadamard product then yields a morphism of Hopf monoids

$$ L \times h \to E \times h \cong h. $$

By Corollary 12, $\mathcal{E}_{L \times h}(x)/\mathcal{E}_h(x) \in \mathbb{N}[x]$. Since $\mathcal{E}_{L \times h}(x) = \sum_{n \ge 0} \dim h[n] x^n$, the result follows. $\square$

Let $a_n = \dim h[n]$. Corollary 14 states that the ratio of the ordinary to the exponential generating function of the sequence $(a_n)_{n \ge 0}$ must be nonnegative. This translates into a sequence of polynomial inequalities, the first of which are as follows:

$$ 5a_3 \ge 3a_2a_1, \quad 23a_4 + 12a_2a_1^2 \ge 20a_3a_1 + 6a_2^2. $$

In particular, not every nonnegative sequence arises as the sequence of dimensions of a Hopf monoid.

## 3.3 A test for Hopf monoids over $E$

Our next result is a necessary condition for a Hopf monoid in species to contain or surject onto the exponential species $E$.

Given a sequence $(a_n)_{n \ge 0}$, its *binomial transform* $(b_n)_{n \ge 0}$ is defined by

$$ b_n := \sum_{i=0}^{n} \binom{n}{i} (-1)^i a_{n-i}. $$
**Corollary 15 (The E-test)** Suppose $\mathbf{h}$ is a connected Hopf monoid that either contains the species $\mathbf{E}$ or surjects onto $\mathbf{E}$ (in both cases as a Hopf monoid). Let $a_n = \dim \mathbf{h}[n]$ and $\bar{a}_n = \dim \mathbf{h}[n]_{S_n}$. Then the binomial transform of $(a_n)_{n \ge 0}$ must be nonnegative and $(\bar{a}_n)_{n \ge 0}$ must be nondecreasing.

More plainly, in this setting, we must have the following inequalities:

$$a_1 \ge a_0, \quad a_2 \ge 2a_1 - a_0, \quad a_3 \ge 3a_2 - 3a_1 + a_0, \dots$$

and $\bar{a}_n \ge \bar{a}_{n-1}$ for all $n \ge 1$.

**Proof:** Since $\mathcal{E}_{\mathbf{h}}(x) = \exp(x)$, the quotient $\mathcal{E}_{\mathbf{h}}(x)/\mathcal{E}_{\mathbf{E}}(x)$ is given by

$$b_0 + b_1 x + b_2 \frac{x^2}{2} + b_3 \frac{x^3}{3!} + \dots,$$

where $(b_n)_{n \ge 0}$ is the binomial transform of $(a_n)_{n \ge 0}$. It is nonnegative by Corollary 12. Replacing exponential for type generating functions yields the result for $(\bar{a}_n)_{n \ge 0}$, since $\mathcal{T}_{\mathbf{E}}(x) = \frac{1}{1-x}$. $\square$

We make a further remark regarding connected *linearized* Hopf monoids. These are Hopf monoids of a set theoretic nature. See [2, §8.7] for details. Briefly, there are set maps $\mu_{A,B}(x, y)$ and $\Delta_{A,B}(z)$ that produce single structures (written $(x, y) \mapsto x \cdot y$ and $z \mapsto (z|_A, z|_A)$, respectively), which are compatible at the level of set maps and which produce a Hopf monoid in species when linearized. It follows that if $\mathbf{h}$ is a linearized Hopf monoid, then there is a unique morphism of Hopf monoids from $\mathbf{h}$ onto $\mathbf{E}$. Thus, Corollary 15 provides a test for existence of a linearized Hopf monoid structure on $\mathbf{h}$.

**Example 16** We return to the species $\Pi'$ of set partitions into distinct block sizes. We might ask if this can be made into a linearized Hopf monoid in some way (after Example 13, this would not be as a Hopf submonoid of $\Pi'$). With $a_n$ and $b_n$ as above, we have:

$$(a_n)_{n \ge 0} = 1, 1, 1, 4, 5, 16, 82, 169, 541, \dots,$$

$$(b_n)_{n \ge 0} = 1, 0, 0, 3, -8, 25, -9, -119, 736, \dots.$$

Thus $\Pi'$ fails the E-test and the answer to the above question is negative.

## 3.4 A test for Hopf monoids over L

Let $\mathbf{h}$ be a connected Hopf monoid in species. Let $a_n = \dim \mathbf{h}[n]$ and $\bar{a}_n = \dim \mathbf{h}[n]_{S_n}$. Note that the analogous integers for the species $\mathbf{L}$ of linear orders are $b_n = n!$ and $\bar{b}_n = 1$. Now suppose that $\mathbf{h}$ contains $\mathbf{L}$ or surjects onto $\mathbf{L}$ as a Hopf monoid. An obvious necessary condition for this situation is that $a_n \ge n!$ and $\bar{a}_n \ge 1$. Our next result provides stronger conditions.

**Corollary 17 (The L-test)** Suppose $\mathbf{h}$ is a connected Hopf monoid that either contains the species $\mathbf{L}$ or surjects onto $\mathbf{L}$ (in both cases as a Hopf monoid). If $a_n = \dim \mathbf{h}[n]$ and $\bar{a}_n = \dim \mathbf{h}[n]_{S_n}$, then

$$a_n \ge n a_{n-1} \quad \text{and} \quad \bar{a}_n \ge \bar{a}_{n-1} \quad (\forall n \ge 1).$$

**Proof:** It follows from Corollary 12 that both $\mathcal{E}_{\mathbf{h}}(x)/\mathcal{E}_{\mathbf{L}}(x)$ and $\mathcal{T}_{\mathbf{h}}(x)/\mathcal{T}_{\mathbf{L}}(x)$ are nonnegative. These yield the first and second set of inequalities, respectively. $\square$
Before giving an application of the corollary, we introduce a new Hopf monoid in species. A composition of a set $I$ is an ordered collection of disjoint nonempty subsets of $I$ whose union is $I$. The notation $abc$ is shorthand for the composition $(\{a, b\}, \{c\})$ of $\{a, b, c\}$.

Let $\mathbf{Pal}$ denote the species of set compositions whose sequence of block sizes is palindromic. So, for instance,

$$ \mathbf{Pal}[\{a, b\}] = \mathbb{k}\{ab, a|b, b|a\} $$

and

$$ \mathbf{Pal}[\{a, b, c, d, e\}] = \mathbb{k}\{abcde, a|bcd|e, ab|c|de, a|b|c|d|e, \dots \}. $$

The latter space has dimension $171 = 1 + 5(\binom{4}{3}) + (\binom{5}{2})3 + 5!$ and $\dim \mathbf{Pal}[5]_{S_5} = 4$ for the four types of palindromic set compositions shown above.

Given a palindromic set composition $\pi = \pi_1 | \cdots | \pi_r$, we view it as a triple $\pi = (\pi^-, \pi^0, \pi^+)$, where $\pi^-$ is the initial sequence of blocks, $\pi^0$ is the central block if this exists (if the number of blocks is odd) and otherwise it is the empty set, and $\pi^+$ is the final sequence of blocks. That is,

$$ \pi^{-} = \pi_{1} | \cdots | \pi_{\lfloor r/2 \rfloor}, \qquad \pi^{0} = \begin{cases} \pi_{\lfloor r/2 \rfloor+1} & \text{if } r \text{ is odd,} \\ \emptyset & \text{if } r \text{ is even,} \end{cases} \qquad \pi^{+} = \pi_{\lceil r/2+1 \rceil} | \cdots | \pi_{r}. $$

Given $S \subseteq I$, let

$$ \pi|_S := \pi_1 \cap S | \pi_2 \cap S | \cdots | \pi_r \cap S, $$

where empty intersections are deleted. Then $\pi|_S$ is a composition of $S$. It is not always the case that $\pi|_S$ is palindromic. Let us say that $S$ is *admissible* for $\pi$ when it is, i.e.,

$$ \#(\pi_i \cap S) = \#(\pi_{r+1-i} \cap S) \quad \text{for all } i = 1, \dots, r. $$

In this case, both $\pi|_S$ and $\pi|_{I \setminus S}$ are palindromic.

We now define product and coproduct operations on $\mathbf{Pal}$. Fix a decomposition $I = S \sqcup T$. Product. Given palindromic set compositions $\pi \in \mathbf{Pal}[S]$ and $\sigma \in \mathbf{Pal}[T]$, we put

$$ \mu_{S,T}(\pi \otimes \sigma) := (\pi^{-} | \sigma^{-}, \pi^{0} \cup \sigma^{0}, \sigma^{+} | \pi^{+}). $$

In other words, we concatenate the initial sequences of blocks of $\pi$ and $\sigma$ in that order, merge their central blocks, and concatenate their final sequences in the opposite order. The result is a palindromic composition of $I$. For example, with $S = \{a, b\}$ and $T = \{c, d, e, f\}$,

$$ (a|b) \otimes (c|de|f) \mapsto a|c|de|f|b. $$

Coproduct. Given a palindromic set composition $\tau \in \mathbf{Pal}[I]$, we put

$$ \Delta_{S,T}(\tau) := \begin{cases} \tau|_S \otimes \tau|_T & \text{if } S \text{ is admissible for } \pi, \\ 0 & \text{otherwise.} \end{cases} $$

For example, with $S$ and $T$ as above,

$$ ad|b|e|cf \mapsto 0 \quad \text{and} \quad e|abcd|f \mapsto (ab) \otimes (e|cd|f). $$

These operations endow $\mathbf{Pal}$ with the structure of Hopf monoid, as may be easily checked.
**Example 18** We ask if **Pal** contains (or surjects onto) the Hopf monoid **L**. Both Hopf monoids are cocommutative and not commutative. Writing $a_n = \dim \mathbf{Pal}[n]$, we have:

$$ (a_n)_{n \ge 0} = 1, 1, 3, 7, 43, 171, 1581, 8793, 108347, \dots $$

Every linear order is a palindromic set composition with singleton blocks. Thus $a_n \ge n!$ for all $n$ and the question has some hope for an affirmative answer. However,

$$ (a_n - na_{n-1})_{n \ge 1} = 0, 1, -2, 15, -44, 555, -2274, 38003, \dots, $$

so **Pal** fails the **L**-test and the answer to the above question is negative.

## 3.5 Examples of nonnegative quotients

We comment on a few examples where the quotient power series $\mathcal{E}_h(x)/\mathcal{E}_k(x)$ is not only nonnegative but is known to have a combinatorial interpretation as a generating function.

**Example 19** Consider the Hopf monoid $\Pi$ of set partitions. It contains $\mathbb{E}$ as a Hopf submonoid via the map that sends $*_{I}$ to the partition of $I$ into singletons. We have

$$ \mathcal{E}_{\Pi}(x)/\mathcal{E}_{\mathbb{E}}(x) = \exp(\exp(x) - x - 1), $$

which is the exponential generating function for the number of set partitions into blocks of size strictly bigger than 1. This fact may also be understood with the aid of Theorem 7, as follows. The $I$-component of the right ideal $\mathbb{E}_+\Pi$ is linearly spanned by elements of the form $*_{S} \cdot \pi$ where $I = S \sqcup T$ and $\pi$ is a partition of $T$. Now, since $*_{S} = *_{\{i\}} \cdot *_{S \setminus \{i\}}$ (for any $i \in S$), we have that $\mathbb{E}_+\Pi[I]$ is linearly spanned by elements of the form $*_{\{i\}} \cdot \pi$ where $i \in I$ and $\pi$ is a partition of $I \setminus \{i\}$. But these are precisely the partitions with at least one singleton block.

**Example 20** Let $\Sigma$ be the Hopf monoid of set compositions defined in [2, Section 12.4]. It contains **L** as a Hopf submonoid via the map that views a linear order as a composition into singletons. This and other morphisms relating $\mathbb{E}$, $\mathbb{L}$, $\Pi$ and $\Sigma$, as well as other Hopf monoids, are discussed in [2, Section 12.8].

The sequence $(\dim \Sigma[n])_{n \ge 0}$ is A000670 in [17]. We have

$$ \mathcal{E}_{\Sigma}(x) = \frac{1}{2 - \exp(x)}. $$

Moreover, it is known from [18, Exercise 5.4.(a)] that

$$ \frac{1-x}{2-\exp(x)} = \sum_{n \ge 0} \frac{s_n}{n!} x^n $$

where $s_n$ is the number of threshold graphs with vertex set $[n]$ and no isolated vertices. Together with Theorem 7, this suggests the existence of a basis for $\Sigma/\mathbb{L}_+\Sigma$ indexed by such graphs.
References

[1] Eiichi Abe, *Hopf algebras*, Cambridge Tracts in Mathematics, vol. 74, Cambridge University Press, Cambridge, 1980.

[2] Marcelo Aguiar and Swapneel Mahajan, *Monoidal functors, species and Hopf algebras*, CRM Monograph Series, vol. 29, American Mathematical Society, Providence, RI, 2010.

[3] François Bergeron, Gilbert Labelle, and Pierre Leroux, *Combinatorial species and tree-like structures*, Encyclopedia of Mathematics and its Applications, vol. 67, Cambridge University Press, Cambridge, 1998, Translated from the 1994 French original by Margaret Readdy, with a foreword by Gian-Carlo Rota.

[4] Adriano M. Garsia and Nolan Wallach, *Qsym over Sym is free*, J. Combin. Theory Ser. A **104** (2003), no. 2, 217–263.

[5] André Joyal, *Une théorie combinatoire des séries formelles*, Adv. in Math. **42** (1981), no. 1, 1–82.

[6] Irving Kaplansky, *Bialgebras*, Lecture Notes in Mathematics, Department of Mathematics, University of Chicago, Chicago, Ill., 1975.

[7] Moss E. Sweedler and Richard G. Larson, *An associative orthogonal bilinear form for Hopf algebras*, Amer. J. Math. **91** (1969), 75–94.

[8] Aaron Lauve and Sarah Mason, *QSym over Sym has a stable basis*, available at arXiv:1003.2124v1.

[9] Volodymyr Lyubashenko, *Modular transformations for tensor categories*, J. Pure Appl. Algebra **98** (1995), no. 3, 279–327.

[10] Ian G. Macdonald, *Symmetric functions and Hall polynomials*, second ed., Oxford Mathematical Monographs, Oxford University Press, New York, 1995, with contributions by A. Zelevinsky.

[11] Susan Montgomery, *Hopf algebras and their actions on rings*, CBMS Regional Conference Series in Mathematics, vol. 82, Published for the CBMS, Washington, DC, 1993.

[12] Warren D. Nichols and M. Bettina Zoeller, *A Hopf algebra freeness theorem*, Amer. J. Math. **111** (1989), no. 2, 381–385.

[13] Ulrich Oberst and Hans-Jürgen Schneider, *Untergruppen formeller Gruppen von endlichem Index*, J. Algebra **31** (1974), 10–44.

[14] Hans-Jürgen Schneider, *Principal homogeneous spaces for arbitrary Hopf algebras*, Isr. J. Math. **72** (1990), no. 1–2, 167–195.

[15] Yorck Sommerhäuser, *On Kaplansky's conjectures*, Interactions between ring theory and representations of algebras (Murcia), Lecture Notes in Pure and Appl. Math., vol. 210, Dekker, New York, 2000, pp. 393–412.

[16] David E. Radford, *Pointed Hopf algebras are free over Hopf subalgebras*, J. Algebra **45** (1977), no. 2, 266–273.

[17] Neil J. A. Sloane, *The on-line encyclopedia of integer sequences*, published electronically at www.research.att.com/~njas/sequences/, OEIS.

[18] Richard P. Stanley, *Enumerative combinatorics. Vol. 2.*, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999, with a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[19] Mitsuhiro Takeuchi, *Finite Hopf algebras in braided tensor categories*, J. Pure Appl. Algebra **138** (1999), no. 1, 59–82.