14
$\begingroup$

For two sets $O$ and $A$, we will call a category structure a collection of functions ${\sf dom}:A\to O,\ {\sf cod}:A\to O,\ {\sf 1}:O\to A,\ \circ:A\times_OA\to A$ satisfying the usual axioms for a category.

Can we parametrize the number of category structures (up to iso or equivalence) on two sets $O$ and $A$ in terms of their cardinalities? If a closed-form solution is too much to ask, can we get asymptotics for finite sets?

Denote by ${\sf Cat}^\cong(n,m)$ the number of isomorphism classes of category structures on two sets $O$ and $A$ as above with $|O|=n$ and $|A|=m$. We trivially have that $n\leq m$. For $n=m=0$ we have exactly one category, and for $n=m=1$ we have a unique up to iso category. In general for $n=m$ we have ${\sf Cat}^\cong(n,m)=1$, but all these observations are trivial.

For $n=1$ and $1\leq m$ we are counting the number of monoids on a set with $m$ elements, which I tried to search but was unable to find -- I did find this related question, and the comments by Qiaochu Yuan give a lower bound of $B^\leq_m\leq{\sf Cat}(1,m)$ where $B^\leq_m$ is the $m^{th}$ ordered Bell number. As the comment by Douglas Zare suggests, this indicates that asymptotics are the best we should hope for since the ordered Bell numbers grow faster than exponential in $m$.

The case for semigroups is cutting edge for a set with $12$ elements by a paper linked in the answer to the linked question, so any asymptotics will have to use the existence of units to hopefully shave things down. The second linked paper gives a closed-form solution for the number of nilpotent semigroups of degree $3$, so adding mild restrictions seems to potentially allow for more tractable counting.

Denote by ${\sf Cat}^\simeq(n,m)$ the number of equivalence classes of category structures on two sets $O$ and $A$ as above. We trivially have ${\sf Cat}^\simeq(n,m)\leq{\sf Cat}^\cong(n,m)$ with equality holding for $n=m$, but beyond this I don't see much concrete to say.

It may be useful to use the cardinalities of the hom-sets between objects in the category structures instead of the cardinality of the overall set of arrows, but beyond more obvious observations nothing jumps out at me using this approach either. For $1<n$ and $n<m$ it is trivial (and kind of fun) to count some small cases, but I don't know how to search the OEIS to see if the sequence is already catalogued. Any assistance is appreciated.


First linked paper: Distler A., Jefferson C., Kelsey T., Kotthoff L. (2012) The Semigroups of Order 10. In: Milano M. (eds) Principles and Practice of Constraint Programming. CP 2012. Lecture Notes in Computer Science, vol 7514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33558-7_63

Second linked paper: Distler A., Mitchell J. D., (2012) The Number of Nilpotent Semigroups of Degree 3. In: The Electronic Journal of Combinatorics, Volume 19, Issue 2 (2012). https://doi.org/10.37236/2441

$\endgroup$
22
  • 2
    $\begingroup$ Just a typo: if ${\sf 1}$ is the arrow sending an object to its identity you probably want it to go from $O$ to $A$ $\endgroup$ – fosco Apr 29 at 9:39
  • $\begingroup$ @fosco Fixed, thank you. $\endgroup$ – Alec Rhea Apr 29 at 9:46
  • 3
    $\begingroup$ For monoids, see oeis.org/A058129 "Number of monoids (semigroups with identity) of order n." $\endgroup$ – Gerald Edgar Apr 29 at 10:23
  • 2
    $\begingroup$ There is no hope to answer this question. You can adjoin an identity to a semigroup to get a monoid so the number of monoids of order 14 is greater than the number of semigroups of order 13 which we don't know. So adding the identity requirement doesn't really make things easier. By the way I fixed the link. $\endgroup$ – Benjamin Steinberg Apr 29 at 12:22
  • 1
    $\begingroup$ @DavidRoberts, I would guess that almost all categories asymptotically have a zero morphism between any hom sets for such there are morphisms and at product of three non identities is a zero morphism. $\endgroup$ – Benjamin Steinberg Apr 30 at 2:42
24
$\begingroup$

The problem of counting semigroups and monoids of order $n$ up to isomorphism and anti-isomorphism (i.e., contravariant equvialence) is a very classical problem whose answer is conjectured but nobody has made serious progress in proving over the last 60 years. The analogous situation in group theory is that virtually all finite group theorists agree that the vast majority of groups of order less than or equal to $n$ are $p$-groups and likely $2$-groups, but nobody knows how to prove it.

