Relation order of a numerical semigroup

Definition

Let \(S\) be a numerical semigroup. It is defined the relation \(\le_S\) over \(\mathbb{Z}\) as follows:

\[ a \le_S b \Longleftrightarrow b - a \in S. \]

It can be proven that \(\le_S\) is a partial order relation. From this relation order is possible to characterize the pseudo-Frobenius numbers of \(S\).

Examples

\(\circ\) Let \(S = \langle 10, 14, 17, 21 \rangle\) and the integers \(x_1 = 8, x_2 = 62\). For \(x_1\), there is no positive integer \(y \ne x_1\) such that \(y \le_S x_1\), since \(x_1 - y = 8 - y < 10\) and the only element in \(S\) smaller than \(10\) is \(0\), therefore \(x_1\) is a minimal in \(\mathbb{N}\), but is not minimal in \(\mathbb{Z}\), since \(-2 \le_S x_1\). On the other hand, for \(x_2 = 62\) we have that \(10 \le_S 62\) and \(62 \le_S 72\).

\(\circ\) Let \(S\) be a numerical semigroup and let \(F(S)\) be the Frobenius number of \(S\). If we suppose that \(F(S) \le_S x\) for some \(x \in \mathbb{Z} \setminus S\), then there exists \(s \in S\) such that \(x = F(S) + s\), but that means \(x \in S\), which is a contradiction. Therefore, \(F(S)\) is maximal in \(\mathbb{Z} \setminus S\).

Examples with GAP

The following examples are made with the package NumericalSgps in GAP.

\(\diamond\) Let \(S = \langle 15,16,17,20 \rangle\), in GAP:

gap> S := NumericalSemigroup(15,16,17,20);
<Numerical semigroup with 4 generators>

Given a numerical semigroup \(S\) and a list of integers \(A\), the function HasseDiagramOfNumericalSemigroup returns a binary relation which is the Hasse diagram of \(A\) with respect to the order \(\le_S\).

gap> A := [3, 20, 37, 57, 60];
[ 3, 20, 37, 57, 60 ]
gap> h := HasseDiagramOfNumericalSemigroup(S, A);
<general mapping: Domain([ 3, 20, 37, 57, 60 ]) -> Domain(
[ 3, 20, 37, 57, 60 ]) >

Moreover, given a binary relation, the function DotBinaryRelation returns a GraphViz dot that represents the given binary relation.

gap> DotBinaryRelation(h);
"digraph  NSGraph{rankdir = TB; edge[dir=back];\n1 [label=\"3\"];\n2 [lab\
el=\"20\"];\n3 [label=\"37\"];\n4 [label=\"57\"];\n5 [label=\"60\"];\n2 -\
> 1;\n3 -> 2;\n5 -> 2;\n4 -> 3;\n}"
gap> Print(DotBinaryRelation(h));
digraph  NSGraph{rankdir = TB; edge[dir=back];
1 [label="3"];
2 [label="20"];
3 [label="37"];
4 [label="57"];
5 [label="60"];
2 -> 1;
3 -> 2;
5 -> 2;
4 -> 3;
}

The graph obtained is as follows.

NSGraph 1 3 2 20 2->1 3 37 3->2 4 57 4->3 5 60 5->2

\(\diamond\) Let \(S = \langle 18, 22, 25, 30 \rangle\), in GAP:

gap> S := NumericalSemigroup(18, 22, 25, 30);
<Numerical semigroup with 4 generators>

Given a numerical semigroup and two integers \(a,b \in \mathbb{Z}\), the following function returns true if \(a \le_S b\) and false otherwise.

gap> AreRelatedNumericalSemigroup := function(S,a,b)
>       if not IsNumericalSemigroup(S) then
>               Error("First argument must be a Numerical Semigroup");
>       fi;
>       if not IsInt(a) then
>               Error("Second argument must be an integer");
>       fi;
>       if not IsInt(b) then
>               Error("Third argument must be an integer");
>       fi;
>       if (b-a) in S then
>               return true;
>       fi;
>       return false;
> end;
function( S, a, b ) ... end

If we consider \(a = 65, b = 95\) and \(a = 18, b = 22\),

gap> AreRelatedNumericalSemigroup(S, 65, 95);
true
gap> AreRelatedNumericalSemigroup(S, 18, 22);
false

References

Assi, Abdallah, Marco D’Anna, and Pedro A. Garcı́a-Sánchez. 2020. Numerical Semigroups and Applications. Vol. 3. RSME Springer Series. Springer, [Cham]. https://doi.org/10.1007/978-3-030-54943-5.
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.