In mathematics, a numerical semigroup is a special kind of a semigroup

Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...

. Its underlying set

Set

A set is a collection of well defined and distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematics. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from...

 is the set of all nonnegative integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s except a finite number and the binary operation

Binary operation

In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....

 is the operation of addition

Addition

Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....

 of integers. Also, the integer 0

0 (number)

0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...

 must be an element of the semigroup. For example, while the set

Set

A set is a collection of well defined and distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematics. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from...

 {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 numerical semigroups are also called 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₁n₁ + x₂ n₂ + ... + x_r n_r for a given set {n₁, n₂, ..., n_r} of positive integers and for arbitrary nonnegative integers x₁, x₂, ..., x_r. This problem had been considered by several mathematicians like Frobenius

Ferdinand Georg Frobenius

Ferdinand Georg Frobenius was a German mathematician, best known for his contributions to the theory of differential equations and to group theory...

 (1849 – 1917) and Sylvester

James Joseph Sylvester

James Joseph Sylvester was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory and combinatorics...

 (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

Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...

.

Definition

Let N be the set of nonnegative integers. A subset S of N is called a numerical semigroup if and only if the following conditions are satisfied.

1. 0 is an element of S
2. N − S, the complement of S in N, is finite.
3. 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₁, n₂, ..., n_r} be a nonempty set of positive integers. The set of all integers of the form x₁ n₁ + x₂ n₂ + ... + 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 subset of N generated by A. Then S is a numerical semigroup if and only if gcd

Greatest common divisor

In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

 (A) = 1. Moreover, every numerical semigroup arises in this way.

Examples

The following subsets of N are numerical semigroups.

1. ⟨ 1 ⟩ = {0, 1, 2, 3, ...}
2. ⟨ 1, 2 ⟩ = {0, 1, 2, 3, ...}
3. ⟨ 2, 3 ⟩ = {0, 2, 3, 4, 5, 6, ...}
4. Let a be a positive integer. ⟨ a, a + 1, a + 2, ... , 2a - 1 ⟩ = {0, a, a + 1, a + 2, a + 3, ...}.
5. 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 , ...}.

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.

1. The set N − S is called the set of gaps in S and is denoted by G(S).
2. The number 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).
3. The greatest element in G(S) is called the Frobenius number ( or, the conductor) of S and is denoted by F(S).

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 : F(S) = 13.
• The genus of S : g(S) = 8.

Numerical semigroups with small Frobenius number or genus

n	Semigroup S    with F(S) = n	Semigroup S    with g(S) = n
1	⟨ 2, 3 ⟩	⟨ 2, 3 ⟩
2	⟨ 3, 4, 5 ⟩	⟨ 3, 4, 5 ⟩    ⟨ 2, 5 ⟩
3	⟨ 4, 5, 6, 7 ⟩    ⟨ 2, 5 ⟩	⟨ 4, 5, 6, 7, ⟩    ⟨ 3, 5, 7 ⟩    ⟨ 3, 4 ⟩    ⟨ 2, 7 ⟩
4	⟨ 5, 6, 7, 8, 9 ⟩    ⟨ 3, 5, 7 ⟩	⟨ 5, 6, 7, 8, 9 ⟩    ⟨ 4, 6, 7, 9 ⟩    ⟨ 3, 7, 8 ⟩    ⟨ 4, 5, 7 ⟩    ⟨ 4, 5, 6 ⟩    ⟨ 3, 5, ⟩    ⟨ 2, 9 ⟩

Numerical semigroups with embedding dimension two

The following general results were known to Sylvester. Let a and b be positive integers such that gcd

Greatest common divisor

In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

 (a, b) = 1. Then

• F(⟨ a, b ⟩) = (a − 1) (b − 1) − 1.
• 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. It is also known that no polynomial formula can be found to compute the Frobenius number or genus of a numerical semigroup with embedding dimension three. Interestingly, it is known that every positive integer is the Frobenius number of some numerical semigroup with embedding dimension three.

Rodseth's algorithm

The following algorithm, known as Rodseth's algorithm, can be used to compute the Frobenius number of a numerical semigroup S generated by {a₁, a₂, a₃} where a₁ < a₂ < a₃ and gcd

Greatest common divisor

In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

( a₁, a₂, a₃) = 1.

• Let s₀ be the unique integer such that a₂s₀ ≡ a₃ mod a₁, 0 ≤ s₀ < a₁.
• The continued fraction algorithm is applied to the ratio a₁/s₀:
  • a₁ = q₁s₀ − s₁, 0 ≤ s₁ < s₀,
  • s₀ = q₂s₁ − s₂, 0 ≤ s₂ < s₁,
  • s₁ = q₃s₂ − s₃, 0 ≤ s₃ < s₂,
  • ...
  • s_m−1 = q_m+1s_m,
  • s_m+1 = 0,

where q_i ≥ 2, s_i ≥ 0 for all i.

• Let p₋₁ = 0, p₀ = 1, p_i+1 = q_i+1p_i − p_i−1 and r_i = (s_ia₂ − p_ia₃)/a₁.
• 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₃/a₂ < s_v/p_v·
• Then, F(S) = −a₁ + a₂(s_v − 1) + a₃(p_v+1 − 1) − min{a₂s_v+1, a₃p_v}.

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.