arXiv:1605.03907v1 [math.CO] 12 May 2016

A combinatorial problem and numerical
semigroups
Aureliano M. Robles-Pérez∗† and José Carlos Rosales∗‡

Abstract
Let a = (a1 , . . . , an ) and b = (b1 , . . . , bn ) be two n-tuples of positive
integers, let X be a set of positive integers, and let g be a positive integer.
In this work we show an algorithmic process in order to compute all the
sets C of positive integers that fulfill the following conditions:
1. the cardinality of C is equal to g;
2. if x, y ∈ N \ {0} and x + y ∈ C, then C ∩ {x, y} 6= ∅;
3. if x ∈ C and

x−bi
ai

∈ N \ {0} for some i ∈ {1, . . . , n}, then

x−bi
ai

∈ C;

4. X ∩ C = ∅.

Keywords: combinatorial problems, numerical semigroups, Frobenius pseudovarieties.
2010 Mathematics Subject Classification: 11B75, 05A99, 20M14.

1

Introduction

In certain lottery game, we have to guess six (positive) numbers to win the
main prize. By analysing the results of different draws, it has been observed
that some patterns happen frequently. In effect, if C is a winner combination,
then is rather probable that one of the following conditions is fulfilled.
(C1) If x, y are positive integers such that x + y ∈ C, then C ∩ {x, y} =
6 ∅.
(C2) If x ∈ C and x − 4 is a positive integer, then x − 4 ∈ C.
(C3) If x ∈ C and

x−1
2

is a positive integer, then

x−1
2

∈ C.

(C4) 5 6∈ C.
∗ Both

of the authors are supported by FQM-343 (Junta de Andalucı́a), MTM2014-55367P (MINECO, Spain), and FEDER funds. The second author is also partially supported by
Junta de Andalucı́a/FEDER Grant Number FQM-5849.
† Departamento de Matemática Aplicada, Universidad de Granada, 18071-Granada, Spain.
E-mail: arobles@ugr.es
‡ Departamento de Álgebra, Universidad de Granada, 18071-Granada, Spain.
E-mail: jrosales@ugr.es

1

The question naturally arises as to whether a combination fulfilling the four
conditions simultaneously exists. The purpose of this work will be to give an
answer to this type of combinatorial problems.
Let Z and N be the sets of integers and non-negative integers, respectively.
Let a = (a1 , . . . , an ) and b = (b1 , . . . , bn ) be two n-tuples (with n ≥ 1) of positive
integers, let X be a non-empty subset of N \ {0}, and let g be a positive integer.
Let us denote by P(a, b, X, g) the problem of computing all the subsets C of
N \ {0} that fulfill the following conditions.
(P 1) The cardinality of C is equal to g.
(P 2) If x, y ∈ N \ {0} and x + y ∈ C, then C ∩ {x, y} 6= ∅.
(P 3) If x ∈ C and

x−bi
ai

∈ N \ {0} for some i ∈ {1, . . . , n}, then

x−bi
ai

∈ C.

(P 4) X ∩ C = ∅.
With the previous notation, we observe that the problem proposed at the
beginning is just P((1, 2), (4, 1), {5}, 6).
A numerical semigroup (see [5]) is a submonoid S of (N, +) such that N \ S
is finite. The cardinality of N \ S is so-called the genus of S and is denoted by
g(S).
It is easy to see that C is a solution of P(a, b, X, g) if and only if S = N \ C
is a numerical semigroup that fulfills the following conditions.
(S1) g(S) = g.
(S2) If s ∈ S \ {0}, then as + b ∈ S n (where as + b = (a1 s + b1, . . . , an s + bn)).
(S3) X ⊆ S.
Let us denote by N (a, b, X) the set
{S | S is a numerical semigroup, X ⊆ S, and as + b ∈ S n for all s ∈ S \ {0}} .
With this notation, the solutions of P(a, b, X, g) are the elements of the set
{N \ S | S ∈ N (a, b, X) and g(S) = g}.
Let S be a numerical semigroup. The Frobenius number of S (see [1]),
denoted by F(S), is the maximum integer that does not belong to S.
A Frobenius variety (see [4]) is a non-empty family of numerical semigroups
V that fulfills the following conditions.
(V 1) If S, T ∈ V, then S ∩ T ∈ V.
(V 2) If S ∈ V and S 6= N, then S ∪ {F(S)} ∈ V.
In Section 2 we will see that N (a, b, X) is a Frobenius variety. In addition,
we will show that such a variety is finite if and only if gcd(X ∪ {b1 , . . . , bn }) = 1
(where, as usual, gcd(A) is the greatest common divisor of the elements in A).
Let us denote by M (a, b, X) the intersection of all the elements in N (a, b, X).
Observe that M (a, b, X) is always a submonoid of (N, +). In addition, we will
2

prove that M (a, b, X) is a numerical semigroup if and only if N (a, b, X) has
finitely many elements.
In Section 2 we will show that P(a, b, X, g) has solution if and only if the
cardinality of N \ M (a, b, X) is greatest than or equal to g. Moreover, we will
give an algorithm in order to compute M (a, b, X). Therefore, we will have an
algorithmic process to decide whether P(a, b, X, g) has solution.
In Section 3, with the help of some results from [4], we will arrange the
elements of N (a, b, X) in a tree with root N. Moreover, we will characterize
the children of a vertex in such a tree and, consequently, will have a recursive
procedure in order to build N (a, b, X). Accordingly, we will have an algorithmic
process to compute all the elements of N (a, b, X) with a fixed genus and, in
particular, an algorithm to compute all the solutions of P(a, b, X, g).
Finally, in Section 4 we will state and solve a generalization of the problem
P(a, b, X, g).

