Leaf-discriminating trees for multiparameter counting of numerical semigroups
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Leaf-discriminating trees for multiparameter counting of numerical semigroups".
Jane: Here's the gist of the paper. A new approach to counting numerical semigroups by their Frobenius number and genus is proposed using two ad-hoc leaf-discriminating trees that significantly reduce the search space compared to previous methods.
Tom: Theoretical Foundation of Recurrences The paper proves multiparameter recurrence relations and proposes a new approach to counting semigroups by the Frobenius number and by the genus through leaf-discriminating trees.
Jane: On the theoretical side, it is known that the number of semigroups of each genus grows asymptotically with the genus like the Fibonacci numbers and that the number of semigroups of each Frobenius number grows asymptotically in such a way that each number doubles the previous but one.
Tom: The authors prove a formula for the number of numerical semigroups of each Frobenius number, genus, and multiplicity (first nonzero nongap), under the assumption that the multiplicity m and the Frobenius number F satisfy m ⩾ F +1/3.
Paper summary: Tom: So, to wrap up this paper, "Leaf-discriminating trees for multiparameter counting of numerical semigroups," the main contribution is providing a formula for the exact values of nF m g under the condition that the multiplicity is greater than or equal to the Frobenius number plus one third.
Jane: And they also present a new version of the seeds algorithm specifically adapted for counting by genus and for giving those numbers for each combination of those three first jumps.
Lu: The authors provide a detailed multiparameter decomposition of these counts with respect to multiplicity and genus, which is really helpful for understanding the structure underlying these sequences.
Meng: I see how this helps the theoretical side, but what about the practical deployment? Is this method efficient enough to run on real traffic scenarios without needing massive pre-computation?
Tom: The efficiency comes from reducing the search space substantially—twenty-three percent for genus and zero point zero three percent for Frobenius number counting compared to previous methods.
Jane: And they also show that their adaptation of the seeds algorithm reduces the search space by twenty-three percent compared to RGD unleaved algorithms, which is a concrete computational win.
Lu: The paper establishes a multiparameter exact version of those increasing behaviors, proving the growth patterns for both the Frobenius number and genus using these specific parameter relationships.
Meng: It sounds like this work solidifies some of the theoretical boundaries on how fast these counts can grow under certain conditions related to m and F.
Tom: Yes, it provides a formula for exact values under those conditions, which is what I find most valuable from an engineering standpoint; having a precise calculation instead of just an estimate.
Jane: Ultimately, this research gives us a new set of tools—the leaf-discriminating trees and the derived formulas—to count numerical semigroups much more precisely and efficiently than we could before.
Conclusion: Tom: So, we've looked at how this paper uses these special leaf-discriminating trees to count numerical semigroups using their Frobenius number and genus.
Jane: It seems like the core idea here is using a smarter way to navigate the space of all possible semigroups instead of just guessing through every single possibility.
Lu: The authors are essentially building two specific types of trees, one for counting by genus and one for counting by Frobenius number, and showing that looking only at the leaves of these trees gets you exactly what you want to count.
Meng: So instead of checking every single semigroup in a huge set, you prune the search space down really aggressively before even starting the main calculation.
Tom: Exactly. And they've managed to get this pruning done so that they only need twenty-three percent of the original search space for genus and zero point zero three percent for Frobenius number counting.
Jane: That reduction in search space is significant, especially when those counts are growing exponentially, right? It means you can handle problems that were previously just too big to even attempt.
Lu: And on the theoretical side, they've proven exact formulas for these counts under certain conditions involving the multiplicity and the Frobenius number.
Tom: That's a big deal because it gives us not just an algorithm, but a mathematical certainty for how many of these structures exist.
Jane: It moves this from just being a clever counting trick to providing an exact structure we can actually calculate with confidence.
Meng: For practical deployment, that means if we have a really complex system that generates these semigroups, this method is way more efficient at finding the exact numbers needed for analysis.
Tom: It's about getting precise data faster and without wasting computing power on things we don't need to know about.
Jane: But what does all this mean for us outside of pure math? It suggests a new kind of toolset for analyzing complex mathematical systems that pop up in science or even computer science.
Lu: It opens the door to exploring these structures in ways that were previously computationally infeasible, which is where the real impact lies.
Tom: So, we've seen how they build this better search mechanism and what precise formulas they derive from it for counting numerical semigroups.
Maria Bras-Amor´os, Vicen¸c Torra
cs.DM, math.AC, math.CO
Submitted: 2026-07-25
Updated: 2026-11-09
Comments: 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
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Importance score: 83/100
The gist: A new approach to counting numerical semigroups by their Frobenius number and genus is proposed using two ad-hoc leaf-discriminating trees that significantly reduce the search space compared to…
Key concepts
- Frobenius Number (F)
- The largest integer that cannot be expressed as a non-negative integer linear combination of the generators of a numerical semigroup. The paper focuses on counting semigroups based on this value, showing how the number of such semigroups grows in a predictable pattern.
- Genus (g)
- A measure related to the structure of a numerical semigroup, representing how far it is from being a complete intersection. The paper analyzes how the count of semigroups changes as their genus increases, linking it to Fibonacci-like growth.
- Leaf-discriminating Trees
- These are specific tree structures used in the algorithm that are optimized for counting. Their leaves directly correspond to the numerical semigroups being counted, making them much more efficient than exploring general trees for this counting task.
- Multiplicity (m)
- The smallest positive integer in a numerical semigroup, which is essentially its first nonzero nongap. The paper establishes exact formulas for the number of semigroups based on the relationship between the multiplicity and the Frobenius number.
Terminology
Summary
A new approach to counting numerical semigroups by their Frobenius number and genus is proposed using two ad-hoc leaf-discriminating trees that significantly reduce the search space compared to previous methods. p. 0 We prove multiparameter recurrence relations and 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.Where the paper says it
Theoretical Foundation of Recurrences
The paper proves multiparameter recurrence relations and proposes a new approach to counting semigroups by the Frobenius number and by the genus through leaf-discriminating trees. On the theoretical side, it is known that the number of semigroups of each genus grows asymptotically with the genus like the Fibonacci numbers and that the number of semigroups of each Frobenius number grows asymptotically in such a way that each number doubles the previous but one. p. 0 03% of that required by previous approaches and this allowed to obtain
an important number of unkown terms from both sequences. On the theoretical side, it is known that the number of semigroups of each
genus grows asymptotically with the genus like the Fibonacci numbers and that
the number of semigroups of each Frobenius number grows asymptotically in such
a way that each number doubles the previous but one. On the theoretical side, it is known that the number of semigroups of each
genus grows asymptotically with the genus like the Fibonacci numbers and that
the number of semigroups of each Frobenius number grows asymptotically in such
a way that each number doubles the previous but one. We prove a formula for the
number of numerical semigroups of each Frobenius number, genus, and multiplicity (first nonzero nongap), under the assumption that the multiplicity m and the
Frobenius number F satisfy m ⩾
F +1
3
. It is known that asymptotically almost all
semigroups satisfy this condition. This formula gives, under the required restriction, a multiparameter exact version of the increasing behaviours just mentioned. 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 prove multiparameter recurrence relations and propose a new approach to counting semigroups by
the Frobenius number and by the genus, by introducing two ad-hoc trees.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Algorithmic Improvements and Tree Structures
The computational side involves implementing 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 or Frobenius number. The authors introduce two ad-hoc trees: 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. p. 0 We prove multiparameter recurrence relations and 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. In this work, we introduce the general leaf-discriminating trees as an extension of
the unleaved tree used in the RGD-unleaved algorithm, now for counting semigroups
either by the genus or by the Frobenius number. The genus-leaf-discriminating tree
is what was called the unleaved tree in [6]. The genus-leaf-discriminating tree
is what was called the unleaved tree in [6]. The Frobenius-leaf-discriminating tree will
contain only nodes with descendants with a given Frobenius number and its leaves will
be exactly the semigroups of that given Frobenius number.Where the paper says it
Where the paper says it
Where the paper says it
Computational Results and Efficiency
The approach reduces the search space for genus to 23% and for Frobenius to 0. p. 0 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. 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. With this
parallelization we obtained n78 = 76122842716469053, n79 = 123262186663081640,
n80 = 199583757387067387, as well as the number of semigroups of each Frobenius
number up to 132. Using the same algorithm we also computed the number of irreducible numerical semigroups, that is, semigroups that can not be obtained as a proper
intersection of two semigroups, for Frobenius number up to 132 (i. The idea of pruning branches of the general
tree has previously been used in the context of the search of counterexamples of Wilf’s
conjecture [26] (or to the related Eliahou’s conditions [12]) in [8, 9], in which nodes
whose descendants are known to verify the conjectures are not further explored. In this work, we introduce the general leaf-discriminating trees as an extension of
the unleaved tree used in the RGD-unleaved algorithm, now for counting semigroups
either by the genus or by the Frobenius number.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Key Findings on Growth Behaviors
The paper establishes a multiparameter exact version of the increasing behaviors mentioned earlier, proving that if m ⩾ F + 2/3, then nF,m = 2nF −2,m−1. Furthermore, they prove the two-step doubling growth by the Frobenius number and the Fibonacci-like growth by the genus. p. 6 Then, from these formulas we
will derive the multiparameter versions of the two-step doubling growth of the number
of semigroups by Frobenius number (Theorem 2. 10) and the Fibonacci-like growth of
the number of semigroups by genus (Theorem 2. (4)
Define now
γd,F (A) = F − 2 − #A − σd(A)
νd,m(A) = m − 2 − σd(A)
From the definitions of γd,F (A) and νd,m(A), and by (1), one can deduce that, if F −
2m = d, for any A ∈ Bd, whenever d ⩾ 0,
νd,m(A) ⩽ γd,F (A). (5)
A #A span1
(A) σ1(A) γ1,F (A) ν1,m(A)
∅ 0 ∅ 0 F − 2 m − 2
Table 4: Sets in B1
A #A span2
(A) σ2(A) γ2,F (A) ν2,m(A)
∅ 0 ∅ 0 F − 2 m − 2
Table 5: Sets in B2
A #A span3
(A) σ3(A) γ3,F (A) ν3,m(A)
∅ 0 ∅ 0 F − 2 m − 2
{1} 1 {1, 2} 2 F − 5 m − 4
{2} 1 {2} 1 F − 4 m − 3
Table 6: Sets in B3
To illustrate all these definitions, in Table 4 to Table 11 we provide the list of all sets
in B1, B2, .Where the paper says it
Where the paper says it
Conclusion and Contributions
The research provides a formula for the exact values of nF,m,g under the condition m ⩾ F +1/3. The authors present a new version of the seeds algorithm for counting semigroups by genus and also for giving the number of semigroups of each genus and each combination of the three first jumps. p. 2 We provide efficient ways to parallelize the algorithm by a detailed analysis of the
abundance of the semigroups of each combination of the first three jumps. With this
parallelization we obtained n78 = 76122842716469053, n79 = 123262186663081640,
n80 = 199583757387067387, as well as the number of semigroups of each Frobenius
number up to 132. , for genus up to
64). In addition, we have (i) the multiparameter decomposition of all numbers ng up
to n80, by splitting by the multiplicity, and second and third jumps; (ii) the multiparameter decomposition of the number of semigroups of each Frobenius number up to
132, by splitting by the genus and multiplicity. 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.Where the paper says it
Where the paper says it
Where the paper says it
Acknowledgements
This research is supported by project PID2024-156636NB-C21 (MATSE), funded by MCIN/AEI/10.13039/501100011033/ FEDER, UE, the project RED2024-153572-T, funded by MICIU/AEI/10.13039/50110066, and by the project “HERMES” funded by the European Union NextGenerationEU/PRTR via INCIBE. p. 8 A #A span4
(A) σ4(A) γ4,F (A) ν4,m(A)
∅ 0 ∅ 0 F − 2 m − 2
{1} 1 {1, 2} 2 F − 5 m − 4
{3} 1 {3} 1 F − 4 m − 3
Table 7: Sets in B4
A #A span5
(A) σ5(A) γ5,F (A) ν5,m(A)
∅ 0 ∅ 0 F − 2 m − 2
{1} 1 {1, 2} 2 F − 5 m − 4
{2} 1 {2, 4} 2 F − 5 m − 4
{3} 1 {3} 1 F − 4 m − 3
{4} 1 {4} 1 F − 4 m − 3
{1, 2} 2 {1, 2, 3, 4} 4 F − 8 m − 6
{1, 3} 2 {1, 2, 3, 4} 4 F − 8 m − 6
{2, 4} 2 {2, 4} 2 F − 6 m − 4
{3, 4} 2 {3, 4} 2 F − 6 m − 4
Table 8: Sets in B5
1. The sets in the union in the definition of MF,m(A) are disjoint. Unfortunately, the current implementation does not
scale up for genus larger than 64. The terms n76 and n77 were obtained in [6] using another algorithm, the rightgenerators descendant algorithm (RGD). g =13 g =14 g =15 g =16 g =17 g =18 g =19 g =20 g =21 g =22 g =23 g =24 total
m = 2 0 m = 3 0 m = 4 0 m = 5 2 5 8 9 8 6 3 1 42 m = 6 0 m = 7 4 12 23 32 31 23 13 5 1 144 m = 8 0 m = 9 4 19 45 73 87 76 49 23 7 1 384 m = 10 2 14 44 83 106 97 64 29 8 1 448 m = 11 1 9 36 84 126 126 84 36 9 1 512 m = 12 0 m = 13 1 10 45 120 210 252 210 120 45 10 1 1024 m = 14 1 9 36 84 126 126 84 36 9 1 512 m = 15 1 8 28 56 70 56 28 8 1 256 m = 16 1 7 21 35 35 21 7 1 128 m = 17 1 6 15 20 15 6 1 64 m = 18 1 5 10 10 5 1 32 m = 19 1 4 6 4 1 16 m = 20 1 3 3 1 8 m = 21 1 2 1 4 m = 22 1 1 2 m = 23 1 1 m = 24 0 m = 25 1 1
total 14 70 211 446 688 790 675 424 190 58 11 1 Σ = 3578
Table 1: Values of #SF =24,m,g and #SF =24,m. g =13 g =14 g =15 g =16 g =17 g =18 g =19 g =20 g =21 g =22 g =23 g =24 g =25 total
m = 2 1 1 m = 3 1 1 1 1 1 5 m = 4 4 5 4 4 3 2 1 23 m = 5 0 m = 6 8 16 25 27 24 17 10 4 1 132 m = 7 6 16 31 42 46 40 27 14 5 1 228 m = 8 8 26 54 76 82 68 42 19 6 1 382 m = 9 8 31 71 115 140 134 99 56 24 7 1 686 m = 10 4 24 69 128 170 168 126 72 30 8 1 800 m = 11 2 16 58 127 189 203 161 93 37 9 1 896 m = 12 1 10 45 120 210 252 210 120 45 10 1 1024 m = 13 1 11 55 165 330 462 462 330 165 55 11 1 2048 m = 14 1 10 45 120 210 252 210 120 45 10 1 1024 m = 15 1 9 36 84 126 126 84 36 9 1 512 m = 16 1 8 28 56 70 56 28 8 1 256 m = 17 1 7 21 35 35 21 7 1 128 m = 18 1 6 15 20 15 6 1 64 m = 19 1 5 10 10 5 1 32 m = 20 1 4 6 4 1 16 m = 21 1 3 3 1 8 m = 22 1 2 1 4 m = 23 1 1 2 m = 24 1 1 m = 25 0 m = 26 1 1
total 44 157 424 860 1360 1676 1600 1170 643 256 70 12 1 Σ = 8273
Table 2: Values of #SF =25,m,g and #SF =25,m. Then, from these formulas we
will derive the multiparameter versions of the two-step doubling growth of the number
of semigroups by Frobenius number (Theorem 2. 10) and the Fibonacci-like growth of
the number of semigroups by genus (Theorem 2. We will base all our results on the definition of the sets
of subsets Bd that follows. We want to remark that this definition is equivalent to
that of the set of subsets denoted Ak in Zhao’s reference [28], with k = d. We will characterize the
genus-leaf-discriminating tree and the Frobenius-leaf discriminating tree. Then we will
explain how the pruned trees are constructed by means of deciding at each node which
descendants should be in the pruned tree and which ones should not.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved counting of numerical semigroups by genus using leaf-discriminating trees reduces search space for genus to 23% and for Frobenius number to 0.03% compared to previous approaches, allowing for an important number of unknown terms from both sequences.
-
Development of a multiparameter exact formula for the number of numerical semigroups with Frobenius number F, multiplicity m and genus g under the assumption that m is greater than or equal to F plus one third provides a multiparameter exact version of the increasing behaviors observed in asymptotic growth.
-
Implementation of a seeds-based algorithm adapted to explore genus-leaf-discriminating trees allows for efficient counting by genus while reducing the search space to 23% of that required by previous algorithms exploring the whole semigroup tree, achieving computation times significantly faster than RGD-unleaved algorithms.
-
Introduction of parallelization strategies based on the abundance of semigroups with combinations of the first three jumps enables efficient computation for counting by genus, with computational demands balanced according to a priority scheme based on m and u plus v.
-
Creation of a new algorithm for exploring the Frobenius-leaf-discriminating tree allows for computing NF (the number of numerical semigroups with Frobenius number F) up to 132 and the number of irreducible semigroups for that range, which are published in OEIS A158206.
Abstract
A numerical semigroup is a cofinite additive submonoid of N. The largest element of the complement is its Frobenius number and the cardinality of its complement is the 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.
Sources
- Exploring the unleaved tree of numerical semigroups up to a given genus
- The shape of a random numerical semigroup
- Trimming the numerical semigroups tree to probe Wilf's conjecture to higher genus
- Algorithms for numerical semigroups with fixed maximum primitive
- On counting numerical semigroups by maximum primitive and Wilf's conjecture
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns