# Algorithms for Generalized Numerical Semigroups

Carmelo Cisto  Universitá di Messina, Dipartimento di Matematica e
Informatica, Viale Ferdinando Stagno D’Alcontres 31, 98166 Messina, Italy
<EMAIL_ADDRESS>,  Manuel Delgado  CMUP, Departamento de Matemática,
Faculdade de Ciências, Universidade do Porto, Rua do Campo Alegre 687,
4169-007 Porto, Portugal<EMAIL_ADDRESS>and  Pedro A. García-Sánchez
Departamento de Álgebra, Facultad de Ciencias, Campus Fuentenueva s/n, 18071
Granada, España<EMAIL_ADDRESS>
###### Abstract.

We provide algorithms for performing computations in generalized numerical
semigroups, that is, submonoids of $\mathbb{N}^{d}$ with finite complement in
$\mathbb{N}^{d}$. These semigroups are affine semigroups, which in particular
implies that they are finitely generated. For a given finite set of elements
in $\mathbb{N}^{d}$ we show how to deduce if the monoid spanned by this set is
a generalized numerical semigroup and, if so, we calculate its set of gaps.
Also, given a finite set of elements in $\mathbb{N}^{d}$ we can determine if
it is the set of gaps of a generalized numerical semigroup and, if so, compute
the minimal generators of this monoid. We provide a new algorithm to compute
the set of all generalized numerical semigroups with a prescribed genus (the
cardinality of their sets of gaps). Its implementation allowed us to compute
(for various dimensions) the number of numerical semigroups for genus that had
not been attained before.

###### Key words and phrases:

Generalized numerical semigroup, gaps, minimal generators, genus

###### 1991 Mathematics Subject Classification:

20M14, 05A15, 11D07,20-04

All the authors acknowledge partial support by the project MTM2017-84890-P,
which is funded by Ministerio de Economía y Competitividad and Fondo Europeo
de Desarrollo Regional FEDER. The second and third authors acknowledge partial
support by CMUP (UID/MAT/00144/2013 and UID/MAT/00144/2019), which is funded
by FCT (Portugal) with national (MEC) and European structural funds through
the programs FEDER, under the partnership agreement PT2020. The second author
acknowledges a sabbatical grant from the FCT: SFRH/BSAB/142918/2018.

##  1\. Introduction

Let $d$ be a positive integer. A generalized numerical semigroup is a
submonoid of $\mathbb{N}^{d}$ with finite complement in $\mathbb{N}^{d}$,
where by $\mathbb{N}$ we mean the set of non negative integers. Submonoids of
$\mathbb{N}^{d}$ have been studied by many authors, and in particular those
that are finitely generated, which are known in the literature as affine
semigroups.

Generalized numerical semigroups were studied in [9] as a straightforward
generalization of the well known concept of numerical semigroup, that is, a
submonoid of $\mathbb{N}$ with finite complement in $\mathbb{N}$. If $S$ is a
submonoid of $\mathbb{N}^{d}$ with finite complement in $\mathbb{N}^{d}$, then
the elements in $\operatorname{H}(S)=\mathbb{N}^{d}\setminus S$ are the _gaps_
of $S$, and the _genus_ of $S$ is $\operatorname{g}(S)=|\operatorname{H}(S)|$.
In [9], a procedure to compute the set of generalized numerical semigroups in
$\mathbb{N}^{d}$ with genus $g$ is presented; the cardinality of this set is
denoted by $N_{g,d}$. Also it is shown that for fixed genus $g$, the map
$d\mapsto N_{g,d}$ is a polynomial of degree $g$. Other asymptotic properties
are presented and several interesting conjectures are raised. In [12], the
number $N_{g,d}$ is computed for several (low) values, and the concept of
generalized numerical semigroup is extended to affine semigroups having finite
complement in their associated spanning cones. In [6] (finite) sets generating
generalized numerical semigroups are characterized, and a procedure to compute
the set of gaps is presented.

The aim of this manuscript is to present procedures to determine if a given
set of elements in $\mathbb{N}^{d}$ generates a generalized numerical
semigroup and, if so, compute the set of gaps of the resulting monoid. Dually,
we present a procedure to determine if a finite set of points in
$\mathbb{N}^{d}$ represents the set of gaps of an affine semigroup, and then
we give a method for constructing the minimal generating set of this affine
semigroup. We use then these procedures to produce the set of generalized
numerical semigroups with given genus. Careful implementations of the
mentioned procedures have been made in order to make them usable in practice.
A section is devoted to these implementations and the new data obtained from
them.

The GAP [10] package numericalsgps [8] offers tools to deal with numerical and
affine semigroups. The possibility of having fast methods to pass from
generators to gaps and vice versa allows to describe an affine semigroup by
its set of gaps (in the case this set is finite). Membership in a generalized
numerical semigroup for which the gaps are known is then trivial, in contrast
to membership for an affine semigroup for which only a set of generators is
known. Also given an affine semigroup defined by a set of generators one may
wonder if it is a generalized numerical semigroup, and thus compute its gaps.
Benefiting of the features of the computer algebra system GAP, one can, once
computed, add the set of gaps as an attribute of the semigroup (which in
particular makes, from that moment on, the membership problem trivial during
the GAP session). This opens the possibility of defining new methods for
affine semigroups once their gaps are known. In particular, this provides ways
to compute special gaps and pseudo-Frobenius elements (the later terminology
was used in [11]). The implementations of these methods is available in [8],
in particular in the files affine.* and afine-def.*. The documentation
produced for these functions can be consulted in the GAP help system or in the
manual of the package.

The paper is structured as follows. In Section 2, we summarize the main
definitions and properties concerning generalized numerical semigroups that
will be used in the algorithms presented in this manuscript. Sections 3, 4 and
5 are devoted to describe three algorithms, one to compute the set of all
generalized numerical semigroups of given genus, another to calculate the set
of gaps from a minimal generating set of a generalized numerical semigroup,
and a procedure to compute the minimal set of generators of a generalized
numerical semigroup, once its gaps are known. In Section 6, we provide a new
and alternative way to produce all generalized numerical semigroups of given
genus, different from that of Section 3. Then we have two sections with a
rather experimental flavor. First we comment on the implementations of the
algorithms; while in the last we gather some computational results obtained.

##  2\. Basics on Generalized numerical semigroups

It is known that every submonoid $S$ of $\mathbb{N}^{d}$ admits a unique
minimal set of generators $\mathcal{A}(S)$, that is, every element in $S$ is a
linear combination of elements in $\mathcal{A}(S)$ with coefficients in
$\mathbb{N}$ ($S=\langle\mathcal{A}(S)\rangle$), and no proper subset of
$\mathcal{A}(S)$ has this property. It is easy to see that, if
$S\subseteq\mathbb{N}^{d}$ is a monoid, the unique minimal set of generators
is $\mathcal{A}(S)=S^{*}\setminus(S^{*}+S^{*})$, where
$S^{*}=S\setminus\\{0\\}$. This set is not always finite, and submonoids
$S\subseteq\mathbb{N}^{d}$ for which $\mathcal{A}(S)$ is finite are called
_affine semigroups_.

We recall that a _numerical semigroup_ is a submonoid $S$ of $\mathbb{N}$ such
that $\mathbb{N}\setminus S$ is a finite set. The elements of
$\operatorname{H}(S)=\mathbb{N}\setminus S$ are called the _gaps_ of $S$ (in
some places they are known as _holes_) and the largest integer not in $S$ is
the _Frobenius number_ of $S$, denoted by $\operatorname{F}(S)$. The number
$g=|\operatorname{H}(S)|$ is the _genus_ of $S$.

It is well known that the minimal set of generators of every numerical
semigroup $S$ is finite. The elements of $\mathcal{A}(S)$ are sometimes known
as the _atoms_ (irreducibles, primitive elements) of $S$ or simply minimal
generators. Moreover, the fact that $\mathbb{N}\setminus S$ is finite is
equivalent to impose that the greatest common divisor of its minimal
generating set is one. For an introduction to numerical semigroups please
refer to [14], and also to [2], where it is explained where the names used
above come from.

Among affine semigroups, we are interested in _generalized numerical
semigroups_ , which are submonoids in $\mathbb{N}^{d}$, with $d\geq 2$, and
finite complement in $\mathbb{N}^{d}$ (see [9] and [6]). The notions of _gaps_
and genus can be then stated for generalized numerical semigroups as for
numerical semigroups.

The most important differences between numerical semigroups and generalized
numerical semigroups consist in the identification of a Frobenius element and
those generators larger than this element: $\mathbb{N}$ has a natural total
order while $\mathbb{N}^{d}$ has only a natural partial order (that is induced
by the total order in $\mathbb{N}$). The notions of Frobenius element and
generators greater than the Frobenius element provide a way to build the
semigroup tree of all numerical semigroups up to a given genus (see [4]). The
corresponding notions for generalized numerical semigroups are given in [9] by
introducing particular total orders in $\mathbb{N}^{d}$, called _relaxed
monomial orders_.

######  Definition 1.

A total order, $\preceq$, on the elements of $\mathbb{N}^{d}$ is called a
_relaxed monomial order_ if it satisfies:

  * i)

if $\mathbf{v},\mathbf{w}\in\mathbb{N}^{d}$ and if
$\mathbf{v}\preceq\mathbf{w}$, then $\mathbf{v}\preceq\mathbf{w}+\mathbf{u}$
for all $\mathbf{u}\in\mathbb{N}^{d}$;

  * ii)

if $\mathbf{v}\in\mathbb{N}^{d}$ and $\mathbf{v}\neq\mathbf{0}$, then
$\mathbf{0}\preceq\mathbf{v}$.

######  Example 2.

Among the relaxed monomial orders there are the well known _monomial orders_
as defined, for instance, in [7, Section2]. A classical example is the
following. Let $\alpha,\beta\in\mathbb{N}^{d}$, we define $\alpha\preceq\beta$
if and only if the first nonzero coordinate of $\beta-\alpha$, starting from
the left, is positive. The relation $\preceq$ is called _lexicographic order_
and it is a relaxed monomial order.

Not all relaxed monomial orders are monomial orders. Take, for instance,
$\leq_{m}$ to be an order on $\mathbb{N}^{d}$ induced by a monomial order. We
define $\mathbf{u}\preceq\mathbf{v}$ if

  * •

$\min(\mathbf{u})<\min(\mathbf{v})$ or if

  * •

$\min(\mathbf{u})=\min(\mathbf{v})$ and $\mathbf{u}\leq_{m}\mathbf{v}$. The
order $\preceq$ is a relaxed monomial order that is not a monomial order. For
instance, in $\mathbb{N}^{3}$ we have $(3,1,1)\preceq(2,7,8)$. However,
$(3,1,1)+(0,2,2)\npreceq(2,7,8)+(0,2,2)$, that is, $\preceq$ is not a monomial
order.

Following the proof of Corollary 6 in [7, Section 2.4], we can easily see that
a relaxed monomial order in $\mathbb{N}^{d}$ is a well-ordering. So it is
possible to state the following general definition.

######  Definition 3.

Let $S$ be a submonoid of $\mathbb{N}^{d}$ and $\preceq$ a relaxed monomial
order. We define $\mathbf{m}_{\preceq}(S)$ the smallest element of
$S\setminus\\{\mathbf{0}\\}$ with respect to $\preceq$, and it is called
_multiplicity_ of $S$ with respect to $\preceq$.

For what concerns the notions of Frobenius element and generators greater than
the Frobenius element we follow [9]. It is worth to mention that the same
definition of Frobenius element is stated for every submnoids $S$ of
$\mathbb{N}^{d}$ in [11], with the difference that the existence of a
Frobenius element is not always guaranteed. In particular, the fact that $S$
is a generalized numerical semigroup is a sufficient condition for the
existence of a Frobenius element. A different definition, also inspired in the
numerical semigroup setting, is that of _Frobenius vector_ , as presented in
[1].

