Numerical semigroup

Last updated

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. [1] [2]

Contents

The definition of numerical semigroup is intimately related to the problem of determining nonnegative integers that can be expressed in the form x1n1 + x2n2 + ... + xrnr for a given set {n1, n2, ..., nr} of positive integers and for arbitrary nonnegative integers x1, x2, ..., xr. This problem had been considered by several mathematicians like Frobenius (1849–1917) and Sylvester (1814–1897) at the end of the 19th century. [3] During the second half of the twentieth century, interest in the study of numerical semigroups resurfaced because of their applications in algebraic geometry. [4]

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.

  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 = {n1, n2, ..., nr} be a nonempty set of positive integers. The set of all integers of the form x1n1 + x2n2 + ... + xrnr 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. [5]

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 , ...}.
  6. Well-tempered harmonic semigroup H={0,12,19,24,28,31,34,36,38,40,42,43,45,46,47,48,...} [6]

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 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).
  3. The greatest element in G(S) is called the Frobenius number of S and is denoted by F(S).
  4. 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:


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 ⟩

Computation of Frobenius number

Numerical semigroups with embedding dimension two

The following general results were known to Sylvester. [7] Let a and b be positive integers such that gcd (a, b) = 1. Then

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. [8] Every positive integer is the Frobenius number of some numerical semigroup with embedding dimension three. [9]

Rödseth's algorithm

The following algorithm, known as Rödseth's algorithm, [10] [11] can be used to compute the Frobenius number of a numerical semigroup S generated by {a1, a2, a3} where a1 < a2 < a3 and gcd ( a1, a2, a3) = 1. Its worst-case complexity is not as good as Greenberg's algorithm [12] but it is much simpler to describe.

where qi ≥ 2, si ≥ 0 for all i.

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:

See also

Related Research Articles

In mathematics, more specifically in ring theory, a Euclidean domain is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination of them. Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is a unique factorization domain.

<span class="mw-page-title-main">Monoid</span> Algebraic structure with an associative operation and an identity element

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.

<span class="mw-page-title-main">Semigroup</span> Algebraic structure consisting of a set with an associative binary operation

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

<span class="mw-page-title-main">Symmetric group</span> Type of group in abstract algebra

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are such permutation operations, the order of the symmetric group is .

In mathematics, the concept of an inverse element generalises the concepts of opposite and reciprocal of numbers.

<span class="mw-page-title-main">Gaussian integer</span> Complex number whose real and imaginary parts are both integers

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as or

<span class="mw-page-title-main">Generating set of a group</span> Abstract algebra concept

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.

In mathematics, in particular abstract algebra, a graded ring is a ring such that the underlying additive group is a direct sum of abelian groups such that ⁠⁠. The index set is usually the set of nonnegative integers or the set of integers, but can be any monoid. The direct sum decomposition is usually referred to as gradation or grading.

Ring theory is the branch of mathematics in which rings are studied: that is, structures supporting both an addition and a multiplication operation. This is a glossary of some terms of the subject.

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.

In mathematics, the term Cartan matrix has three meanings. All of these are named after the French mathematician Élie Cartan. Amusingly, the Cartan matrices in the context of Lie algebras were first investigated by Wilhelm Killing, whereas the Killing form is due to Cartan.

In matrix theory, the Perron–Frobenius theorem, proved by Oskar Perron and Georg Frobenius, asserts that a real square matrix with positive entries has a unique eigenvalue of largest magnitude and that eigenvalue is real. The corresponding eigenvector can be chosen to have strictly positive components, and also asserts a similar statement for certain classes of nonnegative matrices. This theorem has important applications to probability theory ; to the theory of dynamical systems ; to economics ; to demography ; to social networks ; to Internet search engines (PageRank); and even to ranking of American football teams. The first to discuss the ordering of players within tournaments using Perron–Frobenius eigenvectors is Edmund Landau.

In mathematics, the Grothendieck group, or group of differences, of a commutative monoid M is a certain abelian group. This abelian group is constructed from M in the most universal way, in the sense that any abelian group containing a homomorphic image of M will also contain a homomorphic image of the Grothendieck group of M. The Grothendieck group construction takes its name from a specific case in category theory, introduced by Alexander Grothendieck in his proof of the Grothendieck–Riemann–Roch theorem, which resulted in the development of K-theory. This specific case is the monoid of isomorphism classes of objects of an abelian category, with the direct sum as its operation.

