N-Chain of factorizations

Definition

Let \(S\) be a numerical semigroup, let \(s \in S\) and let \(\mathbf{Z}(s)\) be the set of factorizations of \(s\) in \(S\). Given \(x,y \in \mathbf{Z}(s)\) and a non-negative integer \(N\), it is said that \(x_1, x_2, \ldots, x_k \in \mathbb{Z}(s)\) is an \(N-\)chain joining \(x\) and \(y\) if

  • \(x_1 = x\), \(x_k = y\),

  • for all \(i \in \{1, 2, \ldots, k-1\}\), \(d(x_i, x_{i+1}) \le N\), where \(d(x_i, x_{i+1})\) denotes the distance between \(x_i\) and \(x_{i+1}\).

Examples

\(\circ\) Let \(S = \langle 5, 12, 16 \rangle\) and \(s = 70\). The set of factorizations is

\[ \mathbf{Z}(70) = \{(14, 0, 0), (2, 5, 0), (6, 2, 1), (2, 1, 3)\}. \]

If we compute the distance between each pair, it is obtained the following graph.

NSGraph 1 (14, 0, 0) 2 (2, 5, 0) 1--2 12 3 (6, 2, 1) 1--3 8 4 (2, 1, 3) 1--4 12 2--3 5 2--4 4 3--4 5

Let us consider \(x = (2,1,3)\) and \(y = (14,0,0)\). We have an \(8-\)chain, since the sequence \(x_1 = x, x_2 = (6,2,1), x_3 = y\) is such that \(d(x_1, x_2) = 5\) and \(d(x_2, x_3) = 8\). In fact, \(N = 8\) is the least \(N\) so that for any two factorizations of \(s = 70\) there is an \(8-\)chain. It is said that \(N = 8\) is the catenary degree of \(s = 70\) in \(S\).

Examples with GAP

Nowadays, there are no functions in package NumericalSgps related to \(N-\)chain of factorizations. However, given a numerical semigroup, a positive integer \(N\), and a list of factorizations \(I = \{x_1, \ldots, x_n\}\), the following function returns true if \(I\) is an \(N-\)chain of factorizations joining \(x_1\) and \(x_n\).

gap> IsNChainOfFactorizations := function(S,N,I)
>       local n, value, i;
>       if not IsNumericalSemigroup(S) then
>               Error("First argument must be a Numerical Semigroup");
>       fi;
>       if not IsInt(N) then
>               Error("Second argument must be a non-negative integer");
>       fi;
>       if N < 0 then
>               Error("Second argument must be a non-negative integer");
>       fi;
>       if not IsList(I) or I = [] then
>               Error("Third argument must be a non-empty list of factorizations of an element");
>       fi;
>       n := Length(I);
>       value := ImageHomomorfismOfNumericalSemigroup(S, I[1]);
>       for i in [1..n-1] do
>         if not ImageHomomorfismOfNumericalSemigroup(S, I[i+1]) = value then
>               Error("Third argument is not a list of factorizations of an element");
>         fi;
>         if DistanceFactorizations(I[i], I[i+1]) > N then
>             return false;
>         fi;
>       od;
>       return true;
> end;
function( S, N, I ) ... end

The functions ImageHomomorfismOfNumericalSemigroup and DistanceFactorizations are not implemented in package NumericalSgps, their code are as follows.

