Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 A B C Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

2 Numerical Semigroups
 2.1 Generating Numerical Semigroups
 2.2 Some basic tests

2 Numerical Semigroups

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

2.1 Generating Numerical Semigroups

Recalling 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.

To create a numerical semigroup in GAP the function NumericalSemigroup is used.

2.1-1 NumericalSemigroup
‣ NumericalSemigroup( Representation, List )( function )

Representation

May be "generators", "minimalgenerators", "modular", "propmodular", "elements", "gaps", "fundamentalgaps", "subadditive" or "apery" according to whether the semigroup is to be given by means of a system of generators, a minimal system of generators, a condition of the form ax mod m le x, a condition of the form ax mod mle cx, a set of all elements up to the conductor, the set of gaps, the set of fundamental gaps, a periodic subaditive function, or the Apéry set.

When no string is given as first argument it is assumed that the numerical semigroup will be given by means of a set of generators.

List

When the semigroup is given through a set of generators, this set may be given as a list or through its individual elements.

The set of all elements up to the conductor, the set of gaps, the set of fundamental gaps or the Apéry set are given through lists.

A periodic subadditive function with period m is given through the list of images of the elements, from 1 to m. The image of m has to be 0.

Numerical semigroups generated by an interval of positive integers and embedding dimension two numerical semigroups are known to be proportionally modular, and thus they are treated as such (unles the representation "minimalgenerators" is specified), since membership and other problems are solved faster for these semigroups.

gap> s1 := NumericalSemigroup("generators",3,5,7);
<Numerical semigroup with 3 generators>
gap> s2 := NumericalSemigroup("generators",[3,5,7]);
<Numerical semigroup with 3 generators>
gap> s1=s2;
true
gap> s := NumericalSemigroup("minimalgenerators",3,7);
<Numerical semigroup with 2 generators>
gap> s := NumericalSemigroup("modular",3,5);
<Modular numerical semigroup satisfying 3x mod 5 <= x >
gap> s1:=NumericalSemigroup("generators",2,5);       
<Modular numerical semigroup satisfying 5x mod 10 <= x >
gap> s = s1;
true
gap> s:=NumericalSemigroup(4,5,6);
<Proportionally modular numerical semigroup satisfying 6x mod 24 <= 2x >

Once it is known that a numerical semigroup contains the element 1, i.e. the semigroup is N, the semigroup is treated as such.

gap> NumericalSemigroup(1);
<The numerical semigroup N>
gap> NumericalSemigroupByInterval(1/3,1/2);
<The numerical semigroup N>
 

2.1-2 ModularNumericalSemigroup
‣ ModularNumericalSemigroup( a, b )( function )

Given two positive integers a and b, this function returns a modular numerical semigroup satisfying ax mod b le x.

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

2.1-3 ProportionallyModularNumericalSemigroup
‣ ProportionallyModularNumericalSemigroup( a, b, c )( function )

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

gap> ProportionallyModularNumericalSemigroup(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 >

2.1-4 NumericalSemigroupByGenerators
‣ NumericalSemigroupByGenerators( List )( function )
‣ NumericalSemigroupByMinimalGenerators( List )( function )
‣ NumericalSemigroupByMinimalGeneratorsNC( List )( function )
‣ NumericalSemigroupByInterval( List )( function )
‣ NumericalSemigroupByOpenInterval( List )( function )
‣ NumericalSemigroupBySubAdditiveFunction( List )( function )
‣ NumericalSemigroupByAperyList( List )( function )
‣ NumericalSemigroupBySmallElements( List )( function )
‣ NumericalSemigroupByGaps( List )( function )
‣ NumericalSemigroupByFundamentalGaps( List )( function )

The function NumericalSemigroup (2.1-1) is a front-end for these functions. The argument of each of these functions is a list representing an entity of the type to which the function's name refers.

gap> s:=NumericalSemigroup(3,11);
<Modular numerical semigroup satisfying 22x mod 33 <= x >
gap> GapsOfNumericalSemigroup(s);
[ 1, 2, 4, 5, 7, 8, 10, 13, 16, 19 ]
gap> t:=NumericalSemigroupByGaps(last);
<Numerical semigroup>
gap> s=t;
true

gap> AperyListOfNumericalSemigroupWRTElement(s,20);;
gap> t:=NumericalSemigroupByAperyList(last);
<Numerical semigroup>
gap> s=t;
true

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
‣ IsNumericalSemigroup( NS )( attribute )
‣ IsNumericalSemigroupByGenerators( NS )( attribute )
‣ IsNumericalSemigroupByMinimalGenerators( NS )( attribute )
‣ IsNumericalSemigroupByInterval( NS )( attribute )
‣ IsNumericalSemigroupByOpenInterval( NS )( attribute )
‣ IsNumericalSemigroupBySubAdditiveFunction( NS )( attribute )
‣ IsNumericalSemigroupByAperyList( NS )( attribute )
‣ IsNumericalSemigroupBySmallElements( NS )( attribute )
‣ IsNumericalSemigroupByGaps( NS )( attribute )
‣ IsNumericalSemigroupByFundamentalGaps( NS )( attribute )
‣ IsProportionallyModularNumericalSemigroup( NS )( attribute )
‣ IsModularNumericalSemigroup( NS )( attribute )

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

gap> s:=NumericalSemigroup(3,7);
<Modular numerical semigroup satisfying 7x mod 21 <= x >
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
‣ RepresentsSmallElementsOfNumericalSemigroup( L )( attribute )

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
‣ RepresentsGapsOfNumericalSemigroup( L )( attribute )

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

gap> s:=NumericalSemigroup(3,7);
<Modular numerical semigroup satisfying 7x mod 21 <= x >
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
‣ IsAperyListOfNumericalSemigroup( L )( function )

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
‣ IsSubsemigroupOfNumericalSemigroup( S, T )( function )

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);
<Modular numerical semigroup satisfying 3x mod 6 <= x >
gap> IsSubsemigroupOfNumericalSemigroup(T,S);
true
gap> IsSubsemigroupOfNumericalSemigroup(S,T);
false

2.2-6 BelongsToNumericalSemigroup
‣ BelongsToNumericalSemigroup( n, S )( operation )

n is an integer and S is a numerical semigroup. Tests whether n belongs to S. n in S is the short for BelongsToNumericalSemigroup(n,S).

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
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 A B C Bib Ind

generated by GAPDoc2HTML