A semigroup is called $3$-nilpotent if it has a zero (aka absorbing element) and the product of any $3$ elements is zero. Notice that you build a table in which the product of any three elements is zero, then automatically the associative law is satisfied and so it is very very easy to build such semigroups. In 1976, Kleitman, Rothschild and Spencer showed that asymptotically all associative multiplication tables on the set $\{1,\ldots, n\}$ are $3$-nilpotent. This is not counting up to isomorphism but the feeling is that these kinds of semigroups admit few automorphisms and so that is not overcounting by much.

So the conjecture that has been around forever is the proportion of semigroups of order $n$ which are $3$-nilpotent is $1$. In a beautiful paper Distler and Mitchell gave a closed formula for the number of $3$-nilpotent semigroups up to isomorphism and also up to isomorphism and anti-isomorphism. So conjecturaly this is the asymptotics for the number of finite semigroups. But nobody knows how to prove this conjecture. To the best of my knowledge, but I am a few years out of date, we only know the number of semigroups of order up to 10. The number of semigroups of order up to 10 has been counted up to isomorphism and anti-isomorphism in Distler et al and it is the astronomical number 12,418,001,077,381,302,684. Almost all of these are $3$-nilpotent.

So what does this have to do with counting categories? Well, a one object category is a monoid and natural equivalence is isomorphism (and anti-isomorphism is contravariant equivalence) so this is a special case of the problem. Ah, but you are doing semigroups and we don't like semigroups because they don't even know who they are, lacking an identity (bad pun alert). Well, if you adjoin an identity you get an embedding from the set of isomorphism classes of semigroups of order $n-1$ into the set of isomorphism classes of monoids of order $n$ (same with isomorphism/anti-isomorphism classes). So the number of monoids of order $n$ up to isomorphism is at least as big as the number of semigroup of order $n-1$. Now I would conjecture that almost all monoids of order $n$ arise this way and so the number of monoids of order $n$ should behave like the number of $3$-nilpotent semigroups of order $n-1$. But again this is conjectural. I don't know if this monoid version of the conjecture has been published anywhere and since we don't have conferences these days I can't really ask around. So here is some evidence. In Distler et al it is shown that the number of isomorphism/anti-isomorphism classes of semigroups of order $9$ is 52,989,400,714,478. The number of isomorphism/anti-isomorphism classes of monoids of order $10$ is computed in Distler et al to be 52,991,253,973,742.

So in summary, we most likely know the asymptotics for monoids of order $n$ but it may be 100 years before anybody proves it.

Added. It was suggested in the comments to count Morita equivalence classes of categories instead, but that doesn't help the matter because two finite monoids are Morita equivalent of and only if they are isomorphic. The indecomposable projective right $M$-sets are of the form $eM$ with $e$ idempotent and any Morita equivalent monoid must be isomorphic to one of the form $eMe$ for a projective generator $eM$ of $M$-sets. But if $e\neq 1$, then $|eM|<|M|$ and so cannot generate $M$.

$\endgroup$
3
  • $\begingroup$ Kleitman et al. showed that asymptotically all finite semigroups are 3-nilpotent. What exactly do you mean by multiplication table? $\endgroup$ – John Bentin Apr 30 at 6:14
  • $\begingroup$ @JohnBentin, they were not counting up to isomorphism. They fixed the ground set as 1,...,n and looked at semigroups on that set. So they are counting the number of associative multiplicative tables not isomorphism classes of semigroups. To them the two element cyclic group with 1 as the identity is different than the two element cyclic group with 2 as the identity $\endgroup$ – Benjamin Steinberg Apr 30 at 11:07
  • 1
    $\begingroup$ @JohnBentin I added the word associative before multiplication table. $\endgroup$ – Benjamin Steinberg Apr 30 at 11:14
7
$\begingroup$

Not precisely what you're asking, I think, but there are a few papers in this direction that I know of that might be of interest, for instance:

  • Samer Allouch, Sur l'existence d'une catégorie ayant une matrice strictement positive donnée, arXiv:0806.0060.

Or more recently,

  • Samer Allouch and Carlos Simpson, Classification of categories with matrices of coefficient 2 and order $n$, Communications in Algebra Volume 46, Issue 7 (2018) pp. 3079-3091, doi:10.1080/00927872.2017.1404081, free version,

in which the goal is to count finite/discrete categories given by a matrix which have as entries the number of arrows between two given objects (identified with the (row,column) index).

This doesn't automatically give you something for your question, but maybe some of the bounds in those results might help you reduce the bounds in the case where you only control for the global number of arrows.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.