Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Composition of combinatorial species

Peva Blanchard (Jul 25 2024 at 13:20):

I recently learned about combinatorial species (which I find particularly beautiful).

Let $B$ be the groupoid of finite sets and bijections. A species is defined as a functor $F: B \to B$.

There is a notion of composition of species. If $F$ and $G$ are two species, and $U$ is a finite set, then

$$(F \odot G)[U] = \sum_{\text{partition}~\Gamma~\text{of}~U} F(\Gamma) \cdot \prod_{V \in \Gamma} G(V)$$

I.e., a $F \odot G$ structure is specified by

• a partition $\Gamma = \{U_1,\dots,U_l\}$ of $U$
• a $F$-structure on $\{U_1,\dots,U_l\}$
• and a collection of $G$-structures in $G(V)$ for every $V \in \Gamma$.
  This resembles the composition of polynomials, or formal series.

This is clearly not the composition as endofunctors on $B$.
My first question is: do the two compositions relate in some way?

Second, for fun, I wanted to see what happens if we ask the endofunctor $F$ to "act like a monad" with respect to the species composition. I.e., (at least) to have a natural transformation $F \odot F \Rightarrow F$. It seems that we obtain "tree-like" structures that can be grafted together. (it reminded me of operad, but I know very little beyond the definition, so I'm not sure).
Second question: does this "act like a monad w.r.t. the species composition" make sense?

John Baez (Jul 25 2024 at 13:35):

Any species $F: B \to B$ defines an endofunctor $\hat{F}: \mathsf{Set} \to \mathsf{Set}$ by

$\widehat{F}(X) = \displaystyle{ \sum_{n= 0}^\infty \frac{F(n) \times X^n}{S_n} }$

where I'm identifying $n$ with some $n$-element set, and the symmetric group $S_n$ acts on both $F(n)$ and $X^n$ in the obvious ways. This formula should remind you strongly of a Taylor series, and functors of the form $\widehat{F}$ are called analytic functors.

Composition of species corresponds to composition of analytic functors:

$\widehat{(F \odot G)} \cong \widehat{F} \circ \widehat{G}$

John Baez (Jul 25 2024 at 13:39):

Peva Blanchard said:

Second, for fun, I wanted to see what happens if we ask the endofunctor $F$ to "act like a monad" with respect to the species composition. I.e., (at least) to have a natural transformation $F \odot F \Rightarrow F$. It seems that we obtain "tree-like" structures that can be grafted together. (it reminded me of operad, but I know very little beyond the definition, so I'm not sure).

Very smart!

A monoid object in the category of species with its composition tensor product is exactly an operad. This is one of the slickest ways to define operads.

So, unpacking this a bit: an operad is a species with a multiplication $m: F \odot F \Rightarrow F$ and also the unit $i: I \to F$ where $I$ is the unit object for the composition tensor product, and $m$ and $i$ need to obey the associative law and left/right unit laws.

It's very good to take this definition and unpack it even further to get a longer and very explicit definition of 'operad'.

John Baez (Jul 25 2024 at 13:45):

So we can say:

1) A monoid object in the monoidal category of endofunctors on Set with its composition tensor product is a monad.

2) A monoid object in the monoidal category of species with its composition tensor product is an operad.

It's not a coincidence that they rhyme: Peter May did that on purpose.

Even better, using the formula I wrote down, any operad $F$ gives a monad $\widehat{F}$! But we only get certain specially nice monads this way.

Peva Blanchard (Jul 25 2024 at 14:06):

Oh wow, thank you! CT is so full of wonders.

Morgan Rogers (he/him) (Jul 25 2024 at 15:40):

(It's a symmetric operad btw, I think "operad" on the nLab refers to the non-symmetric version)

Peva Blanchard (Jul 25 2024 at 15:44):

Oh, and I guess the difference between a symmetric operad vs a non-symmetric would be analog to the difference between exponential generating function and an ordinary generating function ?

$$\begin{align*} F_{egs} X &= \sum_{n \ge 0} \frac{F(n) \times X^n}{{\frak S}_n} \\ F_{ogs} X &= \sum_{n \ge 0} F(n) \times X^n \\ \end{align*}$$

Peva Blanchard (Jul 25 2024 at 15:54):

By the way, I arrived to this topic quite unexpectedly. With a friend, we are studying a random field on graphs (e.g., scoring for recommendation in social networks). We want to compute correlation functions, so I started learning about Feynman diagrams (the simple ones, not QFT and alike). I ended up on combinatorial species: it seems that it allows me to focus on the combinatorics without the physics.

There is, for instance, this result that says that to compute cumulants, you only need to consider the connected diagrams without vacuum sub-diagrams (I think). But I read that from a physics book, so this still seems pretty mysterious to me. Hopefully, I can rederive the result in terms of species.

John Baez (Jul 25 2024 at 18:03):

Morgan Rogers (he/him) said:

(It's a symmetric operad btw, I think "operad" on the nLab refers to the non-symmetric version)

What??? That's not the usual default version. Anyway, if you want non-symmetric operads, just replace $B$, the category of finite sets and bijections, by the category $\mathbb{N}$ of finite totally ordered sets and order-preserving bijections.
(I'm calling it $\mathbb{N}$ because it's equivalent to the discrete category on the set $\mathbb{N}$).

Then everything I said still works, and you get a corresponding theory of species that describe structures you can put on totally ordered sets, and non-symmetric operads, also called 'planar' operads.

And as Peva notes, there's both a theory of generating functions for species, called exponential generating functions, and a theory of generating functions for species you can put on totally ordered sets, called the theory of ordinary generating functions.

John Baez (Jul 25 2024 at 18:06):

These two parallel frameworks are just two of an infinitude of similar frameworks, but they are the most famous two.

Todd Trimble (Jul 25 2024 at 18:31):

Morgan Rogers (he/him) said:

(It's a symmetric operad btw, I think "operad" on the nLab refers to the non-symmetric version)

No, it refers to several versions of [[operad]], but at the top of the page is the symmetric aka permutative version.

John Baez (Jul 25 2024 at 18:33):

Okay, good! I was shocked by what Morgan said, but too lazy to check.

fosco (Jul 25 2024 at 19:32):

@Peva Blanchard let me give you a few references

• for the equivalence between species and analytic functors, Joyal's paper is the standard one, but I found a very well-written article of Adamek quite enlightening (it uses very basic category theory, and a clever observation of Vera Trnkova on endofunctors of Set) http://www.tac.mta.ca/tac/volumes/21/11/21-11abs.html
• for the internal monoid of the "substitution" product (the one you denote as $\circ$ or $\odot$), see here http://www.tac.mta.ca/tac/reprints/articles/13/tr13abs.html

fosco (Jul 25 2024 at 19:37):

Peva Blanchard said:

Oh, and I guess the difference between a symmetric operad vs a non-symmetric would be analog to the difference between exponential generating function and an ordinary generating function ?

$$\begin{align*} F_{egs} X &= \sum_{n \ge 0} \frac{F(n) \times X^n}{{\frak S}_n} \\ F_{ogs} X &= \sum_{n \ge 0} F(n) \times X^n \\ \end{align*}$$

There are three things you can do with the sequence of sets $F(n)$ determining a species

• forget that each $F(n)$ is a left $S_n$-set and consider the series that you call $F_{ogs}$, defining the element $\sum_{n\ge 0} |F(n)| X^n$ where $|F(n)|$ denotes cardinality.
• still forget the $S_n$-action, but consider the series $F_{egs}=\sum_{n\ge 0} \frac{|F(n)|}{n!} X^n$. This is what is usually done when defining a formal power series out of a species -one reason, not the only one, to ensure convergence, and to make it such that the "species of elements", i.e. the constant functor at $\{*\}$, has egs

fosco (Jul 25 2024 at 19:38):

the exponential $e^X$, as it should.

fosco (Jul 25 2024 at 19:40):

this second construction has a problem though: there are two species, the species of permutations ($S(n)$ is the set of bijections of an $n$-set) and the species of linear orders ($L(n)$ is the set of total orders taht one can put on an $n$-set) such that $S(n), L(n)$ have both $n!$ elements. So,
$S_{egs} = \sum_{n\ge 0}X^n = \frac 1{1-X} = L_{egs}$
without having that $S\cong L$ as functors.

fosco (Jul 25 2024 at 19:42):

There is a solution to this problem: take into account the reason why $S$ and $L$ are not isomorphic: they are not isomorphic qua left $S_n$-sets.

fosco (Jul 25 2024 at 19:44):

this leads to the definition of the "reduced" formal power series associated to a species -it has another name but I'm lazy to go and check now- where instead of the cardinality $|F(n)|$ you consider the cardinality of the quotient of each $F(n)$ by its left $S_n$-action, $|\frac{F(n)}{\sim}|$ where $\sim$ is the equivalence relation "being in the same orbit". So

$\displaystyle F_{rgs} := \sum_{n\ge 0}|\frac{F(n)}{\sim}| X^n$

fosco (Jul 25 2024 at 19:44):

Now some work for you: find the reduced generating series of $S$ and $L$, they will evidently be different. Problem solved!

Todd Trimble (Jul 25 2024 at 20:20):

for the equivalence between species and analytic functors, Joyal's paper is the standard one, but I found a very well-written article of Adamek quite enlightening

Warning! This is not an equivalence between the category of species and the category of analytic functors, which I think I've seen asserted incorrectly in the literature. However, Joyal did show that it is an equivalence between the groupoid of species and the groupoid of analytic functors.

For example, take the species $X$ which is terminal at a set of cardinality $1$ and initial for all other finite cardinalities, and take the species $X^{\otimes 2}/S_2$ which is terminal at a set of cardinality $2$ and initial for all other finite cardinalities. There is no species map $X \to X^{\otimes 2}/S_2$. However, there is a natural transformation between their analytic functors, where the analytic functor on $X$ is the identity functor on $\mathsf{Set}$ and the analytic functor on $X^{\otimes 2}/S_2$ takes a set $S$ to its symmetric square [the quotient of $S \times S$ that identifies $(x, y)$ with $(y, x)$]. This natural transformation is induced by the diagonal map $S \to S \times S$.

Morgan Rogers (he/him) (Jul 25 2024 at 20:44):

@Todd Trimble The informal definition in the introduction to the operads nLab page doesn't mention actions of symmetric groups and makes a comparison to multicategories (and iirc on the multicategories page the default is the non-symmetric version). Symmetric operads are introduced under that heading. So I think what I said was a meaningful clarification for someone who looked up operads in response to John's comment.

Todd Trimble (Jul 25 2024 at 21:38):

What you call a "clarification"

I think "operad" on the nLab refers to the non-symmetric version

is what I would still call misleading, because it suggests the very thing that made John react. It could also dissuade someone from using the nLab article, thinking "oh, then, that's not the thing I'm after" if they take you at your word.

But everything in your last comment before the last sentence is certainly valid and worth mentioning, and luckily the discussion after your first comment really has clarified matters.

In the service of yet further clarification, now would be a good time to remind readers here that Idea sections in the nLab are typically breezy and sketchy and leave stuff out, and people should always look below the Idea section if they want correct definitions.

John Baez (Jul 25 2024 at 21:43):

I wouldn't mention symmetric group actions if I were giving a 5-minute elevator pitch about operads, but I might mention that May introduced operads to characterize infinite loop spaces, and it's true that for this the symmetric group actions are crucial.

Peva Blanchard (Jul 25 2024 at 21:58):

fosco said:

Now some work for you: find the reduced generating series of $S$ and $L$, they will evidently be different. Problem solved!

Thanks for the input! The puzzle was very instructive and entertaining! Here's my take.

First, we have actions.

• The action of $SU$ on $SU$ is given by conjugation $\sigma \mapsto (f \mapsto \sigma \cdot f \cdot \sigma^{-1})$. This action is not free.
• The action of $SU$ on $LU$, on the other hand, is given by $\sigma \mapsto (f \mapsto \sigma \cdot f)$. Here I am encoding a linear order on $U$ as a bijection $f : \{1,\dots,n\} \to U$. This action is free and transitive.

I think the "freeness" of the action is what makes the difference between the two.

Indeed, assume that there is a natural isomorphism $S \xRightarrow{\eta} L$. Fix an arbitrary permutation $f \in SU$, and let $g = \eta_U f$ be the corresponding linear order on $U$. A consequence of the naturality condition is that $\eta_U$ induces a bijection between the orbit of $f$ and the orbit of $g$ under the action of $SU$. Taking the identity for $f$ reveals the contradiction. On one side, the orbit has size $1$, and on the other, the orbit has size $n!$.

Now let's look at the rgs series of $S$. For every $n$, the number of conjugacy classes in $S[n]$ is, I think, the number of partitions of $n$, i.e., the Bell number $B_n$. (If I remember correctly, two permutations are conjugate iff they have the same cycle decomposition). So

$$S_{rgs}(z) = \sum_n B_n \cdot z^n$$

Regarding the rgs series of $L$, for every $n$, the number of orbits in $L[n]$ under the action of $S[n]$ is $1$, since the action is transitive. Hence,

$$L_{rgs}(z) = \sum_n z^n = \frac{1}{1-z}$$

Peva Blanchard (Jul 25 2024 at 22:02):

to complete the proof: I should say that there are Bell numbers that are different than $1$. E.g., $B_3 \ge 2$.

Morgan Rogers (he/him) (Jul 26 2024 at 13:36):

Todd Trimble said:

What you call a "clarification"

I think "operad" on the nLab refers to the non-symmetric version

is what I would still call misleading, because it suggests the very thing that made John react. It could also dissuade someone from using the nLab article, thinking "oh, then, that's not the thing I'm after" if they take you at your word.

Fair enough, I apologize. I eventually put together that my misremembering of the structure of the operads page comes from confusing it with the multicategories page I mentioned, where one can find (after the formal definition of multicategory) the warning:

Many people (especially non-category theorists) use the word multicategory or the word colored operad to mean what we would call a symmetric multicategory / symmetric operad. These are multicategories equipped with an action of the symmetric group  on the multimorphisms  such that the composition is equivariant with respect to these actions.

The conclusion of this (tangent to the topical) conversation for me is that if "operad" means "symmetric operad" by default, then the motivation/explanation in the opening of the [[operad]] page should be replaced with a source of intuition that more obviously comes equipped with symmetries, such as the loop space example.

Todd Trimble (Jul 26 2024 at 13:39):

Okay, thanks. If anyone feels moved to put in more about that into the Idea section, have at it! (Maybe I'd get around to that, maybe not.)

John Baez (Jul 26 2024 at 13:41):

I could give it a quick try. Right the page is locked - someone else is editing it.

Todd Trimble (Jul 26 2024 at 16:57):

Todd Trimble said:

for the equivalence between species and analytic functors, Joyal's paper is the standard one, but I found a very well-written article of Adamek quite enlightening

Warning! This is not an equivalence between the category of species and the category of analytic functors, which I think I've seen asserted incorrectly in the literature. However, Joyal did show that it is an equivalence between the groupoid of species and the groupoid of analytic functors.

For example, take the species $X$ which is terminal at a set of cardinality $1$ and initial for all other finite cardinalities, and take the species $X^{\otimes 2}/S_2$ which is terminal at a set of cardinality $2$ and initial for all other finite cardinalities. There is no species map $X \to X^{\otimes 2}/S_2$. However, there is a natural transformation between their analytic functors, where the analytic functor on $X$ is the identity functor on $\mathsf{Set}$ and the analytic functor on $X^{\otimes 2}/S_2$ takes a set $S$ to its symmetric square [the quotient of $S \times S$ that identifies $(x, y)$ with $(y, x)$]. This natural transformation is induced by the diagonal map $S \to S \times S$.

I certainly should have added that there is however an equivalence between the category of species and the category of analytic functors whose morphisms are quasi-cartesian natural transformations between them. This means all the naturality squares are quasi-cartesian: commutative squares for which the unique mediating morphism from its span to the pullback of its cospan is an epimorphism (see e.g. Fiore, bottom of page 5 and corollary 4.6).

fosco (Jul 26 2024 at 21:18):

Todd, you're right. But I should have added it, sorry for not mentioning the subtlety! :smile:

Nathaniel Virgo (Aug 04 2024 at 02:21):

I'm trying to work through this

John Baez said:

Anyway, if you want non-symmetric operads, just replace $B$, the category of finite sets and bijections, by the category $\mathbb{N}$ of finite totally ordered sets and order-preserving bijections.
(I'm calling it $\mathbb{N}$ because it's equivalent to the discrete category on the set $\mathbb{N}$).

Then everything I said still works, and you get a corresponding theory of species that describe structures you can put on totally ordered sets, and non-symmetric operads, also called 'planar' operads.

but I've run into an issue. It might be because I'm trying to do this first instead of the symmetric version, but still, maybe I can ask for a hint.

(edit: the short version is, do we also need to impose that the multiplication and unit of the monad are cartesian natural transformations?)

I think we're talking about the ordinary generating function because I don't think we have an action of $S_n$, so we have a functor $F:\mathbb{N}\to \mathbb{N}$, and we're considering the polynomial functor on $\bf Set$

$$\hat F(X) = \sum_{n=0}^\infty F(n)\times X^n.$$

Adding the extra data to turn this into a monad should yield a non-symmetric operad.

The interpretation is that $F(n)$ is the hom-set of morphisms with arity $n$. Then $\hat F(1)$ is just the set of all the morphisms regardless of their arity, while an $\hat F(X)$ is to be thought of as a morphism "formally applied" to elements of $X$, so each input to the morphism gets an element of $X$.

This means in particular that an element of $\hat F(\hat F(1))$ consists of an element of $F(n)$ for some $n$, together with another $n$ elements of $\hat F(1)$ (i.e. morphisms in the operad), which we think of as being wired up to its inputs.

Then the idea is that given a monad $(\hat F, \mu,\eta)$, the multiplication $\mu$ gives the composition law and $\eta$ gives the identity. Specifically, $\mu_1:\hat F(\hat F(1))\to \hat F(1)$ takes in a morphism "formally applied" to a bunch of other morphisms and returns a single morphism, while $\eta_1:1\to \hat F(1)$ picks out some morphism to be the identity.

But here's the problem: in working my way through what the monad laws say here, I can't seem to see anything that forces $\eta_1$ to pick out an element of $F(1)$ rather than $F(n)$ for some other $n$, so it seems like the identity can have an arity other than 1. And similarly, I can't find anything that forces $\mu_1:\hat F(\hat F(1))\to \hat F(1)$ to preserve the number of inputs. So if we have elements of $F(n), F(k_1), \dots, F(k_n)$, it seems like we can compose them to get something with an arity other than $k_1 + \dots + k_n$.

Is it that these things are actually implied by the monad laws and I've missed something (which is quite possible), or is there some other condition we need to impose on the monad to enforce this?

Nathaniel Virgo (Aug 04 2024 at 02:35):

is it that $\mu$ and $\eta$ have to be cartesian natural transformations?

John Baez (Aug 04 2024 at 06:58):

I didn't mean that if $\hat{F}$ is given some arbitrary monad structure then $F$ becomes a nonsymmetric operad. That's like swimming upstream. I meant that if we give the category of functors $F : \mathbb{N} \to \mathsf{Set}$ its "substitution" tensor product $\circ$, a monoid object in this category is a nonsymmetric operad.

There's a monoidal functor from the category of functors $F : \mathbb{N} \to \mathsf{Set}$ to the category of monads on $\mathsf{Set}$, defined on objects by

$\displaystyle{ \hat F(X) = \sum_{n=0}^\infty F(n)\times X^n }$

It follows that if $F$ is a monoid object, $\hat{F}$ become a monad.

I could be wrong, but this is what I was trying to say.

John Baez (Aug 04 2024 at 07:04):

The analogue for symmetric operads is this:

The category of species is the category of functors $F : B \to \mathsf{Set}$ where $B$ is the groupoid of finite sets and bijections. If we give the category of species its "substitution" tensor product $\circ$, a monoid object in this category is a symmetric operad.

John Baez (Aug 04 2024 at 07:12):

By the way, you seem to be defining species to be functors $F: B \to B$. That makes the generating function well-defined but for a well-behaved category it's often good to use the larger category of functors $F: B \to \mathsf{Set}$, which is equivalent to $\mathsf{Set}^{B^{\textrm{op}}}$, since then we can use a bunch of results about presheaf categories without thinking.