chap3.txt

  
  3 Basic operations with numerical semigroups
  
  
  3.1 Invariants
  
  3.1-1 Multiplicity
  
  Multiplicity( NS )  attribute
  MultiplicityOfNumericalSemigroup( NS )  attribute
  
  NS  is  a  numerical semigroup. Returns the multiplicity of NS, which is the
  smallest positive integer belonging to NS.
  
    Example  
    gap> S := NumericalSemigroup("modular", 7,53);
    <Modular numerical semigroup satisfying 7x mod 53 <= x >
    gap> MultiplicityOfNumericalSemigroup(S);
    8
    gap> NumericalSemigroup(3,5);
    <Numerical semigroup with 2 generators>
    gap> Multiplicity(last);
    3
  
  
  3.1-2 GeneratorsOfNumericalSemigroup
  
  GeneratorsOfNumericalSemigroup( S )  attribute
  Generators( S )  attribute
  MinimalGeneratingSystemOfNumericalSemigroup( S )  attribute
  MinimalGeneratingSystem( S )  attribute
  MinimalGenerators( S )  attribute
  
  S  is a numerical semigroup. GeneratorsOfNumericalSemigroup returns a set of
  generators      of      S,      which      may      not      be     minimal.
  MinimalGeneratingSystemOfNumericalSemigroup   returns  the  minimal  set  of
  generators of S.
  
  From  Version 0.980, ReducedSetOfGeneratorsOfNumericalSemigroup is a synonym
  of                              MinimalGeneratingSystemOfNumericalSemigroup;
  GeneratorsOfNumericalSemigroupNC        is        a        synonym        of
  GeneratorsOfNumericalSemigroup.  The  names  are kept for compatibility with
  code produced for previous versions, but will be removed in the future.
  
    Example  
    gap> S := NumericalSemigroup("modular", 5,53);
    <Modular numerical semigroup satisfying 5x mod 53 <= x >
    gap> GeneratorsOfNumericalSemigroup(S);
    [ 11, 12, 13, 32, 53 ]
    gap> S := NumericalSemigroup(3, 5, 53);
    <Numerical semigroup with 3 generators>
    gap> GeneratorsOfNumericalSemigroup(S);
    [ 3, 5, 53 ]
    gap> MinimalGeneratingSystemOfNumericalSemigroup(S);
    [ 3, 5 ]
    gap> MinimalGeneratingSystem(S)=MinimalGeneratingSystemOfNumericalSemigroup(S);
    true
    gap> s := NumericalSemigroup(3,5,7,15);
    <Numerical semigroup with 4 generators>
    gap> HasGenerators(s);
    true
    gap> HasMinimalGenerators(s);
    false
    gap> MinimalGenerators(s);
    [ 3, 5, 7 ]
    gap> Generators(s);
    [ 3, 5, 7, 15 ]
  
  
  3.1-3 EmbeddingDimension
  
  EmbeddingDimension( NS )  attribute
  EmbeddingDimensionOfNumericalSemigroup( NS )  attribute
  
  NS  is  a  numerical  semigroup.  It  returns the cardinality of its minimal
  generating system.
  
    Example  
    gap> s := NumericalSemigroup(3,5,7,15);
    <Numerical semigroup with 4 generators>
    gap> EmbeddingDimension(s);
    3
    gap> EmbeddingDimensionOfNumericalSemigroup(s);
    3
  
  
  3.1-4 SmallElements
  
  SmallElements( NS )  attribute
  SmallElementsOfNumericalSemigroup( NS )  attribute
  
  NS is a numerical semigroup. It returns the list of small elements of NS. Of
  course,  the  time  consumed  to  return  a result may depend on the way the
  semigroup is given.
  
    Example  
    gap> SmallElementsOfNumericalSemigroup(NumericalSemigroup(3,5,7));
    [ 0, 3, 5 ]
    gap> SmallElements(NumericalSemigroup(3,5,7));
    [ 0, 3, 5 ]
  
  
  3.1-5 FirstElementsOfNumericalSemigroup
  
  FirstElementsOfNumericalSemigroup( n, NS )  function
  
  NS  is  a numerical semigroup. It returns the list with the first n elements
  of NS.
  
    Example  
    gap> FirstElementsOfNumericalSemigroup(2,NumericalSemigroup(3,5,7));
    [ 0, 3 ]
    gap> FirstElementsOfNumericalSemigroup(10,NumericalSemigroup(3,5,7));
    [ 0, 3, 5, 6, 7, 8, 9, 10, 11, 12 ]
  
  
  3.1-6 RthElementOfNumericalSemigroup
  
  RthElementOfNumericalSemigroup( S, r )  operation
  
  S  is a numerical semigroup and r is an integer. It returns the r-th element
  of S.
  
    Example  
    gap> S := NumericalSemigroup(7,8,17);;
    gap> RthElementOfNumericalSemigroup(S,53);
    68
  
  
  3.1-7 AperyList
  
  AperyList( S, n )  attribute
  AperyListOfNumericalSemigroupWRTElement( S, n )  operation
  
  S  is  a  numerical semigroup and n is a positive element of S. Computes the
  Apéry  list of S with respect to n. It contains for every i∈ {0,...,n-1}, in
  the  i+1th  position, the smallest element in the semigroup congruent with i
  modulo n.
  
    Example  
    gap> S := NumericalSemigroup("modular", 5,53);;
    gap> AperyListOfNumericalSemigroupWRTElement(S,12);
    [ 0, 13, 26, 39, 52, 53, 54, 43, 32, 33, 22, 11 ]
    gap> AperyList(S,12);
    [ 0, 13, 26, 39, 52, 53, 54, 43, 32, 33, 22, 11 ]
  
  
  3.1-8 AperyList
  
  AperyList( S )  attribute
  AperyListOfNumericalSemigroup( S )  attribute
  
  S  is a numerical semigroup. It computes the Apéry list of S with respect to
  the multiplicity of S.
  
    Example  
    gap> S := NumericalSemigroup("modular", 5,53);;
    gap> AperyListOfNumericalSemigroup(S);
    [ 0, 12, 13, 25, 26, 38, 39, 51, 52, 53, 32 ]
    gap> AperyList(NumericalSemigroup(5,7,11));
    [ 0, 11, 7, 18, 14 ]
  
  
  3.1-9 AperyList
  
  AperyList( S, n )  attribute
  AperyListOfNumericalSemigroupWRTInteger( S, m )  function
  
  S is a numerical semigroup and m is an integer. Computes the Apéry list of S
  with  respect to m, that is, the set of elements x in S such that x-m is not
  in    S.    If    m   is   an   element   in   S,   then   the   output   of
  AperyListOfNumericalSemigroupWRTInteger,   as   sets,   is   the   same   as
  AperyListOfNumericalSemigroupWRTElement, though without side effects, in the
  sense  that this information is no longer used by the package. The output of
  AperyList is the same as AperyListOfNumericalSemigroupWRTElement.
  
    Example  
    gap>  s:=NumericalSemigroup(10,13,19,27);;
    gap> AperyListOfNumericalSemigroupWRTInteger(s,11);
    [ 0, 10, 13, 19, 20, 23, 26, 27, 29, 32, 33, 36, 39, 42, 45, 46, 52, 55 ]
    gap> AperyList(s,11);
    [ 0, 10, 13, 19, 20, 23, 26, 27, 29, 32, 33, 36, 39, 42, 45, 46, 52, 55 ]
    gap> Length(last);
    18
    gap> AperyListOfNumericalSemigroupWRTInteger(s,10);
    [ 0, 13, 19, 26, 27, 32, 38, 45, 51, 54 ]
    gap> AperyListOfNumericalSemigroupWRTElement(s,10);
    [ 0, 51, 32, 13, 54, 45, 26, 27, 38, 19 ]
    gap> Length(last);
    10
    gap> AperyList(s,10);
    [ 0, 51, 32, 13, 54, 45, 26, 27, 38, 19 ]
  
  
  3.1-10 AperyListOfNumericalSemigroupAsGraph
  
  AperyListOfNumericalSemigroupAsGraph( ap )  function
  
  ap  is  the  Apéry  list of a numerical semigroup. This function returns the
  adjacency  list of the graph (ap, E) where the edge u -> v is in E iff v - u
  is in ap. The 0 is ignored.
  
    Example  
    gap> s:=NumericalSemigroup(3,7);;
    gap> AperyListOfNumericalSemigroupWRTElement(s,10);
    [ 0, 21, 12, 3, 14, 15, 6, 7, 18, 9 ]
    gap> AperyListOfNumericalSemigroupAsGraph(last);
    [ ,, [ 3, 6, 9, 12, 15, 18, 21 ],,, [ 6, 9, 12, 15, 18, 21 ],
    [ 7, 14, 21 ],, [ 9, 12, 15, 18, 21 ],,, [ 12, 15, 18, 21 ],,
    [ 14, 21 ], [ 15, 18, 21 ],,, [ 18, 21 ],,, [ 21 ] ]
  
  
  3.1-11 KunzCoordinatesOfNumericalSemigroup
  
  KunzCoordinatesOfNumericalSemigroup( S, m )  function
  
  S  is  a  numerical  semigroup,  and m is a nonzero element of S. The second
  argument is optional, and if missing it is assumed to be the multiplicity of
  S.
  
  Then the Apéry set of m in S has the form [0,k_1m+1,...,k_m-1m+m-1], and the
  output is the (m-1)-uple [k_1,k_2,...,k_m-1]
  
    Example  
    gap> s:=NumericalSemigroup(3,5,7);
    <Numerical semigroup with 3 generators>
    gap> KunzCoordinatesOfNumericalSemigroup(s);
    [ 2, 1 ]
    gap> KunzCoordinatesOfNumericalSemigroup(s,5);
    [ 1, 1, 0, 1 ]
  
  
  3.1-12 KunzPolytope
  
  KunzPolytope( m )  function
  
  m is a positive integer.
  
  The  Kunz coordinates of the semigroups with multiplicity m are solutions of
  a  system  of  inequalities Axge b (see [CAGGB02]). The output is the matrix
  (A|-b).
  
    Example  
    gap> KunzPolytope(3);
    [ [ 1, 0, -1 ], [ 0, 1, -1 ], [ 2, -1, 0 ], [ -1, 2, 1 ] ]
  
  
  3.1-13 CocycleOfNumericalSemigroupWRTElement
  
  CocycleOfNumericalSemigroupWRTElement( S, m )  function
  
  S  is  a numerical semigroup, and m is a nonzero element of S. The output is
  the  matrix  h(i,j)=(w(i)+w(j)-w((i+j)mod  m))/m, where w(i) is the smallest
  element  in  S congruent with i modulo m (and thus it is in the Apéry set of
  m), [GSHKR17].
  
    Example  
    gap> s:=NumericalSemigroup(3,5,7);;
    gap> CocycleOfNumericalSemigroupWRTElement(s,3);
    [ [ 0, 0, 0 ], [ 0, 3, 4 ], [ 0, 4, 1 ] ]
  
  
  3.1-14 FrobeniusNumber
  
  FrobeniusNumber( NS )  attribute
  FrobeniusNumberOfNumericalSemigroup( NS )  attribute
  
  The  largest nonnegative integer not belonging to a numerical semigroup S is
  the  Frobenius  number  of  S. If S is the set of nonnegative integers, then
  clearly its Frobenius number is -1, otherwise its Frobenius number coincides
  with the maximum of the gaps (or fundamental gaps) of S.
  
  NS  is  a  numerical  semigroup.  It  returns the Frobenius number of NS. Of
  course,  the  time  consumed  to  return  a result may depend on the way the
  semigroup is given or on the knowledge already produced on the semigroup.
  
    Example  
    gap> FrobeniusNumberOfNumericalSemigroup(NumericalSemigroup(3,5,7));
    4
    gap> FrobeniusNumber(NumericalSemigroup(3,5,7));
    4
  
  
  3.1-15 Conductor
  
  Conductor( NS )  attribute
  ConductorOfNumericalSemigroup( NS )  attribute
  
  This is just a synonym of  FrobeniusNumberOfNumericalSemigroup (NS)+1.
  
    Example  
    gap> ConductorOfNumericalSemigroup(NumericalSemigroup(3,5,7));
    5
    gap> Conductor(NumericalSemigroup(3,5,7));
    5
  
  
  3.1-16 PseudoFrobeniusOfNumericalSemigroup
  
  PseudoFrobeniusOfNumericalSemigroup( S )  attribute
  
  An integer z is a pseudo-Frobenius number of S if z+S∖{0}⊆ S.
  
  S is a numerical semigroup. It returns set of pseudo-Frobenius numbers of S.
  
    Example  
    gap> S := NumericalSemigroup("modular", 5,53);
    <Modular numerical semigroup satisfying 5x mod 53 <= x >
    gap> PseudoFrobeniusOfNumericalSemigroup(S);
    [ 21, 40, 41, 42 ]
  
  
  3.1-17 TypeOfNumericalSemigroup
  
  TypeOfNumericalSemigroup( NS )  attribute
  
  Stands for Length(PseudoFrobeniusOfNumericalSemigroup (NS)).
  
    Example  
    gap> S := NumericalSemigroup("modular", 5,53);
    <Modular numerical semigroup satisfying 5x mod 53 <= x >
    gap> Type(S);
    4
    gap> TypeOfNumericalSemigroup(S);
    4
  
  
  3.1-18 Gaps
  
  Gaps( NS )  attribute
  GapsOfNumericalSemigroup( NS )  attribute
  
  A  gap  of a numerical semigroup S is a nonnegative integer not belonging to
  S. NS is a numerical semigroup. Both return the set of gaps of NS.
  
    Example  
    gap> GapsOfNumericalSemigroup(NumericalSemigroup(3,5,7));
    [ 1, 2, 4 ]
    gap> Gaps(NumericalSemigroup(5,7,11));
    [ 1, 2, 3, 4, 6, 8, 9, 13 ]
  
  
  3.1-19 DesertsOfNumericalSemigroup
  
  DesertsOfNumericalSemigroup( NS )  function
  
  NS is a numerical semigroup. The output is the list with the runs of gaps of
  NS.
  
    Example  
    gap> s:=NumericalSemigroup(3,5,7);;
    gap> DesertsOfNumericalSemigroup(s);
    [ [ 1, 2 ], [ 4 ] ]
  
  
  3.1-20 IsOrdinaryNumericalSemigroup
  
  IsOrdinaryNumericalSemigroup( NS )  property
  IsOrdinary( NS )  property
  
  NS is a numerical semigroup. Dectects if the semigroup is ordinary, that is,
  with less than two deserts.
  
    Example  
    gap> s:=NumericalSemigroup(3,5,7);;
    gap> IsOrdinary(s);
    false
  
  
  3.1-21 IsAcuteNumericalSemigroup
  
  IsAcuteNumericalSemigroup( NS )  property
  IsAcute( NS )  property
  
  NS is a numerical semigroup. Dectects if the semigroup is acute, that is, it
  is  either  ordinary  or its last desert (the one with the Frobenius number)
  has less elements than the preceding one ([BA04]).
  
    Example  
    gap> s:=NumericalSemigroup(3,5,7);;
    gap> IsAcute(s);
    true
  
  
  3.1-22 Holes
  
  Holes( NS )  attribute
  HolesOfNumericalSemigroup( S )  attribute
  
  S  is a numerical semigroup. Returns the set of gaps x of S such that F(S)-x
  is also a gap, where F(S) stands for the Frobenius number of S.
  
    Example  
    gap> s:=NumericalSemigroup(3,5);;
    gap> Holes(s);
    [  ]
    gap> s:=NumericalSemigroup(3,5,7);;
    gap> HolesOfNumericalSemigroup(s);
    [ 2 ]
  
  
  3.1-23 LatticePathAssociatedToNumericalSemigroup
  
  LatticePathAssociatedToNumericalSemigroup( S, p, q )  attribute
  
  S is a numerical semigroup and p,q are two elements in S.
  
  In  this setting S is an oversemigroup of ⟨ p,q⟩, and consequently every gap
  of  S  is a gap of ⟨ p,q⟩. If c is the conductor of ⟨ p,q⟩, then every gap g
  of  ⟨  p,q⟩  can  be  written uniquely as g=c-1-(ap+bp) for some nonnegative
  integers a,b. We say that (a,b) are the coordinates associated to g.
  
  The  output  is  a  path  in  N^2  such  that  coordinates  of the gaps of S
  correspond  exactly  with the points in N^2 that are between the path in the
  line ax+by=c-1. See [KW14].
  
    Example  
    gap> s:=NumericalSemigroup(16,17,71,72);;
    gap> LatticePathAssociatedToNumericalSemigroup(s,16,17);
    [ [ 0, 14 ], [ 1, 13 ], [ 2, 12 ], [ 3, 11 ], [ 4, 10 ], [ 5, 9 ], [ 6, 8 ],
      [ 7, 7 ], [ 8, 6 ], [ 9, 5 ], [ 10, 4 ], [ 11, 3 ], [ 12, 2 ], [ 13, 1 ],
      [ 14, 0 ] ]
  
  
  3.1-24 Genus
  
  Genus( NS )  attribute
  GenusOfNumericalSemigroup( NS )  attribute
  
  NS is a numerical semigroup. It returns the number of gaps of NS.
  
    Example  
    gap> s:=NumericalSemigroup(16,17,71,72);;
    gap> GenusOfNumericalSemigroup(s);
    80
    gap> S := NumericalSemigroup("modular", 5,53);
    <Modular numerical semigroup satisfying 5x mod 53 <= x >
    gap> Genus(S);
    26
  
  
  3.1-25 FundamentalGaps
  
  FundamentalGaps( S )  attribute
  FundamentalGapsOfNumericalSemigroup( S )  attribute
  
  S  The fundamental gaps of S are those gaps that are maximal with respect to
  the  partial  order  induced  by division in N. is a numerical semigroup. It
  returns the set of fundamental gaps of S.
  
    Example  
    gap> S := NumericalSemigroup("modular", 5,53);
    <Modular numerical semigroup satisfying 5x mod 53 <= x >
    gap> FundamentalGapsOfNumericalSemigroup(S);
    [ 16, 17, 18, 19, 27, 28, 29, 30, 31, 40, 41, 42 ]
    gap> GapsOfNumericalSemigroup(S);
    [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 27, 28, 29,
      30, 31, 40, 41, 42 ]
    gap> Gaps(NumericalSemigroup(5,7,11));
    [ 1, 2, 3, 4, 6, 8, 9, 13 ]
    gap> FundamentalGaps(NumericalSemigroup(5,7,11));
    [ 6, 8, 9, 13 ]
  
  
  3.1-26 SpecialGaps
  
  SpecialGaps( S )  attribute
  SpecialGapsOfNumericalSemigroup( S )  attribute
  
  The special gaps of a numerical semigroup S, are those fundamental gaps such
  that  if they are added to the given numerical semigroup, then the resulting
  set  is  again a numerical semigroup. S is a numerical semigroup. It returns
  the special gaps of S.
  
    Example  
    gap> S := NumericalSemigroup("modular", 5,53);
    <Modular numerical semigroup satisfying 5x mod 53 <= x >
    gap> SpecialGaps(S);
    [ 40, 41, 42 ]
    gap> SpecialGapsOfNumericalSemigroup(S);
    [ 40, 41, 42 ]
  
  
  
  3.2 Wilf's conjecture
  
  Let  S be a numerical semigroup, with conductor c and embedding dimension e.
  Denote by l the cardinality of the set of elements in S smaller than c. Wilf
  in  [Wil78]  asked whether or not l/cge 1/e for all numerical semigroups. In
  this  section  we give some functions to experiment with this conjecture, as
  defined in [Eli15].
  
  3.2-1 WilfNumber
  
  WilfNumber( S )  attribute
  WilfNumberOfNumericalSemigroup( S )  attribute
  
  S  is  a  numerical  semigroup.  Let  c, e and l be the conductor, embedding
  dimension  and  number of elements smaller than c in S. Returns e l-c, which
  was conjetured by Wilf to be nonnegative.
  
    Example  
    gap> l:=NumericalSemigroupsWithGenus(10);;
    gap> Filtered(l, s->WilfNumberOfNumericalSemigroup(s)<0); 
    [  ]
    gap> Maximum(Set(l, s->WilfNumberOfNumericalSemigroup(s)));
    70
    gap> s := NumericalSemigroup(13,25,37);;
    gap> WilfNumber(s);                     
    96
  
  
  3.2-2 EliahouNumber
  
  EliahouNumber( S )  attribute
  TruncatedWilfNumberOfNumericalSemigroup( S )  attribute
  
  S  is  a  numerical  semigroup.  Let  c,  m,  s  and  l  be  the  conductor,
  multiplicity,  number  of  generators smaller than c, and number of elements
  smaller  than c in S, respectively. Let q and r be the quotient and negative
  remainder  of  the  division of c by m, that is, c=qm-r. Returns s l-qd_q+r,
  where  d_q  corresponds  with the number of integers in [c,c+m[ that are not
  minimal generators of S.
  
    Example  
    gap> s:=NumericalSemigroup(5,7,9);;
    gap> TruncatedWilfNumberOfNumericalSemigroup(s);
    4
    gap> s:=NumericalSemigroupWithGivenElementsAndFrobenius([14,22,23],55);;
    gap> EliahouNumber(s);
    -1
  
  
  3.2-3 ProfileOfNumericalSemigroup
  
  ProfileOfNumericalSemigroup( S )  attribute
  
  S is a numerical semigroup. Let c and m be the conductor and multiplicity of
  S,  respectively.  Let  q and r be the quotient and nonpositive remainder of
  the  division  of  c  by  m,  that  is,  c=qm-r.  Returns a list of lists of
  integers,  each  list  is  the cardinality of S ∩ [jm-r, (j+1)m-r[ with j in
  [1..q-1].
  
    Example  
    gap> s:=NumericalSemigroup(5,7,9);;
    gap> ProfileOfNumericalSemigroup(s);
    [ 2, 1 ]
    gap> s:=NumericalSemigroupWithGivenElementsAndFrobenius([14,22,23],55);;
    gap> ProfileOfNumericalSemigroup(s);
    [ 3, 0, 0 ]
  
  
  3.2-4 EliahouSlicesOfNumericalSemigroup
  
  EliahouSlicesOfNumericalSemigroup( S )  attribute
  
  S is a numerical semigroup. Let c and m be the conductor and multiplicity of
  S,  respectively.  Let q and r be the quotient and negative remainder of the
  division  of  c  by m, that is, c=qm-r. Returns a list of lists of integers,
  each  list  is  the  set S ∩ [jm-r, (j+1)m-r[ with j in [1..q]. So this is a
  partition of the set of small elements of S (without 0).
  
    Example  
    gap> s:=NumericalSemigroup(5,7,9);;                                     
    gap> EliahouSlicesOfNumericalSemigroup(s);
    [ [ 5, 7 ], [ 9, 10, 12 ] ]
    gap> SmallElements(s);
    [ 0, 5, 7, 9, 10, 12, 14 ]