Gluing of a set of positive integers
Definition
Let \(A = \{m_1, \ldots, m_r\}\) be a subset of positive integers and let \(A_1, A_2\) be a partition of \(A\). For each \(B = \{ m_{i_1}, \ldots, m_{i_k} \} \in \{A, A_1, A_2\}\), let us consider \(X_B = \{x_i ~ | ~ m_i \in B\}\), the free monoid of \(B\),
\[ Free(X_B) = \{a_1x_{i_1} + \cdots + a_kx_{i_k} ~ | ~ a_1, \ldots, a_k \in \mathbb{N}\}, \]
the monoid homomorfism,
\[ \phi_B: Free(X_B) \to \mathbb{N}, ~~ a_1x_{i_1} + \cdots + x_{i_k}a_k \to a_1 m_{i_1} + \cdots + a_k m_{i_k}. \]
and the kernel congruence of \(\phi_B\). Then, it is said that \(A\) is a gluing of \(A_1\) and \(A_2\) if there exists a system of generators \(\rho\) of \(\sigma\) such that \(\rho = \rho_1 \cup \rho_2 \cup \{(a,b)\}\) with \(\rho_1 \subseteq \sigma_{A_1}, \rho_2 \subseteq \sigma_{A_2}\), \(0 \ne a \in Free(X_{A_1})\) and \(0 \ne b \in Free(X_{A_2})\).
It can be proven that \(A\) is a gluing of \(A_1\) and \(A_2\) if, and only if, for \(d_1 = gcd(A_1)\) and \(d_2 = gcd(A_2)\), then \(lcm(d_1, d_2) = \langle A_1 \rangle \cap \langle A_2 \rangle\), where \(gcd(\cdot)\) denotes the great common divisor and \(lcm(\cdot)\) denotes the least common multiple.
The gluing of a set of positive integers is closely related to the concept of gluing of numerical semigroups.
Examples
\(\circ\) Let \(A = \{15, 25, 24, 36\}\) and let us consider the partition \(A_1 = \{15, 25\}\), \(A_2 = \{24, 36\}\). We have \(gcd(A_1) = 5, gcd(A_2) = 12\) and \(lcm(5, 12) = 60 \in \langle 15, 25 \rangle \cap \langle 24, 36 \rangle\). Therefore, \(A\) is a gluing of \(A_1, A_2\). A system of generators of \(\sigma_1\) is \(\{(3x_2,5x_1)\}\) and for \(\sigma_2\) is \(\{(2x_4, 3x_3)\}\). Moreover, there is the relation \((4x_1, x_3 + x_4) \in \sigma_{A}\), where \(a = 4x_1 \in Free(X_{A_1}) \setminus \{0\}\) and \(b = x_3 + x_4 \in Free(X_{A_2}) \setminus \{0\}\). A system of generators of \(\sigma_A\) is
\[ \rho = \{(3x_2, 5x_1), (2x_4, 3x_3), (4x_1, x_3 + x_4)\}. \]
Examples with GAP
Nowadays, there are no functions in package NumericalSgps related to gluing of a set of positive integers. However, given three list of integers \(A, A_1, A_2\), the following function returns true if \(A\) is a gluing of \(A_1\) and \(A_2\) and false otherwise.
gap> IsGluing := function(A, A_1, A_2)
> local d_1, d_2, d, S, T;
> if not IsListOfIntegersNS(A) then
> Error("First argument must be a non-empty list of positive integers");
> fi;
> if not IsListOfIntegersNS(A_1) then
> Error("Second argument must be a non-empty list of positive integers");
> fi;
> if not IsListOfIntegersNS(A_2) then
> Error("Third argument must be a non-empty list of positive integers");
> fi;
> if not (IsSubset(A, A_1) and IsSubset(A, A_2)) then
> return false;
> fi;
> if not Difference(A, Union(A_1, A_2)) = [] then
> return false;
> fi;
> if not Intersection(A_1, A_2) = [] then
> return false;
> fi;
> d_1 := Gcd(A_1);
> d_2 := Gcd(A_2);
> d := Lcm(Gcd(A_1), Gcd(A_2));
> S := NumericalSemigroup(A_1 / d_1);
> T := NumericalSemigroup(A_2 / d_2);
> if d/d_1 in S and d/d_2 in T then
> return true;
> fi;
> return false;
> end;
function( A, A_1, A_2 ) ... endMoreover, given a list of positive integers \(A\), the following function returns a list \(I = [ [A_1, B_1], \ldots, [A_n, B_n] ]\) such that \(A\) is a gluing of \(A_i, B_i\) for all \(i \in \{1, \ldots, n\}\), that is, all the possible gluings of \(A\).
gap> AllGluings := function(A)
> local a, l_gluings, P;
> if not IsListOfIntegersNS(A) then
> Error("The argument must be a non-empty list of positive integers");
> fi;
> l_gluings := [];
> for P in PartitionsSet(Set(A), 2) do
> if IsGluing(A, P[1], P[2]) then
> Add(l_gluings, P);
> fi;
> od;
> return l_gluings;
> end;
function( A ) ... end\(\diamond\) Let \(A = \{3,7,19,22,47,51\}\) and the partition \(A_1 = \{3, 7, 19, 22, 47\}, A_2 = \{51\}\). If we use the function defined above,
gap> A := [3,7,19,22,47,51];
[ 3, 7, 19, 22, 47, 51 ]
gap> A_1 := [3,7,19,22,47];
[ 3, 7, 19, 22, 47 ]
gap> A_2 := [51];
[ 51 ]
gap> IsGluing(A, A_1, A_2);
trueThen, \(A\) is a gluing of \(A_1\) and \(A_2\). On the other hand, all the gluings of \(A\) are as follows.
gap> AllGluings(A);
[ [ [ 3, 7, 19, 22, 47 ], [ 51 ] ],
[ [ 3, 7, 19, 22, 51 ], [ 47 ] ],
[ [ 3, 7, 19, 47, 51 ], [ 22 ] ],
[ [ 3, 7, 22, 47, 51 ], [ 19 ] ] ]References
https://gap-packages.github.io/ numericalsgps.