On numerical semigroups.

*(English)*Zbl 0614.10046Let \(\{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 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 A. Brauer and 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)\).

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 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 A. Brauer and 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)\).

Reviewer: E.S.Selmer

##### MSC:

11B13 | Additive bases, including sumsets |

##### References:

[1] | Brauer, A.,On a problem of partitions, Amer. J. Math. 64(1942), 299–312. · Zbl 0061.06801 |

[2] | Brauer, A.,Review on J.B. Roberts:Note on linear forms, Math. Rev. 19(1958), 1038. |

[3] | Brauer, A. and J.E. Shockley,On a problem of Frobenius, J. Reine Angew. Math. 211(1962), 215–220. · Zbl 0108.04604 |

[4] | Batesman, P.T.,Remark on a recent note on linear forms, Amer. Math. Monthly 65(1958), 517–518. · Zbl 0083.03801 |

[5] | Hofmeister, S.R.,Zu einem Problem von Frobenius, Norske Videnskabers Selskabs Skrifter 5(1966), 1–37. · Zbl 0156.05001 |

[6] | Johnson, S.M.,A linear diophantine problem, Can. J. Math. 12(1960), 390–398. · Zbl 0096.02803 |

[7] | Kirfel, C.Erweiterung dreielementiger Basen bei konstanter Frobeniuszahl, Math. Scand. 54(1984), 310–316. · Zbl 0549.10042 |

[8] | Mendelsohn, N.S.,A linear diophantine question with applications to non-negative matrices, Ann. N.Y. Acad. Sci. 175(1970), 287–294. · Zbl 0225.10010 |

[9] | Nijenhuis, A. and H.S. Wilf,Representations of integers by linear forms in non-negative integers, J. Number Theory 4(1972), 98–106. · Zbl 0226.10057 |

[10] | Roberts, J.B.,Note on linear forms, Proc. A.M.S. 7(1956), 465–469. · Zbl 0071.03902 |

[11] | Rödseth, Ö.J.,On a linear diophantine problem of Frobenius, J. Reine Angew. Math. 301(1978), 171–178. · Zbl 0374.10011 |

[12] | Rödseth, Ö.J.On a linear diophantine problem of Frobenius II, J. Reine Angew. Math. 307/308(1979), 431–440. · Zbl 0395.10021 |

[13] | Selmer, E.S.,On a linear diophantine problem of Frobenius, J. Reine Angew. Math. 293/294(1977), 1–17. · Zbl 0349.10009 |

[14] | Selmer, E.S.,The local postage stamp problem,Part 1:General theory, Preprint, University of Bargen 42 (1986). |

[15] | Selmer, E.S. and Ö. Beyer,On a linear diophantine problem of Frobenius in three variables, J. Reine Angew. Math. 301(1978), 161–170. · Zbl 0374.10010 |

[16] | Siering, E.,Über lineare Formen und ein Problem von Frobenius, Dissertation, Joh. Gutenberg-Universität, Mainz, 1974. · Zbl 0312.10008 |

[17] | Sylvester, J.J.,Mathematical questions with their solutions, Educational Times 41(1884), 21. · JFM 16.0159.04 |

[18] | Wilf, H.S.,Circle-of-lights algorithm for money-changing problem, Am. Math. Mo. 85: 7(1978), 562–565. · Zbl 0387.10009 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.