Chain associated to a numerical semigroup

Definition

Let \(S\) be a numerical semigroup such that \(S \ne \mathbb{N}\) and let \(\mathcal{G}(\mathcal{S})\) be the directed graph of all numerical semigroups. If \(F(T)\) denotes the Frobenius number of any numerical semigroup \(T\), the path

• \(S_0 = S\),

• \(S_{i+1} = \begin{cases} S_i \cup \{F(S_i)\} & \text{ if } S_i \ne \mathbb{N}, \\ \mathbb{N} & \text{ otherwise,}\end{cases}\)

is well defined, since \(S \cup \{F(S)\}\) is a numerical semigroup, and finite, since \(\mathbb{N} \setminus S\) is finite. Then, there exists a positive integer \(k\) so that

\[ S_0 \subsetneq S_1 \subsetneq \cdots \subsetneq S_k = \mathbb{N}. \]

Moreover, this path connects \(S\) with \(\mathbb{N}\) in \(\mathcal{G}(\mathcal{S})\) and is unique. It is defined the chain associated to \(S\), denoted by \(Ch(S)\), as

\[ Ch(S) = \{S_0, S_1, \ldots, S_k \}. \]

Examples

\(\circ\) Let \(S = \langle 3,5,7 \rangle\). Its Frobenius number is \(F(S) = 4\) and \(S_1 = S \cup \{4\} = \{0, 3, \rightarrow \} = \langle 3, 4, 5 \rangle\). Now, \(F(S_1) = 2\) and \(S_2 = S_1 \cup \{2\} = \{0, 2, \rightarrow\} = \langle 2, 3 \rangle\). Finally, \(S_3 = S_2 \cup \{1\} = \mathbb{N}\). The chain associated to \(S\) is

\[ Ch(S) = \{S_0, S_1, S_2, S_3\} = \{S, \langle 3,4,5 \rangle, \langle 2, 3 \rangle, \mathbb{N}\}. \]

Examples with GAP

Nowadays, there are no functions in package NumericalSgps related to chain associated to a numerical semigroup. However, given a numerical semigroup \(S\), the following function returns the chain associated to \(S\).

gap> ChainOfNumericalSemigroup := function(S)
>       local g, C, i, F, Min_gen, I, T;
>       if not IsNumericalSemigroup(S) then
>               Error("The argument must be a Numerical Semigroup");
>       fi;
>       g := Length(Gaps(S));
>       C := [S];
>       for i in [1..g] do
>               F := FrobeniusNumber(C[i]);
>               Min_gen := MinimalGenerators(C[i]);
>               I := Union(Min_gen, [F]);
>               T := NumericalSemigroupByGenerators(I);
>               Add(C, T);
>       od;
>       return C;
> end;
function( S ) ... end

\(\diamond\) Let \(S = \langle 7, 8, 9, 19, 20 \rangle\), in GAP:

gap> S := NumericalSemigroup(7, 8, 9, 19, 20);
<Numerical semigroup with 5 generators>

The chain associated of \(S\) is as follows.

gap> C := ChainOfNumericalSemigroup(S);
[ <Numerical semigroup with 5 generators>,
  <Numerical semigroup with 5 generators>,
  <Numerical semigroup with 5 generators>,
  <Numerical semigroup with 6 generators>,
  <Numerical semigroup with 7 generators>,
  <Numerical semigroup with 6 generators>,
  <Numerical semigroup with 5 generators>,
  <Numerical semigroup with 4 generators>,
  <Numerical semigroup with 3 generators>,
  <Numerical semigroup with 2 generators>,
  <The numerical semigroup N> ]
gap> List(C, l -> MinimalGenerators(l));
[ [ 7, 8, 9, 19, 20 ], [ 7, 8, 9, 13, 19 ], [ 7, 8, 9, 12, 13 ],
  [ 7, 8, 9, 11, 12, 13 ], [ 7 .. 13 ], [ 6 .. 11 ], [ 5 .. 9 ],
  [ 4 .. 7 ], [ 3 .. 5 ], [ 2, 3 ], [ 1 ] ]