######  Definition 4.

Let $S\subseteq\mathbb{N}^{d}$ be a generalized numerical semigroup. Given a
relaxed monomial order $\preceq$ in $\mathbb{N}^{d}$, we define:

  1. (1)

$\mathbf{F}_{\preceq}(S)$ to be the greatest element in $\operatorname{H}(S)$
with respect to $\preceq$, called _Frobenius element_ of $S$ with respect to
$\preceq$ (we write $\mathbf{F}_{\preceq}(\mathbb{N}^{d})=(-1,\ldots,-1)$ for
convenience);

  2. (2)

$\operatorname{U}_{\preceq}(S)$ to be the set of minimal generators greater
than $\mathbf{F}_{\preceq}(S)$ with respect to $\preceq$.

Given a relaxed monomial order in $\mathbb{N}^{d}$, it is possible to arrange
the set $\mathcal{S}_{d}$ of all generalized numerical semigroups in
$\mathbb{N}^{d}$ as a rooted tree $\mathcal{T}_{\preceq}$, with root in
$\mathbb{N}^{d}$ (in the same way as for numerical semigroups, see [4]). In
particular, we can write an algorithm that provides all generalized numerical
semigroups in $\mathbb{N}^{d}$ of a given genus $g$. The following result,
easy to prove and stated in a more general setting, is useful in this context.

######  Proposition 5.

Let $S\subseteq\mathbb{N}^{d}$ be an affine semigroup, and let
$\mathbf{v}\in\mathcal{A}(S)$. Then $S\setminus\\{\mathbf{v}\\}$ is an affine
semigroup and it is generated by
$\left(\mathcal{A}(S)\setminus\\{\mathbf{v}\\}\right)\cup\\{\mathbf{g}+\mathbf{v}\mid\mathbf{g}\in\mathcal{A}(S)\setminus\\{\mathbf{v}\\}\\}\cup\\{2\mathbf{v},3\mathbf{v}\\}$.

######  Remark 6.

The system of generators described in Proposition 5 does not have to be a
minimal generating system.

######  Example 7.

Let $S=\mathbb{N}^{2}\setminus\\{(1,0)\\}$. Then
$\mathcal{A}(S)=\\{(2,0),(3,0),(1,1),(0,1)\\}$. Let $\preceq$ be the
lexicographic order. So $\mathbf{F}_{\preceq}(S)=(1,0)$, and
$(1,1)\in\operatorname{U}_{\preceq}(S)$. Let
$S^{\prime}=S\setminus\\{(1,1)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(1,1)\\}$.
By Proposition 5, $\\{(2,0),(3,0),(0,1),(3,1),(4,1),(1,2),(2,2),(3,3)\\}$ is a
set generating for $S^{\prime}$. However, $(3,0)+(0,1)=(3,1)$, whence $(3,1)$
is not an atom of $S^{\prime}$.

Observe that from the definition of relaxed monomial order, for a given
submonoid $S\subseteq\mathbb{N}^{d}$ and a given relaxed monomial order
$\preceq$, the multiplicity of $S$ with respect to $\preceq$ is a minimal
generator of $S$. Due to its relevance in this work, we state this fact as a
lemma.

######  Lemma 8.

Let $S$ be a submonoid of $\mathbb{N}^{d}$, and let $\preceq$ be relaxed
monomial order on $\mathbb{N}^{d}$. Then
$\mathbf{m}_{\preceq}(S)\in\mathcal{A}(S)$.

As a consequence we get the following result.

######  Corollary 9.

Let $S$ be a submonoid of $\mathbb{N}^{d}$, and let $\preceq$ be a relaxed
monomial order in $\mathbb{N}^{d}$. Then
$S\setminus\\{\mathbf{m}_{\preceq}(S)\\}$ is a submonoid of $\mathbb{N}^{d}$.

If $S$ is a numerical semigroup, and we remove one of its minimal generators,
then we obtain another numerical semigroup, and the genus increases by one. We
can go the other way around by adding gaps to $S$. The only gaps $h$ that make
$S\cup\\{h\\}$ a numerical semigroup are those that are pseudo-Frobenius
numbers of $S$ ($h+(S\setminus\\{0\\})\subseteq S$) fulfilling that $2h\in S$.
These gaps are known as _special gaps_ , and can be used to construct the set
of oversemigroups of a numerical semigroup [15]. If the generator $a$ we
remove from $S$ is greater than its Frobenius number, then this generator
becomes trivially the Frobenius number of $S\setminus\\{a\\}$. Also the
Frobenius number of $S$ is a special gap of $S$ (unless $S=\mathbb{N}$). Thus
adjoining $\operatorname{F}(S)$ to $S$ produces a numerical semigroup. An
analogue for generalized numerical semigroups is given in the following
result, that suggests the idea for a simple procedure to generate all
generalized numerical semigroups in $\mathbb{N}^{d}$ of given genus $g$.

######  Proposition 10.

_[9, Proposition 4.1]_ Let $S\subseteq\mathbb{N}^{d}$ be a generalized
numerical semigroup, $\preceq$ a relaxed monomial order in $\mathbb{N}^{d}$
and $\mathbf{h}$ a minimal generator.

  * •

The set $T=S\cup\\{\mathbf{F}_{\preceq}(S)\\}$ is a generalized numerical
semigroup, moreover $\mathbf{F}_{\preceq}(S)\in\operatorname{U}_{\preceq}(T)$.

  * •

The set $T=S\setminus\\{\mathbf{h}\\}$ is a generalized numerical semigroup.
Furthermore if $\mathbf{h}\in\operatorname{U}_{\preceq}(S)$, then
$\mathbf{F}_{\preceq}(T)=\mathbf{h}$.

In particular, every generalized numerical semigroups of genus $g+1$ is
obtained from a generalized numerical semigroup $S$ of genus $g$, by removing
an element of $\operatorname{U}_{\preceq}(S)$.

Interesting combinatorial properties involving the number of generalized
numerical semigroups in $\mathbb{N}^{d}$ of a given genus are provided in [9].
If $A\subseteq\mathbb{N}^{d}$, we denote by $\mathrm{Span}_{\mathbb{R}}(A)$
the $\mathbb{R}$-vector space spanned by the elements of $A$.

Let $g,d,r\in\mathbb{N}$, with $d$ and $r$ positive. We will use the following
notation.

  * •

$\mathcal{S}_{g,d}$ is the set of all generalized numerical semigroups with
genus $g$ in $\mathbb{N}^{d}$; $N_{g,d}$ is the cardinality of
$\mathcal{S}_{g,d}$.

  * •

$\mathcal{S}_{g,d}^{(r)}=\left\\{S\in\mathcal{S}_{g,d}\mid\dim(\mathrm{Span}_{\mathbb{R}}(\operatorname{H}(S)))=r\right\\}$;
$N_{g,d}^{(r)}$ denotes the cardinality of $\mathcal{S}_{g,d}^{(r)}$.

######  Theorem 11.

[9, Proposition 5.3] Let $g\in\mathbb{N}$, and define

$F_{g}(x):=\sum_{i=1}^{g}N_{g,i}^{(i)}\binom{x}{i}.$

Then $F_{g}(x)$ is a polynomial in $\mathbb{Q}[x]$ with degree $g$, and
$F_{g}(d)=N_{g,d}$ for all $d\in\mathbb{N}$.

##  3\. A first algorithm generating all generalized numerical semigroups of a
given genus

Now we can present a first algorithm that computes the number of all
generalized numerical semigroup in $\mathbb{N}^{d}$ of a given genus $g$, as
explained in [9]. The main idea is the following: starting from the trivial
generalized numerical semigroup $\mathbb{N}^{d}$ of genus $0$, whose set of
generators is the standard basis of the vector space $\mathbb{R}^{d}$, denoted
by $\\{\mathbf{e}_{1},\ldots,\mathbf{e}_{d}\\}$, we produce all generalized
numerical semigroups of genus $k$ from the ones of genus $k-1$, for $k$ from
$1$ up to $g$. Fixed a relaxed monomial order $\preceq$, for every generalized
numerical semigroup $S$ of genus $k-1$, if
$\operatorname{U}_{\preceq}(S)=\\{\mathbf{g}_{1},\ldots,\mathbf{g}_{m}\\}$, we
produce the generalized numerical semigroups
$S\setminus\\{\mathbf{g}_{1}\\},\ldots,S\setminus\\{\mathbf{g}_{m}\\}$, all of
them with genus $k$. In this way all generalized numerical semigroups of genus
$k$ are produced. If we consider the directed graph $\mathcal{T}_{\preceq}$
whose set of vertices is the set of all generalized numerical semigroups, and
whose edges are the pairs $(S,S\cup\\{\mathbf{F}_{\preceq}(S)\\})$ (we say
that is $S$ is a _son_ of $S\cup\\{\mathbf{F}_{\preceq}(S)\\}$) with $S$ a
generalized numerical semigroup, $S\subsetneq\mathbb{N}^{d}$. Remark that, in
$\mathcal{T}_{\preceq}$, the generalized numerical semigroups are produced
without redundancy, that is, every generalized numerical semigroup
$S\neq\mathbb{N}^{d}$ is the son of a unique generalized numerical semigroup.
In fact, if $S$ is the son of both $T_{1}$ and $T_{2}$, then
$T_{1}=S\cup\\{\mathbf{F}_{\preceq}(S)\\}=T_{2}$. By using Proposition 10, we
have the following result.

######  Theorem 12.

Let $\preceq$ be a relaxed monomial order. Then the graph
$\mathcal{T}_{\preceq}$ is a rooted tree whose root is $\mathbb{N}^{d}$.
Moreover, if $S$ is a generalized numerical semigroup, then the sons of $S$
are $S\setminus\\{\mathbf{g}_{1}\\},\ldots,S\setminus\\{\mathbf{g}_{m}\\}$
with
$\operatorname{U}_{\preceq}(S)=\\{\mathbf{g}_{1},\ldots,\mathbf{g}_{m}\\}$,
and there is a unique path in $\mathcal{T}_{\preceq}$ joining $S$ and
$\mathbb{N}$.

Recall that we denote by $\mathcal{S}_{g,d}$ the set of generalized numerical
semigroups in $\mathbb{N}^{d}$ of genus $g$, and
$N_{g,d}=|\mathcal{S}_{g,d}|$. From the above discussion, the computation of
$N_{g,d}$ may be done by computing of the sets
$\operatorname{U}_{\preceq}(S)$, for all $S\in\mathcal{S}_{g-1,d}$. So to
obtain $N_{g,d}$ we do not need actually to compute every semigroups in
$\mathcal{S}_{g,d}$.

######  Corollary 13.

Let $g,d\in\mathbb{N}^{d}$ and $\preceq$ be a relaxed monomial order. Then

$N_{g,d}=\sum_{S\in\mathcal{S}_{g-1,d}}|\operatorname{U}_{\preceq}(S)|.$

Data: Two integers $g,d\in\mathbb{N}$ and a relaxed monomial order $\preceq$.

Result: $N_{g,d}$

1$G=\\{\mathbf{e}_{1},\mathbf{e}_{2},\dots,\mathbf{e}_{d}\\}$,
$S_{0,d}=\\{(\mathbb{N}^{d},G)\\}$, $N_{0,d}=1$,
$\mathbf{F}_{\preceq}(\mathbb{N}^{d})=(-1,\ldots,-1)$,
$\operatorname{H}(\mathbb{N}^{d})=\emptyset$.

for  _$i\in\\{0,\ldots,g\\}$_ do

2 $S_{i,d}=\\{(S^{(j)},A^{(j)})\mid j\in\\{1,\ldots,N_{i,d}\\}\\}$, where
$\langle A^{(j)}\rangle=S^{(j)}$, $|A^{(j)}|<\infty$.

$N_{i+1,d}=0$.

