Rationality conjecture for submonoid generating functions

About 1 year old · traced to 2025

Let

G(x,y,z)=\sum_{\ell,m,n\geq 0}\#\operatorname{SubMon}([\ell-1]\times[m-1]\times[n-1])\frac{x^\ell y^m z^n}{\ell!m!n!}

be the multivariable exponential generating function for submonoids of products of finite commutative monoids. Rationality conjecture. The generating function $G(x,y,z)$ is a rational function in $e^x,e^y,e^z$ , and the corresponding higher-order multivariable generating function for $\#\operatorname{SubMon}(\prod_i [n_i-1])$ is likewise rational in the exponentials of its variables. This conjecture is motivated by the known one- and two-variable specializations and by partial information obtained from the eigenvalue expansion; the higher-dimensional rationality remains open.

References

Primary source

Caoilainn Kirkpatrick, Amelie el Mahmoud, Kyle Ormsby, Angélica M. Osorno, Dale Schandelmeier-Lynch, Riley Shahar, Lixing Yi, Avery Young and Saron Zhu, “Enumerating submonoids of finite commutative monoids”, arXiv:2508.20786 (2025).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

An unverified reader-written argument claims the conjecture fails in three or more dimensions, but no independent source has checked it.

The conjecture, formulated as Conjecture 3.16 by Kirkpatrick and coauthors in 2025, asks whether $G(x,y,z)$ is rational in $e^x,e^y,e^z$ , with analogous claims in every higher dimension.

Known results

Kirkpatrick et al. (2025): for fixed finite idempotent $P$ , submonoid counts of $P\times[n]$ have a finite eigenvalue expansion $\sum_{\lambda}b_\lambda\lambda^n$ .
The same preprint records supporting one- and two-variable formulas, but says transfer-matrix methods do not control the symmetry needed for three or more factors.

Undated counterexample claim

A reader-written argument claims that a rank-layer construction yields at least $2^{\binom{n+1}{2}}$ submonoids on the diagonal, forcing zero convergence radius after specialization and contradicting exponential rationality; it claims the conjecture fails in all dimensions at least three. This complete counterexample claim has not been independently verified.

Current status (as of August 2026): The conjecture has an unverified claimed counterexample in dimensions at least three; no verified disproof or proof is recorded, and the lower-dimensional cases remain supported by known formulas.

Sources

CounterexampleThis solution needs a summarySee full solutionHide full solution

Counterexample: the trivariate generating function is not rational in the exponentials.

Let a_(l,m,n) be the number of submonoids of [l-1] x [m-1] x [n-1] under coordinatewise maximum, as in Conjecture 3.16 of arXiv:2508.20786. For n >= 2, consider the antichain

A_n = {(i,j,k) in {0,...,n-1}^3 : i+j+k=n-1}.

Its cardinality is binom(n+1,2). For each subset S of A_n, let M_S consist of the zero vector and all finite coordinatewise joins of members of S. This is a submonoid. The join of two distinct members of A_n has coordinate sum strictly greater than n-1, so M_S intersect A_n = S. Therefore all these submonoids are distinct and

a_(n,n,n) >= 2^binom(n+1,2).

Suppose, for contradiction, that G(x,y,z) = sum a_(l,m,n)x^l y^m z^n/(l!m!n!) were rational in e^x,e^y,e^z. Then there would be polynomials P,Q, with Q nonzero, satisfying

Q(e^x,e^y,e^z) G(x,y,z) = P(e^x,e^y,e^z)

as formal power series. Choose a positive integer L greater than every exponent appearing in Q, and substitute (x,y,z)=(t,Lt,L^2t). Distinct exponent triples of Q then give distinct integers i+Lj+L^2k, so q(t)=Q(e^t,e^(Lt),e^(L^2t)) is a nonzero analytic function. The resulting formal identity q(t)g(t)=p(t) implies that any zero of q at t=0 is canceled by p: hence g(t)=G(t,Lt,L^2t) is analytic near zero.

However all coefficients of g are nonnegative, and its diagonal term gives

[t^(3n)]g(t) >= L^(3n) 2^binom(n+1,2)/(n!)^3.

The right-hand side has unbounded (3n)-th root, so g has radius of convergence zero. This contradicts analyticity. Thus the trivariate rationality conjecture is false. The identical rank-layer argument refutes every higher-dimensional version with at least three variables; the known one- and two-variable rational formulas remain unaffected.