Set of factorizations
Definition
Let \(S\) be a numerical semigroup with minimal set of generators \(\{n_1, n_2, \ldots, n_p\}\) and factorization homomorphism \(\phi\). Given \(s \in S\), it is defined the set of factorizations (or the set of expressions) of \(s\) in \(S\) as
\[ \mathbf{Z}(s) = \phi^{-1}(s) = \{a \in \mathbb{N}^p ~ | ~ \phi(a) = s\}. \]
It is said that \(s \in S\) has unique expression if the set \(\mathbf{Z}(s)\) has only one element. It can be proven that for any \(s \in S\), the set of factorizations \(\mathbf{Z}(s)\) is finite. The cardinality of \(|\mathbf{Z}(s)|\) is called the denumerant of \(s\) in \(S\).
Examples
\(\circ\) Let \(S = \langle 7, 9, 12 \rangle\) and \(s = 33\). To compute \(\mathbf{Z}(s)\), we need all the elements \((\alpha, \beta, \gamma) \in \mathbb{N}^3\) such that
\[ 7 \alpha + 9 \beta + 12 \gamma = 33. \]
Each coefficient has an upper bound, which is\(\alpha \le \lfloor \frac{33}{7} \rfloor = 4, \beta \le \lfloor \frac{33}{9} \rfloor = 3, \gamma \le \lfloor \frac{33}{12} \rfloor = 2\). Then, \(\phi(\alpha, \beta, \gamma) = s\) implies \(0 \le \alpha \le 4, 0 \le \beta \le 3\) and \(0 \le \gamma \le 2\). From this bounds it is deduced that \(\mathbf{Z}(33) = \{(3,0,1), (0,1,2)\}\).
Examples with GAP
The following examples are made with the package NumericalSgps in GAP.
\(\diamond\) Let \(S = \langle 37, 42, 44, 51 \rangle\), in GAP:
gap> S := NumericalSemigroup(37, 42, 44, 51);
<Numerical semigroup with 4 generators>Given a numerical semigroup \(S\) and an element \(n \in S\), the functions Factorizations and FactorizationsElementWRTNumericalSemigroup return the set of factorizations of \(n\) in terms of the minimal generating set of \(S\).
gap> Factorizations(S, 500);
[ [ 10, 1, 2, 0 ], [ 2, 7, 3, 0 ], [ 4, 0, 8, 0 ], [ 11, 1, 0, 1 ], [ 3, 7, 1, 1 ], [ 5, 0, 6, 1 ], [ 6, 0, 4, 2 ],
[ 7, 0, 2, 3 ], [ 8, 0, 0, 4 ], [ 0, 6, 1, 4 ] ]
gap> Factorizations(500, S);
[ [ 10, 1, 2, 0 ], [ 2, 7, 3, 0 ], [ 4, 0, 8, 0 ], [ 11, 1, 0, 1 ], [ 3, 7, 1, 1 ], [ 5, 0, 6, 1 ], [ 6, 0, 4, 2 ],
[ 7, 0, 2, 3 ], [ 8, 0, 0, 4 ], [ 0, 6, 1, 4 ] ]
gap> Factorizations(S, 500) = FactorizationsElementWRTNumericalSemigroup(500, S);
true\(\diamond\) Given a list of integers \(Is\) and an integer \(n\), the function FactorizationsIntegerWRTList computes the set of factorizations of \(n\) in terms of the elements in the list \(Is\).
gap> I := [5, 10, 12];
[ 5, 10, 12 ]
gap> FactorizationsIntegerWRTList(40, I);
[ [ 8, 0, 0 ], [ 6, 1, 0 ], [ 4, 2, 0 ], [ 2, 3, 0 ], [ 0, 4, 0 ] ]Given a numerical semigroup \(S\) and a list of elements \(Is\) in \(S\), the function FactorizationsElementListWRTNumericalSemigroup computes the set of factorizations of each element in terms of its minimal generating set.
gap> FactorizationsElementListWRTNumericalSemigroup([320, 321, 322], S);
[ [ [ 0, 1, 4, 2 ], [ 1, 1, 2, 3 ], [ 2, 1, 0, 4 ], [ 4, 2, 2, 0 ],
[ 5, 2, 0, 1 ] ], [ [ 0, 4, 0, 3 ], [ 3, 5, 0, 0 ] ],
[ [ 0, 0, 5, 2 ], [ 1, 0, 3, 3 ], [ 2, 0, 1, 4 ], [ 4, 1, 3, 0 ],
[ 5, 1, 1, 1 ] ] ]\(\diamond\) Let \(S = \langle 14, 17, 20, 32 \rangle\), in GAP:
gap> S := NumericalSemigroup(14, 17, 20, 32);
<Numerical semigroup with 4 generators>Given a numerical semigroup \(S\) and a positive integer \(n\), the function DenumerantOfElementInNumericalSemigroup returns the number of factorizations of \(n\) in terms of the minimal generating set of \(S\), that is, \(|\mathbf{Z}(n)|\) in \(S\).
gap> DenumerantOfElementInNumericalSemigroup(100, S);
4
gap> DenumerantOfElementInNumericalSemigroup(21, S);
0Moreover, given a numerical semigroup \(S\), the function DenumerantFunction returns a function such that for a given \(n\) computes the number of factorizations of \(n\) in terms of the minimal generating set of \(S\).
gap> f := DenumerantFunction(S);
function( n ) ... end
gap> f(101);
2
gap> DenumerantOfElementInNumericalSemigroup(101, S);
2References
https://gap-packages.github.io/ numericalsgps.