Enumerating submonoids of finite commutative monoids
Caoilainn Kirkpatrick, Amelie el Mahmoud, Kyle Ormsby, Angélica M. Osorno, Dale Schandelmeier-Lynch, Riley Shahar, Lixing Yi, Avery Young, Saron Zhu · 2025
Read Enumerating submonoids of finite commutative monoids by Caoilainn Kirkpatrick, Amelie el Mahmoud, Kyle Ormsby, Angélica M. Osorno, Dale Schandelmeier-Lynch, Riley Shahar, Lixing Yi, Avery Young, Saron Zhu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20786.txt.
Introduction
Caoilainn Kirkpatrick and co-authors tackle a counting problem in a 2025 algebra paper. Given a finite set with a well-behaved combining rule, they ask how many smaller closed subsets sit inside a product of that set with a chain of numbers. The chain uses the larger of two values as its rule.
The team shows these subsets can be counted with a transfer matrix method, which tracks how counts build step by step. When the set also has a repeat property, the count takes a neat closed form: a sum of powers weighted by fixed fractions. The result answers a question posed by Donald Knuth. It also feeds into counting tools used in a branch of topology.
Catalog record
| CREATOR | Caoilainn Kirkpatrick, Amelie el Mahmoud, Kyle Ormsby, Angélica M. Osorno, Dale Schandelmeier-Lynch, Riley Shahar, Lixing Yi, Avery Young, Saron Zhu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-20786
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Enumerating submonoids of finite commutative monoids Caoilainn Kirkpatrick, Amelie el Mahmoud, Kyle Ormsby, Angélica M. Osorno, Dale Schandelmeier-Lynch, Riley Shahar, Lixing Yi, Avery Young, Saron Zhu Abstract . Given a finite commutative monoid M M , we show that submonoids of M × [ n ] M\times[n] — where [ n ] = { 0 , 1 , … , n } [n]=\{0,1,\ldots,n\} is equipped with the max operation ∨ \vee — may be enumerated via the transfer matrix method. When M M is also idempotent, we show that there are finitely many integers λ \lambda and rational numbers b λ b_{\lambda} (only depending on M M ) such that the number of submonoids of M × [ n ] M\times[n] is ∑ λ b λ λ n \sum_{\lambda}b_{\lambda}\lambda^{n} . This answers a question of Knuth regarding ternary (and higher order) max-closed relations, and has applications to the enumeration of saturated transfer systems in equivariant infinite loop space theory. 1. Introduction Subgroup lattices have long played an important role in the theory of finite groups. While \operatorname{Sub}G is far from a complete invariant of a finite group G , many important properties of G are faithfully represented by the isomorphism type of \operatorname{Sub}G . In light of this, subgroup lattices have enjoyed intense study; see [ Sch94 ] for an overview. In this paper, we turn our attention to a more general but less ubiquitous algebraic structure: monoids and their submonoid lattices, with particular emphasis on finite commutative and finite commutative idempotent monoids. See Section 2 for recollections of essential definitions. The main problem we attack is easy to state. For a natural number n , let [n]=\{0,1,\ldots,n\} with the operation k\vee\ell=\max\{k,\ell\} . Question . Given a finite monoid M , to what extent does \operatorname{SubMon}M determine the cardinality of \operatorname{SubMon}(M\times[n]) ? Varying the hypotheses on M , we arrive at several satisfactory answers. Our most general result employs the transfer matrix method , which is nicely summarized in [ Sta11 , Chapter 4] . The idea is that, when counted with appropriate weights, length n walks in a particular weighted directed graph G(M) count the submonoids of M\times[n] . These weighted walks are computed by powers of the adjacency matrix W=W(M) of G(M) , thus allowing us to bring linear algebraic tools to bear on the problem. Theorem ( Section 2.1 ) . Suppose M is a finite commutative monoid. Then there is a lower triangular matrix W of natural numbers with rows and columns indexed by a linear extension of \operatorname{SubMon}M such that \#\operatorname{SubMon}(M\times[n])=\sum_{A,B\in\operatorname{SubMon}M}(W^{n})_{A,B}. The entries of W are combinatorial in nature, with W_{A,B}=\#\{I\subseteq A\mid I\text{ an ideal of $A$ and }I\cup B=A\}. (See Section 2.1 and Section 2.1 .) Carefully analyzing these numbers for M a finite Abelian group results in a surprising corollary: Theorem ( Section 2.1 ) . Suppose M is a finite Abelian group and n is a natural number. Then \#\operatorname{SubMon}(M\times[n])=2^{n}\cdot\sum_{m\geq 0}c_{m}2^{-m}\binom{n}{m}\sim\frac{1}{h!}c_{h}n^{h}2^{n-h}, where c_{m} is the number of length m chains in the subgroup lattice of M and h is the height of \operatorname{Sub}M , i.e. , the length of the longest chain in the subgroup lattice. Specializing in another direction, we consider the case of finite idempotent monoids. These are equivalent to finite join-semilattices; see Section 2 (b). Theorem ( Section 3.1 , Section 3.1 ) . Suppose M is a finite commutative idempotent monoid. Then the matrix W(M) is diagonalizable. It follows that there is a finite set of positive integers \Lambda=\Lambda(M) and rational numbers b_{\lambda}=b_{\lambda}(M) for \lambda\in\Lambda such that \#\operatorname{SubMon}(M\times[n])=\sum_{\lambda\in\Lambda}b_{\lambda}\lambda^{n}. The above theorem provides a partial answer to a question of Don Knuth [ Knu24 , Problem 10] . Knuth asks how many “max-closed relations” there are on a finite product of chains \prod[n_{i}] . His max-closed relations are just subsemigroups of \prod[n_{i}] under join. It is straightforward to check that for a join-semilattice P , the “remove e ” map is two-to-one from subsemigroups to submonoids, and hence \#\operatorname{SubSemi}\prod[n_{i}]=2\#\operatorname{SubMon}\prod[n_{i}]. Knuth [ Knu24 ] details how \operatorname{SubSemi}([m]\times[n]) is enumerated by the poly-Bernoulli numbers defined by Kaneko [ Kan97 ] ; see Section 3.3 . Section 3.1 provides an inductive method for attacking this problem, but remains too unwieldy for Knuth’s stated goal of determining \#\operatorname{SubSemi}([8]^{3}) . Indeed, we would first need to diagonalize the matrix W([8]^{2}) which is k\times k with k=\frac{1}{2}B_{9,9}=22\,111\,390\,122\,811; given that storing such a matrix would require around 2 million zettabytes, this is simply too large for practical computation. The connection between commutative idempotent monoids and join-semilattices provides additional motivation for our work. Indeed, we undertook this project not with monoids in mind, but rather with the goal of understanding saturated transfer systems on lattices. These are combinatorial structures on subgroup lattices that are important in equivariant infinite loop space theory; see Section 4 and [ HMOO22 , Rub21 ] . In this context, M=\operatorname{Sub}G (for G a finite Abelian group) equipped with the join operation. It is a consequence of [ BCH+25 ] that saturated transfer systems on \operatorname{Sub}G are in bijective correspondence with \operatorname{SubMon}(\operatorname{Sub}G) . For G=C_{N} cyclic of order N=p_{1}^{n_{1}}\cdots p_{r}^{n_{r}} with p_{i} distinct primes and n_{i} natural numbers, \operatorname{Sub}C_{N}\cong[n_{1}]\times\cdots\times[n_{r}]. As such, the problem of enumerating saturated transfer systems on \operatorname{Sub}C_{N} is equivalent to Knuth’s problem on max-closed relations on \prod[n_{i}] , and Section 3.1 again provides traction. Remark 1.1 . Let \mathrm{CMon} denote the category of commutative monoids and monoid homomorphisms (see Section 2 for definitions), and write \mathrm{CMon}/[n] for the slice category of commutative monoids equipped with a homomorphism to [n] . We can view objects p\colon N\to[n] of \mathrm{CMon}/[n] as strongly multiplicative length n+1 filtrations by ideals. Here an ideal I is a subset I\subseteq N satisfying IN=I , and the filtration by ideals takes the form I_{n}\subseteq I_{n-1}\subseteq\cdots\subseteq I_{1}\subseteq I_{0}=N where I_{k}=p^{-1}[k,n] . In order to reconstruct a monoid homomorphism p\colon N\to[n] from such a chain of ideals, it must also satisfy the strongly multiplicative criterion I_{k}I_{\ell}\subseteq I_{k\vee\ell}\smallsetminus I_{(k\vee\ell)+1} where k\vee\ell=\max\{k,\ell\} . Observe that M\times[n] is naturally an object of \mathrm{CMon}/[n] via projection. In fact, the assignment M\mapsto M\times[n] is left adjoint to the forgetful functor \mathrm{CMon}/[n]\to\mathrm{CMon} , and thus we may view M\times[n] as the free commutative monoid equipped with a strongly multiplicative length n+1 filtration by ideals. This provides a categorical justification for studying M\times[n] and its submonoids beyond our applications to max-closed relations and saturated transfer systems. Overview We now briefly outline the rest of the paper. In Section 2 , we review some basics on monoids and submonoids, introduce the (weighted, directed) submonoid graph of a finite commutative monoid M , and use this to prove Section 2.1 , our most general theorem enumerating submonoids of M\times[n] . We specialize this theorem to M a commutative Abelian group in Section 2.1 , and conclude the section with some observations on generating functions. In Section 3 , we suppose that M is finite, commutative, and idempotent, and use these assumptions to derive a particularly special form for \#\operatorname{SubMon}(M\times[n]) in this case; see Section 3.1 . We use this to demonstrate that \#\operatorname{SubMon}(M\times[n]) is a constant-recursive sequence in this setting, and then make the constants in Section 3.1 explicit for a selection of finite commutative idempotent monoids.