[MathJax off]

3 Basic operations with numerical semigroups

This chapter describes some basic functions to deal with notable elements in a numerical semigroup. A section including functions to test Wilf's conjecture is also included in this chapter. We provide some functions that allow to treat a numerical semigroup as a list, and thus easy the task to access to its elements.

3.1 Invariants

In this section we present formulas to compute invariants and notable elements of a numerical semigroup. Some tests depending on these invariants are provided here, like being an acute or an ordinary numerical semigroup. We also present procedures to construct iterators from a numerical semigroup, or to retrieve several elements from a numerical semigroup as if it were a list (with infinitely many elements).

3.1-1 Multiplicity

NS is a numerical semigroup. Returns the multiplicity of NS, which is the smallest positive integer belonging to NS. Depending on the information known about NS, different methods are implemented. There are methods for the following cases: generators are known, Apéry set is known, it is a modular numerical semigroup, or it is proportionally modular (and thus is defined by a closed interval [RV08]).

gap> NumericalSemigroup(3,5);
<Numerical semigroup with 2 generators>
gap> Multiplicity(last);
3
gap> S := NumericalSemigroup("modular", 7,53);
<Modular numerical semigroup satisfying 7x mod 53 <= x >
gap> MultiplicityOfNumericalSemigroup(S);
8

3.1-2 Generators

S is a numerical semigroup. GeneratorsOfNumericalSemigroup returns a set of generators of S, which may not be minimal. The shorter name Generators may be used. MinimalGeneratingSystemOfNumericalSemigroup returns the minimal set of generators of S. The shorter names MinimalGenerators or MinimalGeneratingSystem may be used.

gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> Generators(S);
[ 11, 12, 13, 32, 53 ]
gap> S := NumericalSemigroup(3, 5, 53);
<Numerical semigroup with 3 generators>
gap> GeneratorsOfNumericalSemigroup(S);
[ 3, 5, 53 ]
gap> MinimalGenerators(S);
[ 3, 5 ]
gap> MinimalGeneratingSystemOfNumericalSemigroup(S);
[ 3, 5 ]
gap> MinimalGeneratingSystem(S)=MinimalGeneratingSystemOfNumericalSemigroup(S);
true
gap> s := NumericalSemigroup(3,5,7,15);
<Numerical semigroup with 4 generators>
gap> HasGenerators(s);
true
gap> HasMinimalGenerators(s);
false
gap> MinimalGenerators(s);
[ 3, 5, 7 ]
gap> Generators(s);
[ 3, 5, 7, 15 ]

3.1-3 EmbeddingDimension

NS is a numerical semigroup. It returns the cardinality of its minimal generating system.

gap> s := NumericalSemigroup(3,5,7,15);
<Numerical semigroup with 4 generators>
gap> EmbeddingDimension(s);
3
gap> EmbeddingDimensionOfNumericalSemigroup(s);
3

3.1-4 SmallElements

NS is a numerical semigroup. It returns the list of small elements of NS. Of course, the time consumed to return a result may depend on the way the semigroup is given.

gap> SmallElements(NumericalSemigroup(3,5,7));
[ 0, 3, 5 ]
gap> SmallElementsOfNumericalSemigroup(NumericalSemigroup(3,5,7));
[ 0, 3, 5 ]

3.1-5 Length

NS is a numerical semigroup. It returns the number of small elements of NS below the conductor. This corresponds with the length of the semigroup ring modulo the conductor ideal. See also LengthOfGoodSemigroup (12.2-14).

gap> Length(NumericalSemigroup(3,5,7));
2

3.1-6 FirstElementsOfNumericalSemigroup

NS is a numerical semigroup. It returns the list with the first n elements of NS.

gap> FirstElementsOfNumericalSemigroup(2,NumericalSemigroup(3,5,7));
[ 0, 3 ]
gap> FirstElementsOfNumericalSemigroup(10,NumericalSemigroup(3,5,7));
[ 0, 3, 5, 6, 7, 8, 9, 10, 11, 12 ]

3.1-7 ElementsUpTo

NS is a numerical semigroup, b a positve integer. It returns the set of elements of NS up to b.

gap> ns := NumericalSemigroup(5,7);;
gap> SmallElements(ns);
[ 0, 5, 7, 10, 12, 14, 15, 17, 19, 20, 21, 22, 24 ]
gap> ElementsUpTo(ns,18);
[ 0, 5, 7, 10, 12, 14, 15, 17 ]
gap> ElementsUpTo(ns,27);
[ 0, 5, 7, 10, 12, 14, 15, 17, 19, 20, 21, 22, 24, 25, 26, 27 ]

