Let N 0 denote the set of non-negative integers. A numerical semigroup is a subset of N 0 which is closed under addition, contains 0, and its complement in N 0 is finite.
Numerical semigroups model, for instance, the amounts of money that can be withdrawn from an ideal cash point or the number of nodes of combinatorial configurations [BS12]. They appear in algebraic geometry, as they model Weierstrass non-gaps, and in music theory as they are the inherent structure of the set of numbers of semitones of the intervals of each overtone of a given fundamental tone with respect to the fundamental tone, when the physical model of the harmonic series is discretized into an equal temperament [Bra17].
For a numerical semigroup Λ the elements in N 0 \ Λ are called gaps and the number of gaps is the genus of the semigroup. The largest gap is called the Frobenius number and the non-gap right after the Frobenius number is the conductor. The multiplicity m of a numerical semigroup is its first non-zero non-gap. A numerical semigroup different than N 0 is said to be ordinary if its gaps are all in a row. The generators of a numerical semigroup are those non-zero non-gaps which can not be obtained as the sum of two smaller non-gaps. One general reference for numerical semigroups is [RG09].
As an example, the set Λ = {0, 4, 5, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, . . . } is a numerical semigroup with Frobenius number 11, conductor 12, genus 6 and multiplicity 4. Its generators are 4 and 5.
It was conjectured in [Bra08] that the number n g of numerical semigroups of genus g asymptotically behaves like the Fibonacci numbers. More precisely, it was conjectured that n g ≥ n g−1 + n g−2 , that the limit of the ratio ng ng−1+ng−2 is 1 and so that the limit of the ratio ng ng−1 is the the golden ratio φ = 1+ √ 5
2 . Many other papers deal with the sequence n g [Kom89, Kom98, Bra09, BdM07, BB09, Eli10, Zha10, BGP11, Kap12, BR12, Bra12, ODo13, BT17, FH16, BF18, Kap17] and Alex Zhai gave a proof for the asymptotic Fibonacci-like behavior of n g [Zha13]. However, it has still not been proved that n g is increasing.
We will see how we can approach this problem and other problems using three different constructions of trees and forests whose nodes are numerical semigroups.
All numerical semigroups can be organized in an infinite tree T whose root is the semigroup N 0 and in which the parent of a numerical semigroup Λ is the numerical semigroup Λ obtained by adjoining to Λ its Frobenius number. For instance, the parent of the semigroup Λ = {0, 4, 5, 8, 9, 10, 12, . . . } is the semigroup Λ = {0, 4, 5, 8, 9, 10, 11, 12, . . . }. In turn, the descendants of a numerical semigroup are the semigroups we obtain by taking away one by one the generators that are larger or equal to the conductor of the semigroup. The parent of a numerical semigroup of genus g has genus g − 1 and all numerical semigroups are in T, at a depth equal to its genus. In particular, n g is the number of nodes of T at depth g. This construction was already considered in [RGGJ03]. Figure 1 shows the tree up to depth 7.
In [Bra12] a new tree construction is introduced as follows. The ordinarization transform of a non-ordinary semigroup Λ with Frobenius number F and multiplicity m is the set Λ = Λ \ {m} ∪ {F }. For instance, the ordinarization transform of the semigroup Λ = {0, 4, 5, 8, 9, 10, 12, . . . } is the semigroup Λ = {0, 5, 8, 9, 10, 11, 12, . . . }.
As an extension, the ordinarization transform of an ordinary semigroup is itself. Note that the genus of the ordinarization transform of a semigroup is the genus of the semigroup. The definition of the ordinarization transform of a numerical semigroup allows the construction of a tree T g on the set of all numerical semigroups of a given genus rooted at the unique ordinary semigroup of this genus, where the parent of a semigroup is its ordinarization transform and the descendants of a semigroup are the semigroups obtained by taking away a generator larger than the Frobenius number and adding a new non-gap smaller than the multiplicity in a licit place. To illustrate this construction with an example in Figure 2 we depicted T 7 .
One significant difference between T g and T is that the first one has only a finite number of nodes, indeed, it has n g nodes, while T is an infinite tree. It was conjectured in [Bra12] that the number of numerical semigroups in T g at a given depth is at most the number of numerical semigroups in T g+1 at the same depth. This was proved in the same reference for the lowest and largest depths. This conjecture would prove that n g+1 ≥ n g .
Almost-ordinary semigroups are those semigroups for which the multiplicity equals the genus and so, there is a unique gap larger than m. The sub-Frobenius number of a non-ordinary semigroup Λ with conductor c is the Frobenius number of Λ ∪ {c − 1}. The subconductor and dominant of a semigroup are, respectively, the smallest and largest integers in its interval of non-gaps immediately previous to the conductor. If Λ is a nonordinary and non almost-ordinary semigroup, with multiplicity m and genus g, and sub-Frobenius number u, then Λ ∪ {u} \ {m} is another numerical semigroup which we denote the almost-ordinarization transform of Λ. For instance, the almost-ordinarization transform of the semigroup Λ = {0, 4, 5, 8, 9, 10, 12, . . . } is the semigroup Λ = {0, 5, 7, 8, 9, 10, 12, . . . }. This transform can be applied subsequently and at some step we will attain the unique almost-ordinary semigroup of that genus and conductor, that is, the semigroup {0, g, g + 1, . . . , c − 2, c, c + 1, . . . }. This defines, for each fixed genus and conductor, a tree rooted at this unique almost-ordinary semigroup of that genus and conductor. The parent of a semigroup is its almost-ordinarization. The descendants of a numerical semigroup are the semigroups we obtain by taking away one by one the generators between the subconductor and the dominant of the semigroup and adjoining a non-gap in a licit place between 0 and the multiplicity of the semigroup.
Figure 3 shows the forest of genus 7.
The author was supported by the Spanish government under grant TIN2016-80250-R and by the Catalan government under grant 2014 SGR 537.