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: Free monoid in species

fosco (Dec 31 2023 at 13:24):

I am a bit confused about a fact on combinatorial species. As usual, a species is a functor $B\to Set$, where $B$ is the category of finite sets and bijections.

Let $y[n]$ be the representable functor $B\to Set$; it acts on objects sending $[n]\in B$ to the symmetric group $S_n$ and all other objects to the empty set. On morphisms (=permutations of $[n]$) it acts through the regular representation of $S_n$ on itself, multiplying on the left. See example 2.3 in Adámek's "Analytic functors and weak pullbacks".

I am interested in studying the free monoid on $y[1]$, with respect to Day convolution. $\ast$. Such free monoid is the sum of all representables, given the properties of Day convolution:

$\sum_n y[1]^{* n} = \sum_n y[1+\dots+1] = \sum_n y[n]$

fosco (Dec 31 2023 at 13:26):

So, it seems to me the free monoid on y[1] is the species of permutations, as defined again in Adámek, example 2.3 who by the way also observes that it arises as "the coproduct of those in (i)", where those in (i) were the representables.

fosco (Dec 31 2023 at 13:27):

Now, by contrast, consider Aguiar and Mahajan's book; page 251 observes that the free monoid on one generator is, instead, the species of linear orders
image.png
(this appears just below eqn. (8.31))

fosco (Dec 31 2023 at 13:30):

I am confused: the species of linear orders and the species of permutation are the prototype of two species who give rise to the same generating power series (as $|L[n]|=|S[n]| = n!$) but they are not isomorphic as species.

So, who is the free monoid on one generator? Does it make a difference that Adamek works with Set-species and Aguiar-Mahajan use linear species?

James Deikun (Dec 31 2023 at 13:53):

ISTM this is indeed the species of linear orders since the species of permutations would have the adjoint action of $\mathfrak{S}_n$.

fosco (Dec 31 2023 at 13:55):

I don't see how to reconcile Adamek's claim then

fosco (Dec 31 2023 at 13:55):

he speaks clearly of the coproduct of all representables

fosco (Dec 31 2023 at 13:56):

James Deikun said:

ISTM this is indeed the species of linear orders since the species of permutations would have the adjoint action of $\mathfrak{S}_n$.

I guess you say this by Yoneda, since representables from a (disjoint union of) group(s) act by conjugation, no?

James Deikun (Dec 31 2023 at 13:58):

Yes. I think Adamek is just calling linear orders permutations. Nothing in his argument really seems to depend on the naming.

fosco (Dec 31 2023 at 13:59):

James Deikun said:

Yes. I think Adamek is just calling linear orders permutations.

who does that?!

James Deikun (Dec 31 2023 at 14:01):

I don't know what to tell you. It's the only explanation I can come up with.

fosco (Dec 31 2023 at 14:04):

well. Let's be rational. Clearly just one of them can be the free monoid on y[1]; if a monoid homomorphism out of $S$ (which is certainly a Day monoid) isn't determined by y[1] it can't be the free monoid

James Deikun (Dec 31 2023 at 14:09):

I suppose if you consider the elements of $B$ as finite ordered sets with a symmetric group action rather than as finite sets with their isomorphisms then linear orders look like "permutations". I don't know what you call the actual permutations then though.

James Deikun (Dec 31 2023 at 14:12):

And also if you're looking at the objects in $\mathsf{Set}$ that come from the images of the representables they are literally sets of permutations. It's just not what a combinatorist would call the species of permutations.

fosco (Dec 31 2023 at 14:13):