2

(a, b)-monoids

In this work, unless stated otherwise, a = (a1 , . . . , an ) and b = (b1 , . . . , bn )
denote two n-tuples of positive integers. If X ⊆ N, then N (a, b, X) is the set
{S | S is a numerical semigroup, X ⊆ S, and as + b ∈ S n for all s ∈ S \ {0}} ,
with as + b = (a1 s + b1 , . . . , an s + bn ).
Proposition 2.1. N (a, b, X) is a Frobenius variety.
Proof. It is clear that N ∈ N (a, b, X) and, therefore, N (a, b, X) 6= ∅. It is also
clear that, if S, T ∈ N (a, b, X), then S∩T ∈ N (a, b, X). Now, let S ∈ N (a, b, X)
such that S 6= N. In order to show that S ∪ {F(S)} ∈ N (a, b, X), it is enough
to see that aF(S) + b ∈ (S ∪ {F(S)})n . Observe that, if i ∈ {1, . . . , n}, then
ai F(S) + bi > F(S) and, therefore, ai F(S) + bi ∈ S ∪ {F(S)}. Consequently,
aF(S) + b ∈ (S ∪ {F(S)})n .
Let M be a submonoid of (N, +). We will say that M is an (a, b)-monoid if
am + b ∈ M n for all m ∈ M \ {0}.
Proposition 2.2. Let M be a submonoid of (N, +) and let X ⊆ N. Then M is
an (a, b)-monoid if and only if M is the intersection of elements in N (a, b, X).
Proof. The sufficient condition is trivial. For the necessary one, let us take
Mk = M ∪ {k, →}, for all k ∈ N (where {k,T→} = {n ∈ N | n ≥ k}). Then it is
clear that Mk ∈ N (a, b, X) and that M = k∈N Mk .
T
Let us observe that, if we denote by M (a, b, X) = S∈N (a,b,X) S, then
M (a, b, X) is the smallest (a, b)-monoid containing X.
Theorem 2.3. Let X be a non-empty subset of N \ {0} and let g be a positive
integer. Then the problem P(a, b, X, g) has solution if and only if the cardinality
of N \ M (a, b, X) is greatest than or equal to g.

3

Proof. (Necessity.) If C is a solution of P(a, b, X, g) and we take S = N \ C,
then S ∈ N (a, b, X) and g(S) = g. Since M (a, b, X) ⊆ S, we have that N \ S ⊆
N \ M (a, b, X) and, thereby, the cardinality of N \ M (a, b, X) is greatest than
or equal to g.
(Sufficiency.) Let us suppose that N \ M (a, b, X) = {c1 < · · · < cg < · · · }.
If we take S = M (a, b, X) ∪ {cg + 1, →}, then it is clear that S ∈ N (a, b, X) and
g(S) = g. Therefore, C = N \ S is a solution of P(a, b, X, g).
Let us observe that, if P(a, b, X, g) has solution and, in addition, we know
M (a, b, X), then the proof of the sufficient condition in the previous theorem
gives us a method to compute a solution of P(a, b, X, g).
If X is a non-empty subset of N, then we denote by hXi the submomoid of
(N, +) generated by X, that is,
hXi = {λ1 x1 + · · · + λk xk | k ∈ N \ {0}, x1 , . . . , xk ∈ X, and λ1 , . . . , λk ∈ N}.
If M = hXi, then we will say that M is generated by X or, equivalently, that X
is a system of generators of M . The next result is well known (see, for instance,
[5]).
Lemma 2.4. If X ⊆ N, then hXi is a numerical semigroup if and only if
gcd(X) = 1.
We know that M (a, b, X) is a submonoid of (N, +). From the following
proposition we will get that, if X ⊆ N \ {0}, then M (a, b, X) is a numerical
semigroup if and only if gcd(X ∪ {b1 , . . . , bn }) = 1.
Proposition 2.5. If X ⊆ N\{0}, then gcd(M (a, b, X)) = gcd(X ∪{b1 , . . . , bn }).
Proof. Let d = gcd(M (a, b, X)) and d′ = gcd(X ∪ {b1 , . . . , bn }). In order to
prove the proposition, we will show that d′ | d and d | d′ . (As usual, if p, q are
positive integers, then p | q means that p divides q.)
First of all, it is clear that h{d′ }i is an (a, b)-monoid containing X. Therefore,
M (a, b, X) ⊆ h{d′ }i and, consequently, d′ | d.
Now, let us take x ∈ X. Then {x, a1 x + b1 , . . . , an x + bn } ⊆ M (a, b, X) and
gcd{x,
a1 x+ b1 , . . . , an x+ bn } = gcd{x, b1 , . . . , bn }. Therefore,
we have that X ∪
S
S
( ni=1 {ai x + bi | x ∈ X}) ⊆ M (a, b, X) and gcd (X ∪ ( ni=1 {ai x + bi | x ∈ X}))
= gcd(X ∪ {b1 , . . . , bn }) = d′ . Accordingly, d | d′ .
In the next result we show when the Frobenius variety N (a, b, X) is finite.
Theorem 2.6. Let X be a subset of N \ {0}. Then the following conditions are
equivalent.
1. N (a, b, X) is finite.
2. M (a, b, X) is a numerical semigroup.
3. gcd(X ∪ {b1 , . . . , bn }) = 1.

4