3.1-8 \[ \]

S is a numerical semigroup and r is an integer. It returns the r-th element of S.

gap> S := NumericalSemigroup(7,8,17);;
gap> S[53];
68

3.1-9 \{ \}

S is a numerical semigroup and ls is a list of integers. It returns the list [S[r] : r in ls].

gap> S := NumericalSemigroup(7,8,17);;
gap> S{[1..5]};
[ 0, 7, 8, 14, 15 ]

3.1-10 NextElementOfNumericalSemigroup

S is a numerical semigroup and r is an integer. It returns the returns the least integer greater than r belonging to S.

gap> S := NumericalSemigroup(7,8,17);;
gap> NextElementOfNumericalSemigroup(S,9);
14
gap> NextElementOfNumericalSemigroup(16,S);
17
gap> NextElementOfNumericalSemigroup(S,FrobeniusNumber(S))=Conductor(S);
true

3.1-11 ElementNumber_NumericalSemigroup

S is a numerical semigroup and r is an integer. Both functions (which are like synonyms) return the r-th element of S.

gap> S := NumericalSemigroup(7,8,17);;
gap> ElementNumber_NumericalSemigroup(S,53);
68
gap> RthElementOfNumericalSemigroup(S,53);
68

3.1-12 NumberElement_NumericalSemigroup

S is a numerical semigroup and r is an integer. It returns the position of r in S (and fail if the integer is not in the semigroup).

gap> S := NumericalSemigroup(7,8,17);;
gap> NumberElement_NumericalSemigroup(S,68);
53

3.1-13 Iterator

S is a numerical semigroup. It returns an iterator over S.

gap> S := NumericalSemigroup(7,8,17);;
gap> iter:=Iterator(S);
<iterator>
gap> NextIterator(iter);
0
gap> NextIterator(iter);
7
gap> NextIterator(iter);
8

3.1-14 Difference

S, T are numerical semigroups. The output is the set \(\textit{S}\setminus \textit{T}\).

gap> ns1 := NumericalSemigroup(5,7);;
gap> ns2 := NumericalSemigroup(7,11,12);;
gap> Difference(ns1,ns2);
[ 5, 10, 15, 17, 20, 27 ]
gap> Difference(ns2,ns1);
[ 11, 18, 23 ]
gap> DifferenceOfNumericalSemigroups(ns2,ns1);
[ 11, 18, 23 ]

3.1-15 AperyList

S is a numerical semigroup and n is a positive element of S. Computes the Apéry list of S with respect to n. It contains for every \(i\in \{0,\ldots,\textit{n}-1\}\), in the \(i+1\)th position, the smallest element in the semigroup congruent with \(i\) modulo n.

gap> S := NumericalSemigroup("modular", 5,53);;
gap> AperyList(S,12);
[ 0, 13, 26, 39, 52, 53, 54, 43, 32, 33, 22, 11 ]
gap> AperyListOfNumericalSemigroupWRTElement(S,12);
[ 0, 13, 26, 39, 52, 53, 54, 43, 32, 33, 22, 11 ]
gap> First(S,x-> x mod 12 =1);
13

3.1-16 AperyList

S is a numerical semigroup. It computes the Apéry list of S with respect to the multiplicity of S.

gap> AperyList(NumericalSemigroup(5,7,11));
[ 0, 11, 7, 18, 14 ]
gap> S := NumericalSemigroup("modular", 5,53);;
gap> AperyListOfNumericalSemigroup(S);
[ 0, 12, 13, 25, 26, 38, 39, 51, 52, 53, 32 ]

3.1-17 AperyList

S is a numerical semigroup and m is an integer. Computes the Apéry list of S with respect to m, that is, the set of elements \(x\) in S such that \(x-\)m is not in S. If m is an element in S, then the output of AperyListOfNumericalSemigroupWRTInteger, as sets, is the same as AperyListOfNumericalSemigroupWRTElement, though without side effects, in the sense that this information is no longer used by the package. The output of AperyList is the same as AperyListOfNumericalSemigroupWRTInteger.