for  _$j\in\\{1,\ldots,N_{i,d}\\}$_ do

3 From $(S^{(j)},A^{(j)})$ find out $\mathcal{A}(S^{(j)})$ and
$E^{(j)}=\operatorname{U}_{\preceq}(S^{(j)})$.

$N_{i+1,d}=N_{i+1,d}+|E^{(j)}|$.

4if  _$i+1=g$_ then

return $N_{g,d}$.

STOP

$S_{i+1,d}=\emptyset$.

for  _$j\in\\{1,\ldots,N_{i,d}\\}$_ do

$\\{\mathbf{g}_{1},\mathbf{g}_{2},\ldots,\mathbf{g}_{|E^{(j)}|}\\}=E^{(j)}$.

for  _$k\in\\{1,\ldots,|E^{(j)}|\\}$_ do

$S^{(j,k)}=S^{(j)}\setminus\\{\mathbf{g}_{k}\\}$.

$\mathbf{F}_{\preceq}(S^{(j,k)})=\mathbf{g}_{k}$.

5 Build $A^{(j,k)}$, with $|A^{(j,k)}|<\infty$, such that $\langle
A^{(j,k)}\rangle=S^{(j,k)}$.

$\operatorname{H}(S^{(j,k)})=\operatorname{H}(S^{(j)})\cup\\{\mathbf{g}_{k}\\}$.

$S_{i+1,d}=S_{i+1,d}\cup\\{(S^{(j,k)},A^{(j,k)})\\}$.

Algorithm 1 Algorithm for computing $N_{g,d}$

Algorithm 1 consists of pseudocode for the procedure discussed above for
computing $N_{g,d}$. We have labeled some lines of the pseudocode in order to
explain them further.

  * •

Line 1 contains the initial step of the algorithm, that is, the root of
$\mathcal{T}_{\preceq}$. It starts from the trivial generalized numerical
semigroup $\mathbb{N}^{d}$, which is finitely generated by the standard-basis
vectors and whose set of gaps is empty. Moreover, it is the unique generalized
numerical semigroup of genus 0, so $N_{0,d}=1$.

  * •

Line 1: $S_{i,d}$ is the set of all generalized numerical semigroups in
$\mathbb{N}^{d}$ of genus $i$; we represent each one of these semigroups
$S^{(j)}$ by a finite system of generators $A^{(j)}$.

  * •

Line 1: $A^{(j)}$ is not in general the minimal system of generators for
$S^{(j)}$; a refinement is needed to find $\mathcal{A}(S^{(j)})$ and
$\operatorname{U}_{\preceq}(S^{(j)})$ to continue the process.

  * •

Lines 1 and successive: if $i+1=g$, then $N_{g,d}$ is computed and the
algorithm ends. One can compute also the set $\mathcal{S}_{g,d}$, it suffices
to run another extra for-loop step. If $i+1<g$, all generalized numerical
semigroups of genus $i+1$ are produced from the generalized numerical
semigroups of genus $i$, by Proposition 10.

  * •

Line 1: a finite system of generators $A^{(j,k)}$ for $S^{(j,k)}$ can be
obtained from Proposition 5.

######  Remark 14.

In Line 3 it is required to compute the set of minimal generators of a
generalized numerical semigroup $S$, once a finite set of generators $A$ of
$S$ is known. This can be performed in different ways. For instance, we can
try to decide when an element $\mathbf{v}\in A$ is linear combination of
elements in $A\setminus\\{\mathbf{v}\\}$ with non negative integers
coefficients. This passes through determining the existence of nonnegative
integer solutions of a linear system of Diophantine equations. Also, we can
observe that $\mathbf{v}\in\mathcal{A}(S)$ if and only if
$\mathbf{v}-\mathbf{g}\notin S$ for every generator $\mathbf{g}\in
A\setminus\\{\mathbf{v}\\}$. This can be performed recursively, or in the case
we know the gaps of $S$, this test is straightforward. The caveat of this
latter approach is memory usage, since we would need to store the set of gaps
for all semigroups computed.

The previous algorithm produces the rooted tree $\mathcal{T}_{\preceq}$, where
the root is $\mathbb{N}^{d}$ and the elements of depth $g$ are all generalized
numerical semigroups of genus $g$. Different relaxed monomial orders will
produce different rooted trees, as the Frobenius elements and the generators
greater than them depend on the chosen monomial order. However, with every
relaxed monomial order, the sons of all generalized numerical semigroups of
genus $g-1$ are going to be all generalized numerical semigroups of genus $g$,
generated without redundancy. Thus these trees all have at level $g$ the set
of all generalized numerical semigroups with genus $g$.

##  4\. An algorithm to compute minimal generators of a generalized numerical
semigroup from its set of gaps

Let $S\subseteq\mathbb{N}^{d}$ be a generalized numerical semigroup and let
$\preceq$ be a relaxed monomial order. We suppose that the set
$\operatorname{H}(S)$ of gaps is known and we want to find the set
$\mathcal{A}(S)$ of minimal generators of $S$. If $S=\mathbb{N}^{d}$, then we
know that $S$ is generated by
$\\{\mathbf{e}_{1},\mathbf{e}_{2},\dots,\mathbf{e}_{d}\\}$, the standard basis
vectors of $\mathbb{R}^{d}$. If $S$ is a proper subset of $\mathbb{N}^{d}$,
our procedure is based on the following result, that can be found in a more
general setting in [13, Corollary 9].

######  Corollary 15.

Let $S\subset\mathbb{N}^{d}$ be a generalized numerical semigroup of genus $g$
and let $\preceq$ be a relaxed monomial order in $\mathbb{N}^{d}$. Suppose
that
$\operatorname{H}(S)=\\{\mathbf{h}_{1}\preceq\mathbf{h}_{2}\preceq\dots\preceq\mathbf{h}_{g}\\}$.
Then

  * •

$\mathbf{h}_{1}$ is a minimal generator of $\mathbb{N}^{d}$,

  * •

for every $i\in\\{2,\ldots,g\\}$,
$S\setminus\\{\mathbf{h}_{1},\mathbf{h}_{2},\ldots,\mathbf{h}_{i-1}\\}$ is a
generalized numerical semigroup, and

  * •

$\mathbf{h}_{i}\in\operatorname{U}_{\preceq}(S\setminus\\{\mathbf{h}_{1},\mathbf{h}_{2},\ldots,\mathbf{h}_{i-1}\\})$,
for every $i\in\\{2,\ldots,g\\}$.

###### Proof.

It follows easily from Proposition 10, since
$\mathbf{h}_{i}=\mathbf{F}_{\preceq}(S\setminus\\{\mathbf{h}_{1},\mathbf{h}_{2},\ldots,\mathbf{h}_{i}\\})$.
∎

Data: A set
$H=\\{\mathbf{h}_{1},\mathbf{h}_{2},\ldots,\mathbf{h}_{g}\\}\subseteq\mathbb{N}^{d}$,
a relaxed monomial order $\preceq$

Result: If $S=\mathbb{N}^{d}\setminus H$ is a generalized numerical semigroup,
$\mathcal{A}(S)$ is computed

1
$H_{\preceq}=\\{\mathbf{h}_{j_{1}}\preceq\mathbf{h}_{j_{2}}\preceq\ldots\preceq\mathbf{h}_{j_{g}}\\}$,
$lH=\emptyset$, $G=\\{\mathbf{e}_{1},\mathbf{e}_{2},\ldots,\mathbf{e}_{d}\\}$.

for  _$i\in\\{1,\ldots,g\\}$_ do

if  _$\mathbf{h}_{j_{i}}\notin G$_ then

$\mathbb{N}^{d}\setminus H$ is not a generalized numerical semigroup.

STOP

$lH=lH\cup\\{\mathbf{h}_{j_{i}}\\}$.

$G=G\setminus\\{\mathbf{h}_{j_{i}}\\}$

2 $A=\\{\mathbf{g}+\mathbf{h}_{j_{i}}\mid\mathbf{g}\in
G\\}\cup\\{2\mathbf{h}_{j_{i}},3\mathbf{h}_{j_{i}}\\}$

for  _$\mathbf{v}\in A$_ do

3 if  _$\mathbf{v}$ _is a minimal generator of_ $\mathbb{N}^{d}\setminus lH$_
then

$G=G\cup\\{\mathbf{v}\\}$.

return $G$

Algorithm 2 Algorithm to compute $\mathcal{A}(S)$ from the set
$\operatorname{H}(S)$

As above, we have labeled some lines in the pseudo code in order to explain
how it works.

  * •

Line 1: we arrange the elements of $H$ with respect to $\preceq$.

  * •

Line 2: at this point $G\cup A$ is a finite set of generators of
$\mathbb{N}^{d}\setminus lH$ (Proposition 5); a refiniement into a minimal
generating set is performed in the next steps.

  * •

Line 3: the elements in $G$ are already minimal generators of
$\mathbb{N}^{d}\setminus lH$, so we only have to decice which element in $A$
are minimal generators. Observe that $\mathbf{v}$ is a minimal generator of a
semigroup $S$ if and only if $\mathbf{v}-\mathbf{g}\notin S$ for every
generator $\mathbf{g}$ of $S$, and in this case we have the advantage of
knowing the gap set of the semigroup computed.

Observe that while Algorithm 1 covers all the branches of the tree
$\mathcal{T}_{\preceq}$ with respect to $\preceq$ (up to depth $g$), Algorithm
2 walks through the unique branch linking $\mathbb{N}^{d}$ with
$S=\mathbb{N}^{d}\setminus H$, in the case $S$ is actually a generalized
numerical semigroup such that $\operatorname{H}(S)=H$. Moreover, Algorithm 2
can verify if a given finite set $H\subseteq\mathbb{N}^{d}$ has the property
that $\mathbb{N}^{d}\setminus H$ is a generalized numerical semigroup.
Another way to test if a given set is the set of gaps of a submonoid in
$\mathbb{N}^{d}$ is provided by the next result. For
$\mathbf{x}\in\mathbb{N}^{d}$ we define

$\operatorname{B}(\mathbf{x})=\\{\mathbf{n}\in\mathbb{N}^{d}\mid\mathbf{n}\leq\mathbf{x}\\},$

where $\leq$ denotes the usual partial order in $\mathbb{N}^{d}$.

######  Proposition 16.

Let $H\subset\mathbb{N}^{d}\setminus\\{\mathbf{0}\\}$. Then
$\mathbb{N}^{d}\setminus H$ is a monoid if and only if for every
$\mathbf{h}\in H$, $\mathbf{h}-\mathbf{x}\in H$ for all
$\mathbf{x}\in\operatorname{B}(\mathbf{h})\setminus H$.

###### Proof.

_Necessity_. Suppose there exists $\mathbf{h}\in H$ such that
$\mathbf{y}=\mathbf{h}-\mathbf{x}\notin H$ for some
$\mathbf{x}\in\operatorname{B}(\mathbf{h})\setminus H$. Then
$\mathbf{h}=\mathbf{x}+\mathbf{y}$ with
$\mathbf{x},\mathbf{y}\in\mathbb{N}^{d}\setminus H$; a contradiction.

_Sufficiency_. Suppose that $\mathbb{N}^{d}\setminus H$ is not a monoid. Then
there exists $\mathbf{h}\in H$ such that $\mathbf{h}=\mathbf{x}+\mathbf{y}$
with $\mathbf{x},\mathbf{y}\in\mathbb{N}^{d}\setminus H$. In particular,
$\mathbf{x}\in\operatorname{B}(\mathbf{h})\setminus H$ and
$\mathbf{h}-\mathbf{x}\notin H$, contradicting the hypothesis. ∎

Observe that $\operatorname{B}(\mathbf{h})$ is a finite set for each
$\mathbf{h}\in\mathbb{N}^{d}$. So if $H$ is a finite set, the condition in the
previous proposition is easy to test. In particular, it is also possible to
obtain a procedure to test if a given finite set $H$ is the set of gaps of a
generalized numerical semigroup, without using Algorithm 2.

