[MathJax on]

2 Numerical Semigroups

This chapter describes how to create numerical semigroups in GAP and perform some basic tests.

2.1 Generating Numerical Semigroups

We recall some definitions from Chapter 1.

A numerical semigroup is a subset of the set N of nonnegative integers that is closed under addition, contains 0 and whose complement in N is finite.

We refer to the elements in a numerical semigroup that are less than or equal to the conductor as small elements of the semigroup.

A gap of a numerical semigroup S is a nonnegative integer not belonging to S. The fundamental gaps of S are those gaps that are maximal with respect to the partial order induced by division in N.

Given a numerical semigroup S and a nonzero element s in it, one can consider for every integer i ranging from 0 to s-1, the smallest element in S congruent with i modulo s, say w(i) (this element exists since the complement of S in N is finite). Clearly w(0)=0. The set Ap(S,s)={ w(0),w(1),..., w(s-1)} is called the Apéry set of S with respect to s.

Let a,b,c,d be positive integers such that a/b < c/d, and let I=[a/b,c/d]. Then the set S(I)= N∩ ⋃_n≥ 0 n I is a numerical semigroup. This class of numerical semigroups coincides with that of sets of solutions to equations of the form A x mod B ≤ C x with A,B,C positive integers. A numerical semigroup in this class is said to be proportionally modular. If C = 1, then it is said to be modular.

There are different ways to specify a numerical semigroup S, namely, by its generators; by its gaps, its fundamental or special gaps by its Apéry set, just to name some. In this section we describe functions that may be used to specify, in one of these ways, a numerical semigroup in GAP.

2.1-1 NumericalSemigroup

List is a list of nonnegative integers with greatest common divisor equal to one. These integers may be given as a list or by a sequence of individual elements. The output is the numerical semigroup spanned by List.

String does not need to be present. When it is present, it must be "generators".

		
gap> s1 := NumericalSemigroup(3,5,7);               
<Numerical semigroup with 3 generators>
gap> s2 := NumericalSemigroup([3,5,7]);
<Numerical semigroup with 3 generators>
gap> s3 := NumericalSemigroupByGenerators(3,5,7);             
<Numerical semigroup with 3 generators>
gap> s4 := NumericalSemigroupByGenerators([3,5,7]);
<Numerical semigroup with 3 generators>
gap> s5 := NumericalSemigroup("generators",3,5,7); 
<Numerical semigroup with 3 generators>
gap> s6 := NumericalSemigroup("generators",[3,5,7]);
<Numerical semigroup with 3 generators>
gap> s1=s2;s2=s3;s3=s4;s4=s5;s5=s6;
true
true
true
true
true

2.1-2 NumericalSemigroupBySubAdditiveFunction

A periodic subadditive function with period m is given through the list of images of the integers from 1 to m, [Ros07]. The image of m has to be 0. The output is the numerical semigroup determined by this subadditive function.

In the second form, String must be "subadditive".

gap> s := NumericalSemigroupBySubAdditiveFunction([5,4,2,0]);
<Numerical semigroup>
gap> t := NumericalSemigroup("subadditive",[5,4,2,0]);;     
gap> s=t;
true

2.1-3 NumericalSemigroupByAperyList

List is an Apéry list. The output is the numerical semigroup whose Apéry set with respect to the length of given list is List.

In the second form, String must be "apery".

gap> s:=NumericalSemigroup(3,11);;
gap> ap := AperyListOfNumericalSemigroupWRTElement(s,20);
[ 0, 21, 22, 3, 24, 25, 6, 27, 28, 9, 30, 11, 12, 33, 14, 15, 36, 17, 18, 39 ]
gap> t:=NumericalSemigroupByAperyList(ap);;
gap> r := NumericalSemigroup("apery",ap);;
gap> s=t;t=r;
true
true

2.1-4 NumericalSemigroupBySmallElements

List is the set of small elements of a numerical semigroup, that is, the set of all elements not greater than the conductor. The output is the numerical semigroup with this set of small elements. When no such semigroup exists, an error is returned.

In the second form, String must be "elements".

gap> s:=NumericalSemigroup(3,11);;
gap> se := SmallElements(s);
[ 0, 3, 6, 9, 11, 12, 14, 15, 17, 18, 20 ]
gap> t := NumericalSemigroupBySmallElements(se);;
gap> r := NumericalSemigroup("elements",se);;
gap> s=t;t=r;                                            
true
true
gap> e := [ 0, 3, 6, 9, 11, 14, 15, 17, 18, 20 ];    
[ 0, 3, 6, 9, 11, 14, 15, 17, 18, 20 ]
gap> NumericalSemigroupBySmallElements(e);
Error, The argument does not represent a numerical semigroup called from
<function "NumericalSemigroupBySmallElements">( <arguments> )
 called from read-eval loop at line 35 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

