chap5.txt

  
  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 [RGSGGJM03]).
  
  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 [RGSGGJM03]; S∖{n} is a
  numerical semigroup if and only if n is a minimal generator of S).
  
    Example  
    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 [RGSGGJM03], where it is
  explained why this set is a numerical semigroup).
  
    Example  
    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 and multiples by integers
  
  5.2-1 Intersection
  
  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).
  
    Example  
    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> IntersectionOfNumericalSemigroups(S,T);
    <Numerical semigroup>
    gap> SmallElements(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, n )  operation
  
  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).
  
    Example  
    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 ]
  
  
  5.2-3 MultipleOfNumericalSemigroup
  
  MultipleOfNumericalSemigroup( S, a, b )  function
  
  S is a numerical semigroup, and a and b are positive integers. Computes a S∪
  {b,b+1,->}.  If  b  is  smaller  than a c, with c the conductor of S, then a
  warning is displayed.
  
    Example  
    gap> N:=NumericalSemigroup(1);;
    gap> s:=MultipleOfNumericalSemigroup(N,4,20);;
    gap> SmallElements(s);
    [ 0, 4, 8, 12, 16, 20 ]
  
  
  5.2-4 Difference
  
  Difference( S, T )  operation
  DifferenceOfNumericalSemigroups( S, T )  function
  
  S, T are numerical semigroups. The output is the set S∖ T.
  
    Example  
    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 ]
  
  
  5.2-5 NumericalDuplication
  
  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∪ (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⊆ S). Computes 2S∪ (2E+b).
  
    Example  
    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 ]
  
  
  5.2-6 InductiveNumericalSemigroup
  
  InductiveNumericalSemigroup( S, a, b )  function
  
  S is a numerical semigroup, and a and b are lists of positive integers, such
  that  b[i+1]ge  a[i]b[i].  Computes  inductively  S_0=  N and S_i+1=a[i]S_i∪
  {a[i]b[i],a[i]b[i]+1,->}, and returns S_k, with k the length of a and b.
  
    Example  
    gap> s:=InductiveNumericalSemigroup([4,2],[5,23]);;
    gap> SmallElements(s);
    [ 0, 8, 16, 24, 32, 40, 42, 44, 46 ]
  
  
  
  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 [RGSGGJM03].
  
  5.3-1 OverSemigroupsNumericalSemigroup
  
  OverSemigroupsNumericalSemigroup( s )  function
  
  s  is  a  numerical semigroup. The output is the set of numerical semigroups
  containing it.
  
    Example  
    gap> OverSemigroupsNumericalSemigroup(NumericalSemigroup(3,5,7));
    [ <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 ] ]
  
  
  
  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 [RGSGGJM04].
  
    Example  
    gap> Length(NumericalSemigroupsWithFrobeniusNumber(15));
    200
  
  
  
  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 [RGSGGB03] and [BA08].
  
  5.5-1 NumericalSemigroupsWithGenus
  
  NumericalSemigroupsWithGenus( g )  function
  
  g  is  a  nonnegative integer. The output is the set of numerical semigroups
  with genus g.
  
    Example  
    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 ] ]
  
  
  
  5.6  Constructing  the  set  of  numerical  semigroups  with  a given set of
  pseudo-Frobenius numbers
  
  Refer to PseudoFrobeniusOfNumericalSemigroup (3.1-16).
  
  These procedures are described in [DGSRP16].
  
  5.6-1 ForcedIntegersForPseudoFrobenius
  
  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  N  -  S  for any numerical
                    semigroup S such that PF(S)={g_1,...,g_n}
  
                  forced_elts  is contained in S for any numerical semigroup
                    S such that PF(S)={g_1,...,g_n}
  
      "fail" in case it is found some condition that fails.
  
    Example  
    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:
  
      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  N  -  S  for any numerical
                    semigroup S such that PF(S)={g_1,...,g_n}
  
                  forced_elts  is contained in S for any numerical semigroup
                    S such that PF(S)={g_1,...,g_n}
  
      "fail" in case it is found some condition that fails.
  
    Example  
    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 semigroups S such that PF(S)=PF. When
  Length(PF)=1,       it       makes       use       of      the      function
  NumericalSemigroupsWithFrobeniusNumber (5.4-1)
  
    Example  
    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 ] ]
  
  
  5.6-4 ANumericalSemigroupWithPseudoFrobeniusNumbers
  
  ANumericalSemigroupWithPseudoFrobeniusNumbers( 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 semigroup S such that PF(S)=PF. Returns
  fail    if   it   concludes   that   it   exists   and   suggests   to   use
  NumericalSemigroupsWithPseudoFrobeniusNumbers   if   it   is   not  able  to
  conclude...
  
  It           makes           use           of          the          function
  AnIrreducibleNumericalSemigroupWithFrobeniusNumber       (6.1-4),       when
  Length(PF)=1 or Length(PF)=2 and 2*PF[1] = PF[2].
  
    Example  
    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 ]