arXiv:2607.23111 · v4
Leaf-discriminating trees for multiparameter counting of numerical semigroups
摘要
A numerical semigroup is a cofinite additive submonoid of ${\mathbb N}$. The largest element of the complement is its {\em Frobenius number} and the cardinality of its complement is the {\em genus}. We propose a new approach to counting semigroups by the Frobenius number and by the genus, by introducing two ad-hoc trees. Those are leaf-discriminating trees in the sense that their leaves correspond exactly to the objects we want to count and, so, exploring these trees instead of general trees is optimal. Our approach reduces the search space for genus to 23\% and for Frobenius to 0.03\% of that required by previous approaches and this allowed to obtain an important number of unkown terms from both sequences. We implemented a recursive descending algorithm based on the so-called seeds structure, trimming the general semigroup tree exactly at those nodes with no descendants with a given genus, in the first case, or with no descendants with a given Frobenius number, in the second case. We refined the parallelizing strategies and we overcame the previous limitation of the length of integers in the bitwise representation of the gap sequence and the seed sequence. We computed multiparameter decomposition of the numbers of semigroups of each Frobenius number up to $135$, the number of irreducible semigroups of Frobenius number up to $135$, and of the numbers of semigroups of each genus up to $80$.
作者备注：In the new version we removed the part on theoretical results and focused on the algorithms, the new construction of trees, and computational results. The theoretical part with combinatorial results and recurrences is now in a separated contribution