# Categorifying the free monoid and non-commutative generating functions

I am a complete novice in the art of categorification, so this may not be a great question.

Background.

• The groupoid $\mathbf {FSet}$ of finite sets and bijections categorifies the natural numbers and the functor category $\mathbf {FSet}^{\mathbf {FSet}}$ (called the category of combinatorial species) categorifies generating functions.
• If $X$ is a finite set, the slice category $\mathbf {FSet}/X$ of finite sets over $X$ (or $X$-indexed families of finite sets) categorifies the free commutative monoid on $X$, the forgetful functor $\mathbf {FSet}/X\longrightarrow \mathbf {FSet}$ categorifies word length (or degree of a monomial) and I believe the functor category $(\mathbf {FSet}/X)^{\mathbf {FSet}/X}$ categorifies generating functions in commuting variables $X$.
• Question. Is there a categorification $\mathbf C$ of the free monoid on a finite set $X$ together with a ''forgetful" functor $\mathbf C\longrightarrow \mathbf {FSet}/X$ categorifying the abelianization map such that $\mathbf C^{\mathbf C}$ categorifies generating functions in non-commuting variables $X$.

I assume the answer will be some sort of "free" monoidal category. Please take into account that I am a category-friendly mathematician, but not a category theorist, when formulating your answer.

Vague motivation. Is there a categorification of the Chomsky-Schützenberger theorem on context-free grammars and algebraic power series?

I realize that species categorify exponential generating fuctions and Chomsky-Schützenberger is about ordinary generating functions, but this shouldn't matter.

Update.. The free monoidal category is no good because it only has identity morphisms. It doesn't even work to recover the 1-generated case.

• Can anybody figure out why my link to the Chomsky-Schützenberger theorem is not showing? Thanks! Dec 7, 2011 at 13:43
• The answer is literally the free monoidal category on $X$. Its objects are words on the elements of $X$ and its morphisms are freely generated by the identity morphisms under tensor product (so there are not very many of them unless you give $X$ itself additional structure). You aren't using the right definition of combinatorial species: the domain category is the category of finite sets and bijections, not the ordinary category of finite sets. Dec 7, 2011 at 15:16
• Sorry Quaochu, I forgot to say that but meant it. Does the free monoidal category work for generating functions? What is the forgetful functor to FSet/X. Dec 7, 2011 at 15:41
• @Benjamin: the forgetful functor to $\text{FSet}/X$ sends a word to the set of its letter positions together with their names (the function to $X$). I think the only morphisms in the free monoidal category on a set are identity morphisms, though, so this isn't a particularly interesting observation. Dec 7, 2011 at 16:07
• Yes, the free monoidal category on a set $X$ is equivalent to the discrete category given by the free monoid on $X$, as Qiaochu says, so nothing too exciting here, unfortunately. Dec 7, 2011 at 16:26

I think you've been misled by the standard description of combinatorial species. It's cleaner to think of (exponential) generating functions in one variable as being categorified by analytic functors, namely endofunctors of the form

$$X \mapsto \bigsqcup_{n \ge 0} F_n \otimes_{S_n} X^{\otimes n}$$

where $X$ is an object in a symmetric monoidal category $M$ with infinite coproducts and finite colimits, although these endofunctors won't behave as expected unless the monoidal product distributes over colimits. For example, pointwise coproduct corresponds to adding generating functions, pointwise tensor product corresponds to multiplying generating functions, and composition corresponds to composition.

A straightforward categorification of (again, exponential) generating functions in more than one variable is then analytic functors of more than one variable, e.g. in two variables these take the form

$$X, Y \mapsto \bigsqcup_{n, m \ge 0} F_{n, m} \otimes_{S_n \times S_m} X^{\otimes n} \otimes Y^{\otimes m}.$$

The relationship to species comes from describing convenient choices of "coefficients" $F_n, F_{n, m}$, which I didn't specify above. A common situation is that the coefficients live in a symmetric monoidal category $V$ such that $M$ is both enriched and tensored over $V$. Then $M$ naturally acquires an action by analytic functors with coefficients given by $V$-valued species, or equivalently presheaves $S^{op} \to V$, where $S$ denotes the groupoid of finite sets and bijections. For analytic functors in two commuting variables the coefficients come from presheaves $S^{op} \times S^{op} \to V$, etc. Here you should think of $S$ as the free symmetric monoidal category on an object, $S \times S$ as the free symmetric monoidal category on two objects, etc.

For noncommuting variables and ordinary generating functions, replace "symmetric monoidal" with "monoidal" everywhere above, except that I think extra conditions are required for the resulting functors to be closed under composition (e.g. $V$ should probably still be symmetric monoidal and it should act "centrally" on $M$). Coefficients are now given by $V$-valued presheaves on the free monoidal category on however many objects.

It's important to note that $S$ and $V$ have nothing to do with each other. The misleading thing about the classical case of combinatorial species is that $S$ and $V$ look very similar; the more general theory shows how they diverge. A very important special case is when $V$ is some variant of vector spaces; then $V$-valued species are Schur functors, which subsequently naturally act on any symmetric monoidal linear category with enough colimits.

• As for Chomsky-Schutzenberger, one possible categorification of being an algebraic generating function is being an initial algebra or coalgebra for a polynomial functor (ncatlab.org/nlab/show/initial+algebra+of+an+endofunctor), and then I guess Chomsky-Schutzenberger corresponds to Lambek's theorem. Mar 2, 2015 at 5:25
• I asked this question so long ago I forget what I was after. I will try to suggest your answer soon. Thanks. Mar 2, 2015 at 14:43