gap> s:=NumericalSemigroup(10,13,19,27);;
gap> AperyList(s,11);
[ 0, 10, 13, 19, 20, 23, 26, 27, 29, 32, 33, 36, 39, 42, 45, 46, 52, 55 ]
gap> AperyListOfNumericalSemigroupWRTInteger(s,11);
[ 0, 10, 13, 19, 20, 23, 26, 27, 29, 32, 33, 36, 39, 42, 45, 46, 52, 55 ]
gap> Length(last);
18
gap> AperyListOfNumericalSemigroupWRTInteger(s,10);
[ 0, 13, 19, 26, 27, 32, 38, 45, 51, 54 ]
gap> AperyListOfNumericalSemigroupWRTElement(s,10);
[ 0, 51, 32, 13, 54, 45, 26, 27, 38, 19 ]
gap> AperyList(s,10);
[ 0, 51, 32, 13, 54, 45, 26, 27, 38, 19 ]
gap> Length(last);
10

3.1-18 AperyListOfNumericalSemigroupAsGraph

ap is the Apéry list of a numerical semigroup. This function returns the adjacency list of the graph \((ap, E)\) where the edge \(u -> v\) is in \(E\) iff \(v - u\) is in \(ap\). The 0 is ignored.

gap> s:=NumericalSemigroup(3,7);;
gap> AperyListOfNumericalSemigroupWRTElement(s,10);
[ 0, 21, 12, 3, 14, 15, 6, 7, 18, 9 ]
gap> AperyListOfNumericalSemigroupAsGraph(last);
[ ,, [ 3, 6, 9, 12, 15, 18, 21 ],,, [ 6, 9, 12, 15, 18, 21 ],
[ 7, 14, 21 ],, [ 9, 12, 15, 18, 21 ],,, [ 12, 15, 18, 21 ],,
[ 14, 21 ], [ 15, 18, 21 ],,, [ 18, 21 ],,, [ 21 ] ]

3.1-19 KunzCoordinates

S is a numerical semigroup, and m is a nonzero element of S. The second argument is optional, and if missing it is assumed to be the multiplicity of S.

Then the Apéry set of m in S has the form \([0,k_1m+1,...,k_{m-1}m+m-1]\), and the output is the \((m-1)\)-uple \([k_1,k_2,...,k_{m-1}]\)

gap> s:=NumericalSemigroup(3,5,7);
<Numerical semigroup with 3 generators>
gap> KunzCoordinates(s);
[ 2, 1 ]
gap> KunzCoordinatesOfNumericalSemigroup(s);
[ 2, 1 ]
gap> KunzCoordinates(s,5);
[ 1, 1, 0, 1 ]
gap> KunzCoordinatesOfNumericalSemigroup(s,5);
[ 1, 1, 0, 1 ]

3.1-20 KunzPolytope

m is a positive integer.

The Kunz coordinates of the semigroups with multiplicity m are solutions of a system of inequalities \(Ax\ge b\) (see [CAGB02]). The output is the matrix \((A|-b)\).

gap> KunzPolytope(3);
[ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 2, -1, 0 ], [ -1, 2, 1 ] ]

3.1-21 CocycleOfNumericalSemigroupWRTElement

S is a numerical semigroup, and m is a nonzero element of S. The output is the matrix \(h(i,j)=(w(i)+w(j)-w((i+j)\bmod m))/m\), where \(w(i)\) is the smallest element in S congruent with \(i\) modulo \(m\) (and thus it is in the Apéry set of \(m\)), [GHKR17].

gap> s:=NumericalSemigroup(3,5,7);;
gap> CocycleOfNumericalSemigroupWRTElement(s,3);
[ [ 0, 0, 0 ], [ 0, 3, 4 ], [ 0, 4, 1 ] ]

3.1-22 FrobeniusNumber

The largest nonnegative integer not belonging to a numerical semigroup \(S\) is the Frobenius number of \(S\). If \(S\) is the set of nonnegative integers, then clearly its Frobenius number is \(-1\), otherwise its Frobenius number coincides with the maximum of the gaps (or fundamental gaps) of \(S\).

NS is a numerical semigroup. It returns the Frobenius number of NS. Of course, the time consumed to return a result may depend on the way the semigroup is given or on the knowledge already produced on the semigroup.

gap> FrobeniusNumber(NumericalSemigroup(3,5,7));
4
gap> FrobeniusNumberOfNumericalSemigroup(NumericalSemigroup(3,5,7));
4

3.1-23 Conductor

This is just a synonym of FrobeniusNumberOfNumericalSemigroup (NS)\(+1\).

gap> Conductor(NumericalSemigroup(3,5,7));
5
gap> ConductorOfNumericalSemigroup(NumericalSemigroup(3,5,7));
5

3.1-24 PseudoFrobenius

