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: mathematics

Topic: Submonoids of free commutative monoids

John Baez (Apr 14 2025 at 22:35):

Every subgroup of a free abelian group is free - apparently this was proved by Dedekind! Not every submonoid of a free commutative monoid is free - many submonoids of the free monoid on one generator are not free. But I'm wondering:

Question. Suppose $F$ is a finitely generated free commutative monoid, $\mathbb{N}$ is the free commutative monoid on one generator, and $s, t: F \to \mathbb{N}$ are monoid homomorphisms. Is the equalizer of $s$ and $t$ a free commutative monoid?

Since every finitely generated free commutative monoid is isomorphic to $\mathbb{N}^k$ with its usual additionfor some $k$, we can restate the question more concretely as follows:

Question. Suppose $s, t: \mathbb{N}^k \to \mathbb{N}$ are monoid homomorphisms. Is

$\{x \in \mathbb{N}^k \; \vert \; s(x) = t(x) \} \subseteq \mathbb{N}^k$

a free commutative monoid?

Zoltan A. Kocsis (Z.A.K.) (Apr 15 2025 at 00:24):

(Warning: I haven't had my morning coffee yet, so this is more likely to be wrong than usual)

Wouldn't the monoid $M = \{ (a,b,c) \in \mathbb{N}^3 \mid a + b = 2c\}$ fail to be free commutative? You can't decompose any of the elements $x=(2,0,1)$ or $y=(0,2,1)$ or $z=(1,1,1)$ as nontrivial sums, so they'd have to be among the generators. But then $x + y = z + z$ holds, so $M$ is not free?

John Baez (Apr 15 2025 at 01:21):

That counterexample looks convincing me, but I quit drinking coffee a few weeks ago so someone else should take an independent look! Anyway, thanks!

Oscar Cunningham (Apr 15 2025 at 05:56):

Right, that doesn't look like $\mathbb{N}^2$ to me.c03c61ce-c35f-45ad-b4f0-04ecf906cc26.png

John Baez (Apr 15 2025 at 06:16):

Thanks, Oscar! Using the preorder on a commutative monoid defined by $x \le y$ iff for some $z$ we have $x + y = z$, your picture shows three minimal elements: that is, three elements such that only $0$ is less than them. These must be Zoltan's elements $(2,0,1), (0,2,1)$ and $(1,1,1)$. I believe any free commutative monoid is free on its minimal elements. But that's not happening here! This monoid isn't isomorphic to $\mathbb{N}^3$. Nor $\mathbb{N}^2$, as you mentioned.

Oscar Cunningham (Apr 15 2025 at 08:08):

Right. I was thinking if it was free it had to be $\mathbb{N}^2$ because it lies in a plane. But you can actually make $\mathbb{N}^3$ lie in a plane if you choose three vectors independent over $\mathbb{Q}$. So the important thing to check is that those three minimal vectors do indeed obey a nontrivial relation, as Zoltan said.

John Baez (Apr 15 2025 at 18:13):

And I think we can see the relation in your picture! There are 3 guys close to the origin, in a row. The left guy plus the right guy is twice the middle guy.

John Baez (Apr 15 2025 at 18:16):

This is a nice example of the situation that @Adittya Chaudhuri and I are trying to prove does not happen in the 1st homology monoid of a directed graph.

Morgan Rogers (he/him) (Apr 16 2025 at 07:18):

So are you trying to show that your homology monoid is free or just gather nice properties of it?

Adittya Chaudhuri (Apr 16 2025 at 07:25):

Morgan Rogers (he/him) said:

So are you trying to show that your homology monoid is free or just gather nice properties of it?

We are trying to show our homology monoid is free on a set of "minimal directed cycles".

Morgan Rogers (he/him) (Apr 16 2025 at 07:57):

I'm curious how this homology will work. For instance, consider the following directed graph, where I think I have labelled all of the minimal directed cycles:
image.png
If I purely look at the directed edges that appear, we have $\sum_i C_i = E + I + \sum_j T_j$, in which case the resulting monoid is not free, but maybe I am oversimplifying the construction!

Adittya Chaudhuri (Apr 16 2025 at 08:07):

Morgan Rogers (he/him) said:

I'm curious how this homology will work. For instance, consider the following directed graph, where I think I have labelled all of the minimal directed cycles:
image.png
If I purely look at the directed edges that appear, we have $\sum_i C_i = E + I + \sum_j T_j$, in which case the resulting monoid is not free, but maybe I am oversimplifying the construction!

Thanks for the example. I am trying to understand the point you made.

Adittya Chaudhuri (Apr 16 2025 at 08:17):

Thanks. At the moment, I think your counterexample seems correct. In that case, the homology monoid may not be free. But, I have to think (if I am missing something).

Adittya Chaudhuri (Apr 16 2025 at 10:07):

Morgan Rogers (he/him) said:

So are you trying to show that your homology monoid is free or just gather nice properties of it?

I think "just gather nice properties of it" is also interesting.

Morgan Rogers (he/him) (Apr 16 2025 at 11:12):

For example, any submonoid of a free commutative monoid should be cancellative

John Baez (Apr 16 2025 at 16:55):

Wow, what an interesting example, @Morgan Rogers (he/him)!

I expected and wanted the first homology monoid of a directed graph to be free because 1) it was free in all the examples I could come up with, 2) the first homology group of an undirected graph is free, 3) free commutative monoids are very nice because unlike free abelian groups they're free on a unique set of generators, the minimal elements, 4) in applications these minimal elements play an important role as 'basic feedback loops', the key mechanisms that create positive or negative feedback loops in a complex system like this:

