Semigroups with fixed multiplicity and
embedding dimension

arXiv:1710.03523v1 [] 10 Oct 2017

J. I. Garcı́a-Garcı́a

∗

M. A. Moreno-Frı́as

D. Marı́n-Aragón
‡

J. C. Rosales

A. Vigneron-Tenorio

†

§

¶

Abstract
Given m ∈ N, a numerical semigroup with multiplicity m is called
packed numerical semigroup if its minimal generating set is included in
{m, m + 1, . . . , 2m − 1}. In this work, packed numerical semigroups are
used to built the set of numerical semigroups with fixed multiplicity and
embedding dimension, and to create a partition in this set. Moreover,
Wilf’s conjecture is checked in the tree associated to some packed numerical semigroups.
Keywords: embedding dimension, Frobenius number, genus, multiplicity, numerical semigroup.
MSC-class: 20M14 (Primary), 20M05 (Secondary).

1

Introduction

Let N = {0, 1, 2, . . .} be the set of non-negative integers. A numerical semigroup
is a subset S of N which is closed by sum, 0 ∈ S and N\S is finite. We call
multiplicity to the least positive integer in S and we denote it by m(S).
Given a non-empty subset A of N we denote by hAi to the submonoid of
(N, +) generated by A, that is, hAi = {λ1 a1 + · · · + λn an | n ∈ N, a1 , . . . , an ∈
A, λ1 , . . . , λn ∈ N}. It is well known (for example, see Lemma 2.1 from [5])
that hAi is a numerical semigroup if and only if gcd(A) = 1.
∗ Dpto.
de Matemáticas/INDESS (Instituto Universitario para el Desarrollo Social
Sostenible). Universidad de Cádiz, E-11510 Puerto Real (Cádiz, Spain). E-mail: ignacio.garcia@uca.es. Partially supported by MTM2014-55367-P and by Junta de Andalucı́a
group FQM-366.
† E-mail: daniel.marinaragon@alum.uca.es. Partially supported by Junta de Andalucı́a
group FQM-366.
‡ Dpto. Matemáticas, Universidad de Cádiz, E-11510 Puerto Real (Cádiz, Spain). Email: mariangeles.moreno@uca.es. Partially supported by MTM2014-55367-P and by Junta
de Andalucı́a group FQM-298.
§ Dpto. de Álgebra, Universidad de Granada. Partially supported by MTM2014-55367-P
and by Junta de Andalucı́a group FQM-343. E-mail: jrosales@ugr.es.
¶ Dpto.
de Matemáticas/INDESS (Instituto Universitario para el Desarrollo Social
Sostenible). Universidad de Cádiz, E-11406 Jerez de la Frontera (Cádiz, Spain). E-mail: alberto.vigneron@uca.es. Partially supported by MTM2015-65764-C3-1-P (MINECO/FEDER,
UE) and Junta de Andalucı́a group FQM-366.

1

