Quelle chap1.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/numericalsgps/doc/chap1.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (NumericalSgps) - Chapter 1:
 Introduction
 </title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap1" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chapA.html">A</a> <a href="chapB.html">B</a> <a href="chapC.html">C</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap0.html">[Previous Chapter]</a> <a href="chap2.html">[Next Chapter]</a> </div>

<a href="chap1_mj.html">[MathJax on]</a>
<a id="X7DFB63A97E67C0A1" name="X7DFB63A97E67C0A1"></a>
<div class="ChapSects"><a href="chap1.html#X7DFB63A97E67C0A1">1 
 Introduction
 </a>
</div>

<h3>1 
 Introduction
 </h3>

A numerical semigroup is a subset of the set N of nonnegative integers that is closed under addition, contains 0 and whose complement in N is finite. The smallest positive integer belonging to a numerical semigroup is its multiplicity.

Let S be a numerical semigroup and A be a subset of S. We say that A is a system of generators of S if S={ k_1 a_1+⋯+ k_n a_n | n,k_1,...,k_n∈ N, a_1,...,a_n∈ A}. The set A is a minimal system of generators of S if no proper subset of A is a system of generators of S.

Every numerical semigroup has a unique minimal system of generators. This is a data that can be used in order to uniquely define a numerical semigroup. Observe that since the complement of a numerical semigroup in the set of nonnegative integers is finite, this implies that the greatest common divisor of the elements of a numerical semigroup is 1, and the same condition must be fulfilled by its minimal system of generators (or by any of its systems of generators).

Given a numerical semigroup S and a nonzero element s in it, one can consider for every integer i ranging from 0 to s-1, the smallest element in S congruent with i modulo s, say w(i) (this element exists since the complement of S in N is finite). Clearly w(0)=0. The set Ap(S,s)={ w(0),w(1),..., w(s-1)} is called the Apéry set of S with respect to s. Note that a nonnegative integer x congruent with i modulo s belongs to S if and only if w(i)≤ x. Thus the pair (s, Ap(S,s)) fully determines the numerical semigroup S (and can be used to easily solve the membership problem to S). This set is in fact one of the most powerfull tools known for numerical semigroups, and it is used almost everywhere in the computation of components and invariants associated to a numerical semigroup. Usually the element s is taken to be the multiplicity, since in this way the resulting Apéry set is the smallest possible.

A gap of a numerical semigroup S is a nonnegative integer not belonging to S. The set of gaps of S is usually denoted by H(S), and clearly determines uniquely S. Note that if x is a gap of S, then so are all the nonnegative integers dividing it. Thus in order to describe S we do not need to know all its gaps, but only those that are maximal with respect to the partial order induced by division in N. These gaps are called fundamental gaps.

The largest nonnegative integer not belonging to a numerical semigroup S is the Frobenius number of S. If S is the set of nonnegative integers, then clearly its Frobenius number is -1, otherwise its Frobenius number coincides with the maximum of the gaps (or fundamental gaps) of S. The Frobenius number plus one is known as the conductor of the semigroup. In this package we refer to the elements in the semigroup that are less than or equal to the conductor as small elements of the semigroup. Observe that from the definition, if S is a numerical semigroup with Frobenius number f, then f+ N∖{0}⊆ S. An integer z is a pseudo-Frobenius number of S if z+S∖{0}⊆ S. Thus the Frobenius number of S is one of its pseudo-Frobenius numbers. The type of a numerical semigroup is the cardinality of the set of its pseudo-Frobenius numbers.

The number of numerical semigroups having a given Frobenius number is finite. The elements in this set of numerical semigroups that are maximal with respect to set inclusion are precisely those numerical semigroups that cannot be expressed as intersection of two other numerical semigroups containing them properly, and thus they are known as irreducible numerical semigroups. Clearly, every numerical semigroup is the intersection of (finitely many) irreducible numerical semigroups.

A numerical semigroup S with Frobenius number f is symmetric if for every integer x, either x∈ S or f-x∈ S. The set of irreducible numerical semigroups with odd Frobenius number coincides with the set of symmetric numerical semigroups. The numerical semigroup S is pseudo-symmetric if f is even and for every integer x not equal to f/2 either x∈ S or f-x∈ S. The set of irreducible numerical semigroups with even Frobenius number is precisely the set of pseudo-symmetric numerical semigroups. These two classes of numerical semigroups have been widely studied in the literature due to their nice applications in Algebraic Geometry. This is probably one of the main reasons that made people turn their attention on numerical semigroups again in the last decades. Symmetric numerical semigroups can be also characterized as those with type one, and pseudo-symmetric numerical semigroups are those numerical semigroups with type two and such that its pseudo-Frobenius numbers are its Frobenius number and its Frobenius number divided by two.

