chap2.txt

  
  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 NumericalSemigroupByGenerators
  
  NumericalSemigroupByGenerators( List )  function
  NumericalSemigroup( String, List )  function
  
  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".
  
    Example  
    gap> s1 := NumericalSemigroupByGenerators(3,5,7);             
    <Numerical semigroup with 3 generators>
    gap> s2 := NumericalSemigroupByGenerators([3,5,7]);
    <Numerical semigroup with 3 generators>
    gap> s3 := NumericalSemigroup("generators",3,5,7); 
    <Numerical semigroup with 3 generators>
    gap> s4 := NumericalSemigroup("generators",[3,5,7]);
    <Numerical semigroup with 3 generators>
    gap> s5 := NumericalSemigroup(3,5,7);               
    <Numerical semigroup with 3 generators>
    gap> s6 := NumericalSemigroup([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
  
  NumericalSemigroupBySubAdditiveFunction( List )  function
  NumericalSemigroup( String, List )  function
  
  A  periodic  subadditive function with period m is given through the list of
  images  of  the integers from 1 to m. 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".
  
    Example  
    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
  
  NumericalSemigroupByAperyList( List )  function
  NumericalSemigroup( String, List )  function
  
  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".
  
    Example  
    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
  
  NumericalSemigroupBySmallElements( List )  function
  NumericalSemigroup( String, List )  function
  
  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".
  
    Example  
    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
  
  NumericalSemigroupByGaps( List )  function
  NumericalSemigroup( String, List )  function
  
  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".
  
    Example  
    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
  
  NumericalSemigroupByFundamentalGaps( List )  function
  NumericalSemigroup( String, List )  function
  
  List  is the set of fundamental gaps of a numerical semigroup. 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".
  
    Example  
    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
  
  NumericalSemigroupByAffineMap( a, b, c )  function
  NumericalSemigroup( String, a, b )  function
  
  Given three nonnegative integers a, b and c, with a,c>0 and gcd(b,c)=1, this
  function  returns the least (with restpect to set order inclusion) numerical
  semigroup  containing  c  and closed under the map x↦ ax+b. The procedure is
  explained in [Ugo16].
  
  In the second form, String must be "affinemap".
  
    Example  
    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
  
  ModularNumericalSemigroup( a, b )  function
  NumericalSemigroup( String, a, b )  function
  
  Given  two  positive  integers  a  and  b,  this  function returns a modular
  numerical semigroup satisfying ax mod b le x.
  
  In the second form, String must be "modular".
  
    Example  
    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
  
  ProportionallyModularNumericalSemigroup( a, b, c )  function
  NumericalSemigroup( String, a, b )  function
  
  Given  three  positive  integers  a,  b  and  c,  this  function  returns  a
  proportionally modular numerical semigroup satisfying axmod b le cx.
  
  In the second form, String must be "propmodular".
  
    Example  
    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.
  
    Example  
    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
  
  NumericalSemigroupByInterval( List )  function
  NumericalSemigroup( String, List )  function
  
  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.
  
  String  does  not  need  to  be  present.  When  it  is  present, it must be
  "interval".
  
    Example  
    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
  
  NumericalSemigroupByOpenInterval( List )  function
  NumericalSemigroup( String, List )  function
  
  The input is a list of rational numbers defining a open interval. The output
  is the semigroup of numerators of all rational numbers in this interval.
  
  String  does  not  need  to  be  present.  When  it  is  present, it must be
  "openinterval".
  
    Example  
    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
  
  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).
  
    Example  
    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
  
  RepresentsSmallElementsOfNumericalSemigroup( L )  attribute
  
  Tests  if  the  list  L  (which  has to be a set) may represent the ``small"
  elements of a numerical semigroup.
  
    Example  
    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.
  
    Example  
    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
  
  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]).
  
    Example  
    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.
  
    Example  
    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
  
  IsSubset( S, T )  attribute
  
  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.
  
    Example  
    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
  
  BelongsToNumericalSemigroup( n, S )  operation
  \in( n, S )  operation
  
  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).
  
    Example  
    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