Therefore,

\[ Ch(S) = \{S, \langle 7, 8, 9, 13, 19 \rangle, \langle 7, 8, 9, 12, 13 \rangle, \]

\[ \langle 7, 8, 9, 11, 12, 13 \rangle, \{7, \rightarrow\}, \{6, \rightarrow\}, \ldots, \{2, \rightarrow\}, \mathbb{N}\}. \]

The chain would be as follows.

\(\diamond\) Let \(S = \langle 5, 9, 12 \rangle\), in GAP:

gap> S := NumericalSemigroup(5, 9, 12);
<Numerical semigroup with 3 generators>

Given a numerical semigroup \(S\), the following function returns the graph (in dot) representing the chain associated to \(S\).

gap> DotChainOfNumericalSemigroup := function(S)
>       local hasse, SystemOfGeneratorsToString, chain, n, out, output, i, c, r;
>       if not IsNumericalSemigroup(S) then
>           Error("The argument must be a Numerical Semigroup");
>       fi;
>       hasse:=function(rel)
>           local dom, out;
>           dom:=Flat(rel);
>           out:=Filtered(rel, p-> ForAny(dom, x->([p[1],x] in rel) and ([x,p[2]] in rel)));
>           return Difference(rel,out);
>         end;
>       SystemOfGeneratorsToString := function(sg)
>          return Concatenation("〈 ", JoinStringsWithSeparator(sg, ", "), " 〉");
>       end;
>       chain := Reversed(ChainOfNumericalSemigroup(S));
>       n := Length(chain);
>       out := "";
>       output := OutputTextString(out, true);
>       SetPrintFormattingStatus(output, false);
>       AppendTo(output,"digraph  NSGraph{rankdir = TB; edge[dir=back];\n");
>       for i in [1..n] do
>           if IsIrreducible(chain[i]) then 
>               AppendTo(output,i," [label=\"",SystemOfGeneratorsToString(MinimalGenerators(chain[i])) ,"\", style=filled];\n");
>           else 
>               AppendTo(output,i," [label=\"",SystemOfGeneratorsToString(MinimalGenerators(chain[i])) ,"\"];\n");
>           fi;
>       od;
>       c := [];
>       for i in [1..(n-1)] do
>           Add(c, [i, i+1]);
>       od;
>       c:=hasse(c);
>       for r in c do
>           AppendTo(output,r[1]," -> ",r[2],";\n");
>       od;
>       AppendTo(output, "}");
>       CloseStream(output);
>       return out;  
> end;
function( S ) ... end

gap> h := DotChainOfNumericalSemigroup(S);;
digraph  NSGraph{rankdir = TB; edge[dir=back];
1 [label="〈 1 〉", style=filled];
2 [label="〈 2, 3 〉", style=filled];
3 [label="〈 3, 4, 5 〉", style=filled];
4 [label="〈 4, 5, 6, 7 〉"];
5 [label="〈 5, 6, 7, 8, 9 〉"];
6 [label="〈 5, 7, 8, 9, 11 〉"];
7 [label="〈 5, 8, 9, 11, 12 〉"];
8 [label="〈 5, 9, 11, 12, 13 〉"];
9 [label="〈 5, 9, 12, 13, 16 〉"];
10 [label="〈 5, 9, 12, 16 〉"];
11 [label="〈 5, 9, 12 〉"];
1 -> 2;
2 -> 3;
3 -> 4;
4 -> 5;
5 -> 6;
6 -> 7;
7 -> 8;
8 -> 9;
9 -> 10;
10 -> 11;
}

The chain associated to \(S\) is as follows.

The nodes with grey background are irreducible numerical semigroups.

References

Delgado, M., P. A. Garcia-Sanchez, and J. Morais. 2024. “NumericalSgps, a Package for Numerical Semigroups, Version 1.4.0.” https://gap-packages.github.io/ numericalsgps.

Rosales, J. C., and P. A. Garcı́a-Sánchez. 2009. Numerical Semigroups. Springer.