{{Short description|Special kind of semigroup in mathematics}} In mathematics, a '''numerical semigroup''' is a special kind of a semigroup. Its underlying set is the set of all nonnegative integers except a finite number of integers, and the binary operation is the operation of addition of integers. Also, the integer 0 must be an element of the semigroup. For example, while the set {0, 2, 3, 4, 5, 6, ...} is a numerical semigroup, the set {0, 1, 3, 5, 6, ...} is not because 1 is in the set and 1 + 1 = 2 is not in the set. Numerical semigroups are commutative monoids and are also known as '''numerical monoids'''.<ref>{{cite web|last=Garcia-Sanchez|first=P.A.|title=Numerical semigroups minicourse|url=http://cmup.fc.up.pt/cmup/v2/include/filedb.php?id=117&table=publicacoes&field=file|accessdate=6 April 2011}}</ref><ref>{{cite web|last=Finch|first=Steven|title=Monoids of Natural Numbers|url=http://algo.inria.fr/csolve/mnd.pdf|publisher=INRIA Algorithms Project|accessdate=7 April 2011}}</ref>
The definition of numerical semigroup is intimately related to the problem of determining nonnegative integers that can be expressed in the form ''x''<sub>1</sub>''n''<sub>1</sub> + ''x''<sub>2</sub> ''n''<sub>2</sub> + ... + ''x''<sub>''r''</sub> ''n''<sub>''r''</sub> for a given set {''n''<sub>1</sub>, ''n''<sub>2</sub>, ..., ''n''<sub>''r''</sub>} of positive integers and for arbitrary nonnegative integers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''r''</sub>. This problem had been considered by several mathematicians like Frobenius (1849–1917) and Sylvester (1814–1897) at the end of the 19th century.<ref name=Rosales>{{cite book|last=J.C. Rosales and P.A. Garcia-Sanchez|title=Numerical Semigroups|year=2009|publisher=Springer|isbn=978-1-4419-0159-0}}</ref> During the second half of the twentieth century, interest in the study of numerical semigroups resurfaced because of their applications in algebraic geometry.<ref>{{cite journal|last=V. Barucci |display-authors=et al|title=Maximality properties in numerical semigroups and applications to one-dimensional analytically irreducible local domains|journal=Memoirs of the Amer. Math. Soc.|year=1997|volume=598}}</ref>
== Definition and examples == === Definition ===
Let ''N'' be the set of nonnegative integers. A subset ''S'' of ''N'' is called a numerical semigroup if the following conditions are satisfied.
#0 is an element of ''S'' #''N'' − ''S'', the complement of ''S'' in ''N'', is finite. #If ''x'' and ''y'' are in ''S'' then ''x + y'' is also in ''S''.
There is a simple method to construct numerical semigroups. Let ''A'' = {''n''<sub>1</sub>, ''n''<sub>2</sub>, ..., ''n''<sub>''r''</sub>} be a nonempty set of positive integers. The set of all integers of the form ''x''<sub>1</sub> ''n''<sub>1</sub> + ''x''<sub>2</sub> ''n''<sub>2</sub> + ... + ''x''<sub>''r''</sub> ''n''<sub>''r''</sub> is the subset of ''N'' generated by ''A'' and is denoted by ⟨ ''A'' ⟩. The following theorem fully characterizes numerical semigroups.
=== Theorem ===
Let ''S'' be the subsemigroup of ''N'' generated by ''A''. Then ''S'' is a numerical semigroup if and only if gcd (''A'') = 1. Moreover, every numerical semigroup arises in this way.<ref>{{cite book|last1=García-Sánchez|first1=J.C. Rosales, P.A.|title=Numerical semigroups|date=2009|publisher=Springer|location=New York|isbn=978-1-4419-0160-6|pages=7|edition=First.}}</ref>
=== Examples ===
The following subsets of ''N'' are numerical semigroups. #⟨ 1 ⟩ = {0, 1, 2, 3, ...} #⟨ 1, 2 ⟩ = {0, 1, 2, 3, ...} #⟨ 2, 3 ⟩ = {0, 2, 3, 4, 5, 6, ...} #Let ''a'' be a positive integer. ⟨ ''a'', ''a'' + 1, ''a'' + 2, ... , 2''a'' – 1 ⟩ = {0, ''a'', ''a'' + 1, ''a'' + 2, ''a'' + 3, ...}. #Let ''b'' be an odd integer greater than 1. Then ⟨ 2, ''b'' ⟩ = {0, 2, 4, . . . , ''b'' − 3 , ''b'' − 1, ''b'', ''b'' + 1, ''b'' + 2, ''b'' + 3 , ...}. #Well-tempered harmonic semigroup ''H''={0,12,19,24,28,31,34,36,38,40,42,43,45,46,47,48,...} <ref>{{cite journal|last=M. Bras-Amorós|title=Tempered monoids of real numbers, the golden fractal monoid, and the well-tempered harmonic semigroup|journal=Semigroup Forum|url=https://link.springer.com/article/10.1007/s00233-019-10059-4|doi=10.1007/s00233-019-10059-4|year=2019|volume=99|issue=2 |pages=496–516|arxiv=1703.01077|s2cid=253781462 }}</ref>
== Embedding dimension, multiplicity ==
The set ''A'' is a set of generators of the numerical semigroup ⟨ ''A'' ⟩. A set of generators of a numerical semigroup is a minimal system of generators if none of its proper subsets generates the numerical semigroup. It is known that every numerical semigroup ''S'' has a unique minimal system of generators and also that this minimal system of generators is finite. The cardinality of the minimal set of generators is called the ''embedding dimension'' of the numerical semigroup ''S'' and is denoted by ''e''(''S''). The smallest member in the minimal system of generators is called the ''multiplicity'' of the numerical semigroup ''S'' and is denoted by ''m''(''S'').
== Frobenius number and genus == There are several notable numbers associated with a numerical semigroup ''S''. # The set ''N'' − ''S'' is called the set of gaps in ''S'' and is denoted by ''G''(''S''). # The number of elements in the set of gaps ''G''(''S'') is called the genus of ''S'' (or, the degree of singularity of ''S'') and is denoted by ''g''(''S''). # The greatest element in ''G''(''S'') is called the Frobenius number of ''S'' and is denoted by ''F''(''S''). # The smallest element of ''S'' such that all larger integers are likewise elements of ''S'' is called the conductor; it is ''F''(''S'') + 1. === Examples ===
Let ''S'' = ⟨ 5, 7, 9 ⟩. Then we have: * The set of elements in ''S'' : ''S'' = {0, 5, 7, 9, 10, 12, 14, ...}. * The minimal set of generators of ''S'' : {5, 7, 9}. * The embedding dimension of ''S'' : ''e''(''S'') = 3. * The multiplicity of ''S'' : ''m''(''S'') = 5. * The set of gaps in ''S'' : ''G''(''S'') = {1, 2, 3, 4, 6, 8, 11, 13}. * The Frobenius number of ''S'' is ''F''(''S'') = 13, and its conductor is 14. * The genus of ''S'' : ''g''(''S'') = 8.
'''Numerical semigroups with small Frobenius number or genus''' {| class="wikitable" ! ''n'' !!Semigroup ''S'' <br /> with ''F''(''S'') = ''n'' !!Semigroup ''S'' <br /> with ''g''(''S'') = ''n'' |- | 1 || ⟨ 2, 3 ⟩ || ⟨ 2, 3 ⟩ |- | 2 || ⟨ 3, 4, 5 ⟩ || ⟨ 3, 4, 5 ⟩ <br /> ⟨ 2, 5 ⟩ |- | 3 || ⟨ 4, 5, 6, 7 ⟩ <br /> ⟨ 2, 5 ⟩ || ⟨ 4, 5, 6, 7 ⟩ <br /> ⟨ 3, 5, 7 ⟩ <br /> ⟨ 3, 4 ⟩ <br /> ⟨ 2, 7 ⟩ |- | 4 || ⟨ 5, 6, 7, 8, 9 ⟩ <br /> ⟨ 3, 5, 7 ⟩ || ⟨ 5, 6, 7, 8, 9 ⟩ <br /> ⟨ 4, 6, 7, 9 ⟩ <br /> ⟨ 3, 7, 8 ⟩ <br /> ⟨ 4, 5, 7 ⟩ <br /> ⟨ 4, 5, 6 ⟩ <br /> ⟨ 3, 5, ⟩ <br /> ⟨ 2, 9 ⟩ |}
== Computation of Frobenius number ==
=== Numerical semigroups with embedding dimension two ===
The following general results were known to Sylvester.<ref>{{cite journal|last=J. J. Sylvester|department=Mathematics from the ''Educational Times'' with additional papers and solutions|journal=Educational Times|year=1884|volume=41|page=21|title=7382|url=https://archive.org/details/mathematicalque05unkngoog/page/n150}}</ref> Let ''a'' and ''b'' be positive integers such that gcd (''a'', ''b'') = 1. Then *''F''(⟨ ''a'', ''b'' ⟩) = (''a'' − 1) (''b'' − 1) − 1 = ''ab'' − (''a'' + ''b''). *''g''(⟨ ''a'', ''b'' ⟩) = (''a'' − 1)(''b'' − 1) / 2.
=== Numerical semigroups with embedding dimension three ===
There is no known general formula to compute the Frobenius number of numerical semigroups having embedding dimension three or more. No polynomial formula can be found to compute the Frobenius number or genus of a numerical semigroup with embedding dimension three.<ref>{{cite journal|last=F. Curtis|title=On formulas for the Frobenius number of a numerical semigroup|journal=Mathematica Scandinavica|year=1990|volume=67|issue=2|pages=190–192|url=https://www.mscand.dk/article/view/12330|accessdate=18 March 2019|doi=10.7146/math.scand.a-12330|doi-access=free}}</ref> Every positive integer is the Frobenius number of some numerical semigroup with embedding dimension three.<ref>{{cite journal|last=J. C. Rosales |display-authors=etal|title=Every positive integer is the Frobenius number of a numerical semigroup with three generators|journal=Mathematica Scandinavica|year=2004|volume=94|pages=5–12|url=http://www.mscand.dk/article/view/14427/12424|accessdate=14 March 2015| issue=1| doi=10.7146/math.scand.a-14427|doi-access=free}}</ref>
=== Rödseth's algorithm ===
The following algorithm, known as Rödseth's algorithm,<ref>{{cite book|last=J.L. Ramírez Alfonsín|title=The Diophantine Frobenius Problem|url=https://archive.org/details/diophantinefrobe00alfo_560|url-access=limited|year=2005|publisher=Oxford University Press|isbn=978-0-19-856820-9|pages=[https://archive.org/details/diophantinefrobe00alfo_560/page/n19 4]–6}}</ref> <ref>{{cite journal|last=Ö.J. Rödseth|title=On a linear Diophantine problem of Frobenius|journal=J. Reine Angew. Math.|year=1978|volume=301|pages=171–178}}</ref> can be used to compute the Frobenius number of a numerical semigroup ''S'' generated by {''a''<sub>1</sub>, ''a''<sub>2</sub>, ''a''<sub>3</sub>} where ''a''<sub>1</sub> < ''a''<sub>2</sub> < ''a''<sub>3</sub> and gcd ( ''a''<sub>1</sub>, ''a''<sub>2</sub>, ''a''<sub>3</sub>) = 1. Its worst-case complexity is not as good as Greenberg's algorithm <ref>{{cite journal|last=Harold Greenberg|title=Solution to a linear Diophantine equation for non-negative integers|journal=Journal of Algorithms|year=1988|volume=9|issue=3|pages=343–353|doi=10.1016/0196-6774(88)90025-9}}</ref> but it is much simpler to describe. *Let ''s''<sub>0</sub> be the unique integer such that ''a''<sub>2</sub>''s''<sub>0</sub> ≡ ''a''<sub>3</sub> mod ''a''<sub>1</sub>, 0 ≤ ''s''<sub>0</sub> < ''a''<sub>1</sub>. *The continued fraction algorithm is applied to the ratio ''a''<sub>1</sub>/''s''<sub>0</sub>: **''a''<sub>1</sub> = ''q''<sub>1</sub>''s''<sub>0</sub> − ''s''<sub>1</sub>, 0 ≤ ''s''<sub>1</sub> < ''s''<sub>0</sub>, **''s''<sub>0</sub> = ''q''<sub>2</sub>''s''<sub>1</sub> − ''s''<sub>2</sub>, 0 ≤ ''s''<sub>2</sub> < ''s''<sub>1</sub>, **''s''<sub>1</sub> = ''q''<sub>3</sub>''s''<sub>2</sub> − ''s''<sub>3</sub>, 0 ≤ ''s''<sub>3</sub> < ''s''<sub>2</sub>, **... **''s''<sub>''m''−1</sub> = ''q''<sub>''m''+1</sub>''s''<sub>''m''</sub>, **''s''<sub>''m''+1</sub> = 0, :where ''q''<sub>i</sub> ≥ 2, ''s''<sub>i</sub> ≥ 0 for all i. *Let ''p''<sub>−1</sub> = 0, ''p''<sub>0</sub> = 1, ''p''<sub>''i''+1</sub> = ''q''<sub>''i''+1</sub>''p''<sub>i</sub> − ''p''<sub>''i''−1</sub> and ''r''<sub>i</sub> = (''s''<sub>''i''</sub>''a''<sub>2</sub> − ''p''<sub>''i''</sub>''a''<sub>3</sub>)/''a''<sub>1</sub>. *Let ''v'' be the unique integer number such that ''r''<sub>''v''+1</sub> ≤ 0 < ''r''<sub>''v''</sub>, or equivalently, the unique integer such **''s''<sub>''v''+1</sub>/''p''<sub>''v''+1</sub> ≤ ''a''<sub>3</sub>/''a''<sub>2</sub> < ''s''<sub>''v''</sub>/''p''<sub>''v''</sub>· *Then, ''F''(''S'') = −''a''<sub>1</sub> + ''a''<sub>2</sub>(''s''<sub>''v''</sub> − 1) + ''a''<sub>3</sub>(''p''<sub>''v''+1</sub> − 1) − min{''a''<sub>2</sub>''s''<sub>''v''+1</sub>, ''a''<sub>3</sub>''p''<sub>''v''</sub>}.
== Special classes of numerical semigroups == An ''irreducible numerical semigroup'' is a numerical semigroup such that it cannot be written as the intersection of two numerical semigroups properly containing it. A numerical semigroup ''S'' is irreducible if and only if ''S'' is maximal, with respect to set inclusion, in the collection of all numerical semigroups with Frobenius number ''F''(''S'').
A numerical semigroup ''S '' is ''symmetric'' if it is irreducible and its Frobenius number ''F''(''S'') is odd. We say that ''S'' is ''pseudo-symmetric'' provided that ''S'' is irreducible and F(S) is even. Such numerical semigroups have simple characterizations in terms of Frobenius number and genus: *A numerical semigroup ''S'' is symmetric if and only if ''g''(''S'') = (''F''(''S'') + 1)/2. *A numerical semigroup ''S'' is pseudo-symmetric if and only if ''g''(''S'') = (''F''(''S'') + 2)/2.
== See also == *Frobenius number *Special classes of semigroups *Semigroup *Sylver coinage
== References == {{reflist}}
Category:Semigroup theory Category:Algebraic structures Category:Number theory