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: analytic functor/finite sets

Jan Pax (Dec 13 2023 at 14:52):

Here I have the following question: what does mean the notation
$f \in F[n]$ on the page 10

so what do mean $f$ and $x_1,...,x_n$ here:
$(f,(x_1,...,x_n))$

So, from where to where f leads/goes and how it is defined ?
And where lives the equation

$(f,(x_1,...,x_n)) . \sigma = (f\cdot \sigma,(x_{\sigma(1)},...,x_{\sigma(n)}))$

Also, how did he computed the note on the page 10:
$f(x) = \sum f_n \frac{x^n}{n!}$
?

Finally, why has he chosen "/" in this notation
$\sum_{n\in\mathbb{N}} F[n] \times X^n / S_n$
Is it just notation that $S_n$ acts on $X^n$ without any literal meaning ?

I'd be happy if someone could shed some light into this matter.

John Baez (Dec 13 2023 at 15:06):

When I click on your link I get this message:

Website blocked due to riskware
Website Blocked: docdro.id

v2.6.16 | Riskware: 2.0.202312131448
Malwarebytes Browser Guard blocked this page because it may contain malicious activity.
Warning icon

We strongly recommend you do not continue. You may be putting your safety at risk by visiting this site. For more information, visit Malwarebytes Support.

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

So, I can't answer all your questions, but when people write something like $F[n] \times X^n/S_n$ they mean:

• the symmetric group $S_n$ acts on the set $F[n]$
• the symmetric group $S_n$ acts on $X^n$ by permuting the entries of an $n$-tuple in $X^n$
• so the symmetric group $S_n$ acts on $F[n] \times X^n$
• so we can take the quotient of the set $F[n] \times X^n$ by this group action and get a new set called $F[n] \times X^n/S_n$.

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

Maybe the thing you're missing is the idea of the quotient of a set by a group action. If a group $G$ acts on a set $X$, we use $X/G$ to denote the set of orbits, and we call $X/G$ the 'quotient' of $X$ by $G$.

Reid Barton (Dec 13 2023 at 15:45):

I'd assume the reason for the choice "/" specifically is, first of all, it does represent a kind of quotient operation, but mainly it's in order to suggest the analogy with the division (by $n!$, which corresponds to the group $S_n$) in the formula for the exponential generating function $\sum f_n \frac{x^n}{n!}$.

Jan Pax (Dec 13 2023 at 15:52):

Here is my new upload without bugs, I hope. The question is as it was before. $f \in F[n]$ on the page 10

so what do mean $f$ and $x_1,...,x_n$ here:
$(f,(x_1,...,x_n))$

So, from where to where f leads/goes and how it is defined ?
And where lives the equation

$(f,(x_1,...,x_n)) . \sigma = (f\cdot \sigma,(x_{\sigma(1)},...,x_{\sigma(n)}))$

Also, how did he computed the note on the page 10:
$f(x) = \sum f_n \frac{x^n}{n!}$
?

Todd Trimble (Dec 13 2023 at 16:35):

Here $f$ is just an element of the set $F[n]$ on which $S_n$ acts. It need not be a function.

In the note, he's pointing out an analogy between analytic functors and formal power series. The analogy can be made formally precise by saying there's a rig (i.e. semiring) homomorphism, from the rig of isomorphism classes of analytic functors (with addition induced by coproduct, and multiplication induced by this convolution product), to the rig of Mac Laurin series whose Mac Laurin coefficients $a_n$ (appearing in the term $a_n x^n/n!$) are natural numbers.

Todd Trimble (Dec 13 2023 at 17:59):

I forgot to say: the Mac Laurin coefficients $f_n$ on page 10 are the cardinalities $|F[n]|$.

Jan Pax (Dec 13 2023 at 22:30):

@Todd Trimble OK. What is $F[n]$ in general and what connection it has with $n$ ?

David Egolf (Dec 13 2023 at 22:50):

On page 9, we have $F: \mathbb{P} \to \mathsf{Set}$. This functor maps the object $n \in \mathbb{P}$ to the set $F[n]$, I believe. Note that the objects of $\mathbb{P}$ are the natural numbers.

I'm not sure if that helps clarify things!

Todd Trimble (Dec 13 2023 at 23:13):

