<?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 6:
Irreducible 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="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<p><a id="X83C597EC7FAA1C0F" name="X83C597EC7FAA1C0F"></a></p>
<div class="ChapSects"><a href="chap6.html#X83C597EC7FAA1C0F">6 <span class="Heading">
Irreducible numerical semigroups
</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X83C597EC7FAA1C0F">6.1 <span class="Heading">
Irreducible numerical semigroups
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X87D62468791EDE8A">6.1-1 IsIrreducibleNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7BCDAFE3791A3C48">6.1-2 IsSymmetricNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X84125DC485D48A88">6.1-3 IsPseudoSymmetricNumericalSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7C8AB03F7E0B71F0">6.1-4 AnIrreducibleNumericalSemigroupWithFrobeniusNumber</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X78345A267ADEFBAB">6.1-5 IrreducibleNumericalSemigroupsWithFrobeniusNumber</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8227EF2B7F67E2FB">6.1-6 DecomposeIntoIrreducibles</a></span>
</div>
</div>
<h3>6 <span class="Heading">
Irreducible numerical semigroups
</span></h3>
<p><a id="X83C597EC7FAA1C0F" name="X83C597EC7FAA1C0F"></a></p>
<h4>6.1 <span class="Heading">
Irreducible numerical semigroups
</span></h4>
<p>An irreducible numerical semigroup is a semigroup that cannot be expressed as the intersection of numerical semigroups properly containing it.</p>
<p>It is not difficult to prove that a semigroup is irreducible if and only if it is maximal (with respect to set inclusion) in the set of all numerical semigroup having its same Frobenius number (see <a href="chapBib.html#biBRB03">[RB03]</a>). Hence, according to <a href="chapBib.html#biBFGH87">[FH87]</a> (respectively <a href="chapBib.html#biBBDF97">[BF97]</a>), symmetric (respectively pseudo-symmetric) numerical semigroups are those irreducible numerical semigroups with odd (respectively even) Frobenius number.</p>
<p>In <a href="chapBib.html#biBRGGJ03">[GJ03]</a> it is shown that a numerical semigroup is irreducible if and only if it has only one special gap. We use this characterization.</p>
<p>In this section we show how to construct the set of all numerical semigroups with a given Frobenius number. First we construct an irreducible numerical semigroup with the given Frobenius number (as explained in <a href="chapBib.html#biBRGS04">[JCR04]</a>), and then we construct the rest from it. That is why we have separated both functions.</p>
<p>Every numerical semigroup can be expressed as an intersection of irreducible numerical semigroups. If S can be expressed as S=S_1cap cdotscap S_n, with S_i irreducible numerical semigroups, and no factor can be removed, then we say that this decomposition is minimal. Minimal decompositions can be computed by using Algorithm 26 in <a href="chapBib.html#biBRGGJ03">[GJ03]</a>.</p>
<p><a id="X87D62468791EDE8A" name="X87D62468791EDE8A"></a></p>
<h5>6.1-1 IsIrreducibleNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsIrreducibleNumericalSemigroup</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 true if <var class="Arg">s</var> is irreducible, false otherwise.</p>
<table class="example">
<tr><td><pre>
gap> IsIrreducibleNumericalSemigroup(NumericalSemigroup(4,6,9));
true
gap> IsIrreducibleNumericalSemigroup(NumericalSemigroup(4,6,7,9));
false
</pre></td></tr></table>
<p><a id="X7BCDAFE3791A3C48" name="X7BCDAFE3791A3C48"></a></p>
<h5>6.1-2 IsSymmetricNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsSymmetricNumericalSemigroup</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 true if <var class="Arg">s</var> is symmetric, false otherwise.</p>
<table class="example">
<tr><td><pre>
gap> IsSymmetricNumericalSemigroup(NumericalSemigroup(10,23));
true
gap> IsSymmetricNumericalSemigroup(NumericalSemigroup(10,11,23));
false
</pre></td></tr></table>
<p><a id="X84125DC485D48A88" name="X84125DC485D48A88"></a></p>
<h5>6.1-3 IsPseudoSymmetricNumericalSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsPseudoSymmetricNumericalSemigroup</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 true if <var class="Arg">s</var> is pseudo-symmetric, false otherwise.</p>
<table class="example">
<tr><td><pre>
gap> IsPseudoSymmetricNumericalSemigroup(NumericalSemigroup(6,7,8,9,11));
true
gap> IsPseudoSymmetricNumericalSemigroup(NumericalSemigroup(4,6,9));
false
</pre></td></tr></table>
<p><a id="X7C8AB03F7E0B71F0" name="X7C8AB03F7E0B71F0"></a></p>
<h5>6.1-4 AnIrreducibleNumericalSemigroupWithFrobeniusNumber</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AnIrreducibleNumericalSemigroupWithFrobeniusNumber</code>( <var class="Arg">f</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">f</var> is an integer greater than or equal to -1. The output is an irreducible numerical semigroup with frobenius number <var class="Arg"> f</var>. From the way the procedure is implemented, the resulting semigroup has at most four generators (see <a href="chapBib.html#biBRGS04">[JCR04]</a>).</p>
<table class="example">
<tr><td><pre>
gap> FrobeniusNumber(AnIrreducibleNumericalSemigroupWithFrobeniusNumber(28));
28
</pre></td></tr></table>
<p><a id="X78345A267ADEFBAB" name="X78345A267ADEFBAB"></a></p>
<h5>6.1-5 IrreducibleNumericalSemigroupsWithFrobeniusNumber</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IrreducibleNumericalSemigroupsWithFrobeniusNumber</code>( <var class="Arg">f</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">f</var> is an integer greater than or equal to -1. The output is the set of all irreducible numerical semigroups with frobenius number <var class="Arg">f</var>.</p>
<table class="example">
<tr><td><pre>
gap> Length(IrreducibleNumericalSemigroupsWithFrobeniusNumber(39));
227
</pre></td></tr></table>
<p><a id="X8227EF2B7F67E2FB" name="X8227EF2B7F67E2FB"></a></p>
<h5>6.1-6 DecomposeIntoIrreducibles</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DecomposeIntoIrreducibles</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 a set of irreducible numerical semigroups containing it. These elements appear in a minimal decomposition of <var class="Arg">s</var> as intersection into irreducibles.</p>
<table class="example">
<tr><td><pre>
gap> DecomposeIntoIrreducibles(NumericalSemigroup(5,6,8));
[ <Numerical semigroup>, <Numerical semigroup> ]
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.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
>
2472
