Quasi-Ordinarization Transform of a Numerical Semigroup

Abstract

In this study, we present the notion of the quasi-ordinarization transform of a numerical semigroup. The set of all semigroups of a fixed genus can be organized in a forest whose roots are all the quasi-ordinary semigroups of the same genus. This way, we approach the conjecture on the increasingness of the cardinalities of the sets of numerical semigroups of each given genus. We analyze the number of nodes at each depth in the forest and propose new conjectures. Some properties of the quasi-ordinarization transform are presented, as well as some relations between the ordinarization and quasi-ordinarization transforms.

1. Introduction

A numerical semigroup is a cofinite submonoid of ${\mathbb{N}}_0$ under addition, where ${\mathbb{N}}_0$ is the set of nonnegative integers.

While the symmetry of structures has traditionally been studied with the aid of groups, it is also possible to relax the definition of symmetry, so as to describe some forms of symmetry that arise in quasicrystals, fractals, and other natural phenomena, with the aid of semigroups or monoids, rather than groups. For example, Rosenfeld and Nordahl [1] lay the groundwork for such a theory of symmetry based on semigroups and monoids, and they cite some applications in chemistry.

Suppose that $\mathrm{\Lambda }$ is a numerical semigroup. The elements in the complement ${\mathbb{N}}_0\setminus \mathrm{\Lambda }$ are called the gaps of the semigroup and the number of gaps is its genus. The Frobenius number is the largest gap and the conductor is the non-gap that equals the Frobenius number plus one. The first non-zero non-gap of a numerical semigroup (usually denoted by m) is called its multiplicity. An ordinary semigroup is a numerical semigroup different from ${\mathbb{N}}_0$ in which all gaps are in a row. The non-zero non-gaps of a numerical semigroup that are not the result of the sum of two smaller non-gaps are called the generators of the numerical semigroup. It is easy to deduce that the set of generators of a numerical semigroup must be co-prime. One general reference for numerical semigroups is [2].

To illustrate all these definitions, consider the well-tempered harmonic semigroup $H=\{0,12,19,24,28,31,34,36,38,40,42,43,45,46,47,48,\dots \}$, where we use $“\dots ”$ to indicate that the semigroup consecutively contains all the integers from the number that precedes the ellipsis. The semigroup H arises in the mathematical theory of music [3]. It is obviously cofinite and it contains zero. One can also check that it is closed under addition. Hence, it is a numerical semigroup. Its Frobenius number is 44, its conductor is 45, its genus is 33, and its multiplicity is 12. Its generators are $\{12,19,28,34,42,45,49,51\}$.

The number of numerical semigroups of genus g is denoted $n_g$. It was conjectured in [4] that the sequence $n_g$ asymptotically behaves as the Fibonacci numbers. In particular, it was conjectured that each term in the sequence is larger than the sum of the two previous terms, that is, $n_g\ge n_{g-1}+n_{g-2}$ for $g\ge 2$, with each term being increasingly similar to the sum of the two previous terms as g approaches infinity, more precisely ${lim}_{g\to \infty }\frac{n_g}{n_{g-1}+n_{g-2}}=1$ and, equivalently, ${lim}_{g\to \infty }\frac{n_g}{n_{g-1}}=\varphi =\frac{1+\sqrt{5}}{2}$. A number of papers deal with the sequence $n_g$ [5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]. Alex Zhai proved the asymptotic Fibonacci-like behavior of $n_g$ [21]. However, it remains unproven that $n_g$ is increasing. This was already conjectured by Bras-Amorós in [22]. More information on $n_g$, as well as the list of the first 73 terms can be found in entry A007323 of The On-Line Encyclopedia of Integer Sequences [23].

It is well known that all numerical semigroups can be organized in an infinite tree $\mathcal{T}$ whose root is the semigroup ${\mathbb{N}}_0$ and in which the parent of a numerical semigroup $\mathrm{\Lambda }$ is the numerical semigroup ${\mathrm{\Lambda }}^{\prime }$ obtained by adjoining to $\mathrm{\Lambda }$ its Frobenius number. For instance, the parent of the semigroup $H=\{0,12,19,24,28,31,34,36,38,40,42,43,45,46,47,48,\dots \}$ is the semigroup $H^{\prime }=\{0,12,19,24,28,31,34,36,38,40,42,43,\mathbf{44},45,46,47,48,\dots \}$. In turn, the children of a numerical semigroup are the semigroups we obtain by taking away the generators one by one that are larger than 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 $\mathcal{T}$, at a depth equal to its genus. In particular, $n_g$ is the number of nodes of $\mathcal{T}$ at depth g. This construction was already considered in [24]. Figure 1 shows the tree up to depth 7.

