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: theory: category theory

Topic: species

John Baez (Jan 05 2024 at 11:28):

The nLab article lists 5 monoidal structures on [[species]], and @fosco's recent comments here make me want to fit them together more clearly. (There could also be even more.) They might be related to the various monoidal stuctures on [[polynomial functors]], but I'd rather start by considering a simpler analogous situation: the various monoid structures on $\mathbb{N}[[x]]$. I have a lot say but I'll just get started and say a little.

John Baez (Jan 05 2024 at 11:33):

For any rig $R$, $R[[x]]$ is the rig of formal power series

$\hat{f}(x) = \sum_{i = 0}^\infty f_i x^i$

where $f_i \in R$. Its underlying set is isomorphic to the set of functions

$f: \mathbb{N} \to R$

A lot of stuff I'll say will apply to any commutative rig $R$, but I'm mainly interested in $R = \mathbb{N}$, the initial rig, and traditional mathematicians may prefer $R = \mathbb{Z}$ or $R = \mathbb{C}$ or something like that.

John Baez (Jan 05 2024 at 11:40):

Here are some monoid structures on $R[[x]]$.

1. Addition. This is the usual addition in $R[[x]]$ and also the pointwise addition of functions $f: \mathbb{N} \to R$.
2. The Cauchy product. This is the usual multiplication of power series in $R[[x]]$. I'm giving it this goofy name just to hint that this is related to the monoidal structure on species called the Cauchy product.

John Baez (Jan 05 2024 at 11:41):

3. The Hadamard product. This is the usual pointwise multiplication of functions $f: \mathbb{N} \to R$. I'm giving it this goofy name just to hint that this is related to the monoidal structure on species called the Hadamard product.

John Baez (Jan 05 2024 at 11:43):

4. The Dirichlet product. The underlying set of $R[[x]]$ is isomorphic to the set of Dirichlet series $\tilde{f}(s) = \sum_{n = 0}^\infty f_n n^{-s}$. The usual multiplication of Dirichlet series thus gives $R[[x]]$ yet another monoid structure. (Note that Dirichlet series are again a kind of 'formal' series, no convergence required.)

John Baez (Jan 05 2024 at 11:52):

5. Composition. We can attempt to formally 'compose' formal power series $\hat{f}, \hat{g} \in R[[x]]$ and get

$(f \circ g)(x) = f(g(x))$

but I believe this can lead to a divergent sum unless $g(0) = 0$, meaning that the constant term $g_0$ vanishes.

John Baez (Jan 05 2024 at 11:54):

I believe this problem goes away if we choose $R = \mathbb{N} \cup \{\infty\}$ with its hopefully obvious rig structure; then we can say any divergent sum equals $\infty$.

John Baez (Jan 05 2024 at 11:54):

When we categorify and work with species this problem goes away too, thanks to the existence of infinite sets.

John Baez (Jan 05 2024 at 11:56):

@James Deikun says there's also a problem with the Dirichlet product unless we impose a condition on the 0th term. I don't see this! Why is that?

James Deikun (Jan 05 2024 at 11:59):

Every number divides zero, so term 0 of the resulting Dirichlet series is the sum of {the product of the two 0th terms, the 0th term of the first series times the sum of non-0th coefficients of the second series, the 0th term of the second series times the sum of non-0th coefficients of the first series}.

James Deikun (Jan 05 2024 at 12:01):

The problem also goes away if both of your series are finite, though.

John Baez (Jan 05 2024 at 12:01):

Okay, thanks! I never thought about that.

Anyway, I'm hoping that problems with monoid structures 4 and 5 go away if we let $R$ be nice enough. I'm not sure exactly what I need, but maybe I need a partially ordered rig where everything is $\ge 0$, addition and multiplication are monotone, and every subset has a supremum. In rigs like this, properly defined, we should be able to sum any infinite series and have all the rules we want hold.

John Baez (Jan 05 2024 at 12:02):

And yes, you're right - we can also switch to working with $R[x]$.

James Deikun (Jan 05 2024 at 12:04):

$\omega$-continuous semirings maybe?