If S is a numerical semigroup and S = hAi, we say that A is a system of
generators of S. Moreover, A is a minimal system of generators of S if S 6= hBi
for every B ( A. In Theorem 2.7 from [5] it is shown that every numerical
semigroup has a unique minimal system of generator and this system is finite.
We denote by msg(S) and e(S) the minimal system of generators of S and its
cardinality, also called the embedding dimension of S.
In this work, our main aim is to show a procedure that allows us to build
recursively the set L(m, e) formed by all the numerical semigroup with multiplicity m and embedding dimension e.
We say that a numerical semigroup S is a packed numerical semigroup if
msg(S) ⊆ {m(S), m(S) + 1, . . . , 2m(S) − 1}. The set of all packed numerical semigroups with multiplicity m and embedding dimension e is denoted by
C(m, e).
In Section 2, an equivalence relation R in the set L(m, e) is defined. We show
that if S ∈ L(m, e) then [S] ∩ C(m, e) has cardinality 1, so {[S] | S ∈ C(m, e)} is
a partition if L(m, e). Hence, for computing all the elements of the set L(m, e)
is only necessary do the following steps:
1. Compute C(m, e).
2. For every S ∈ C(m, e) compute [S].
We see that it is easy to compute C(m, e) because, actually, this problem
is equivalent to compute all the subsets A of {1, 2, . . . , m − 1} such that A has
cardinality e−1 and gcd(A∪{m}) = 1. For computing [S] we order its elements
making a tree with root in S, and see how the children of the vertices are.
In this way, we can build recursively the elements of [S] adding in each step
the children of the vertices we got in the previous step. This procedure is not
algorithmic because [S] is infinite and we can not build it in a finite number of
steps.
If S is a numerical semigroup, we call Frobenius number (respectively, genus)
of S the greater integer which is not in S (respectively, the cardinality of N\S)
and we denote it by F (S) (respectively, g(S)). These invariants have been
widely studied (see [3]) and they, together with the embedding dimension, are
the background of one the most important problems in this theory: Wilf’s
conjecture which stablishes that if S is a numerical semigroup then e(S)g(S) ≤
(e(S) − 1)(F (S) + 1) (see [8]). Nowadays, it is still open.
In this work, we show that if we go along through the branches of the tree
associated to [S], the numerical semigroups have a greater Frobenius number
and genus. These facts allow us to give an algorithm for building all the elements
of L(m, e) with a fixed Frobenius number and/or genus. Finally, in order to
compute the Frobenius number and the genus of the numerical semigroups of
[S], we give an algorithm based in [2].
The content of this work is organized as follows. In Section 2, a partition of
the set L(m, e) is studied and we establish an application φ : L(m, e) → C(m, e)
such that [S] ∩ C(m, e) is equal to {φ(S)} for every S ∈ L(m, e). Theorem 9,
in Section 3, allows us to compute recursively the elements of [S]. In Section
4, we give some algorithms for computing the elements of [S] with Frobenius
number and/or genus less than fixed integer numbers. Finally, in Section 5, we
show how the Apery set of the elements of [S] allows us to compute easily their

2

Frobenius number and genus. Besides, we also check that Wilf’s conjecture is
satisfied for some elements of [S].

2

A partition of L(m, e)

If A and B are subsets of N we denote by A + B = {a + b | a ∈ A and b ∈ B}.
It is well known (for example see Proposition 2.10 from [5]) that if S is a
numerical semigroup then e(S) ≤ m(S). Note that if e(S) = 1 then S = N.
Therefore, in the sequel, we assume that e and m are integers such that 2 ≤ e ≤
m.
Given S ∈ L(m, e) we denote by φ(S) the numerical semigroup generated by
{m}+{x mod m | x ∈ msg(S)}. Clearly, φ(S) is a packed numerical semigroup
and therefore we have the following result.
Lemma 1. With the previous assumptions, φ defines a surjective map from
L(m, e) to C(m, e).
We define in L(m, e) the following equivalence relation: SRT if φ(S) = φ(T ).
Given S ∈ L(m, e), [S] denotes the set {T ∈ L(m, e) | SRT }. Therefore, the
quotient set L(m, e)/R = {[S] | S ∈ L(m, e)} is a partition of L(m, e).
Lemma 2. If S ∈ L(m, e), then [S] ∩ C(m, e) = {φ(S)}.
Proof. By Lemma 1, we know that φ(S) ∈ C(m, e). Moreover, it is clear that
φ(φ(S)) = φ(S). Therefore, SRφ(S) and φ(S) ∈ [S] ∩ C(m, e).
If T ∈ [S] ∩ C(m, e), then φ(T ) = φ(S) and φ(T ) = T , so T = φ(S).
The following result is a consequence of the previous lemmas.
Theorem 3. Let m and e be integers such that 2 ≤ e ≤ m. Then {[S] | S ∈
C(m, e)} is a partition of L(m, e). Moreover, if {S, T } ⊆ C(m, e) and S 6= T
then [S] ∩ [T ] = ∅.
Therefore, as a consequence of Theorem 3, for computing all the elements
of the set L(m, e) is only necessary to do the following steps:
1. Compute C(m, e).
2. For every S ∈ C(m, e) compute [S].
C(m, e) is easy to compute using the following result.
Proposition 4. Let m and e be integers such that 2 ≤ e ≤ m, and let A be
a subset of {1, . . . , m − 1} with cardinality e − 1 such that gcd(A ∪ {m}) = 1.
Then S = h{m} + (A ∪ {0})i ∈ C(m, e). Moreover, every element of C(m, e) has
this form.
Proof. The set S is a numerical semigroup because gcd({m} + (A ∪ {0})) =
gcd(A∪{m}) = 1. It is straightforward to prove that msg(S) = {m}+(A∪{0}),
so S ∈ C(m, e).
If S ∈ C(m, e) then msg(S) = {m, m+r1 , . . . , m+re−1 } with {r1 , . . . , re−1 } ⊆
{1 . . . , m − 1}.
Moreover, since gcd{m, m + r1 , . . . , m + re−1 } = 1,
gcd{m, r1 , . . . , re−1 } = 1.

3

We illustrate the content of the previous proposition with an example.
Example 5. We are going to compute the set C(6, 3) formed by all the packed
numerical semigroups of multiplicity 6 and embedding dimension 3. For this
purpose, and using Proposition 4, it is enough computing the subsets A of
{1, 2, 3, 4, 5} of cardinality 2 such that gcd(A ∪ {6}) = 1. These sets are {1, 2},
{1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {3, 5} and {4, 5}. Therefore, C(6, 3) is
{h6, 7, 8i, h6, 7, 9i, h6, 7, 10i, h6, 7, 11i, h6, 8, 9i, h6, 8, 11i, h6, 9, 10i, h6, 9, 11i, h6, 10, 11i}.
Note that if m is a prime number then every subset A of {1, . . . , m − 1}
with cardinality e − 1 verifies that gcd(A ∪ {m}) = 1. Therefore, we have the
following result.
Proposition 6. If m is a prime number and e is an integer number such that
2 ≤ e ≤ m then C(m, e) has cardinality m−1
e−1 .
Our next goal in this work is to show a recursive procedure that allows us
to compute [S] for every S ∈ C(m, e). In order to achieve it, in the next section,
we set the elements of [S] in a tree.

3

The tree associated to [S]

A graph G is pair (V, E) where V is a set (with elements called vertices) and E
is a subset of {(v, w) ∈ V × V | v 6= w} (with elements called edges). A path
which connects 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.
A graph G is a tree if there is a vertex r (known as the root of G) such that
for any other vertex x of G there exists a unique path connecting x and r. If
(x, y) is an edge of a tree, we say that x is a child of y.
Lemma 7. If {n1 < n2 < · · · < ne } is a minimal system of generators of a
numerical semigroup and ne − n1 > n1 then {n1 , . . . , ne−1 , ne − n1 } is also a
minimal system of generators of a numerical semigroup.
Proof. In other case, there exists k ∈ {1, . . . , e − 1} such that nk ∈ {ne −
n1 } + hn1 , . . . , nk−1 , nk+1 , . . . , , ne−1 , ne − n1 i. But it is not possible because
ne − n1 + n1 = ne > nk .
Let S be a numerical semigroup. We denote by M (S) the maximum of
msg(S). If S ∈ L(m, e), we define the following sequence of elements of L(m, e):
• S0 = S,
• Sn+1 = h(msg(Sn )\{M (Sn )}) ∪ {M (Sn ) − m}i if M (Sn ) − m > m.
Because of Lemma 7, there exists a sequence: S = S0 ( S1 ( . . . ( Sk =
φ(S) ∈ C(m, e).
Example 8. Let S ∈ L(5, 3) be the semigroup minimally generated by {5, 13, 21}.
Then, we have the following sequence of elements of L(5, 3): S0 = h5, 13, 21i (
S1 = h5, 13, 16i ( S2 = h5, 11, 13i ( S3 = h5, 8, 11i ( S4 = h5, 6, 8i = φ(S) ∈
C(5, 3).
Let S be in C(m, e). We define the graph G([S]) as follows: [S] is the set
of vertices and (A, B) ∈ [S] × [S] is an edge if msg(B) = (msg(A)\{M (A)}) ∪
{M (A) − m} with .
4

Theorem 9. If S ∈ C(m, e) then G([S]) is a tree with root S. Moreover, if
P ∈ [S] and msg(P ) = {n1 < n2 < · · · < ne } then the children of P in G([S])
are the numerical semigroups of the form h({n1 , . . . , ne }\{nk })∪{nk +n1 }i such
that k ∈ {2, . . . , e}, nk + n1 > ne and nk + n1 ∈
/ h{n1 , . . . , ne }\{nk }i.
Proof. From the definition and the comment after Lemma 7, we have that G([S])
is a tree with root S.
Let k be in {2, . . . , e} such that nk + n1 > ne and nk + n1 ∈
/
h{n1 , . . . , ne }\{nk }i. If H = h({n1 , . . . , ne }\{nk }) ∪ {nk + n1 }i is clear that
msg(H) = ({n1 , . . . , ne }\{nk })∪{nk +n1 } and msg(P ) = (msg(H)\{M (H)})∪
{M (H) − m}. Therefore H is a child of P .
Conversely, if H is a child P then (H, P ) is an edge of G([S]) and we obtain
that H is as the theorem describes.
The previous theorem allows us to build recursively the elements of [S] as it
is shown in the next example.
Example 10. Figure 1 shows some levels of the tree G([h5, 6, 8i]).
h5, 6, 8i

=

a

h5, 8, 11i

h5, 6, 13i

O

h5, 11, 13i

=

b

h5, 13, 16i

=

h5, 16, 18i

=

=

h5, 23, 26i

h5, 16, 23i

b

h5, 21, 23i

h5, 11, 23i

O

h5, 11, 28i

b

h5, 18, 26i

b

O

h5, 13, 21i

b

h5, 18, 21i

=

h5, 11, 18i

b

h5, 16, 28i

b

b

h5, 21, 28i

h5, 18, 31i

h5, 16, 33i

Figure 1: Seven levels of the tree of the packed numerical semigroup h5, 6, 8i.
Note that the cardinality of [S] is infinity, so it is impossible to compute all
the elements of [S]. However, in the next section, we show that it is possible to
compute all the elements of [S] with a fixed Frobenius number or genus.

5

4

Frobenius number and genus

Let P be a numerical semigroup with minimal generating set {n1 < n2 <
· · · < ne }, k ∈ {2, . . . , e} and H be the numerical semigroup generated by
({n1 , . . . , ne }\{nk })∪{nk +n1 }. Then H ⊂ P , F (P ) ≤ F (H) and g(P ) < g(H).
We can formulate the following result.
Proposition 11. If S ∈ C(m, e), P ∈ [S] and (H, P ) is an edge of G([S]) then
F (P ) ≤ F (H) and g(P ) < g(H).
From previous proposition, for every semigroup S the numerical semigroups
obtained from it have a greater or equal Frobenius number and a greater genus
than S. These facts allow us to formulate Algorithm 1 and 3 for computing all
the elements in [S] with Frobenius number less than or equal to a given integer
and genus less than or equal to another given integer.
Algorithm 1 Sketch of the algorithm to determinate the elements of T ∈ [S]
such that F (T ) ≤ F for a fixed integer F .
INPUT: (S, F ) where S is a packed numerical semigroup and F is a positive
integer.
OUTPUT: {T ∈ [S] | F (T ) ≤ F }.
1: if F (S) > F then
2:
return ∅
3: while true do
4:
A = {S} and B = {S}.
5:
C = {H | H is a child of an element of B, F (H) ≤ F }.
6:
if C = ∅ then
7:
return A
8:
A = A ∪ C, B = C.
Next example illustrates how the previous algorithm works.
Example 12. We compute all the elements of [h5, 6, 8i] with Frobenius number
less than or equal to 25.
• A = {h5, 6, 8i}, B = {h5, 6, 8i} and C = {h5, 8, 11i, h5, 6, 13i}.
• A = {h5, 6, 8i, h5, 8, 11i, h5, 6, 13i}, B = {h5, 8, 11i, h5, 6, 13i} and C =
{h5, 11, 13i}.
• A = {h5, 6, 8i, h5, 8, 11i, h5, 6, 13i, h5, 11, 13i}, B = {h5, 11, 13i} and C =
{h5, 11, 18i}.
• A = {h5, 6, 8i, h5, 8, 11i, h5, 6, 13i, h5, 11, 13i, h5, 11, 18i}, B = {h5, 11, 18i}
and C = ∅.
Therefore, the set {T ∈ [h5, 6, 8i] | F (T )
{h5, 6, 8i, h5, 8, 11i, h5, 6, 13i, h5, 11, 13i, h5, 11, 18i}.

≤

25} is equal to

Next algorithm allows us to compute all the numerical semigroups with
multiplicity m, embedding dimension e and Frobenius number less than or equal
to F . Note that if S is a numerical semigroup, such that S 6= N then m(S) − 1 ∈
/
S and then m(S) − 1 ≤ F (S).
6

Algorithm 2 Sketch of the algorithm to determinate the numerical semigroups
with a fixed embedding dimension and bounded Frobenius number.
INPUT: m, e, and F positive integers such that 2 ≤ e ≤ m ≤ F + 1.
OUTPUT: {S | S numerical semigroup, m(S) = m, e(S) = e and F (S) ≤
F }.
1: compute C(m, e), using Proposition 4.
2: for all S ∈ C(m, e) do
3:
compute A(S) = {T ∈ [S] | F (T ) ≤ F }, using Algorithm 1.
4: return ∪S∈C(m,e) A(S)
Now, we exchange the concept for Frobenius number for the genus in Algorithm 1 and 2.
Algorithm 3 Sketch of the algorithm to determinate the numerical semigroups
with bounded genus.
INPUT: (S, g) where S is a packed numerical semigroup and g is a positive
integer.
OUTPUT: {T ∈ [S] | g(T ) ≤ g}.
1: if g(S) > g then
2:
return ∅
3: A = {S} and B = {S}.
4: while true do
5:
C = {H | H is a child of an element of B, g(H) ≤ g}.
6:
if C = ∅ then
7:
return A
8:
A = A ∪ C, B = C
Next example illustrates how the previous algorithm works.
Example 13. We compute all the elements of [h5, 6, 8i] with genus less than or
equal to 15.
• A = {h5, 6, 8i}, B = {h5, 6, 8i} and C = {h5, 8, 11i, h5, 6, 13i}.
• A = {h5, 6, 8i, h5, 8, 11i, h5, 6, 13i}, B = {h5, 8, 11i, h5, 6, 13i} and C =
{h5, 11, 13i}.
• A = {h5, 6, 8i, h5, 8, 11i, h5, 6, 13i, h5, 11, 13i}, B = {h5, 11, 13i} and C =
{h5, 11, 18i}.
• A = {h5, 6, 8i, h5, 8, 11i, h5, 6, 13i, h5, 11, 13i, h5, 11, 18i}, B = {h5, 11, 18i}
and C = ∅.
Algorithm 3 returns {h5, 6, 8i, h5, 8, 11i, h5, 6, 13i, h5, 11, 13i, h5, 11, 18i}.
Note that if S is a numerical semigroup such that S 6= N then {1, . . . , m(S)−
1} ⊆ N\S and then m(S) − 1 ≤ g(S).
Next algorithm is obtained combining the previous results.

7

Algorithm 4 Sketch of an algorithm for computing numerical semigroups with
fixed multiplicity, embedding dimension and bounded genus
INPUT: m, e, and g positive integers such that 2 ≤ e ≤ m ≤ g + 1.
OUTPUT: {S | S numerical semigroup, m(S) = m, e(S) = e and g(S) ≤ g}.
1: compute C(m, e), using Proposition 4.
2: for all S ∈ C(m, e) do
3:
compute A(S) = {T ∈ [S] | g(T ) ≤ g}, using Algorithm 3.
4: return ∪S∈C(m,e) A(S)
Note that applying Algorithm 1 and 2 we have to compute the Frobenius
number and the genus, respectively, of the numerical semigroups we obtain
recursively when we build [S]. Results of the next section allow us to compute
easily the Frobenius number and the genus of every semigroup of [S].

5

The Apery set of the elements of [S]

Let S be a numerical semigroup and n ∈ S\{0}. The Apery set (named by [1])
of n in S is Ap(S, n) = {s ∈ S | s − n ∈
/ S}. Next result is a consequence of
Lema 2.4 from [5].
Lemma 14. Let S be a numerical semigroup and n ∈ S\{0}. Then Ap(S, n)
has cardinality n. Moreover, Ap(S, n) = {w(0) = 0, w(1), . . . , w(n − 1)} where
w(i) is the less element in S congruent with i modulo n.
The set Ap(S, n) give us a lot of information of S. The following result is
found in [7].
Lemma 15. Let S be a numerical semigroup and n ∈ S\{0}. Then:
• F (S) = max(Ap(S, n)) − n.
P
• g(S) = n1 ( w∈Ap(S,n) w) − n−1
2 .
The following result is a consequence of Lemma 14.
Lemma 16. Let S be a numerical semigroup with minimal system of generators {n1 , n2 , . . . , ne } and Ap(S, n1 ) = {0, w(1), . . . , w(n1 − 1)}. Then w(i) =
min{a2 n2 + · · · + ae ne | (a2 , . . . , ae ) ∈ Ne−1 and a2 n2 + · · · + ae ne ≡ i mod n1 }.
Note that the set {(a2 , . . . , ae ) ∈ Ne−1 | a2 n2 + · · · + ae ne ≡ i mod n1 }
has a finite number of minimal elements (using the usual ordering in Ne−1 ) by
Dickson’s Lemma (Theorem 5.1 from [4]). We denote the set of these minimal
elements by M((n1 , . . . , ne ), i). Next result is a obtained from Lemma 16.
Proposition 17. Let S be a numerical semigroup with minimal system of
generators {n1 , n2 , . . . , ne } and Ap(S, n1 ) = {0, w(1), . . . , w(n1 − 1)}. Then
w(i) = min{a2 n2 + · · · + ae ne | (a2 , . . . , ae ) ∈ M((n1 , . . . , ne ), i)}.
Next example illustrates the previous results.

8

Example 18. In this example we try to compute the Apery set of the numerical
semigroups of [h5, 6, 8i] that we obtained in Example 10.
For every i ∈ {1, 2, 3, 4} let A(i) be the set {(a2 , a3 ) ∈ N2 | a2 · 1 + a3 · 3 ≡
i mod 5}, and let M(i) be the set of the minimal elements of A(i). Then,
M(1) = {(1, 0), (0, 2)}, M(2) = {(2, 0), (0, 4), (1, 2)}, M(3) = {(3, 0), (0, 1)}
and M(4) = {(4, 0), (0, 3), (1, 1)}.
Now, if we take an element from [h5, 6, 8i], for example S = h5, 21, 13i,
and we want to compute Ap(S, 5) = {0, w(1), w(2), w(3), w(4)}, by applying
Proposition 17 we have that w(1) = min{21, 26} = 21, w(2) = min{42, 52, 47} =
42, w(3) = min{63, 13} = 13 and w(4) = min{84, 39, 34} = 34.
Note that in the previous example it was easy to compute M(i) for every
i ∈ {1, 2, 3, 4}. Now, we want to give an algorithm that always allows us to
compute M((n1 , . . . , ne ), i). In order to do it, we introduce the following sets:
C(1) = {(x2 , . . . , xe ) ∈ Ne−1 | n2 x2 + · · · + ne xe ≡ i mod n1 },
C(2) = {(x1 , x2 , . . . , xe ) ∈ Ne | (−n1 )x1 + n2 x2 + · · · + ne xe = i},
C(3) = {(x1 , x2 , . . . , xe , xe+1 ) ∈ Ne+1 | (−n1 )x1 +n2 x2 +· · ·+ne xe +(−i)xe+1 = 0}.
Lemma 19. If (a2 , . . . , ae ) ∈ C(1) then there exists a1 ∈ N such that
(a1 , a2 , . . . , ae ) ∈ C(2).
Proof. It is enough to note that if n2 a2 + · · · + ne ae ≡ i mod n1 then, there
exist a1 ∈ N such that n2 a2 + · · · + ne ae = i + a1 n1 .
Thanks to [6] we know that C(3) is a finitely generated submonoid of Ne+1 .
Next result can be deduced from Lemma 2 of [6].
Lemma 20. Let A be the set {α1 , . . . , αt } with αi = (αi1 , αi2 , . . . , αie , αi e+1 )
a system of generators of C(3). If we suppose that α1 , . . . , αd are the elements
in A with the last coordinate equal to zero and αd+1 , . . . , αq are the elements of
S with the last coordinate equal to 1, then C(2) = {ᾱd+1 , . . . ᾱq } + hᾱ1 , . . . , ᾱd i
where ᾱi = (αi1 , αi2 , . . . , αie ).
Note that M((n1 , . . . , ne ), i) are the minimal elements of C(1). Hence, the
following result allows us to compute it.
Proposition 21. The minimal elements of C(1) are the same that the minimal
elements of the set {(αd+1 2 , . . . , αd+1 e ), . . . , (αq2 , . . . , αqe )}.
Proof. Let k be in {d + 1, . . . , q}. We check if (αk2 , . . . , αke ) ∈ C(1). Since
(αk1 , . . . , αke , 1) ∈ C(3), then (−n1 )αk1 + n2 αk2 + · · · + ne αke − i = 0. Therefore
n2 αk2 + · · · + ne αke ≡ i mod n1 so (αk2 , . . . , αke ) ∈ C(1).
We finish the proof checking that if (a2 , . . . , ae ) ∈ C(1) then there exists
k ∈ {d + 1, . . . , q} such that (αk2 , . . . , αke ) ≤ (a2 , . . . , ae ). By Lemma 19, there
exists a1 ∈ N such that (a1 , a2 , . . . , ae ) ∈ C(2). Hence by Lemma 20, there exists
k ∈ {d + 1, . . . , q} such that (αk1 , αk2 , . . . , αke ) ≤ (a1 , a2 , . . . , ae ). Therefore, we
have that (αk2 , . . . , αke ) ≤ (a2 , . . . , ae ).
A efficient algorithm for computing a finite system of generators of C(3) is
given in [2]. So, applying the previous result we have an algorithm which allows
us to compute the minimal elements of C(1). Therefore, using Proposition 17
and the idea exposed in Example 18, we have an algorithm for computing easily
Ap(T, m) for every T ∈ [S]. Finally, thanks to Lemma 15 we can compute easily
F (T ) and g(T ) for every T ∈ [S].
9

6

Examples

We devote this section to illustrate the previous results with several examples.
They show all the semigroups with a fixed multiplicity, embedding dimension,
and Frobenius number or genus. Besides, we check Wilf’s conjecture for many
semigroups in the tree associated to [S] for several packed numerical semigroups.
The computations have been done in an Intel i7 with 32 Gb of RAM, and using
Mathematica ([9]).
Example 22. In this example we compute all the numerical semigroups with
multiplicity 6, embedding dimension 3, and Frobenius number equal to 23.
With these fixed conditions, the set C(m, e) is
{h6, 7, 8i, h6, 7, 9i, h6, 7, 10i, h6, 7, 11i, h6, 8, 9i,
h6, 8, 11i, h6, 9, 10i, h6, 9, 11i, h6, 10, 11i}.
The Frobenius number of these semigroups are 17, 17, 15, 16, 19, 21, 23, 25
and 25, respectively. So, by Proposition 11, for computing the semigroups
with Frobenius number 23, we only consider the packed numerical semigroups
L = {h6, 7, 8i, h6, 7, 9i, h6, 7, 10i, h6, 7, 11i, h6, 8, 9i, h6, 8, 11i, h6, 9, 10i}. Applying
Algortihm 2, we compute the elements in G([S]) with the fixed Frobenius number. For example, from the first packed numerical semigroups in L only one
numerical semigroup with Frobenius number equal to 23 is obtained (see Figure 2), but there is no numerical semigroups with Frobenius number equal to
23 in G[h6, 8, 9i] (see Figure 3). Hence, the set of numerical semigroups with
multiplicity 6, embedding dimension 3, and Frobenius number equal to 23 is
{h6, 8, 13i, h6, 7, 15i, h6, 7, 22i, h6, 7, 29i, h6, 9, 10i}.

h6, 7, 8i, Frob.no. = 17
O
h6, 8, 13i, Frob.no. = 23
5
i
h6, 13, 14i, Frob.no. = 35

h6, 8, 19i, Frob.no. = 29

Figure 2: Two levels of the tree associated to the semigroup h6, 7, 8i.

h6, 8, 9i, Frob.no. = 19
5
i
h6, 9, 14i, Frob.no. = 31

h6, 8, 15i, Frob.no. = 25

Figure 3: One level of the tree associated to the semigroup h6, 8, 9i.
Example 23. In this example, all the numerical semigroups with multiplicity 6,
embedding dimension 3, and genus equal to 16 are computed. From Example
10

22, the set C(6, 3) is
{h6, 7, 8i, h6, 7, 9i, h6, 7, 10i, h6, 7, 11i,
h6, 8, 9i, h6, 8, 11i, h6, 9, 10i, h6, 9, 11i, h6, 10, 11i}.
The genus of these semigroups are 9, 9, 9, 10, 10, 11, 12, 13 and 13, respectively.
So, by Proposition 11, for computing the semigroups with genus 16, we apply
Algorithm 3 to all elements in C(6, 3). For example, for the semigroups h6, 7, 8i
and h6, 8, 9i we obtain the trees showed in Figures 4 and 5, respectively. Thus,
the set of numerical semigroups with multiplicity 6, embedding dimension 3,
and genus 16 is
{h6, 14, 9i, h6, 8, 21i, h6, 15, 11i, h6, 10, 17i}.

h6, 7, 8i, genus = 9
O
h6, 8, 13i, genus = 12
5
h
h6, 13, 14i, genus = 18

h6, 8, 19i, genus = 15
O
h6, 8, 25i, genus = 18

Figure 4: Three levels of the tree associated to the semigroup h6, 7, 8i.

h6, 8, 9i, genus = 10
6
h
h6, 9, 14i, genus = 16

h6, 8, 15i, genus = 13
O
h6, 8, 21i, genus = 16

Figure 5: Two levels of the tree associated to the semigroup h6, 8, 9i.
Example 24. Now, we check Wilf’s conjecture for several elements in the tree
associated to some packed numerical semigroups. In this example, the elements
are showed as a set with three entries A, f, g where A is the minimal generating
set of a numerical semigroup, and f and g are their Frobenius number and
genus, respectively. Figure 6 illustrates two levels of the tree associated to
the semigroup S = h110, 216, 217, 218, 219i. Note that for all its elements the
(S)+1
e(S)
= 54 ≤ F g(S)
is held, and therefore they all satisfy Wilf’s
inequality e(S)−1
conjecture.

11

12

{{110, 218, 219, 326, 327}, 8911, 4456}

{{110, 217, 219, 326, 328}, 7811, 3927}

{{110, 217, 218, 219, 326}, 7811, 3925}

{{110, 216, 219, 327, 328}, 5941, 3025}

{{110, 216, 218, 327, 329}, 6051, 3026}

Figure 6: Tree for checking Wilf’s conjecture.

{{110, 217, 218, 326, 329}, 7811, 3926}

{{110, 216, 218, 219, 327}, 5941, 2998}

{{110, 216, 217, 218, 219}, 5941, 2971}

{{110, 216, 217, 328, 329}, 5941, 2974}

{{110, 216, 217, 219, 328}, 5941, 2972}

{{110, 216, 217, 218, 439}, 5941, 2973}

{{110, 216, 217, 218, 329}, 5941, 2972}

In Table 1 we show some packed numerical semigroups and the minimum
and maximum of the quotients (F (T ) + 1)/g(T ) of the semigroups T in their
associated trees until a fixed level. Note that all tested semigroups (more than
66000) satisfy Wilf’s conjecture.
Semigroup
{{97, 111, 142, 159, 171}, 958, 525}
{{110, 216, 217, 218, 219}, 5941, 2971}
{{115, 151, 172, 189, 201}, 1282, 724}
{{111, 115, 122, 171, 181, 200, 201}, 702, 445}
{{117, 125, 142, 173, 191, 203, 213}, 794, 476}

number
3694
425
2656
35735
28688

F (•)+1

min{ g(•) }
1496/981
2055/1081
1937/1224
1488/1027
382/261

F (•)+1

max{ g(•) }
2705/1357
2
670/339
2012/1041
899/458

Table 1: Checking Wilf’s conjecture (up to level 15).
Packed semigroups allow us to propose new problems for numerical semigroups. For example, minimal values of F (S) and g(S) for all S ∈ L(m, e) can
be studied by using this kind of semigroups. It is easy to prove that these minima are reached in elements belonging to C(m, e). So, min{F (S) | S ∈ L(m, e)}
and min{g(S) | S ∈ L(m, e)} can be computed from the finite sets {F (S) | S ∈
C(m, e)} and {g(S) | S ∈ C(m, e)}, respectively. Another interesting problem is
to compute max{F (S) | S ∈ C(m, e)}.

References
[1] R. Apéry, Sur les branches superlinéaires des courbes algébriques, C. R.
Acad. Sci. Paris 222 (1946), 1198–2000.
[2] E. Contejean and H. Devie, An efficient incremental algorithm for
solving system of linear Diophantine equations, Information and Computation 113 (1994), 143–172.
[3] J. L. Ramı́rez Alfonsı́n, The Diophantine Frobenius problem, Oxford
Univ. Press, 2005.
[4] J. C. Rosales, and P. A. Garcı́a-Sánchez, Finitely generated commutative monoids, Nova Science Publishers, Inc. New York, 1999.
[5] J. C. Rosales, and P. A. Garcı́a-Sánchez, Numerical semigroups,
Developments in Mathematics, Vol 20, Springer, New York, 2009.
[6] J. C. Rosales, and P. A. Garcı́a-Sánchez, J. I. Garcı́a-Garcı́a
and M. B. Branco, Systems of inequalities and numerical semigroups,
J. London Math. Soc. 65 (2002), 611–623.
[7] E. S. Selmer, On a linear Diophantine problem of Frobenius, J. Reine
Angew. Math 293/294 (1997), 1–17.
[8] H. S. Wilf, A circle-of-lights algorithm for the ”money-changing problem”,
Amer. Math. Monthly 85 (1978), 562–565.
[9] Wolfram Research, Inc. Mathematica, Versión 10.0, Champaign, IL
(2014).

13

