NumericalSgps an introduction - SSC 2023

Gaps and small elements

Recall that a numerical semigroup \(S\) is a subset of the set of nonnegative integers, \(\mathbb{N}\), that is closed under addition, \(0\in S\), and there are only finitely many positive integers not belonging to \(S\). The first two contidions imply that \((S,+)\) is a submonoid of \((\mathbb{N},+)\).

The set \(\mathbb{N}\setminus S\) is known as the set of gaps of \(S\), denoted \(\operatorname{G}(S)\), and the largest integer not belonging to \(S\) is its Frobenius number, \(\operatorname{F}(S)\). The conductor of \(S\), \(\operatorname{C}(S)\) is the smallest integer having the following property: \(\operatorname{C}(S)+\mathbb{N}\subseteq S\).

LoadPackage("num");

true

s:=NumericalSemigroupByGaps([1..5]);

Numerical semigroup

10 in s;

true

FrobeniusNumber(s);

5

Gaps(s);

[ 1, 2, 3, 4, 5 ]

We can see which elements in the semigroup are in a given interval.

Intersection(s,[0..30]);

[ 0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 ]

Or which is the \(i^{th}\) element in the semigroup.

s[1];

0

s[2];

6

Or even, what are the first \(n\) elements in the semigroup.

s{[1..20]};

[ 0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 ]

The genus of \(S\) is the cardinality of \(\mathbb{N}\setminus S\), denoted \(\operatorname{g}(S)\).

Genus(s);

5

The set \(S\cap[0,\operatorname{C}(S)]\) is known as the set of small elements of \(S\) (if we remove the conductor, then somtimes is called the set of left or sporadic elements).

SmallElements(s);

[ 0, 6 ]

s=NumericalSemigroupBySmallElements([0,6]);

true