I think this kind of back-engineering on nomenclature is incredibly contrived and there must be a simple explanation. I think if one takes for granted that S and L are not isomorphic (although I'd like to see a clean categorical argument: "Tree-like structures" relies on the difference between the type generating series of S and L to deduce they are not isomorphic)

fosco (Dec 31 2023 at 14:13):

then one can argue with the universal property that only one will satisfy.

James Deikun (Dec 31 2023 at 14:15):

The reason I'm back-engineering Adamek's nomenclature rather than Aguiar and Mahajan's is that I've already been convinced by the universal property of the linear orders.

fosco (Dec 31 2023 at 14:16):

James Deikun said:

And also if you're looking at the objects in $\mathsf{Set}$ that come from the images of the representables they are literally sets of permutations. It's just not what a combinatorist would call the species of permutations.

I am probably being dense but I don't understand this remark. I think I agree that the species of permutations sends [n] to S_n and acts with the adjoint representation, and the conceptual reason appeasing my category-pilled brain is that a $\times$-group (i.e. an internal group with respect to the Cartesian monoidal structure) must be a species valued in groups and group homomorphisms. Hence the action of $\tau\in S_n$ on S_n must be via group automorphisms, not just set functions. Hence conjugation; plus there is the argument that uses Yoneda.

fosco (Dec 31 2023 at 14:19):

James Deikun said:

The reason I'm back-engineering Adamek's nomenclature rather than Aguiar and Mahajan's is that I've already been convinced by the universal property of the linear orders.

Can you point me to the convincing argument or reproduce it here? I guess a definitive argument might be this: find another Day-monoid, and a monoid homomorphism $S\to M$ that is not uniquely determined by an element in $M[1]$ (I'm using the adjunction isomorphism $Species(y[1],UM)\cong Mon(Species)(y[1]^\star,M)$)

James Deikun (Dec 31 2023 at 14:21):

The remark refers to a fact that a "permutation" is usually defined as an automorphism of a set. So with non-structural-set-theorist brain turned on, you can say the coproduct of all representables picks out exactly the set of all permutations of each standard finite set, although the assigned action does not respect their group structure.

fosco (Dec 31 2023 at 14:22):

You're confusing me, but I think it's my fault. I'm slow at this.

fosco (Dec 31 2023 at 14:25):

First problem that I have is this.

What exactly is the reason why S and L are not isomorphic? That the family of bijections between S[n] and L[n] isn't natural for all [n]? Is it unnatural at all n, or does one need to go further than small values of n? I am surprised one needs a lot of artillery to show that two functors are not isomorphic.

fosco (Dec 31 2023 at 14:27):

Second problem I have is with nomenclature, which led me to open this thread. But I don't want to get philosophical, I prefer to prove a theorem.

At the best of our current knowledge, this must be true: the set of monoid homomorphisms $Mon(Species)(S,M)$ is not in bijection with $M[1]$ for all Day monoids in species, naturally in M

Would taking M=L work?

James Deikun (Dec 31 2023 at 14:29):

The permutations (with their natural, adjoint action) can't form a free monoid under the Day convolution product you're using since the adjoint action of $\mathfrak{S}_2$ on itself is different from its action on $\mathfrak{S}_1 + \mathfrak{S}_1$. The former is trivial, the latter isn't.

fosco (Dec 31 2023 at 14:31):

is + a typo for $\times$?

James Deikun (Dec 31 2023 at 14:34):

Actually I guess it's a typo for $*$.

fosco (Dec 31 2023 at 14:37):

then I understand even less. The conjugation action on S_2 is trivial because S_2 is abelian. The conjugation action on S_1 is trivial because the group is trivial, and now what is $\ast$? Day convolution?

$\ast$ is an operation between species, not between groups

Todd Trimble (Dec 31 2023 at 14:39):

You can see the species of linear orders and the species of permutations are not isomorphic because $S_n$ acts transitively on $L[n]$ but not on $P[n]$. (You could identify both with the set $S_n$, but in the former, $S_n$ acts by left translation; in the latter, $S_n$ acts by conjugation.)

The conjugate of a permutation will be another permutation of the same cycle type, and so the action on permutations cannot possibly be transitive. This shows up already for $n = 2$.

James Deikun (Dec 31 2023 at 14:40):

Yes. I am abusing notation to refer by $\mathfrak{S}_n$ to both the group of permutations on an n-element set and the species of "permutations on an n-element set". Conjugation on $\mathfrak{S}_2$ is trivial because the group is trivial; the action of $\mathfrak{S}_2$ (the group) on (the only nontrivial sort of) the species $\mathfrak{S}_1 * \mathfrak{S}_1$ is nontrivial because while it acts trivially within each of the copies, it also exchanges the copies.

fosco (Dec 31 2023 at 14:41):

Todd, let's see if I understand your argument: the argument you're using here is that two isomorphic species must be isomorphic as symmetric sequences, so degreewise isomorphic as left $S_n$-sets, and this is not the case for S and L, so they can't be isomorphic.

If this rewording of your claim is correct, this settles it.

Todd Trimble (Dec 31 2023 at 14:42):

Anyway, James is perfectly correct that it's $L[n]$ that is the "tensor algebra" = free monoid.

I suppose Adamek was not thinking about structure types when he was giving names, but I'd be inclined to forgive him and assume that he knows this distinction.

Chris Grossack (they/them) (Dec 31 2023 at 14:43):

fosco said:

First problem that I have is this.

What exactly is the reason why S and L are not isomorphic? That the family of bijections between S[n] and L[n] isn't natural for all [n]? Is it unnatural at all n, or does one need to go further than small values of n? I am surprised one needs a lot of artillery to show that two functors are not isomorphic.

You should think of L as a kind of "torsor" or "affine space" for S. To see why, ask yourself "which linear order should be identified with the identity permutation?" there's no canonical choice, you have to just choose one. Of course, once you've chosen a linear order to be the identity, you can permute that linear order in the obvious way to get all the other linear orders too.

Using this it shouldn't be hard to show that the isomorphism you build isn't natural, even for $n=2$, since a choice was made. I would write it down and include it here, but I'm currently typing this from my phone on my way to see a friend.

fosco (Dec 31 2023 at 14:43):

I mean, I'm not angry at Adamek, how could I? I just want to understand...

fosco (Dec 31 2023 at 14:45):

Chris Grossack (they/them) said:

fosco said:

First problem that I have is this.

What exactly is the reason why S and L are not isomorphic? That the family of bijections between S[n] and L[n] isn't natural for all [n]? Is it unnatural at all n, or does one need to go further than small values of n? I am surprised one needs a lot of artillery to show that two functors are not isomorphic.

You should think of L as a kind of "torsor" or "affine space" for S. To see why, ask yourself "which linear order should be identified with the identity permutation?" there's no canonical choice, you have to just choose one. Of course, once you've chosen a linear order to be the identity, you can permute that linear order in the obvious way to get all the other linear orders too.

Using this it shouldn't be hard to show that the isomorphism you build isn't natural, even for $n=2$, since a choice was made. I would write it down and include it here, but I'm currently typing this from my phone on my way to see a friend.

Ah, ok, I like this point of view.

Todd Trimble (Dec 31 2023 at 14:45):

fosco said:

Todd: the argument you're using here is that two isomorphic species must be isomorphic as symmetric sequences, so degreewise isomorphic as left $S_n$-sets, and this is not the case

I don't know what you're trying to say. The category of species is equivalent to the product $\prod_n Set^{S_n}$.

fosco (Dec 31 2023 at 14:46):

that's what I'm trying to say: isomorphic species would become isomorphic objects in $\prod Set^{S_n}$.

Todd Trimble (Dec 31 2023 at 14:46):

And so what do you claim I'm saying wrong?

fosco (Dec 31 2023 at 14:46):

Ah, but no, I agree with you, I was rewording it.

James Deikun (Dec 31 2023 at 14:46):

I think he's not saying that the premise of your argument is not the case, he's saying that part of your argument is that the premise of the premise of your argument is not the case.

fosco (Dec 31 2023 at 14:47):

S and L are not isomorphic as symmetric sequences, hence not isomorphic as species

Todd Trimble (Dec 31 2023 at 14:47):

James, I can't follow this, and anyway I have to leave. It's been real.

fosco (Dec 31 2023 at 14:48):

downsides of answering to three people at the same time, I lost a piece of message. Will edit

James Deikun (Dec 31 2023 at 14:49):

IOW: you're not saying something that is not the case, you're saying that something is not the case.

fosco (Dec 31 2023 at 14:50):

:grinning: what a mess has been this last string of messages!

fosco (Dec 31 2023 at 14:53):

Todd, for when you come back: I agree with you, and this proof is clear to me, the take-home is, if on two species that have degreewise the same cardinality, the actions of S_n are different, they can't be isomorphic as species.

I really wonder how can it be that people doing combinatorics find "discrepancy of cycle-index series" a more compelling argument for $S\not\cong L$ than this other simple argument.. brains really are very different.

Chris Grossack (they/them) (Dec 31 2023 at 15:03):

If I'm not making an easy mistake, I think the cycle index proof and the $\mathfrak{S}_n$ action proof are "basically the same". After all, you build the cycle index polynomial by consulting the $\mathfrak{S}_n$-action. I wouldn't be surprised if someone who has spent a lot of time with cycle index polynomials can "short circuit" the whole computation by just recognizing the $\mathfrak{S}_n$-actions are different, and concluding that the cycle index polynomials would be too.

fosco (Dec 31 2023 at 15:08):

Yes, I was about to say that in hindsight, the cycle-index series is just a refinement of the generating series that takes into account the $S_n$-set structure. After all we're talking about the same thing

fosco (Dec 31 2023 at 15:09):

Anyway. Very good. Now this is settled.

The next question is: is there a literature about the category of $L$-algebras? By an $L$-algebra I mean equivalently an object of:

• the Eilenberg-Moore category of the monad $L*-$
• the category of endofunctor algebras $y[1] * -$

(they are equivalent, by the aforementioned freeness of L)

Todd Trimble (Dec 31 2023 at 17:37):

fosco said:

Todd, for when you come back: I agree with you, and this proof is clear to me, the take-home is, if on two species that have degreewise the same cardinality, the actions of S_n are different, they can't be isomorphic as species.

I really wonder how can it be that people doing combinatorics find "discrepancy of cycle-index series" a more compelling argument for $S\not\cong L$ than this other simple argument.. brains really are very different.

Not to beat a dead horse, but about "really wonder" (with emphasis even!): I have in my head pictures of combinatorial structures. A linear order, you know, a chain of arrows in a straight line, is palpably different from a disjoint union of cycles where arrows loop around in each cycle, and that picture is pretty compelling to me. Any two linear orders on an n-element set are isomorphic, are "the same" in that sense, hence the transitivity of the action. On the other hand, you have lots of different cycle types; they are not all the same. Isn't that pretty easy?

fosco (Dec 31 2023 at 17:54):

wordcels and shape rotators, algebraists and geometers... :grinning:

(I agree it's easy. But somehow I keep discovering that thinking in an easy way requires a lifetime of training)

Todd Trimble (Dec 31 2023 at 22:13):

In answer to your last question: an $L$-module $L \otimes F \to F$ (I'm using $\otimes$ for the Day convolution, not $\ast$, as the former is standard in the species community) is the same thing as a monoid map

$L \to [F, F]$

where of course $[F, F]$ denotes internal hom, adjoint to $\otimes$ in the usual sense. But since $L$ is the free monoid generated by $y[1]$, such a structure is tantamount to a species map $y[1] \to [F, F]$, or likewise to a species map $y[1] \otimes F \to F$, or what a species-theorist might denote as $x \otimes F \to F$.

Todd Trimble (Dec 31 2023 at 22:13):

A structure in

$(x \otimes F)[S]$

for a finite set $S$ consists of a choice of point in $S$ together with a structure of type $F$ on the complement of that point.

Todd Trimble (Dec 31 2023 at 22:13):

Funnily enough, could could also view such a map $x \otimes F \to F$ as tantamount to a map $F \to DF$, a coalgebra structure over the derivative endofunctor $D$ on species, insofar as we have $DF = [x, F]$.

Todd Trimble (Dec 31 2023 at 22:13):

Seems like a potentially fun thing to contemplate...

fosco (Dec 31 2023 at 22:25):

Todd Trimble said:

Seems like a potentially fun thing to contemplate...

I am in the process to contemplate it, indeed. ;-)

fosco (Dec 31 2023 at 22:27):

Todd Trimble said:

In answer to your last question: an $L$-module $L \otimes F \to F$ (I'm using $\otimes$ for the Day convolution, not $\ast$, as the former is standard in the species community) is the same thing as a monoid map

$L \to [F, F]$

where of course $[F, F]$ denotes internal hom, adjoint to $\otimes$ in the usual sense. But since $L$ is the free monoid generated by $y[1]$, such a structure is tantamount to a species map $y[1] \to [F, F]$, or likewise to a species map $y[1] \otimes F \to F$, or what a species-theorist might denote as $x \otimes F \to F$.

Yes, in hindsight this was totally obvious, it is true for every action monad, and it's precisely what I wanted. Thanks a lot! and well, it's earlier than midnight on the east coast, but: happy 2024, which up here :flag_estonia: just started!

fosco (Dec 31 2023 at 22:49):

I guess the upshot is that coalgebras for $D$ are essentially endomorphisms of species with their iterates. I started from the analogy that regards discrete dynamical systems as algebras for the action monad $\mathbb N \times -$, i.e. sets with an endomorphism.

fosco (Dec 31 2023 at 22:51):

It seems that, as I expected, and for a stupid reason in hindsight, the analogy holds as the categories of L-algebras I mentioned are equivalent, and there is one more: coEilenberg-Moore for $\{L,-\}$.

Todd Trimble (Dec 31 2023 at 23:18):

Happy New Year!

Todd Trimble (Dec 31 2023 at 23:18):

There is one more thing I want to point out: the underlying functor of the monad $L \otimes -$ has a right adjoint, $[L, -]$. In this situation, where a monad is a left adjoint, its right adjoint automatically carries a comonad structure which is mated to the original monad structure, and moreover, the Eilenberg-Moore category for $L \otimes -$ is equivalent to the co-Eilenberg-Moore category for the comonad $[L, -]$. We now recognize that this co-EM category of comonad coalgebras $[L, -]$ is equivalent to the category of coalgebras for the endofunctor $D$.

Todd Trimble (Dec 31 2023 at 23:19):

But more importantly (in my mind): this situation is analogous to the concept of plethory. Traditionally, a plethory can be regarded as a representable comonad on the category of commutative rings, or in other words as a right adjoint comonad on the category of commutative rings. More generally, there's such a thing as a Tall-Wraith monoid which generalizes the concept of plethory: for any Lawvere theory $T$, a Tall-Wraith monoid can be identified with a left adjoint monad on the category of $T$-algebras, or equivalently as a right adjoint comonad on $Set^T$.

Todd Trimble (Dec 31 2023 at 23:19):

This time we have a right adjoint comonad on species $Set^{\mathbb{P}}$, so we are in the midst of a plethory-like structure.

Todd Trimble (Dec 31 2023 at 23:19):

That's all I'll say for the moment. ;-)