An integer \(z\) is a pseudo-Frobenius number of \(S\) if \(z+S\setminus\{0\}\subseteq S\).

S is a numerical semigroup. It returns the set of pseudo-Frobenius numbers of S.

gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> PseudoFrobenius(S);
[ 21, 40, 41, 42 ]
gap> PseudoFrobeniusOfNumericalSemigroup(S);
[ 21, 40, 41, 42 ]

3.1-25 Type

Stands for Length(PseudoFrobeniusOfNumericalSemigroup (NS)).

gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> Type(S);
4
gap> TypeOfNumericalSemigroup(S);
4

3.1-26 Gaps

A gap of a numerical semigroup \(S\) is a nonnegative integer not belonging to \(S\). NS is a numerical semigroup. Both return the set of gaps of NS.

gap> Gaps(NumericalSemigroup(5,7,11));
[ 1, 2, 3, 4, 6, 8, 9, 13 ]
gap> GapsOfNumericalSemigroup(NumericalSemigroup(3,5,7));
[ 1, 2, 4 ]

3.1-27 Weight

If \(l_1<\cdots <l_g\) are the gaps of NS, then its (Weierstrass) weight is \(\sum_{i=1}^g (l_i-i)\).

gap> Weight(NumericalSemigroup(4,5,6,7));
0
gap> Weight(NumericalSemigroup(4,5));    
9

3.1-28 Deserts

NS is a numerical semigroup. The output is the list with the runs of gaps of NS.

gap> s:=NumericalSemigroup(3,5,7);;
gap> Deserts(s);
[ [ 1, 2 ], [ 4 ] ]
gap> DesertsOfNumericalSemigroup(s);
[ [ 1, 2 ], [ 4 ] ]

3.1-29 IsOrdinary

NS is a numerical semigroup. Dectects if the semigroup is ordinary, that is, with less than two deserts.

This filter implies IsAcuteNumericalSemigroup (3.1-30).

gap> s:=NumericalSemigroup(3,5,7);;
gap> IsOrdinary(s);
false

3.1-30 IsAcute

NS is a numerical semigroup. Dectects if the semigroup is acute, that is, it is either ordinary or its last desert (the one with the Frobenius number) has less elements than the preceding one ([Bra04]).

gap> s:=NumericalSemigroup(3,5,7);;
gap> IsAcute(s);
true

3.1-31 Holes

S is a numerical semigroup. Returns the set of gaps \(x\) of S such that \(F(S)-x\) is also a gap, where \(F(S)\) stands for the Frobenius number of S.

gap> s:=NumericalSemigroup(3,5);;
gap> Holes(s);
[  ]
gap> s:=NumericalSemigroup(3,5,7);;
gap> HolesOfNumericalSemigroup(s);
[ 2 ]

3.1-32 LatticePathAssociatedToNumericalSemigroup

S is a numerical semigroup and p,q are two coprime elements in S.

In this setting S is an oversemigroup of \(\langle p,q\rangle\), and consequently every gap of S is a gap of \(\langle p,q\rangle\). If \(c\) is the conductor of \(\langle p,q\rangle\), then every gap \(g\) of \(\langle p,q\rangle\) can be written uniquely as \(g=c-1-(ap+bp)\) for some nonnegative integers \(a,b\). We say that \((a,b)\) are the coordinates associated to \(g\).

The output is a path in \(\mathbb{N}^2\) such that the coordinates of the gaps of \(S\) correspond exactly with the points in \(\mathbb{N}^2\) that are between the path and the line \(ax+by=c-1\). See [KW14].

gap> s:=NumericalSemigroup(16,17,71,72);;
gap> LatticePathAssociatedToNumericalSemigroup(s,16,17);
[ [ 0, 14 ], [ 1, 13 ], [ 2, 12 ], [ 3, 11 ], [ 4, 10 ], [ 5, 9 ], [ 6, 8 ],
  [ 7, 7 ], [ 8, 6 ], [ 9, 5 ], [ 10, 4 ], [ 11, 3 ], [ 12, 2 ], [ 13, 1 ],
  [ 14, 0 ] ]

3.1-33 Genus

NS is a numerical semigroup. It returns the number of gaps of NS.

gap> s:=NumericalSemigroup(16,17,71,72);;
gap> Genus(s);
80
gap> GenusOfNumericalSemigroup(s);
80
gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> Genus(S);
26

3.1-34 FundamentalGaps

