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: The category theoretic origin of arithmetic product [x-post]

fosco (Dec 29 2023 at 22:50):

(I am crossposting from MathOverflow as this question is more oriented towards people with competence in category theory than in combinatorics; or at least, a category theorist might know the reference / I can brainstorm more peacefully / I can show off my sheer ignorance of enumerative combinatorics :grinning:

===

The paper "On the arithmetic product of combinatorial species" introduces a combinatorial interpretation for the arithmetic product of two combinatorial species $M,N$.

In short, let $F:Bij\to Set$ be a (finite) combinatorial species and define its (modified) Dirichlet series to be

$\displaystyle D_F(s) = \sum_{n=1}^\infty\frac{|F[n]|}{n!n^s}$

where $|F[n]|$ is the cardinality of the set $F[n]$. Then, the arithmetic product $\boxdot$ is a monoidal operation on the category of species such that $D_{M\boxdot N}(s)=D_M(s)D_N(s)$.

Explicitly, one takes an (exponential) power series $\sum \frac{a_n}{n!}X^n$ for the species $M$, and one $\sum \frac{b_n}{n!}X^n$ for $N$, and their arithmetic product is

$\displaystyle \sum \frac{c_n}{n!}X^n \qquad c_n := \sum_{d\mid n} \begin{Bmatrix}n\\d\end{Bmatrix}a_db_{n/d}$

(there is an unfortunate clash of notation between this notation and Stirling numbers of the 2nd kind here, but $\left\{\begin{smallmatrix}n\\ d\end{smallmatrix}\right\}$ is just the "modified binomial" $\frac{n!}{d!(n/d)!}$).

fosco (Dec 29 2023 at 22:50):

With sparse remarks here and there, the paper proves what boils down to the fact that the category of species has a symmetric monoidal structure given by $\boxdot$. The only thing is, usually Dirichlet series and their convolution are not defined in this way, but instead without the $\frac 1{n!}$. At any rate, it seems to me that with the appropriate substitution/transport of structure the monoidal category $(Species,+,\boxdot)$ can be regarded as a categorified version of the semiring of Dirichlet series with nonnegative integer coefficients.

My question is: is there a description of this monoidal structure that looks concise to a category theorist, or at least as concise as all other monoidal structures (Cartesian, Day convolution, substitution...) do? What is the universal property, if any, of the $\boxdot$ structure? (Compare this question with: the substitution product of species is the unique monoidal structure making $Species$ monoidally equivalent to the category of analytic functors + composition, and it's called "substitution product" because it coincides with the composition of formal power series $(\sum a_n t^n)\circ g = \sum a_n g(t)^n$).

My understanding is that this structure is related to the substitution product (obtained as iterated convolution) which is what the authors (and other people studying species with more combinatorial jargon) call "assemblies": indeed, they say:

The most interesting combinatorial construction associated to the arithmetic product is the assembly of cloned
structures. Informally, an assembly of cloned G-structures is an assembly of G-structures in the above sense, where
all structures in the assembly are isomorphic replicas of the same structure. Moreover, information about ‘homologous
vertices’ or ‘genetic similarity’ between each pair in the assembly is also provided. The structures of F ⊡ G have
some resemblance with the structures of the substitution F(G). An element of F ⊡ G can be represented as a cloned
assembly of G-structures together with an external F-structure (an F-assembly of cloned G-structures). Because
of the symmetry F ⊡ G = G ⊡ F this structures can also be represented as G-assemblies of cloned F-structures.
For example, if L+ denotes the species of non-empty lists, the structures of F ⊡ L+ could be thought of either as
F-assemblies of cloned lists, or as lists of cloned F-structures.

But I'm having a really hard time even understanding what is the notion of a "rectangle" that the authors employ to give to $\boxdot$ a combinatorial interpretation. I reason way better with coends and Kan extensions...

James Deikun (Dec 29 2023 at 23:27):

I can't access the article (CloudFlare is being even more difficult than usual with its "connection security check" which actually seems to be a browser insecurity check) but my guess is that a F ⊡ G structure on a set is something like an arrangement of the set into a literal rectangular grid with an F-structure on the rows and a G-structure on the columns.

James Deikun (Dec 29 2023 at 23:33):

So if you simply take the "structure of a set" for F and G, what you get is a set equipped with two cross-cutting partitions into sets of equal sizes--the intersection of one block from each partition is exactly one element.

James Deikun (Dec 29 2023 at 23:37):

If you take the "structure of a totally ordered set" for both F and G, what you get should be a totally ordered set equipped with a(n ordered) factorization of its size into two numbers.

fosco (Dec 29 2023 at 23:43):

the issue in downloading the paper is easily solved... How deep in hell will I end up if I attach a pdf here?

On-the-arithmetic-product-of-combinatorial-species.pdf

fosco (Dec 29 2023 at 23:46):

for what concerns the rest, I am in trouble deciphering what a "rectangle" is:

For a finite set U, we say that an ordered pair (π, τ ) of partitions of U is a partial rectangle on U when
$\pi\land\tau = \hat 0$.

I am already lost: what is $\land$? What is $\hat 0$?

James Deikun (Dec 29 2023 at 23:51):

They don't define $\hat{0}$ but if we assume they mean the partition that separates every element of the set, then it matches the pictures and a "rectangle" is the structure I mentioned above as Set ⊡ Set.

James Deikun (Dec 29 2023 at 23:52):

(And if we assume $\wedge$ is the common refinement of two partitions.)

James Deikun (Dec 29 2023 at 23:56):

So an ordered pair of partitions is a "partial rectangle" when they jointly shatter the set, and it is a "rectangle" if also every block from one partition meets every block from the other. The overall result is that you have an arrangement of the set into a rectangular grid, quotiented by permutations of rows and by permutations of columns.

James Deikun (Dec 29 2023 at 23:58):

They also define F ⊡ G the way I thought: you have a rectangle, an F-structure on the rows, and a G-structure on the columns.

James Deikun (Dec 30 2023 at 00:00):

The one difference is that they don't allow 0-row or 0-column rectangles, for retrospectively obvious reasons (sums would diverge when dealing with the empty set).

fosco (Dec 30 2023 at 00:06):

So, summing up:

• $\pi=[123|45|6],\tau=[14|25|36]$ is a partial rectangle, because the third element of $\pi$ has empty intersection with the first two of $\tau$
• $\pi=[123|456],\tau=[14|25|36]$ is a rectangle;
• $\pi=[123|45|6],\tau=[12|35|46]$ is neither.

fosco (Dec 30 2023 at 00:08):

For the partial rectangle $\pi=[123|45|6],\tau=[14|25|36]$, one can build a $3\times 3$ matrix, where if $\pi=[\pi_1|\pi_2|\pi_3]$ and $\tau=[\tau_1|\tau_2|\tau_3]$, one puts $\pi_i\cap \tau_j$ at the entry $(i,j)$

fosco (Dec 30 2023 at 00:09):

this matrix contains the only element in such intersection, if it's nonempty

fosco (Dec 30 2023 at 00:10):

as a consequence, for a proper rectangle, this arranges the elements of $\{1,\dots,6\}$ into a 3x2 rectangle

fosco (Dec 30 2023 at 00:11):

now I wonder why it's not explained like this :grinning: and why no one bothered to draw a better picture

fosco (Dec 30 2023 at 00:12):

Good, now I know what they are doing. Tomorrow I want to know what they are really doing :wink: what is the universal property of this monoidal structure?

James Deikun (Dec 30 2023 at 00:18):

I think taking the Cartesian product of sets as a monoidal product on the category of finite nonempty sets and bijections, you get this product as Day convolution.

fosco (Dec 30 2023 at 07:56):

James Deikun said:

I think taking the Cartesian product of sets as a monoidal product on the category of finite nonempty sets and bijections, you get this product as Day convolution.

Judging from what they write, it sounds right.

Whew, if it's that simple, I really wonder why they have to resort to such a contrived machinery, rectangles, Dirichlet products.. It's a Day convolution, totally obscured by the way the definition is given.

I'm glad I know category theory... :laughing:

Mike Shulman (Dec 30 2023 at 08:17):

The recent paper Monoidal Kleisli Bicategories and the Arithmetic Product of Coloured Symmetric Sequences by Gambino, Garner, and Vasilakopoulou studies this operation category-theoretically and extends it to "colored" species. Their starting point is, indeed, that it is Day convolution. They cite another paper "The Boardman-Vogt tensor product of operadic bimodules" by Dwyer and Hess as having rediscovered this operation (and presumably expressed it as Day convolution) in the context of "symmetric sequences" (which are equivalent to species), and a paper "Boardman–Vogt tensor products of absolutely free operads" by Bremner and Dotsenko as having noticed that the two are the same.

Mike Shulman (Dec 30 2023 at 08:18):

I think Day convolution is one of those things that must have been rediscovered dozens of times in the history of mathematics.

fosco (Dec 30 2023 at 08:36):

Very good (Nathanael posted an answer on mathoverflow recommending the same paper).

fosco (Dec 30 2023 at 09:08):

And now for an historical question: Mendez and Maia clearly know a bit of category theory. Day convolution was around at the time (even multiple times, I agree with you Mike). Day convolution is easier (and you gain something if you phrase things that way, for example, the monoidal product is closed).

Why did they not use it?!

fosco (Dec 30 2023 at 09:09):

Mike Shulman said:

I think Day convolution is one of those things that must have been rediscovered dozens of times in the history of mathematics.

Another example is somewhere around categories modeling spectra: it's just a Day convolution, did it really take that long to at least try phrasing things that way?

I think this comment might sound patronizing, which is not, I am just really fascinated by the sociology of mathematics, at the same time wondering how many blind spots do I have for dual reasons...

Mike Shulman (Dec 30 2023 at 09:10):

I have no actual idea and haven't even looked at the paper, but knowing "a bit" of category theory doesn't imply they knew about Day convolution. It doesn't tend to be covered in introductory courses or textbooks.

Mike Shulman (Dec 30 2023 at 09:17):

fosco said:

Another example is somewhere around categories modeling spectra: it's just a Day convolution

I assume you're talking about things like [[symmetric spectra]] and [[orthogonal spectra]]? In addition to ignorance of Day convolution, I think another reason those took so long is the sort of no-go argument in Lewis's 1991 paper Is there a convenient category of spectra?. People wanted a really nice category of spectra and found that was impossible, and it took a while to realize that you could give up just a bit of what you wanted and still get something really useful. I believe it was the more complicated approach of [[EKMM]] that made people realize this in principle, and after that conceptual barrier was broken, diagram spectra appeared fairly quickly.

fosco (Dec 30 2023 at 09:19):

Ah, I vaguely recall reading some historical account like that in Barnes-Roitzheim's "Foundations of stable homotopy"

John Baez (Dec 30 2023 at 14:20):

fosco said:

With sparse remarks here and there, the paper proves what boils down to the fact that the category of species has a symmetric monoidal structure given by $\boxdot$. The only thing is, usually Dirichlet series and their convolution are not defined in this way, but instead without the $\frac 1{n!}$. At any rate, it seems to me that with the appropriate substitution/transport of structure the monoidal category $(Species,+,\boxdot)$ can be regarded as a categorified version of the semiring of Dirichlet series with nonnegative integer coefficients.

My question is: is there a description of this monoidal structure that looks concise to a category theorist, or at least as concise as all other monoidal structures (Cartesian, Day convolution, substitution...) do? What is the universal property, if any, of the $\boxdot$ structure?

Yes, it's Day convolution with respect to the $\times$ monoidal structure on the groupoid of finite sets - that is, the monoidal structure that arises from restricting the cartesian product on the category of finite sets to this groupoid.

John Baez (Dec 30 2023 at 14:24):

For a lot more on this, see:

• John Baez and James Dolan, Dirichlet species and the Artin-Hasse zeta function.

John Baez (Dec 30 2023 at 14:25):

We show how this monoidal structure on species is related to the Riemann zeta function and other zeta functions.

John Baez (Dec 30 2023 at 14:27):

In particular we explain how those factors of 1/n! naturally take care of themselves.

John Baez (Dec 30 2023 at 14:28):

I also explained this so-called "Dirichlet" monoidal structure on the nLab article [[species]], but in less detail.

John Baez (Dec 30 2023 at 14:42):

Someone should prove that the 5 main monoidal structures on species arise from it being a '2-plethory', which is a monoidal category object in the 2-category of 2-birigs. @Joe Moeller , @Todd Trimble and I proved something very similar in the Vect-enriched case:

John Baez (Dec 30 2023 at 14:44):

• Schur functors and categorified plethysm.

Todd Trimble (Dec 30 2023 at 15:07):

The Dirichlet product is just different I think, not tied to the (2-)plethory structure we were exploring. It's more tied to the zeta function stuff you and James Dolan were exploring! (You'll be able to find the link more quickly than I can.)

John Baez (Dec 30 2023 at 15:15):

Ugh, you're right! We look at 2 monoidal structures on theccategory of Vect-valued species and 2 'comonoidal' structures, as well as the 'substitution' monoidal structure. But none of those bring in the Dirichlet or Hadamard monoidal structures! So the category of Vect-valued species is really even richer than a 2-plethory.

John Baez (Dec 30 2023 at 15:16):

And the category of ordinary species carries all these structures too!

Todd Trimble (Dec 30 2023 at 15:30):

The Hadamard product does have a role to play here in there in our studies, but Dirichlet is a whole other (and interesting) world.

Todd Trimble (Dec 30 2023 at 15:31):

For example, the Joyal "rule of signs" we invoke is a good example of a Hadamard product coming into view.

fosco (Dec 30 2023 at 15:53):

thanks to everyone

fosco (Dec 30 2023 at 15:53):

John Baez said:

• Schur functors and categorified plethysm.

I'm (a bit) familiar with this!

fosco (Dec 30 2023 at 16:08):

John Baez said:

For a lot more on this, see:

• John Baez and James Dolan, Dirichlet species and the Artin-Hasse zeta function.

this is also interesting (and I didn't know about it). Just one thing: Maia and Méndez observe that the Dirichlet series of the species of nonempty linear orders gives the $\zeta$ function, as well as the species on nonempty permutations (for obvious reasons) and (after they introduce the notion of a multiplicative species) also the Dirichlet series of the species of cyclic permutations (Example 25, eq. (88)) gives the zeta function, shifted by 1 and in the form of products of primes. You seem to use a different, more number-theoretic (with a functor of points), approach, to get to the same result, I was wondering how they are related.
And dropping a reference to Méndez, Maia might help other people, like me, that were googling the concept and are inclined to follow an nLab link more than other references.

fosco (Dec 30 2023 at 16:10):

I should be happy I had this vague idea to "consider the primes as atoms for the multiplicative monoids of nonzero naturals" instead of $[1]$ as a generator of the additive monoidal structure. Also that I was about to rediscover -or at least to ask- something that intrigued many other people as well.

John Baez (Dec 30 2023 at 18:11):

And dropping a reference to Méndez, Maia might help other people, like me, that were googling the concept and are inclined to follow an nLab link more than other references.

True. Of course we wrote our paper in 2012, before they wrote theirs, so really they should have cited us. :upside_down:

Todd Trimble (Dec 30 2023 at 18:17):

John Baez said:

Someone should prove that the 5 main monoidal structures on species arise from it being a '2-plethory', which is a monoidal category object in the 2-category of 2-birigs. Joe Moeller , Todd Trimble and I proved something very similar in the Vect-enriched case:

On the other hand, didn't you say (conjecture) once upon a time that the groupoid of finite sets equipped with both of these monoidal products (one by restriction of coproduct, the other by restriction of product) is the initial distributive category. Unfortunately I forget who proved that.

Todd Trimble (Dec 30 2023 at 18:17):

Anyway, it could be high time to consider how their Day convolutions interplay; I'm reminded here that David Spivak and others also study Dirichlet products in the context of polynomial functors.

Todd Trimble (Dec 30 2023 at 18:22):

(His polynomial functors, haha!)

John Baez (Dec 30 2023 at 18:23):

Todd Trimble said:

On the other hand, didn't you say (conjecture) once upon a time that the groupoid of finite sets equipped with both of these monoidal products (one by restriction of coproduct, the other by restriction of product) is the initial distributive category.

Yes, I did conjecture that, and this is discussed under the amusing name Baez's conjecture on the nLab.

Unfortunately I forget who proved that.

It was first proved incorrectly by Elgueta, then proved again by him - correctly I hope, but the proof is far from simple so I honestly don't know. It was later studied by some other authors listed on the nLab.

Nathanael Arkor (Dec 30 2023 at 18:54):

John Baez said:

And dropping a reference to Méndez, Maia might help other people, like me, that were googling the concept and are inclined to follow an nLab link more than other references.

True. Of course we wrote our paper in 2012, before they wrote theirs, so really they should have cited us. :upside_down:

(Just to clarify, the Maia–Méndez paper is from 2005.)

John Baez (Dec 30 2023 at 18:57):

Oh, sorry! I got mixed up. So yes, we should definitely cite them and they couldn't have cited us.

John Baez (Dec 30 2023 at 18:58):

I'll cite them now before I forget....

John Baez (Dec 30 2023 at 21:17):

Done!

Mike Shulman (Dec 30 2023 at 21:20):

The nLab page https://ncatlab.org/nlab/show/species#dirichlet_product could also benefit from the other citations mentioned in this thread.

David Michael Roberts (Dec 31 2023 at 01:38):

Fwiw Elgueta's paper is published in JPAA https://doi.org/10.1016/j.jpaa.2021.106738