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] 

5 Constructing numerical semigroups from others
 5.1 Adding and removing elements of a numerical semigroup
 5.2 Intersections and quotients by integers
 5.3 Constructing the set of all numerical semigroups containing a given numerical semigroup
 5.4 Constructing the set of numerical semigroup with given Frobenius number
 5.5 Constructing the set of numerical semigroups with genus g, that is, numerical semigroups with exactly g gaps
 5.6 Constructing the set of numerical semigroups with a given set of pseudo-Frobenius numbers

5 Constructing numerical semigroups from others

5.1 Adding and removing elements of a numerical semigroup

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]).

5.1-1 RemoveMinimalGeneratorFromNumericalSemigroup
‣ RemoveMinimalGeneratorFromNumericalSemigroup( n, S )( function )

S is a numerical semigroup and n is one if its minimal generators.

The output is the numerical semigroup S ∖{n} (see [RGGJ03]; S∖{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 ]

                        

5.1-2 AddSpecialGapOfNumericalSemigroup
‣ AddSpecialGapOfNumericalSemigroup( g, S )( function )

S is a numerical semigroup and g is a special gap of S

The output is the numerical semigroup S ∪{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

                        

5.2 Intersections and quotients by integers

5.2-1 IntersectionOfNumericalSemigroups
‣ 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);
<Modular numerical semigroup satisfying 17x mod 34 <= x >
gap> SmallElementsOfNumericalSemigroup(S);
[ 0, 11, 12, 13, 22, 23, 24, 25, 26, 32, 33, 34, 35, 36, 37, 38, 39, 43 ]
gap> SmallElementsOfNumericalSemigroup(T);
[ 0, 2, 4, 6, 8, 10, 12, 14, 16 ]
gap> IntersectionOfNumericalSemigroups(S,T);
<Numerical semigroup>
gap> SmallElementsOfNumericalSemigroup(last);
[ 0, 12, 22, 23, 24, 25, 26, 32, 33, 34, 35, 36, 37, 38, 39, 43 ]

5.2-2 QuotientOfNumericalSemigroup
‣ QuotientOfNumericalSemigroup( S, n )( function )

S is a numerical semigroup and n is an integer. Computes the quotient of S by n, that is, the set { x∈ N | nx ∈ S}, which is again a numerical semigroup. S / n may be used as a short for QuotientOfNumericalSemigroup(S, n).

gap> s:=NumericalSemigroup(3,29);
<Modular numerical semigroup satisfying 58x mod 87 <= x >
gap> SmallElementsOfNumericalSemigroup(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> SmallElementsOfNumericalSemigroup(t);
[ 0, 3, 5, 6, 8 ]
gap> u := s / 7;
<Numerical semigroup>
gap> SmallElementsOfNumericalSemigroup(u);
[ 0, 3, 5, 6, 8 ]

5.3 Constructing the set of all numerical semigroups containing a given numerical semigroup

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∪{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 this new numerical semigroups until we reach N.

These procedures are described in [RGGJ03].

5.3-1 OverSemigroupsNumericalSemigroup
‣ OverSemigroupsNumericalSemigroup( s )( function )

s is a numerical semigroup. The output is the set of numerical semigroups containing it.

gap> OverSemigroupsNumericalSemigroup(NumericalSemigroup(3,5,7));
[ <The numerical semigroup N>, <Numerical semigroup>, <Numerical semigroup>, 
  <Numerical semigroup with 3 generators> ]
gap> List(last,s->MinimalGeneratingSystemOfNumericalSemigroup(s));
[ [ 1 ], [ 2, 3 ], [ 3 .. 5 ], [ 3, 5, 7 ] ]

5.4 Constructing the set of numerical semigroup with given Frobenius number

5.4-1 NumericalSemigroupsWithFrobeniusNumber
‣ NumericalSemigroupsWithFrobeniusNumber( f )( function )

f is an non zero integer greater than or equal to -1. The output is the set of numerical semigroups with Frobenius number f. The algorithm implemented is given in [RGGM04].

gap> Length(NumericalSemigroupsWithFrobeniusNumber(20));
900

                        

5.5 Constructing the set of numerical semigroups with genus g, that is, numerical semigroups with exactly g gaps

Given a numerical semigroup of genus g, 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].

5.5-1 NumericalSemigroupsWithGenus
‣ NumericalSemigroupsWithGenus( g )( function )

g is a nonnegative integer. The output is the set of numerical semigroups with genusg.

gap> NumericalSemigroupsWithGenus(5);
[ <Proportionally modular numerical semigroup satisfying 11x mod 66 <= 5x >, 
  <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>, 
  <Modular numerical semigroup satisfying 11x mod 22 <= x > ]
gap> List(last,MinimalGeneratingSystemOfNumericalSemigroup);
[ [ 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 ] ]

5.6 Constructing the set of numerical semigroups with a given set of pseudo-Frobenius numbers

Refer to PseudoFrobeniusOfNumericalSemigroup (3.2-4).

These procedures are described in [{{{15].

5.6-1 ForcedIntegersForPseudoFrobenius
‣ ForcedIntegersForPseudoFrobenius( PF )( function )

PF is a list of positive integers (given as a list or individual elements). The output is:

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 ] ]

5.6-2 SimpleForcedIntegersForPseudoFrobenius
‣ SimpleForcedIntegersForPseudoFrobenius( fg, fe, PF )( function )

Is just a quicker version of ForcedIntegersForPseudoFrobenius (5.6-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:

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 ] ]

5.6-3 NumericalSemigroupsWithPseudoFrobeniusNumbers
‣ NumericalSemigroupsWithPseudoFrobeniusNumbers( g )( function )

PF is a list of positive integers (given as a list or individual elements). The output is: a list of numerical semigrups S such that PF(S)=PF When Length(PF)=1, it makes use of the function NumericalSemigroupsWithFrobeniusNumber (5.4-1)

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,MinimalGeneratingSystemOfNumericalSemigroup);   
[ [ 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 ] ]

5.6-4 RandomNumericalSemigroupWithPseudoFrobeniusNumbers
‣ RandomNumericalSemigroupWithPseudoFrobeniusNumbers( g )( 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" option The output is: A numerical semigrups S such that PF(S)=PF, at random. Returns fail if it conludes that it exists and suggets to use NumericalSemigroupsWithPseudoFrobeniusNumbers if it is not able to conclude...

It makes use of the function AnIrreducibleNumericalSemigroupWithFrobeniusNumber (6.1-4), when Length(PF)=1.

gap> pf := [ 83, 169, 173, 214, 259 ];;                     
gap> RandomNumericalSemigroupWithPseudoFrobeniusNumbers(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 ]
 [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