Proof. The equivalence between conditions 2 and 3 is consequence of Lemma 2.4
and Proposition 2.5. Now, let us see the equivalence between conditions 1 and
2.
(1. ⇒ 2.) It is enough to observe that the finite intersection of numerical
semigroups is another numerical semigroup.
(2. ⇒ 1.) If S ∈ N (a, b, X), then M (a, b, X) ⊆ S. Thus, S = M (a, b, X) ∪ Y
with Y ⊆ N \ M (a, b, X). Since N \ M (a, b, X) is finite, we conclude that
N (a, b, X) is finite.
Our next aim in this section will be to give an algorithm in order to compute
M (a, b, X). For this is fundamental the following result.
Proposition 2.7. Let M be a submonoid of (N, +) generated by X ⊆ N \ {0}.
Then M is an (a, b)-monoid if and only if ax + b ∈ M n for all x ∈ X.
Proof. The necessary condition is trivial. For the sufficiency, let m ∈ M \ {0}.
Then there exist x1 , . . . , xt ∈ X such that m = x1 + · · · + xt . If t = 1, then
m = x1 and am+b = ax1 +b ∈ M n . If t ≥ 2, then am+b = a(x1 +· · ·+xt )+b =
a(x1 + · · · + xt−1 ) + axt + b. Since a(x1 + · · · + xt−1 ), axt + b ∈ M n , we finish
the proof.
The above proposition will be useful in order to determine whether a submonoid M of (N, +) is or is not an (a, b)-monoid. Let us see an example.
Example 2.8. S = h{4, 5, 11}i is an ((1, 2), (4, 1))-monoid because (1, 2)4 +
(4, 1) = (8, 9) ∈ S 2 , (1, 2)5 + (4, 1) = (9, 11) ∈ S 2 , and (1, 2)11 + (4, 1) =
(15, 23) ∈ S 2 . Nevertheless, T = h{5, 7, 9}i is not an ((1, 2), (4, 1))-monoid
because (1, 2)5 + (4, 1) = (9, 11) ∈
/ T 2 (observe that 11 ∈
/ T ).
With the help of Proposition 2.7, it would be possible to give an algorithm
in order to compute M (a, b, X). However, we are going to postpone such an
algorithm because, as we will see now, we can focus on case in which gcd(X ∪
{b1 , . . . , bn }) = 1, and thus simplify the computations.
We say that an integer d divides an n-tupla of integers c = (c1 , . . . , cn ) if
d | ci for all i ∈ {1, . . . , n}. In such a case, we denote by dc = cd1 , . . . , cdn . If
A ⊆ Z and k ∈ Z, then 
kA = {ka | a ∈ A}. Finally, if A ⊆ Z, d ∈ Z, and d | a
a
=
for all a ∈ A, then A
d
d |a∈A .
Lemma 2.9. Let M be an (a, b)-monoid such that M 6= {0}. If gcd(M ) = d,
then
1. d divides b;
2. if d′ ∈ N \ {0} and d′ | d, then

M
d′


is an a, db′ -monoid;

3. if k ∈ N \ {0}, then kM is an (a, kb)-monoid.
Proof. 1. If we take X = M \ {0}, and having in mind that M (a, b, X) is the
smallest (a, b)-monoid containing X, then this item is consequence of Proposition 2.5.
5

M
2. It is clear that M
d′ is a submonoid of (N, +). In addition, if x ∈ d′ \ {0},
then d′ x ∈ M \ {0} and, therefore, ad′ x + b ∈ M n . Consequently, ax + db′ ∈

M n
Mn
.
d′ = d′
3. It is clear that kM is a submonoid of (N, +). Now, arguing as in the
previous item, if x ∈ kM \ {0}, then xk ∈ M \ {0} and, therefore, a kx + b ∈ M n .
Consequently, ax + kb ∈ k · M n = (kM )n .

The next proposition says us that, in order to compute M (a,b, X), it is
the
sufficient to calculate d = gcd (X ∪ {b1 , . . . , bn }) and M a, db , X
d ). By
 b1


bn
b X
way, observe that gcd X
∪
,
.
.
.
,
,
=
1
and,
therefore,
M
a,
is
a
d
d
d
d d
numerical semigroup.
Proposition 2.10. Let X be a subset
of N \ {0}. If gcd (X ∪ {b1 , . . . , bn }) = d,

then M (a, b, X) = d · M a, db , X
.
d

is an (a, b)Proof. From item 3 of Lemma 2.9, we have that d · M a, db , X
d

monoid containing X. Therefore, M (a, b, X) ⊆ d · M a, db , Xd .
On the other hand, from
 Proposition 2.5 andX item 2 of Lemma 2.9, web deduce

M(a,b,X)
b
that
is an a, d -monoid containing d . Consequently, M a, d , X
d
d ⊆

