An affine semigroup \(S\) is a finitely generated cancellative monoid that is reduced (no units other than 0) and is torsion-free (\( a s= b s\) implies \(a=b\), with \(a,b\in \mathbb N\) and \(s\in S\)). Up to isomorphism any affine semigroup can be viewed as a finitely generated submonoid of \(\mathbb N^k\) for some positive integer \(k\). Thus affine semigroups are a natural generalization of numerical semigroups.
Some of the functions in this chapter may work considerably faster when some external package is installed and its use is allowed. When this is the case, it is referred in the function documentation. We refer the user to Chapter 13 for details on the use of external packages.
The most common way to give an affine semigroup is by any of its systems of generators. As for numerical semigroups, any affine semigroup admits a unique minimal system of generators. A system of generators can be represented as a list of lists of nonnegative integers; all lists in the list having the same length (a matrix actually). If \(G\) is a subgroup of \(\mathbb Z^k\), then \(S=G\cap \mathbb N^k\) is an affine semigroup (these semigroups are called full affine semigroups). As \(G\) can be represented by its defining equations (homogeneous and some of them possibly in congruences), we can represent \(S\) by the defining equations of \(G\); indeed \(S\) is just the set of nonnegative solutions of this system of equations. We can represent the equations as a list of lists of integers, all with the same length. Every list is a row of the matrix of coefficients of the system of equations. For the equations in congruences, if we arrange them so that they are the first ones in the list, we provide the corresponding moduli in a list. So for instance, the equations \(x+y\equiv 0\bmod 2,\ x-2y=0\) will be represented as [[1,1],[1,-2]] and the moduli [2].
As happens with numerical semigroups, there are different ways to specify an affine semigroup \(S\), namely, by means of a system of generators, a system of homogeneous linear Diophantine equations or a system of homogeneous linear Diophantine inequalities, just to mention some. In this section we describe functions that may be used to specify, in one of these ways, an affine semigroup in GAP.
‣ AffineSemigroup( [String, ]List ) | ( function ) |
‣ AffineSemigroupByGenerators( List ) | ( function ) |
List is a list of n-tuples of nonnegative integers, if the semigroup to be created is n-dimensional. The n-tuples may be given as a list or by a sequence of individual elements. The output is the affine semigroup spanned by List.
String does not need to be present. When it is present, it must be "generators" and List must be a list, not a sequence of individual elements.
gap> s1 := AffineSemigroup([1,3],[7,2],[1,5]); <Affine semigroup in 2 dimensional space, with 3 generators> gap> s2 := AffineSemigroup([[1,3],[7,2],[1,5]]);; gap> s3 := AffineSemigroupByGenerators([1,3],[7,2],[1,5]);; gap> s4 := AffineSemigroupByGenerators([[1,3],[7,2],[1,5]]);; gap> s5 := AffineSemigroup("generators",[[1,3],[7,2],[1,5]]);; gap> Length(Set([s1,s2,s3,s4,s5])); 1
‣ AffineSemigroupByEquations( List ) | ( function ) |
‣ AffineSemigroup( String, List ) | ( function ) |
List is a list with two components. The first represents a matrix with integer coefficients, say \(A=(a_{ij})\), and so it is a list of lists of integers all with the same length. The second component is a list of positive integers, say \(d=(d_i)\), which may be empty. The list \(d\) must be of length less than or equal to the length of \(A\) (number of rows of \(A\)).
The output is the full semigroup of nonnegative integer solutions to the system of homogeneous equations
\(a_{11}x_1+\cdots+a_{1n}x_n\equiv 0\bmod d_1, \)
\(\cdots \)
\(a_{k1}x_1+\cdots+a_{kn}x_n\equiv 0\bmod d_k, \)
\(a_{k+1\, 1}x_1+\cdots +a_{k+1\, n}=0, \)
\(\cdots \)
\(a_{m1}x_1+\cdots+a_{mn}x_n=0. \)
If \(d\) is empty, then there will be no equations in congruences.
As pointed at the beginning of the section, the equations \(x+y\equiv 0\bmod 2,\ x-2y=0\) will be represented as \(A\) equal to [[1,1],[1,-2]] and the moduli \(d\) equal to [2].
In the second form, String must be "equations".
gap> s1 := AffineSemigroup("equations",[[[1,1]],[3]]); <Affine semigroup> gap> s2 := AffineSemigroupByEquations([[[-2,1]],[3]]); <Affine semigroup> gap> s1=s2; true
‣ AffineSemigroupByInequalities( List ) | ( function ) |
‣ AffineSemigroup( String, List ) | ( function ) |
List is a list of lists (a matrix) of integers that represents a set of inequalities.
Returns the (normal) affine semigroup of nonegative integer solutions of the system of inequalities \(List\times X\ge 0\).
In the second form, String must be "inequalities".
gap> a1:=AffineSemigroup("inequalities",[[2,-1],[-1,3]]); <Affine semigroup> gap> a2:=AffineSemigroupByInequalities([[2,-1],[-1,3]]); <Affine semigroup> gap> a1=a2; true
‣ AffineSemigroupByPMInequality( f, b, g ) | ( function ) |
‣ AffineSemigroup( String, List ) | ( function ) |
f, g are lists of integers and b is a positive integer.
Returns the proportionally modular affine semigroup defined by the \(f\times X \pmod{b} \leq g\times X\)
In the second form, String must be "pminequality".
gap> s:=AffineSemigroupByPMInequality([0, 1, 1, 0, -1], 4, [1, 0, -2, -3, 1]); <Affine semigroup> gap> [ 3, 0, 0, 4, 12 ] in s; true gap> [ 3, 0, 0, 4, 1 ] in s; false
‣ AffineSemigroupByGaps( List ) | ( function ) |
‣ AffineSemigroup( [String, ]List ) | ( function ) |
In the second form, String must be "gaps" and List must be a list, not a sequence of individual elements.
In the first form, List is a list of n-tuples of nonnegative integers, if the semigroup to be created is n-dimensional. The n-tuples may be given as a list or by a sequence of individual elements. The output is the affine semigroup with gaps List. If the given set is not a set of gaps of a numerical semigroup, then the function raises an error.
gap> gaps := [[1,0,0,0],[1,1,0,0],[2,0,0,0],[2,1,0,0],[5,0,0,0]];; gap> a1 := AffineSemigroup("gaps", gaps ); <Affine semigroup> gap> a2 := AffineSemigroupByGaps( gaps ); <Affine semigroup> gap> a1 = a2; true gap> Generators(a1);; gap> Set(last); [ [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 0, 1 ], [ 1, 0, 1, 0 ], [ 1, 2, 0, 0 ], [ 2, 0, 0, 1 ], [ 2, 0, 1, 0 ], [ 2, 2, 0, 0 ], [ 3, 0, 0, 0 ], [ 4, 0, 0, 0 ], [ 5, 1, 0, 0 ] ]
‣ FiniteComplementIdealExtension( List ) | ( function ) |
List is a list or sequence of \(n\)-tuples of nonnegative integers. If the monoid \(M=\{0\}\cup (\mathtt{List}+\mathbb{N}^n)\) is an affine semigroup (equivalently, \(M\) has finitely many gaps), then the output is \(M\). Otherwise, an error is raised.
gap> s:=FiniteComplementIdealExtension([[0,2],[1,1],[3,0]]); <Affine semigroup> gap> MinimalGenerators(s); [ [ 0, 3 ], [ 1, 1 ], [ 0, 2 ], [ 3, 0 ], [ 2, 1 ], [ 1, 2 ], [ 3, 1 ], [ 5, 0 ], [ 4, 0 ] ] gap> s:=FiniteComplementIdealExtension([0,2],[1,1],[3,0]); <Affine semigroup>
‣ Gaps( S ) | ( attribute ) |
S is an affine semigroup, the output is its set of gaps, if this set has finitely many elements. Otherwise the output is 'fail' and a warning is raised. The procedure is inspired in [CFR18]
gap> a:=AffineSemigroup([[1,0,0,0],[3,1,0,0],[1,2,0,0],[0,0,1,0], > [0,2,1,0],[0,1,1,0],[0,0,0,1],[0,2,0,1],[0,1,0,1],[0,3,0,0], > [0,5,0,0],[0,4,0,0]]); <Affine semigroup in 4 dimensional space, with 12 generators> gap> Set(Gaps(a)); [ [ 0, 1, 0, 0 ], [ 0, 2, 0, 0 ], [ 1, 1, 0, 0 ], [ 2, 1, 0, 0 ] ] gap> n := AffineSemigroup([1,1],[0,1]);; gap> Gaps(n); #I The given affine semigroup has infinitely many gaps fail
‣ Genus( S ) | ( attribute ) |
S is an affine semigroup, the output is the cardinality of its set of gaps, if this set is finite. Otherwise the output is 'infinite'. The procedure is inspired in [CFR18]
gap> a:=AffineSemigroup([[1,0,0,0],[3,1,0,0],[1,2,0,0],[0,0,1,0], > [0,2,1,0],[0,1,1,0],[0,0,0,1],[0,2,0,1],[0,1,0,1],[0,3,0,0], > [0,5,0,0]]); <Affine semigroup in 4 dimensional space, with 11 generators> gap> Genus(a); 7 gap> n := AffineSemigroup([1,1],[0,1]);; gap> Genus(n); #I The given affine semigroup has infinitely many gaps infinity gap> last > 10^50; true
‣ PseudoFrobenius( S ) | ( attribute ) |
S is an affine semigroup, the output is its set of pseudo-Frobenius vectors, that is, the gaps \(g\) of S such that for every nonzero element \(s\) of S, the vector \(g+s\) is in S. The package will only find pseudo-Frobenius vectors for affine semigroups with a finite set of gaps.
gap> a:=AffineSemigroup([[1,0,0,0],[3,1,0,0],[1,2,0,0],[0,0,1,0], > [0,2,1,0],[0,1,1,0],[0,0,0,1],[0,2,0,1],[0,1,0,1],[0,3,0,0], > [0,5,0,0],[0,4,0,0]]); <Affine semigroup in 4 dimensional space, with 12 generators> gap> PseudoFrobenius(a); [ [ 0, 2, 0, 0 ], [ 2, 1, 0, 0 ] ]
‣ SpecialGaps( S ) | ( attribute ) |
S is an affine semigroup, the output is its set of special gaps of S, that is, the gaps \(g\) of S such that \(\textit{S}\cup\{g\}\) is a semigroup. Special gaps can only be computed in the package for affine semigroups with finitely many gaps.
gap> a:=AffineSemigroup([[1,0,0,0],[3,1,0,0],[1,2,0,0],[0,0,1,0], > [0,2,1,0],[0,1,1,0],[0,0,0,1],[0,2,0,1],[0,1,0,1],[0,3,0,0], > [0,5,0,0],[0,4,0,0]]); <Affine semigroup in 4 dimensional space, with 12 generators> gap> SpecialGaps(a); [ [ 0, 2, 0, 0 ], [ 2, 1, 0, 0 ] ]
‣ Generators( S ) | ( function ) |
‣ GeneratorsOfAffineSemigroup( S ) | ( function ) |
S is an affine semigroup, the output is a system of generators.
gap> a:=AffineSemigroup([[1,0],[0,1],[1,1]]); <Affine semigroup in 2 dimensional space, with 3 generators> gap> Generators(a); [ [ 0, 1 ], [ 1, 0 ], [ 1, 1 ] ]
‣ MinimalGenerators( S ) | ( function ) |
‣ MinimalGeneratingSystem( S ) | ( function ) |
S is an affine semigroup, the output is its system of minimal generators.
gap> a:=AffineSemigroup([[1,0],[0,1],[1,1]]); <Affine semigroup in 2 dimensional space, with 3 generators> gap> MinimalGenerators(a); [ [ 0, 1 ], [ 1, 0 ] ]
‣ RemoveMinimalGeneratorFromAffineSemigroup( n, S ) | ( function ) |
S is an affine semigroup and n is one if its minimal generators.
The output is the affine semigroup \( \textit{S} \setminus\{\textit{n}\} \) (\(S\setminus\{n\}\) is an affine semigroup if and only if \(n\) is a minimal generator of \(S\)).
gap> a:=AffineSemigroup([2,0],[0,4]); <Affine semigroup in 2 dimensional space, with 2 generators> gap> b:=RemoveMinimalGeneratorFromAffineSemigroup([2,0],a);Generators(b); <Affine semigroup in 2 dimensional space, with 4 generators> [ [ 0, 4 ], [ 2, 4 ], [ 4, 0 ], [ 6, 0 ] ]
‣ AddSpecialGapOfAffineSemigroup( g, S ) | ( function ) |
S is an semigroup and g is a special gap of S.
The output is the numerical semigroup \( \textit{S} \cup\{\textit{g}\} \) (see [RGGJ03], where it is explained why this set is a numerical semigroup).
gap> s:=AffineSemigroup([[2,0],[3,0],[0,4],[0,5],[1,1]]); <Affine semigroup in 2 dimensional space, with 5 generators> gap> t:=AddSpecialGapOfAffineSemigroup([1,12],s); <Affine semigroup in 2 dimensional space, with 6 generators> gap> Gaps(s); [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 6 ], [ 0, 7 ], [ 0, 11 ], [ 1, 0 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 7 ], [ 1, 8 ], [ 1, 12 ], [ 2, 1 ], [ 2, 3 ], [ 3, 2 ], [ 4, 3 ] ] gap> Gaps(t); [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 6 ], [ 0, 7 ], [ 0, 11 ], [ 1, 0 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 7 ], [ 1, 8 ], [ 2, 1 ], [ 2, 3 ], [ 3, 2 ], [ 4, 3 ] ]
‣ AsAffineSemigroup( S ) | ( function ) |
S is a numerical semigroup, the output is S regarded as an affine semigroup.
gap> s:=NumericalSemigroup(1310,1411,1546,1601); <Numerical semigroup with 4 generators> gap> MinimalPresentationOfNumericalSemigroup(s);;time; 2960 gap> a:=AsAffineSemigroup(s); <Affine semigroup in 1 dimensional space, with 4 generators> gap> GeneratorsOfAffineSemigroup(a); [ [ 1310 ], [ 1411 ], [ 1546 ], [ 1601 ] ] gap> MinimalPresentationOfAffineSemigroup(a);;time; 237972
If we use the package SingularInterface, the speed up is considerable.
gap> NumSgpsUseSingularInterface(); ... gap> MinimalPresentationOfAffineSemigroup(a);;time; 32
‣ IsAffineSemigroup( AS ) | ( attribute ) |
‣ IsAffineSemigroupByGenerators( AS ) | ( attribute ) |
‣ IsAffineSemigroupByEquations( AS ) | ( attribute ) |
‣ IsAffineSemigroupByInequalities( AS ) | ( attribute ) |
AS is an affine semigroup and these attributes are available (their names should be self explanatory). They reflect what is currently known about the semigroup.
gap> a1:=AffineSemigroup([[3,0],[2,1],[1,2],[0,3]]); <Affine semigroup in 2 dimensional space, with 4 generators> gap> IsAffineSemigroupByEquations(a1); false gap> IsAffineSemigroupByGenerators(a1); true gap> ns := NumericalSemigroup(3,5); <Numerical semigroup with 2 generators> gap> IsAffineSemigroup(ns); false gap> as := AsAffineSemigroup(ns); <Affine semigroup in 1 dimensional space, with 2 generators> gap> IsAffineSemigroup(as); true
‣ BelongsToAffineSemigroup( v, a ) | ( function ) |
‣ \in( v, a ) | ( operation ) |
v is a list of nonnegative integers and a an affine semigroup. Returns true if the vector is in the semigroup, and false otherwise.
If the semigroup is full and its equations are known (either because the semigroup was defined by equations, or because the user has called IsFullAffineSemgiroup(a) and the output was true), then membership is performed by evaluating v in the equations. The same holds for normal semigroups and its defining inequalities. If the set of gaps is finite and known, then membership is just checking that v has nonnegative integers and it is not in the set of gaps.
v in a can be used for short.
gap> a:=AffineSemigroup([[2,0],[0,2],[1,1]]);; gap> BelongsToAffineSemigroup([5,5],a); true gap> BelongsToAffineSemigroup([1,2],a); false gap> [5,5] in a; true gap> [1,2] in a; false
‣ IsFull( S ) | ( property ) |
‣ IsFullAffineSemigroup( S ) | ( property ) |
S is an affine semigroup.
Returns true if the semigroup is full, false otherwise. The semigroup is full if whenever \(a,b\in S\) and \(b-a\in \mathbb N^k\), then \(a-b\in S\), where \(k\) is the dimension of \(S\).
If the semigroup is full, then its equations are stored in the semigroup for further use.
gap> a:=AffineSemigroup("equations",[[[1,1,1],[0,0,2]],[2,2]]);; gap> IsFull(a); true gap> IsFullAffineSemigroup(a); true
‣ HilbertBasisOfSystemOfHomogeneousEquations( ls, m ) | ( operation ) |
ls is a list of lists of integers and m a list of integers. The elements of ls represent the rows of a matrix \(A\). The output is a minimal generating system (Hilbert basis) of the set of nonnegative integer solutions of the system \(Ax=0\) where the \(k\) first equations are in the congruences modulo m[i], with \(k\) the length of m.
If the package NormalizInterface has not been loaded, then Contejean-Devie algorithm is used [CD94] instead (if this is the case, congruences are treated as in [RG98]).
gap> HilbertBasisOfSystemOfHomogeneousEquations([[1,0,1],[0,1,-1]],[2]); [ [ 0, 2, 2 ], [ 1, 1, 1 ], [ 2, 0, 0 ] ]
If \(C\) is a pointed cone (a cone in \(\mathbb Q^k\) not containing lines and \(0\in C\)), then \(S=C\cap \mathbb N^k\) is an affine semigroup (known as normal affine semigroup). So another way to give an affine semigroup is by a set of homogeneous inequalities, and we can represent these inequalities by its coefficients. If we put them in a matrix \(S\) can be defined as the set of nonnegative integer solutions to \(Ax \ge 0\).
‣ HilbertBasisOfSystemOfHomogeneousInequalities( ls ) | ( operation ) |
ls is a list of lists of integers. The elements of ls represent the rows of a matrix \(A\). The output is a minimal generating system (Hilbert basis) of the set of nonnegative integer solutions to \(Ax\ge 0\).
If the package NormalizInterface has not been loaded, then Contejean-Devie algorithm is used [CD94] instead (the use of slack variables is described in [CAGB02]).
gap> HilbertBasisOfSystemOfHomogeneousInequalities([[2,-3],[0,1]]); [ [ 1, 0 ], [ 2, 1 ], [ 3, 2 ] ]
‣ EquationsOfGroupGeneratedBy( M ) | ( function ) |
M is a matrix of integers. The output is a pair \([A,m]\) that represents the set of defining equations of the group spanned by the rows of M: \(Ax=0\in \mathbb Z_{n_1}\times \cdots \times \mathbb Z_{n_t}\times \mathbb Z^k\), with \(m=[n_1,\ldots,n_t]\).
gap> EquationsOfGroupGeneratedBy([[1,2,0],[2,-2,2]]); [ [ [ 0, 0, -1 ], [ -2, 1, 3 ] ], [ 2 ] ]
‣ BasisOfGroupGivenByEquations( A, m ) | ( function ) |
A is a matrix of integers and m is a list of positive integers. The output is a basis for the group with defining equations \(Ax=0\in \mathbb Z_{n_1}\times \cdots \times \mathbb Z_{n_t}\times \mathbb Z^k\), with \(m=[n_1,\ldots,n_t]\).
gap> BasisOfGroupGivenByEquations([[0,0,1],[2,-1,-3]],[2]); [ [ -1, -2, 0 ], [ -2, 2, -2 ] ]
Let \(S_1\) and \(S_2\) be two affine semigroups with the same dimension generated by \(A_1\) and \(A_2\), respectively. We say that the affine semigroup \(S\) generated by the union of \(A_1\) and \(A_2\) is a gluing of \(S_1\) and \(S_2\) if \(G(S_1)\cap G(S_2)=d\mathbb Z\) (\(G(\cdot)\) stands for group spanned by) for some \(d\in S_1\cap S_2\).
The algorithm used is explained in [RG99a].
‣ GluingOfAffineSemigroups( a1, a2 ) | ( function ) |
a1, a2 are affine semigroups. Determines if they can be glued, and if so, returns the gluing. Otherwise it returns fail.
gap> a1:=AffineSemigroup([[2,0],[0,2]]); <Affine semigroup in 2 dimensional space, with 2 generators> gap> a2:=AffineSemigroup([[1,1]]); <Affine semigroup in 2 dimensional space, with 1 generators> gap> GluingOfAffineSemigroups(a1,a2); <Affine semigroup in 2 dimensional space, with 3 generators> gap> Generators(last); [ [ 0, 2 ], [ 1, 1 ], [ 2, 0 ] ]
A minimal presentation of an affine semigroup is defined analogously as for numerical semigroups (see Chapter 4). We warn the user to take into account that minimal generators are stored in a set, and thus might be arranged in a different way to the initial input. If a presentation is needed with a certain arrangment in the set of generators, or some of the generators are not necessarily minimal, then GeneratorsOfKernelCongruence (11.3-3) is recommended.
‣ CircuitsOfKernelCongruence( M ) | ( operation ) |
M is matrix with nonnegative integer coefficients. The output is the set of circuits (pairs with minimal support) of the congruence \(\{(x,y)\mid x\textit{M}=y\textit{M}\}\). The computation is performed by using Lemma 8.8 in [ES96].
gap> s:=NumericalSemigroup(4,6,9);; gap> CircuitsOfKernelCongruence([[4],[6],[9]]); [ [ [ 3, 0, 0 ], [ 0, 2, 0 ] ], [ [ 9, 0, 0 ], [ 0, 0, 4 ] ], [ [ 0, 3, 0 ], [ 0, 0, 2 ] ] ] gap> MinimalPresentation(s); [ [ [ 0, 0, 2 ], [ 0, 3, 0 ] ], [ [ 0, 2, 0 ], [ 3, 0, 0 ] ] ]
‣ PrimitiveRelationsOfKernelCongruence( M ) | ( operation ) |
M is matrix with nonnegative integer coefficients. The output is the set of primitive relations of the congruence \(R=\{(x,y)\mid x\textit{M}=y\textit{M}\}\). A pair (relation) \((x,y)\) in \(R\) is primitive if \(x\neq y\) and it cannot be expressed as a sumo of two nonzero pairs in \(R\).
gap> PrimitiveRelationsOfKernelCongruence([[4],[6],[9]]); [ [ [ 0, 0, 2 ], [ 0, 3, 0 ] ], [ [ 0, 0, 2 ], [ 3, 1, 0 ] ], [ [ 0, 0, 4 ], [ 9, 0, 0 ] ], [ [ 0, 1, 2 ], [ 6, 0, 0 ] ], [ [ 0, 2, 0 ], [ 3, 0, 0 ] ] ]
‣ GeneratorsOfKernelCongruence( M ) | ( operation ) |
M is matrix with nonnegative integer coefficients. The output is a system of generators of the congruence \(\{(x,y)\mid x\textit{M}=y\textit{M}\}\).
The main difference with MinimalPresentationOfAffineSemigroup (11.3-6) is that the matrix M can have repeated rows and these are not treated as a set.
gap> M := [[2,0],[0,2],[1,1]]; [ [ 2, 0 ], [ 0, 2 ], [ 1, 1 ] ] gap> GeneratorsOfKernelCongruence(M); [ [ [ 0, 0, 2 ], [ 1, 1, 0 ] ] ]
‣ CanonicalBasisOfKernelCongruence( M, Ord ) | ( operation ) |
M is matrix with nonnegative integer coefficients, Ord a term ordering. The output is a canonical basis of the congruence \(\{(x,y)\mid x\textit{M}=y\textit{M}\}\) (see [RG99b]). This corresponds with the exponents of the Gröbner basis of the kernel ideal of the morphism \(x_i\mapsto Y^{m_i}\), with \(m_i\) the \(i\)th row of \(M\).
Accepted term orderings are lexicographic (MonomialLexOrdering()), graded lexicographic (MonomialGrlexOrdering()) and reversed graded lexicographic (MonomialGrevlexOrdering()).
gap> M:=[[3],[5],[7]];; gap> CanonicalBasisOfKernelCongruence(M,MonomialLexOrdering()); [ [ [ 0, 7, 0 ], [ 0, 0, 5 ] ], [ [ 1, 0, 1 ], [ 0, 2, 0 ] ], [ [ 1, 5, 0 ], [ 0, 0, 4 ] ], [ [ 2, 3, 0 ], [ 0, 0, 3 ] ], [ [ 3, 1, 0 ], [ 0, 0, 2 ] ], [ [ 4, 0, 0 ], [ 0, 1, 1 ] ] ] gap> CanonicalBasisOfKernelCongruence(M,MonomialGrlexOrdering()); [ [ [ 0, 7, 0 ], [ 0, 0, 5 ] ], [ [ 1, 0, 1 ], [ 0, 2, 0 ] ], [ [ 1, 5, 0 ], [ 0, 0, 4 ] ], [ [ 2, 3, 0 ], [ 0, 0, 3 ] ], [ [ 3, 1, 0 ], [ 0, 0, 2 ] ], [ [ 4, 0, 0 ], [ 0, 1, 1 ] ] ] gap> CanonicalBasisOfKernelCongruence(M,MonomialGrevlexOrdering()); [ [ [ 0, 2, 0 ], [ 1, 0, 1 ] ], [ [ 3, 1, 0 ], [ 0, 0, 2 ] ], [ [ 4, 0, 0 ], [ 0, 1, 1 ] ] ]
‣ GraverBasis( M ) | ( operation ) |
M is matrix with integer coefficients. The output is a Graver basis for M.
gap> gr:=GraverBasis([[3,5,7]]); [ [ -7, 0, 3 ], [ -5, 3, 0 ], [ -4, 1, 1 ], [ -3, -1, 2 ], [ -2, -3, 3 ], [ -1, -5, 4 ], [ -1, 2, -1 ], [ 0, -7, 5 ], [ 0, 7, -5 ], [ 1, -2, 1 ], [ 1, 5, -4 ], [ 2, 3, -3 ], [ 3, 1, -2 ], [ 4, -1, -1 ], [ 5, -3, 0 ], [ 7, 0, -3 ] ]
‣ MinimalPresentation( a ) | ( operation ) |
‣ MinimalPresentationOfAffineSemigroup( a ) | ( operation ) |
a is an affine semigroup. The output is a minimal presentation for a.
There are four methods implemented for this function, depending on the packages loaded. All of them use elimination, and Herzog's correspondence, computing the kernel of a ring homomorphism ([Her70]). The fastest procedure is achieved when SingularInterface is loaded, followed by Singular. The procedure that does not use external packages uses internal GAP Gröbner basis computations and thus it is slower. Also in this case, from the Gröbner basis, a minimal set of generating binomials must be refined, and for this Rclasses are used (if NormalizInterface is loaded, then the factorizations are faster). The 4ti2 implementation uses 4ti2 internal Gröbner bases and factorizations are done via zsolve.
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> MinimalPresentation(a); [ [ [ 0, 2, 0 ], [ 1, 0, 1 ] ] ] gap> MinimalPresentationOfAffineSemigroup(a); [ [ [ 0, 2, 0 ], [ 1, 0, 1 ] ] ]
‣ BettiElements( a ) | ( operation ) |
‣ BettiElementsOfAffineSemigroup( a ) | ( operation ) |
a is an affine semigroup. The output is the set of Betti elements of a (defined as for numerical semigroups).
This function relies on the computation of a minimal presentation.
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> BettiElements(a); [ [ 2, 2 ] ] gap> BettiElementsOfAffineSemigroup(a); [ [ 2, 2 ] ]
‣ ShadedSetOfElementInAffineSemigroup( v, a ) | ( function ) |
a is an affine semigroup and v is an element in a. This is a translation to affine semigroups of ShadedSetOfElementInNumericalSemigroup (4.1-7).
‣ IsGeneric( a ) | ( property ) |
‣ IsGenericAffineSemigroup( a ) | ( property ) |
a is an affine semigroup.
The same as IsGenericNumericalSemigroup (4.3-2) but for affine semigroups.
This property implies IsUniquelyPresentedAffineSemigroup (11.3-10).
‣ IsUniquelyPresented( a ) | ( property ) |
‣ IsUniquelyPresentedAffineSemigroup( a ) | ( property ) |
a is an affine semigroup.
The same as the homonym function for numerical semigroups (4.3-1), but for affine semigroups.
‣ DegreesOfPrimitiveElementsOfAffineSemigroup( a ) | ( operation ) |
a is an affine semigroup. The output is the set of primitive elements of a (defined as for numerical semigroups).
This function has three implementations (methods), one using Graver basis via the Lawrence lifting of a and the other (much faster) using NormalizInterface. Also a 4ti2 version using its Graver basis computation is provided.
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> DegreesOfPrimitiveElementsOfAffineSemigroup(a); [ [ 0, 2 ], [ 1, 1 ], [ 2, 0 ], [ 2, 2 ] ]
The invariants presented here are defined as for numerical semigroups (Chapter 9).
As with presentations, the user should take into account that minimal generators are stored in a set, and thus might be arranged in a different way to the initial input.
‣ FactorizationsVectorWRTList( v, ls ) | ( operation ) |
v is a list of nonnegative integers and ls is a list of lists of nonnegative integers. The output is set of factorizations of v in terms of the elements of ls.
If no extra package is loaded, then factorizations are computed recursively; and thus slowly. If NormalizInterface is loaded, then a system of equations is solved with Normaliz, and the performance is much better. If 4ti2Interface is loaded instead, then factorizations are calculated using zsolve command of 4ti2.
gap> FactorizationsVectorWRTList([5,5],[[2,0],[0,2],[1,1]]); [ [ 2, 2, 1 ], [ 1, 1, 3 ], [ 0, 0, 5 ] ]
‣ Factorizations( v, a ) | ( operation ) |
‣ Factorizations( a, v ) | ( operation ) |
v is a list of nonnegative integers and a is an affine semigroup. The output is set of factorizations of v in terms of the minimal generators of of a.
gap> a:=AffineSemigroup([[2,0],[0,2],[1,1]]); <Affine semigroup in 2 dimensional space, with 3 generators> gap> Factorizations([5,5],a); [ [ 2, 1, 2 ], [ 1, 3, 1 ], [ 0, 5, 0 ] ] gap> Factorizations(a,[5,5]); [ [ 2, 1, 2 ], [ 1, 3, 1 ], [ 0, 5, 0 ] ] gap> MinimalGenerators(a); [ [ 0, 2 ], [ 1, 1 ], [ 2, 0 ] ]
‣ Elasticity( n, a ) | ( operation ) |
‣ Elasticity( a, n ) | ( operation ) |
‣ ElasticityOfFactorizationsElementWRTAffineSemigroup( n, a ) | ( function ) |
a is an affine semigroup and n an element of a. The output is the maximum length divided by the minimum length of the factorizations of n in terms of the minimal generating set of a.
gap> a:=AffineSemigroup([[2,0],[0,2],[1,1]]);; gap> Elasticity([5,5],a); 1 gap> Elasticity(a,[5,5]); 1 gap> ElasticityOfFactorizationsElementWRTAffineSemigroup([5,5],a); 1
‣ Elasticity( a ) | ( operation ) |
‣ ElasticityOfAffineSemigroup( a ) | ( operation ) |
a is an affine semigroup. The output is the elasticity of a (defined as for numerical semigroups).
The procedure used is based on [Phi10], where it is shown that the elasticity can be computed by using circuits. The set of circuits is calculated using [ES96].
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> Elasticity(a); 1 gap> ElasticityOfAffineSemigroup(a); 1
‣ DeltaSet( a ) | ( operation ) |
‣ DeltaSetOfAffineSemigroup( a ) | ( function ) |
a is an affine semigroup. The output is the Delta set of a (defined as for numerical semigroups). The the procedure used is explained in [GOW19].
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> DeltaSet(a); [ ] gap> s:=NumericalSemigroup(10,13,15,47);; gap> a:=AsAffineSemigroup(s);; gap> DeltaSetOfAffineSemigroup(a); [ 1, 2, 3, 5 ]
‣ CatenaryDegree( a ) | ( operation ) |
‣ CatenaryDegreeOfAffineSemigroup( a ) | ( function ) |
a is an affine semigroup. The output is the catenary degree of a (defined as for numerical semigroups).
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> CatenaryDegree(a); 2 gap> CatenaryDegreeOfAffineSemigroup(a); 2
‣ EqualCatenaryDegreeOfAffineSemigroup( a ) | ( function ) |
a is an affine semigroup. The output is the equal catenary degree of a (defined as for numerical semigroups).
This function relies on the results presented in [GSOSt13].
‣ HomogeneousCatenaryDegreeOfAffineSemigroup( a ) | ( function ) |
a is an affine semigroup. The output is the homogeneous catenary degree of a (defined as for numerical semigroups).
This function is based on [GSOSt13].
‣ MonotoneCatenaryDegreeOfAffineSemigroup( a ) | ( function ) |
a is an affine semigroup. The output is the monotone catenary degree of a (defined as for numerical semigroups), computed as explained in [Phi10].
gap> a:=AffineSemigroup("inequalities",[[2,-1],[-1,3]]); <Affine semigroup> gap> GeneratorsOfAffineSemigroup(a); [ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 3, 1 ] ] gap> CatenaryDegreeOfAffineSemigroup(a); 3 gap> EqualCatenaryDegreeOfAffineSemigroup(a); 2 gap> HomogeneousCatenaryDegreeOfAffineSemigroup(a); 3 gap> MonotoneCatenaryDegreeOfAffineSemigroup(a); 3
‣ TameDegree( a ) | ( operation ) |
‣ TameDegreeOfAffineSemigroup( a ) | ( operation ) |
a is an affine semigroup. The output is the tame degree of a (defined as for numerical semigroups). If a is given by equations (or its equations are known), then the procedure explained in [GOW19] is used.
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> TameDegree(a); 2 gap> TameDegreeOfAffineSemigroup(a); 2
‣ OmegaPrimality( v, a ) | ( operation ) |
‣ OmegaPrimality( a, v ) | ( operation ) |
‣ OmegaPrimalityOfElementInAffineSemigroup( v, a ) | ( operation ) |
v is a list of nonnegative integers and a is an affine semigroup. The output is the omega primality of a (defined as for numerical semigroups). Returns 0 if the element is not in the semigroup.
The implementation of this procedure is performed as explained in [BGG11] (also, if the semigroup has defining equations, then it takes advantage of this fact as explained in this reference).
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> OmegaPrimality(a,[5,5]); 6 gap> OmegaPrimality([5,5],a); 6 gap> OmegaPrimalityOfElementInAffineSemigroup([5,5],a); 6
‣ OmegaPrimality( a ) | ( operation ) |
‣ OmegaPrimalityOfAffineSemigroup( a ) | ( function ) |
a is an affine semigroup. The output is the omega primality of a (defined as for numerical semigroups).
gap> a:=AffineSemigroup([2,0],[0,2],[1,1]);; gap> OmegaPrimality(a); 2 gap> OmegaPrimalityOfAffineSemigroup(a); 2
Let \(S\) be an affine semigroup contained in \(\mathbb{N}^n\) for some positive integer \(n\). We say that \(I\subseteq \mathbb{Z}^n\) is an ideal of \(S\) if \(I+S\subseteq I\). A subset \(X\) is a system of generators of \(I\) if \(I=\bigcup_{i\in X} i+S\). And this system is a minimal system if no proper subset of \(X\) generates \(I\). In this section we present some procedures dealing with finitely generated ideals of affine semigroups.
‣ IdealOfAffineSemigroup( l, S ) | ( function ) |
‣ +( l, S ) | ( function ) |
S is an affine semigroup, and l a list of lists of integers (with the same length as the dimension of S) or l is a list of integers with the same length as the dimension of S (a principal ideal). The output is the ideal of S generated by l.
There are several shortcuts for this function, as shown in the example.
gap> a:=AffineSemigroup([2,0],[0,2]);; gap> i:=IdealOfAffineSemigroup([[1,0],[0,3]],a); <Ideal of affine semigroup> gap> [[1,0],[0,3]]+a=i; true gap> [0,1]+a; <Ideal of affine semigroup> gap> IsSubset(i,[1,0]+a); true gap> IsSubset([1,0]+a,i); false
‣ IsIdealOfAffineSemigroup( Obj ) | ( function ) |
Tests if the object Obj is an ideal of an affine semigroup.
gap> i:=[2,0]+AffineSemigroup([2,0],[0,2]);; gap> IsIdealOfAffineSemigroup(i); true
‣ MinimalGenerators( I ) | ( attribute ) |
I is an ideal of a numerical semigroup. The output is the minimal system of generators of I.
gap> i:=[[1,0],[3,0]]+AffineSemigroup([2,0],[0,2]);; gap> MinimalGenerators(i); [ [ 1, 0 ] ]
‣ Generators( I ) | ( attribute ) |
I is an ideal of an affine semigroup. The output is a system of generators of the ideal.
gap> i:=[[1,0],[3,0]]+AffineSemigroup([2,0],[0,2]);; gap> Generators(i); [ [ 1, 0 ], [ 3, 0 ] ]
‣ AmbientAffineSemigroupOfIdeal( I ) | ( function ) |
I is an ideal of an affine semigroup, say \(S\). The output is \(S\).
gap> i:=[2,0]+AffineSemigroup([2,0],[0,2]);; gap> AmbientAffineSemigroupOfIdeal(i); <Affine semigroup in 2 dimensional space, with 2 generators>
‣ IsIntegral( I ) | ( property ) |
‣ IsIntegralIdealOfAffineSemigroup( I ) | ( property ) |
I is an ideal of an affine semigroup, say \(S\). Detects if \(I\subseteq S\).
gap> a:=AffineSemigroup([2,0],[0,2]);; gap> IsIntegral([1,0]+a); false gap> IsIntegral([2,0]+a); true
‣ BelongsToIdealOfAffineSemigroup( l, I ) | ( function ) |
‣ \in( l, I ) | ( operation ) |
I is an ideal of an affine semigroup, l is list of integers. The output is true if l belongs to I.
l in I can be used for short.
gap> a:=AffineSemigroup([2,0],[0,2]);; gap> i:=[2,0]+a; <Ideal of affine semigroup> gap> [2,0] in i; true gap> [4,4] in i; true gap> [1,2] in i; false
‣ SumIdealsOfAffinSemigroup( I, J ) | ( function ) |
‣ +( I, J ) | ( operation ) |
I, J are ideals of an affine semigroup. The output is the sum of both ideals \(\{ i+j \ |\ i\in \textit{I}, j\in \textit{J}\}\).
gap> a:=AffineSemigroup([2,0],[0,2]);; gap> i:=[2,0]+a; <Ideal of affine semigroup> gap> j:=[[1,0],[0,1]]+a; <Ideal of affine semigroup> gap> i+j; <Ideal of affine semigroup> gap> MinimalGenerators(i+j); [ [ 2, 1 ], [ 3, 0 ] ]
‣ MultipleOfIdealOfAffineSemigroup( n, I ) | ( function ) |
‣ *( n, I ) | ( function ) |
I is an ideal of an affine semigroup, n is a non negative integer. The output is the ideal \(\textit{I}+\cdots+\textit{I}\) (n times).
n * I can be used for short.
gap> a:=AffineSemigroup([2,0],[0,2]);; gap> j:=[[1,0],[0,1]]+a; <Ideal of affine semigroup> gap> 2*j; <Ideal of affine semigroup> gap> MinimalGenerators(2*j); [ [ 0, 2 ], [ 1, 1 ], [ 2, 0 ] ]
‣ TranslationOfIdealOfAffineSemigroup( l, I ) | ( function ) |
‣ +( l, I ) | ( function ) |
Given an ideal I of an affine semigroup \(S\) and a list of integers l, returns an ideal of the numerical semigroup S generated by \(\{i_1+l,\ldots,i_n+l\}\), where \(\{i_1,\ldots,i_n\}\) is the system of generators of I.
As a synonym to TranslationOfIdealOfNumericalSemigroup(l, I), the expression l + I may be used.
gap> a:=AffineSemigroup([2,0],[0,2]);; gap> j:=[[1,0],[0,1]]+a;; gap> [2,2]+j; <Ideal of affine semigroup> gap> MinimalGenerators([2,2]+j); [ [ 2, 3 ], [ 3, 2 ] ]
‣ UnionIdealsOfAffineSemigroup( I, J ) | ( function ) |
‣ Union( I, J ) | ( function ) |
I, J are ideals of an affine semigroup. The output is the union of both ideals.
gap> a:=AffineSemigroup([2,0],[0,2]);; gap> i:=[2,0]+a;; gap> j:=[[1,0],[0,1]]+a;; gap> Union(i,j); <Ideal of affine semigroup> gap> MinimalGenerators(Union(i,j)); [ [ 0, 1 ], [ 1, 0 ], [ 2, 0 ] ]
‣ Intersection( I, J ) | ( operation ) |
‣ IntersectionIdealsOfAffineSemigroup( I, J ) | ( function ) |
Given two ideals I and J of an affine semigroup S returns the ideal of the affine semigroup S that is the intersection of the ideals I and J.
gap> a:=AffineSemigroup([1,0],[0,1]);; gap> i:=[2,0]+a;; gap> j:=[[1,0],[0,1]]+a;; gap> Intersection(i,j); #I Using contejeanDevieAlgorithm for Hilbert Basis. Please, consider using NormalizInterface, 4ti2Interface or 4ti2gap. #I Using contejeanDevieAlgorithm for Hilbert Basis. Please, consider using NormalizInterface, 4ti2Interface or 4ti2gap. <Ideal of affine semigroup> gap> MinimalGenerators(Intersection(i,j)); #I Using contejeanDevieAlgorithm for Hilbert Basis. Please, consider using NormalizInterface, 4ti2Interface or 4ti2gap. #I Using contejeanDevieAlgorithm for Hilbert Basis. Please, consider using NormalizInterface, 4ti2Interface or 4ti2gap. [ [ 2, 0 ] ]
‣ MaximalIdeal( S ) | ( operation ) |
Returns the maximal ideal of the affine semigroup S.
gap> a:=AffineSemigroup([2,0],[0,2]);; gap> MinimalGenerators(MaximalIdeal(a)); [ [ 0, 2 ], [ 2, 0 ] ]
generated by GAPDoc2HTML