SSL chap11_mj.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/numericalsgps/doc/chap11_mj.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>
<script type="text/javascript"
src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (NumericalSgps) - Chapter 11:
Affine 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" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap11" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chapA_mj.html">A</a> <a href="chapB_mj.html">B</a> <a href="chapC_mj.html">C</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap10_mj.html">[Previous Chapter]</a> <a href="chap12_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap11.html">[MathJax off]</a></p>
<p><a id="X7D92A1997D098A00" name="X7D92A1997D098A00"></a></p>
<div class="ChapSects"><a href="chap11_mj.html#X7D92A1997D098A00">11 <span class="Heading">
Affine semigroups
</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11_mj.html#X7E39DA7780D02DF5">11.1 <span class="Heading">
Defining affine semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7D7B03E17C8DBEA2">11.1-1 AffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X855C8667830AEDDC">11.1-2 AffineSemigroupByEquations</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7846AD1081C14EF1">11.1-3 AffineSemigroupByInequalities</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7CC110D4798AAD99">11.1-4 AffineSemigroupByPMInequality</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X83F6DDB787E07771">11.1-5 AffineSemigroupByGaps</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7A3648D67CF81370">11.1-6 FiniteComplementIdealExtension</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X8361194C86AE807B">11.1-7 Gaps</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X867B27BD81104BEE">11.1-8 Genus</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X80C3CD2082CE02F7">11.1-9 PseudoFrobenius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X82D42FCE81F20277">11.1-10 SpecialGaps</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X84FDF85D7CDEDF3E">11.1-11 Generators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7ED1549486C251CA">11.1-12 MinimalGenerators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X80516BCC78FDD45D">11.1-13 RemoveMinimalGeneratorFromAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7B78E02F7C50583F">11.1-14 AddSpecialGapOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X844806D97B4781B5">11.1-15 AsAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7A2902207BAA3936">11.1-16 IsAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X851788D781A13C50">11.1-17 BelongsToAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X8607B621833FAECB">11.1-18 IsFull</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7D4D017A79AD98E2">11.1-19 HilbertBasisOfSystemOfHomogeneousEquations</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X825B1CD37B0407A6">11.1-20 HilbertBasisOfSystemOfHomogeneousInequalities</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X8307A0597864B098">11.1-21 EquationsOfGroupGeneratedBy</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7A1CE5A98425CEA1">11.1-22 BasisOfGroupGivenByEquations</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11_mj.html#X7F13DF9D7A4FB547">11.2 <span class="Heading">
Gluings of affine semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7FE3B3C380641DDC">11.2-1 GluingOfAffineSemigroups</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11_mj.html#X86A1018D7CB7BA81">11.3 <span class="Heading">
Presentations of affine semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X795EEE4481E0497C">11.3-1 CircuitsOfKernelCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X78B04C198258D3F8">11.3-2 PrimitiveRelationsOfKernelCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7EE005267DEBC1DE">11.3-3 GeneratorsOfKernelCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7AD2271E84F705D3">11.3-4 CanonicalBasisOfKernelCongruence</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7C3546477E07A1EA">11.3-5 GraverBasis</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X80A7BD7478D8A94A">11.3-6 MinimalPresentation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X86BCBD32781EBC2D">11.3-7 BettiElements</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7C1B355F83A55285">11.3-8 ShadedSetOfElementInAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X81CA53DA8216DC82">11.3-9 IsGeneric</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X79EC6F7583B0CBDD">11.3-10 IsUniquelyPresented</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7DCAFC5F7F74F3CB">11.3-11 DegreesOfPrimitiveElementsOfAffineSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11_mj.html#X80A934B0826E21A6">11.4 <span class="Heading">
Factorizations in affine semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X8780C7E5830B9AE2">11.4-1 FactorizationsVectorWRTList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X820A0D06857C4EF5">11.4-2 Factorizations</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7F394FA67BE5151B">11.4-3 Elasticity</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X819CDBAA84DB7E83">11.4-4 Elasticity</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X839549448300AD26">11.4-5 DeltaSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X80742F2F7DECDB4C">11.4-6 CatenaryDegree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7EADD306875FCBE6">11.4-7 EqualCatenaryDegreeOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X84FE571A7E9E1AE9">11.4-8 HomogeneousCatenaryDegreeOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X8510C1527F2FE18E">11.4-9 MonotoneCatenaryDegreeOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X8457595E7AA542E6">11.4-10 TameDegree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X850790EE8442FD7D">11.4-11 OmegaPrimality</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7A3571E187D0FCDE">11.4-12 OmegaPrimality</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap11_mj.html#X849D1ECC808F2BBA">11.5 <span class="Heading">
Finitely generated ideals of affine semigroups
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X85775D4E7B9C7DAB">11.5-1 IdealOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X82A647B27FDFE49B">11.5-2 IsIdealOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7F16A5A27CBB7B93">11.5-3 MinimalGenerators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X8086C1EE7EAAB33D">11.5-4 Generators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X82D18D7B877582B0">11.5-5 AmbientAffineSemigroupOfIdeal</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7B0FBEC285F54B8D">11.5-6 IsIntegral</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7F00912C853AA83D">11.5-7 BelongsToIdealOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X83A4392281981911">11.5-8 SumIdealsOfAffinSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7D056A0C7F868209">11.5-9 MultipleOfIdealOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X788264A27ACD6AB5">11.5-10 TranslationOfIdealOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7880F29982B559F2">11.5-11 UnionIdealsOfAffineSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X7ED03363783D8FCD">11.5-12 Intersection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap11_mj.html#X79ECACE4793A6B00">11.5-13 MaximalIdeal</a></span>
</div></div>
</div>
<h3>11 <span class="Heading">
Affine semigroups
</span></h3>
<p>An <em>affine semigroup</em> <span class="SimpleMath">\(S\)</span> is a finitely generated cancellative monoid that is reduced (no units other than 0) and is torsion-free (<span class="SimpleMath">\( a s= b s\)</span> implies <span class="SimpleMath">\(a=b\)</span>, with <span class="SimpleMath">\(a,b\in \mathbb N\)</span> and <span class="SimpleMath">\(s\in S\)</span>). Up to isomorphism any affine semigroup can be viewed as a finitely generated submonoid of <span class="SimpleMath">\(\mathbb N^k\)</span> for some positive integer <span class="SimpleMath">\(k\)</span>. Thus affine semigroups are a natural generalization of numerical semigroups.</p>
<p>Some of the functions in this chapter may work considerably faster when some external package is installed and its use is allowed. When this is the case, it is referred in the function documentation. We refer the user to Chapter <a href="chap13_mj.html#X84A2793F7A9F3E6A"><span class="RefLink">13</span></a> for details on the use of external packages.</p>
<p><a id="X7E39DA7780D02DF5" name="X7E39DA7780D02DF5"></a></p>
<h4>11.1 <span class="Heading">
Defining affine semigroups
</span></h4>
<p>The most common way to give an affine semigroup is by any of its systems of generators. As for numerical semigroups, any affine semigroup admits a unique minimal system of generators. A system of generators can be represented as a list of lists of nonnegative integers; all lists in the list having the same length (a matrix actually). If <span class="SimpleMath">\(G\)</span> is a subgroup of <span class="SimpleMath">\(\mathbb Z^k\)</span>, then <span class="SimpleMath">\(S=G\cap \mathbb N^k\)</span> is an affine semigroup (these semigroups are called <em>full affine semigroups</em>). As <span class="SimpleMath">\(G\)</span> can be represented by its defining equations (homogeneous and some of them possibly in congruences), we can represent <span class="SimpleMath">\(S\)</span> by the defining equations of <span class="SimpleMath">\(G\)</span>; indeed <span class="SimpleMath">\(S\)</span> is just the set of nonnegative solutions of this system of equations. We can represent the equations as a list of lists of integers, all with the same length. Every list is a row of the matrix of coefficients of the system of equations. For the equations in congruences, if we arrange them so that they are the first ones in the list, we provide the corresponding moduli in a list. So for instance, the equations <span class="SimpleMath">\(x+y\equiv 0\bmod 2,\ x-2y=0\)</span> will be represented as [[1,1],[1,-2]] and the moduli [2].</p>
<p>As happens with numerical semigroups, there are different ways to specify an affine semigroup <span class="SimpleMath">\(S\)</span>, namely, by means of a system of generators, a system of homogeneous linear Diophantine equations or a system of homogeneous linear Diophantine inequalities, just to mention some. In this section we describe functions that may be used to specify, in one of these ways, an affine semigroup in <strong class="pkg">GAP</strong>.</p>
<p><a id="X7D7B03E17C8DBEA2" name="X7D7B03E17C8DBEA2"></a></p>
<h5>11.1-1 AffineSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AffineSemigroup</code>( [<var class="Arg">String</var>, ]<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">‣ AffineSemigroupByGenerators</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">List</code> is a list of n-tuples of nonnegative integers, if the semigroup to be created is n-dimensional. The n-tuples may be given as a list or by a sequence of individual elements. The output is the affine semigroup spanned by <code class="code">List</code>.</p>
<p><code class="code">String</code> does not need to be present. When it is present, it must be <code class="code">"generators"</code> and <code class="code">List</code> must be a list, not a sequence of individual elements.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s1 := AffineSemigroup([1,3],[7,2],[1,5]);</span>
<Affine semigroup in 2 dimensional space, with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">s2 := AffineSemigroup([[1,3],[7,2],[1,5]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s3 := AffineSemigroupByGenerators([1,3],[7,2],[1,5]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s4 := AffineSemigroupByGenerators([[1,3],[7,2],[1,5]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s5 := AffineSemigroup("generators",[[1,3],[7,2],[1,5]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(Set([s1,s2,s3,s4,s5]));</span>
1
</pre></div>
<p><a id="X855C8667830AEDDC" name="X855C8667830AEDDC"></a></p>
<h5>11.1-2 AffineSemigroupByEquations</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AffineSemigroupByEquations</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">‣ AffineSemigroup</code>( <var class="Arg">String</var>, <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">List</code> is a list with two components. The first represents a matrix with integer coefficients, say <span class="SimpleMath">\(A=(a_{ij})\)</span>, and so it is a list of lists of integers all with the same length. The second component is a list of positive integers, say <span class="SimpleMath">\(d=(d_i)\)</span>, which may be empty. The list <span class="SimpleMath">\(d\)</span> must be of length less than or equal to the length of <span class="SimpleMath">\(A\)</span> (number of rows of <span class="SimpleMath">\(A\)</span>).</p>
<p>The output is the full semigroup of nonnegative integer solutions to the system of homogeneous equations <br /> <span class="SimpleMath">\(a_{11}x_1+\cdots+a_{1n}x_n\equiv 0\bmod d_1, \)</span><br /> <span class="SimpleMath">\(\cdots \)</span><br /> <span class="SimpleMath">\(a_{k1}x_1+\cdots+a_{kn}x_n\equiv 0\bmod d_k, \)</span><br /> <span class="SimpleMath">\(a_{k+1\, 1}x_1+\cdots +a_{k+1\, n}=0, \)</span><br /> <span class="SimpleMath">\(\cdots \)</span><br /> <span class="SimpleMath">\(a_{m1}x_1+\cdots+a_{mn}x_n=0. \)</span><br /></p>
<p>If <span class="SimpleMath">\(d\)</span> is empty, then there will be no equations in congruences.</p>
<p>As pointed at the beginning of the section, the equations <span class="SimpleMath">\(x+y\equiv 0\bmod 2,\ x-2y=0\)</span> will be represented as <span class="SimpleMath">\(A\)</span> equal to [[1,1],[1,-2]] and the moduli <span class="SimpleMath">\(d\)</span> equal to [2].</p>
<p>In the second form, <code class="code">String</code> must be <code class="code">"equations"</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s1 := AffineSemigroup("equations",[[[1,1]],[3]]);</span>
<Affine semigroup>
<span class="GAPprompt">gap></span> <span class="GAPinput">s2 := AffineSemigroupByEquations([[[-2,1]],[3]]);</span>
<Affine semigroup>
<span class="GAPprompt">gap></span> <span class="GAPinput">s1=s2;</span>
true
</pre></div>
<p><a id="X7846AD1081C14EF1" name="X7846AD1081C14EF1"></a></p>
<h5>11.1-3 AffineSemigroupByInequalities</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AffineSemigroupByInequalities</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">‣ AffineSemigroup</code>( <var class="Arg">String</var>, <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">List</code> is a list of lists (a matrix) of integers that represents a set of inequalities.</p>
<p>Returns the (normal) affine semigroup of nonegative integer solutions of the system of inequalities <span class="SimpleMath">\(List\times X\ge 0\)</span>.</p>
<p>In the second form, <code class="code">String</code> must be <code class="code">"inequalities"</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1:=AffineSemigroup("inequalities",[[2,-1],[-1,3]]);</span>
<Affine semigroup>
<span class="GAPprompt">gap></span> <span class="GAPinput">a2:=AffineSemigroupByInequalities([[2,-1],[-1,3]]);</span>
<Affine semigroup>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1=a2;</span>
true
</pre></div>
<p><a id="X7CC110D4798AAD99" name="X7CC110D4798AAD99"></a></p>
<h5>11.1-4 AffineSemigroupByPMInequality</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AffineSemigroupByPMInequality</code>( <var class="Arg">f</var>, <var class="Arg">b</var>, <var class="Arg">g</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">‣ AffineSemigroup</code>( <var class="Arg">String</var>, <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">f</var>, <var class="Arg">g</var> are lists of integers and <var class="Arg">b</var> is a positive integer.</p>
<p>Returns the proportionally modular affine semigroup defined by the <span class="SimpleMath">\(f\times X \pmod{b} \leq g\times X\)</span></p>
<p>In the second form, <code class="code">String</code> must be <code class="code">"pminequality"</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=AffineSemigroupByPMInequality([0, 1, 1, 0, -1], 4, [1, 0, -2, -3, 1]); </span>
<Affine semigroup>
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 3, 0, 0, 4, 12 ] in s;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">[ 3, 0, 0, 4, 1 ] in s;</span>
false
</pre></div>
<p><a id="X83F6DDB787E07771" name="X83F6DDB787E07771"></a></p>
<h5>11.1-5 AffineSemigroupByGaps</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AffineSemigroupByGaps</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">‣ AffineSemigroup</code>( [<var class="Arg">String</var>, ]<var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In the second form, <code class="code">String</code> must be <code class="code">"gaps"</code> and <code class="code">List</code> must be a list, not a sequence of individual elements.</p>
<p>In the first form, <code class="code">List</code> is a list of n-tuples of nonnegative integers, if the semigroup to be created is n-dimensional. The n-tuples may be given as a list or by a sequence of individual elements. The output is the affine semigroup with gaps <code class="code">List</code>. If the given set is not a set of gaps of a numerical semigroup, then the function raises an error.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gaps := [[1,0,0,0],[1,1,0,0],[2,0,0,0],[2,1,0,0],[5,0,0,0]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1 := AffineSemigroup("gaps", gaps );</span>
<Affine semigroup>
<span class="GAPprompt">gap></span> <span class="GAPinput">a2 := AffineSemigroupByGaps( gaps );</span>
<Affine semigroup>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1 = a2;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Generators(a1);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Set(last);</span>
[ [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 0, 1 ],
[ 1, 0, 1, 0 ], [ 1, 2, 0, 0 ], [ 2, 0, 0, 1 ], [ 2, 0, 1, 0 ],
[ 2, 2, 0, 0 ], [ 3, 0, 0, 0 ], [ 4, 0, 0, 0 ], [ 5, 1, 0, 0 ] ]
</pre></div>
<p><a id="X7A3648D67CF81370" name="X7A3648D67CF81370"></a></p>
<h5>11.1-6 FiniteComplementIdealExtension</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FiniteComplementIdealExtension</code>( <var class="Arg">List</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">List</var> is a list or sequence of <span class="SimpleMath">\(n\)</span>-tuples of nonnegative integers. If the monoid <span class="SimpleMath">\(M=\{0\}\cup (\mathtt{List}+\mathbb{N}^n)\)</span> is an affine semigroup (equivalently, <span class="SimpleMath">\(M\)</span> has finitely many gaps), then the output is <span class="SimpleMath">\(M\)</span>. Otherwise, an error is raised.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=FiniteComplementIdealExtension([[0,2],[1,1],[3,0]]);</span>
<Affine semigroup>
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalGenerators(s);</span>
[ [ 0, 3 ], [ 1, 1 ], [ 0, 2 ], [ 3, 0 ], [ 2, 1 ], [ 1, 2 ], [ 3, 1 ], [ 5, 0 ], [ 4, 0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=FiniteComplementIdealExtension([0,2],[1,1],[3,0]);</span>
<Affine semigroup>
</pre></div>
<p><a id="X8361194C86AE807B" name="X8361194C86AE807B"></a></p>
<h5>11.1-7 Gaps</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Gaps</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><var class="Arg">S</var> is an affine semigroup, the output is its set of gaps, if this set has finitely many elements. Otherwise the output is 'fail' and a warning is raised. The procedure is inspired in <a href="chapBib_mj.html#biBC-F-U">[CFR18]</a></p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup([[1,0,0,0],[3,1,0,0],[1,2,0,0],[0,0,1,0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[0,2,1,0],[0,1,1,0],[0,0,0,1],[0,2,0,1],[0,1,0,1],[0,3,0,0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[0,5,0,0],[0,4,0,0]]);</span>
<Affine semigroup in 4 dimensional space, with 12 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Set(Gaps(a));</span>
[ [ 0, 1, 0, 0 ], [ 0, 2, 0, 0 ], [ 1, 1, 0, 0 ], [ 2, 1, 0, 0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">n := AffineSemigroup([1,1],[0,1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gaps(n);</span>
#I The given affine semigroup has infinitely many gaps
fail
</pre></div>
<p><a id="X867B27BD81104BEE" name="X867B27BD81104BEE"></a></p>
<h5>11.1-8 Genus</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Genus</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><var class="Arg">S</var> is an affine semigroup, the output is the cardinality of its set of gaps, if this set is finite. Otherwise the output is 'infinite'. The procedure is inspired in <a href="chapBib_mj.html#biBC-F-U">[CFR18]</a></p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup([[1,0,0,0],[3,1,0,0],[1,2,0,0],[0,0,1,0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[0,2,1,0],[0,1,1,0],[0,0,0,1],[0,2,0,1],[0,1,0,1],[0,3,0,0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[0,5,0,0]]);</span>
<Affine semigroup in 4 dimensional space, with 11 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Genus(a);</span>
7
<span class="GAPprompt">gap></span> <span class="GAPinput">n := AffineSemigroup([1,1],[0,1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Genus(n);</span>
#I The given affine semigroup has infinitely many gaps
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">last > 10^50;</span>
true
</pre></div>
<p><a id="X80C3CD2082CE02F7" name="X80C3CD2082CE02F7"></a></p>
<h5>11.1-9 PseudoFrobenius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PseudoFrobenius</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><var class="Arg">S</var> is an affine semigroup, the output is its set of pseudo-Frobenius vectors, that is, the gaps <span class="SimpleMath">\(g\)</span> of <var class="Arg">S</var> such that for every nonzero element <span class="SimpleMath">\(s\)</span> of <var class="Arg">S</var>, the vector <span class="SimpleMath">\(g+s\)</span> is in <var class="Arg">S</var>. The package will only find pseudo-Frobenius vectors for affine semigroups with a finite set of gaps.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup([[1,0,0,0],[3,1,0,0],[1,2,0,0],[0,0,1,0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[0,2,1,0],[0,1,1,0],[0,0,0,1],[0,2,0,1],[0,1,0,1],[0,3,0,0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[0,5,0,0],[0,4,0,0]]);</span>
<Affine semigroup in 4 dimensional space, with 12 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">PseudoFrobenius(a);</span>
[ [ 0, 2, 0, 0 ], [ 2, 1, 0, 0 ] ]
</pre></div>
<p><a id="X82D42FCE81F20277" name="X82D42FCE81F20277"></a></p>
<h5>11.1-10 SpecialGaps</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SpecialGaps</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><var class="Arg">S</var> is an affine semigroup, the output is its set of special gaps of <var class="Arg">S</var>, that is, the gaps <span class="SimpleMath">\(g\)</span> of <var class="Arg">S</var> such that <span class="SimpleMath">\(\textit{S}\cup\{g\}\)</span> is a semigroup. Special gaps can only be computed in the package for affine semigroups with finitely many gaps.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup([[1,0,0,0],[3,1,0,0],[1,2,0,0],[0,0,1,0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[0,2,1,0],[0,1,1,0],[0,0,0,1],[0,2,0,1],[0,1,0,1],[0,3,0,0],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[0,5,0,0],[0,4,0,0]]);</span>
<Affine semigroup in 4 dimensional space, with 12 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">SpecialGaps(a);</span>
[ [ 0, 2, 0, 0 ], [ 2, 1, 0, 0 ] ]
</pre></div>
<p><a id="X84FDF85D7CDEDF3E" name="X84FDF85D7CDEDF3E"></a></p>
<h5>11.1-11 Generators</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Generators</code>( <var class="Arg">S</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">‣ GeneratorsOfAffineSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">S</var> is an affine semigroup, the output is a system of generators.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup([[1,0],[0,1],[1,1]]);</span>
<Affine semigroup in 2 dimensional space, with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Generators(a);</span>
[ [ 0, 1 ], [ 1, 0 ], [ 1, 1 ] ]
</pre></div>
<p><a id="X7ED1549486C251CA" name="X7ED1549486C251CA"></a></p>
<h5>11.1-12 MinimalGenerators</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalGenerators</code>( <var class="Arg">S</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">‣ MinimalGeneratingSystem</code>( <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">S</var> is an affine semigroup, the output is its system of minimal generators.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup([[1,0],[0,1],[1,1]]);</span>
<Affine semigroup in 2 dimensional space, with 3 generators>
gap> MinimalGenerators(a);
[ [ 0, 1 ], [ 1, 0 ] ]
</pre></div>
<p><a id="X80516BCC78FDD45D" name="X80516BCC78FDD45D"></a></p>
<h5>11.1-13 RemoveMinimalGeneratorFromAffineSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RemoveMinimalGeneratorFromAffineSemigroup</code>( <var class="Arg">n</var>, <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">S</var> is an affine semigroup and <var class="Arg">n</var> is one if its minimal generators.</p>
<p>The output is the affine semigroup <span class="SimpleMath">\( \textit{S} \setminus\{\textit{n}\} \)</span> (<span class="SimpleMath">\(S\setminus\{n\}\)</span> is an affine semigroup if and only if <span class="SimpleMath">\(n\)</span> is a minimal generator of <span class="SimpleMath">\(S\)</span>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup([2,0],[0,4]);</span>
<Affine semigroup in 2 dimensional space, with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=RemoveMinimalGeneratorFromAffineSemigroup([2,0],a);Generators(b);</span>
<Affine semigroup in 2 dimensional space, with 4 generators>
[ [ 0, 4 ], [ 2, 4 ], [ 4, 0 ], [ 6, 0 ] ]</pre></div>
<p><a id="X7B78E02F7C50583F" name="X7B78E02F7C50583F"></a></p>
<h5>11.1-14 AddSpecialGapOfAffineSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AddSpecialGapOfAffineSemigroup</code>( <var class="Arg">g</var>, <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">S</var> is an semigroup and <var class="Arg">g</var> is a special gap of <var class="Arg">S</var>.</p>
<p>The output is the numerical semigroup <span class="SimpleMath">\( \textit{S} \cup\{\textit{g}\} \)</span> (see <a href="chapBib_mj.html#biBRGGJ03">[RGGJ03]</a>, where it is explained why this set is a numerical semigroup).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=AffineSemigroup([[2,0],[3,0],[0,4],[0,5],[1,1]]);</span>
<Affine semigroup in 2 dimensional space, with 5 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">t:=AddSpecialGapOfAffineSemigroup([1,12],s);</span>
<Affine semigroup in 2 dimensional space, with 6 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gaps(s);</span>
[ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 6 ], [ 0, 7 ], [ 0, 11 ], [ 1, 0 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ],
[ 1, 7 ], [ 1, 8 ], [ 1, 12 ], [ 2, 1 ], [ 2, 3 ], [ 3, 2 ], [ 4, 3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Gaps(t);</span>
[ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 6 ], [ 0, 7 ], [ 0, 11 ], [ 1, 0 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ],
[ 1, 7 ], [ 1, 8 ], [ 2, 1 ], [ 2, 3 ], [ 3, 2 ], [ 4, 3 ] ]</pre></div>
<p><a id="X844806D97B4781B5" name="X844806D97B4781B5"></a></p>
<h5>11.1-15 AsAffineSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsAffineSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">S</var> is a numerical semigroup, the output is <var class="Arg">S</var> regarded as an affine semigroup.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=NumericalSemigroup(1310,1411,1546,1601);</span>
<Numerical semigroup with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalPresentationOfNumericalSemigroup(s);;time;</span>
2960
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AsAffineSemigroup(s);</span>
<Affine semigroup in 1 dimensional space, with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfAffineSemigroup(a);</span>
[ [ 1310 ], [ 1411 ], [ 1546 ], [ 1601 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalPresentationOfAffineSemigroup(a);;time;</span>
237972
</pre></div>
<p>If we use the package <code class="code">SingularInterface</code>, the speed up is considerable.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NumSgpsUseSingularInterface();</span>
...
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalPresentationOfAffineSemigroup(a);;time;</span>
32
</pre></div>
<p><a id="X7A2902207BAA3936" name="X7A2902207BAA3936"></a></p>
<h5>11.1-16 IsAffineSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsAffineSemigroup</code>( <var class="Arg">AS</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">‣ IsAffineSemigroupByGenerators</code>( <var class="Arg">AS</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">‣ IsAffineSemigroupByEquations</code>( <var class="Arg">AS</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">‣ IsAffineSemigroupByInequalities</code>( <var class="Arg">AS</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><var class="Arg">AS</var> is an affine semigroup and these attributes are available (their names should be self explanatory). They reflect what is currently known about the semigroup.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1:=AffineSemigroup([[3,0],[2,1],[1,2],[0,3]]);</span>
<Affine semigroup in 2 dimensional space, with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAffineSemigroupByEquations(a1);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAffineSemigroupByGenerators(a1);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ns := NumericalSemigroup(3,5);</span>
<Numerical semigroup with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAffineSemigroup(ns);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">as := AsAffineSemigroup(ns);</span>
<Affine semigroup in 1 dimensional space, with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsAffineSemigroup(as);</span>
true
</pre></div>
<p><a id="X851788D781A13C50" name="X851788D781A13C50"></a></p>
<h5>11.1-17 BelongsToAffineSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BelongsToAffineSemigroup</code>( <var class="Arg">v</var>, <var class="Arg">a</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">‣ \in</code>( <var class="Arg">v</var>, <var class="Arg">a</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">v</var> is a list of nonnegative integers and <var class="Arg">a</var> an affine semigroup. Returns true if the vector is in the semigroup, and false otherwise.</p>
<p>If the semigroup is full and its equations are known (either because the semigroup was defined by equations, or because the user has called <code class="code">IsFullAffineSemgiroup(a)</code> and the output was true), then membership is performed by evaluating <var class="Arg">v</var> in the equations. The same holds for normal semigroups and its defining inequalities. If the set of gaps is finite and known, then membership is just checking that <var class="Arg">v</var> has nonnegative integers and it is not in the set of gaps.</p>
<p><var class="Arg"> v in a</var> can be used for short.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup([[2,0],[0,2],[1,1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">BelongsToAffineSemigroup([5,5],a);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">BelongsToAffineSemigroup([1,2],a);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">[5,5] in a;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">[1,2] in a;</span>
false
</pre></div>
<p><a id="X8607B621833FAECB" name="X8607B621833FAECB"></a></p>
<h5>11.1-18 IsFull</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFull</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsFullAffineSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><var class="Arg">S</var> is an affine semigroup.</p>
<p>Returns true if the semigroup is full, false otherwise. The semigroup is full if whenever <span class="SimpleMath">\(a,b\in S\)</span> and <span class="SimpleMath">\(b-a\in \mathbb N^k\)</span>, then <span class="SimpleMath">\(a-b\in S\)</span>, where <span class="SimpleMath">\(k\)</span> is the dimension of <span class="SimpleMath">\(S\)</span>.</p>
<p>If the semigroup is full, then its equations are stored in the semigroup for further use.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=AffineSemigroup("equations",[[[1,1,1],[0,0,2]],[2,2]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFull(a);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFullAffineSemigroup(a);</span>
true
</pre></div>
<p><a id="X7D4D017A79AD98E2" name="X7D4D017A79AD98E2"></a></p>
<h5>11.1-19 HilbertBasisOfSystemOfHomogeneousEquations</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HilbertBasisOfSystemOfHomogeneousEquations</code>( <var class="Arg">ls</var>, <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">ls</var> is a list of lists of integers and <var class="Arg">m</var> a list of integers. The elements of <var class="Arg">ls</var> represent the rows of a matrix <span class="SimpleMath">\(A\)</span>. The output is a minimal generating system (Hilbert basis) of the set of nonnegative integer solutions of the system <span class="SimpleMath">\(Ax=0\)</span> where the <span class="SimpleMath">\(k\)</span> first equations are in the congruences modulo <var class="Arg">m[i]</var>, with <span class="SimpleMath">\(k\)</span> the length of <var class="Arg">m</var>.</p>
<p>If the package <code class="code">NormalizInterface</code> has not been loaded, then Contejean-Devie algorithm is used <a href="chapBib_mj.html#biBMR1283022">[CD94]</a> instead (if this is the case, congruences are treated as in <a href="chapBib_mj.html#biBR-GS">[RG98]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">HilbertBasisOfSystemOfHomogeneousEquations([[1,0,1],[0,1,-1]],[2]);</span>
[ [ 0, 2, 2 ], [ 1, 1, 1 ], [ 2, 0, 0 ] ]
</pre></div>
<p>If <span class="SimpleMath">\(C\)</span> is a pointed cone (a cone in <span class="SimpleMath">\(\mathbb Q^k\)</span> not containing lines and <span class="SimpleMath">\(0\in C\)</span>), then <span class="SimpleMath">\(S=C\cap \mathbb N^k\)</span> is an affine semigroup (known as normal affine semigroup). So another way to give an affine semigroup is by a set of homogeneous inequalities, and we can represent these inequalities by its coefficients. If we put them in a matrix <span class="SimpleMath">\(S\)</span> can be defined as the set of nonnegative integer solutions to <span class="SimpleMath">\(Ax \ge 0\)</span>.</p>
<p><a id="X825B1CD37B0407A6" name="X825B1CD37B0407A6"></a></p>
<h5>11.1-20 HilbertBasisOfSystemOfHomogeneousInequalities</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HilbertBasisOfSystemOfHomogeneousInequalities</code>( <var class="Arg">ls</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">ls</var> is a list of lists of integers. The elements of <var class="Arg">ls</var> represent the rows of a matrix <span class="SimpleMath">\(A\)</span>. The output is a minimal generating system (Hilbert basis) of the set of nonnegative integer solutions to <span class="SimpleMath">\(Ax\ge 0\)</span>.</p>
<p>If the package <code class="code">NormalizInterface</code> has not been loaded, then Contejean-Devie algorithm is used <a href="chapBib_mj.html#biBMR1283022">[CD94]</a> instead (the use of slack variables is described in <a href="chapBib_mj.html#biBR-GS-GG-B">[CAGB02]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">HilbertBasisOfSystemOfHomogeneousInequalities([[2,-3],[0,1]]);</span>
[ [ 1, 0 ], [ 2, 1 ], [ 3, 2 ] ]
</pre></div>
<p><a id="X8307A0597864B098" name="X8307A0597864B098"></a></p>
<h5>11.1-21 EquationsOfGroupGeneratedBy</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EquationsOfGroupGeneratedBy</code>( <var class="Arg">M</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">M</var> is a matrix of integers. The output is a pair <span class="SimpleMath">\([A,m]\)</span> that represents the set of defining equations of the group spanned by the rows of <var class="Arg">M</var>: <span class="SimpleMath">\(Ax=0\in \mathbb Z_{n_1}\times \cdots \times \mathbb Z_{n_t}\times \mathbb Z^k\)</span>, with <span class="SimpleMath">\(m=[n_1,\ldots,n_t]\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">EquationsOfGroupGeneratedBy([[1,2,0],[2,-2,2]]);</span>
[ [ [ 0, 0, -1 ], [ -2, 1, 3 ] ], [ 2 ] ]
</pre></div>
<p><a id="X7A1CE5A98425CEA1" name="X7A1CE5A98425CEA1"></a></p>
<h5>11.1-22 BasisOfGroupGivenByEquations</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BasisOfGroupGivenByEquations</code>( <var class="Arg">A</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">A</var> is a matrix of integers and <var class="Arg">m</var> is a list of positive integers. The output is a basis for the group with defining equations <span class="SimpleMath">\(Ax=0\in \mathbb Z_{n_1}\times \cdots \times \mathbb Z_{n_t}\times \mathbb Z^k\)</span>, with <span class="SimpleMath">\(m=[n_1,\ldots,n_t]\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">BasisOfGroupGivenByEquations([[0,0,1],[2,-1,-3]],[2]);</span>
[ [ -1, -2, 0 ], [ -2, 2, -2 ] ]
</pre></div>
<p><a id="X7F13DF9D7A4FB547" name="X7F13DF9D7A4FB547"></a></p>
<h4>11.2 <span class="Heading">
Gluings of affine semigroups
</span></h4>
<p>Let <span class="SimpleMath">\(S_1\)</span> and <span class="SimpleMath">\(S_2\)</span> be two affine semigroups with the same dimension generated by <span class="SimpleMath">\(A_1\)</span> and <span class="SimpleMath">\(A_2\)</span>, respectively. We say that the affine semigroup <span class="SimpleMath">\(S\)</span> generated by the union of <span class="SimpleMath">\(A_1\)</span> and <span class="SimpleMath">\(A_2\)</span> is a gluing of <span class="SimpleMath">\(S_1\)</span> and <span class="SimpleMath">\(S_2\)</span> if <span class="SimpleMath">\(G(S_1)\cap G(S_2)=d\mathbb Z\)</span> (<span class="SimpleMath">\(G(\cdot)\)</span> stands for group spanned by) for some <span class="SimpleMath">\(d\in S_1\cap S_2\)</span>.</p>
<p>The algorithm used is explained in <a href="chapBib_mj.html#biBMR1678508">[RG99a]</a>.</p>
<p><a id="X7FE3B3C380641DDC" name="X7FE3B3C380641DDC"></a></p>
<h5>11.2-1 GluingOfAffineSemigroups</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GluingOfAffineSemigroups</code>( <var class="Arg">a1</var>, <var class="Arg">a2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">a1, a2</var> are affine semigroups. Determines if they can be glued, and if so, returns the gluing. Otherwise it returns fail.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1:=AffineSemigroup([[2,0],[0,2]]);</span>
<Affine semigroup in 2 dimensional space, with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">a2:=AffineSemigroup([[1,1]]);</span>
<Affine semigroup in 2 dimensional space, with 1 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">GluingOfAffineSemigroups(a1,a2);</span>
<Affine semigroup in 2 dimensional space, with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Generators(last);</span>
[ [ 0, 2 ], [ 1, 1 ], [ 2, 0 ] ]
</pre></div>
<p><a id="X86A1018D7CB7BA81" name="X86A1018D7CB7BA81"></a></p>
<h4>11.3 <span class="Heading">
Presentations of affine semigroups
</span></h4>
<p>A <em>minimal presentation</em> of an affine semigroup is defined analogously as for numerical semigroups (see Chapter <a href="chap4_mj.html#X7969F7F27AAF0BF1"><span class="RefLink">4</span></a>). We warn the user to take into account that minimal generators are stored in a set, and thus might be arranged in a different way to the initial input. If a presentation is needed with a certain arrangment in the set of generators, or some of the generators are not necessarily minimal, then <code class="func">GeneratorsOfKernelCongruence</code> (<a href="chap11_mj.html#X7EE005267DEBC1DE"><span class="RefLink">11.3-3</span></a>) is recommended.</p>
<p><a id="X795EEE4481E0497C" name="X795EEE4481E0497C"></a></p>
<h5>11.3-1 CircuitsOfKernelCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CircuitsOfKernelCongruence</code>( <var class="Arg">M</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">M</var> is matrix with nonnegative integer coefficients. The output is the set of circuits (pairs with minimal support) of the congruence <span class="SimpleMath">\(\{(x,y)\mid x\textit{M}=y\textit{M}\}\)</span>. The computation is performed by using Lemma 8.8 in <a href="chapBib_mj.html#biBMR1394747">[ES96]</a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">s:=NumericalSemigroup(4,6,9);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">CircuitsOfKernelCongruence([[4],[6],[9]]);</span>
[ [ [ 3, 0, 0 ], [ 0, 2, 0 ] ], [ [ 9, 0, 0 ], [ 0, 0, 4 ] ], [ [ 0, 3, 0 ], [ 0, 0, 2 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalPresentation(s);</span>
[ [ [ 0, 0, 2 ], [ 0, 3, 0 ] ], [ [ 0, 2, 0 ], [ 3, 0, 0 ] ] ]
</pre></div>
<p><a id="X78B04C198258D3F8" name="X78B04C198258D3F8"></a></p>
<h5>11.3-2 PrimitiveRelationsOfKernelCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrimitiveRelationsOfKernelCongruence</code>( <var class="Arg">M</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">M</var> is matrix with nonnegative integer coefficients. The output is the set of primitive relations of the congruence <span class="SimpleMath">\(R=\{(x,y)\mid x\textit{M}=y\textit{M}\}\)</span>. A pair (relation) <span class="SimpleMath">\((x,y)\)</span> in <span class="SimpleMath">\(R\)</span> is primitive if <span class="SimpleMath">\(x\neq y\)</span> and it cannot be expressed as a sumo of two nonzero pairs in <span class="SimpleMath">\(R\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrimitiveRelationsOfKernelCongruence([[4],[6],[9]]);</span>
[ [ [ 0, 0, 2 ], [ 0, 3, 0 ] ], [ [ 0, 0, 2 ], [ 3, 1, 0 ] ],
[ [ 0, 0, 4 ], [ 9, 0, 0 ] ], [ [ 0, 1, 2 ], [ 6, 0, 0 ] ],
[ [ 0, 2, 0 ], [ 3, 0, 0 ] ] ]
</pre></div>
<p><a id="X7EE005267DEBC1DE" name="X7EE005267DEBC1DE"></a></p>
<h5>11.3-3 GeneratorsOfKernelCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfKernelCongruence</code>( <var class="Arg">M</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">M</var> is matrix with nonnegative integer coefficients. The output is a system of generators of the congruence <span class="SimpleMath">\(\{(x,y)\mid x\textit{M}=y\textit{M}\}\)</span>.</p>
<p>The main difference with <code class="func">MinimalPresentationOfAffineSemigroup</code> (<a href="chap11_mj.html#X80A7BD7478D8A94A"><span class="RefLink">11.3-6</span></a>) is that the matrix <var class="Arg">M</var> can have repeated rows and these are not treated as a set.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M := [[2,0],[0,2],[1,1]];</span>
[ [ 2, 0 ], [ 0, 2 ], [ 1, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfKernelCongruence(M);</span>
[ [ [ 0, 0, 2 ], [ 1, 1, 0 ] ] ]
</pre></div>
<p><a id="X7AD2271E84F705D3" name="X7AD2271E84F705D3"></a></p>
<h5>11.3-4 CanonicalBasisOfKernelCongruence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CanonicalBasisOfKernelCongruence</code>( <var class="Arg">M</var>, <var class="Arg">Ord</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">M</var> is matrix with nonnegative integer coefficients, <var class="Arg">Ord</var> a term ordering. The output is a canonical basis of the congruence <span class="SimpleMath">\(\{(x,y)\mid x\textit{M}=y\textit{M}\}\)</span> (see <a href="chapBib_mj.html#biBRGS99">[RG99b]</a>). This corresponds with the exponents of the Gröbner basis of the kernel ideal of the morphism <span class="SimpleMath">\(x_i\mapsto Y^{m_i}\)</span>, with <span class="SimpleMath">\(m_i\)</span> the <span class="SimpleMath">\(i\)</span>th row of <span class="SimpleMath">\(M\)</span>.</p>
<p>Accepted term orderings are lexicographic (<code class="code">MonomialLexOrdering()</code>), graded lexicographic (<var class="Arg">MonomialGrlexOrdering()</var>) and reversed graded lexicographic (<var class="Arg">MonomialGrevlexOrdering()</var>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">M:=[[3],[5],[7]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">CanonicalBasisOfKernelCongruence(M,MonomialLexOrdering());</span>
[ [ [ 0, 7, 0 ], [ 0, 0, 5 ] ], [ [ 1, 0, 1 ], [ 0, 2, 0 ] ],
[ [ 1, 5, 0 ], [ 0, 0, 4 ] ], [ [ 2, 3, 0 ], [ 0, 0, 3 ] ],
[ [ 3, 1, 0 ], [ 0, 0, 2 ] ], [ [ 4, 0, 0 ], [ 0, 1, 1 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">CanonicalBasisOfKernelCongruence(M,MonomialGrlexOrdering());</span>
[ [ [ 0, 7, 0 ], [ 0, 0, 5 ] ], [ [ 1, 0, 1 ], [ 0, 2, 0 ] ],
[ [ 1, 5, 0 ], [ 0, 0, 4 ] ], [ [ 2, 3, 0 ], [ 0, 0, 3 ] ],
[ [ 3, 1, 0 ], [ 0, 0, 2 ] ], [ [ 4, 0, 0 ], [ 0, 1, 1 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">CanonicalBasisOfKernelCongruence(M,MonomialGrevlexOrdering());</span>
[ [ [ 0, 2, 0 ], [ 1, 0, 1 ] ], [ [ 3, 1, 0 ], [ 0, 0, 2 ] ],
[ [ 4, 0, 0 ], [ 0, 1, 1 ] ] ]
</pre></div>
<p><a id="X7C3546477E07A1EA" name="X7C3546477E07A1EA"></a></p>
<h5>11.3-5 GraverBasis</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraverBasis</code>( <var class="Arg">M</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">M</var> is matrix with integer coefficients. The output is a Graver basis for <var class="Arg">M</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gr:=GraverBasis([[3,5,7]]);</span>
[ [ -7, 0, 3 ], [ -5, 3, 0 ], [ -4, 1, 1 ], [ -3, -1, 2 ], [ -2, -3, 3 ],
[ -1, -5, 4 ], [ -1, 2, -1 ], [ 0, -7, 5 ], [ 0, 7, -5 ], [ 1, -2, 1 ],
[ 1, 5, -4 ], [ 2, 3, -3 ], [ 3, 1, -2 ], [ 4, -1, -1 ], [ 5, -3, 0 ],
[ 7, 0, -3 ] ]
</pre></div>
<p><a id="X80A7BD7478D8A94A" name="X80A7BD7478D8A94A"></a></p>
<h5>11.3-6 MinimalPresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalPresentation</code>( <var class="Arg">a</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalPresentationOfAffineSemigroup</code>( <var class="Arg">a</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><var class="Arg">a</var> is an affine semigroup. The output is a minimal presentation for <var class="Arg">a</var>.</p>
<p>There are four methods implemented for this function, depending on the packages loaded. All of them use elimination, and Herzog's correspondence, computing the kernel of a ring homomorphism ([Her70]). The fastest procedure is achieved when SingularInterface is loaded, followed by Singular. The procedure that does not use external packages uses internal GAP Gröbner basis computations and thus it is slower. Also in this case, from the Gröbner basis, a minimal set of generating binomials must be refin | |
