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: deprecated: chemistry

Topic: open Petri net questions

Sam Tenka (Jun 05 2022 at 16:50):

@Benjamin Merlin Bumpus @Sophie Libkind @Layla @Jordy Lopez Garcia your group proved John's additivity conjecture! You also posed a next conjecture / question --- could you state it here? If your powerful brains haven't already figured it out, I'd probably enjoy working at it, too. And if it already is figured out, I'd enjoy learning it!

John Baez (Jun 06 2022 at 04:31):

I stated another question... and later I also remembered a deeper conjecture, something I've been meaning to prove for a while now.

John Baez (Jun 06 2022 at 04:33):

Here's the one I stated.

John Baez (Jun 06 2022 at 04:35):

First, remember that there's a category $\mathsf{Open}(\mathsf{Petri})$ of open Petri nets, a decorated cospan category where the objects are finite sets and a morphism is an open Petri net, meaning a cospan of finite sets

$A \xrightarrow{i} S \xleftarrow{o} B$

together with a Petri net

$s, t: T \to \mathbb{N}[S]$

John Baez (Jun 06 2022 at 04:46):

(Actually this is a lie: a morphism is really an isomorphism class of open Petri nets; this is explained in various papers of mine, but I can also explain it here if asked.)

John Baez (Jun 06 2022 at 04:48):

Now, the original conjecture which some folks at the AMS MRC apparently actually proved was a complete classification of functors

$F : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

where $\mathsf{B} \mathbb{N}$ is the category with one object and natural numbers as morphisms, composition being addition of natural numbers.

John Baez (Jun 06 2022 at 04:49):

I'm too lazy to restate the classification until someone actually asks, but briefly it says every such functor $F$ is a finite sum of functors of a very specific sort, called

$F_{m,n} : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

which count the transitions of various kinds (depending on two natural numbers $m, n$).

John Baez (Jun 06 2022 at 04:54):

Moreover every such finite sum gives a functor

$F : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

So, these functors are completely understood. And they're important because, intuitively speaking, they are the "additive invariants of open Petri nets".

John Baez (Jun 06 2022 at 04:55):

(Invariants taking natural numbers as values, I mean.)

John Baez (Jun 06 2022 at 04:56):

Now for the next question! There's a subcategory of $\mathsf{Open}(\mathsf{Petri})$ consisting of (isomorphism classes of) open Petri nets

John Baez (Jun 06 2022 at 04:57):

$A \xrightarrow{i} S \xleftarrow{o} B,$

$s, t: T \to \mathbb{N}[S]$

such that the functions $i, o$ are monic.

John Baez (Jun 06 2022 at 04:58):

Let's call this subcategory $\mathsf{Mon}(\mathsf{Petri})$, at least until we come up with a better name.

John Baez (Jun 06 2022 at 05:00):

The question is, what are all the functors

John Baez (Jun 06 2022 at 05:01):

$F : \mathsf{Mon}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$ ?

John Baez (Jun 06 2022 at 05:04):

All the finite sums functors $F_{m,n}$ restrict from $\mathsf{Open}(\mathsf{Petri})$ to $\mathsf{Mon}(\mathsf{Petri})$, of course, and this restriction process is one-to-one (I claim), so the classification we had before is part of the classification we want.

John Baez (Jun 06 2022 at 05:05):

However, I believe there are a few other new functors

$F : \mathsf{Mon}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

John Baez (Jun 06 2022 at 05:06):

and then of course sums of these - and sums of these with the ones we had already, that are sums of those of the type $F_{m,n}$.

John Baez (Jun 06 2022 at 05:26):

I think there are just a few other "essentially new" ones.

John Baez (Jun 06 2022 at 05:28):

I'm happy to answer questions about anything here; I know this account may seem a bit mysterious since I didn't explain everything in detail, but filling in every single detail would have been pretty long and I hope at least the general outline of what I'm up to is apparent.

Sam Tenka (Jun 06 2022 at 15:18):

I'll try to work on this after grad school work today (5pm eastern is my self-imposed time). Anyone wanna join me, e.g. in a video call?

John Baez (Jun 06 2022 at 23:01):

The people who are "supposed" to be working on this question are those in @Sophie Libkind's group.

