The set of numerical semigroups of a given genus. (Q1935456)

A numerical semigroup \(S\) is a submonoid of the set of nonnegative integers, \(\mathbb N\), with finite complement in \(\mathbb N\). The elements in \(\mathbb N\setminus S\) are the gaps of \(S\), and its cardinality, denoted by \(g(S)\), is the genus of \(S\). The Frobenius number of \(S\), \(F(S)\), is largest integer not belonging to \(S\). The least positive integer in \(S\) is the multiplicity of \(S\), denoted by \(m(S)\). A numerical semigroup \(S\) is elementary if \(F(S)<2m(S)\). Denote by \(\mathcal S(F,g)\) the set of numerical semigroups with Frobenius number \(F\) and genus \(g\). The authors present a procedure to compute this set as follows. Let \(\mathcal E(F,g)\) be the set of elementary numerical semigroups with Frobenius number \(F\) and genus \(g\). The authors show that the map \(\theta\colon\mathcal S(F,g)\to\mathcal E(F,g)\), \[ \theta(S)=(S\setminus \{x\in S\setminus\{0\}\mid x<F/2\})\cup\{F-x\mid x\in S\setminus\{0\}\mid x<F/2\} \] is surjective. Let \(R\) be the kernel congruence of \(\theta\), that is, \(SRT\) if \(\theta(S)=\theta(T)\). For \(S\) in \(\mathcal S(F,g)\) denote by \([S]\) the \(R\)-class of \(S\). Then it is proved: every \(R\)-class contains a unique element of \(\mathcal E(F,g)\), and if \(E\in\mathcal E(F,g)\), the set \([E]\) can be arranged in a tree rooted in \(E\). The authors give a method to compute the set \(\mathcal E(F,g)\), and for every \(E\in\mathcal E(F,g)\) the elements in \([E]\). In this way an algorithm to compute \(\mathcal S(F,g)=\bigcup_{E\in\mathcal E(F,g)}[E]\) is presented. These procedures are then translated in terms of Kunz coordinates with respect to \(2g\). Kunz coordinates were introduced by \textit{E. Kunz} [Über die Klassifikation numerischer Halbgruppen. Regensburger Math. Schr. 11 (1987; Zbl 0618.14008)] and were studied independently by \textit{J. C. Rosales}, \textit{P. A. García-Sánchez, J. I. García-García}, and \textit{M. B. Branco} [J. Lond. Math. Soc., II. Ser. 65, No. 3, 611-623 (2002; Zbl 1022.20032)]. For a given genus \(g\) the set of all possible Frobenius numbers of numerical semigroups having genus \(g\) is \([g,2g-1]\); and for fixed Frobenius number \(F\), the set of all possible genera of numerical semigroups with Frobenius number \(F\) is \(\left[\lceil(F+1)/2\rceil,F\right]\). Hence, as an application, the authors present alternative ways (to the ones already existing in the literature) for computing the set of all numerical semigroups with given genus \(g\), \(\bigcup_{F=g}^{2g-1}\mathcal S(F,g)\), and the set of all numerical semigroups with given Frobenius number \(F\), \(\bigcup_{g=\lceil(F+1)/2\rceil}^F\mathcal S(F,g)\). One of the advantages of the method presented for the computation of the set of numerical semigroups with fixed genus \(g\) is that it does not rely on the computation of the set of all numerical semigroups with genus \(g-1\) as it has been performed before in the literature (see for instance [\textit{M. Bras-Amorós}, Semigroup Forum 76, No. 2, 379-384 (2008; Zbl 1142.20039)]). Unfortunately, the authors do not provide timings for a possible implementation of this approach. The reviewer has implemented the algorithm in \texttt{gap} and has compared the execution times with the functions already implemented in the package \texttt{numericalsgps}. The executions times are by far larger than those of \texttt{NumericalSemigroupsWithGenus} (that uses the traditional method) and \texttt{NumericalSemigroupsWithFrobeniusNumber} (the implementation used in \texttt{numericalsgps} for this purpose is the one presented by \textit{J. C. Rosales, P. A. García-Sánchez, J. I. García-García} and \textit{J. A. Jiménez Madrid} [J. Pure Appl. Algebra 189, No. 1-3, 301-313 (2004; Zbl 1070.20072)]).