In this chapter we explain how to compute a minimal presentation of a numerical semigroup. Recall that a minimal presentation is a minimal generating system of the kernel congruence of the factorization map of the numerical semigroup. If S is a numerical semigroup minimally generated by {n_1,...,n_e}, then the factorization map is the epimorphism φ: N^e-> S, (x_1,...,x_e)↦ x_1n_1+dots+ x_en_e; its kernel is the congruence { (a,b) ∣ φ(a)=φ(b)}.
The set of minimal generators is stored in a set, and so it may not be arranged as the user gave them. This may affect the arrangement of the coordinates of the pairs in a minimal presentation, since every coordinate is associated to a minimal generator.
In this section we provide a way to compute minimal presentations of a numerical semigroup. These presentations are constructed from some special elelements in the semigroup (Betti elemenents) whose associated graphs are nonconnected. A generalization of these graphs are the simplicial complexes called shaded sets of an element.
If the variable NumSgpsUseEliminationForMinimalPresentations is set to true, then minimal presentations are computed via binomial ideals and elimination.
‣ MinimalPresentation( S ) | ( operation ) |
‣ 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+⋯+a_i_nm_n= b_i_1m_1+ ⋯ +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 [RG99b]).
gap> s:=NumericalSemigroup(3,5,7);; gap> MinimalPresentation(s); [ [ [ 0, 0, 2 ], [ 3, 1, 0 ] ], [ [ 0, 1, 1 ], [ 4, 0, 0 ] ], [ [ 0, 2, 0 ], [ 1, 0, 1 ] ] ] gap> MinimalPresentationOfNumericalSemigroup(s); [ [ [ 0, 0, 2 ], [ 3, 1, 0 ] ], [ [ 0, 1, 1 ], [ 4, 0, 0 ] ], [ [ 0, 2, 0 ], [ 1, 0, 1 ] ] ]
The first element in the list means that 1× 3+1× 7=2× 5, and the others have similar meanings.
‣ 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_i∈ S}, and the second component is the set of edges of this graph, that is, { {m_i,m_j} | n-(m_i+m_j)∈ S}.
This function is used to compute a minimal presentation of the numerical semigroup S, as explained in [Ros96a].
gap> s:=NumericalSemigroup(3,5,7);; gap> GraphAssociatedToElementInNumericalSemigroup(10,s); [ [ 3, 5, 7 ], [ [ 3, 7 ] ] ]
‣ BettiElements( S ) | ( operation ) |
‣ BettiElementsOfNumericalSemigroup( S ) | ( function ) |
S is a numerical semigroup.
The output is the set of elements in S whose associated graph is nonconnected [GO10].
gap> s:=NumericalSemigroup(3,5,7);; gap> BettiElementsOfNumericalSemigroup(s); [ 10, 12, 14 ] gap> BettiElements(s); [ 10, 12, 14 ]
‣ IsMinimalRelationOfNumericalSemigroup( p, S ) | ( function ) |
S is a numerical semigroup and p is a pair (a relation) of lists of integers. Determines if the pair p is a minimal relation in a minimal presentation of S.
gap> s:=NumericalSemigroup(4,6,9);; gap> MinimalPresentation(s); [ [ [ 0, 0, 2 ], [ 0, 3, 0 ] ], [ [ 0, 2, 0 ], [ 3, 0, 0 ] ] ] gap> IsMinimalRelationOfNumericalSemigroup([[2,1,0],[0,0,2]],s); false gap> IsMinimalRelationOfNumericalSemigroup([[3,1,0],[0,0,2]],s); true
‣ AllMinimalRelationsOfNumericalSemigroup( S ) | ( function ) |
S is a numerical semigroup. The output is the union of all minimal presentations of S. Notice that if [x,y] is a minimal relator, then either [x,y] or [y,x] will be in the output, but not both.
gap> s:=NumericalSemigroup(4,6,9);; gap> MinimalPresentation(s); [ [ [ 0, 0, 2 ], [ 0, 3, 0 ] ], [ [ 0, 2, 0 ], [ 3, 0, 0 ] ] ] gap> AllMinimalRelationsOfNumericalSemigroup(s); [ [ [ 0, 3, 0 ], [ 0, 0, 2 ] ], [ [ 3, 0, 0 ], [ 0, 2, 0 ] ], [ [ 3, 1, 0 ], [ 0, 0, 2 ] ] ]
‣ DegreesOfPrimitiveElementsOfNumericalSemigroup( S ) | ( function ) |
S is a numerical semigroup.
The output is the set of elements s in S such that there exists a minimal solution to msg⋅ x-msg⋅ y = 0, such that x,y are factorizations of s, and msg is the minimal generating system of S. Betti elements are primitive, but not the way around in general.
gap> s:=NumericalSemigroup(3,5,7);; gap> DegreesOfPrimitiveElementsOfNumericalSemigroup(s); [ 3, 5, 7, 10, 12, 14, 15, 21, 28, 35 ]
‣ ShadedSetOfElementInNumericalSemigroup( n, S ) | ( function ) |
S is a numerical semigroup and n is an element in S.
The output is a simplicial complex C. If {m_1,...,m_n} is the set of minimal generators of S, then L ∈ C if n-∑_i∈ L m_i∈ S ([SW86]).
This function is a generalization of the graph associated to n.
gap> s:=NumericalSemigroup(3,5,7);; gap> ShadedSetOfElementInNumericalSemigroup(10,s); [ [ ], [ 3 ], [ 3, 7 ], [ 5 ], [ 7 ] ]
Let S be a numerical semigroup, and let K be a field. Let {n_1,dots,n_e} be a set of minimal generators of S, and let K[x_1,dots,x_e] be the ring of polynomial in the indeterminates x_1,dots,x_e and with coefficients in K. Let K[t] be the ring of polynomials in t with coefficients in K.
Let φ: K[x_1,dots,x_e] -> K[t] be the ring homomorphism determined by φ(x_i)=t^n_i for all i. The image of this morphism is usually known as the semigroup ring associated to S. The kernel is the (binomial) ideal associated to S. According to [Her70], from the exponents of the binomials in this ideal we can recover a presentation of S and viceversa.
‣ BinomialIdealOfNumericalSemigroup( [K, ]S ) | ( operation ) |
The argument K is optional; when it is not supplied, the field of rational numbers is taken as base field. S is a numerical semigroup. The output is the binomial ideal associated to S.
gap> s:=NumericalSemigroup(3,5,7);; gap> BinomialIdealOfNumericalSemigroup(GF(2),s); <two-sided ideal in GF(2)[x_1,x_2,x_3], (3 generators)> gap> GeneratorsOfTwoSidedIdeal(last); [ x_1^3*x_2+x_3^2, x_1^4+x_2*x_3, x_1*x_3+x_2^2 ] gap> BinomialIdealOfNumericalSemigroup(s); <two-sided ideal in Rationals[x_1,x_2,x_3], (3 generators)> gap> GeneratorsOfTwoSidedIdeal(last); [ -x_1^3*x_2+x_3^2, -x_1^4+x_2*x_3, -x_1*x_3+x_2^2 ] gap> MinimalPresentation(s); [ [ [ 0, 0, 2 ], [ 3, 1, 0 ] ], [ [ 0, 1, 1 ], [ 4, 0, 0 ] ], [ [ 0, 2, 0 ], [ 1, 0, 1 ] ] ]
A numerical semigroup S is uniquely presented if for any two minimal presentations σ and τ and any (a,b)∈ σ, either (a,b)∈ τ or (b,a)∈ τ, that is, there is essentially a unique minimal presentation (up to arrangement of the components of the pairs in it).
‣ IsUniquelyPresented( S ) | ( property ) |
‣ IsUniquelyPresentedNumericalSemigroup( S ) | ( property ) |
S is a numerical semigroup.
The output is true if S has uniquely presented. The implementation is based on [GO10].
gap> s:=NumericalSemigroup(3,5,7);; gap> IsUniquelyPresented(s); true gap> IsUniquelyPresentedNumericalSemigroup(s); true
‣ IsGeneric( S ) | ( property ) |
‣ IsGenericNumericalSemigroup( S ) | ( property ) |
S is a numerical semigroup.
The output is true if S has a generic presentation, that is, in every minimal relation all generators occur. These semigroups are uniquely presented (see [BGG11]).
This filter implies IsUniquelyPresentedNumericalSemigroup (4.3-1).
gap> s:=NumericalSemigroup(3,5,7);; gap> IsGeneric(s); true gap> IsGenericNumericalSemigroup(s); true
generated by GAPDoc2HTML