John Baez (Jun 06 2022 at 23:02):

They include @Layla, @Jordy Lopez Garcia, @Benjamin Merlin Bumpus, and maybe other folks I'm forgetting.

John Baez (Jun 06 2022 at 23:03):

So I think you should organize meetings with them... or they should organize meetings with you!

John Baez (Jun 06 2022 at 23:06):

Of course you can also just dive in and think about this. But they plan to write and publish a paper on my first conjecture and maybe this particular followup question, so if you work on this it'd be best to cooperate with them... or at least expect that any paper winds up including them as coauthors.

(Having written lots of papers, I find that friction is reduced if issues of "who is a coauthor" get settled soon. I know it sounds bureaucratic, but it prevents people from being disappointed because they expected to be coauthors and weren't.)

John Baez (Jun 06 2022 at 23:06):

I don't really have time today to talk about this puzzle in real time on a video call, but if you have any questions, like what is the question exactly?, I'd be really glad to answer them here.

John Baez (Jun 06 2022 at 23:07):

I would also sometime like to meet "all of Sophie's group", including you if you want, and say a bit more about this.

Sam Tenka (Jun 06 2022 at 23:26):

John Baez said:

Of course you can also just dive in and think about this. But they plan to write and publish a paper on my first conjecture and maybe this particular followup question, so if you work on this it'd be best to cooperate with them... or at least expect that any paper winds up including them as coauthors.

(Having written lots of papers, I find that friction is reduced if issues of "who is a coauthor" get settled soon. I know it sounds bureaucratic, but it prevents people from being disappointed because they expected to be coauthors and weren't.)

@Sophie Libkind 's group: I'd love to join your discussions if possible! Also, if I end up contributing math insight that you all think is substantive to the second conjecture's resolution, may I be a coauthor on a future paper discussing that conjecture? I didn't help at all with the first conjecture, so I think it would make sense for me not to a coauthor otherwise. What do you think?)

Benjamin Merlin Bumpus (he/him) (Jun 07 2022 at 11:59):

hi :wave:🏻, I’m currently on holiday, but I’ll be back in action next week, so maybe we can discuss it then. we already made some progress on John’s second conjecture, so it probably makes sense for all of us to chat next week

Jordy Lopez Garcia (Jun 07 2022 at 13:01):

Howdy! Sounds good! Maybe I can make a Doodle poll and see when we can all meet?

John Baez (Jun 08 2022 at 15:30):

Go for it! If you understand the conjectures and want to work on them, I may not need to be there. (I'm not imagining myself as a coauthor here.) I have another conjecture that's considerably deeper, which I could explain sometime, but maybe you've got enough to do.

Layla (Jun 09 2022 at 01:38):

John Baez said:

$A \xrightarrow{i} S \xleftarrow{o} B,$

$s, t: T \to \mathbb{N}[S]$

such that the functions $s, t$ are monic.

In the SubCategory Mon(OPerti), there are no conditions on the legs?

John Baez (Jun 09 2022 at 05:01):

Layla said:

John Baez said:

$A \xrightarrow{i} S \xleftarrow{o} B,$

$s, t: T \to \mathbb{N}[S]$

such that the functions $s, t$ are monic.

In the subcategory $\mathsf{Mon}(\mathsf{Petri})$, there are no conditions on the legs?

Sorry, that was a typo. I meant to require that $i$ and $o$ are monic, not $s$ and $t$. So, yes, the condition is that the legs of the cospan are monic!

John Baez (Jun 09 2022 at 05:01):

I'll fix this in my earlier comment so I don't confuse people more....

Layla (Jun 09 2022 at 14:12):

Thanks ..

Sam Tenka (Jun 09 2022 at 18:37):

Jordy Lopez Garcia said:

Howdy! Sounds good! Maybe I can make a Doodle poll and see when we can all meet?

happy to do doodle poll (if it's okay for me to join)!

Jordy Lopez Garcia (Jun 09 2022 at 23:00):

@Sam Tenka I will add you to the subgroup where we have the poll :)!

John Baez (Jun 13 2022 at 23:33):

Elsewhere @Sam Tenka wrote:

John Baez (Jun 13 2022 at 23:34):

Just a microscopic note: John Baez's set does not generate the abelian monoid of functors from open petri, since infinitary sum and infinitary product disagree. This is something that is obvious to y'all but that is probably good to write carefully.

John Baez (Jun 13 2022 at 23:35):

Let me just explain this correction to my original conjecture.

John Baez (Jun 13 2022 at 23:37):

I had written my conjecture like this:

Every functor

$F : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

is a finite sum of functors of a very specific sort, called

$F_{m,n} : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

which count the transitions of various kinds (depending on two natural numbers $m, n$.

John Baez (Jun 13 2022 at 23:39):

Sam is saying that the finite sum part is wrong. For example, there's a functor

$G : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

that simply maps each open Petri net to the total number of transitions in this open Petri net.

John Baez (Jun 13 2022 at 23:39):

We have

$G = \sum_{m,n \in \mathbb{N}} F_{m,n}$

but this is not a finite sum.

John Baez (Jun 13 2022 at 23:41):

So, we have to state the conjecture more precisely, especially since not every infinite sum of functors $F_{m,n}$ is even well-defined. We need to allow infinite sums, but only infinite sums that converge in a certain sense.

John Baez (Jun 13 2022 at 23:43):

Namely, we need to allow infinite sums of the form

$\sum_{m,n \in \mathbb{N}} a_{m,n} F_{m,n}$

where $a_{m,n}$ are natural numbers and the sum

$\sum_{m,n \in \mathbb{N}} a_{m,n} F_{m,n}(f)$

converges for each morphism $f$. Here 'converges' means this: each $a_{m,n} F_{m,n}(f)$ is a natural number, and we want the sum of these natural numbers to be finite, not infinite.

John Baez (Jun 13 2022 at 23:43):

There are other ways to say this stuff, but I hope this is reasonably clear.

John Baez (Jun 13 2022 at 23:45):

After the notion of "convergent sum of functors to $B\mathbb{N}$" has been defined, we can state a corrected version of the conjecture as follows:

Every functor

$F : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

is a convergent sum of functors of a very specific sort, called

$F_{m,n} : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

which count the transitions of various kinds (depending on two natural numbers $m, n$.

Sam Tenka (Jun 14 2022 at 03:09):

John Baez said:

After the notion of "convergent sum of functors to $B\mathbb{N}$" has been defined, we can state a corrected version of the conjecture as follows:

Every functor

$F : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

is a convergent sum of functors of a very specific sort, called

$F_{m,n} : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

which count the transitions of various kinds (depending on two natural numbers $m, n$.

@John Baez If I'm not mistaken ${\color{red}^\dagger}$, then we here can use the finitude of each $f$ (as fancy graph) to further simplify reasoning about convergence: for each $f$, all but finitely many $F_{m,n}$ evaluate at $f$ to zero. So we have pointwise convergence for free. Because of this, it's enough to replace "direct sum" by "direct product" in your original conjecture. My preference ${\color{red}^\circ}$ is to say the same thing in yet another way: the abelian monoid we seek is the dual (with dualizing object $\mathbb{N}$) abelian monoid of the direct sum you conjectured.

${\color{red}^\circ}$ p.s. --- I prefer this for the same reason that in rep theory the regular representation $\mathbb{C}[G]$ and the function space $\mathbb{C}^G$ are (for finite $G$) "the same" due to our god-given basis ($G$ as a set), but they have different (covariant vs contravariant) mental flavors.

${\color{red}^\dagger}$ p.(p.s.) --- many authors who consider this case forget to consider the complementary case. I follow their tradition.

John Baez (Jun 14 2022 at 05:03):

All these remarks are great, @Sam Tenka. I agree wholeheartedly.

John Baez (Jun 14 2022 at 05:04):

An implication of what you're saying is that with the notion of convergence I gave back here, every infinite sum

John Baez (Jun 14 2022 at 05:05):

$\sum_{m,n \in \mathbb{N}} a_{m,n} F_{m,n}$

where $a_{m,n}$ are natural numbers converges!

John Baez (Jun 14 2022 at 05:09):

So I can state the conjecture this way

Every functor

$F : \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B} \mathbb{N}$

is of the form

$\sum_{m,n} a_{m,n} F_{m,n}$

for some natural numbers $a_{m,n}$, where $F_{m,n}$ is the functor that counts transitions with $m$ inputs and $n$ outputs.

John Baez (Jun 14 2022 at 05:12):

But I like your way of thinking about it.

Conjecture. The commutative monoid of functors $F: \mathsf{Open}(\mathsf{Petri}) \to \mathsf{B}\mathbb{N}$, with pointwise addition as the monoid operation, is isomorphic to $\mathbb{N}^{\mathbb{N}\times\mathbb{N}}$, where the isomorphism sends any function $a \in \mathbb{N}^{\mathbb{N}\times\mathbb{N}}$ to the functor

$\sum_{m,n \in \mathbb{N}} a_{m,n} F_{m,n}$

John Baez (Jun 14 2022 at 05:16):

And the isomorphism sends a function $a \in \mathbb{N}^{\mathbb{N}\times\mathbb{N}}$ to the functor

$\sum_{m,n \in \mathbb{N}} a_{m,n} F_{m,n}$

Sam Tenka (Jun 14 2022 at 05:53):

@John Baez thanks for the encouraging words!

I'm a bit confused about the conjecture --- doesn't it follow directly from Ben&Sophie&Layla&Jordy's proof?

Their proof shows how to start with a functor $F$ and present it as an infinite sum --- we just get $a_{m,n}$ by evaluating $F$ on a petri net with a single transition. Meanwhile, we can go the other way --- from $a$ to $F$ --- using the summation you wrote; it'll always converge as noted above. Going from $a$ to $F$ back to $a$ gives the identity on $\mathbb{N}^{\mathbb{N}\times \mathbb{N}}$, by construction. The other round trip --- from $F$ to $a$ back to $F$ --- gives the identity by the Jordy/Layla/Sophie/Ben theorem, which says that a functor's action on each single-transition net determines the functor itself. So we have a bijection between monoids; that this bijection is an isomorphism of monoids follows by "distributivity" of infinite sums, which follows because we have "absolute convergence". Less metaphorically, distributivity follows again because each graph is finite.

John Baez (Jun 14 2022 at 05:55):

I haven't really read a write-up of Ben&Sophie&Layla&Jordy's proof.

Sam Tenka (Jun 14 2022 at 05:56):

@John Baez me neither but I believe it since Jordy et al explained it to me.
I can write the basic idea here if you'd like (they probably shared a more thorough writeup tho?)

John Baez (Jun 14 2022 at 05:57):

They've never sent me a writeup, but I think it's best if you and them all cooperate to create a nice writeup and show that to me.

Sam Tenka (Jun 14 2022 at 05:58):

Okay! Will ask them next we video meet if they'd like another brain and eyes on board the writing process.

John Baez (Jun 14 2022 at 05:59):

Yeah, I'm in no doubt that the result is true, so I think my main job is to coax y'all to write up a nice proof, which could become a nice little paper.

Sam Tenka (Jun 14 2022 at 06:03):

(Here's something a bit interesting btw.

It's a practice problem I solved (or, based on @Benjamin Merlin Bumpus 's comments below, maybe not?) to prepare for the monically open petri nets.

Let's take the simpler situation of monically open "vine"s. Intuitively, a monically open vine is a $2$-regular undirected graph, but monically open --- it is locally a special case of a graph theorist's tree but globally can curl up into itself to form cycles, hence the name.

Formally, a monically open vine $G$ is a cospan $X\to V\leftarrow Y$ of finite sets decorated with a finite undirected graph (edges $E$) on vertices $V$ satisfying:
[monicity] The maps $X\to V\leftarrow Y$ are monic
[regularity] $\deg(v)+|\text{img}(X)\cap \{v\}|+|\text{img}(Y)\cap \{v\}|=2$ for each $v:V$
We write $G:X\to Y$ when $G$ is a vine. We can can compose two vines $G:X\to Y$ and $H:y\to z$ by gluing $G,H$ along the (sub)set $y$ of their shared nodes. This is unique up to isomorphism. So we'll form a category $\textsf{Vine}$ whose objects are sets and whose morphisms are isomorphism classes of vines.

Now: what are all the functors from $\mathsf{Vine}$ to $\mathbb{N}$ that are also additive in the sense that tensor also goes to plus?

Answer: they are $\mathbb{N}$-linear combinations of $\mathcal{L}, \mathcal{R}, \mathcal{I}, \mathcal{B}$ defined by $\mathcal{L}(G) = |V|-|Y|$, $\mathcal{R}(G) = |V|-|X|$, $\mathcal{I}(G) = |E|$, and $\mathcal{B}=\text{number of selfloops}$. Intuitively, the functors $\mathcal{L},\mathcal{R}$ measure the size of graphs as half-closed-half-open intervals or as half-open-half-closed intervals. The halfishness helps composition just as halfish numeric intervals compose well: $[\ell,m) \sqcup [m,n) = [\ell, n)$. It was @Layla who discovered these functors in the monically open petri case! $\textsf{Vine}$ is self-dual and precomposing with its oppositification functor swaps $\mathcal{L}, \mathcal{R}$ and fixes $\mathcal{O}, \mathcal{B}$ . Note (count half-edges, i.e. edges in the sense of serre) that $2\mathcal{I}=\mathcal{R}+\mathcal{L}$ --- they are $\mathbb{Q}$-linearly dependent but $\mathbb{N}$-linearly irredundant!

Proof Sketch: start with any vine. use additivity to decompose a vine into its connected components. use functoriality to decompose each chain into its edges. We are left with four kinds of atomic parts: "bras", "kets", "pipes", and "bubbles", each with one edge and (0,2);(2,0);(1,1);(0,0) many (inputs/outputs). Note: this decomposition is far from unique: if we have a strand of consecutive pipes, we can form or annihilate bra-ket zigzag pairs as we please. Writing out 4 part-count generators and 1 creation/annhilation part-count relation reveals that the only invariants are formed from $\mathcal{L}, \mathcal{R}, \mathcal{I}, \mathcal{B}$.

)

EOM --- sorry for long

Benjamin Merlin Bumpus (he/him) (Jun 14 2022 at 10:12):

@John Baez and @Sam Tenka we were always assuming the sum was infinite (at least that's how it's written in my notes :rolling_on_the_floor_laughing: )

also, @Sam Tenka i like the Vine example; I think you're rediscovering some of the stuff we were working on during the last day at Beaver Hollow. We also were thinking about the left and right "private vertex" maps (i.e. $\mathcal{L}$ and $\mathcal{R}$), but we also found a few more motifs that need to be counted individually.

B.t.w, I'm rather convinced (no proof that I know of yet... I haven't thought about it since Buffalo) that we found all of the "atomic" functors for the monic version of John's conjecture. I suggest we try to get a meeting time agreed upon so that we don't duplicate efforts (and so we can decide when we're going to write it all up) :+1:

John Baez (Jun 14 2022 at 13:58):

This "vine" conjecture is quite interesting! The extra invariants may help @Wilmer Leal, @Kris Brown and me in our project.

Sam Tenka (Jun 14 2022 at 14:31):

Benjamin Merlin Bumpus said:

John Baez and Sam Tenka we were always assuming the sum was infinite (at least that's how it's written in my notes :rolling_on_the_floor_laughing: )

also, Sam Tenka i like the Vine example; I think you're rediscovering some of the stuff we were working on during the last day at Beaver Hollow. We also were thinking about the left and right "private vertex" maps (i.e. $\mathcal{L}$ and $\mathcal{R}$), but we also found a few more motifs that need to be counted individually.

B.t.w, I'm rather convinced (no proof that I know of yet... I haven't thought about it since Buffalo) that we found all of the "atomic" functors for the monic version of John's conjecture. I suggest we try to get a meeting time agreed upon so that we don't duplicate efforts (and so we can decide when we're going to write it all up) :+1:

Oh! Wow, I'd love indeed to learn what motifs-to-count / atomic functors you found!

Sophie Libkind (Jun 14 2022 at 17:16):

Just catching up on this thread and it's reinvigorated my excitement for this project! Looking forward to meeting soon :)

John Baez (Jun 14 2022 at 18:35):

Yeah, I'm excited to hear people have been finding lots of new invariants for monic open Petri nets! When I raised this question I figured there would be a manageable number of them (besides the $F_{m,n}$), but I had no idea what they were.