##  5\. An algorithm to compute the set of gaps of a generalized numerical
semigroup from a generating set

Let $S\subseteq\mathbb{N}^{d}$ be a generalized numerical semigroup and
suppose that a finite set of (not necessarily minimal) generators is known. A
possible way to compute $\operatorname{H}(S)$ is via the following
characterization that appears in [6].

######  Theorem 17.

[6, Theorem 2.8] Let $d\geq 2$ and let $S=\langle A\rangle$ be the monoid
generated by a set $A\subseteq\mathbb{N}^{d}$. Then $S$ is a generalized
numerical semigroup if and only if the set $A$ fulfills the following
conditions.

  1. (1)

For all $j\in\\{1,2,\ldots,d\\}$, there exist
$a_{1}^{(j)},a_{2}^{(j)},\ldots,a_{r_{j}}^{(j)}$,
$r_{j}\in\mathbb{N}\setminus\\{0\\}$, such that
$\gcd(a_{1}^{(j)},a_{2}^{(j)},\ldots,a_{r_{j}}^{(j)})=1$, and
$a_{1}^{(j)}\mathbf{e}_{j},a_{2}^{(j)}\mathbf{e}_{j},\ldots,a_{r_{j}}^{(j)}\mathbf{e}_{j}\in
A$. In particular, if $S_{i}$ is the intersection of $S$ with the $i$th
coordinate, then $S_{i}$ is a numerical semigroup.

  2. (2)

For every $i,k\in\\{1,\ldots,d\\}$, with $i<k$, there exist
$\mathbf{x}_{ik},\mathbf{x}_{ki}\in A$ such that
$\mathbf{x}_{ik}=\mathbf{e}_{i}+n_{i}^{(k)}\mathbf{e}_{k}$ and
$\mathbf{x}_{ki}=\mathbf{e}_{k}+n_{k}^{(i)}\mathbf{e}_{i}$ for some
$n_{i}^{(k)},n_{k}^{(i)}\in\mathbb{N}$.

Furthermore, if we define
$\mathbf{v}=(v^{(1)},v^{(2)},\ldots,v^{(d)})\in\mathbb{N}^{d}$ as

$v^{(j)}=\sum_{i\neq
j}^{d}\operatorname{F}^{(i)}n_{i}^{(j)}+\operatorname{F}^{(j)},$

where $\operatorname{F}^{(i)}=\max\\{\operatorname{F}(S_{i}),0\\}$ for all
$i$, then $\operatorname{H}(S)\subseteq\operatorname{B}(\mathbf{v})$.

Data: A finite set $A\subseteq\mathbb{N}^{d}$

Result: If $S:=\langle A\rangle$ is a generalized numerical semigroup,
$\operatorname{H}(S)$ is computed

1 for  _$i\in\\{1,\ldots,d\\}$_ do

Gather in a set $A_{j}$ the elements $a\in\mathbb{N}$ such $a\mathbf{e}_{j}\in
A$ .

if  _$S_{j}=\langle A_{j}\rangle$ is a numerical semigroup_ then

Compute $\operatorname{F}^{(i)}=\max\\{\operatorname{F}(S_{j}),0\\}$

else

$\langle A\rangle$ is not a generalized numerical semigroup

STOP

2for  _$i\in\\{1,\ldots,d\\}$_ do

for  _$k\in\\{1,\ldots,d\\}$ , $k\neq i$_ do

Find $n_{i}^{(k)}\in\mathbb{N}$ such that
$\mathbf{e}_{i}+n_{i}^{(k)}\mathbf{e}_{k}\in A$

if  _$n_{i}^{(k)}$ does not exist_ then

$\langle A\rangle$ is not a generalized numerical semigroup

STOP

3for  _$i\in\\{1,\ldots,d\\}$_ do

$v^{(j)}=\sum_{i\neq j}^{d}F^{(i)}n_{i}^{(j)}+F^{(j)}$

$\mathbf{v}=(v^{(1)},v^{(2)},\ldots,v^{(d)})$

$\operatorname{B}(\mathbf{v})=\\{\mathbf{n}\in\mathbb{N}^{d}\mid\mathbf{n}\leq\mathbf{v}\\}$

$\operatorname{H}(S)=\emptyset$

4 for  _$\mathbf{x}\in\operatorname{B}(\mathbf{v})$_ do

if  _$\mathbf{x}\notin\langle A\rangle$_ then

$\operatorname{H}(S)=\operatorname{H}(S)\cup\\{\mathbf{x}\\}$

return $\operatorname{H}(S)$

Algorithm 3 Algorithm to compute $\operatorname{H}(S)$ from a finite set $A$
such that $\langle A\rangle=S$

A brief description of main parts of the algorithm follows.

  * •

Line 1: we check if the first condition of Theorem 17 holds; if not, $A$ does
not generate a generalized numerical semigroup.

  * •

Line 2: we check if the second condition of Theorem 17 is satisfied, and if
this is not the case, $A$ does not generate a generalized numerical semigroup.

  * •

Line 3: we compute all coordinates of the vector $\mathbf{v}$ referred in
Theorem 17 such that
$\operatorname{H}(S)\subseteq\operatorname{B}(\mathbf{v})$.

  * •

Line 4: observe that $\operatorname{B}(\mathbf{v})$ is a finite set, so we
have to look for the gaps of the semigroup among a finite number of elements.

##  6\. An alternative procedure to compute all generalized numerical
semigroups of given genus

The algorithm described in Section 3 allows to obtain all generalized
numerical semigroups in $\mathbb{N}^{d}$ up to genus $g$, and in particular,
to compute $N_{g,d}$, the cardinality of $\mathcal{S}_{g,d}$. Observe that
with that procedure, in order to compute $N_{g,d}$ one has to compute all
$N_{g^{\prime},d}$ for all $g^{\prime}<g$, that is, the whole semigroup tree
$\mathcal{T}_{\preceq}$ up to level $g$.

In this section we define a rooted tree that contains all generalized
numerical semigroups in $\mathbb{N}^{d}$ of fixed genus $g$, so that we are
able to compute the set $\mathcal{S}_{g,d}$ without considering all
generalized numerical semigroups of genus less than $g$. Such rooted tree is
inspired by the _ordinarization tranform_ for numerical semigroups, introduced
in [5].

######  Proposition 18.

Let $\preceq$ be a relaxed monomial order in $\mathbb{N}^{d}$ and
$\mathbf{s}\in\mathbb{N}^{d}$. Suppose that the set
$\\{\mathbf{t}\in\mathbb{N}^{d}\mid\mathbf{t}\preceq\mathbf{s}\\}$ is finite.
Then the set
$S=\\{\mathbf{x}\in\mathbb{N}^{d}\mid\mathbf{s}\prec\mathbf{x}\\}\cup\\{\mathbf{0}\\}$
is a generalized numerical semigroup.

###### Proof.

By hypothesis, $\mathbb{N}^{d}\setminus S$ is finite. Moreover if
$\mathbf{x},\mathbf{y}\in S$ then $\mathbf{s}\preceq\mathbf{x}$ and
$\mathbf{s}\preceq\mathbf{y}$, so $\mathbf{s}\preceq\mathbf{x}+\mathbf{y}$
since $\preceq$ is a relaxed monomial order. ∎

######  Definition 19.

Let $\preceq$ be a relaxed monomial order. A monoid $S\subseteq\mathbb{N}^{d}$
satisfying the hypothesis of the above proposition is an _ordinary_
generalized numerical semigroup with respect to $\preceq$.

Let
$\\{\mathbf{0}=\mathbf{s}_{0}\preceq\mathbf{s}_{1}\preceq\cdots\preceq\mathbf{s}_{g}\\}$
be the list of the first $g+1$ elements in $\mathbb{N}^{d}$, ordered by
$\preceq$. We denote the ordinary generalized numerical semigroup in
$\mathbb{N}^{d}$ of genus $g$ with respect to $\preceq$ by

$R_{g,d}(\preceq)=\\{\mathbf{x}\in\mathbb{N}^{d}\mid\mathbf{s}_{g}\prec\mathbf{x}\\}\cup\\{\mathbf{0}\\}.$

Observe that the previous definition of ordinary generalized numerical
semigroup depends strongly on the relaxed monomial order defined: different
relaxed monomial orders define different ordinary generalized numerical
semigroup of given genus. While for numerical semigroups, once $g$ is fixed,
there exists a unique ordinary numerical semigroup of genus $g$, for
generalized numerical semigroups (following the above definition) the
uniqueness of the ordinary generalized numerical semigroup of genus $g$ can
only be guaranteed by fixing also a relaxed monomial order $\preceq$.

If $S\subseteq\mathbb{N}^{d}$ is a generalized numerical semigroup, we can
define the set of _special gaps_ of $S$ as

$\operatorname{SG}(S)=\\{\mathbf{h}\in\operatorname{H}(S)\mid 2\mathbf{h}\in
S,\mathbf{h}+\mathbf{s}\in S\ \mbox{for all}\ \mathbf{s}\in
S\setminus\\{0\\}\\}.$

Observe that $\operatorname{H}(S)$ and $\operatorname{SG}(S)$ do not depend on
the fixed relaxed monomial order. The following result, which is the analogue
to [14, Proposition 4.33] for generalized numerical semigroups, characterizes
the elements in $\operatorname{SG}(S)$. It highlights the duality between the
concepts of minimal generator and special gap. The proof is straightforward
and we will omit it.

######  Proposition 20.

Let $S\subseteq\mathbb{N}^{d}$ be a generalized numerical semigroup and let
$\mathbf{h}\in\operatorname{H}(S)$. Then $S\cup\\{\mathbf{h}\\}$ is a
generalized numerical semigroup if and only if
$\mathbf{h}\in\operatorname{SG}(S)$.

The following result will help us to construct a generalized numerical
semigroup from another by removing the multiplicity and adding the Frobenius
element, and thus keeping the genus untouched.

######  Lemma 21.

Let $S\subsetneq\mathbb{N}^{d}$ be a generalized numerical semigroup, let
$\preceq$ be a relaxed monomial order and suppose that $S$ is not ordinary
with respect to $\preceq$. If
$T=(S\cup\\{\mathbf{F}_{\preceq}(S)\\})\setminus\\{\mathbf{m}_{\preceq}(S)\\}$,
then

  * •

$T$ is a generalized numerical semigroup,

  * •

$\mathbf{m}_{\preceq}(S)\in\operatorname{SG}(T)$,
$\mathbf{m}_{\preceq}(S)\prec\mathbf{m}_{\preceq}(T)$, and

  * •

$\mathbf{F}_{\preceq}(S)\in\operatorname{U}_{\preceq}(T\cup\\{\mathbf{m}_{\preceq}(S)\\})\setminus\\{\mathbf{m}_{\preceq}(S)\\}$.

###### Proof.

From the definition of relaxed monomial order,
$\mathbf{F}_{\preceq}(S)\in\operatorname{SG}(S)$. Hence
$S\cup\\{\mathbf{F}_{\preceq}(S)\\}$ is a generalized numerical semigroup in
light of Proposition 20. Since $S$ is not ordinary, we have that
$\mathbf{m}_{\preceq}(S)\preceq\mathbf{F}_{\preceq}(S)$. In fact, if $S$ is
not ordinary, there exist $\mathbf{s}\in S$ and $\mathbf{h}\in H(S)$ such that
$\mathbf{s}\prec\mathbf{h}$, and in particular
$\mathbf{m}_{\preceq}(S)\preceq\mathbf{s}\prec\mathbf{h}\preceq\mathbf{F}_{\preceq}(S)$.
It follows that
$\mathbf{m}_{\preceq}(S)=\mathbf{m}_{\preceq}(S\cup\\{\mathbf{F}_{\preceq}(S)\\})$.
Thus, by Corollary 9, $T$ is a generalized numerical semigroup.