Another class of numerical semigroups that catched the attention of researchers working on Algebraic Geometry and Commutative Ring Theory is the class of numerical semigroups with maximal embedding dimension. The embedding dimension of a numerical semigroup is the cardinality of its minimal system of generators. It can be shown that the embedding dimension is at most the multiplicity of the numerical semigroup. Thus maximal embedding dimension numerical semigroups are those numerical semigroups for which their embedding dimension and multiplicity coincide. These numerical semigroups have nice maximal properties, not only (of course) related to their embedding dimension, but also by means of their presentations. Among maximal embedding dimension there are two classes of numerical semigroups that have been studied due to the connections with the equivalence of algebroid branches. A numerical semigroup S is Arf if for every x≥ y≥ z∈ S, then x+y-z∈ S; and it is saturated if the following condition holds: if s,s_1,...,s_r∈ S are such that s_i≤ s for all i∈ {1,...,r} and z_1,...,z_r∈ Z are such that z_1s_1+⋯+z_rs_r≥ 0, then s+z_1s_1+⋯ +z_rs_r∈ S.

If we look carefully inside the set of fundamental gaps of a numerical semigroup, we see that there are some fulfilling the condition that if they are added to the given numerical semigroup, then the resulting set is again a numerical semigroup. These elements are called special gaps of the numerical semigroup. A numerical semigroup other than the set of nonnegative integers is irreducible if and only if it has only a special gap.

The inverse operation to the one described in the above paragraph is that of removing an element of a numerical semigroup. If we want the resulting set to be a numerical semigroup, then the only thing we can remove is a minimal generator.

Let a,b,c,d be positive integers such that a/b < c/d, and let I=[a/b,c/d]. Then the set S(I)= N∩ ⋃_n≥ 0 n I is a numerical semigroup. This class of numerical semigroups coincides with that of sets of solutions to equations of the form A x mod B ≤ C x with A,B,C positive integers. A numerical semigroup in this class is said to be proportionally modular.

A sequence of positive rational numbers a_1/b_1 < ⋯ < a_n/b_n with a_i,b_i positive integers is a Bézout sequence if a_i+1b_i - a_i b_i+1=1 for all i∈ {1,...,n-1}. If a/b=a_1/b_1 < ⋯ < a_n/b_n =c/d, then S([a/b,c/d])=⟨ a_1,...,a_n⟩. Bézout sequences are not only interesting for this fact, they have shown to be a major tool in the study of proportionally modular numerical semigroups.

If S is a numerical semigroup and k is a positive integer, then the set S/k={ x∈ N | kx∈ S} is a numerical semigroup, known as the quotient S by k.

Let m be a positive integer. A subadditive function with period m is a map f: N-> N such that f(0)=0, f(x+y)≤ f(x)+f(y) and f(x+m)=f(x). If f is a subadditive function with period m, then the set M_f={ x∈ N | f(x)≤ x} is a numerical semigroup. Moreover, every numerical semigroup is of this form. Thus a numerical semigroup can be given by a subadditive function with a given period. If S is a numerical semigroup and s∈ S, snot=0, and Ap(S,s)={ w(0),w(1),..., w(s-1)}, then f(x)=w(x mod s) is a subadditive function with period s such that M_f=S.

Let S be a numerical semigroup generated by {n_1,...,n_k}. Then we can define the following morphism (called sometimes the factorization morphism) by φ: N^k -> S, φ(a_1,...,a_k)=a_1n_1+⋯+a_kn_k. If σ is the kernel congruence of φ (that is, aσ b if φ(a)=φ(b)), then S is isomorphic to N^k/σ. A presentation for S is a system of generators (as a congruence) of σ. If {n_1,...,n_p} is a minimal system of generators, then a minimal presentation is a presentation such that none of its proper subsets is a presentation. Minimal presentations of numerical semigroups coincide with presentations with minimal cardinality, though in general these two concepts are not the same for an arbitrary commutative semigroup.

A set I of integers is an ideal relative to a numerical semigroup S provided that I+S⊆ I and that there exists d∈ S such that d+I⊆ S. If I⊆ S, we simply say that I is an ideal of S. If I and J are relative ideals of S, then so is I-J={z∈ Z | z+J⊆ I}, and it is tightly related to the operation ":" of ideals in a commutative ring.

In this package we have implemented the functions needed to deal with the elements exposed in this introduction.

Many of the algorithms, and the necessary background to understand them, can be found in the monographs <a href="chapBib.html#biBfgcm">[RG99c]</a>, <a href="chapBib.html#biBRGbook">[RG09]</a> and <a href="chapBib.html#biBnsapp">[AG16b]</a>. Some examples in these books have been illustrated with the help of this package. So the reader can also find there more examples on the usage of the functions implemented here.

This package was presented in <a href="chapBib.html#biBJMDA">[DGM06]</a>. For a survey of the features of this package, see <a href="chapBib.html#biBMR3493240">[DG16]</a>.

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap0.html">[Previous Chapter]</a> <a href="chap2.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chapA.html">A</a> <a href="chapB.html">B</a> <a href="chapC.html">C</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality100%

¤ Dauer der Verarbeitung: 0.12 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.