John Baez (Jan 05 2024 at 12:05):

In some sense working with $R[x]]$ is more natural since it's the free $R$-algebra on one generator! The only reason I decided to talk about $R[[x]]$ is that formal power series show up as generating functions of species, so one would like taking the generating function to map all 5 monoidal structures on species to operations on $R[[x]]$. (But this raises various issues - like the one James raised, and also the issue of the $1/n!$ in the formula for generating functions.)

John Baez (Jan 05 2024 at 12:06):

Perhaps for my current 'decategorified' questions I'll switch to talking about $R[x]$.

Oscar Cunningham (Jan 05 2024 at 12:09):

(You have an extra ']' in the first 'R[x]' there.)

John Baez (Jan 05 2024 at 12:11):

Thanks.

John Baez (Jan 05 2024 at 12:13):

Okay, so I'll work with $R[x]$. Now to the actual point: I've presented 5 monoid structures on $R[x]$ as if they were a kind of 'grab-bag', a disorganized list of possibilities. But that makes it hard to see the laws relating them. And there's something much more organized going on here.

John Baez (Jan 05 2024 at 12:17):

Roughly it seems to work like this. For any monoid $M$ and any commutative ring $R$, the set of finitely supported functions

$f: M \to R$

becomes a rig with the 'convolution' product

$(f \ast g)(m) = \sum_{m'+m'' = m} f(m') g(m'')$