Also, as
$T\cup\\{\mathbf{m}_{\preceq}(S)\\}=S\cup\\{\mathbf{F}_{\preceq}(S)\\}$ is a
generalized numerical semigroup, we have
$\mathbf{m}_{\preceq}(S)\prec\mathbf{m}_{\preceq}(T)$ and, by Proposition 20,
$\mathbf{m}_{\preceq}(S)\in\operatorname{SG}(T)$. Moreover,
$\mathbf{F}_{\preceq}(S)$ is a minimal generator of
$T\cup\\{\mathbf{m}_{\preceq}(S)\\}$ and
$\mathbf{m}_{\preceq}(S)\neq\mathbf{F}_{\preceq}(S)\succ\mathbf{F}_{\preceq}(T\cup\\{\mathbf{m}_{\preceq}(S)\\})$.
∎

######  Definition 22.

Recall that $\mathcal{S}_{g,d}$ is the set of all generalized numerical
semigroups in $\mathbb{N}^{d}$ of genus $g$. We define the _ordinarization
transform_ with respect to $\preceq$,
$\mathcal{O}_{\preceq}:\mathcal{S}_{g,d}\rightarrow\mathcal{S}_{g,d}$ as
follows:

$\mathcal{O}_{\preceq}(S)=\begin{cases}(S\cup\\{\mathbf{F}_{\preceq}(S)\\})\setminus\\{\mathbf{m}_{\preceq}(S)\\},&\hbox{if
}S\hbox{is not ordinary},\\\ S,&\hbox{otherwise}.\end{cases}$

Note that this map is well defined by Lemma 21.

######  Lemma 23.

Let $T\subseteq\mathbb{N}^{d}$ be a generalized numerical semigroup and
$\preceq$ a relaxed monomial order in $\mathbb{N}^{d}$. If there exist
$\mathbf{h}\in\operatorname{SG}(T)$ with
$\mathbf{h}\prec\mathbf{m}_{\preceq}(T)$ and
$\mathbf{x}\in\operatorname{U}_{\preceq}(T\cup\\{\mathbf{h}\\})\setminus\\{\mathbf{h}\\}$,
then
$\mathcal{O}_{\preceq}((T\cup\\{\mathbf{h}\\})\setminus\\{\mathbf{x}\\})=T$.

###### Proof.

If $S=(T\cup\\{\mathbf{h}\\})\setminus\\{\mathbf{x}\\}$, then we have
$T=(S\cup\\{\mathbf{x}\\})\setminus\\{\mathbf{h}\\}$, and so in light of Lemma
21, it suffices to prove that $\mathbf{h}=\mathbf{m}_{\preceq}(S)$ and
$\mathbf{x}=\mathbf{F}_{\preceq}(S)$. Since
$\mathbf{h}\preceq\mathbf{m}_{\preceq}(T)$, we deduce
$\mathbf{h}\preceq\mathbf{t}$ for every $\mathbf{t}\in T$, and consequently
$\mathbf{h}=\mathbf{m}_{\preceq}(S)$. Furthermore, since
$\mathbf{x}\in\operatorname{U}_{\preceq}(T\cup\\{\mathbf{m}_{\preceq}(S)\\})$,
we get
$\mathbf{x}\succ\mathbf{F}_{\preceq}(T\cup\\{\mathbf{h}\\})=\mathbf{F}_{\preceq}(S\cup\\{\mathbf{x}\\})$,
whence $\mathbf{x}=\mathbf{F}_{\preceq}(S)$. ∎

Let $g\in\mathbb{N}$, $\preceq$ be a relaxed monomial order in
$\mathbb{N}^{d}$, and $\mathcal{E}$ be the set of pairs of the form
$(S,\mathcal{O}_{\preceq}(S))$. We denote the directed graph
$(\mathcal{S}_{g,d},\mathcal{E})$ by $\mathcal{T}_{g,\preceq}^{d}$.

######  Theorem 24.

Let $g\in\mathbb{N}$. The graph $\mathcal{T}_{g,\preceq}^{d}$ is a rooted tree
with root $R_{g,d}(\preceq)$. Moreover, if $T\in\mathcal{S}_{g,d}$, then the
sons of $T$ are the semigroups of the form
$(T\cup\\{\mathbf{h}\\})\setminus\\{\mathbf{x}\\}$ with
$\mathbf{h}\in\operatorname{SG}(T)$, $\mathbf{h}\prec\mathbf{m}_{\preceq}(T)$,
and
$\mathbf{x}\in\operatorname{U}_{\preceq}(T\cup\\{\mathbf{h}\\})\setminus\\{\mathbf{h}\\}$.

###### Proof.

Let $T\in\mathcal{S}_{g,d}$, we define the following sequence:

  * •

$T_{0}=T$,

  * •

$T_{i+1}=\left\\{\begin{array}[]{ll}\mathcal{O}_{\preceq}(T_{i})&\mbox{if
}T_{i}\neq R_{g,d}(\preceq),\\\
R_{g,d}(\preceq)&\mbox{otherwise,}\end{array}\right.$

in particular $T_{i}=\mathcal{O}_{\preceq}^{i}(T)$ for all $i$. This sequence
stabilizes at a certain point, since the multiplicity must be among the first
$g+1$ elements of $\mathbb{N}^{d}$ (ordered by $\preceq$), and at each step
the multiplicity increases. Let $k$ be the first integer such that
$T_{k}=R_{g,d}(\preceq)$. So the edges
$(T_{0},T_{1}),(T_{1},T_{2}),\ldots,(T_{k-1},T_{k})$ provide the unique path
from $T$ to the ordinary numerical semigroup of genus $g$ (with respect to
$\preceq$).

By Lemma 23, every pair $(T\cup\\{\mathbf{h}\\})\setminus\\{\mathbf{x}\\},T)$
is an edge of $\mathcal{T}_{g,\preceq}^{d}$ for every choice of $\mathbf{h}$
and $\mathbf{x}$ as in the statement, that is
$(T\cup\\{\mathbf{h}\\})\setminus\\{\mathbf{x}\\},T)$ is a son of $T$.
Conversely let $(S,T)$ be an edge of $\mathcal{T}_{g,\preceq}^{d}$. From the
definition we have $T=\mathcal{O}_{\preceq}(S)$ so
$T=(S\cup\\{\mathbf{F}_{\preceq}(S)\\})\setminus\\{\mathbf{m}_{\preceq}(S)\\}$.
In particular
$S=(T\cup\\{\mathbf{m}_{\preceq}(S)\\}\setminus\\{\mathbf{F}_{\preceq}(S)\\}$
and from Lemma 21 we have $\mathbf{m}_{\preceq}(S)\in\operatorname{SG}(T)$
with $\mathbf{m}_{\preceq}(S)\prec\mathbf{m}_{\preceq}(T)$, and
$\mathbf{F}_{\preceq}(S)\in\operatorname{U}_{\preceq}(T\cup\\{\mathbf{m}_{\preceq}(S)\\})\setminus\\{\mathbf{m}_{\preceq}(S)\\}$.
This fact ensures that all descendants in $\mathcal{T}_{g,\preceq}^{d}$ of a
generalized numerical semigroup are of the described form. ∎

######  Corollary 25.

Let $T\in\mathcal{S}_{g,d}$. Then $T$ is a leaf in
$\mathcal{T}_{g,\preceq}^{d}$ if and only if for all
$\mathbf{h}\in\operatorname{SG}(T)$ either
$\mathbf{h}\succ\mathbf{m}_{\preceq}(T)$ or
$\operatorname{U}_{\preceq}(T\cup\\{\mathbf{h}\\})\subseteq\\{\mathbf{h}\\}$.

Theorem 24 allow us to write another algorithm to produce all generalized
numerical semigroups in $\mathbb{N}^{d}$ of genus $g$; the previous corollary
gives us the stop condition.

Data: Two integers $g,d\in\mathbb{N}$ and a relaxed monomial order $\preceq$
in $\mathbb{N}^{d}$.

Result: $\mathcal{S}_{g,d}$

Compute $R_{g,d}(\preceq)$.

$\mathcal{S}_{g,d}=\\{R_{g,d}(\preceq)\\},\mathcal{L}=\\{R_{g,d}(\preceq)\\}$.

1 while  _Exists $S\in\mathcal{L}$ _such that_
$\\{\mathbf{h}\in\operatorname{SG}(S)\mid\mathbf{h}\preceq\mathbf{m}_{\preceq}(S)\\}\neq\emptyset$_
do

$\mathcal{I}=\emptyset$

for  _$S\in\mathcal{L}$_ do

if
_$\\{\mathbf{h}\in\operatorname{SG}(S)\mid\mathbf{h}\preceq\mathbf{m}_{\preceq}(S)\\}\neq\emptyset$_
then

$\mathcal{R}=\emptyset$

2 for
_$\mathbf{h}\in\\{\mathbf{h}\in\operatorname{SG}(S)\mid\mathbf{h}\preceq\mathbf{m}_{\preceq}(S)\\}$_
do

$\mathcal{R}=\mathcal{R}\cup\\{S\cup\\{\mathbf{h}\\}\\}$

3for  _$T\in\mathcal{R}$_ do

for  _$\mathbf{x}\in\operatorname{U}_{\preceq}(T)$ with
$\mathbf{x}\neq\mathbf{m}_{\preceq}(S)$_ do

$\mathcal{I}=\mathcal{I}\cup\\{T\setminus\\{x\\}\\}$

$\mathcal{S}_{g,d}=\mathcal{S}_{g,d}\cup\mathcal{I}$

4 $\mathcal{L}=\mathcal{I}$

return $\mathcal{S}_{g,d}$

Algorithm 4 Algorithm for computing the set $\mathcal{S}_{g,d}$

Let us give a few comments regarding the labeled lines of Algorithm 4.

  * •

Line 1: the algorithm stops when all computed semigroups are leaves of
$\mathcal{T}_{g,\preceq}^{d}$; we gather in $\mathcal{L}$ the semigroups for
which we have to do computations at each step.

  * •

Line 2: for each semigroup $S$ of the current step we have to compute its
sons, and for this we need all semigroups $S\cup\\{\mathbf{h}\\}$ with
$\mathbf{h}\in\operatorname{SG}(S)$ and smaller than $\mathbf{m}_{\preceq}(S)$
with respect to $\preceq$.

  * •

Line 3: for each semigroup $T$ computed in the previous line we compute
$T\setminus\\{\mathbf{x}\\}$ for all
$\mathbf{x}\in\operatorname{U}_{\preceq}(T)$. These are the sons of all
semigroup in $\mathcal{L}$, that we collect in $\mathcal{I}$.

  * •

Line 4: in the next step we have to repeat the same procedure considering the
semigroups in $\mathcal{I}$.

######  Example 26.

Let $\preceq$ be the lexicographic order in $\mathbb{N}^{2}$. Consider the
semigroup $R_{3,2}(\preceq)=\mathbb{N}^{2}\setminus\\{(0,1),(0,2),(0,3)\\}$,
we compute its sons in $\mathcal{T}_{3,\preceq}^{2}$.
Following the pseudocode we start with
$\mathcal{S}_{3,2}=\\{R_{3,2}(\preceq)\\},\mathcal{L}=\\{R_{3,2}(\preceq)\\}$.
In line 1 we have $\mathbf{m}_{\preceq}(R_{3,2}(\preceq))=(0,4)$ so
$\\{\textbf{h}\in\operatorname{SG}(R_{3,2}(\preceq))\mid\textbf{h}\preceq\mathbf{m}_{\preceq}(0,4))\\}=\\{(0,2),(0,3)\\}$.
So, following line 2 of the pseudocode, we consider:

  * •

$T_{(0,2)}=R_{3,2}(\preceq)\cup\\{(0,2)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,3)\\}$,
with $\operatorname{U}_{\preceq}(T_{(0,2)})=\\{(1,0),(1,1),(0,5)\\}$,

  * •

