This chapter provides several functions to construct numerical semigroups from others (via intersections, quotients by an integer, removing or adding integers, etc.).
In this section we show how to construct new numerical semigroups from a given numerical semigroup. Two dual operations are presented. The first one removes a minimal generator from a numerical semigroup. The second adds a special gap to a semigroup (see [RGGJ03]).
‣ RemoveMinimalGeneratorFromNumericalSemigroup( n, S ) | ( function ) |
S is a numerical semigroup and n is one if its minimal generators.
The output is the numerical semigroup \( \textit{S} \setminus\{\textit{n}\} \) (see [RGGJ03]; \(S\setminus\{n\}\) is a numerical semigroup if and only if \(n\) is a minimal generator of \(S\)).
gap> s:=NumericalSemigroup(3,5,7); <Numerical semigroup with 3 generators> gap> RemoveMinimalGeneratorFromNumericalSemigroup(7,s); <Numerical semigroup with 3 generators> gap> MinimalGeneratingSystemOfNumericalSemigroup(last); [ 3, 5 ]
‣ AddSpecialGapOfNumericalSemigroup( g, S ) | ( function ) |
S is a numerical semigroup and g is a special gap of S.
The output is the numerical semigroup \( \textit{S} \cup\{\textit{g}\} \) (see [RGGJ03], where it is explained why this set is a numerical semigroup).
gap> s:=NumericalSemigroup(3,5,7);; gap> s2:=RemoveMinimalGeneratorFromNumericalSemigroup(5,s); <Numerical semigroup with 3 generators> gap> s3:=AddSpecialGapOfNumericalSemigroup(5,s2); <Numerical semigroup> gap> SmallElementsOfNumericalSemigroup(s) = > SmallElementsOfNumericalSemigroup(s3); true gap> s=s3; true
We provide functions to build numerical semigroups from others by means of intersections, quotients, multiples and related constructions.
‣ Intersection( S, T ) | ( operation ) |
‣ IntersectionOfNumericalSemigroups( S, T ) | ( function ) |
S and T are numerical semigroups. Computes the intersection of S and T (which is a numerical semigroup).
gap> S := NumericalSemigroup("modular", 5,53); <Modular numerical semigroup satisfying 5x mod 53 <= x > gap> T := NumericalSemigroup(2,17); <Numerical semigroup with 2 generators> gap> SmallElements(S); [ 0, 11, 12, 13, 22, 23, 24, 25, 26, 32, 33, 34, 35, 36, 37, 38, 39, 43 ] gap> SmallElements(T); [ 0, 2, 4, 6, 8, 10, 12, 14, 16 ] gap> Intersection(S,T); <Numerical semigroup> gap> SmallElements(last); [ 0, 12, 22, 23, 24, 25, 26, 32, 33, 34, 35, 36, 37, 38, 39, 43 ] gap> IntersectionOfNumericalSemigroups(S,T) = Intersection(S,T); true
5.2-2 \+‣ \+( S, T ) | ( operation ) |
S and T are numerical semigroups. Computes the sum of S and T (which is a numerical semigroup).
gap> s:=NumericalSemigroup(4,9);; gap> t:=NumericalSemigroup(6,7);; gap> MinimalGenerators(s+t); [ 4, 6, 7, 9 ]
‣ QuotientOfNumericalSemigroup( S, n ) | ( function ) |
‣ \/( S, n ) | ( operation ) |
S is a numerical semigroup and n is an integer. Computes the quotient of S by n, that is, the set \(\{ x\in {\mathbb N}\ |\ nx \in S\}\), which is again a numerical semigroup. S / n may be used as a short for QuotientOfNumericalSemigroup(S, n).
gap> s:=NumericalSemigroup(3,29); <Numerical semigroup with 2 generators> gap> SmallElements(s); [ 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 50, 51, 53, 54, 56 ] gap> t:=QuotientOfNumericalSemigroup(s,7); <Numerical semigroup> gap> SmallElements(t); [ 0, 3, 5, 6, 8 ] gap> u := s / 7; <Numerical semigroup> gap> SmallElements(u); [ 0, 3, 5, 6, 8 ]
‣ MultipleOfNumericalSemigroup( S, a, b ) | ( function ) |
S is a numerical semigroup, and a and b are positive integers. Computes \(a S\cup \{b,b+1,\to\}\). If b is smaller than \(a c\), with \(c\) the conductor of \(S\), then a warning is displayed.
gap> N:=NumericalSemigroup(1);; gap> s:=MultipleOfNumericalSemigroup(N,4,20);; gap> SmallElements(s); [ 0, 4, 8, 12, 16, 20 ]
‣ NumericalDuplication( S, E, b ) | ( function ) |
S is a numerical semigroup, and E and ideal of S, and b is a positive odd integer, so that \(2S\cup (2E+b)\) is a numerical semigroup (this extends slightly the original definition where b was imposed to be in S, [DS13]; now the condition imposed is \(E+E+b\subseteq S\)). Computes \(2S\cup (2E+b)\).
gap> s:=NumericalSemigroup(3,5,7); <Numerical semigroup with 3 generators> gap> e:=6+s; <Ideal of numerical semigroup> gap> ndup:=NumericalDuplication(s,e,3); <Numerical semigroup with 4 generators> gap> SmallElements(ndup); [ 0, 6, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24 ]
‣ AsNumericalDuplication( T ) | ( function ) |
T is a numerical semigroup. Detects whether or not T can be expressed as NumericalDuplication(S,E,b), with E a proper ideal of S. Returns the list [S,E,b] if this is possible, and fail otherwise.
Notice that a numerical semigroup can be represented in different ways as a numerical duplication.
gap> s:=NumericalSemigroup(3,5,7);; gap> ndup:=NumericalDuplication(s,6+s,11);; gap> asdup:=AsNumericalDuplication(ndup); [ <Numerical semigroup with 3 generators>, <Ideal of numerical semigroup>, 3 ] gap> ndup = CallFuncList(NumericalDuplication,asdup); true
‣ InductiveNumericalSemigroup( a, b ) | ( function ) |
a and b are lists of positive integers, with \(k\) the length of a and b, and such that \(b[i+1]\ge a[i]b[i]\) (\(0\le i\le k-1\)). Computes inductively \(S_0=\mathbb N\) and \(S_{i+1}=a[i]S_i\cup \{a[i]b[i],a[i]b[i]+1,\to\}\), and returns \(S_{k}\).
gap> s:=InductiveNumericalSemigroup([4,2],[5,23]);; gap> SmallElements(s); [ 0, 8, 16, 24, 32, 40, 42, 44, 46 ]
‣ DilatationOfNumericalSemigroup( S, a ) | ( function ) |
S is a numerical semigroup, and a is a positive integer. If \(M\) is the maximal ideal of S, then a must be in \(M-2M\). Computes the numerical semigroup \(\{0\} \cup \{a+s \mid s\in M\}\), see [BS19].
gap> s:=NumericalSemigroup(3,4,5);; gap> m:=MaximalIdeal(s);; gap> SmallElements(m-2*m); [ -3 ] gap> d:=DilatationOfNumericalSemigroup(s,3); <Numerical semigroup> gap> SmallElements(d); [ 0, 6 ]
In order to construct the set of numerical semigroups containing a fixed numerical semigroup \(S\), one first constructs its unitary extensions, that is to say, the sets \(S\cup\{g\}\) that are numerical semigroups with \(g\) a positive integer. This is achieved by constructing the special gaps of the semigroup, and then adding each of them to the numerical semigroup. Then we repeat the process for each of these new numerical semigroups until we reach \( {\mathbb N} \).
These procedures are described in [RGGJ03].
‣ OverSemigroups( s ) | ( operation ) |
‣ OverSemigroupsNumericalSemigroup( s ) | ( function ) |
s is a numerical semigroup. The output is the set of numerical semigroups containing it.
gap> s := NumericalSemigroup(3,5,7);; gap> OverSemigroups(s); [ <The numerical semigroup N>, <Numerical semigroup with 2 generators>, <Numerical semigroup with 3 generators>, <Numerical semigroup with 3 generators> ] gap> List(last,s->MinimalGenerators(s)); [ [ 1 ], [ 2, 3 ], [ 3 .. 5 ], [ 3, 5, 7 ] ] gap> OverSemigroupsNumericalSemigroup(s) = OverSemigroups(s); true
Finding the set of all numerical semigroups with a given Frobenius number is not accomplished via over semigroups. In order to achieve this, we use fundamental gaps. If the multiplicity is fixed, then the construction relies on the calculation of irreducible numerical semigroups with that Frobenius number and multiplicity.
‣ NumericalSemigroupsWithFrobeniusNumberFG( f ) | ( function ) |
f is an integer. The output is the set of numerical semigroups with Frobenius number f. The algorithm implemented is given in [RGGJM04].
gap> Length(NumericalSemigroupsWithFrobeniusNumberFG(15)); 200
‣ NumericalSemigroupsWithFrobeniusNumberAndMultiplicity( f, m ) | ( function ) |
f and m are integers. The output is the set of numerical semigroups with Frobenius number f and multiplicity m. The algorithm implemented is given in [BOR21].
gap> Length(NumericalSemigroupsWithFrobeniusNumberAndMultiplicity(15,6)); 28
‣ NumericalSemigroupsWithFrobeniusNumber( f ) | ( function ) |
f is an integer. As happens with the function NumericalSemigroupsWithFrobeniusNumberFG (5.4-1), the output is the set of numerical semigroups with Frobenius number f. It makes use of NumericalSemigroupsWithFrobeniusNumberAndMultiplicity (5.4-2) to compute the semigroups with the Frobenius number given for all the possible multiplicities.
gap> Length(NumericalSemigroupsWithFrobeniusNumber(15)); 200
‣ NumericalSemigroupsWithFrobeniusNumberPC( f ) | ( function ) |
f is an integer. The output is the set of numerical semigroups with Frobenius number f. It relies on pre-computed data, which is available for small values of f.
gap> Length(NumericalSemigroupsWithFrobeniusNumberPC(15)); 200
Finding the set of all numerical semigroups with a given maximum primitive.
‣ NumericalSemigroupsWithMaxPrimitiveAndMultiplicity( M, m ) | ( function ) |
M and m are integers. The output is the set of numerical semigroups with maximum primitive M and multiplicity m. The algorithm implemented is based on work by M. Delgado and Neeraj Kumar.
gap> Length(NumericalSemigroupsWithMaxPrimitiveAndMultiplicity(15,6)); 27
‣ NumericalSemigroupsWithMaxPrimitive( M ) | ( function ) |
M is an integer. The output is the set of numerical semigroups with maximum primitive M. It makes use of NumericalSemigroupsWithMaxPrimitiveAndMultiplicity (5.5-1) to compute the semigroups with the given maximum primitive for all the possible multiplicities.
gap> NumericalSemigroupsWithMaxPrimitive(5); [ <Numerical semigroup with 2 generators>, <Numerical semigroup with 2 generators>, <Numerical semigroup with 3 generators>, <Numerical semigroup with 2 generators> ] gap> Length(NumericalSemigroupsWithMaxPrimitive(15)); 194
‣ NumericalSemigroupsWithMaxPrimitivePC( M ) | ( function ) |
M is an integer. The output is the set of numerical semigroups with maximum primitive M. It relies on pre-computed data, which is available for small values of M.
gap> Length(NumericalSemigroupsWithMaxPrimitivePC(15)); 194
Given a numerical semigroup of genus g (that is, with exactly g gaps), removing minimal generators, one obtains numerical semigroups of genus g+1. In order to avoid repetitions, we only remove minimal generators greater than the Frobenius number of the numerical semigroup (this is accomplished with the local function sons).
These procedures are described in [RGGB03] and [Bra08].
‣ NumericalSemigroupsWithGenus( g ) | ( function ) |
g is a nonnegative integer. The output is the set of numerical semigroups with genus g. If the user just wants to use some numerical semigroup with a given genus pseudo-randomly choosen, he is probably looking for the function RandomNumericalSemigroupWithGenus (B.1-7).
gap> NumericalSemigroupsWithGenus(5); [ <Numerical semigroup with 6 generators>, <Numerical semigroup with 5 generators>, <Numerical semigroup with 5 generators>, <Numerical semigroup with 5 generators>, <Numerical semigroup with 5 generators>, <Numerical semigroup with 4 generators>, <Numerical semigroup with 4 generators>, <Numerical semigroup with 4 generators>, <Numerical semigroup with 4 generators>, <Numerical semigroup with 3 generators>, <Numerical semigroup with 3 generators>, <Numerical semigroup with 2 generators> ] gap> List(last,MinimalGenerators); [ [ 6 .. 11 ], [ 5, 7, 8, 9, 11 ], [ 5, 6, 8, 9 ], [ 5, 6, 7, 9 ], [ 5, 6, 7, 8 ], [ 4, 6, 7 ], [ 4, 7, 9, 10 ], [ 4, 6, 9, 11 ], [ 4, 5, 11 ], [ 3, 8, 10 ], [ 3, 7, 11 ], [ 2, 11 ] ]
‣ NumericalSemigroupsWithGenusPC( g ) | ( function ) |
g is a nonnegative integer. The output is the set of numerical semigroups with genus g. It relies on pre-computed data, which is available for small values of g.
gap> Length(NumericalSemigroupsWithGenusPC(15)); 2857
Refer to PseudoFrobeniusOfNumericalSemigroup (3.1-24).
These procedures are described in [DGR16], and are used to find the set of numerical semigroups with a prescribed set of pseudo-Frobenius numbers.
‣ ForcedIntegersForPseudoFrobenius( PF ) | ( function ) |
PF is a list of positive integers (given as a list or individual elements). The output is:
in case there exists a numerical semigroup \(S\) such that \(PF(S)=PF\):
a list \([forced\_gaps,forced\_elts]\) such that:
\(forced\_gaps\) is contained in \({\mathbb N} - S\) for any numerical semigroup S such that \(PF(S)=\{g\_1,\ldots,g\_n\}\)
forced_elts is contained in \(S\) for any numerical semigroup \(S\) such that \(PF(S)=\{g\_1,\ldots,g\_n\}\)
"fail" in case it is found some condition that fails.
gap> pf := [ 58, 64, 75 ]; [ 58, 64, 75 ] gap> ForcedIntegersForPseudoFrobenius(pf); [ [ 1, 2, 3, 4, 5, 6, 7, 8, 11, 15, 16, 17, 25, 29, 32, 58, 64, 75 ], [ 0, 59, 60, 67, 68, 69, 70, 71, 72, 73, 74, 76 ] ]
‣ SimpleForcedIntegersForPseudoFrobenius( fg, fe, PF ) | ( function ) |
Is just a quicker version of ForcedIntegersForPseudoFrobenius (5.7-1)
fg is a list of integers that we require to be gaps of the semigroup; fe is a list of integers that we require to be elements of the semigroup; PF is a list of positive integers. The output is:
in case there exists a numerical semigroup \(S\) such that \(PF(S)=PF\):
a list \([forced\_gaps,forced\_elts]\) such that:
\(forced\_gaps\) is contained in \({\mathbb N} - S\) for any numerical semigroup S such that \(PF(S)=\{g\_1,\ldots,g\_n\}\)
forced_elts is contained in \(S\) for any numerical semigroup \(S\) such that \(PF(S)=\{g\_1,\ldots,g\_n\}\)
"fail" in case it is found some condition that fails.
gap> pf := [ 15, 20, 27, 35 ];; gap> fint := ForcedIntegersForPseudoFrobenius(pf); [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 20, 27, 35 ], [ 0, 19, 23, 25, 26, 28, 29, 30, 31, 32, 33, 34, 36 ] ] gap> free := Difference([1..Maximum(pf)],Union(fint)); [ 11, 13, 14, 17, 18, 21, 22, 24 ] gap> SimpleForcedIntegersForPseudoFrobenius(fint[1],Union(fint[2],[free[1]]),pf); [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 20, 24, 27, 35 ], [ 0, 11, 19, 22, 23, 25, 26, 28, 29, 30, 31, 32, 33, 34, 36 ] ]
‣ NumericalSemigroupsWithPseudoFrobeniusNumbers( PF ) | ( function ) |
PF is a list of positive integers (given as a list or individual elements). The output is: a list of numerical semigroups S such that PF(S)=PF. When Length(PF)=1, it makes use of the function NumericalSemigroupsWithFrobeniusNumber (5.4-3)
gap> pf := [ 58, 64, 75 ]; [ 58, 64, 75 ] gap> Length(NumericalSemigroupsWithPseudoFrobeniusNumbers(pf)); 561 gap> pf := [11,19,22];; gap> NumericalSemigroupsWithPseudoFrobeniusNumbers(pf); [ <Numerical semigroup>, <Numerical semigroup>, <Numerical semigroup>, <Numerical semigroup>, <Numerical semigroup> ] gap> List(last,MinimalGenerators); [ [ 7, 9, 17, 20 ], [ 7, 10, 13, 16, 18 ], [ 9, 12, 14, 15, 16, 17, 20 ], [ 10, 13, 14, 15, 16, 17, 18, 21 ], [ 12, 13, 14, 15, 16, 17, 18, 20, 21, 23 ] ] gap> Set(last2,PseudoFrobeniusOfNumericalSemigroup); [ [ 11, 19, 22 ] ] g
‣ ANumericalSemigroupWithPseudoFrobeniusNumbers( PF ) | ( function ) |
PF is a list of positive integers (given as a list or individual elements). Alternatively, a record with fields "pseudo_frobenius" and "max_attempts" may be given. The output is: A numerical semigroup S such that \(PF(S)=PF\). Returns fail if it concludes that it does not exist and suggests to use NumericalSemigroupsWithPseudoFrobeniusNumbers if it is not able to conclude...
When \(Length(PF)=1\) or \(Length(PF)=2\) and \(2*PF[1] = PF[2]\), it makes use of the function AnIrreducibleNumericalSemigroupWithFrobeniusNumber (6.1-4).
gap> pf := [ 83, 169, 173, 214, 259 ];; gap> ANumericalSemigroupWithPseudoFrobeniusNumbers(pf); <Numerical semigroup> gap> gen := MinimalGeneratingSystem(last); [ 38, 57, 64, 72, 79, 98, 99, 106, 118, 120, 124, 132, 134, 146, 147, 154, 165, 168, 179 ] gap> ns := NumericalSemigroup(gen); <Numerical semigroup with 19 generators> gap> PseudoFrobeniusOfNumericalSemigroup(ns); [ 83, 169, 173, 214, 259 ]
generated by GAPDoc2HTML