Multiparameter counting of numerical semigroups: recurrences and leaf-discriminating trees
Abstract
A numerical semigroup is a subset of the nonnegative integers, closed under addition and with finite complement. The size of the complement is its genus. The problem of counting semigroups by the largest gap got very important through the so-called Frobenius problem, first documented in 1884. Accordingly, the largest gap is called the Frobenius number. In the last two decades, counting by the genus has become a subject of even more intense study, mostly because of the non-solved conjectures on its monotonic and super-Fibonacci growth. 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 is optimal. On the theoretical side, it is known that the number of semigroups of each genus grows asymptotically with the genus as the Fibonacci numbers and that the number of semigroups of each Frobenius number grows asymptotically as a two-step doubling sequence. We prove a formula for the number of numerical semigroups of each Frobenius number F, genus g, and multiplicity m (first nonzero nongap), for m≥(F+1)/3. It is known that asymptotically almost all semigroups satisfy this inequality. This formula gives a multiparameter exact version of the increasing behaviours just mentioned. On the computational side, 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.
Related
- Porteous Meets Walsh: Counting Critical Points for ℋ2-Norm Model Order Reduction Using Algebraic Geometry Behind Multiparameter Eigenvalue Problems
- The type and cardinality of minimal presentations of numerical semigroups with embedding dimension four
- Power sums of critical points of gap polynomials for symmetric and pseudo-symmetric numerical semigroups
- Telescopic Structure of Numerical Semigroups Generated by Unsigned Stirling Numbers of the First Kind
- A power-sum obstruction to cyclotomicity in a family of symmetric numerical semigroups
BibTeX
@misc{brasamoros2026multiparameter,
title = {{Multiparameter counting of numerical semigroups: recurrences and leaf-discriminating trees}},
author = {Maria Bras-Amorós and Vicenç Torra},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.23111},
eprint = {2607.23111},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.23111},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Multiparameter counting of numerical semigroups: recurrences and leaf-discriminating trees
AU - Maria Bras-Amorós
AU - Vicenç Torra
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2607.23111
UR - https://arxiv.org/abs/2607.23111
AB - A numerical semigroup is a subset of the nonnegative integers, closed under addition and with finite complement. The size of the complement is its genus. The problem of counting semigroups by the largest gap got very important through the so-called Frobenius problem, first documented in 1884. Accordingly, the largest gap is called the Frobenius number. In the last two decades, counting by the genus has become a subject of even more intense study, mostly because of the non-solved conjectures on its monotonic and super-Fibonacci growth. 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 is optimal. On the theoretical side, it is known that the number of semigroups of each genus grows asymptotically with the genus as the Fibonacci numbers and that the number of semigroups of each Frobenius number grows asymptotically as a two-step doubling sequence. We prove a formula for the number of numerical semigroups of each Frobenius number F, genus g, and multiplicity m (first nonzero nongap), for m≥(F+1)/3. It is known that asymptotically almost all semigroups satisfy this inequality. This formula gives a multiparameter exact version of the increasing behaviours just mentioned. On the computational side, 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.
ER -