gap> ImageHomomorfismOfNumericalSemigroup := function(S, I)
>       local Min_gen, p, j, sum, a;
>       if not IsNumericalSemigroup(S) then
>               Error("First argument must be a Numerical Semigroup");
>       fi;
>       if not IsList(I) then
>               Error("Second argument must be a non-empty list of positive integers");
>       fi;
>       Min_gen := MinimalGenerators(S);
>       p := Length(Min_gen);
>       if not p = Length(I) then
>               Error("Length of minimal system of generators and length of second argument are different");
>       fi;
>       sum := 0;
>       j := 1;
>       for a in I do
>               if not IsInt(a) then
>                     Error("Second argument must be a list of positive integers");
>               fi;
>               if a < 0 then
>                     Error("Second argument must be a list of positive integers");
>               fi;
>               sum := sum + a * Min_gen[j];
>               j := j + 1;
>       od;
>       return sum;
> end;
function( S, Is ) ... end
gap> DistanceFactorizations := function(x,y)
>       local n, sum_1, sum_2, i, x_i, y_i, t_i;
>       if not IsList(x) or x = [] then
>               Error("First argument must be a non-empty list of integers");
>       fi;
>       if not IsList(y) or y = [] then
>               Error("Second argument must be a non-empty list of integers");
>       fi;
>       n := Length(x);
>       if not Length(y) = n then
>               Error("Arguments must be of the same length");
>       fi;
>       sum_1 := 0;
>       sum_2 := 0;
>       for i in [1..n] do
>           x_i := x[i];
>           y_i := y[i];
>           if not IsInt(x_i) then
>               Error("First argument must be a non-empty list of integers");
>           fi;
>           if not IsInt(y_i) then
>               Error("Second argument must be a non-empty list of integers");
>           fi;
>           t_i := Minimum(x[i], y[i]);
>           sum_1 := sum_1 + x[i] - t_i;
>           sum_2 := sum_2 + y[i] - t_i;
>       od;
>       return Maximum(sum_1, sum_2);
> end;
function( x, y ) ... end

\(\diamond\) Let \(S = \langle 20, 21, 46, 53 \rangle\), in GAP:

gap> S := NumericalSemigroup(20, 21, 46, 53);
<Numerical semigroup with 4 generators>

Let us consider a list of factorizations of \(s = 200 \in S\).

gap> 200 in S;
true
gap> Factorizations(200,S);
[ [ 10, 0, 0, 0 ], [ 1, 2, 3, 0 ], [ 0, 7, 0, 1 ], [ 4, 1, 1, 1 ],
  [ 1, 1, 0, 3 ] ]
gap> L := [[1,2,3,0], [0,7,0,1], [4,1,1,1], [1,1,0,3]];
[ [ 1, 2, 3, 0 ], [ 0, 7, 0, 1 ], [ 4, 1, 1, 1 ], [ 1, 1, 0, 3 ] ]

It is defined the catenary degree of \(s\) as the least \(N\) such that for any two factorizations \(x, y \in \mathbf{Z}(s)\), there is an \(N\)-chain joining them.

gap> c := CatenaryDegree(200, S);
6
gap> List([1..c], x -> IsNChainOfFactorizations(S,x,L));              
[ false, false, false, false, false, true ]

In this case, the chain of factorizations that we defined joining \(x = (1,2,3,0)\) and \(y = (1,1,0,3)\) is a \(6-\)chain.

\(\diamond\) Given a numerical semigroup and a list of factorizations \(I = \{x_1, \ldots, x_n\}\), the following function returns the value \(N\) such that \(I\) is an \(N-\)chain of factorizations joining \(x_1\) and \(x_n\).

gap> NChainOfFactorizations := function(S,I)
>       local n, value, N, i, dist_i;
>       if not IsNumericalSemigroup(S) then
>               Error("First argument must be a Numerical Semigroup");
>       fi;
>       if not IsList(I) or I = [] then
>               Error("Second argument must be a non-empty list of factorizations of an element");
>       fi;
>       n := Length(I);
>       value := ImageHomomorfismOfNumericalSemigroup(S, I[1]);
>       N := -1;
>       for i in [1..n-1] do
>         if not ImageHomomorfismOfNumericalSemigroup(S, I[i+1]) = value then
>               Error("Second argument is not a list of factorizations of an element");
>         fi;
>         dist_i := DistanceFactorizations(I[i], I[i+1]);
>         if  dist_i > N then
>             N := dist_i;
>         fi;
>       od;
>       return N;
> end;
function( S, I ) ... end

For example, considering \(S = \langle 37, 42, 43, 50, 66 \rangle\), \(s = 240\) and \(I = \{(3, 0, 3, 0, 0), (4, 1, 0, 1, 0), (2, 0, 0, 2, 1), (0, 1, 0, 0, 3) \}\),

gap> 240 in S;
true
gap> I := [ [3,0,3,0,0], [4,1,0,1,0], [2,0,0,2,1], [0,1,0,0,3] ];
[ [ 3, 0, 3, 0, 0 ], [ 4, 1, 0, 1, 0 ], [ 2, 0, 0, 2, 1 ], [ 0, 1, 0, 0, 3 ] ]
gap> NChainOfFactorizations(S,I);
4
gap> IsNChainOfFactorizations(S,3,I);
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.