On numerical semigroups (Q5916421)

Let \(\{s_ i\}\), \(i=1,2,...,t\), be a basis of coprime natural numbers. The numerical semigroup \(S=<s_ 1,...,s_ t>\) is the set of all linear combinations \(n_ 1s_ 1+...+n_ ts_ t\), \(n_ i\in {\mathbb{N}}\cup \{0\}\). The largest integer not in S is the Frobenius number \(g(\{s_ i\})=g(S)=g\). We define \(g-S=\{g-s\); \(s\in S\}\), where clearly S and g-S are disjoint. The semigroup S is called symmetric if \(S\cup (g- s)={\mathbb{Z}}\). This means that exactly half of the numbers 0,1,...,g belong to S, so g is odd. An important new concept is the set \(S'=\{x\in {\mathbb{Z}}\); \(x\not\in S\), \(x+s\in S\) for all \(s\in S\), \(s>0\}\). The number of elements in S' is called the type of S. Clearly \(g\in S'\), and this is the only element of S' (type \(=1)\) iff S is symmetric, hence g odd. If g is even, \(S\cup (g- S)={\mathbb{Z}}\setminus \{g/2\}\) iff \(S'=\{g/2,g\}\) (type \(=2)\) iff exactly half of the numbers 0,1,...,g-1 belong to S. The reviewer has earlier proposed the problem to determine all extensions of the basis \(\{s_ i\}\) with an element \(\not\in S\) which leaves the Frobenius number unchanged. It is shown that this is impossible just in the two cases: 1) g odd, S symmetric; 2) g even, \(S'=\{g/2,g\}\). Incidentally, this result was already proved in \textit{H. Metternich} [Über ein Problem von Frobenius, Diplomarbeit, Joh. Gutenberg- Universität, Mainz 1981]. It is shown that the number of different symmetric semigroups for given g grows exponentially with g. A useful concept in Frobenius theory is the minimal system S(s), \(s\in S\), \(s>0\), of the smallest numbers of S in all residue classes modulo s. It is shown (Proposition 7) that the ''structure'' of S(s) is in a sense independent of s. It is well known that removal of a common divisor of all but one of the basis elements \(s_ i\) does not seriously influence the Frobenius problem. If this is done in all possible ways, the ''derived semigroup'' results; it has the same type as S. For \(t=2\), the type is trivially 1. If \(t=3\), and the derived semigroup is minimally generated by the resulting three pairwise relatively prime elements, it is shown that the type is 2. An example (due to J. Backelin) shows that there is no upper bound on the type for any \(t\geq 4\). This important observation partly explains a common experience of all workers in the field: The difficulty of the Frobenius problem increases drastically when moving from \(t\leq 3\) to \(t\geq 4.\) The authors define a ''super-symmetric'' semigroup, and show that their original definition is equivalent to the following construction: Let \(p_ 1,p_ 2,...,p_ t\) be pairwise relatively prime positive integers, and put \(s_ i=(\prod^{t}_{1}p_ j)/p_ i\). For this basis, they then prove that \(g=(t-1)\prod^{t}_{1}p_ i- \sum^{t}_{1}s_ i\). This formula, however, is a trivial consequence of an old result in \textit{A. Brauer} and \textit{B. M. Seelbinder} [Am. J. Math. 76, 343-346 (1954; Zbl 0056.269)]. It is finally shown that if the type of S is T, the number of elements in S which are less than g is at least \((g+1)/(T+1)\).