<?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 2:
Numerical Semigroups
</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" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><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="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="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<p><a id="X8324E5D97DC2A801" name="X8324E5D97DC2A801"></a></p>
<div class="ChapSects"><a href="chap2.html#X8324E5D97DC2A801">2 <span class="Heading">
Numerical Semigroups
</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7E89D7EB7FCC2197">2.1 <span class="Heading">
Generating Numerical Semigroups
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X86DEEBFE854B60A6">2.1-1 NumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X87206D597873EAFF">2.1-2 ModularNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X879171CD7AC80BB5">2.1-3 ProportionallyModularNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X79B38AB3816BF3C5">2.1-4 NumericalSemigroupByGenerators</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap2.html#X7EF4254C81ED6665">2.2 <span class="Heading">Some basic tests</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X7B1B6B8C82BD7084">2.2-1 IsNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X87B02A9F7AF90CB9">2.2-2 RepresentsSmallElementsOfNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X78906CCD7BEE0E58">2.2-3 RepresentsGapsOfNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X84A611557B5ACF42">2.2-4 IsAperyListOfNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X86D5B3517AF376D4">2.2-5 IsSubsemigroupOfNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2.html#X864C2D8E80DD6D16">2.2-6 BelongsToNumericalSemigroup</a></span>
</div>
</div>
<h3>2 <span class="Heading">
Numerical Semigroups
</span></h3>
<p>This chapter describes how to create numerical semigroups in <strong class="pkg">GAP</strong> and perform some basic tests.</p>
<p><a id="X7E89D7EB7FCC2197" name="X7E89D7EB7FCC2197"></a></p>
<h4>2.1 <span class="Heading">
Generating Numerical Semigroups
</span></h4>
<p>Recalling some definitions from Chapter <a href="chap1.html#X7DFB63A97E67C0A1"><b>1</b></a>.</p>
<p>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.</p>
<p>We refer to the elements in a numerical semigroup that are less than or equal to the Frobenius number plus 1 as <em>small elements</em> of the semigroup.</p>
<p>A <em>gap</em> of a numerical semigroup S is a nonnegative integer not belonging to S. The <em>fundamental gaps</em> of S are those gaps that are maximal with respect to the partial order induced by division in N.</p>
<p>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 <em>Apéry set</em> of S with respect to s.</p>
<p>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)= Ncap bigcup_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 <em>proportionally modular</em>. If C = 1, then it is said to be <em>modular</em>.</p>
<p>There are several different ways to specify a numerical semigroup S, namely, by its generators; by its gaps, its fundamental or special gaps by its Apéry set, just to name some. In this section we describe functions that may be used to specify, in one of these ways, a numerical semigroup in <strong class="pkg">GAP</strong>.</p>
<p>To create a numerical semigroup in <strong class="pkg">GAP</strong> the function <code class="code">NumericalSemigroup</code> is used.</p>
<p><a id="X86DEEBFE854B60A6" name="X86DEEBFE854B60A6"></a></p>
<h5>2.1-1 NumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroup</code>( <var class="Arg">Type, List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Type</code></p>
<p>May be <code class="code">"generators"</code>, <code class="code">"minimalgenerators"</code>, <code class="code">"modular"</code>, <code class="code">"propmodular"</code>, <code class="code">"elements"</code>, <code class="code">"gaps"</code>, <code class="code">"fundamentalgaps"</code>, <code class="code">"subadditive"</code> or <code class="code">"apery"</code> according to whether the semigroup is to be given by means of a condition of the form ax mod m <= x, a system of generators, a condition of the form ax mod m <= cx, a set of all elements up to the Frobenius number +1, the set of gaps, the set of fundamental gaps, a periodic subaditive function or the Apéry set.</p>
<p>When no string is given as first argument it is assumed that the numerical semigroup will be given by means of a set of generators.</p>
<p><code class="code">List</code></p>
<p>When the semigroup is given through a set of generators, this set may be given as a list or through its individual elements.</p>
<p>The set of all elements up to the Frobenius number +1, the set of gaps, the set of fundamental gaps or the Apéry set are given through lists.</p>
<p>A periodic subadditive function with period m is given through the list of images of the elements, from 1 to m. The image of m has to be 0.</p>
<table class="example">
<tr><td><pre>
gap> s1 := NumericalSemigroup("generators",3,5,7);
<Numerical semigroup with 3 generators>
gap> s2 := NumericalSemigroup("generators",[3,5,7]);
<Numerical semigroup with 3 generators>
gap> s1=s2;
true
gap> s := NumericalSemigroup("minimalgenerators",3,7);
<Numerical semigroup with 2 generators>
gap> s := NumericalSemigroup("modular",3,5);
<Modular numerical semigroup satisfying 3x mod 5 <= x >
gap> s1 := NumericalSemigroup("generators",2,5);
<Numerical semigroup with 2 generators>
gap> s = s1;
true
....................................
</pre></td></tr></table>
<p><a id="X87206D597873EAFF" name="X87206D597873EAFF"></a></p>
<h5>2.1-2 ModularNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ModularNumericalSemigroup</code>( <var class="Arg">a, b</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Given two positive integers <var class="Arg">a</var> and <var class="Arg">b</var>, this function returns a modular numerical semigroup satisfying ax mod b <= x.</p>
<table class="example">
<tr><td><pre>
gap> ModularNumericalSemigroup(3,7);
<Modular numerical semigroup satisfying 3x mod 7 <= x >
</pre></td></tr></table>
<p><a id="X879171CD7AC80BB5" name="X879171CD7AC80BB5"></a></p>
<h5>2.1-3 ProportionallyModularNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ProportionallyModularNumericalSemigroup</code>( <var class="Arg">a, b, c</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Given three positive integers <var class="Arg">a</var>, <var class="Arg">b</var> and <var class="Arg">c</var>, this function returns a proportionally modular numerical semigroup satisfying ax mod b <= cx.</p>
<table class="example">
<tr><td><pre>
gap> ProportionallyModularNumericalSemigroup(3,7,12);
<Proportionally modular numerical semigroup satisfying 3x mod 7 <= 12x >
</pre></td></tr></table>
<p><a id="X79B38AB3816BF3C5" name="X79B38AB3816BF3C5"></a></p>
<h5>2.1-4 NumericalSemigroupByGenerators</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupByGenerators</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupByMinimalGenerators</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupByMinimalGeneratorsNC</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupByInterval</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupByOpenInterval</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupBySubAdditiveFunction</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupByAperyList</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupBySmallElements</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupByGaps</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NumericalSemigroupByFundamentalGaps</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="func">NumericalSemigroup</code> (<a href="chap2.html#X86DEEBFE854B60A6"><b>2.1-1</b></a>) is a front-end for these functions. The argument of each of these functions is a list representing an entity of the type to which the function's name refers.</p>
<table class="example">
<tr><td><pre>
gap> s:=NumericalSemigroup(3,11);
<Numerical semigroup with 2 generators>
gap> GapsOfNumericalSemigroup(s);
[ 1, 2, 4, 5, 7, 8, 10, 13, 16, 19 ]
gap> t:=NumericalSemigroupByGaps(last);
<Numerical semigroup>
gap> s=t;
true
gap> AperyListOfNumericalSemigroupWRTElement(s,20);;
gap> t:=NumericalSemigroupByAperyList(last);
<Numerical semigroup>
gap> s=t;
true
...
</pre></td></tr></table>
<p><a id="X7EF4254C81ED6665" name="X7EF4254C81ED6665"></a></p>
<h4>2.2 <span class="Heading">Some basic tests</span></h4>
<p>This section describes some basic tests on numerical semigroups.The first described tests refer to the way the semigroup was created. Then are presented functions to test if a given list represents the small elements, gaps or the Apéry set (see <a href="chap1.html#X7DFB63A97E67C0A1"><b>1.</b></a>) of a numerical semigroup; to test if an integer belongs to a numerical semigroup and if a numerical semigroup is a subsemigroup of another one.</p>
<p><a id="X7B1B6B8C82BD7084" name="X7B1B6B8C82BD7084"></a></p>
<h5>2.2-1 IsNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroup</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupByGenerators</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupByMinimalGenerators</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupByInterval</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupByOpenInterval</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupBySubAdditiveFunction</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupByAperyList</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupBySmallElements</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupByGaps</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNumericalSemigroupByFundamentalGaps</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsProportionallyModularNumericalSemigroup</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsModularNumericalSemigroup</code>( <var class="Arg">NS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><var class="Arg">NS</var> is a numerical semigroup and these attributes are available (their names should be self explanatory).</p>
<table class="example">
<tr><td><pre>
gap> s:=NumericalSemigroup(3,7);
<Numerical semigroup with 2 generators>
gap> AperyListOfNumericalSemigroupWRTElement(s,30);;
gap> t:=NumericalSemigroupByAperyList(last);
<Numerical semigroup>
gap> IsNumericalSemigroupByGenerators(s);
true
gap> IsNumericalSemigroupByGenerators(t);
false
gap> IsNumericalSemigroupByAperyList(s);
false
gap> IsNumericalSemigroupByAperyList(t);
true
</pre></td></tr></table>
<p><a id="X87B02A9F7AF90CB9" name="X87B02A9F7AF90CB9"></a></p>
<h5>2.2-2 RepresentsSmallElementsOfNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RepresentsSmallElementsOfNumericalSemigroup</code>( <var class="Arg">L</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Tests if the list <var class="Arg">L</var> (which has to be a set) may represent the ``small" # elements of a numerical semigroup.</p>
<table class="example">
<tr><td><pre>
gap> L:=[ 0, 3, 6, 9, 11, 12, 14, 15, 17, 18, 20 ];
[ 0, 3, 6, 9, 11, 12, 14, 15, 17, 18, 20 ]
gap> RepresentsSmallElementsOfNumericalSemigroup(L);
true
gap> L:=[ 6, 9, 11, 12, 14, 15, 17, 18, 20 ];
[ 6, 9, 11, 12, 14, 15, 17, 18, 20 ]
gap> RepresentsSmallElementsOfNumericalSemigroup(L);
false
</pre></td></tr></table>
<p><a id="X78906CCD7BEE0E58" name="X78906CCD7BEE0E58"></a></p>
<h5>2.2-3 RepresentsGapsOfNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RepresentsGapsOfNumericalSemigroup</code>( <var class="Arg">L</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Tests if the list <var class="Arg">L</var> may represent the gaps (see <a href="chap1.html#X7DFB63A97E67C0A1"><b>1.</b></a>) of a numerical semigroup.</p>
<table class="example">
<tr><td><pre>
gap> s:=NumericalSemigroup(3,7);
<Numerical semigroup with 2 generators>
gap> L:=GapsOfNumericalSemigroup(s);
[ 1, 2, 4, 5, 8, 11 ]
gap> RepresentsGapsOfNumericalSemigroup(L);
true
gap> L:=Set(List([1..21],i->RandomList([1..50])));
[ 2, 6, 7, 8, 10, 12, 14, 19, 24, 28, 31, 35, 42, 50 ]
gap> RepresentsGapsOfNumericalSemigroup(L);
false
</pre></td></tr></table>
<p><a id="X84A611557B5ACF42" name="X84A611557B5ACF42"></a></p>
<h5>2.2-4 IsAperyListOfNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsAperyListOfNumericalSemigroup</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Tests whether a list <var class="Arg">L</var> of integers may represent the Apéry list of a numerical semigroup. It returns <code class="keyw">true</code> when the periodic function represented by <var class="Arg">L</var> is subadditive (see <code class="func">RepresentsPeriodicSubAdditiveFunction</code> (<a href="chapA.html#X8466A4DC82F07579"><b>A.2-1</b></a>)) and the remainder of the division of <code class="code">L[i]</code> by the length of <var class="Arg">L</var> is <code class="code">i</code> and returns <code class="keyw">false</code> otherwise (the crieterium used is the one explained in <a href="chapBib.html#biBR96">[Ros96b]</a>).</p>
<table class="example">
<tr><td><pre>
gap> IsAperyListOfNumericalSemigroup([0,21,7,28,14]);
true
</pre></td></tr></table>
<p><a id="X86D5B3517AF376D4" name="X86D5B3517AF376D4"></a></p>
<h5>2.2-5 IsSubsemigroupOfNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsSubsemigroupOfNumericalSemigroup</code>( <var class="Arg">S, T</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">S</var> and <var class="Arg">T</var> are numerical semigroups. Tests whether <var class="Arg">T</var> is contained in <var class="Arg">S</var>.</p>
<table class="example">
<tr><td><pre>
gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> T := NumericalSemigroup(2,3);
<Numerical semigroup with 2 generators>
gap> IsSubsemigroupOfNumericalSemigroup(T,S);
true
gap> IsSubsemigroupOfNumericalSemigroup(S,T);
false
</pre></td></tr></table>
<p><a id="X864C2D8E80DD6D16" name="X864C2D8E80DD6D16"></a></p>
<h5>2.2-6 BelongsToNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BelongsToNumericalSemigroup</code>( <var class="Arg">n, S</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">n</var> is an integer and <var class="Arg">S</var> is a numerical semigroup. Tests whether <var class="Arg">n</var> belongs to <var class="Arg">S</var>. <code class="code">n in S</code> is the short for <code class="code">BelongsToNumericalSemigroup(n,S)</code>.</p>
<table class="example">
<tr><td><pre>
gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> BelongsToNumericalSemigroup(15,S);
false
gap> 15 in S;
false
gap> SmallElementsOfNumericalSemigroup(S);
[ 0, 11, 12, 13, 22, 23, 24, 25, 26, 32, 33, 34, 35, 36, 37, 38, 39, 43 ]
gap> BelongsToNumericalSemigroup(13,S);
true
gap> 13 in S;
true
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap1.html">Previous Chapter</a> <a href="chap3.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><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="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 />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
2464