<span class="mw-page-title-main">Coin problem</span> Mathematical problem

In mathematics, the coin problem is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. The Frobenius number exists as long as the set of coin denominations is setwise coprime.

In algebra, a presentation of a monoid is a description of a monoid in terms of a set Σ of generators and a set of relations on the free monoid Σ∗ generated by Σ. The monoid is then presented as the quotient of the free monoid by these relations. This is an analogue of a group presentation in group theory.

<span class="mw-page-title-main">Monogenic semigroup</span>

In mathematics, a monogenic semigroup is a semigroup generated by a single element. Monogenic semigroups are also called cyclic semigroups.

In mathematics, a semigroup with two elements is a semigroup for which the cardinality of the underlying set is two. There are exactly five nonisomorphic semigroups having two elements:

In mathematical optimization, the problem of non-negative least squares (NNLS) is a type of constrained least squares problem where the coefficients are not allowed to become negative. That is, given a matrix A and a (column) vector of response variables y, the goal is to find

In mathematics, Bhargava's factorial function, or simply Bhargava factorial, is a certain generalization of the factorial function developed by the Fields Medal winning mathematician Manjul Bhargava as part of his thesis in Harvard University in 1996. The Bhargava factorial has the property that many number-theoretic results involving the ordinary factorials remain true even when the factorials are replaced by the Bhargava factorials. Using an arbitrary infinite subset S of the set of integers, Bhargava associated a positive integer with every positive integer k, which he denoted by k !S, with the property that if one takes S = itself, then the integer associated with k, that is k !, would turn out to be the ordinary factorial of k.

References

  1. ↑ Garcia-Sanchez, P.A. "Numerical semigroups minicourse" . Retrieved 6 April 2011.
  2. ↑ Finch, Steven. "Monoids of Natural Numbers" (PDF). INRIA Algorithms Project. Retrieved 7 April 2011.
  3. ↑ J.C. Rosales and P.A. Garcia-Sanchez (2009). Numerical Semigroups. Springer. ISBN   978-1-4419-0159-0.
  4. ↑ V. Barucci; et al. (1997). "Maximality properties in numerical semigroups and applications to one-dimensional analytically irreducible local domains". Memoirs of the Amer. Math. Soc. 598.
  5. ↑ García-Sánchez, J.C. Rosales, P.A. (2009). Numerical semigroups (First. ed.). New York: Springer. p. 7. ISBN   978-1-4419-0160-6.{{cite book}}: CS1 maint: multiple names: authors list (link)
  6. ↑ M. Bras-Amorós (2019). "Tempered monoids of real numbers, the golden fractal monoid, and the well-tempered harmonic semigroup". Semigroup Forum . 99 (2): 496–516. arXiv: 1703.01077 . doi:10.1007/s00233-019-10059-4. S2CID   253781462.
  7. ↑ J. J. Sylvester (1884). "7382". Mathematics from the Educational Times with additional papers and solutions. Educational Times. 41: 21.
  8. ↑ F. Curtis (1990). "On formulas for the Frobenius number of a numerical semigroup". Mathematica Scandinavica . 67 (2): 190–192. doi: 10.7146/math.scand.a-12330 . Retrieved 18 March 2019.
  9. ↑ J. C. Rosales; et al. (2004). "Every positive integer is the Frobenius number of a numerical semigroup with three generators". Mathematica Scandinavica . 94 (1): 5–12. doi: 10.7146/math.scand.a-14427 . Retrieved 14 March 2015.
  10. ↑ J.L. Ramírez Alfonsín (2005). The Diophantine Frobenius Problem . Oxford University Press. pp.  4–6. ISBN   978-0-19-856820-9.
  11. ↑ Ö.J. Rödseth (1978). "On a linear Diophantine problem of Frobenius". J. Reine Angew. Math. 301: 171–178.
  12. ↑ Harold Greenberg (1988). "Solution to a linear Diophantine equation for non-negative integers". Journal of Algorithms. 9 (3): 343–353. doi:10.1016/0196-6774(88)90025-9.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.