David Egolf is correct. $F[n]$ is Joyal's preferred notation for a value of the species $F$ at an $n$-element set. Not sure how much you want to hear, but there's a pretty rich literature on species. In many applications, a species (short for "species of structure") gives the set of structures of some type (like a tree structure, or a structure of endofunction, or of a permutation, etc.) that are possible to endow a finite set with, and then permutations of that finite set, say of $\{1, \ldots, n\}$ will induce, by "transport of structure", an action of $S_n$ on the set of structures $F[n]$.

It's in French, but I think Joyal's original article is still one of the best places to start learning the theory of species. I'm sure others here would be happy to supply references that they like.

Jan Pax (Dec 13 2023 at 23:47):

@Todd Trimble I just wonder how have they created $f(x) = \sum f_n \frac{x^n}{n!}$ ?

Todd Trimble (Dec 14 2023 at 00:15):

I don't understand the question. They (meaning Gambino) just wrote it down! And I don't know what he said about it; I'm only seeing the slides.

Todd Trimble (Dec 14 2023 at 00:15):

But to give some search terms: that formal power series expression for $f(x)$ is often called the "exponential generating function", or egf, in cases where we take $f_n$ to be the number of structures of a certain type on an $n$-element set.

Todd Trimble (Dec 14 2023 at 00:15):

For example, in the case of possible ways of linearly ordering an $n$-element set -- the number of them is $n!$ -- the egf $\sum_{n \geq 0} n! \frac{x^n}{n!}$ is the power series for $\frac1{1-x}$. The number of possible necklace structures or cyclic orderings on an $n$-element set is $(n-1)!$, so there the egf is the power series for $-\log(1-x)$.

Todd Trimble (Dec 14 2023 at 00:15):

One good book for learning about egfs is Concrete Mathematics by Graham, Knuth, and Patashnik. Another, I'm told, is generatingfunctionology (I think that's the title).

Todd Trimble (Dec 14 2023 at 02:28):

Oh, I now see what may be puzzling you. There are two instances of the letter $f$ on page 10, but unless I'm totally confused (I don't think I am), those $f$'s are referring to totally different things!! The $f$ appearing on the right is an element of $F[n]$. The $f$ appearing on the left is an egf. Totally different!

Todd Trimble (Dec 14 2023 at 02:29):

That's an unfortunate clash of notation.

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

This free book may be easier than Joyal's paper:

• François Bergeron, Gilbert Labelle, and Pierre Leroux, Introduction to the Theory of Species of Structures.

Jan Pax (Dec 16 2023 at 17:31):

@Todd Trimble If $f$ is not a function but just an element of $F[n]$ what then does $f\cdot \sigma$ mean in $(f,(x_1,...,x_n)) . \sigma = (f\cdot \sigma,(x_{\sigma(1)},...,x_{\sigma(n)}))$ and where does this composition live ?

David Egolf (Dec 16 2023 at 17:47):

I'm not sure, but here's my guess in case it is helpful:

• I think $\sigma$ is an element of $S_n$, the symmetric group on $n$ elements. That means that $\sigma: n \to n$ is an endomorphism of $n$ in $\mathbb{P}$.
• The functor $F: \mathbb{P} \to \mathsf{Set}$ then provides $F(\sigma): F[n] \to F[n]$. $F$ provides this information for each $\sigma \in S_n$, so I think $F$ is telling us how $S_n$ acts on $F[n]$.

David Egolf (Dec 16 2023 at 17:50):

• Consequently, I am guessing that $f \cdot \sigma$ refers to $F(\sigma)(f) \in F[n]$.

Todd Trimble (Dec 16 2023 at 18:21):

David is correct. (I personally would write $F: \mathbb{P}^{op} \to \mathsf{Set}$ for a right action, but it doesn't make much difference here since a groupoid like $\mathbb{P}$ is isomorphic to its opposite.)

Todd Trimble (Dec 16 2023 at 18:27):

This by the way is not uncommon notation. In group representation theory, a left action of a group $G$ on a vector space $V$ is commonly denoted using notation like $g \cdot v$. What is really meant of course, if the representation is given by a monoid homomorphism $\phi: G \to \hom(V, V)$, is $\phi(g)(v)$. Here we are just extrapolating this notation from the case of a 1-object category (like a group or monoid) to the case of a category with many objects, like $\mathbb{P}$.

John Baez (Dec 16 2023 at 22:39):

$F[n]$ is a set with a right action of $S_n$, so when we have $f \in F[n]$ and $\sigma \in S_n$, then $\sigma$ can act on the right giving a new element that someone decided to call $f \cdot \sigma$.

John Baez (Dec 16 2023 at 22:39):

All this is a pretty standard way to talk.