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: category theory

Topic: What is the trace of the category of divisibility posets?

Emily (she/her) (Nov 09 2024 at 00:24):

I have a puzzle which I think might be fun to work out. I've posted it on MO here, and will share it below.

Lately I've been trying to gather more examples of centres and traces, hoping to write a comprehensive treatment on those on Clowder.

One of the examples I've been trying to understand better is the category of divisibility posets $\mathcal{D}$, which is defined as follows.

• For each $n\in\mathbb{N}_{\geq1}$, let $D_n$ be the poset consisting of the set $\{1,\ldots,n\}$ together with the preorder $\preceq$ given by declaring $k\preceq\ell$ if $k$ divides $\ell$.
• Then, let $\mathcal{D}$ be the full subcategory of the category $\mathsf{Pos}$ of posets and monotone maps spanned by the posets $D_n$ for all $n\in\mathbb{N}_{\geq1}$.

Recalling the definitions, the center of $\mathcal{D}$ is defined as

$$\begin{align*} \mathrm{Z}(\mathcal{D})&\overset{\scriptstyle\mathrm{def}}{=}\int_{D_n\in\mathcal{D}}\mathrm{Hom}_{\mathcal{D}}(D_n,D_n)\\ &\cong\mathrm{Nat}(\mathrm{id}_{\mathcal{D}},\mathrm{id}_{\mathcal{D}}), \end{align*}$$

while the trace of $\mathcal{D}$ is defined as

$$\begin{align*} \mathrm{Tr}(\mathcal{D})&\overset{\scriptstyle\mathrm{def}}{=}\int^{D_n\in\mathcal{D}}\mathrm{Hom}_{\mathcal{D}}(D_n,D_n)\\ &\cong\left.\left(\coprod_{D_n\in\mathrm{Obj}(\mathcal{D})}\mathrm{Hom}_{\mathcal{D}}(D_n,D_n)\right)\middle/\mathord{\sim}\right., \end{align*}$$

where $\sim$ is the equivalence relation generated by $f\circ g\sim g\circ f$. Finally, the quotient map from $\coprod_{D_n\in\mathrm{Obj}(\mathcal{D})}\mathrm{Hom}_{\mathcal{D}}(D_n,D_n)$ to $\mathrm{Tr}(\mathcal{D})$ is called the trace map of $\mathcal{D}$.

Looking at naturality with respect to the maps $[k]\colon D_1\to D_n$ given by $1\mapsto k$ shows the centre of $\mathcal{D}$ to be trivial. However, as is usual with centres and traces, computing the trace seems to be much, much harder.

Question. Is there a neat description of the trace of $\mathcal{D}$ and the trace map?