Denote by \(\operatorname{n}(S)=\#\{s \in S : s<\operatorname{F}(S)\}\). It follows that \(\operatorname{n}(S)+\operatorname{g}(S)=\operatorname{F}(S)+1\). Since for every \(n\in S\) with \(n<\operatorname{F}(S)\) we have that \(\operatorname{F}(S)-n\not\in S\), we have that there are less left elements than gaps, and so the following inequality always holds.

Genus(s)>= (FrobeniusNumber(s)+1)/2;

true

The intersection of two numerical semigroups is again a numerical semigroup.

t:=NumericalSemigroupBySmallElements([0,5,10,15]);

Numerical semigroup

tis:=Intersection(t,s);

Numerical semigroup

SmallElements(tis);

[ 0, 10, 15 ]

Adding a gap to a numerical semigroup does not in general produce a numerical semigroup. There are some gaps that have the property that added to the numerical semigroup yield a new numerical semigroup. If \(g\) is one of these gaps and \(S\) is our numerical semigroup, then \(g+S\) must be a subset of \(S\cup\{g\}\), and also \(kg\in S\cup\{g\}\) for every nonnegative integer \(k\). This last condition is equivalent to \(2g\in S\). Notice that \(\operatorname{F}(S)\) fulfils these conditions, and so \(S\cup\{\operatorname{F}(S)\}\) is always a numerical semigroup whenever \(S\setminus\mathbb{N}\).

The set of gaps that can be added to a numerical semigroup so that the new set is a numerical semigroup are called special gaps.

SpecialGaps(s);

[ 3, 4, 5 ]

so:=AddSpecialGapOfNumericalSemigroup(4,s);
SmallElements(so);

Numerical semigroup

[ 0, 4, 6 ]

We can repeat the process until we reach \(\mathbb{N}\), calculating in this way the set of all over-semigroups of our numerical semigroup.

os:=OverSemigroups(s);;
List(os,SmallElements);

[ [ 0 ], [ 0, 2 ], [ 0, 2, 4 ], [ 0, 2, 4, 6 ], [ 0, 3 ], [ 0, 3, 4, 6 ], [ 0, 3, 5 ], [ 0, 3, 6 ], [ 0, 4 ], [ 0, 4, 6 ], [ 0, 5 ], [ 0, 6 ] ]

s:=NumericalSemigroup(4,5,7);;
JupyterSplashDot(DotOverSemigroups(s));

Minimal generators

Given \(A\) a set of positive integers, the submonoid (under addition) of \(\mathbb{N}\) generated by \(A\) is the intersection of all submonoids of \(\mathbb{N}\) contanining \(A\), which can be described as \[ \langle A\rangle = \left\{ \sum_{i=1}^n \lambda_i a_i : n\in\mathbb{N}, \lambda_i\in \mathbb{N}, a_i\in A\right\}.\] The submonoid \(\langle A\rangle\) is a numerical semigroup if and only if \(\gcd(A)=1\).

We say that \(A\) is a generating system of \(S\) if \(S=\langle A\rangle\), and that \(A\) is a minimal generating system of \(S\) if, in addition, no proper subset of \(A\) generates \(S\).

Every numerical semgiroup has a unique minimal generating system: \(S^*\setminus (S^*+S^*)\), with \(S^*=S\setminus\{0\}\). Sometimes the elements in the minimal generating system of \(S\) are called minimal generators, atoms, irreducible, or primitive elements of \(S\). The cardinality of the minimal generating system of \(S\) is known as the embedding dimension of \(S\), denoted \(\operatorname{e}(S)\).

Generators(s);

[ 4, 5, 7 ]

MinimalGenerators(s);

[ 4, 5, 7 ]

EmbeddingDimension(s);

3

MinimalGenerators(tis);

[ 10, 15, 16, 17, 18, 19, 21, 22, 23, 24 ]

EmbeddingDimension(tis);

10

We can define a numerical semigoup by giving one of its generating sets.

s:=NumericalSemigroup(3,5,7,10,6);

Numerical semigroup with 5 generators

MinimalGenerators(s);

[ 3, 5, 7 ]

The multiplicity of a numerical semigroup \(S\) is the least positive integer in \(S\) (and coincides with its smallest minimal generator), we will denote it by \(\operatorname{m}(S)\).

Multiplicity(s);

3

No two minimal generators of \(S\) can be congruent modulo de multiplicity, and thus \(\operatorname{e}(S)\le \operatorname{m}(S)\).

The sum of two numerical semigroups is a numerical semigroup, and the generators of the sum is the union of the generators of the two given numerical semigroups.

tus:=t+s;

Numerical semigroup with 7 generators

tus=NumericalSemigroup(Union(MinimalGenerators(t),MinimalGenerators(s)));

true

An element \(n\in S\) is a minimal generator if and only if \(S\setminus\{n\}\) is a minimal generator.

SmallElements(s);

[ 0, 3, 5 ]

sr:=RemoveMinimalGeneratorFromNumericalSemigroup(3,s);
MinimalGenerators(sr);

Numerical semigroup with 5 generators

[ 5, 6, 7, 8, 9 ]

Every time we remove a minimal generator, we obtain a new semigroup whose genus increases by one. If we start with \(\mathbb{N}\), this procedure gives a way to compute the set of numerical semigroups with a given genus.

l20:=NumericalSemigroupsWithGenus(20);;
Length(l20);

37396

Let us depict the set of numerical semigroups of genus up to four.

c:=Union(List([0..4],i->NumericalSemigroupsWithGenus(i)));;
cc:=Filtered(Cartesian(c,c),p->IsSubset(p[2],p[1]) and IsSubset(MinimalGenerators(p[2]),Difference(p[2],p[1])) 
                                and Length(Difference(p[2],p[1]))=1);;
d:=Domain(List(c,MinimalGenerators));;
pairs:=List(cc,p->Tuple([MinimalGenerators(p[1]),MinimalGenerators(p[2])]));;
br:=BinaryRelationByElements(d,pairs);

<object>

JupyterSplashDot(DotBinaryRelation(br));

For any numerical semigroup \(S\) (other than \(\mathbb{N}\)), the set \(T=S\cup\{\operatorname{F}(S)\}\) is also a numerical semigroup. The semigroup \(S\) is obtained from \(T\) by removing a minimal generator larger than its Frobenius number.

So if we remove minimal generators larger than the Frobenius number, we still obtain the same numerical semigroups, but the above directed graph becomes a tree.

cc:=Filtered(Cartesian(c,c),p->IsSubset(p[2],p[1]) and Difference(p[2],p[1])=[FrobeniusNumber(p[1])]);;
pairs:=List(cc,p->Tuple([MinimalGenerators(p[1]),MinimalGenerators(p[2])]));;
br:=BinaryRelationByElements(d,pairs);

<object>

JupyterSplashDot(DotBinaryRelation(br));

Exercise

Given a numerical semigroup \(S\) and a finite set of nonnegative integers \(F\), write a procedure that checks if \(S\cup F\) is a numerical semigroup (do the same for \(S\setminus F\)).

Exercise

Write a procedure to check Wilf’s conjecture for numerical semigroups generated by at most four generators no larger than 40.

Apéry sets

One of the most important tools when studying numerical semigroups is the concept of Apéry sets. Given a numerical semigroup \(S\) and \(n\) a nonzero element of \(S\) (one can define also Apéry sets for elements outside \(S\), but we are not going to deal with them here), the Apéry set of \(n\) in \(S\) (or of \(S\) with respect to \(n\)) is the set \[\operatorname{Ap}(S,n)=\{ s\in S : s-n\not\in S\}.\] This set has precisely \(n\) elements, one in each congruence class modulo \(n\). Moreover, for every \(s\in S\) there exist unique \(k\in \mathbb{N}\) and \(w\in \operatorname{Ap}(S,n)\) such that \(s=kn+w\). This in particular implies that the embedding dimension of \(S\) is always smaller than or equal to its multiplicity, since \((\operatorname{Ap}(S,n))\setminus\{0\}\cup\{n\}\) is a minimal generating set of \(S\) for all \(n\in S\setminus\{0\}\).

s:=NumericalSemigroup(6,10,15);;
AperyList(s,12);

[ 0, 25, 26, 15, 16, 41, 6, 31, 20, 21, 10, 35 ]

If the second argument is not given, then the Apéry set is taken with respect to the multiplicity of the numerical semigroup.

AperyList(s);

[ 0, 25, 20, 15, 10, 35 ]

The output is arranged in a list, so that in the \(i^{th}\) position (starting in 0) we find the least element in \(S\) congruent with \(i\) modulo \(n\). In this way, membership to \(S\) becomes trivial once an Apéry set of the semigroup is known.

This has some other interesting consequences:

FrobeniusNumber(s)=Maximum(AperyList(s,12))-12;

true

Genus(s)=(Sum(AperyList(s,12)))/12- (12-1)/2;

true

Let \(m\) be the multiplcity of \(S\), and let \(w_i\) be the element in the Apéry set of \(m\) in \(S\) congruent with \(i\) modulo \(m\). We can write \(w_i=k_im+i\). The tuple \((k_1,\dots,k_{m-1})\) is known as the Kunz coordinates of \(S\).

KunzCoordinates(s);

[ 4, 3, 2, 1, 5 ]

Notice that every nonnegative integer \(x\) can be written as \(x=k m+i\) for some \(k,n\in \mathbb{N}\), with \(i<m\). It follows easily that \(x\in S\) if and only if \(k\ge k_i\). So it is at no surprise that the genus is precisely the sum of the Kunz coordinates of \(S\), which is just a reformulation of the above statement on the genus.

Genus(s)=Sum(KunzCoordinates(s));

true

Notice that \(w_i+w_j\in S\) for all \(i,j\), and thus \(w_i+w_j=k_{ij}m+w_{i+j \bmod n}\), this imposes some conditions on the tuples \((k_1,\dots,k_{m-1})\) that can be Kunz coordinates of a numerical semigroup with multiplicity \(m\). In fact, there is a one to one correspondence between numerical semigroups with multiplicity \(m\) and integers points in what it is called the Kunz polyhedron.

KunzPolytope(6);

[ [ 1, 0, 0, 0, 0, -1 ], [ 0, 1, 0, 0, 0, -1 ], [ 0, 0, 1, 0, 0, -1 ], [ 0, 0, 0, 1, 0, -1 ], [ 0, 0, 0, 0, 1, -1 ], [ 2, -1, 0, 0, 0, 0 ], [ 1, 1, -1, 0, 0, 0 ], [ 1, 0, 1, -1, 0, 0 ], [ 1, 0, 0, 1, -1, 0 ], [ 0, 2, 0, -1, 0, 0 ], [ 0, 1, 1, 0, -1, 0 ], [ -1, 1, 0, 0, 1, 1 ], [ -1, 0, 1, 1, 0, 1 ], [ 0, -1, 1, 0, 1, 1 ], [ 0, -1, 0, 2, 0, 1 ], [ 0, 0, -1, 1, 1, 1 ], [ 0, 0, 0, -1, 2, 1 ] ]

The first elements of this output mean that \(x_i\ge 1\), while for instance \([ 1, 0, 1, -1, 0, 0 ]\) translates to \(x_1+x_3\ge x_4\), and $ [ 0, 0, 0, -1, 2, 1 ]$ to \(2x_5+1\ge x_4\).

x:=List([1..5],i->Indeterminate(Rationals,i));;
x1:=Concatenation(x,[1]);;

\(w_i+w_j\ge w_{i+j \mod m}\)

for eq in KunzPolytope(6) do Print(eq*x1," ≥ 0\n"); od;

x_1-1 ≥ 0
x_2-1 ≥ 0
x_3-1 ≥ 0
x_4-1 ≥ 0
x_5-1 ≥ 0
2*x_1-x_2 ≥ 0
x_1+x_2-x_3 ≥ 0
x_1+x_3-x_4 ≥ 0
x_1+x_4-x_5 ≥ 0
2*x_2-x_4 ≥ 0
x_2+x_3-x_5 ≥ 0
-x_1+x_2+x_5+1 ≥ 0
-x_1+x_3+x_4+1 ≥ 0
-x_2+x_3+x_5+1 ≥ 0
-x_2+2*x_4+1 ≥ 0
-x_3+x_4+x_5+1 ≥ 0
-x_4+2*x_5+1 ≥ 0

The genus of a numerical semigroup \(S\) with Kunz coordinates \((x_1,\dots,x_{m-1})\) is \(x_1+\dots+x_{m-1}\). Thus if we want to compute all numerical semigrops withe genus 13 and genus six, we just need to determine the set of integer solutions of the above inequalities and the equation \(x_1+\dots+x_5=13\).

As we have seen, Apéry sets are a useful tool to check membership to the semigroup. If we remove one of the minimal generators, then the corresponding Kunz coordinate will be incresed by one, and if we add a special gap, then the corresponding Kunz coordinate will decrease by one.

MinimalGenerators(s);

[ 6, 10, 15 ]

AperyList(s);

[ 0, 25, 20, 15, 10, 35 ]

AperyList(RemoveMinimalGeneratorFromNumericalSemigroup(10,s));

[ 0, 25, 20, 15, 16, 35 ]

SpecialGaps(s);

[ 29 ]

AperyList(AddSpecialGapOfNumericalSemigroup(29,s));

[ 0, 25, 20, 15, 10, 29 ]

Exercise

Provide several examples to check how Apéry sets behave under intersections and sums of numerical semigroups.