Sophie

Sophie

distrib > Mandriva > 2010.0 > i586 > media > contrib-release > by-pkgid > 5e1854624d3bc613bdd0dd13d1ef9ac7 > files > 2469

gap-system-4.4.12-5mdv2010.0.i586.rpm

  
  4 Presentations of Numerical Semigroups
  
  In  this  chapter  we  explain  how  to  compute a minimal presentation of a
  numerical semigroup. There are three functions involved in this process.
  
  
  4.1 Presentations of Numerical Semigroups
  
  4.1-1 FortenTruncatedNCForNumericalSemigroups
  
  > FortenTruncatedNCForNumericalSemigroups( L ) _____________________function
  
  L  contains  the  list  of  coefficients  of  a single linear equation. This
  function  gives  a  minimal generator of the affine semigroup of nonnegative
  solutions  of  this  equation  with  the  first coordinate equal to one (see
  [CD94]). Returns fail if no solution exists.
  
  ---------------------------  Example  ----------------------------
    gap> FortenTruncatedNCForNumericalSemigroups([ -57, 3 ]);
    [ 1, 19 ]
    gap> FortenTruncatedNCForNumericalSemigroups([ -57, 33 ]);
    fail
    gap> FortenTruncatedNCForNumericalSemigroups([ -57, 19 ]);
    [ 1, 3 ]
  ------------------------------------------------------------------
  
  4.1-2 MinimalPresentationOfNumericalSemigroup
  
  > MinimalPresentationOfNumericalSemigroup( S ) _____________________function
  
  S is a numerical semigroup. The output is a list of lists with two elements.
  Each  list  of  two  elements  represents  a  relation  between  the minimal
  generators  of the numerical semigroup. If { {x_1,y_1},...,{x_k,y_k}} is the
  output  and  {m_1,...,m_n}  is  the  minimal  system  of  generators  of the
  numerical  semigroup,  then  {x_i,y_i}={{a_i_1,...,a_i_n},{b_i_1,...,b_i_n}}
  and a_i_1m_1+cdots+a_i_nm_n= b_i_1m_1+ cdots +b_i_nm_n.
  
  Any  other  relation  among  the  minimal generators of the semigroup can be
  deduced from the ones given in the output.
  
  The algorithm implemented is described in [Ros96a] (see also [RG99]).
  
  ---------------------------  Example  ----------------------------
    gap> s:=NumericalSemigroup(3,5,7);
    <Numerical semigroup with 3 generators>
    gap> MinimalPresentationOfNumericalSemigroup(s);
    [ [ [ 1, 0, 1 ], [ 0, 2, 0 ] ], [ [ 4, 0, 0 ], [ 0, 1, 1 ] ],
      [ [ 3, 1, 0 ], [ 0, 0, 2 ] ] ]
    
                            
  ------------------------------------------------------------------
  
  The first element in the list means that 1x 3+1x 7=2x 5, and so on.
  
  4.1-3 GraphAssociatedToElementInNumericalSemigroup
  
  > GraphAssociatedToElementInNumericalSemigroup( n, S ) _____________function
  
  S is a numerical semigroup and n is an element in S.
  
  The  output  is a pair. If {m_1,...,m_n} is the set of minimal generators of
  S,  then  the first component is the set of vertices of the graph associated
  to  n in S, that is, the set { m_i | n-m_iin S}, and the second component is
  the set of edges of this graph, that is, { {m_i,m_j} | n-(m_i+m_j)in S}.
  
  This  function  is  used  to compute a minimal presentation of the numerical
  semigroup S, as explained in [Ros96a].
  
  ---------------------------  Example  ----------------------------
    gap> s:=NumericalSemigroup(3,5,7);
    <Numerical semigroup with 3 generators>
    gap> GraphAssociatedToElementInNumericalSemigroup(10,s);
    [ [ 3, 5, 7 ], [ [ 3, 7 ] ] ]
    
                            
  ------------------------------------------------------------------