M(a,b,X)
, that is, d · M a, db , X
d
d ⊆ M (a, b, X).
We are now ready to show the announced algorithm.
Algorithm 2.11.
INPUT: A non-empty finite set of positive integers X such that
gcd (X ∪ {b1 , . . . , bn }) = 1.
OUTPUT: M (a, b, X).
(1) A = ∅ and G = X.
(2) If G \ A = ∅, then return hGi and stop the algorithm.
(3) m = min(G \ A).
(4) H = {ai m + bi | i ∈ {1, . . . , n} and ai m + bi ∈
/ hGi}.
(5) If H = ∅, then go to (7).
(6) G = G ∪ H.
(7) A = A ∪ {m} and go to (2).
Let us justify briefly the performance of this algorithm. Let us observe that,
if the algorithm stops, then it returns hGi such that ag + b ∈ hGin for all g ∈ G.
Therefore, by applying Proposition 2.7, we have that hGi is an (a, b)-monoid.
In addition, by construction, it is clear that G must be a subset of every (a, b)monoid which contains X. Thus, hGi is the smallest (a, b)-monoid containing
X. Consequently, in order to justify the algorithm, it will be enough to see that
the algorithm stops. In fact, when we arrive to step (7) at the first time, we
have that gcd(G) = 1 and, thereby, hGi is a numerical semigroup. Therefore,
N \ hGi is finite and we can go to the step (6) only in a finite number of times.
Remark 2.12. If we suppose, for a moment, that X = ∅ (in some sense, we are
removing condition (P 4) in P(a, b, X, g)), then it is obvious that Sk = {0, k, →},
for all k ∈ N (where {0, k, →} = {0} ∪ {n ∈ N | n ≥ k}), are numerical
6

semigroups that belong to N (a, b, X) independently of the chosen n-tuples a, b.
Thus M (a, b, X) = {0}, that is, the submonoid S of (N, +) generated by X = ∅.
We can observed that, if we apply Algorithm 2.11 in this case, we obtain this
output.
Remark 2.13. Now, let us suppose that a, b are 0-tuples, that is, we remove
condition (P 3) in P(a, b, X, g). In this case, it is straightforward to see that
M (a, b, X) is just the monoid generated by X. In addition, that is the output
of Algorithm 2.11 in this case.
After Remarks 2.12 and 2.13, we can conclude that (P 2) is the essential
condition in order to have a structure related with monoids and, specifically,
with numerical semigroups.
Let us illustrate the performance of Algorithm 2.11 with two examples.
Example 2.14. We are going to compute M = M ((1, 2), (4, 1), {5}).
• A = ∅ and G = {5}.
• m = 5, H = {9, 11}, G = {5, 9, 11}, and A = {5}.
• m = 9, H = {13}, G = {5, 9, 11, 13}, and A = {5, 9}.
• m = 11, H = ∅, G = {5, 9, 11, 13}, and A = {5, 9, 11}.
• m = 13, H = {17}, G = {5, 9, 11, 13, 17}, and A = {5, 9, 11, 13}.
• m = 17, H = ∅, G = {5, 9, 11, 13, 17}, and A = {5, 9, 11, 13, 17}.
Therefore, M = h{5, 9, 11, 13, 17}i.
Going back to the problem P((1, 2), (4, 1), {5}, 6) of the introduction, we have
that, since N \ M = {1, 2, 3, 4, 6, 7, 8, 12} has cardinality equal to 8, then Theorem 2.3 asserts that the proposed problem has solution. Moreover, the solutions
will be some subsets, with cardinality equal to 6, of {1, 2, 3, 4, 6, 7, 8, 12}. In addition, by the proof of the sufficiency of Theorem 2.3, we know that {1, 2, 3, 4, 6, 7}
is a solution of such a problem.
We finish this section with an example in which M (a, b, X) is not a numerical
semigroup.
Example 2.15. Let us see that P ((2, 3), (4, 2), {6, 8}, 9) has solution. For that,
we begin with the computation of M ((2, 3), (4, 2), {6, 8}). By applying Proposition 2.10, since gcd({6, 8, 4, 2}) = 2, we know that M ((2, 3), (4, 2), {6, 8}) =
2 · M ((2, 3), (2, 1), {3, 4}). Now, from Algorithm 2.11, M ((2, 3), (2, 1), {3, 4}) =
h{3, 4}i. Therefore, M ((2, 3), (4, 2), {6, 8}) = h{6, 8}i = {0, 6, 8, 12, 14, 16, . . .}.
Since N \ M ((2, 3), (4, 2), {6, 8}) has infinitely many elements, its cardinality
is grater than or equal to 9 and, consequently, Theorem 2.3 assures that the
problem P ((2, 3), (4, 2), {6, 8}, 9) has solution. Moreover, by the proof of the
sufficiency of Theorem 2.3, we have that {1, 2, 3, 4, 5, 7, 9, 10, 11} is a solution.

7

3

The tree associated to N (a, b, X)

