Numerical semigroups with a given set of pseudo-Frobenius numbers (Q2804216)

A numerical semigroup \(S\) is a submonoid of \((\mathbb{N},0)\) where \(\mathbb{N} = \{0,1,2,\ldots\}\), and \(\mathbb{N} \setminus S\) is finite. This finite set is called the set of gaps of \(S\). The largest of these gaps is called the Frobenius number of \(S\) and is denoted \(F(S)\). An integer \(x\) is called a pseduo-Frobenius number of \(S\) if \(x+s\in S\) for all \(s \in S\setminus \{0\}\). We denote the set of pseudo-Frobenius numbers of \(S\) by \(PF(S)\).NEWLINENEWLINEBlanco and Rosales have described an algorithm to organize the set of all numerical semigroups \(S\) with fixed Frobenius number \(F\) as a tree [\textit{V. Blanco} and \textit{J. C. Rosales}, Forum Math. 25, No. 6, 1249--1261 (2013; Zbl 1347.11027)]. The authors of this paper consider a similar question. Given a finite set of positive integers \(T\), how can we construct the set of all numerical semigroups \(S\) with \(PF(S) = T\)? Any such semigroup must have its Frobenius number equal to the maximum element of \(T\), so we may begin by first computing all numerical semigroups with \(F(S) = \max(T)\), and then compute the pseudo-Frobenius numbers of each. This approach can be very slow in practice. Previous work answers this main question in the case where \(|PF(S)| \leq 2\) [\textit{A. M. Robles-Pérez} and \textit{J. C. Rosales}, Proc. R. Soc. Edinb., Sect. A, Math. 146, No. 5, 1081--1090 (2016; Zbl 1403.11025)].NEWLINENEWLINEThe authors give two procedures for determining the set of all semigroups with a given set of pseudo-Frobenius numbers. The first takes up the majority of the paper and is based on computing sets of `forced gaps' and `forced elements'. To give a basic example, a numerical semigroup \(S\) with \(PF(S) = \{19,29\}\) must have \(29-19 = 10 \not\in S\), and also \(19-(29-19) = 9 \in S\). The authors give algorithms to compute sets of forced gaps and forced elements and then describe how to understand the possibilities for the remaining elements, the `free integers'. The second procedure depends on the idea of representing a numerical semigroup as an intersection of numerical semigroups containing it, which is related to the concept of an irreducible numerical semigroup.NEWLINENEWLINEThe authors give several concrete examples and illustrate their algorithms with pseudocode. The algorithms from this paper are open source and have been implemented as part of the NumericalSgps package for the computer algebra system GAP.