Congruences
Definition
Let us consider \(p \in \mathbb{N}\) arbitrary but fixed. Given \(\rho \in \mathbb{N}^p \times \mathbb{N}^p\), the congruence generated by \(\rho\) is the smallest congruence on \(\mathbb{N}^p\) containing \(\rho\), and it is denoted by \(Cong(\rho)\).
Let \(\tau\) be a congruence on \(\mathbb{N}^p\). If there exists a system of generators \(\rho\) of \(\tau\) with finitely many elements, it is said that \(\tau\) is finitely generated, and if \(\rho\) has the least cardinality possible among the cardinals of system of generators of \(\tau\), it is said that \(\rho\) is a minimal relation.
Finally, it is said that an element \((a,b) \in \tau \setminus \{(0,0)\}\) is irreducible if it cannot be expressed as \((a,b) = (a_1, b_1) + (a_2, b_2)\) for some \((a_1, b_1), (a_2, b_2) \in \tau \setminus \{(0,0)\}\).
Examples
\(\circ\) Let \(S\) be a numerical semigroup and \(\phi\) its factorization homomorfism. Then, \(\ker(\phi)\) is a congruence, where
\[ \ker(\phi) = \{(a,b) \in \mathbb{N}^p ~ | ~ \phi(a) = \phi(b)\}. \]
It can be proven that \(\ker(\phi)\) is always finitely generated. A minimal relation \(\rho\) of \(\ker(\phi)\) is called a minimal presentation of \(S\). A minimal presentation of a numerical semigroup provides us the essential relations between minimal generators.
Examples with GAP
The following example is made with the package NumericalSgps in GAP.
\(\diamond\) Let \(S = \langle 13, 42, 79, 106, 115 \rangle\), in GAP:
gap> S := NumericalSemigroup(13, 42, 79, 106, 115);
<Numerical semigroup with 5 generators>The functions MinimalPresentation and MinimalPresentationOfNumericalSemigroup compute a minimal presentation of a given numerical semigroup.
gap> MinimalPresentation(S);
[ [ [ 0, 0, 0, 0, 2 ], [ 8, 3, 0, 0, 0 ] ], [ [ 0, 0, 0, 1, 1 ], [ 17, 0, 0, 0, 0 ] ],
[ [ 0, 0, 0, 2, 0 ], [ 1, 2, 0, 0, 1 ] ], [ [ 0, 0, 1, 0, 1 ], [ 2, 4, 0, 0, 0 ] ],
[ [ 0, 0, 1, 1, 0 ], [ 11, 1, 0, 0, 0 ] ], [ [ 0, 0, 2, 0, 0 ], [ 4, 0, 0, 1, 0 ] ],
[ [ 0, 1, 0, 0, 1 ], [ 6, 0, 1, 0, 0 ] ], [ [ 0, 3, 0, 1, 0 ], [ 9, 0, 0, 0, 1 ] ],
[ [ 0, 4, 1, 0, 0 ], [ 2, 0, 0, 1, 1 ] ], [ [ 0, 5, 0, 0, 0 ], [ 4, 0, 2, 0, 0 ] ] ]
gap> MinimalPresentation(S) = MinimalPresentationOfNumericalSemigroup(S);
trueIf we want all the minimal relators in a numerical semigroup, the function AllMinimalRelationsOfNumericalSemigroup computes it.
gap> AllMinimalRelationsOfNumericalSemigroup(S);
[ [ [ 1, 2, 0, 0, 1 ], [ 0, 0, 0, 2, 0 ] ], [ [ 2, 0, 0, 1, 1 ], [ 0, 4, 1, 0, 0 ] ],
[ [ 2, 4, 0, 0, 0 ], [ 0, 0, 1, 0, 1 ] ], [ [ 4, 0, 0, 1, 0 ], [ 0, 0, 2, 0, 0 ] ],
[ [ 4, 0, 2, 0, 0 ], [ 0, 5, 0, 0, 0 ] ], [ [ 6, 0, 1, 0, 0 ], [ 0, 1, 0, 0, 1 ] ],
[ [ 7, 1, 1, 0, 0 ], [ 0, 0, 0, 2, 0 ] ], [ [ 8, 0, 0, 1, 0 ], [ 0, 5, 0, 0, 0 ] ],
[ [ 8, 3, 0, 0, 0 ], [ 0, 0, 0, 0, 2 ] ], [ [ 9, 0, 0, 0, 1 ], [ 0, 3, 0, 1, 0 ] ],
[ [ 11, 1, 0, 0, 0 ], [ 0, 0, 1, 1, 0 ] ], [ [ 17, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 1 ] ]
, [ [ 19, 0, 0, 0, 0 ], [ 0, 4, 1, 0, 0 ] ] ]On the other hand, the function IsMinimalRelationOfNumericalSemigroup returns true or false depending on whether a pair (a relation) is a minimal relator or not.
gap> IsMinimalRelationOfNumericalSemigroup([ [1, 2, 0, 0, 1], [0, 0, 0, 2, 0] ], S);
true
gap> IsMinimalRelationOfNumericalSemigroup([ [11, 0, 1, 0, 0], [5, 1, 0, 0, 1] ], S);
falseReferences
https://gap-packages.github.io/ numericalsgps.