(By "neat" here I'm thinking of something like how conjugacy classes of symmetric groups may be described as Young diagrams.)

Here are some miscellaneous notes:

• Decomposing each $n$ as $n=2^{e_1}\cdots p^{e_k}_{k}$, we may equivalently describe $\mathcal{D}$ as a category whose objects are sets of strings of the form $(a_1,\ldots,a_k)$ with $a_1\leq e_1,\ldots,a_k\leq e_k$ for a given $(e_1,\ldots,e_k)$ and maps are monotone maps with respect to the index-wise order.
• The trace of the category $\mathcal{D}_m$ spanned by the divisibility posets $D_1,\ldots,D_m$ has the following cardinalities from $m=1$ to $m=8$: $(1,2,4,6,11,21,39,59)$. (OEIS gives nothing for these.)
• For example, the equivalence classes in $\mathrm{Tr}(\mathcal{D}_3)$ are the following:

Class 1:
  D_1 -> D_1: (1,)
  D_2 -> D_2: (1, 1)
  D_2 -> D_2: (2, 2)
  D_3 -> D_3: (1, 1, 1)
  D_3 -> D_3: (1, 1, 2)
  D_3 -> D_3: (1, 3, 1)
  D_3 -> D_3: (2, 2, 2)
  D_3 -> D_3: (3, 3, 3)

Class 2:
  D_2 -> D_2: (1, 2)
  D_3 -> D_3: (1, 1, 3)
  D_3 -> D_3: (1, 2, 1)
  D_3 -> D_3: (1, 2, 2)
  D_3 -> D_3: (1, 3, 3)

Class 3:
  D_3 -> D_3: (1, 2, 3)

Class 4:
  D_3 -> D_3: (1, 3, 2)

Here e.g. $(1,3,2)$ denotes the map sending $(1,2,3)$ to $(1,3,2)$.

• A complete enumeration of the equivalence classes in $\mathrm{Tr}(\mathcal{D}_m)$ from $m=1$ to $m=8$ is available here.

Amar Hadzihasanovic (Nov 09 2024 at 08:27):

Can you say something about why you choose the full subcategory of $\mathsf{Pos}$ on the divisibility posets?
The divisibility posets are all graded (by the number of prime factors counted with their multiplicity), and in my experience the natural notion of morphism between graded posets is never “all monotone maps”, it needs to take into account the grading somehow (e.g. be grade-preserving, or grade-non-increasing, which is for example implied by “sends lower sets to lower sets”).

Emily (she/her) (Nov 09 2024 at 13:23):

No reason in particular; do you think putting extra conditions on the maps related to the grading could make the computation of the trace significantly easier?

Amar Hadzihasanovic (Nov 09 2024 at 15:55):

No, I don't have any particular ideas! Just thought that one could try out different notions of morphism that are more constrained, i.e. take into account more of the structure of divisibility posets, and see if the corresponding sequence of cardinalities of $\mathrm{Tr}(\mathcal{D}_m)$ shows up on OEIS.

Amar Hadzihasanovic (Nov 09 2024 at 15:57):

For example “closed” maps, those that are lower-set preserving, would corresponding to maps “reflecting” divisors, that is, every divisor of $f(n)$ is equal to $f(m)$ for some divisor $m$ of $n$. These would in particular be grade-non-increasing and always be such that $f(1) = 1$. It seems like a natural constraint to try.

Amar Hadzihasanovic (Nov 09 2024 at 16:05):

I'm sorry if this is a bit of an annoying reply, I don't mean to respond to “How can I do A?” by saying “Why not do B instead?”; it is just that I do not have many ideas about your original question but am both curious about the motivation, and generally find the question of “exploring the enumerative combinatorics of category-theoretic invariants of certain finite categories” very fascinating, so I would like to see if something more recognisable pops out if we tweak these categories.

Todd Trimble (Nov 10 2024 at 14:40):

Emily (she/her) said:

• For each $n\in\mathbb{N}_{\geq1}$, let $D_n$ be the poset consisting of the set $\{1,\ldots,n\}$ together with the preorder $\preceq$ given by declaring $k\preceq\ell$ if $k$ divides $\ell$.
• Then, let $\mathcal{D}$ be the full subcategory of the category $\mathsf{Pos}$ of posets and monotone maps spanned by the posets $D_n$ for all $n\in\mathbb{N}_{\geq1}$.

[...]

Here are some miscellaneous notes:

• Decomposing each $n$ as $n=2^{e_1}\cdots p^{e_k}_{k}$, we may equivalently describe $\mathcal{D}$ as a category whose objects are sets of strings of the form $(a_1,\ldots,a_k)$ with $a_1\leq e_1,\ldots,a_k\leq e_k$ for a given $(e_1,\ldots,e_k)$ and maps are monotone maps with respect to the index-wise order.

That note doesn't sound right. Those objects seem to be divisibility down-sets generated by $n$ (a product of linear orders, as noted by Sam Hopkins at MO), with a single maximal element as indexed by $(e_1, \ldots, e_k)$. Whereas $\{1, \ldots, n\}$ ordered by divisibility can have multiple maximal elements (for $n = 7$, the elements $4, 5, 6, 7$ are all maximal).

(Rereading the comments under the MO post, it seems you then removed that note from the MO post, but then didn't remove it here.)

Emily (she/her) (Nov 11 2024 at 18:44):

Amar Hadzihasanovic said:

No, I don't have any particular ideas! Just thought that one could try out different notions of morphism that are more constrained, i.e. take into account more of the structure of divisibility posets, and see if the corresponding sequence of cardinalities of $\mathrm{Tr}(\mathcal{D}_m)$ shows up on OEIS.

Oh, that's a great idea! I'll try exploring some of these numerically and see if anything interesting comes up!

Emily (she/her) (Nov 11 2024 at 18:47):

Amar Hadzihasanovic said:

I'm sorry if this is a bit of an annoying reply, I don't mean to respond to “How can I do A?” by saying “Why not do B instead?”; it is just that I do not have many ideas about your original question but am both curious about the motivation, and generally find the question of “exploring the enumerative combinatorics of category-theoretic invariants of certain finite categories” very fascinating, so I would like to see if something more recognisable pops out if we tweak these categories.

No worries!

Emily (she/her) (Nov 11 2024 at 18:47):

On motivation, I'm afraid I don't have anything too nice to say, I originally started thinking about this in the context of trying to come up with problems for an AI benchmark contest thing, and this category of divisibility posets felt a bit similar in flavour to other "combinatorial" categories like the simplex category

Emily (she/her) (Nov 11 2024 at 18:50):

In general I'm also trying to gather as many interesting examples of traces of categories as I can, though, since I'm working on writing a comprehensive treatise about centres and traces on Clowder

Emily (she/her) (Nov 11 2024 at 18:52):

Todd Trimble said:

Emily (she/her) said:

• For each $n\in\mathbb{N}_{\geq1}$, let $D_n$ be the poset consisting of the set $\{1,\ldots,n\}$ together with the preorder $\preceq$ given by declaring $k\preceq\ell$ if $k$ divides $\ell$.
• Then, let $\mathcal{D}$ be the full subcategory of the category $\mathsf{Pos}$ of posets and monotone maps spanned by the posets $D_n$ for all $n\in\mathbb{N}_{\geq1}$.

[...]

Here are some miscellaneous notes:

• Decomposing each $n$ as $n=2^{e_1}\cdots p^{e_k}_{k}$, we may equivalently describe $\mathcal{D}$ as a category whose objects are sets of strings of the form $(a_1,\ldots,a_k)$ with $a_1\leq e_1,\ldots,a_k\leq e_k$ for a given $(e_1,\ldots,e_k)$ and maps are monotone maps with respect to the index-wise order.

That note doesn't sound right. Those objects seem to be divisibility down-sets generated by $n$ (a product of linear orders, as noted by Sam Hopkins at MO), with a single maximal element as indexed by $(e_1, \ldots, e_k)$. Whereas $\{1, \ldots, n\}$ ordered by divisibility can have multiple maximal elements (for $n = 7$, the elements $4, 5, 6, 7$ are all maximal).

(Rereading the comments under the MO post, it seems you then removed that note from the MO post, but then didn't remove it here.)

Yep! I had in mind something like picking a list of all primes which divide $\{1,\ldots,n\}$ and representing $1,\ldots,n$ as strings $(a_1,\ldots,a_n)$, but ended up fumbling up the description when first writing the question. In the end I decided to just remove it since it's not really that helpful of a description, I think...