Leaf-discriminating trees for multiparameter counting of numerical semigroups

arXiv:2607.23111 · cs.DM, math.AC, math.CO · Submitted 2026-07-25 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

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.

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. p. 0
Where the paper says it

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 .

This formula gives a multiparameter exact version of the increasing behaviours just mentioned. p. 0
Where the paper says it

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.

Specifically, they prove that if m ⩾ F + 2/3, then nF,m,g = nF −2,m−1,g−1 + nF −2,m−1,g−2. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

The genus-leaf-discriminating tree is what was called the unleaved tree in [6]. p. 2
Where the paper says it

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 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. p. 2
Where the paper says it

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.

Computational Results and Efficiency

The approach reduces the search space for genus to 23% and for Frobenius to 0. p. 0

Where the paper says it

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. p. 0
Where the paper says it

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.

The authors computed multiparameter decomposition of the numbers of semigroups up to certain limits and obtained specific large values such as n78 = 76122842716469053. p. 2
Where the paper says it

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 seeds algorithm is shown to be the most efficient algorithm to explore the semigroup tree, and its adaptation to the genus-leaf-discriminating tree reduces the search space by 23% compared to RGD-unleaved algorithms. p. 2
Where the paper says it

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.

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

Where the paper says it

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.

This is achieved through a detailed analysis of sets defined in terms of parameters d, A, σd(A), γd,F(A), and νd,m(A). p. 7
Where the paper says it

(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, .

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

Where the paper says it

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.

They also compute the multiparameter decomposition of these numbers with respect to multiplicity and genus. p. 2
Where the paper says it

, 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.

The approach reduces the search space for genus to 23% and for Frobenius to 0.03% of that required by previous approaches. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. This research was conducted using the resources of High Performance Computing Center North (HPC2N). p. 1
Where the paper says it

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).

The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grants agreement no. 2025-22-1579, NAISS 2026/3-170. p. 3
Where the paper says it

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.

The authors would like to thank Axel Bacher and Roman Iakymchuk for their comments and Nathan Kaplan for interesting remarks, and specially for suggesting the alternative proof of Theorem 2. p. 6
Where the paper says it

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.

12 in Remark 2. p. 6
Where the paper says it

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.

13, by means of Kunz coordinates. p. 2
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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

Related papers