(Maybe I don't need $R$ to be commutative here?)

John Baez (Jan 05 2024 at 12:17):

$\mathbb{N}$ is free monoid on one generator and therefore the initial rig. So it has two monoid structures. So we get two 'convolution' monoid structures on the set of finitely supported functions

$f: \mathbb{N} \to R$

John Baez (Jan 05 2024 at 12:18):

One of these is the Cauchy product and the other is the Dirichlet product.

John Baez (Jan 05 2024 at 12:19):

But also we get two more monoid structures on the set of finitely supported functions $f: \mathbb{N} \to R$, coming from pointwise addition and multiplication! These are what I called addition and the Hadamard product.

John Baez (Jan 05 2024 at 12:19):

I guess all this stuff would still work if we replace $\mathbb{N}$ by any rig - so we should generalize it.

John Baez (Jan 05 2024 at 12:21):

But then there's a final twist of the knife, which is special to $\mathbb{N}$: the set of finitely supported functions $f: \mathbb{N} \to R$ is isomorphic to $R[x]$, the free $R$-algebra on one generator. And so it gets the 'composition' product, defined by composing polynomials.

John Baez (Jan 05 2024 at 12:27):

The point here is that since $R[x]$ is free on one generator $x$, any element $g \in R[x]$ determines a unique homomorphism $R[x] \to R[x]$ sending $x$ to $g$. This homomorphism sends any $f \in R[x]$ to some element we call $f \circ g$. And this is composition of polynomials!

John Baez (Jan 05 2024 at 12:31):

Note that since $f \mapsto f \circ g$ is a homomorphism we get 'left distributive laws'

$(f_1 + f_2) \circ g = f_1 \circ g + f_2 \circ g$
$(f_1 f_2) \circ g = (f_1 \circ g)(f_2 \circ g)$

John Baez (Jan 05 2024 at 12:32):

But we don't get the right distributive laws - they're not true.

John Baez (Jan 05 2024 at 12:34):

$R[x]$ together with addition, the Cauchy product (= multiplication of polynomials), and composition is part of something even better, called a 'rig-plethory'. These are defined here:

• Baez, Moeller and Trimble, Schur functors and categorified plethysm.

See the introduction and section 5.

John Baez (Jan 05 2024 at 12:41):

But this story seems to leave out the Hadamard product and Dirichlet product! So the question is: how can we include those too, in a nice way?

John Baez (Jan 05 2024 at 12:41):

I suppose I should explain rig-plethories, to make that a fair question! But I have to quit now.

JR (Jan 05 2024 at 13:16):

John Baez said:

5. Composition. We can attempt to formally 'compose' formal power series $\hat{f}, \hat{g} \in R[[x]]$ and get

$(f \circ g)(x) = f(g(x))$

but I believe this can lead to a divergent sum unless $g(0) = 0$, meaning that the constant term $g_0$ vanishes.

https://en.wikipedia.org/wiki/Carleman_matrix#Properties

fosco (Jan 05 2024 at 13:25):

A family of monoidal structures on species is described at 2.11 in Street's "charades" paper https://arxiv.org/pdf/1503.02783.pdf cf also its section 11 calling the groupoid of linear bijections of $\mathbb F_q$ (described in "The category of representations of the general linear groups over a finite field") into play

I have both papers next on the reading list !

James Deikun (Jan 05 2024 at 14:31):

So the first family of monoidal structures from Street is given for $\mathsf{Set}$-valued species as:

$$(F \otimes_{L} G)(Z) = \coprod_{X \cup Y = Z} F(X) \times L(X \cap Y) \times G(Y)$$

James Deikun (Jan 05 2024 at 14:32):

where $L$ is some fixed species (in general it needs to be enhanced with a braiding a la [[Drinfeld center]] but we can probably ignore that for this case).

James Deikun (Jan 05 2024 at 14:35):

The other one doesn't seem to work for Set-species at all.

James Deikun (Jan 05 2024 at 14:59):

There's also a product on power series $f \boxtimes g = \frac{f + g}{1 - fg}$ that should give rise to a product on species.

Todd Trimble (Jan 05 2024 at 20:43):

For any power series $\phi(x)$ whose constant coefficient is $0$ and whose linear coefficient is invertible, one can "conjugate" addition into a commutative, associative product on power series, $f \boxtimes g = \phi(f(\phi^{-1} x) + g(\phi^{-1} x))$, but I wouldn't automatically expect such to lift functorially to species, since there may be pesky minus signs. But I guess the result for $\phi(x) = \tan(x)$, which is

$\frac{f + g}{1 - fg} = (f + g)(1 + fg + (fg)^2 + \ldots),$

might be okay (although expect the constant coefficient to be "infinite", unless $f, g$ have constant coefficient $0$).

James Deikun (Jan 05 2024 at 20:58):

I guess it lifts to species as "an $F \boxtimes G$ structure on X is an ordered partition of X into an odd number of possibly-empty subsets, which alternate between having an F-structure and a G-structure".

James Deikun (Jan 05 2024 at 21:02):

(I specifically picked that one out of all the examples I knew of that construction because it looked like it would lift, and to something nontrivial but not too complicated.)

James Deikun (Jan 05 2024 at 21:08):

(I'm not too confident the associativity lifts under my description though... :frowning: )

Jacques Carette (Jan 05 2024 at 22:04):

A quick note that Brent Yorgey worked out some nice uniform ways to look at many of these monoidal structures on Species in his 2014 PhD Thesis; see Chapter 4. The whole thesis is a pleasure to read, Brent takes enormous care in ensuring his works twins precise definitions with illustrative explanations. The 'arithmetic product' in particular gets a new treatment in section 4.2.2.

John Baez (Jan 05 2024 at 22:16):

Thanks, everyone! Infinitely many symmetric monoidal structures on $\mathsf{Set}$ are described here, and infinitely many more here. Some commutative products on formal power series naturally arise from formal group laws, and Qiaochu Yuan tried to categorify some of these and obtain symmetric monoidal structures on $\mathsf{Set}$ here.

John Baez (Jan 05 2024 at 22:19):

It would be interesting to try to classify all symmetric monoidal structures on $\mathsf{Set}$, or on the category of species. But right now I'm less interested in doing that than in seeing how the 5 already listed commutative monoid structures on $\mathbb{N}[x]$ fit together into a single structure (e.g., what compatibility relations they obey, and how to derive these 'instantly'), and then how the 5 corresponding symmetric monoidal structures on the category of species fit together into a single structure.

John Baez (Jan 05 2024 at 22:42):

It may not be obvious, but I've only been writing things about monoid structures on $R[x]$ that should easily categorify to give results about monoidal category structures on species! I find it easiest to tackle problems in a decategorified situation and then categorify, when possible.

John Baez (Jan 05 2024 at 22:47):

Summarizing my main message so far: suppose $R$ and $S$ are commutative rigs. Let $X$ be the set of finitely supported functions $h: S \to R$, i.e. functions such that $h(s) = 0$ for all but finitely many $S$. Then $X$ gets 4 commutative monoid structures: 2 coming from the 2 monoid structures on $R$ via pointwise operations, and 2 more coming from the 2 monoid structures on $S$ via convolution.

John Baez (Jan 05 2024 at 22:48):

I keep thinking the latter 2 are better understood as comonoid structures, and I should flesh this out.

John Baez (Jan 05 2024 at 22:50):

But anyway, when $S = \mathbb{N}$ then there's an obvious isomorphism of sets $X \cong R[x]$, and 2 of the above 4 monoid structures are the usual rig structure on $R[x]$: addition and multiplication of polynomials!

Todd Trimble (Jan 05 2024 at 22:50):

John Baez said:

Thanks, everyone! Infinitely many symmetric monoidal structures on $\mathsf{Set}$ are described here, and infinitely many more here. Some commutative products on formal power series naturally arise from formal group laws, and Qiaochu Yuan tried to categorify some of these and obtain symmetric monoidal structures on $\mathsf{Set}$ here.

I'm having trouble squaring the second sentence with the third. Just how rigorously established were these symmetric monoidal structures? I've read only cursorily, but it looked a bit conjectural.

John Baez (Jan 05 2024 at 22:52):

The infinitely many symmetric monoidal structures found by JMAA and Speyer (listed in the first two references in blue) did not all come from formal group laws. Qiaochu tried to get some from formal group laws, and it seems some of those did not work.

John Baez (Jan 05 2024 at 22:55):

I think everything I know about this is explained more clearly at those links.

Todd Trimble (Jan 05 2024 at 22:59):

I'm not seeing the infinitely many examples from the first reference in blue (am I blind?). But Speyer does indeed seem to reference infinitely many that do come from formal group laws.

John Baez (Jan 06 2024 at 10:49):

The set $S$ in the first reference is arbitrary, and each choice of cardinality of that set gives a different monoidal structure on $\mathsf{Set}$. That's all I meant.

John Baez (Jan 06 2024 at 10:57):

I hinted that this could be categorified, but I guess I should actually do it so everyone sees what I mean:

John Baez said:

Summarizing my main message so far: suppose $R$ and $S$ are commutative rigs. Let $X$ be the set of finitely supported functions $h: S \to R$, i.e. functions such that $h(s) = 0$ for all but finitely many $S$. Then $X$ gets 4 commutative monoid structures: 2 coming from the 2 monoid structures on $R$ via pointwise operations, and 2 more coming from the 2 monoid structures on $S$ via convolution.

John Baez (Jan 06 2024 at 10:59):

There are different possible categorifications but let's try this one. Like algebraic geometers use 'ring' to mean 'commutative rig', I'm going to use '2-rig' to mean 'symmetric 2-rig', one where the monoidal structure is symmetric. I'm doing this just to save on typing now!

Say a cocomplete 2-rig is a cocomplete symmetric monoidal category $R$ where the tensor product $\otimes$ distributes over colimits. Note $R$ has two symmetric monoidal structures, $\otimes$ and $+$, the first distributing over the second.

Define a [[rig category]] following Kelly and Laplaza: it's a category $S$ with two symmetric monoidal structures $\otimes$ and $\oplus$, the first distributing over the second, with the distributivity natural isomorphism obeying a legion of coherence laws.

John Baez (Jan 06 2024 at 11:01):

Suppose $R$ is a cocomplete 2-rig and $S$ is a small rig category. Let $X = R^S$ be the category of all functors from $S$ to $R$. Then $X$ gets 4 symmetric monoidal structures: 2 coming from the 2 symmetric monoidal structures $\otimes$ and $+$ on $R$ via pointwise operations, and 2 more coming from the 2 symmetric monoidal structures $\otimes$ and $+$ on $S$ via [[Day convolution]].

John Baez (Jan 06 2024 at 11:10):

I don't know great names for these 4 symmetric monoidal structures on $R^S$, but let's use $\otimes$ and $+$ to stand for those coming from $\otimes$ and $+$ on $R$ via pointwise operations, and $\ast_\otimes$ and $\ast_+$ to stand for those coming from $\otimes$ and $+$ on $S$ via Day convolution.

John Baez (Jan 06 2024 at 11:12):

Then I believe $R^S$ is cocomplete and $\otimes$, $\ast_\otimes$ and $\ast_+$ distribute over colimits, so $R^S$ becomes a cocomplete 2-rig in three ways! Maybe someone should check me on this.

John Baez (Jan 06 2024 at 11:33):

Now let's see how species are a special case of this. In this example:

• $R$ is the category of sets, made into a cocomplete 2-rig with $\otimes = \times$.
• $S$ is the groupoid of finite sets, which is a [[rig category]] with symmetric monoidal structures $\otimes$ and $\oplus$ that arise from restricting $+$ and $\times$ from the category of finite sets to the groupoid of finite sets.

John Baez (Jan 06 2024 at 11:36):

Then $R^S$ is the category of species and we get 4 symmetric monoidal structures on it:

1. $+$ is the coproduct of species.
2. $\otimes$ is the Hadamard product, i.e. cartesian product, of species.
3. $\ast_{+}$ is the Cauchy product of species.
4. $\ast_\otimes$ is the Dirichlet product of species.

John Baez (Jan 06 2024 at 11:40):

These fit together to make species into a cocomplete 2-rig in three ways: via the Hadamard product, Cauchy product and Dirichlet product.

Kenji Maillard (Jan 08 2024 at 12:03):

The substitution product should also fit into this picture: fix any base functor $\iota : S \to R$ and $F, G \in R^S$, then $F \circ_\iota G := \mathrm{Lan}_{\iota} F \circ G$ endows $R^S$ with a skew-monoidal structure (cf Monads need not be endofunctors, T. Altenkirch, J. Chapman and T. Uustalu). In the case of species, I guess $\iota$ should be the embedding of the groupoid of finite sets into Set.
The reference above gives a sufficient condition (including fully faithfulness of $\iota$) for this skew-monoidal structure to be monoidal (Definition 4.1 and Theorem 4.4), but the condition does not apply to the case of species because $\iota$ is not full in that case.

John Baez (Jan 08 2024 at 16:55):

Cool! I'm a bit too lazy to read this paper right now, but what sort of things do $R$ and $S$ need to be for Altenkirch's result to hold? Maybe just categories? For me to get the other 4 monoidal structures I assumed $S$ is a rig category and $S$ is a complete 2-rig, but I bet they use far weaker assumptions.

Kenji Maillard (Jan 09 2024 at 12:13):

Indeed, this construction does not use the 2-rig structures, but it does use that $S$ is small and $R$ cocomplete in order to assert the existence of the left Kan extensions along $\iota$.

James Deikun (Jan 09 2024 at 12:31):

For $S$ a groupoid it should suffice for $\iota$ to reflect isomorphisms I think.

James Deikun (Jan 09 2024 at 12:38):

(Basically because being an isomorphism is absolute and thus preserved by all the parallel functors $F$. In general I think when $S$ consists solely of X-morphisms you could get a proper monoidal structure with weaker conditions on the subcategory of $R^S$ on functors that preserve X-morphisms where one of the weaker conditions is that $\iota$ reflects X-morphisms.)

James Deikun (Jan 09 2024 at 12:55):

Probably the easiest thing is just to point out that all the functors involved, excepting Kan extensions, factor uniquely through the inclusion of $R^\mathrm{core}$ in $R$ and just use the theorems and conditions in the paper for a product on $(R^\mathrm{core})^S$ which ends up yielding a (skew-)monoidal category isomorphic to the one on $R^S$ via the unique factorization and via all the Kan extensions "factoring" through extension along the inclusion.