Distance between factorizations
Definition
Let \(S\) be a numerical semigroup minimally generated by \(\{n_1, \ldots, n_p\}\), 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)\), it is defined the distance between \(x\) and \(y\), denoted by \(d(x,y)\), as
\[ d(x,y) = \max \{ | x - (x \land y) |, | y - (x \land y) | \} \]
where \(|x|\) is the length of \(x\) and \(x \land y\) is the greatest common divisor of \(x,y\), that is,
\[ x \land y = (\min \{x_1, y_1\}, \ldots, \min \{x_p, y_p\}). \]
It can be proven that \(d(x,y) = \max \{|x|, |y|\} - |x \land y|\).
Examples
\(\circ\) Let \(S = \langle 7, 9, 14 \rangle\) and \(s = 49\). The set of factorizations is \(\mathbf{Z}(49) = \{(7,0,0), (1,3,1)\}\), and
\[ (7,0,0) \land (1,3,1) = (1,0,0). \]
Therefore, the distance between the factorizations \((7,0,0)\) and \((1,3,1)\) is
\[ d((7,0,0), (1,3,1)) = \max \{ | x - (x \land y) |, | y - (x \land y) | \} = \max \{ 6, 4 \} = 6. \]
Examples with GAP
Nowadays, there are no functions in package NumericalSgps related to distance between factorizations. However, given two lists of integers of the same length \(I_1 = \{x_1, \ldots, x_n\}, I_2 = \{y_1, \ldots, y_n\}\), the following function returns the distance between \(x = (x_1, \ldots, x_n)\) and \(y = (y_1, \ldots, y_n)\).
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 34, 38, 41, 77, 103 \rangle\), in GAP:
gap> S := NumericalSemigroup(34, 38, 41, 77, 103);
<Numerical semigroup with 5 generators>Given a numerical semigroup \(S\) and an integer \(n \in S\), the function Factorizations returns the factorizations of \(n\) in \(S\).
gap> 315 in S;
true
gap> Factorizations(315,S);
[ [ 1, 2, 5, 0, 0 ], [ 7, 0, 0, 1, 0 ], [ 0, 1, 3, 2, 0 ],
[ 4, 2, 0, 0, 1 ], [ 2, 0, 1, 0, 2 ] ]Let us consider \(x = (1,2,5,0,0)\) and \(y = (0,1,3,2,0)\), if we use the function defined above, the distance between \(x\) an \(y\) is
gap> DistanceFactorizations([1,2,5,0,0],[0,1,3,2,0]);
4References
https://gap-packages.github.io/ numericalsgps.