numerical monoid
   HOME

TheInfoList



OR:

In mathematics, a numerical semigroup is a special kind of a semigroup. Its underlying
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
is the set of all nonnegative
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s except a finite number and the
binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...
is the operation of
addition Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
of integers. Also, the integer 0 must be an element of the semigroup. For example, while the set is a numerical semigroup, the set is not because 1 is in the set and 1 + 1 = 2 is not in the set. Numerical semigroups are commutative
monoids In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids ar ...
and are also known as numerical monoids. The definition of numerical semigroup is intimately related to the problem of determining nonnegative integers that can be expressed in the form ''x''1''n''1 + ''x''2 ''n''2 + ... + ''x''''r'' ''n''''r'' for a given set of positive integers and for arbitrary nonnegative integers ''x''1, ''x''2, ..., ''x''''r''. This problem had been considered by several mathematicians like Frobenius (1849–1917) and
Sylvester Sylvester or Silvester is a name derived from the Latin adjective ''silvestris'' meaning "wooded" or "wild", which derives from the noun ''silva'' meaning "woodland". Classical Latin spells this with ''i''. In Classical Latin, ''y'' represented a ...
(1814–1897) at the end of the 19th century. During the second half of the twentieth century, interest in the study of numerical semigroups resurfaced because of their applications in
algebraic geometry Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
.


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'' = be a nonempty set of positive integers. The set of all integers of the form ''x''1 ''n''1 + ''x''2 ''n''2 + ... + ''x''''r'' ''n''''r'' 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.


Examples

The following subsets of ''N'' are numerical semigroups. #⟨ 1 ⟩ = #⟨ 1, 2 ⟩ = #⟨ 2, 3 ⟩ = #Let ''a'' be a positive integer. ⟨ ''a'', ''a'' + 1, ''a'' + 2, ... , 2''a'' – 1 ⟩ = . #Let ''b'' be an odd integer greater than 1. Then ⟨ 2, ''b'' ⟩ = . # Well-tempered
harmonic A harmonic is a wave with a frequency that is a positive integer multiple of the ''fundamental frequency'', the frequency of the original periodic signal, such as a sinusoidal wave. The original signal is also called the ''1st harmonic'', the ...
semigroup ''H''=


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 The coin problem (also referred to as the Frobenius coin problem or Frobenius problem, after the mathematician Ferdinand Frobenius) is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of ...
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'' = . * The minimal set of generators of ''S'' : . * The embedding dimension of ''S'' : ''e''(''S'') = 3. * The multiplicity of ''S'' : ''m''(''S'') = 5. * The set of gaps in ''S'' : ''G''(''S'') = . * 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


Computation of Frobenius number


Numerical semigroups with embedding dimension two

The following general results were known to Sylvester. 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. Every positive integer is the Frobenius number of some numerical semigroup with embedding dimension three.


Rödseth's algorithm

The following algorithm, known as Rödseth's algorithm, can be used to compute the Frobenius number of a numerical semigroup ''S'' generated by where ''a''1 < ''a''2 < ''a''3 and gcd ( ''a''1, ''a''2, ''a''3) = 1. Its worst-case complexity is not as good as Greenberg's algorithm but it is much simpler to describe. *Let ''s''0 be the unique integer such that ''a''2''s''0 ≡ ''a''3 mod ''a''1, 0 ≤ ''s''0 < ''a''1. *The continued fraction algorithm is applied to the ratio ''a''1/''s''0: **''a''1 = ''q''1''s''0 − ''s''1, 0 ≤ ''s''1 < ''s''0, **''s''0 = ''q''2''s''1 − ''s''2, 0 ≤ ''s''2 < ''s''1, **''s''1 = ''q''3''s''2 − ''s''3, 0 ≤ ''s''3 < ''s''2, **... **''s''''m''−1 = ''q''''m''+1''s''''m'', **''s''''m''+1 = 0, :where ''q''i ≥ 2, ''s''i ≥ 0 for all i. *Let ''p''−1 = 0, ''p''0 = 1, ''p''''i''+1 = ''q''''i''+1''p''i − ''p''''i''−1 and ''r''i = (''s''''i''''a''2 − ''p''''i''''a''3)/''a''1. *Let ''v'' be the unique integer number such that ''r''''v''+1 ≤ 0 < ''r''''v'', or equivalently, the unique integer such **''s''''v''+1/''p''''v''+1 ≤ ''a''3/''a''2 < ''s''''v''/''p''''v''· *Then, ''F''(''S'') = −''a''1 + ''a''2(''s''''v'' − 1) + ''a''3(''p''''v''+1 − 1) − min.


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 The coin problem (also referred to as the Frobenius coin problem or Frobenius problem, after the mathematician Ferdinand Frobenius) is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of ...
*
Special classes of semigroups In mathematics, a semigroup is a nonempty set together with an associative binary operation. A special class of semigroups is a class of semigroups satisfying additional properties or conditions. Thus the class of commutative semigroups consists o ...
* Semigroup *
Sylver coinage Sylver coinage is a mathematical game for two players, invented by John H. Conway. It is discussed in chapter 18 of '' Winning Ways for Your Mathematical Plays''. This article summarizes that chapter. The two players take turns naming positive ...


References

{{reflist Semigroup theory Algebraic structures Number theory