2.1-5 NumericalSemigroupByGaps

List is the set of gaps of a numerical semigroup. The output is the numerical semigroup with this set of gaps. When no semigroup exists with the given set as set of gaps, an error is returned.

In the second form, String must be "gaps".

gap> g := [ 1, 2, 4, 5, 7, 8, 10, 13, 16 ];;
gap> s := NumericalSemigroupByGaps(g);;
gap> t := NumericalSemigroup("gaps",g);;
gap> s=t;
true
gap> h := [ 1, 2, 5, 7, 8, 10, 13, 16 ];;   
gap> NumericalSemigroupByGaps(h);
Error, The argument does not represent the gaps of a numerical semigroup called
 from
<function "NumericalSemigroupByGaps">( <arguments> )
 called from read-eval loop at line 34 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

2.1-6 NumericalSemigroupByFundamentalGaps

List is the set of fundamental gaps of a numerical semigroup, [RGGJM04]. The output is the numerical semigroup determined by these gaps. When the given set contains elements (which will be gaps) that are not fundamental gaps, they are silently removed.

In the second form, String must be "fundamentalgaps".

gap> fg := [ 11, 14, 17, 20, 23, 26, 29, 32, 35 ];;
gap> NumericalSemigroupByFundamentalGaps(fg);
<Numerical semigroup>
gap> NumericalSemigroup("fundamentalgaps",fg);     
<Numerical semigroup>
gap> last=last2;
true
gap> gg := [ 11, 17, 20, 22, 23, 26, 29, 32, 35 ];; #22 is not fundamental
gap> NumericalSemigroup("fundamentalgaps",fg);     
<Numerical semigroup>

2.1-7 NumericalSemigroupByAffineMap

Given three nonnegative integers a, b and c, with a,c>0 and gcd(b,c)=1, this function returns the least (with respect to set order inclusion) numerical semigroup containing c and closed under the map x↦ ax+b. The procedure is explained in [Ugo17].

In the second form, String must be "affinemap".

gap> s:=NumericalSemigroupByAffineMap(3,1,3);
<Numerical semigroup with 3 generators>
gap> SmallElements(s);
[ 0, 3, 6, 9, 10, 12, 13, 15, 16, 18 ]
gap> t:=NumericalSemigroup("affinemap",3,1,3);;
gap> s=t;
true

2.1-8 ModularNumericalSemigroup

Given two positive integers a and b, this function returns a modular numerical semigroup satisfying ax mod b ≤ x, [RGU05].

In the second form, String must be "modular".

gap> ModularNumericalSemigroup(3,7);
<Modular numerical semigroup satisfying 3x mod 7 <= x >
gap> NumericalSemigroup("modular",3,7);  
<Modular numerical semigroup satisfying 3x mod 7 <= x >

2.1-9 ProportionallyModularNumericalSemigroup

Given three positive integers a, b and c, this function returns a proportionally modular numerical semigroup satisfying axmod b ≤ cx, [RAGU03].

In the second form, String must be "propmodular".

gap> ProportionallyModularNumericalSemigroup(3,7,12);
<Proportionally modular numerical semigroup satisfying 3x mod 7 <= 12x >
gap> NumericalSemigroup("propmodular",3,7,12);
<Proportionally modular numerical semigroup satisfying 3x mod 7 <= 12x >

When c=1, the semigroup is seen as a modular numerical semigroup.

gap> NumericalSemigroup("propmodular",67,98,1);
<Modular numerical semigroup satisfying 67x mod 98 <= x >

Numerical semigroups generated by an interval of positive integers are known to be proportionally modular, and thus they are treated as such, since membership and other problems can be solved efficiently for these semigroups.

2.1-10 NumericalSemigroupByInterval

The input is a list of rational numbers defining a closed interval. The output is the semigroup of numerators of all rational numbers in this interval, [RAGU03].

String does not need to be present. When it is present, it must be "interval".

		
gap> NumericalSemigroupByInterval(7/5,5/3);
<Proportionally modular numerical semigroup satisfying 25x mod 35 <= 4x >
gap> NumericalSemigroup("interval",[7/5,5/3]);
<Proportionally modular numerical semigroup satisfying 25x mod 35 <= 4x >
gap> SmallElements(last);
[ 0, 3, 5 ]

2.1-11 NumericalSemigroupByOpenInterval

The input is a list of rational numbers defining an open interval. The output is the semigroup of numerators of all rational numbers in this interval, [RU06].

String does not need to be present. When it is present, it must be "openinterval".

		
gap> NumericalSemigroupByOpenInterval(7/5,5/3);
<Numerical semigroup>
gap> NumericalSemigroup("openinterval",[7/5,5/3]);
<Numerical semigroup>
gap> SmallElements(last);                         
[ 0, 3, 6, 8 ] 

2.2 Some basic tests