A graph G is a pair (V, E), where
• V is a non-empty set, which elements are called vertices of G,
• E is a subset of {(v, w) ∈ V × V | v 6= w}, which elements are called edges
of G.
A path (of length n) connecting the vertices x and y of G is a sequence of
different edges of the form (v0 , v1 ), (v1 , v2 ), . . . , (vn−1 , vn ) such that v0 = x and
vn = y.
We say that a graph G is a tree if there exists a vertex r (known as the
root of G) such that, for every other vertex x of G, there exists a unique path
connecting x and r. If (x, y) is an edge of the tree, then we say that x is a child
of y.
We define the graph G(N (a, b, X)) in the following way.
• N (a, b, X) is the set of vertices of G(N (a, b, X));
• (S, S ′ ) ∈ N (a, b, X) × N (a, b, X) is an edge of G(N (a, b, X)) if S ′ = S ∪
{F(S)}.
By Proposition 2.1 and [4, Theorem 27], we have that G(N (a, b, X)) is a tree
with root N. Our first purpose in this section will be to establish what are the
children of a vertex in such a tree. For this we need to introduce some concepts.
Let S be a numerical semigroup and let G be a system of generators of
S. We say that G is a minimal system of generators of S if S 6= hY i for all
Y ( G. It is well known (see [5]) that every numerical semigroup admits a
unique minimal system of generators and that, in addition, such a system is
finite. Observe that, if we denote by msg(S) the minimal system of generators
of S, then msg(S) = (S \ {0}) \ ((S \ {0}) + (S \ {0})). On the other hand, we
have (see [5]) that, if S is a numerical semigroup and s ∈ S, then S \ {s} is
another numerical semigroup if and only if s ∈ msg(S).
An immediate consequence of [4, Proposition 24, Theorem 27] is the next
result.
Theorem 3.1. The graph G(N (a, b, X)) is a tree with root N. Moreover, the
set of children of a vertex S ∈ N (a, b, X) is
{S \ {m} | m ∈ msg(S), m > F(S), and S \ {m} ∈ N (a, b, X)} .
In the next result we will show the conditions that must satisfy m ∈ msg(S)
in order to have S \ {m} ∈ N (a, b, X).
Proposition 3.2. Let S ∈ N (a, b, X) and let m ∈ msg(S). Then S \ {m} ∈
i
N (a, b, X) if and only if m−b
∈
/ S \ {0} for all i ∈ {1, . . . , n} and m ∈
/ X.
ai

8

Proof. (Necessity.) Since X ⊆ S \ {m}, we have that m ∈
/ X. Let us suppose
i
i
that there exists i ∈ {1, . . . , n} such that m−b
∈
S
\
{0}.
Since m−b
6= m, we
ai
 ai 
m−bi
m−bi
have that ai ∈ S \ {0, m} and that ai
+ bi = m 6∈ S \ {m}. Therefore,
ai
S \ {m} ∈
/ N (a, b, X).
(Sufficiency.) If S \ {m} ∈
/ N (a, b, X), then there exists s ∈ S \ {0, m} and
there exists i ∈ {1, . . . , n} such that ai s + bi ∈
/ S \ {m}. Since S ∈ N (a, b, X),
i
=
we know that ai s + bi ∈ S. Therefore, ai s + bi = m and, consequently, m−b
ai
s ∈ S \ {0}.
Our next purpose will be to build recurrently the tree G(N (a, b, X)) from
the root and joining each vertex with its children by means of edges. In order
to make easy that construction, we will study the relation between the minimal
system of generators of a numerical semigroup S and the minimal system of
generators of S \ {m}, where m is a minimal generator of S greater than F(S).
First of all, it is clear that, if S is minimally generated by {m, m+1, . . . , 2m−1}
(that is, S = {0, m, →}), then S \ {m} = {0, m + 1, →} is minimally generated
by {m + 1, m + 2, . . . , 2m + 1}. In other case we can apply the following result,
which is [2, Corollary 18].
Proposition 3.3. Let S be a numerical semigroup with minimal system of
generators msg(S) = {n1 < n2 < · · · < np }. If i ∈ {2, . . . , p} and ni > F(S),
then


 {n1 , . . . , np } \ {ni }, if there exists j ∈ {2, . . . , i − 1}
such that ni + n1 − nj ∈ S;
msg(S \ {ni }) =


({n1 , . . . , np } \ {ni }) ∪ {ni + n1 }, in other case.
Let us illustrate the previous results with an example.
Example 3.4. By Proposition 2.7, it is easy to see that S = h{5, 7, 8, 9, 11}i ∈
N ((1, 2), (4, 1), {5}). On the other hand, from Theorem 3.1, we know that the
set of children of S in the tree G(N ((1, 2), (4, 1), {5})) is
{S \ {m} | m ∈ msg(S), m > F(S), and S \ {m} ∈ N ((1, 2), (4, 1), {5})} .
Since F(S) = 6, we have that {m ∈ msg(S) | m > F(S)} = {7, 8, 9, 11}.
Furthermore, by Proposition 3.2, we know that S \ {m} ∈ N ((1, 2), (4, 1), {5})
if and only if m ∈
/ {5} and {m − 4, m−1
2 } ∩ (S \ {0}) = ∅. Thus, since that
9−1
}
∩(S
\
{0})
= {8 − 4, 8−1
{7 − 4, 7−1
2
2 } ∩(S \ {0}) = ∅, {9 − 4, 2 } ∩(S \ {0}) 6= ∅,
}
∩
(S
\
{0})
=
6
∅,
we
conclude
that
S
=
h{5, 7, 8, 9, 11}i has
and {11 − 4, 11−1
2
two children. Namely, they are h{5, 7, 8, 9, 11}i \ {7} = h{5, 8, 9, 11, 12}i and
h{5, 7, 8, 9, 11}i\ {8} = h{5, 7, 9, 11, 13}i, where we have applied Proposition 3.3.
Following the idea of the previous example, we can recurrently build the tree
G(N ((1, 2), (4, 1), {5})) beginning with its root, that is, from N = h{1}i.

9

h{1}i
h{2, 3}i
❅❅
h{2, 5}i

h{3, 4, 5}i
PP
PPP
✡✡
h{4, 5, 6, 7}i
h{3, 5, 7}i
❳❳❳
✚
❳
❅
❳❳
✚
❅
h{5, 6, 7, 8, 9}i
h{4, 5, 7}i
h{4, 5, 6}i
PP
PP
❏❏
PP
PPP
✡✡
P
h{5, 7, 8, 9, 11}i h{5, 6, 8, 9}i h{5, 6, 7, 9}i
h{4, 5, 11}i
❜
✡
❏
❜❜
✡
❏
h{5, 8, 9, 11, 12}i h{5, 7, 9, 11, 13}i h{5, 6, 9, 13}i
h{5, 9, 11, 12, 13}i
h{5, 9, 11, 13, 17}i
Let us observe that, since gcd({5} ∪ {4, 1}) = 1 and by Theorem 2.6, then
we know that N ((1, 2), (4, 1), {5}) is a finite Frobenius variety and, thereby, we
have been able of building it completely in a finite number of steps.
Let us also observe that, if S ∈ N (a, b, X), then g(S) is equal to the length of
the path connecting S with N in the tree G((N (a, b, X)). Therefore, in order to
build the elements of N (a, b, X) with a fixed genus g, we only need to build the
elements of N (a, b, X) which are connected to N through a path of length less
than or equal to g. Consequently, we have an algorithmic process to compute
all the solutions of the problem P(a, b, X, g).
For instance, in the tree G(N ((1, 2), (4, 1), {5})), the numerical semigroups
which are connected to N through a path of length 6 are h{5, 8, 9, 11, 12}i,
h{5, 7, 9, 11, 13}i, and h{5, 6, 9, 13}i. Therefore, the problem proposed in the introduction has three solutions. Namely, N \ h{5, 8, 9, 11, 12}i = {1, 2, 3, 4, 6, 7},
N\h{5, 7, 9, 11, 13}i = {1, 2, 3, 4, 6, 8}, and N\h{5, 6, 9, 11, 13}i = {1, 2, 3, 4, 7, 8}.
We finish with an example in which N (a, b, X) is an infinite Frobenius variety.
Example 3.5. Let us compute all the solutions of P((2, 3), (4, 2), {6, 8}, 4).
First of all, from Example 2.15, we know that M ((2, 3), (4, 2), {6, 8}) = h{6, 8}i
and, by Theorem 2.3, that the problem has solution. Moreover, since gcd({6, 8}∪
{4, 2}) = 2 6= 1, we have that N ((2, 3), (4, 2), {6, 8}) is a infinite Frobenius variety. However, in a finite number of steps, we can compute the elements of
G(N ((2, 3), (4, 2), {6, 8})) which are connected to N through a path of length 4,
such as we show in the following scheme.

10

h{1}i = N
h{2, 3}i
✧ ❜
❜❜
✧✧
h{3, 4, 5}i
h{2, 5}i
❍
❜
✏✏
❍❍
❜
❜
✏✏✏
h{4, 5, 6, 7}i h{3, 5, 7}i h{3, 4}i
h{2, 7}i
❜❳❳❳❳
✘✘✘
❅❅
✘
❅
❜
❳❳
✘
✘
❅
❜
h{5, 6, 7, 8, 9}i h{4, 6, 7, 9}i h{4, 5, 6}i h{3, 7, 8}i h{3, 5}i
h{2, 9}i
Therefore, the sets N\ h{5, 6, 7, 8, 9}i = {1, 2, 3, 4}, N\ h{4, 6, 7, 9}i = {1, 2, 3, 5},
N \ h{4, 5, 6}i = {1, 2, 3, 7}, N \ h{3, 7, 8}i = {1, 2, 4, 5}, N \ h{3, 5}i = {1, 2, 4, 7},
and N \ h{2, 9}i = {1, 3, 5, 7} are the (six) solutions of P((2, 3), (4, 2), {6, 8}, 4).
Remark 3.6. Let us observe that, in the construction of the trees, we can assume
that X = ∅ or that a, b are 0-tuples (see Remarks 2.12 and 2.13). Then, we
obtain correctly all the possible solutions in each case. In particular, if we
consider jointly such assumptions, then we get the tree associated to the full
family of numerical semigroups.

4

A generalization of the problem

Along this section r, g are non-negative integers, a = (a1 , . . . , an ) and b =
(b1 , . . . , bn ) are n-tuples of positive integers, and X is a non-empty subset of {r+
1, →}. We will denote by Pr (a, b, X, g) the (generalized) problem of computing
all the subsets C of {r + 1, →} that fulfill the following conditions.
(GP 1) The cardinality of C is equal to g.
(GP 2) If x, y ∈ {r + 1, →} and x + y ∈ C, then C ∩ {x, y} 6= ∅.
(GP 3) If x ∈ C and

x−bi
ai

∈ {r + 1, →} for some i ∈ {1, . . . , n}, then

x−bi
ai

∈ C.

(GP 4) X ∩ C = ∅.
Let us observe that P0 (a, b, X, g) = P(a, b, X, g).
It is clear that a set C is a solution of Pr (a, b, X, g) if and only if S =
{0, r + 1, →} \ C is a numerical semigroup that fulfills the following conditions.
(GS1) g(S) = r + g.
(GS2) If s ∈ S \ {0}, then as + b ∈ S n .
(GS3) X ⊆ S.

11

Let us denote by Nr (a, b, X) the set of all numerical semigroups which are
subsets of {0, r + 1, →} and satisfy the conditions (GS2) and (GS3). Let
us observe that, with this notation, the solutions of Pr (a, b, X, g) are the elements of the set {{0, r+, 1 →} \ S | S ∈ Nr (a, b, X) and g(S) = r + g}. Moreover, Nr (a, b, X) = {S ∈ N (a, b, X) | S ⊆ {0, r + 1, →}}.
The following proposition is analogous to Theorem 2.3.
T
Proposition 4.1. Let us take Mr (a, b, X) = S∈Nr (a,b,X) S. Then the problem
Pr (a, b, X, g) has solution if and only if the cardinality of N \ Mr (a, b, X) is
greatest than or equal to g + r.
Proof. (Necessity.) If C is a solution of Pr (a, b, X, g), then we have that S =
{0, r + 1, →} \ C ∈ Nr (a, b, X) and g(S) = g + r. Since Mr (a, b, X) ⊆ S, then
the cardinality of N \ Mr (a, b, X) is greatest than or equal to g + r.
(Sufficiency.) If {0, r + 1, →} \ Mr (a, b, X) = {c1 < · · · < cg < · · · } and
S = Mr (a, b, X) ∪ {cg + 1, →}, then it is easy to see that S ∈ Nr (a, b, X) and
g(S) = g + r. Therefore, C = {0, r + 1, →} \ S is a solution of Pr (a, b, X, g).
Observe that the cardinality of N \ Mr (a, b, X) is greatest than or equal to
g + r if and only if the cardinality of {0, r + 1, →} \ Mr (a, b, X) is greatest than
or equal to g.
Proposition 4.2. Mr (a, b, X) = M (a, b, X).
T
Proof. Since Nr (a, b, X) ⊆ N (a, b, X), then M (a, b, X) = S∈N (a,b,X) S ⊆
T
S∈Nr (a,b,X) S = Mr (a, b, X). Let us now see the other inclusion.
Since {0, r + 1, →} ∈ N (a, b, X) and N (a, b, X) is a Frobenius variety, we
have that, if S ∈ N (a, b, X), then S ∩{0, r+1, →} ∈ N (a, b, X). In addition, S ∩
{0, r+1, →} ⊆ {0, r+1, →} and, therefore, S∩{0, r+1, →} ∈ Nr (a, b, X). In this
way, R = {S T
∩ {0, r + 1, →} | ST∈ N (a, b, T
X)} ⊆ Nr (a, b, X). Consequently,
Mr (a, b, X) = S∈Nr (a,b,X) S ⊆ S∈R S = S∈N (a,b,X) S = M (a, b, X).
As an immediate consequence of Proposition 4.2 and Proposition 2.10, we
have the next result.
Corollary 4.3.
 If gcd (X ∪ {b1 , . . . , bn }) = d, then we get that Mr (a, b, X) =
d · M a, db , X
d .
Let us observe that, as a consequence fo the previous corollary, we can use
Algorithm 2.11 in order to compute Mr (a, b, X).
The following result is the analogous to Theorem 2.6 for the current problem.
Corollary 4.4. The following conditions are equivalent.
1. Nr (a, b, X) is finite.
2. Mr (a, b, X) is a numerical semigroup.
3. gcd(X ∪ {b1 , . . . , bn }) = 1.

12

Proof. The equivalence between conditions 2 and 3 is consequence of Proposition 4.2 and Theorem 2.6. Now, let us see the equivalence between conditions
1 and 2.
(1. ⇒ 2.) It is enough to observe that the finite intersection of numerical
semigroups is another numerical semigroup.
(2. ⇒ 1.) If S ∈ Nr (a, b, X), then Mr (a, b, X) ⊆ S. Thus, S = Mr (a, b, X) ∪
Y for some Y ⊆ N \ Mr (a, b, X). Since N \ Mr (a, b, X) is finite, then we can
conclude that Nr (a, b, X) is finite.
Let us illustrate the previous results with several examples.
Example 4.5. Let us see that Pr ((1, 2), (4, 1), {5}, 6) has solution if and only if
r ∈ {0, 1, 2}. Since {5} ⊆ {r + 1, →}, then we have that r ∈ {0, 1, 2, 3, 4, }. From
Proposition 4.2 and Example 2.14, we have that M = Mr ((1, 2), (4, 1), {5}, 6) =
h{5, 9, 11, 13, 17}i. Since N \ M = {1, 2, 3, 4, 6, 7, 8, 12} has cardinality equal to
8, by applying Proposition 4.1, we easily deduce that Pr ((1, 2), (4, 1), {5}, 6) has
solution if and only if r ∈ {0, 1, 2}.
Example 4.6. If r ∈ {0, 1, 2, 3, 4, 5}, then we have that Nr ((2, 3), (4, 2), {6, 8})
is an infinite set. In fact, this is an immediate consequence of Corollary 4.4 and
that gcd({4, 2, 6, 8}) = 2 6= 1.
Example 4.7. Let us compute P3 ((2, 3), (4, 2), {6, 8}, 9). From Proposition 4.2
and Example 2.15 we have that M3 ((2, 3), (4, 2), {6, 8}) = h{6, 8}i. Now, if we
apply the construction given in the sufficiency of Proposition 4.1, we have that
{4, 5, 7, 9, 10, 11, 13, 15, 17} is a solution.
If G is a tree and u, v are two vertices of G such that there exists a path
between them, then we will say that u is a descendant of v. The next result has
an easy proof.
Proposition 4.8. Nr (a, b, X) is the set of all descendants of {0, r + 1, →} in
the tree G(N (a, b, X)).
A Frobenius pseudo-variety (see [3]) is a non-empty family P of numerical
semigroups that fulfills the following conditions.
(P V 1) P has a maximum element max(P) (with respect to the inclusion
order).
(P V 2) If S, T ∈ P, then S ∩ T ∈ P.
(P V 3) If S ∈ P and S 6= max(P), then S ∪ F(S) ∈ P.
As an immediate consequence of Proposition 4.8 and the comment above to
Example 7 in [3], we have the following result.
Proposition 4.9. Nr (a, b, X) is a Frobenius pseudo-variety.

13

Let us observe that, if r ≥ 1, then max (Nr (a, b, X)) = {0, r + 1, →} 6= N.
Therefore, by applying [3, Proposition 1], we have that Nr (a, b, X) is not a
Frobenius variety.
Now, let us notice that the subgraph, of a tree, which is formed by a vertex
and all its descendants is also a tree. We will denote by G (Nr (a, b, X)) the
subtree of G (N (a, b, X)) formed by {0, r + 1, →} and all its descendants.
Example 4.10. Since the root of the tree G(N3 ((1, 2), (4, 1), {5})) is {0, 4, →}
= h{4, 5, 6, 7}i, from Example 3.4 we have that such a tree is the following one.
h{4, 5, 6, 7}i
❳❳❳
✚
❳❳❳
❅❅
✚
h{5, 6, 7, 8, 9}i
h{4, 5, 7}i
h{4, 5, 6}i
PP
PP
❏❏
PP
PPP
✡✡
P
h{5, 7, 8, 9, 11}i h{5, 6, 8, 9}i h{5, 6, 7, 9}i
h{4, 5, 11}i
❜
✡
❏
❜❜
✡
❏
h{5, 8, 9, 11, 12}i h{5, 7, 9, 11, 13}i h{5, 6, 9, 13}i
h{5, 9, 11, 12, 13}i
h{5, 9, 11, 13, 17}i
Let us observe that Nr (a, b, X) is the set of vertices in G (Nr (a, b, X)), and
that (S, S ′ ) ∈ Nr (a, b, X)×Nr (a, b, X) is an edge of G (Nr (a, b, X)) if and only if
S ′ = S ∪ {F(S)}. It is also clear that, if S ∈ Nr (a, b, X), then the set formed by
the children of S in Nr (a, b, X) is the same that the set formed by the children
of S in N (a, b, X). In this way, by applying Theorem 3.1, we have the next
result.
Proposition 4.11. The graph G (Nr (a, b, X)) is a tree with root {0, r + 1, →}.
Moreover, the set of children of a vertex S in G (Nr (a, b, X)) is
{S \ {m} | m ∈ msg(S), m > F(S), and S \ {m} ∈ N (a, b, X)} .
Now, let us notice that, by using Propositions 3.2 and 3.3, we can compute
the children of any vertex S in G (Nr (a, b, X)) and, consequently, we have an
algorithmic process to recurrently build the elements of Nr (a, b, X).
We finish this section with an illustrative example about the above comment.
Example 4.12. Let us compute all the solutions of P3 ((2, 3), (4, 2), {6, 8}, 4). In
order to do this, we have to determine the vertices of G(N3 ((2, 3), (4, 2), {6, 8}))
which are connected to {0, 4, →} = h{4, 5, 6, 7}i through a path of length 4.
Let us observe that, if A is the set of vertices (of a tree) which are connected
to the root through a path of length k, then the set formed by all vertices that
are children of some vertex of A is just the set of vertices which are connected to
14

the root through a path of length k + 1. Thus, if we denote by Ai the set formed
by the vertices of G(N3 ((2, 3), (4, 2), {6, 8})) which are connected to h{4, 5, 6, 7}i
through a path of length i, then (by applying Propositions 4.11, 3.2, and 3.3)
we obtain recurrently the following sets.
• A0 = {h{4, 5, 6, 7}i}
• A1 = {h{5, 6, 7, 8, 9}i, h{4, 6, 7, 9}i, h{4, 5, 6}i}
• A2 = {h{6, 7, 8, 9, 10, 11}i, h{5, 6, 8, 9}i, h{5, 6, 7, 8}i, h{4, 6, 9, 11}i,
h{4, 6, 7}i}
• A3 = {h{6, 8, 9, 10, 11, 13}i, h{6, 7, 8, 10, 11}i, h{6, 7, 8, 9, 11}i,
h{6, 7, 8, 9, 10}i, h{5, 6, 8}i, h{4, 6, 11, 13}i, h{4, 6, 9}i}
• A4 = {h{6, 8, 10, 11, 13, 15}i, h{6, 8, 9, 11, 13}i, h{6, 8, 9, 10, 13}i,
h{6, 8, 9, 10, 11}i, h{6, 7, 8, 11}i, h{6, 7, 8, 10}i, h{6, 7, 8, 9}i,
h{4, 6, 13, 15}i, h{4, 6, 11}i}
Therefore, the set of solutions of P3 ((2, 3), (4, 2), {6, 8}, 4) is
{h{4, 5, 6, 7}i \ S | S ∈ A4 } = {{4, 5, 7, 9}, {4, 5, 7, 10}, {4, 5, 7, 11}, {4, 5, 7, 13},
{4, 5, 9, 10}, {4, 5, 9, 11}, {4, 5, 10, 11}, {5, 7, 9, 11}, {5, 7, 9, 13}} .

References
[1] J. L. Ramı́rez Alfonsı́n, The Diophantine Frobenius problem. Oxford Lecture Series in Mathematics and its Applications, Vol. 30. (Oxford University
Press, Oxford, 2005).
[2] A. M. Robles-Pérez, J. C. Rosales, The numerical semigroup of phrases’
lengths in a simple alphabet, The Scientific World Journal 2013 (2013),
Article ID 459024, 9 pages.
[3] A. M. Robles-Pérez, J. C. Rosales, Frobenius pseudo-varieties in numerical
semigroups, Ann. Mat. Pura Appl. 194 (2015), 275-287.
[4] J. C. Rosales, Families of numerical semigroups closed under finite intersections and for the Frobenius number, Houston J. Math. 34 (2008), 339–348.
[5] J. C. Rosales and P. A. Garcı́a-Sánchez, Numerical semigroups. Developments in Mathematics, vol. 20. (Springer, New York, 2009).

15