$T_{(0,3)}=R_{3,2}(\preceq)\cup\\{(0,3)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,2)\\}$,
with
$\operatorname{U}_{\preceq}(T_{(0,3)})=\\{(1,0),(1,1),(0,3),(1,2),(0,4),(0,5)\\}$

This means that we obtain $\mathcal{R}=\\{T_{(0,2)},T_{(0,3)}\\}$. So the sons
of $R_{3,2}(\preceq)$, obtained with the procedure in line 3, are the
following:

  * •

$S_{1}=T_{(0,2)}\setminus\\{(1,0)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,3),(1,0)\\}$,

  * •

$S_{2}=T_{(0,2)}\setminus\\{(1,1)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,3),(1,1)\\}$,

  * •

$S_{3}=T_{(0,2)}\setminus\\{(0,5)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,3),(0,5)\\}$,

  * •

$S_{4}=T_{(0,3)}\setminus\\{(1,0)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,2),(1,0)\\}$,

  * •

$S_{5}=T_{(0,3)}\setminus\\{(1,1)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,2),(1,1)\\}$,

  * •

$S_{6}=T_{(0,3)}\setminus\\{(1,2)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,2),(1,2)\\}$,

  * •

$S_{7}=T_{(0,3)}\setminus\\{(0,4)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,2),(0,4)\\}$,

  * •

$S_{8}=T_{(0,2)}\setminus\\{(0,5)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(0,2),(0,5)\\}$.

In particular
$\mathcal{I}=\\{S_{1}S_{2},S_{3},S_{4},S_{5},S_{6},S_{7},S_{8}\\}$ and
$\mathcal{S}_{3,2}=\\{R_{3,2}(\preceq)\\}\cup\mathcal{I}$.
At this point (that is line 4) $\mathcal{L}=\mathcal{I}$ and we start again
the procedure considering all semigroups in $\mathcal{L}$. If we continue, we
obtain all generalized numerical semigroup of genus $g$.
Observe that for $S_{1},S_{2},S_{3},S_{6},S_{7},S_{8}$ the set
$\\{\mathbf{h}\in\operatorname{SG}(S)\mid\mathbf{h}\preceq\mathbf{m}_{\preceq}(S)\\}$
is empty, so they are leaves in $\mathcal{T}_{3,\preceq}^{2}$ and in this
second step we have to consider the procedures in line 2 and line 3 only for
the semigroups $S_{4}$ and $S_{5}$.

The sons of $S_{4}$ are:

  * •

$S_{9}=S_{4}\cup\\{(0,2)\\}\setminus\\{(1,1)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(1,0),(1,1)\\}$,

  * •

$S_{10}=S_{4}\cup\\{(0,2)\\}\setminus\\{(2,1)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(1,0),(2,1)\\}$,

  * •

$S_{11}=S_{4}\cup\\{(0,2)\\}\setminus\\{(1,2)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(1,0),(1,2)\\}$,

  * •

$S_{12}=S_{4}\cup\\{(0,2)\\}\setminus\\{(2,0)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(1,0),(2,0)\\}$,

  * •

$S_{13}=S_{4}\cup\\{(0,2)\\}\setminus\\{(1,1)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(1,0),(3,0)\\}$.

The sons of $S_{5}$ are:

  * •

$S_{14}=S_{5}\cup\\{(0,2)\\}\setminus\\{(2,1)\\}=\mathbb{N}^{2}\setminus\\{(0,1),(1,1),(2,1)\\}$.

In particular, in line 3 of the second step we obtain
$\mathcal{I}=\\{S_{9},S_{10},S_{11},S_{12},S_{13},S_{14}\\}$. Now the third
step starts.

The semigroups $S_{10},S_{11},S_{14}$ are leaves in
$\mathcal{T}_{3,\preceq}^{2}$, so for the successive computations we have to
consider $S_{9},S_{12},S_{13}$.

The sons of $S_{9}$ are:

  * •

$S_{15}=S_{9}\cup\\{(0,1)\\}\setminus\\{(2,0)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(1,1),(2,0)\\}$,

  * •

$S_{16}=S_{9}\cup\\{(0,1)\\}\setminus\\{(3,0)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(1,1),(3,0)\\}$,

  * •

$S_{17}=S_{9}\cup\\{(0,1)\\}\setminus\\{(1,2)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(1,1),(1,2)\\}$.

The sons of $S_{12}$ are:

  * •

$S_{18}=S_{12}\cup\\{(0,1)\\}\setminus\\{(2,1)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(2,0),(2,1)\\}$,

  * •

$S_{19}=S_{12}\cup\\{(0,1)\\}\setminus\\{(3,0)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(2,0),(3,0)\\}$,

  * •

$S_{20}=S_{12}\cup\\{(0,1)\\}\setminus\\{(4,0)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(2,0),(4,0)\\}$,

  * •

$S_{21}=S_{12}\cup\\{(0,1)\\}\setminus\\{(5,0)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(2,0),(5,0)\\}$.

The only son of $S_{13}$ is:

  * •

$S_{22}=S_{13}\cup\\{(0,1)\\}\setminus\\{(5,0)\\}=\mathbb{N}^{2}\setminus\\{(1,0),(3,0),(5,0)\\}$.

At the end of third step we have
$\mathcal{L}=\\{S_{15},S_{16},S_{17},S_{18},S_{19},S_{20},S_{21},S_{22}\\}$.
For each one of these semigroups $\mathbf{m}_{\preceq}(S)=(0,1)$ and the set
$\\{\mathbf{h}\in\operatorname{SG}(S)\mid\mathbf{h}\preceq\mathbf{m}_{\preceq}(S)\\}$
is empty, so the procedure ends. So we have obtained exactly 23 different
generalized numerical semigroups. We can see a representation of the graph
$\mathcal{T}_{3,\preceq}^{2}$ in Figure 1.

$R_{3,2}(\preceq)$$S_{1}$$S_{2}$$S_{3}$$S_{4}$$S_{9}$$S_{15}$$S_{16}$$S_{17}$$S_{10}$$S_{11}$$S_{12}$$S_{18}$$S_{19}$$S_{20}$$S_{21}$$S_{13}$$S_{22}$$S_{5}$$S_{14}$$S_{6}$$S_{7}$$S_{8}$
Figure 1. The tree $\mathcal{T}_{3,\preceq}^{2}$, with $\preceq$ the
lexicographic order.

By Theorem 24 it is possible to produce all generalized numerical semigroups
of genus $g$ in $\mathbb{N}^{d}$ starting from $R_{g,d}(\preceq)$. This
procedure works as in the previous example, and it avoids considering all
generalized numerical semigroup of genus less then $g$, as happens in the
algorithm given in Section 3.

##  7\. Some remarks concerning implementations

The relaxed monomial order GAP used by default is the lexicographic order. Our
current implementations are not yet prepared to give the user the possibility
of choosing another order.

There was an important speedup in a preliminary implementation of Algorithm 3
after observing that the cartesian product of elements of the numerical
semigoups in the axes consists of elements of the generalized numerical
semigroup. Thus one may exclude this set from the set of possible gaps. Note
one can use the relatively efficient function that the numericalsgps package
provides for computing the set of small elements of a numerical semigroup.

We implemented Algorithm 4 in a recursive way. It explores the tree in a depth
first manner. Note that an exploration in a breadth first manner soon causes
memory problems since at least the semigroups of previous genus have to be
stored, even when one is just concerned with counting. By doing this in a
depth first manner there is only a small amount of information that needs to
be stored (unless we go very deep in the tree), the disadvantage being that
one has to decide in advance the genus one wants to attend. One somehow
overcomes this by making some previsions on the time that will be spent based
on the time taken for computations of lower genus. Furthermore, our
implementation includes the computation of the coefficients needed for the
polynomial referred in Theorem 11. In particular we considered the following
GAP code:

⬇

recursiveAffineSons:= function(s,N,L)

local H, gens, ml, smallgaps, smallPFs, SmSG, sons, t, E, i;

H:=Gaps(s);

gens:=Generators(s);

ml:=Minimum(gens); #multiplicity

smallgaps:=Filtered(H,j->j<ml);

smallPFs:=Filtered(smallgaps,g->not ForAny(gens,n -> n+g in H));

SmSG:=Filtered(smallPFs,g->not(2*g in H));

#special gaps smaller than the multiplicity

if not(IsEmpty(SmSG)) then

sons:=affineSons(s,SmSG);

for t in sons do

E:=recursiveAffineSons(t,N,L);

N:=E[1];

L:=E[2];

od;

fi;

N:=N+1;

i:=Rank(H);

L[i]:=L[i]+1;

return [N,L];

end;

We used the previous recursive procedure as a local function, initializing
$S:=R_{g,d}(\preceq)$ (while $\preceq$ is the lexicographic order), N to zero
and L to be the zero list with $d$ entries. In fact, the code works in such a
way that at the end of all recursion steps the variable N will contain the
number of all generalized numerical semigroups with given genus, and the $i$th
element of the list L will contain the number of generalized numerical
semigroups whose set of gaps generates a vector space of dimension $i$. These
variables are updated for the first time when the current semigroup has no
sons and successively each time going up in the recursion. The local function
affineSons computes the sons of the current semigroup. This function requires
as input also the set of special gaps smaller than the multiplicity of the
current semigroup, in order to avoid to compute many times the set SmSG.

Algorithm 4 can be used also to compute the number of numerical semigroups of
given genus. The present implementation in the package numericalsgps of the
function NumericalSemigroupsWithGenus designed for this uses the “standard
tree” and it is faster than the implementation we have for our algorithm. This
is maybe due to the choice of a more appropriate encoding, which in the case
of the package is presently based on Apéry sets. Even if it can be introduced
also for affine semigroups (see [11]), the Apéry set is in general an infinite
set for generalized numerical semigroups, while it is finite for numerical
semigroups. For this and other reasons, in what concerns the aim of Algorithm
4, at this moment we do not know if it is not possible to work with Apéry sets
(or something related to it) in generalized numerical semigroups in the same
way as for numerical semigroup.

In order to have sufficient examples to test our implementations at the time
this work was being prepared we implemented a method to generate a pseudo-
random generalized numerical semigroup of a genus given: from a semigroup of
genus $g-1$ one obtains one of genus $g$ by removing one minimal generator at
random (obtained using the GAP function RandomList).

##  8\. Some computational results

Let, as above, $N_{g,d}$ be the number of all generalized numerical semigroups
in $\mathbb{N}^{d}$ of genus $g$. If $d=1$, it has been proved that the
sequence $\\{N_{g,1}\\}$ has a Fibonacci-like behaviour (see [16]), that is,
$\lim_{g\rightarrow\infty}N_{g,1}/N_{g-1,1}=\phi$ where $\phi$ is the golden
ratio, as conjectured by M. Bras-Amóros in [3]. That conjecture was justified
by the computation of the values $N_{g,1}$ for $g=1$ up to $g=50$. A natural
question is whether the sequence $\\{N_{g,d}\\}$ with $d>1$ has a particular
behaviour. In order to shed some light on it we did several computations,
presented in the tables in this section.