Causal loop diagram for a business department

John Baez (Apr 16 2025 at 16:57):

Your name is going on the Acknowledgements to our paper right now - you've saved us a lot of time spent trying to prove something that's not true!

John Baez (Apr 16 2025 at 17:00):

(Zoltan and Oscar too, for dispelling another silly hope I had about freeness.)

John Baez (Apr 16 2025 at 17:21):

Morgan Rogers (he/him) said:

For example, any submonoid of a free commutative monoid should be cancellative.

Right, we do get that.

Here's another cool fact I'd like to deploy somehow:

Say you have a finitely generated free commutative monoid $M$ equipped with the partial order where $x \le y$ iff $y = x + z$ for some $z$. Then Dickson's Lemma says every subset of $M$ has a finite set of minimal elements!

We can say this in a less fancy way: say we have $M = \mathbb{N}^k$ equipped with the partial order where $x \le y$ iff $x_i \le y_i$ for all $i = 1, \dots , k$. Then every subset of $M$ has a finite set of minimal elements.

Here's a subset of $\mathbb{N}^2$ and its minimal elements:

John Baez (Apr 16 2025 at 17:23):

This subset $S$ (the dots in the shaded region) is actually a submonoid. Note that if we regard $S$ as a commutative monoid in its own right, its partial ordering is different than the partial ordering it inherits from $\mathbb{N}^2$, since we often have $x,y \in S$ with $y = x + z$ where $z \in \mathbb{N}^2$ but not $z \in S$.

$S$ has more minimal elements if we regard it as a commutative monoid in its own right than if we regard it as a subset of the commutative monoid $\mathbb{N}^2$. For all I know, it's not finitely generated!

John Baez (Apr 16 2025 at 18:00):

Here's a puzzle for everyone. What's the smallest directed graph you can find where its first homology monoid is not a free commutative monoid?

John Baez (Apr 16 2025 at 18:58):

Morgan Rogers (he/him) (Apr 16 2025 at 19:18):

Ha once you know something is false it's a lot easier to find a counterexample :upside_down:

Adittya Chaudhuri (Apr 16 2025 at 19:20):

John Baez said:

I think I have an example with 2 vertices and 4 edges.

notfree.png
May be this is the one?

Morgan Rogers (he/him) (Apr 16 2025 at 19:21):

Spoiled! :stuck_out_tongue_closed_eyes:

Alex Kreitzberg (Apr 16 2025 at 19:53):

Adittya Chaudhuri said:

notfree.png
May be this is the one?

I don't know how to explain it, but this has Yin Yang vibes

John Baez (Apr 16 2025 at 20:16):

Yes, that was my example:

I took Morgan Rogers' trick and kept simplifying it.

Ha once you know something is false it's a lot easier to find a counterexample.

Indeed. I'm sure you too could have trimmed down your counterexample, but it's not really important - I just wanted to see how small I could make it, since a small counterexample is more likely to show up in applications.

Adittya Chaudhuri (Apr 17 2025 at 02:32):

@John Baez Nice. But, I constructed this example only after you gave the spoiler.