In [9], a new tree construction is introduced as follows. The ordinarization transform of a non-ordinary semigroup $\mathrm{\Lambda }$ with Frobenius number F and multiplicity m is the set ${\mathrm{\Lambda }}^{\prime }=\mathrm{\Lambda }\setminus \left\{m\right\}\cup \left\{F\right\}$. For instance, the ordinarization transform of the semigroup $H=\{0,\mathbf{12},19,24,28,31,34,36,38,40,42,43,45,46,47,48,\dots \}$ is the semigroup $H^{\prime }=\{0,19,24,28,31,34,36,38,40,42,43,\mathbf{44},45,46,47,48,\dots \}$ The ordinarization transform of an ordinary semigroup is then defined to be 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 ${\mathcal{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 children of a semigroup are the semigroups obtained by taking away the generators one by one that are 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 ${\mathcal{T}}_7$.

One significant difference between ${\mathcal{T}}_g$ and $\mathcal{T}$ is that the first one has only a finite number of nodes. In fact, it has $n_g$ nodes, while $\mathcal{T}$ is an infinite tree. It was conjectured in [9] that the number of numerical semigroups in ${\mathcal{T}}_g$ at a given depth is at most the number of numerical semigroups in ${\mathcal{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}\ge n_g$.

In Section 2, we will construct the quasi-ordinarization transform of a general semigroup, paralleling the ordinarization transform. If the quasi-ordinarization transform is applied repeatedly to a numerical semigroup, it ends up in a quasi-ordinary semigroup. In Section 3, we define the quasi-ordinarization number of a semigroup as the number of successive quasi-ordinarization transforms of the semigroup that give a quasi-ordinary semigroup. Section 4 analyzes the number of numerical semigroups of a given genus and a given quasi-ordinarization number in terms of the given parameters. We present the conjecture that the number of numerical semigroups of a given genus and a fixed quasi-ordinarization number increases with the genus and we prove it for the largest quasi-ordinarization numbers. In Section 5, we present the forest of semigroups of a given genus that is obtained when connecting each semigroup to its quasi-ordinarization transform. The forest corresponding to genus g is denoted ${\mathcal{F}}_g$. Section 6 analyzes the relationships between $\mathcal{T}$, ${\mathcal{T}}_g$, and ${\mathcal{F}}_g$.

From the perspective of the forests of numerical semigroups here presented, the conjecture in Section 4 translates to the conjecture that the number of numerical semigroups in ${\mathcal{F}}_g$ at a given depth is at most the number of numerical semigroups in ${\mathcal{F}}_{g+1}$ at the same depth. The results in Section 4 provide a proof of the conjecture for the largest depths. Proving this conjecture for all depths, would prove that $n_{g+1}\ge n_g$. Hence, we expect our work to contribute to the proof of the conjectured increasingness of the sequence $n_g$ (A007323).

2. Quasi-Ordinary Semigroups and Quasi-Ordinarization Transform

Quasi-ordinary semigroups are those semigroups for which $m=g$ and so, there is a unique gap larger than m. The sub-Frobenius number of a non-ordinary semigroup $\mathrm{\Lambda }$ with Frobenius number F is the Frobenius number of $\mathrm{\Lambda }\cup \left\{F\right\}$.

The subconductor of a semigroup with Frobenius number F is the smallest nongap in the interval of nongaps immediatelly previous to F. For instance, the subconductor of the above example, $H=\{0,12,19,24,28,31,34,36,38,40,42,43,45,46,47,48,\dots \}$, is 42.

Lemma 1.

Let Λ be a non-ordinary and non quasi-ordinary semigroup, with multiplicity m, genus g, and sub-Frobenius number f. Then, $\mathrm{\Lambda }\cup \left\{f\right\}\setminus \left\{m\right\}$ is another numerical semigroup of the same genus g.

Proof. 

Since $\mathrm{\Lambda }$ is already a numerical semigroup, it is enough to see that $F-f$ is not in $\mathrm{\Lambda }\cup \left\{f\right\}\setminus \left\{m\right\}$, where F is the Frobenius number of $\mathrm{\Lambda }$. Notice that for a non-ordinary numerical semigroup, the difference between its Frobenius number and its sub-Frobenius number needs to be less than the multiplicity of the semigroup; hence, $F-f\notin \mathrm{\Lambda }$. So, the only option for $F-f$ to be in $\mathrm{\Lambda }\cup \left\{f\right\}\setminus \left\{m\right\}$ is that $F-f=f$. In this case, any integer between 1 and $f-1$ must be a gap, since the integers between $F-1$ and $F-f+1$ are nongaps. In this case, $\mathrm{\Lambda }$ would be quasi-ordinary, contradicting the hypotheses. □

Definition 1.

The quasi-ordinarization transform of a non-ordinary and non quasi-ordinary numerical semigroup Λ, with multiplicity m, genus g and sub-Frobenius number f, is the numerical semigroup $\mathrm{\Lambda }\cup \left\{f\right\}\setminus \left\{m\right\}$.

The quasi-ordinarization of either an ordinary or quasi-ordinary semigroup is defined to be itself.

As an example, the quasi-ordinarization of the well-tempered harmonic semigroup $H=\{0,\mathbf{12},19,24,28,31,34,36,38,40,42,43,45,46,47,48,\dots \}$ used in the previous examples is $H^{\prime }=\{0,19,24,28,31,34,36,38,40,\mathbf{41},42,43,45,46,47,48,\dots \}.$

Remark 1.

In the ordinarization and quasi-ordinarization transform process, we replace the multiplicity by the largest and second largest gap, respectively, and we obtain numerical semigroups. In general, if we replace the multiplicity by the third largest gap, we do not obtain a numerical semigroup.

See for instance $\{0,2,4,6,8,10,11,\dots \}$. Replacing 2 by 5, we obtain $\{0,4,5,6,8,10,11,\dots \}$, which is not a numerical semigroup since $9=4+5$ is not in the set.

3. Quasi-Ordinarization Number

Next, lemma explicits that there is only one quasi-ordinary semigroup with genus g and conductor c where $c\le 2g$.

Lemma 2.

For each of the positive integers g and c with $c\le 2g$, the semigroup $\{0,g,g+1,\dots ,c-2,c,c+1\dots \}$ is the unique quasi-ordinary semigroup of genus g and conductor c.

The quasi-ordinarization transform of a non-ordinary semigroup of genus g and conductor c can be applied subsequently and at some step, we will attain the quasi-ordinary semigroup of that genus and conductor, that is, the numerical semigroup $\{0,g,g+1,\dots ,c-2,c,c+1,\dots \}$. The number of such steps is defined to be the quasi-ordinarization number of $\mathrm{\Lambda }$.

We denote by ${\varrho }_{g,q}$, the number of numerical semigroups of genus g and quasi-ordinarization number q. In

Table 1. Number of semigroups of each genus and quasi-ordinarization number.

${\mathit{\varrho }}_{\mathit{g},\mathit{q}}$	$\mathit{g}=1$	$\mathit{g}=2$	$\mathit{g}=3$	$\mathit{g}=4$	$\mathit{g}=5$	$\mathit{g}=6$	$\mathit{g}=7$	$\mathit{g}=8$	$\mathit{g}=9$	$\mathit{g}=10$
$q=0$	1	2	3	4	5	6	7	8	9	10
$q=1$			1	3	6	15	24	42	61	93
$q=2$					1	2	7	16	43	89
$q=3$							1	1	4	11
$q=4$									1	1
sum=	1	2	4	7	12	23	39	67	118	204
${\varrho }_{g,q}$	$g=11$	$g=12$	$g=13$	$g=14$	$g=15$	$g=16$	$g=17$	$g=18$	$g=19$	$g=20$
$q=0$	11	12	13	14	15	16	17	18	19	20
$q=1$	123	174	219	291	355	453	537	666	774	936
$q=2$	176	327	538	903	1379	2127	3022	4441	5979	8417
$q=3$	30	75	209	448	990	1894	3575	6367	10,796	17,960
$q=4$	2	3	19	34	106	295	829	1847	4447	9019
$q=5$	1	1	2	2	9	18	55	116	403	986
$q=6$			1	1	2	2	7	9	36	48
$q=7$					1	1	2	2	7	7
$q=8$							1	1	2	2
$q=9$									1	1
sum=	343	592	1001	1693	2857	4806	8045	13,467	22,464	37,396
${\varrho }_{g,q}$	$g=21$	$g=22$	$g=23$	$g=24$	$g=25$	$g=26$	$g=27$	$g=28$	$g=29$	$g=30$
$q=0$	21	22	23	24	25	26	27	28	29	30
$q=1$	1072	1272	1437	1680	1878	2166	2401	2739	3012	3405
$q=2$	10,966	14,826	18,774	24,770	30,539	39,321	47,697	60,083	71,711	88,938
$q=3$	28,265	44,272	66,046	99,525	140,960	204,611	281,077	394,617	525,838	720,977
$q=4$	18,673	35,178	65,533	115,252	197,836	329,568	533,479	848,091	1,304,275	2,001,344
$q=5$	2981	7165	17,640	37,770	84,075	166,465	331,872	615,860	1,135,074	1,989,842
$q=6$	181	464	1383	3603	11,141	26,864	67,991	153,882	352,322	727,680
$q=7$	25	37	94	170	652	1679	5300	14,899	42738	107,050
$q=8$	7	7	23	24	85	99	321	715	2506	7073
$q=9$	2	2	7	7	23	23	69	83	233	331
$q=10$	1	1	2	2	7	7	23	23	68	70
$q=11$			1	1	2	2	7	7	23	23
$q=12$					1	1	2	2	7	7
$q=13$							1	1	2	2
$q=14$									1	1
sum=	62,194	103,246	170,963	282,828	467,224	770,832	1,270,267	2,091,030	3,437,839	5,646,773

, one can see the values of ${\varrho }_{g,q}$ for genus up to 45. It has been computed by an exhaustive exploration of the semigroup tree using the RGD algorithm [12].

Lemma 3.

The quasi-ordinarization number of a non-ordinary numerical semigroup of genus g coincides with the number of non-zero non-gaps of the semigroup that are smaller than or equal to $g-1$.

Proof. 

A non-ordinary numerical semigroup of genus g is non-quasi-ordinary if and only if its multiplicity is at most $g-1$. Consequently, we can repeatedly apply the quasi-ordinarization transform to a numerical semigroup while its multiplicity is at most $g-1$. Furthermore, the number of consecutive transforms that we can apply before obtaining the quasi-ordinary semigroup is hence the number of its non-zero non-gaps that are at most the genus minus one. □

For a numerical semigroup $\mathrm{\Lambda }$, we will consider its enumeration $\lambda$, that is, the unique increasing bijective map between ${\mathbb{N}}_0$ and $\mathrm{\Lambda }$. The element $\lambda \left(i\right)$ is then denoted ${\lambda }_i$. As a consequence of the previous lemma, for a numerical semigroup $\mathrm{\Lambda }$ with quasi-ordinarization number equal to q, the non-gaps that are at most $g-1$ are exactly ${\lambda }_0=0,{\lambda }_1,\dots ,{\lambda }_q$.

Lemma 4.

The maximum quasi-ordinarization number of a non-ordinary semigroup of genus g is $\lfloor \frac{g-1}{2}\rfloor$.

Proof. 

Let $\mathrm{\Lambda }$ be a numerical semigroup with quasi-ordinarization number equal to q. Since the Frobenius number F is at most $2g-1$, the total number of gaps from 1 to $2g-1$ is g, and so the number of non-gaps from 1 to $2g-1$ is $g-1$. The number of those non-gaps that are larger than $g-1$ is $g-1-q$. On the other hand, ${\lambda }_q+{\lambda }_1,{\lambda }_q+{\lambda }_2,\dots ,2{\lambda }_q$ are different non-gaps between g and $2g-1$. So, the number of non-gaps between g and $2g-1$ is at least q. All these results imply that $g-1-q\ge q$ and so, $q\le \frac{g-1}{2}$.

On the other hand, the bound stated in the lemma is attained by the hyperelliptic numerical semigroup

$$\{0,2,4,\dots ,2⌊\frac{g-1}{2}⌋,2\left(⌊\frac{g-1}{2}⌋+1\right),\dots ,2g,2g+1,2g+2,\dots \}.$$

(1)

□

We will next see that the maximum ordinarization number stated in the previous lemma is attained uniquely by the numerical semigroup in (1). To prove this result, we will need the next lemma. Let us recall that $A+B=\{a+b:a\in A,b\in B\}$ and that $\#A$ denotes the cardinality of A.

Lemma 5.

Consider a finite subset $A=\{a_1<\cdots <a_n\}\subseteq {\mathbb{N}}_0$.

• The set $A+A$ contains at least $2n-1$ elements
• If $n\ge 1$, the set $A+A$ contains exactly $2n-1$ elements if and only if there exists a positive integer α such that $a_i=a_1+(i-1)\alpha$ for all $i\le n$.
• If $n\ge 4$, the set $A+A$ contains exactly $2n$ elements if and only if either
  • there exists a positive integer α such that $a_i=a_1+\alpha (i-1)$ for all i with $1\le i<n$ and $a_n=a_1+n\alpha$,
  • there exists a positive integer α such that $a_i=a_1+i\alpha$ for all i with $2\le i\le n$.

Proof. 

The first item stems from the fact that if $A=\{a_1,\dots ,a_n\}$, then $A+A$ must contain at least $2a_1,a_1+a_2,a_1+a_3,\dots ,a_1+a_n,a_2+a_n,a_3+a_n,\dots ,a_{n-1}+a_n,2a_n$, which are all different.

The second item easily follows from the fact that if $A+A$ has $2n-1$ elements, then $A+A$ must be exactly the set $2a_1,a_1+a_2,a_1+a_3,\dots ,a_1+a_n,a_2+a_n,a_3+a_n,\dots ,a_{n-1}+a_n,2a_n$. Indeed, in this case, the increasing set $\{a_1+a_3,\dots ,a_1+a_n,a_2+a_n,a_3+a_n,\dots ,a_{n-1}+a_n,2a_n\}$ must coincide with the increasing set $\{2a_2,a_2+a_3,a_2+a_4,\dots ,a_2+a_n,a_3+a_n,\dots ,$$a_{n-1}+a_n,2a_n\}$, having as a consequence that $2a_2=a_1+a_3$ and so, $a_2=\frac{a_1+a_3}{2}=a_1+\frac{a_3-a_1}{2}$, and $a_3=2a_2-a_1=a_1+2\frac{a_3-a_1}{2}$. Hence,

$$\begin{array}{ccc}\hfill a_2& =& a_1+\frac{a_3-a_1}{2}\hfill \\ \hfill a_3& =& a_1+2\frac{a_3-a_1}{2}\hfill \end{array}$$

Similarly, one can show that $2a_3=a_2+a_4$ and, so, $a_4=2a_3-a_2=2a_1+4\frac{a_3-a_1}{2}-a_1-\frac{a_3-a_1}{2}=a_1+3\frac{a_3-a_1}{2}$. It equally follows that

$$\begin{array}{ccc}\hfill a_4& =& a_1+3\frac{a_3-a_1}{2}\hfill \\ \hfill a_5& =& a_1+4\frac{a_3-a_1}{2}\hfill \\ & ⋮\end{array}$$

For the third item, one direction of the proof is obvious, so we just need to prove the other one, that is, if the sum contains $2n$ elements, then $a_1,\dots ,a_n$ must be as stated.

We will proceed by induction. Suppose that $n=4$ and that the set $A+A$ contains exactly 8 elements. Since the ordered sequence

$$2a_1<a_1+a_2<2a_2<a_2+a_3<2a_3<a_3+a_4<2a_4$$

(2)

already contains 7 elements, then necessarily two of the elements $a_1+a_3,a_1+a_4,a_2+a_4$ coincide with one element in (2) and the third one is not in (2). So, at least one of $a_1+a_3$ and $a_2+a_4$ must be in (2).

Suppose first that $a_1+a_3$ is in (2). Then, necessarily $a_1+a_3=2a_2$, which means that $a_2-a_1=a_3-a_2$. Hence, there exists $\alpha$ (in fact, $\alpha =a_2-a_1$) such that $a_2=a_1+\alpha$ and $a_3=a_1+2\alpha$. Now, the elements

$$2a_1<a_1+a_2<2a_2<a_2+a_3<2a_3$$

(3)

are equally separated by the same separation $\alpha$. That is,

$$\begin{array}{ccc}\hfill (a_1+a_2)-\left(2a_1\right)& =& \alpha \hfill \\ \hfill \left(2a_2\right)-(a_1+a_2)& =& \alpha \hfill \\ \hfill (a_2+a_3)-\left(2a_2\right)& =& \alpha \hfill \\ \hfill \left(2a_3\right)-(a_2+a_3)& =& \alpha .\hfill \end{array}$$

Additionally, the elements

$$a_4+a_1<a_4+a_2<a_4+a_3$$

(4)

are equally separated by the same separation $\alpha$. That is,

$$\begin{array}{ccc}\hfill (a_4+a_3)-(a_4+a_2)& =& \alpha \hfill \\ \hfill (a_4+a_2)-(a_4+a_1)& =& \alpha .\hfill \end{array}$$

Furthermore, $A+A$ must contain all the elements in (3) and (4) as well as the element $2a_4$, which is not in (3), nor in (4). Since $\#(A+A)=8$, this means that there must be exatly one element that is both in (3) and (4). The only way for this to happen is that $2a_3=a_4+a_1$. Consequently, $a_4+a_1=2a_1+4\alpha$, and so, $a_4=a_1+4\alpha$. This proves the result in the first case.

For the case in which $a_2+a_4$ is in (2), it is necessary that $a_2+a_4=2a_3$, which means that $a_3-a_2=a_4-a_3$. Hence, there exists $\beta$ (in fact, $\beta =a_3-a_2$) such that $a_3=a_2+\beta$ and $a_4=a_2+2\beta$. Now, the elements

$$2a_2<a_2+a_3<2a_3<a_3+a_4<2a_4$$

(5)

are equally separated by the same separation $\beta$. That is,

$$\begin{array}{ccc}\hfill (a_2+a_3)-\left(2a_2\right)& =& \beta \hfill \\ \hfill \left(2a_3\right)-(a_2+a_3)& =& \beta \hfill \\ \hfill (a_3+a_4)-\left(2a_3\right)& =& \beta \hfill \\ \hfill \left(2a_4\right)-(a_3+a_4)& =& \beta .\hfill \end{array}$$

Additionally, the elements

$$a_1+a_2<a_1+a_3<a_1+a_4$$

(6)

are equally separated by the same separation $\beta$. That is,

$$\begin{array}{ccc}\hfill (a_1+a_3)-(a_1+a_2)& =& \beta \hfill \\ \hfill (a_1+a_4)-(a_1+a_3)& =& \beta .\hfill \end{array}$$

Now, $A+A$ must contain all the elements in (5) and (6), as well as the element $2a_1$, which is not in (5), nor in (6). Since $\#(A+A)=8$, this means that there must be exactly one element that is both in (5) and in (6). The only way for this to happen is that $a_1+a_4=2a_2$. Consequently, $a_1+a_4=2a_1+4\alpha$, and so, $a_4=a_1+4\alpha$. Hence, $a_2=a_1+2\beta$, $a_3=a_1+3\beta$, $a_4=a_1+4\beta$. This proves the result in the second case and concludes the proof for $n=4$.

Now, let us prove the result for a general $n>4$. We will denote $A_n$ the set $\{a_1,\dots ,a_n\}$.

Notice that $A_1+A_1=\left\{2a_1\right\}$ while, if $i>1$, then $\{a_{i-1}+a_i,2a_i\}\subseteq (A_i+A_i)\setminus (A_{i-1}+A_{i-1})$, hence, $\#((A_i+A_i)\setminus (A_{i-1}+A_{i-1}))\ge 2$. Consequently, if $\#(A_n+A_n)=2n$, we can affirm that there exists exactly one integer s such that $\#(A_r+A_r)=2r-1,$ for all $r<s$ and $\#(A_r+A_r)=2r$ for all $r\ge s$.

If $s=n$, then we already have, by the second item of the lemma, that $a_i=a_1+(i-1)\gamma$ for a given positive integer $\gamma$ for all $i<n$.

On one hand,

$$A_{n-1}+A_{n-1}=\{2a_1,2a_1+\gamma ,2a_1+2\gamma ,2a_1+3\gamma ,\dots ,2a_1+(2n-4)\gamma \},$$

(7)

which has $2n-3$ elements. On the other hand,

$$A_{n-1}+a_n=\{(a_1+a_n),(a_1+a_n)+\gamma ,(a_1+a_n)+2\gamma ,(a_1+a_n)+3\gamma ,\dots ,(a_1+a_n)+(n-2)\gamma \},$$

(8)

has $n-1$ elements.

Now, $A+A=(A_{n-1}+A_{n-1})\cup (A_{n-1}+a_n)\cup \left(2a_n\right)$. By the inclusion–exclusion principle, and since $2a_n$ is not in $(A_{n-1}+A_{n-1})\cup (A_{n-1}+a_n)$,

$$\begin{array}{ccc}\hfill \#\left((A_{n-1}+A_{n-1})\cap (A_{n-1}+a_n)\right)& =& \#(A_{n-1}+A_{n-1})+\#(A_{n-1}+a_n)+1-\#(A+A)\hfill \\ & =& (2n-3)+(n-1)+1-2n\hfill \\ & =& n-3\hfill \end{array}$$

By (7) and (8), we conclude that $(a_1+a_n)+(n-4)\gamma =2a_1+(2n-4)\gamma$, that is, $a_n=a_1+n\gamma$. Hence, the result follows with $\alpha =\gamma$.

On the contrary, if $s<n$, then, since $\#\left(A_{n-1}+A_{n-1}\right)=2(n-1)$, we can apply the induction hypothesis and affirm that either one of the following cases, (a) or (b), holds.

(a)

There exists a positive integer ${\alpha }_{n-1}$ such that $a_i=a_1+{\alpha }_{n-1}(i-1)$ for all i with $1\le i<n-1$ and $a_{n-1}=a_1+(n-1)\alpha$;

(b)

There exists a positive integer $\alpha$ such that $a_i=a_1+i{\alpha }_{n-1}$ for all i with $2\le i\le n-1$.

In case (a), we will have

$$\begin{array}{c}\hfill A_{n-1}+A_{n-1}=\{2a_1,2a_1+{\alpha }_{n-1},2a_1+2{\alpha }_{n-1},\dots \\ \hfill \dots ,2a_1+(2n-4){\alpha }_{n-1},2a_1+(2n-2){\alpha }_{n-1}\},\end{array}$$

and

$$\begin{array}{c}\hfill A_{n-1}+a_n=\{(a_1+a_n),(a_1+a_n)+{\alpha }_{n-1},(a_1+a_n)+2{\alpha }_{n-1},\dots \\ \hfill \dots ,(a_1+a_n)+(n-3){\alpha }_{n-1},(a_1+a_n)+(n-1){\alpha }_{n-1}\},\end{array}$$

In case (b), we will have

$$\begin{array}{c}\hfill A_{n-1}+A_{n-1}=\{2a_1,2a_1+2{\alpha }_{n-1},2a_1+3{\alpha }_{n-1},\dots \\ \hfill \dots ,2a_1+(2n-3){\alpha }_{n-1},2a_1+(2n-2){\alpha }_{n-1}\},\end{array}$$

and

$$\begin{array}{c}\hfill A_{n-1}+a_n=\{(a_1+a_n),(a_1+a_n)+2{\alpha }_{n-1},(a_1+a_n)+3{\alpha }_{n-1},\dots \\ \hfill \dots ,(a_1+a_n)+(n-1){\alpha }_{n-1}\},\end{array}$$

Now,

$$\begin{array}{ccc}\hfill \#\left((A_{n-1}+A_{n-1})\cap (A_{n-1}+a_n)\right)& =& \#(A_{n-1}+A_{n-1})+\#(A_{n-1}+a_n)+1-\#(A+A)\hfill \\ & =& \#(A_{n-1}+A_{n-1})-n\hfill \\ & =& n-2.\hfill \end{array}$$

This is only possible in case (b) with

$$\begin{array}{c}\hfill (A_{n-1}+A_{n-1})\cap (A_{n-1}+a_n)=\{(a_1+a_2),(a_1+a_n)+2{\alpha }_{n-1},(a_1+a_n)+3{\alpha }_{n-1},\dots \\ \hfill \dots ,(a_1+a_n)+(n-2){\alpha }_{n-1}\},\end{array}$$

and, hence, with $(a_1+a_n)+(n-2){\alpha }_{n-1}=2a_1+(2n-2){\alpha }_{n-1}$, that is, $a_n=a_1+n{\alpha }_{n-1}$, hence yielding the result with $\alpha ={\alpha }_{n-1}$. □

Lemma 6.

Let $g>2$ and $g\ne 4,g\ne 6$. The unique non-quasi-ordinary numerical semigroup of genus g and quasi-ordinarization number $\lfloor \frac{g-1}{2}\rfloor$ is $\{0,2,4,\dots ,2g,2g+2,2g+3\dots \}$.

Proof. 

If $g=3$, there is only one numerical semigroup non-ordinary and non-quasi-ordinary as we can observe in Figure 1, and it is exactly $\{0,2,4,6,\dots \}$, which indeed, has a quasi-ordinarization number $\lfloor \frac{g-1}{2}\rfloor$ and it is of the form $\{0,2,4,\dots ,2g,2g+1,2g+2,\dots \}$. The case $g=4$ and $g=6$ are excluded from the statement (and analyzed in Remark 2). So, we can assume that either $g=5$ or $g>6$.

Suppose that the quasi-ordinarization number of $\mathrm{\Lambda }$ is $\lfloor \frac{g-1}{2}\rfloor$. Since ${\lambda }_{\lfloor \frac{g-1}{2}\rfloor }\le g-1$, we know that the set of all non-gaps between 0 and $2g-2$ must contain all the sums

$$\mathrm{\Sigma }=\{{\lambda }_i+{\lambda }_j:0\le i,j\le \lfloor \frac{g-1}{2}\rfloor \}.$$

However, the number of non-gaps between 0 and $2g-2$ is either $g-1$ or g depending on whether $2g-1$ is a gap or not. So, $\#\mathrm{\Sigma }\le g$. On the other hand, by Lemma 5, $\#\mathrm{\Sigma }\ge 2\lfloor \frac{g-1}{2}\rfloor +1$.

If g is odd, we get that $2\lfloor \frac{g-1}{2}\rfloor +1=g$ and so, $\#\mathrm{\Sigma }=g$. Then, by the second item in Lemma 5, we get that ${\lambda }_i=i{\lambda }_1$ for $i\le \frac{g-1}{2}$. Now, ${\lambda }_{\frac{g-1}{2}}=\frac{g-1}{2}{\lambda }_1$ and, since ${\lambda }_{\frac{g-1}{2}}\le g-1$, one can deduce that ${\lambda }_1\le 2$. If ${\lambda }_1=1$ this contradicts $g>1$. So, ${\lambda }_i=2i$ for $0\le i\le \frac{g-1}{2}$ and the remaining non-gaps between g and $2g$ are necessarily ${\lambda }_i=2i$ for $i=\frac{g-1}{2}+1$ to $i=g$.

If g is even, then $g-1\le \#\mathrm{\Sigma }\le g$. If $\#\mathrm{\Sigma }=g$, then, since the number of summands in the sum $\mathrm{\Sigma }$ is at least 4 (because we excluded the even genera 4 and 6), we can apply the third item in Lemma 5. Then, we obtain ${\lambda }_{\frac{g}{2}-1}=\frac{g}{2}{\lambda }_1$. This, together with ${\lambda }_{\frac{g}{2}-1}\le g-1$ implies that ${\lambda }_1\le 2\frac{g-1}{g}<2$. So, ${\lambda }_1=1$, contradicting $g>1$. Hence, it must be $\mathrm{\Sigma }=g-1$. If $\mathrm{\Sigma }=g-1$, then, by the second item in Lemma 5, we obtain ${\lambda }_i=i{\lambda }_1$ for all $i\le \frac{g}{2}-1$. Now, ${\lambda }_{\frac{g}{2}-1}=(\frac{g}{2}-1){\lambda }_1$ and, since ${\lambda }_{\frac{g}{2}-1}\le g-1$, one can deduce that ${\lambda }_1\le 2\frac{g-1}{g-2}$. However, $2\frac{g-1}{g-2}<3$ if $g\ge 5$. So, ${\lambda }_1$ con only be 1 or 2. If ${\lambda }_1=1$ this contradicts $g>1$. So, ${\lambda }_i=2i$ for $0\le i\le \frac{g}{2}-1$ and the remaining non-gaps between g and $2g$ are necessarily ${\lambda }_i=2i$ for $i=\frac{g}{2}$ to $i=g$. □

Remark 2.

For $g=4$, the maximum quasi-ordinarization number $\lfloor \frac{g-1}{2}\rfloor =1$ is, in fact, attained by three of the 7 semigroups of genus 4. The semigroups whose quasi-ordinarization number is maximum are $\{0,3,6,\dots \}$, $\{0,2,4,6,8,\dots \}$, $\{0,3,5,6,8,\dots \}$.

For $g=6$, the maximum quasi-ordinarization number $\lfloor \frac{g-1}{2}\rfloor =2$ is, in fact, attained by two of the 23 semigroups of genus 6. The semigroups whose quasi-ordinarization number is maximum are $\{0,2,4,6,8,10,12,\dots \}$, $\{0,4,5,8,9,10,12,\dots \}$.

Hence, $g=4$ and $g=6$ are exceptional cases.

4. Analysis of ${\mathbf{\varrho }}_{\mathbf{g},\mathbf{q}}$

Let us denote $o_{g,r}$, the number of numerical semigroups of genus g and ordinarization number r and ${\varrho }_{g,q}$, the number of numerical semigroups of genus g and quasi-ordinarization number r.

We can observe a behavior of ${\varrho }_{g,q}$ very similar to the behavior of $o_{g,r}$ introduced in [9].

Indeed, for odd g and large r, it holds ${\varrho }_{g,q}=o_{g,r}$ and for even g and large q, it holds ${\varrho }_{g,q}=o_{g,r+1}$. We will give a partial proof of these equalities at the end of this section.

It is conjcetured in [9] that, for each genus $g\in {\mathbb{N}}_0$ and each ordinarization number $r\in {\mathbb{N}}_0$,

$$o_{g,r}\le o_{g+1,r}.$$

We can write the new conjecture below paralleling this.

Conjecture 1.

For each genus $g\in {\mathbb{N}}_0$ and each quasi-ordinarization number $q\in {\mathbb{N}}_0$,

$${\varrho }_{g,q}\le {\varrho }_{g+1,q}.$$

Now, we will provide some results on ${\varrho }_{g,q}$ for high quasi-ordinarization numbers. First, we will need Freĭman’s Theorem [25,26] as formulated in [27].

Theorem 2

(Freĭman). Let A be a set of integers such that $\#A=k\ge 3$. If $\#(A+A)\le 3k-4$, then A is a subset of an arithmetic progression of length $\#(A+A)-k+1\le 2k-3$.

The next lemma is a consequence of Freĭman’s Theorem. The lemma shows that the first non-gaps of numerical semigroups of large quasi-ordinarization number must be even.

Lemma 7.

If a semigroup Λ of genus g has quasi-ordinarization number q with $\frac{g+1}{3}\le q\le \lfloor \frac{g-1}{2}\rfloor$ then all its non-gaps which are less than or equal to $g-1$ are even.

Proof. 

Suppose that $\mathrm{\Lambda }$ is a semigroup of genus g and quasi-ordinarization number $q\ge \frac{g+1}{3}$.

Since the quasi-ordinarization is q, this means that ${\lambda }_0=0,{\lambda }_1,\dots ,{\lambda }_q\le g-1$ and ${\lambda }_{q+1}\ge g$, hence $\mathrm{\Lambda }\cap [0,g-1]=\{{\lambda }_0,{\lambda }_1,\dots ,{\lambda }_q\}$. Let $A=\mathrm{\Lambda }\cap [0,g-1]$. By the previous equality, $\#A=q+1$. We have that the elements in $A+A$ are upper bounded by $2g-2$ and so $A+A\subseteq \mathrm{\Lambda }\cap [0,2g-2]$. Then, $\#(A+A)\#(\mathrm{\Lambda }\cap [0,2g-2\left]\right)<\#(\mathrm{\Lambda }\cap [0,2g\left]\right)$. Since the Frobenius number of $\mathrm{\Lambda }$ is at most $2g-1$, $\#(\mathrm{\Lambda }\cap [0,2g\left]\right)=g+1$ and, so, $\#(A+A)\le g$. Now, since $q\ge \frac{g+1}{3}$, we have $g\le 3q-1=3(q+1)-4=3(\#A)-4$ and we can apply Theorem 2 with $k=q+1$. Thus, we have that A is a subset of an arithmetic progression of length at most $g-k+1=g-q$.

Let $d\left(A\right)$ be the difference between consecutive terms of this arithmetic progression. The number $d\left(A\right)$ can not be larger than or equal to three since otherwise ${\lambda }_q\ge q·d\left(A\right)\ge 3q\ge 3\frac{g+1}{3}>g$, a contradiction with q being the quasi-ordinarization number.

If $d\left(A\right)=1$, then $A\subseteq [0,g-q-1]$ and so $\mathrm{\Lambda }\cap [g-q,g-1]=\varnothing$. We claim that in this case $A\subseteq \left\{0\right\}\cup [\lceil \frac{g}{2}\rceil ,g-q-1]$. Indeed, suppose that $x\in A$. Then, $2x$ satisfies either $2x\le g-q-1$ or $2x\ge g$. If the second inequality is satisfied, then it is obvious that $x\in \left\{0\right\}\cup [\lceil \frac{g}{2}\rceil ,g-q-1]$. If the first inequality is satisfied, then we will prove that $mx\le g-q-1$ for all $m\ge 2$ by induction on m and this leads to $x=0$. Indeed, if $mx\le g-q-1$, then $x\le \frac{g-q-1}{m}\le \frac{g-\frac{g+1}{3}-1}{m}=\frac{2g-4}{3m}<\frac{2g}{3m}$. Now, $(m+1)x<\frac{2g(m+1)}{3m}=\frac{(2m+2)g}{3m}$ and since $m\ge 2$, we have $(m+1)x<\frac{(2m+m)g}{3m}=g$ and so $(m+1)x\le g-1$. Since $(m+1)x$ is in $\mathrm{\Lambda }\cap [0,g-1]=A\subseteq [0,g-q-1]$, this means that $(m+1)x\le g-q-1$ and this proves the claim.

Now, $A\subseteq \left\{0\right\}\cup [\lceil \frac{g}{2}\rceil ,g-q-1]$ together with $\#A=q+1$ implies that $q\le g-q-\lceil \frac{g}{2}\rceil =\lfloor \frac{g}{2}\rfloor -q\le \frac{g}{2}-\frac{g+1}{3}=\frac{g-2}{6}<q$, a contradiction.

So, we deduce that $d\left(A\right)=2$, leading to the proof of the lemma. □

The next lemma was proved in [9].

Lemma 8.

Suppose that a numerical semigroup Λ has ω gaps between 1 and $n-1$ and $n\ge 2\omega +2$, then

• $n\in \mathrm{\Lambda }$,
• the Frobenius number of Λ is smaller than n,
• the genus of Λ is ω.

Let $\mathrm{\Lambda }$ be a numerical semigroup. As in [9], let us say that a set $B\subset {\mathbb{N}}_0$ is $\mathrm{\Lambda }$-closed if for any $b\in B$ and any $\lambda$ in $\mathrm{\Lambda }$, the sum $b+\lambda$ is either in B or it is larger than $max\left(B\right)$. If B is $\mathrm{\Lambda }$-closed, so is $B-min\left(B\right)$. Indeed, $b-min\left(B\right)+\lambda =(b+\lambda )-min\left(B\right)$ is either in $B-min\left(B\right)$ or it is larger than $max\left(B\right)-min\left(B\right)=max(B-min(B\left)\right)$. The new $\mathrm{\Lambda }$-closed set contains 0. We will denote by $C(\mathrm{\Lambda },i)$, the $\mathrm{\Lambda }$-closed sets of size i that contain 0.

Let ${\mathcal{S}}_{\gamma }$ be the set of numerical semigroups of genus $\gamma$. It was proved in [9] that, for r, an integer with $\frac{g+2}{3}\le r\le \lfloor \frac{g}{2}\rfloor$, it holds

$$o_{g,r}=\sum _{\mathrm{\Omega }\in {\mathcal{S}}_{(\lfloor \frac{g}{2}\rfloor -r)}}\#C(\mathrm{\Omega },⌊\frac{g}{2}⌋-r+1).$$

We will see now that, for q an integer with $\frac{g+1}{3}\le q\le \lfloor \frac{g-1}{2}\rfloor$, it holds

$${\varrho }_{g,q}=\sum _{\mathrm{\Omega }\in {\mathcal{S}}_{(\lfloor \frac{g-1}{2}\rfloor -q)}}\#C(\mathrm{\Omega },⌊\frac{g-1}{2}⌋-q+1).$$

This proves that, for q, an integer with $\frac{g+2}{3}\le q\le \lfloor \frac{g-1}{2}\rfloor$, we have

$${\varrho }_{g,q}=\left\{\begin{array}{cc}{o}_{g,q}\hfill & \mathrm{if} g \mathrm{is} \mathrm{odd},\hfill \\ o_{g,q+1}\hfill & \mathrm{if} g \mathrm{is} \mathrm{even}.\hfill \end{array}\right.$$

Theorem 3.

Let $g\in {\mathbb{N}}_0$, $g\ge 1$, and let q be an integer with $\frac{g+1}{3}\le q\le \lfloor \frac{g-1}{2}\rfloor$. Define $\omega =\lfloor \frac{g-1}{2}\rfloor -q$

• If Ω is a numerical semigroup of genus ω and B is an Ω-closed set of size $\omega +1$ and first element equal to 0 then

  $$\{2j:j\in \mathrm{\Omega }\}\cup \{2j-2max\left(B\right)+2g+1:j\in B\}\cup (2g+{\mathbb{N}}_0)$$
  is a numerical semigroup of genus g and quasi-ordinarization number equal to q.
• All numerical semigroups of genus g and quasi-ordinarization number q can be uniquely written as

  $$\{2j:j\in \mathrm{\Omega }\}\cup \{2j-2max\left(B\right)+2g+1:j\in B\}\cup (2g+{\mathbb{N}}_0)$$
  for a unique numerical semigroup Ω of genus ω and a unique Ω-closed set B of size $\omega +1$ and first element equal to 0.
• The number ${\rho }_{g,q}$ of numerical semigroups of genus g and quasi-ordinarization number q depends only on ω. It is exactly

  $$\sum _{\mathrm{\Omega }\in {\mathcal{S}}_{\omega }}\#C(\mathrm{\Omega },\omega +1).$$

Proof. 

• Suppose that $\mathrm{\Omega }$ is a numerical semigroup of genus $\omega$ and B is an $\mathrm{\Omega }$-closed set of size $\omega +1$ and first element equal to 0. Let $X=\{2j:j\in \mathrm{\Omega }\}$, $Y=\{2j-2max(B)+2g+1:j\in B\}$, and $Z=(2g+{\mathbb{N}}_0)$.
  First of all, let us see that the complement ${\mathbb{N}}_0\setminus (X\cup Y\cup Z)$ has g elements. Notice that all elements in X are even while all elements in Y are odd. So, X and Y do not intersect. Additionally, the unique element in $Y\cap Z$ is $2g+1$. The number of elements in the complement will be

  $$\begin{array}{ccc}\hfill \#{\mathbb{N}}_0\setminus (X\cup Y\cup Z)& =& 2g-\#\{x\in X:x<2g\}-\#Y+1\hfill \\ & =& 2g-\#\{s\in \mathrm{\Omega }:s<g\}-\#B+1\hfill \\ & =& 2g-\omega -\#\{s\in \mathrm{\Omega }:s<g\}.\hfill \end{array}$$
  We know that all gaps of $\mathrm{\Omega }$ are at most $2\omega -1=2(\lfloor \frac{g-1}{2}\rfloor -q)-1\le g-1-2q-1<g$. So, $\#\{s\in \mathrm{\Omega }:s<g\}=g-\omega$ and we conclude that $\#{\mathbb{N}}_0\setminus (X\cup Y\cup Z)=g$.
  Before proving that $X\cup Y\cup Z$ is a numerical semigroup, let us prove that the number of non-zero elements in $X\cup Y\cup Z$, which are smaller than or equal to $g-1$ is q. Once we prove that $X\cup Y\cup Z$ is a numerical semigroup, this will mean, by Lemma 3, that it has quasi-ordinarization number q. On the one hand, all elements in Y are larger than $g-1$. Indeed, if $\lambda$ is the enumeration of $\mathrm{\Omega }$ (i.e., $\mathrm{\Omega }=\{{\lambda }_0,{\lambda }_1,\dots \}$ with ${\lambda }_i<{\lambda }_{i+1}$), then $max\left(B\right)\le {\lambda }_{\omega }\le 2\omega =2\lfloor \frac{g-1}{2}\rfloor -2q\le g-1-2\frac{g+1}{3}<\frac{g}{3}$. Now, for any $j\in B$, $2j-2max\left(B\right)+2g+1>2g-2max\left(B\right)>g$. On the other hand, all gaps of $\mathrm{\Omega }$ are at most $2\omega -1=2\lfloor \frac{g-1}{2}\rfloor -2q-1<g-\frac{2(g+1)}{3}-1<\frac{g}{3}-1$ and so all the even integers not belonging to X are less than g. So, the number of non-zero non-gaps of $X\cup Y\cup Z$ smaller than or equal to $g-1$ is $\lfloor \frac{g-1}{2}\rfloor -\omega =q$.
  To see that $X\cup Y\cup Z$ is a numerical semigroup, we only need to see that it is closed under addition. It is obvious that $X+Z\subseteq Z$, $Y+Z\subseteq Z$, $Z+Z\subseteq Z$. It is also obvious that $X+X\subseteq X$ since $\mathrm{\Omega }$ is a numerical semigroup and that $Y+Y\subseteq Z$ since, as we proved before, all elements in Y are larger than g.
  It remains to see that $X+Y\subseteq X\cup Y\cup Z$. Suppose that $x\in X$ and $y\in Y$. Then, $x=2i$ for some $i\in \mathrm{\Omega }$ and $y=2j-2max\left(B\right)+2g+1$ for some $j\in B$. Then, $x+y=2(i+j)-2max\left(B\right)+2g+1$. Since B is $\mathrm{\Omega }$-closed, we have that either $i+j\in B$ and so $x+y\in Y$ or $i+j>max\left(B\right)$. In this case, $x+y\in Z$. So, $X+Y\subseteq Y\cup Z$.
• First of all notice that, since the Frobenius number of a semigroup $\mathrm{\Lambda }$ of genus g is smaller than $2g$, it holds

  $$\mathrm{\Lambda }\cap (2g+{\mathbb{N}}_0)=(2g+{\mathbb{N}}_0).$$
  For any numerical semigroup $\mathrm{\Lambda }$, the set $\mathrm{\Omega }=\{\frac{j}{2}:j\in \mathrm{\Lambda }\cap \left(2{\mathbb{N}}_0\right)\}$ is a numerical semigroup. If $\mathrm{\Lambda }$ has a quazi-ordinarization number $q\ge \frac{g+1}{3}$ then, by Lemma 7,

  $$\mathrm{\Lambda }\cap [0,g-1]=(2\mathrm{\Omega })\cap [0,g-1].$$
  The semigroup $\mathrm{\Omega }$ has exactly $q+1$ non-gaps between 0 and $\lfloor \frac{g-1}{2}\rfloor$ and $\omega =\lfloor \frac{g-1}{2}\rfloor -q$ gaps between 0 and $\lfloor \frac{g-1}{2}\rfloor$. We can use Lemma 8 with $n=\lfloor \frac{g+1}{2}\rfloor$ since

  $$2\omega +2=2⌊\frac{g-1}{2}⌋-2q+2\le g-1-\frac{2(g+1)}{3}+2=\frac{g+1}{3},$$

  which implies $2\omega +2\le \frac{g+1}{3}\le \lfloor \frac{g+1}{2}\rfloor =n$. Then, the genus of $\mathrm{\Omega }$ is $\omega$ and the Frobenius number of $\mathrm{\Omega }$ is at most $\lfloor \frac{g+1}{2}\rfloor$. This means that all even integers larger than $g-1$ belong to $\mathrm{\Lambda }$.
  Define $D=(\mathrm{\Lambda }\cap [0,2g\left]\right)\setminus 2\mathrm{\Omega }$. That is, D is the set of odd non-gaps of $\mathrm{\Lambda }$ smaller than $2g$. We claim that $\overline{B}=\{\frac{j-1}{2}:j\in D\cup \{2g+1\}\}$ is a $\mathrm{\Omega }$-closed set of size $\omega +1$. The size follows from the fact that the number of non-gaps of $\mathrm{\Lambda }$ between g and $2g$ is $g-q$ and that the number of even integers in the same interval is $\lceil \frac{g+1}{2}\rceil$. Suppose that $\lambda \in \mathrm{\Omega }$ and $b\in \overline{B}$. Then, $b=\frac{j-1}{2}$ for some j in $D\cup \{2g+1\}$ and $b+\lambda =\frac{(j+2\lambda )-1}{2}$. If $\frac{(j+2\lambda )-1}{2}max\left(\overline{B}\right)=\frac{(2g+1)-1}{2}$, we are done. Otherwise, we have $j+2\lambda \le 2g$. Since $\mathrm{\Lambda }$ is a numerical semigroup and both $j,2\lambda \in \mathrm{\Lambda }$, it holds $j+2\lambda \in \mathrm{\Lambda }\cap [0,2g]$. Furthermore, $j+2\lambda$ is odd since j is also. So, $b+\lambda$ is either larger than $max\left(\overline{B}\right)$ or it is in $\overline{B}$. Then, $B=\overline{B}-min\left(\overline{B}\right)$ is a $\mathrm{\Lambda }$-closed set of size $\omega +1$ and first element zero.
• The previous two points define a bijection between the set of numerical semigroups in ${\mathcal{S}}_g$ of quasi-ordinarization number q and the set $\{C(\mathrm{\Omega },\omega +1):\mathrm{\Omega }\in {\mathcal{S}}_{\omega }\}.$ Hence, ${\rho }_{g,q}={\sum }_{\mathrm{\Omega }\in {\mathcal{S}}_{\omega }}\#C(\mathrm{\Omega },\omega +1).$

□

Corollary 1.

Suppose that $\frac{g+2}{3}\le q\le \lfloor \frac{g-1}{2}\rfloor$. Then,

$${\varrho }_{g,q}=\left\{\begin{array}{cc}{o}_{g,q}\hfill & if g is odd,\hfill \\ o_{g,q+1}\hfill & if g is even.\hfill \end{array}\right.$$

Define, as in [9], the sequence $f_{\omega }$ by $f_{\omega }={\sum }_{\mathrm{\Omega }\in {\mathcal{S}}_{\omega }}\#C(\mathrm{\Omega },\omega +1).$ The first elements in the sequence, from $f_0$ to $f_{15}$ are

ω	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$f_{\omega }$	1	2	7	23	68	200	615	1764	5060	14,626	41,785	117,573	332,475	933,891	2,609,832	7,278,512

We remark that this sequence appears in [5], where Bernardini and Torres proved that the number of numerical semigroups of genus $3\omega$ whose number of even gaps is $\omega$ is exactly $f_{\omega }$. It corresponds to the entry A210581 of The On-Line Encyclopedia of Integer Sequences [23].

We can deduce the values ${\varrho }_{g,q}$ using the values in the previous table together with Theorem 3 for any g, whenever $q\ge max(\frac{g+2}{3},\lfloor \frac{g-1}{2}\rfloor -15)$.

The next corollary is a consequence of the fact that the sequence $f_{\omega }$ is increasing for $\omega$ between 0 and 15.

Corollary 2.

For any $g\in \mathbb{N}$ and any $q\ge max(\frac{g}{3}+1,\lfloor \frac{g}{2}\rfloor -15)$, it holds ${\varrho }_{g,q}\ge {\varrho }_{g+1,q}$.

If we proved that $f_{\omega }\le f_{\omega +1}$ for any $\omega$, this would imply ${\varrho }_{g,q}\le {\varrho }_{g+1,q}$ for any $q>\frac{g}{3}$.

5. The Forest ${\mathcal{F}}_{\mathbf{g}}$

Fix a genus g. We can define a graph in which the nodes are all semigroups of that genus and whose edges connect each semigroup to its quasi-ordinarization transform, if it is not itself. The graph is a forest ${\mathcal{F}}_g$ rooted at all ordinary and quasi-ordinary semigroups of genus g. In particular, the quasi-ordinarization transform defines, for each fixed genus and conductor, a tree rooted at the unique quasi-ordinary semigroup of that genus and conductor, given in Lemma 2. See ${\mathcal{F}}_4$ in Figure 3, ${\mathcal{F}}_6$ in Figure 4, and ${\mathcal{F}}_7$ in Figure 5.

In the forest ${\mathcal{F}}_g$, we know that the parent of a numerical semigroup that is not a root is its quasi-ordinarization transform. Let us analyze now, what the children of a numerical semigroup are. The next result is well known and can be found, for instance, in [2]. We use ${\mathrm{\Lambda }}^{*}$ to denote $\mathrm{\Lambda }\setminus \left\{0\right\}$.

Lemma 9.

Suppose that Λ is a numerical semigroup and that $a\in {\mathbb{N}}_0\setminus \mathrm{\Lambda }$. The set $a\cup \mathrm{\Lambda }$ is a numerical semigroup if and only if

• $a+{\mathrm{\Lambda }}^{*}\subseteq {\mathrm{\Lambda }}^{*}$,
• $2a\in \mathrm{\Lambda }$,
• $3a\in \mathrm{\Lambda }$.

The elements $a\in {\mathbb{N}}_0\setminus \mathrm{\Lambda }$ such that $a+\mathrm{\Lambda }\subseteq \mathrm{\Lambda }$, are denoted pseudo-Frobenius numbers of $\mathrm{\Lambda }$. The elements $a\in {\mathbb{N}}_0\setminus \mathrm{\Lambda }$ such that $\{2a,3a\}\subseteq \mathrm{\Lambda }$, are denoted fundamental gaps of $\mathrm{\Lambda }$. The elements satisfying the three conditions will be called candidates.

Suppose that a numerical semigroup $\mathrm{\Lambda }$ with Frobenius number F has children in ${\mathcal{F}}_g$. Let $e_1,\dots ,e_r$ be the generators of $\mathrm{\Lambda }$ between the subconductor and $F-1$. For $i=1,\dots ,r$, let $c_1^i,\dots ,c_{k_i}^i$ be the candidates of $\mathrm{\Lambda }\setminus \left\{e_i\right\}$. The children of $\mathrm{\Lambda }$ in ${\mathcal{F}}_g$ are the semigroups of the form $\mathrm{\Lambda }\setminus \left\{e_i\right\}\cup \left\{c_j^i\right\}$, for $i=1,\dots ,r$ and $j=1,\dots ,k_i$.

6. Relating ${\mathcal{F}}_{\mathbf{g}}$, ${\mathcal{T}}_{\mathbf{g}}$, and $\mathcal{T}$

Now, we analyze the relation between the kinship of different nodes in ${\mathcal{F}}_g$, ${\mathcal{T}}_g$, and $\mathcal{T}$. If two semigroups are children of the same semigroup $\mathrm{\Lambda }$, then they are called siblings. If ${\mathrm{\Lambda }}_1$ and ${\mathrm{\Lambda }}_2$ are siblings, and ${\mathrm{\Lambda }}_3$ is a child of ${\mathrm{\Lambda }}_2$, then we say that ${\mathrm{\Lambda }}_3$ is a niece/nephew of ${\mathrm{\Lambda }}_1$.

Let $q(\mathrm{\Lambda })$ denote the quasi-ordinarization of $\mathrm{\Lambda }$. The next lemmas are quite immediate from the definitions.

Lemma 10.

If ${\mathrm{\Lambda }}_1$ is a child of ${\mathrm{\Lambda }}_2$ in $\mathcal{T}$, then $q\left({\mathrm{\Lambda }}_1\right)$ is a niece/nephew of $q\left({\mathrm{\Lambda }}_2\right)$ in $\mathcal{T}$.

As an example, ${\mathrm{\Lambda }}_1=\{0,4,5,8,9,10,12,\dots \}$ is a child of ${\mathrm{\Lambda }}_2=\{0,4,5,8,\dots \}$ in $\mathcal{T}$, while $q\left({\mathrm{\Lambda }}_1\right)=\{0,5,7,8,9,10,12,\dots \}$ is a niece of $q\left({\mathrm{\Lambda }}_2\right)=\{0,5,6,8,\dots \}$ in $\mathcal{T}$.

Lemma 11.

If ${\mathrm{\Lambda }}_1$ and ${\mathrm{\Lambda }}_2$ are siblings in $\mathcal{T}$, then they are siblings in ${\mathcal{T}}_g$ but not in ${\mathcal{F}}_g$.

As an example, ${\mathrm{\Lambda }}_1=\{0,5,7,9,10,11,12,14,\dots \}$ and ${\mathrm{\Lambda }}_2=\{0,5,7,9,10,12,\dots \}$ are siblings in $\mathcal{T}$ and in ${\mathcal{T}}_7$ (see Figure 2), but they are not siblings in ${\mathcal{F}}_7$ (see Figure 5).

Lemma 12.

If ${\mathrm{\Lambda }}_1$ and ${\mathrm{\Lambda }}_2$ are siblings in ${\mathcal{T}}_g$, then $q\left({\mathrm{\Lambda }}_1\right)$ and $q\left({\mathrm{\Lambda }}_2\right)$ are siblings in $\mathcal{T}$.

As an example, ${\mathrm{\Lambda }}_1=\{0,3,6,9,10,12,\dots \}$ and ${\mathrm{\Lambda }}_2=\{0,5,6,10,\dots \}$ are siblings in ${\mathcal{T}}_7$ (see Figure 2), and $q\left({\mathrm{\Lambda }}_1\right)=\{0,6,8,9,10,12,\dots \}$ and $q\left({\mathrm{\Lambda }}_2\right)=\{0,6,8,10,\dots \}$ are siblings in $\mathcal{T}$.

As a consequence of the previous two lemmas, we obtain this final lemma.

Lemma 13.

If ${\mathrm{\Lambda }}_1$ and ${\mathrm{\Lambda }}_2$ are siblings in $\mathcal{T}$, then $q\left({\mathrm{\Lambda }}_1\right)$ and $q\left({\mathrm{\Lambda }}_2\right)$ are siblings in $\mathcal{T}$.

As an example, ${\mathrm{\Lambda }}_1=\{0,5,7,9,10,11,12,14,\dots \}$ and ${\mathrm{\Lambda }}_2=\{0,5,7,9,10,12,\dots \}$ are siblings in $\mathcal{T}$ and $q\left({\mathrm{\Lambda }}_1\right)=\{0,7,8,9,10,11,12,14,\dots \}$ and $q\left({\mathrm{\Lambda }}_2\right)=\{0,7,8,9,10,12,\dots \}$ are siblings in $\mathcal{T}$.

7. Conclusions

Quasi-ordinary semigroups are those semigroups that have all gaps except one in a row, while ordinary semigroups have all gaps in a row.

We defined a quasi-ordinarization transform that, applied repeatedly to a non-ordinary numerical semigroup stabilizes in a quasi-ordinary semigroup of the same genus.

From this transform, fixing a genus g, we can define a forest ${\mathcal{F}}_g$ whose nodes are all semigroups of genus g, whose roots are all ordinary and quasi-ordinary semigroups of that genus, and whose edges connect each non-ordinary and non-quasi-ordinary numerical semigroup to its quasi-ordinarization transform.

We conjectured that the number of numerical semigroups in ${\mathcal{F}}_g$ at a given depth is at most the number of numerical semigroups in ${\mathcal{F}}_{g+1}$ at the same depth. We provided a proof of the conjecture for the largest possible depths. Proving this conjecture for all depths would prove the conjecture that $n_{g+1}\ge n_g$. Hence, we expect our work to be a step toward the proof of the conjectured increasingness of the sequence $n_g$.