Table 1. Computational results for $N_{g,2}$ $g$ | $N_{g,2}$ | $N_{g-1,2}+N_{g-2,2}$ | $\frac{N_{g-1,2}+N_{g-2,2}}{N_{g,2}}$ | $\frac{N_{g,2}}{N_{g-1,2}}$
---|---|---|---|---
0 | 1 |  |  |
1 | 2 |  |  | 2
2 | 7 | 3 | 0,4285714286 | 3,5
3 | 23 | 9 | 0,3913043478 | 3,2857142857
4 | 71 | 30 | 0,4225352113 | 3,0869565217
5 | 210 | 94 | 0,4476190476 | 2,9577464789
6 | 638 | 281 | 0,4404388715 | 3,0380952381
7 | 1894 | 848 | 0,4477296727 | 2,9686520376
8 | 5570 | 2532 | 0,4545780969 | 2,9408658923
9 | 16220 | 7464 | 0,4601726264 | 2,9120287253
10 | 46898 | 21790 | 0,4646253572 | 2,8913686806
11 | 134856 | 63118 | 0,4680399834 | 2,8755170796
12 | 386354 | 181754 | 0,4704338508 | 2,8649374147
13 | 1102980 | 521210 | 0,4725470997 | 2,8548429678
14 | 3137592 | 1489334 | 0,4746742088 | 2,8446499483
15 | 8892740 | 4240572 | 0,4768577514 | 2,8342563342
16 | 25114649 | 12030332 | 0,4790165294 | 2,8241744389
17 | 70686370 | 34007389 | 0,4811024954 | 2,8145473982
18 | 198319427 | 95801019 | 0,4830642184 | 2,8056247194
19 | 554813870 | 269005797 | 0,4848577362 | 2,797577012
20 | 1548231268 | 753133297 | 0,4864475434 | 2,7905417505
21 | 4310814033 | 2103045138 | 0,4878533664 | 2,7843476114

######  Remark 27.

The values presented in Table 1 for $g\in\\{19,20,21\\}$ are new. The others
coincide with those presented in [12, Table 3], except for $g=18$, which seems
to be wrong in that paper. Our suspicion is based on the fact that that the
number $n_{18}/n_{17}$ in the second column of the table in their paper, which
corresponds to the number $N_{18,2}/N_{17,2}$ in the forth column of Table 1,
is smaller than expected, from the regularity exhibited by the sequence of
values in that column.

We compute some values of $N_{g,d}^{(r)}$ in order to build the polynomial
$F_{g}(d)$ of Theorem 11. Some polynomials are given in [9], exactly:

  * •

$F_{1}(d)=d$

  * •

$F_{2}(d)=\frac{3}{2}d^{2}+\frac{1}{2}d$

  * •

$F_{3}(d)=\frac{5}{3}d^{3}+\frac{5}{2}d^{2}-\frac{1}{6}d$

Other values of $N_{g,d}^{(r)}$ have been computed, in particular:

$\begin{array}[]{llllll}N_{4,2}^{(2)}=57,&N_{5,2}^{(2)}=186,&N_{6,2}^{(2)}=592,&N_{7,2}^{(2)}=1816,&N_{8,2}^{(2)}=5436,&N_{9,2}^{(2)}=15984,\\\
N_{4,3}^{(3)}=100,&N_{5,3}^{(3)}=621,&N_{6,3}^{(3)}=3230,&N_{7,3}^{(3)}=15371,&N_{8,3}^{(3)}=69333,&N_{9,3}^{(3)}=301425,\\\
N_{4,4}^{(4)}=41,&N_{5,4}^{(4)}=672,&N_{6,4}^{(4)}=6321,&N_{7,4}^{(4)}=47432,&N_{8,4}^{(4)}=315393,&N_{9,4}^{(4)}=1945238,\\\
&N_{5,5}^{(5)}=196,&N_{6,5}^{(5)}=4745,&N_{7,5}^{(5)}=63205,&N_{8,5}^{(5)}=648115,&N_{9,5}^{(5)}=5742670,\\\
&&N_{6,6}^{(6)}=1057,&N_{7,6}^{(6)}=35480,&N_{8,6}^{(6)}=637312,&N_{9,6}^{(6)}=8584915,\\\
&&&N_{7,7}^{(7)}=6322,&N_{8,7}^{(7)}=281099,&N_{9,7}^{(7)}=6563802,\\\
&&&&N_{8,8}^{(8)}=41393,&N_{9,8}^{(8)}=2355792,\\\
&&&&&N_{9,9}^{(9)}=293608.\\\ \end{array}$

In [3] one can see the following known values:

$N_{4,1}^{(1)}=7,\ \ N_{5,1}^{(1)}=12,\ \ N_{6,1}^{(1)}=23,\ \
N_{7,1}^{(1)}=39,\ \ N_{8,1}^{(1)}=67,\ \ N_{9,1}^{(1)}=118.$

so the following polynomials can be expressed :

  * •

$F_{4}(d)=\frac{41}{24}d^{4}+\frac{77}{12}d^{3}-\frac{65}{24}d^{2}+\frac{19}{12}d$,

  * •

$F_{5}(d)=\frac{49}{30}d^{5}+\frac{35}{3}d^{4}-\frac{22}{3}d^{3}+\frac{53}{6}d^{2}-\frac{14}{5}d$,

  * •

$F_{6}(d)=\frac{1057}{720}d^{6}+\frac{841}{48}d^{5}-\frac{1045}{144}d^{4}+\frac{563}{48}d^{3}+\frac{148}{45}d^{2}-\frac{15}{4}d$,

  * •

$F_{7}(d)=\frac{3161}{2520}d^{7}+\frac{8257}{360}d^{6}+\frac{127}{18}d^{5}-\frac{1735}{72}d^{4}+\frac{31757}{360}d^{3}-\frac{15091}{180}d^{2}+\frac{577}{21}d$,

  * •

$F_{8}(d)=\frac{41393}{40320}d^{8}+\frac{38921}{1440}d^{7}+\frac{128099}{2880}d^{6}-\frac{9227}{62}d^{5}+\frac{1875151}{5760}d^{4}-\frac{467041}{1440}d^{3}+\frac{1234271}{10080}d^{2}-\frac{25}{24}d$,

  * •

$F_{9}(d)=\frac{5243}{6480}d^{9}+\frac{14767}{504}d^{8}+\frac{58399}{540}d^{7}-\frac{203159}{720}d^{6}+\frac{301811}{540}d^{5}-\frac{24961}{144}d^{4}-\frac{3909443}{6480}d^{3}+\frac{536093}{840}d^{2}-\frac{1427}{9}d$.

Table 2. Some values of $N_{g,d}$ for $d>2$. $g$ | $N_{g,3}$ | $N_{g,4}$ | $N_{g,5}$ | $N_{g,6}$ | $N_{g,7}$ | $N_{g,8}$ | $N_{g,9}$ | $N_{g,10}$
---|---|---|---|---|---|---|---|---
1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
2 | 15 | 26 | 40 | 57 | 77 | 100 | 126 | 155
3 | 67 | 146 | 270 | 449 | 693 | 1012 | 1416 | 1915
4 | 292 | 811 | 1810 | 3512 | 6181 | 10122 | 15681 | 23245
5 | 1215 | 4320 | 11686 | 26538 | 53361 | 98096 | 168336 | 273522
6 | 5075 | 22885 | 74685 | 197960 | 453922 | 935426 | 1775943 | 3159590
7 | 20936 | 119968 | 472430 | 1461084 | 3818501 | 8815672 | 18505065 | 36024450
8 | 85842 | 625609 | 2973105 | 10725499 | 31932733 | 82542263 | 191448588 | 407552845
9 | 349731 | 3247314 | 18643540 | 78488473 | 266223972 | 770328304 | 1973498062 | 4591979390
10 | 1418323 | 16800886 |  |  |  |  |  |
11 | 5731710 | 86739337 |  |  |  |  |  |
12 | 23100916 | 447283982 |  |  |  |  |  |
13 | 92882954 | 2304942650 |  |  |  |  |  |
14 | 372648740 |  |  |  |  |  |  |

######  Remark 28.

The values of Table 2 up to dimension 9 have been effectively computed. Of
course, they coincide with the values given by the polynomials $F_{g}(d)$
mentioned above, in the cases this value exists. As a consequence of our
computations we observe that we are able to compute the number of generalized
numerical semigroups with genus up to 9 for any dimension (using the
polynomial given by Theorem 11). The last column of the table contains the
values for dimension 10.

All the values presented are new, except for those of dimension 3, up to genus
13. These already appear in [12, Table 3], and our computations confirm them.

We end the paper by doing some comparisons between $(N_{g,1})^{2}$ and
$N_{g,2}$, for $g$ not greater than $21$. Recall that, up to $g=21$ the values
$N_{g,2}$ appear for the first time in this work, while the values of
$N_{g,1}$ for the same values of $g$ are well known. The comparisons are
registered in Table 3.

Table 3. Values to estimate $(N_{g,1})^{2}/N_{g,2}$. $g$ | $N_{g,1}$ | $(N_{g,1})^{2}$ | $N_{g,2}$ | $\frac{(N_{g,1})^{2}}{N_{g,2}}$
---|---|---|---|---
1 | 1 | 1 | 2 | 0,5
2 | 2 | 4 | 7 | 0,5714285714
3 | 4 | 16 | 23 | 0,6956521739
4 | 7 | 49 | 71 | 0,6901408451
5 | 12 | 144 | 210 | 0,6857142857
6 | 23 | 529 | 638 | 0,829153605
7 | 39 | 1521 | 1894 | 0,803062302
8 | 67 | 4489 | 5570 | 0,8059245961
9 | 118 | 13924 | 16220 | 0,8584463625
10 | 204 | 41616 | 46898 | 0,8873725958
11 | 343 | 117649 | 134856 | 0,872404639
12 | 592 | 350464 | 386354 | 0,9071059184
13 | 1001 | 1002001 | 1102980 | 0,9084489293
14 | 1693 | 2866249 | 3137592 | 0,9135187112
15 | 2857 | 8162449 | 8892740 | 0,9178778419
16 | 4806 | 23097636 | 25114649 | 0,9196877886
17 | 8045 | 64722025 | 70686370 | 0,9156224177
18 | 13467 | 181360089 | 198319427 | 0,9144847368
19 | 22464 | 504631296 | 554813870 | 0,9095506138
20 | 37396 | 1398460816 | 1548231268 | 0,9032635142
21 | 62194 | 3868093636 | 4310814033 | 0,8973000474

Note that for all the $g$’s in the table we have that $(N_{g,1})^{2}<N_{g,2}$.
Also, note that the ratio $(N_{g,1})^{2}/N_{g,2}$ is increasing from $g=1$ to
$g=16$ and starts then to be decreasing until reaching $g=21$. What happens
next is not known, since $N_{g,2}$ has not been computed for $g\geq 22$.

It is easy to check using the data presented in Table 2 that having decreasing
ratios is no longer true when $d$ is bigger than $2$. In fact for $d\geq 3$,
one quickly has $(N_{g,1})^{d}>N_{g,d}$, by letting $g$ grow. Moreover the
ratio $(N_{g,1})^{d}/N_{g,d}$ seems to grow quickly, as $g$ grows.

Let us return to the case $d=2$. Some questions arise:

  1. (1)

Is it true $(N_{g,1})^{2}<N_{g,2}$ for every $g\in\mathbb{N}$?

  2. (2)

Does $\lim\limits_{g\rightarrow\infty}\frac{(N_{g,1})^{2}}{N_{g,2}}$ exist,
and is nonzero?

If the second question has a positive answer, one has that
$\lim\limits_{g\rightarrow\infty}\frac{N_{g,2}}{N_{g-1,2}}=\phi^{2}$, where
$\phi$ is the golden ratio, as can easily be shown.

If the first question has a positive answer and the ratio
$\frac{(N_{g,1})^{2}}{N_{g,2}}$ is decreases from a certain value on (as our
experiments suggest), then it is true also that
$\lim\limits_{g\rightarrow\infty}\frac{(N_{g,1})^{2}}{N_{g,2}}=k$ with
$0<k<1$.

The numerical data collected is for the moment not sufficient to give us too
much confidence on our observations or to state any nice conjecture
(especially for the case $d\geq 3$), as happened with Bras-Amorós when she
realized that the sequence of the number of numerical semigroups counted by
genus had a Fibonacci-like behaviour. Since the algorithms and the
implementations have still space to be improved, obtaining more numerical data
may be seen as an active goal.

### Acknowledgements