This section describes some basic tests on numerical semigroups. The first described tests refer to what the semigroup is currently known to be (not necessarily the way it was created). Then are presented functions to test if a given list represents the small elements, gaps or the Apéry set (see 1.) of a numerical semigroup; to test if an integer belongs to a numerical semigroup and if a numerical semigroup is a subsemigroup of another one.

2.2-1 IsNumericalSemigroup

NS is a numerical semigroup and these attributes are available (their names should be self explanatory).

gap> s:=NumericalSemigroup(3,7);
<Numerical semigroup with 2 generators>
gap> AperyListOfNumericalSemigroupWRTElement(s,30);;
gap> t:=NumericalSemigroupByAperyList(last);
<Numerical semigroup>
gap> IsNumericalSemigroupByGenerators(s);
true
gap> IsNumericalSemigroupByGenerators(t);
false
gap> IsNumericalSemigroupByAperyList(s);
false
gap> IsNumericalSemigroupByAperyList(t);
true

2.2-2 RepresentsSmallElementsOfNumericalSemigroup

Tests if the list L (which has to be a set) may represent the ``small" elements of a numerical semigroup.

gap> L:=[ 0, 3, 6, 9, 11, 12, 14, 15, 17, 18, 20 ];
[ 0, 3, 6, 9, 11, 12, 14, 15, 17, 18, 20 ]
gap> RepresentsSmallElementsOfNumericalSemigroup(L);
true
gap> L:=[ 6, 9, 11, 12, 14, 15, 17, 18, 20 ];
[ 6, 9, 11, 12, 14, 15, 17, 18, 20 ]
gap> RepresentsSmallElementsOfNumericalSemigroup(L);
false

2.2-3 RepresentsGapsOfNumericalSemigroup

Tests if the list L may represent the gaps (see 1.) of a numerical semigroup.

gap> s:=NumericalSemigroup(3,7);
<Numerical semigroup with 2 generators>
gap> L:=GapsOfNumericalSemigroup(s);
[ 1, 2, 4, 5, 8, 11 ]
gap> RepresentsGapsOfNumericalSemigroup(L);
true
gap> L:=Set(List([1..21],i->RandomList([1..50])));
[ 2, 6, 7, 8, 10, 12, 14, 19, 24, 28, 31, 35, 42, 50 ]
gap> RepresentsGapsOfNumericalSemigroup(L);
false

2.2-4 IsAperyListOfNumericalSemigroup

Tests whether a list L of integers may represent the Apéry list of a numerical semigroup. It returns true when the periodic function represented by L is subadditive (see RepresentsPeriodicSubAdditiveFunction (A.2-1)) and the remainder of the division of L[i] by the length of L is i and returns false otherwise (the criterium used is the one explained in [Ros96b]).

gap> IsAperyListOfNumericalSemigroup([0,21,7,28,14]);
true

2.2-5 IsSubsemigroupOfNumericalSemigroup

S and T are numerical semigroups. Tests whether T is contained in S.

gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> T:=NumericalSemigroup(2,3);
<Numerical semigroup with 2 generators>
gap> IsSubsemigroupOfNumericalSemigroup(T,S);
true
gap> IsSubsemigroupOfNumericalSemigroup(S,T);
false

2.2-6 IsSubset

S is a numerical semigroup. T can be a numerical semigroup, in which case the function is just a synonym of IsSubsemigroupOfNumericalSemigroup (2.2-5), or a list of integers, in which case tests whether all elements of the list belong to S.

gap> ns1 := NumericalSemigroup(5,7);;
gap> ns2 := NumericalSemigroup(5,7,11);;
gap> IsSubset(ns1,ns2);
false
gap> IsSubset(ns2,[5,15]);
true
gap> IsSubset(ns1,[5,11]);
false
gap> IsSubset(ns2,ns1);   
true

2.2-7 BelongsToNumericalSemigroup

n is an integer and S is a numerical semigroup. Tests whether n belongs to S. \in(n,S) calls the infix variant n in S, and both can be seen as a short for BelongsToNumericalSemigroup(n,S). Several methods are implemented for membership, depending on the properties of S known. For instance, there are methods if any of the following information is known: Apéry set, small elements, defining (proportionally) modular Diophantine equation, fundamental gaps, gaps, generators.

gap> S := NumericalSemigroup("modular", 5,53);
<Modular numerical semigroup satisfying 5x mod 53 <= x >
gap> BelongsToNumericalSemigroup(15,S);
false
gap> 15 in S;
false
gap> SmallElementsOfNumericalSemigroup(S);
[ 0, 11, 12, 13, 22, 23, 24, 25, 26, 32, 33, 34, 35, 36, 37, 38, 39, 43 ]
gap> BelongsToNumericalSemigroup(13,S);
true
gap> 13 in S;
true

generated by GAPDoc2HTML