S The fundamental gaps of \(S\) are those gaps that are maximal with respect to the partial order induced by division in \({\mathbb N}\). It returns the set of fundamental gaps of S.

gap> FundamentalGaps(NumericalSemigroup(5,7,11));
[ 6, 8, 9, 13 ]
gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> FundamentalGapsOfNumericalSemigroup(S);
[ 16, 17, 18, 19, 27, 28, 29, 30, 31, 40, 41, 42 ]
gap> GapsOfNumericalSemigroup(S);
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 27, 28, 29,
  30, 31, 40, 41, 42 ]
gap> Gaps(NumericalSemigroup(5,7,11));
[ 1, 2, 3, 4, 6, 8, 9, 13 ]

3.1-35 SpecialGaps

The special gaps of a numerical semigroup \(S\) are those fundamental gaps such that if they are added to the given numerical semigroup, then the resulting set is again a numerical semigroup. S is a numerical semigroup. It returns the special gaps of S.

gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> SpecialGaps(S);
[ 40, 41, 42 ]
gap> SpecialGapsOfNumericalSemigroup(S);
[ 40, 41, 42 ]

3.2 Wilf's conjecture

Let \(S\) be a numerical semigroup, with conductor \(c\) and embedding dimension \(e\). Denote by \(l\) the cardinality of the set of elements in \(S\) smaller than \(c\). Wilf in [Wil78] asked whether or not \(l/c\ge 1/e\) for all numerical semigroups. In this section we give some functions to experiment with this conjecture, as defined in [Eli18].

3.2-1 WilfNumber

S is a numerical semigroup. Let \(c\), \(e\) and \(l\) be the conductor, embedding dimension and number of elements smaller than \(c\) in S. Returns \(e l-c\), which was conjetured by Wilf to be nonnegative.

gap> s := NumericalSemigroup(13,25,37);;
gap> WilfNumber(s);
96
gap> l:=NumericalSemigroupsWithGenus(10);;
gap> Filtered(l, s->WilfNumber(s)<0);
[  ]
gap> Maximum(Set(l, s->WilfNumberOfNumericalSemigroup(s)));
70

3.2-2 EliahouNumber

S is a numerical semigroup. Let \(c\), \(m\), \(s\) and \(l\) be the conductor, multiplicity, number of generators smaller than \(c\), and number of elements smaller than \(c\) in S, respectively. Let \(q\) and \(r\) be the quotient and nonpositive remainder of the division of \(c\) by \(m\), that is, \(c=qm-r\). Returns \(s l-qd_q+r\), where \(d_q\) corresponds with the number of integers in \([c,c+m[\) that are not minimal generators of S.

gap> s:=NumericalSemigroupWithGivenElementsAndFrobenius([14,22,23],55);;
gap> EliahouNumber(s);
-1
gap> s:=NumericalSemigroup(5,7,9);;
gap> TruncatedWilfNumberOfNumericalSemigroup(s);
4

3.2-3 ProfileOfNumericalSemigroup

S is a numerical semigroup. Let \(c\) and \(m\) be the conductor and multiplicity of S, respectively. Let \(q\) and \(r\) be the quotient and nonpositive remainder of the division of \(c\) by \(m\), that is, \(c=qm-r\). Returns a list of lists of integers, each list is the cardinality of \( S \cap [jm-r, (j+1)m-r[\) with \( j\) in [1..q-1].

gap> s:=NumericalSemigroup(5,7,9);;
gap> ProfileOfNumericalSemigroup(s);
[ 2, 1 ]
gap> s:=NumericalSemigroupWithGivenElementsAndFrobenius([14,22,23],55);;
gap> ProfileOfNumericalSemigroup(s);
[ 3, 0, 0 ]

3.2-4 EliahouSlicesOfNumericalSemigroup

S is a numerical semigroup. Let \(c\) and \(m\) be the conductor and multiplicity of S, respectively. Let \(q\) and \(r\) be the quotient and nonpositive remainder of the division of \(c\) by \(m\), that is, \(c=qm-r\). Returns a list of lists of integers, each list is the set \( S \cap [jm-r, (j+1)m-r[\) with \( j\) in [1..q]. So this is a partition of the set of small elements of S (without \(0\) and \(c\)).

gap> s:=NumericalSemigroup(5,7,9);;                                     
gap> EliahouSlicesOfNumericalSemigroup(s);
[ [ 5, 7 ], [ 9, 10, 12 ] ]
gap> SmallElements(s);
[ 0, 5, 7, 9, 10, 12, 14 ]

generated by GAPDoc2HTML