The first and second authors want to thank the amazing hospitality found in
the Instituto de Matemáticas de la Universidad de Granada (IEMath-GR). Most of
the results in this paper where obtained during their stay there.

The authors also thank the Centro de Servicios de Informática y Redes de
Comunicaciones (CSIRC), Universidad de Granada, for providing the computing
time, specially Rafael Arco Arredondo for installing this package and the
extra software needed in alhambra.ugr.es, and Santiago Melchor Ferrer for
helping in job submission to the cluster.

## References

  * [1] A. Assi, P.A. García-Sánchez, and I. Ojeda.  Frobenius vectors, hilbert series and gluings of affine semigroups.  Journal of Commutative Algebra, 7(3):317–335, 2015.
  * [2] Abdallah Assi and Pedro A. García-Sánchez.  Numerical semigroups and applications, volume 1 of RSME Springer Series.  Springer, 2016.
  * [3] Maria Bras-Amorós.  Fibonacci-like behavior of the number of numerical semigroups of a given genus.  Semigroup Forum, 76(2):379–384, 2008.
  * [4] Maria Bras-Amorós.  Bounds on the number of numerical semigroups of a given genus.  Journal of Pure and Applied Algebra, 213(6):997–1001, 2009.
  * [5] Maria Bras-Amorós.  The ordinarization transform of a numerical semigroup and semigroups with a large number of intervals.  Journal of Pure and Applied Algebra, 216(11):2507–2518, 2012.
  * [6] Carmelo Cisto, Gioia Failla, and Rosanna Utano.  On the generators of a generalized numerical semigroup.  Analele Univ. “Ovidius”, 27(1):49–59, 2019.
  * [7] David Cox, John Little, and Donal O’shea.  Ideals, varieties, and algorithms, volume 3.  Springer, 2007.
  * [8] M. Delgado, P. A. Garcia-Sanchez, and J. Morais.  NumericalSgps, a package for numerical semigroups, Version 1.1.11.  https://gap-packages.github.io/numericalsgps, Mar 2019.  Refereed GAP package.
  * [9] Gioia Failla, Chris Peterson, and Rosanna Utano.  Algorithms and basic asymptotics for generalized numerical semigroups in $\mathbb{N}^{d}$.  Semigroup Forum, 92(2):460–473, 2016.
  * [10] GAP – Groups, Algorithms, and Programming, Version 4.10.0.  https://www.gap-system.org, Nov 2018.
  * [11] J. I. García-García, I. Ojeda, J. C. Rosales, and A. Vigneron-Tenorio.  On pseudo-frobenius elements of submonoids of $\mathbb{N}^{d}$.  Collect. Math., 2019.  https://doi.org/10.1007/s13348-019-00267-0.
  * [12] J.I. García-García, D. Marín-Aragón, and A. Vigneron-Tenorio.  An extension of wilf’s conjecture to affine semigroups.  Semigroup Forum, 96(2):396–408, 2018.
  * [13] J.I. García-García, M.A. Moreno-Frías, A. Sánchez R. Navarro, and A. Vigneron-Tenorio.  Affine convex body semigroups.  Semigroup Forum, 87(2):331–350, 2013.
  * [14] José Carlos Rosales and Pedro A. García-Sánchez.  Numerical semigroups, volume 20.  Springer Science & Business Media, 2009.
  * [15] José Carlos Rosales, Pedro A. García-Sánchez, Juan Ignacio García-García, and J.A. Jiménez Madrid.  The oversemigroups of a numerical semigroup.  Semigroup Forum, 67(1):145–158, 2003.
  * [16] Alex Zhai.  Fibonacci-like growth of numerical semigroups of a given genus.  Semigroup Forum, 86(3):634–662, 2013.


[a]Tania Robens

# LHC Benchmark scenarios in the TRSM

###### Abstract

The TRSM is a new physics model that extends the scalar sector of the Standard
Model by two additional CP even scalars. It leads to a large variety of
interesting signatures, some of which have not yet been explored by the LHC
experiments. I will also discuss the option to explore the hhh final state
within this model.
RBI-ThPhys-2022-45

##  1 The model

The Two-Real-Singlet Model (TRSM) is a new physics model that enhances the
Standard Model (SM) electroweak sector by two additional fields that are
singlets under the SM gauge group and obey an additional
$\mathbb{Z}_{2}\,\otimes\,\mathbb{Z}_{2}^{\prime}$ symmetry. The model,
including theoretical and experimental constraints, has been discussed in
great detail in [1, 2]. We assume that all scalar fields acquire a vacuum
expectation value (vev) which softly break the above symmetry. As a
consequence, all couplings to SM particles are inherited from the SM-like
doublet via mixing. One of the three scalars has to have properties that
comply with the measurements of the Higgs boson by the LHC experiments [3, 4].
At a hadron collider, typical production and decay processes are given by
either asymmetric (AS) production and decay, in the form of
$p\,p\,\rightarrow\,h_{3}\,\rightarrow\,h_{1}\,h_{2}$, where, depending on the
kinematics, $h_{2}\,\rightarrow\,h_{1}\,h_{1}$ decays are also possible, or
symmetric (S) decays in the form of
$p\,p\,\rightarrow\,h_{i}\,\rightarrow\,h_{j}\,h_{j}$, where in our study none
of the scalars corresponds to the 125 GeV resonance. Note that this in
principle allows for further decays $h_{j}\,\rightarrow\,h_{k}\,h_{k}$, again
depending on the specific benchmark plane (BP) kinematics. We here use the
convention that $M_{1}\,\leq\,M_{2}\,\leq\,M_{3}$ for the masses of the
scalars $h_{1,2,3}$ in the mass eigenstates.

##  2 LHC benchmark scenarios

In [1], several benchmark planes for both asymmetric and symmetric decay
chains were proposed, which are distinct also by the role of the scalar that
complies with the measurements of the 125 GeV resonance. The benchmark planes,
with maximal production cross sections at a 13 TeV LHC, are given below.

  * •

AS BP1: $h_{3}\to h_{1}h_{2}$ ($h_{3}=h_{125}$) : SM-like decays for both
scalars: $\sim\,3\,{\rm pb}$; $h_{1}^{3}$ final states: $\sim 3\,{\rm pb}$

  * •

AS BP2: $h_{3}\to h_{1}h_{2}$ ($h_{2}=h_{125}$): SM-like decays for both
scalars: $\sim\,0.6\,{\rm pb}$; $h_{1}^{3}$ final states: $\sim\,30\,{\rm fb}$

  * •

AS BP3: $h_{3}\to h_{1}h_{2}$ ($h_{1}=h_{125}$): (a) SM-like decays for both
scalars $\sim\,0.3\,{\rm pb}$; (b) $h_{1}^{3}$ final states: $\sim\,0.14\,{\rm
pb}$

  * •

S BP4: $h_{2}\to h_{1}h_{1}$ ($h_{3}=h_{125}$): up to 60 pb

  * •

S BP5: $h_{3}\to h_{1}h_{1}$ ($h_{2}=h_{125}$): up to $2.5\,{\rm pb}$

  * •

S BP6: $h_{3}\to h_{2}h_{2}$ ($h_{1}=h_{125}$): SM-like decays: up to 0.5 pb;
$h_{1}^{4}$ final states: around 14 fb

We also show several of these benchmark planes in figure 1.

Figure 1:  Benchmark planes in the TRSM. Top: Asymmetric final states, for
$h_{3}\,\rightarrow\,h_{1}\,h_{2}$, BPs 1 (left) and 3 (right). Bottom:
Symmetric final states, for $h_{i}\,\rightarrow\,h_{j}h_{j}$, where none of
the $h$s has a mass of 125 GeV, BPs 5 (left) and 4 (right). Mostly taken from
[1], with an update for BP5 first presented in [5, 2].

##  3 hhh final states

In BP3, an intriguing scenario is the one where also $h_{2}$ decays to
$h_{1}h_{1}$, which then leads to a $h_{125}h_{125}h_{125}$ final state. For
the subsequent decay into $b\bar{b}$ pairs, this channel has been investigated
in detail in [6]. The results are shown in table 1, where one sees that
significances close to $5\,\sigma$ can already be achieved with relatively low
integrated luminosity.

$(M_{2},M_{3})$ | $\sigma(pp\rightarrow h_{1}h_{1}h_{1})$ | $\sigma(pp\rightarrow 3b\bar{b})$ | $\text{sig}|_{300\rm{fb}^{-1}}$ | $\text{sig}|_{3000\rm{fb}^{-1}}$
---|---|---|---|---
${[{\rm GeV}]}$ | ${[{\rm fb}]}$ | ${[{\rm fb}]}$ |  |
$(255,504)$ | $32.40$ | $6.40$ | $2.92$ |  $9.23$
$(263,455)$ | $50.36$ | $9.95$ |  $4.78$ |  $15.11$
$(287,502)$ | $39.61$ | $7.82$ |  $4.01$ |  $12.68$
$(290,454)$ | $49.00$ | $9.68$ |  $5.02$ |  $15.86$
$(320,503)$ | $35.88$ | $7.09$ |  $3.76$ |  $11.88$
$(264,504)$ | $37.67$ | $7.44$ |  $3.56$ |  $11.27$
$(280,455)$ | $51.00$ | $10.07$ |  $5.18$ |  $16.39$
$(300,475)$ | $43.92$ | $8.68$ |  $4.64$ |  $14.68$
$(310,500)$ | $37.90$ | $7.49$ |  $4.09$ |  $12.94$
$(280,500)$ | $40.26$ | $7.95$ |  $4.00$ |  $12.65$
Table 1:  Significances for the $h_{125}h_{125}h_{125}$ final states in the
TRSM, at a 14 TeV LHC, from the analysis presented in [6], for various points
in BP3.

##  4 Recasts

It is also interesting to investigate whether current searches can be
reinterpreted and recasted in such a way that they allow to exclude regions in
the models parameter space that were not directly scrutinized in the
experimental search. In [7], the authors have reinterpreted a CMS search for
$p\,p\,\rightarrow\,H\,\rightarrow\,h_{125}h_{125}\,\rightarrow\,4\,b$ [8]. I
have applied these results to the TRSM, in particular to BP5. I display the
corresponding results in figure 2. We see that the sensitive region of
parameter space is significantly extended.

Figure 2:  Recasting $h_{125}h_{125}$ search results from a $36\,{\rm
fb}^{1-}$ CMS search [8], with recast results from [7]. Taken from [9, 5, 2].

##  5 Conclusion and outlook

I discussed benchmark planes in the TRSM, a new physics model that enhances
the SM scalar content by two additional neutral CP-even scalars that allows
for interesting novel decay chains. I reported on benchmark planes, including
a detailed study as well as current recast results. Althogh the experiments at
the LHC already explore parts of the model’s parameter space, there is still
room for further investigation.

## References

  * [1] T. Robens, T. Stefaniak, and J. Wittbrodt,  Eur. Phys. J. C 80, 151 (2020), 1908.08554.
  * [2] T. Robens,  Two-Real-Singlet-Model Benchmark Planes,  2022, 2209.10996.
  * [3] ATLAS,  Nature 607, 52 (2022), 2207.00092.
  * [4] CMS,  Nature 607, 60 (2022), 2207.00043.
  * [5] T. Robens,  TRSM Benchmark Planes - Snowmass White Paper,  in 2022 Snowmass Summer Study, 2022, 2205.14486.
  * [6] A. Papaefstathiou, T. Robens, and G. Tetlalmatzi-Xolocotzi,  JHEP 05, 193 (2021), 2101.00037.
  * [7] D. Barducci, K. Mimasu, J. M. No, C. Vernieri, and J. Zurita,  JHEP 02, 002 (2020), 1910.08574.
  * [8] CMS, A. M. Sirunyan et al.,  JHEP 08, 152 (2018), 1806.03548.
  * [9] T. Robens,  PoS DISCRETE2020-2021, 063 (2022), 2202.09636.