arXiv:1712.05220v1 [math.AC] 14 Dec 2017

Frobenius number and minimum genus of
numerical semigroups with fixed multiplicity and
embedding dimension
J. I. Garcı́a-Garcı́a

∗

M. A. Moreno-Frı́as

D. Marı́n-Aragón
‡

J. C. Rosales

A. Vigneron-Tenorio

†

§

¶

Abstract
Fixed two positive integers m and e, some algorithms for computing
the minimal Frobenius number and minimal genus of the set of numerical
semigroups with multiplicity m and embedding dimension e are provided.
Besides, the semigroups where these minimal values are achieved are computed too.
Keywords: embedding dimension, Frobenius number, genus, multiplicity, numerical semigroup.
MSC-class: 20M14 (Primary), 20M05 (Secondary).

1

Introduction

Given a subset S of the set of non-negative integers denoted by N, S is called a
numerical semigroup if 0 ∈ S, N \ S is finite and S is closed by sum.
If S is a numerical semigroup, it is well-known there exists a unique inclusionwise minimal finite subset A of N such that S = {λ1 a1 + · · · + λn an | n ∈
N, a1 , . . . , an ∈ A and λ1 , . . . , λn ∈ N} (see Theorem 2.7 from [8]). The set A is
called the minimal system of generators of S. In general, given a finite set A ⊂ N,
the monoid generated by A, hAi = {λ1 a1 + · · · + λn an | n ∈ N, a1 , . . . , an ∈ A
and λ1 , . . . , λn ∈ N}, is a numerical semigroup if and only if gcd(A) = 1 (see [8,
∗ 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

Lemma 2.1]). We denote by msg(S) the minimal system of generators of S; its
cardinality is called the embedding dimension of S and it is denoted by e(S).
Other important invariants of a numerical semigroup S are the following:
• The multiplicity of S (denoted by m(S)) is the least positive integer that
belongs to S.
• The Frobenius number of S (denoted by F (S)) is the greatest integer
which does not belong to S.
• The genus of S (denoted by g(S)) is the cardinality of N \ S.
For those readers who are not familiarized with Numerical Semigroup Theory, the terminology used (genus, multiplicity, embedding dimension,. . . ) may
result bizarre in the scope of semigroups. In the literature, one finds many
manuscripts devoted to the study of analytically unramified one dimensional
local domains via their value semigroups, which turn out to be numerical semigroups. All these invariants (see [2]) have interpretations in this theory, and
hence its names.
The relation of these invariantes is of great interest. Indeed, in [10] the
following conjeture appears: if S is a numerical semigroup then e(S)g(s) ≤
(e(S) − 1)(F (S) + 1). Nowadays, this conjecture is still open and it is one of
the most important problems in Numerical Semigroup Theory.
If m and e are positive integers we give the following notations: L(m, e) =
{S | S is a numerical semigroup, m(S) = m, e(S) = e}, g(m, e) = min{g(S) |
S ∈ L(m, e)} and F (m, e) = min{F (S) | S ∈ L(m, e)}. In this work we are
interested in giving algorithms for computing g(m, e), F (m, e), {S ∈ L(m, e) |
g(S) = g(m, e)} and {S ∈ L(m, e) | F (S) = F (m, e)}.
The results of this work are illustrated with several examples. To this aim, we
have used the library FrobeniusNumberAndGenus developed by the authors in
Mathematica ([11]). The library FrobeniusNumberAndGenus is freely available
online at [4]
This work is organized as follows. Section 2 contains some known results
on Frobenius pseudo-varieties which allow us to construct the tree of numerical
semigroup with fixed multiplicity. In Section 3 and Section 4, the minimal genus
and minimal Frobenius number of the set of numerical semigroups with fixed
multiplicity and embedding dimension are studied, giving some algorithm for
computing them and obtaining the semigroups with these minimal values.

2

Frobenius pseudo-variety of numerical semigroups with a fixed multiplicity

According to the notation of [6], a Frobenius pseudo-variety is a non-empty
family P of numerical semigroups which verifies the following conditions:
1. P has a maximum (according to the inclusion order).
2. If {S, T } ⊆ P then S ∩ T ∈ P.
3. If S ∈ P and S 6= max(P) then S ∪ {F (S)} ∈ P.

2

A graph G is a pair (V, E) where V is a set (vertices of G) and E is a subset of
{(u, v) ∈ V ×V | u 6= v} (edges of G). A path of length n connecting the vertices
x and y 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 exists a vertex r (known as the root) 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 son of y.
If P is a Frobenius pseudo-variety we define the graph G(P) as follows: P
is its set of vertices and (S, T ) ∈ P × P is an edge if T = S ∪ {F (S)}.
The following result is a direct consequence of Lemma 12 and Theorem 3 of
[6].
Proposition 1. If P is a Frobenius pseudo-variety, then G(P) is a tree with
root max(P). Moreover, the set of sons of a vertex S ∈ P is {S \ {x} ∈ P | x ∈
msg(S), x > F (S)}.
Let m be a positive integer. We denote by L(m) the set
{S | S is a numerical semigroup with m(S) = m}.
Clearly L(m) is a Frobenius pseudo-variety and max(L(m)) = {0, m, →} =
hm, m + 1, . . . , 2m − 1i. So, as a consequence of Proposition 1 we have the
following result which is fundamental in this work.
Theorem 2. The graph G(L(m)) is a tree rooted in hm, m + 1, . . . , 2m − 1i.
Moreover, the set formed by the sons of a vertex S ∈ L(m) is {S \ {x} | x ∈
msg(S), x > F (S) and x 6= m}.
The previous theorem allows us to build recursively L(m) from its root and
adding to the computed vertices its sons. We illustrate it with an example.
Example 3. We show some levels of tree G(L(4)) giving its vertices and edges,
and the minimal removed generators for obtaining the sons.
h4, 5, 6, 7i
O ●
c●
✐✐✐4
●
✐✐✐✐
✐
5
6
7 ●●
✐
✐
✐
✐
●
✐✐✐✐
h4, 6, 7, 9i
h4, 5, 7i
h4, 5, 6i
O
hPPP
O
❧6
PP
❧❧❧❧
❧
7
9 PPP
7
❧❧ 6
PP
❧❧❧❧
h4, 6, 7i
h4, 5, 11i
h4, 7, 9, 10i
h4, 6, 9, 11i
b ❉❉
O
O ❉
✈: O b❉❉❉
✈✈
7
9
10
9
11
11
❉❉❉
❉❉❉
✈
✈✈

h4, 9, 10, 11i

h4, 7, 10, 13i

h4, 7, 9i

h4, 6, 11, 13i

h4, 6, 9i

h4, 5i

If G is a tree with root r, the level of a vertex x is the length of the only path
which connect x and r. The height of a tree is the value of its maximum level.
If k ∈ N, we denote by N (k, G) = {v ∈ G | v has level k}. So, for Example 3
we have:
N (0, L(4)) = {h4, 5, 6, 7i}.
N (1, L(4)) = {h4, 6, 7, 9i, h4, 5, 7i, h4, 5, 6i}.
N (2, L(4)) = {h4, 7, 9, 10i, h4, 6, 9, 11i, h4, 6, 7i, h4, 5, 11i}.
N (3, L(4)) = {h4, 9, 10, 11i, h4, 7, 10, 13i, h4, 7, 9i, h4, 6, 11, 13i, h4, 6, 9i, h4, 5i}.
3

3

Elements of L(m, e) with minimum genus

Our aim in this section is to give an algorithm that allows us to compute g(m, e)
and {S | S ∈ L(m, e) and g(S) = g(m, e)}. The following result is a consequence
of Theorem 2.
Proposition 4. If m is a positive integer and (S, T ) an edge of G(L(m)), then
g(S) = g(T ) + 1.
As a direct consequence of the previous proposition we have the following
result.
Corollary 5. Fixed m, e ∈ N, if P = min{k ∈ N | N (k, G(L(m)))∩L(m, e) 6= ∅}
then {S ∈ L(m, e) | g(S) = g(m, e)} = N (P, G(L(m))) ∩ L(m, e). Moreover,
g(m, e) = m − 1 + P .
Note that if S is a numerical semigroup and e(S) = 1 then S = N. Note also
that by Proposition 2.10 of [8], if S is a numerical semigroup then e(S) ≤ m(S).
Moreover, it is clear that if m ≥ e ≥ 2 then hm, m + 1, . . . , m + e − 1i ∈ L(m, e).
In this way, we have the following result.
Proposition 6. Let m and e be positive integers.
1. If m < e then L(m, e) = ∅.
2. If e = 1 and L(m, e) 6= ∅ then m = 1 and L(m, e) = {N}.
3. If m ≥ e ≥ 2 then L(m, e) 6= ∅.
Now, we give an algorithm to compute g(m, e) and {S ∈ L(m, e) | g(S) =
g(m, e)}.
Algorithm 1 Sketch of the algorithm to compute g(m, e) and the set of semigroups with a fixed multiplicity and embedding dimension such that its genus
is g(m, e).
INPUT: m and e positive integers such that m ≥ e ≥ 2.
OUTPUT: g(m, e) and {S | S ∈ L(m, e) and g(S) = g(m, e)}.
1: Set k = 0 and A = {hm, m + 1, . . . , 2m − 1i}
2: while True do
3:
if A ∩ L(m, e) 6= ∅ then
4:
return m − 1 + k and A ∩ L(m, e)
5:
for S ∈ A do
6:
C(S)
[ = {T | T is a son of S}
7:
A=
C(S), k = k + 1.
S∈A

We illustrate now the previous algorithm with an example.
Example 7. We compute g(5, 3) and {S ∈ L(5, 3) | g(S) = g(5, 3)} using Algorithm 1.
• k = 0 and A = {h5, 6, 7, 8, 9i}.
• k = 1 and A = {h5, 7, 8, 9, 11i, h5, 6, 8, 9i, h5, 6, 7, 9i, h5, 6, 7, 8i}.
4

• k = 2 and
A = {h5, 8, 9, 11, 12i, h5, 7, 9, 11, 13i, h5, 7, 8, 11i,
h5, 7, 8, 9i, h5, 6, 9, 13i, h5, 6, 8i, h5, 6, 7i}.
It returns g(5, 3) = 6 and {S ∈ L(5, 3) | g(S) = 6} = {h5, 6, 8i, h5, 6, 7i}. In the
package FrobeniusNumberAndGenus, we can run the command Algorithm1[5,3]
to obtain this result.
If S is a numerical semigroup and n ∈ S \ {0}, then the Apéry set of n in
S is Ap(S, n) = {s ∈ S | s − n 6∈ S} (see [1]). Lemma 2.4 of [8] shows that
Ap(S, n) = {w(0) = 0, w(1), . . . , w(n − 1)} where w(i) is the least element of
S congruent with i modulus n. Note that w(i) = ki n + i for some ki ∈ N and
km + i ∈ S if and only if k ≥ ki . Therefore, we have the following result.
Lemma 8. Let S be a numerical semigroup, n ∈ S \ {0} and Ap(S, n) =
{0, k1 n + 1, . . . , kn−1 n + n − 1}. Then g(S) = k1 + · · · + kn−1 .
Next result can be easily deduced from Corollary 4 of [5].
Lemma 9. Let m and e integers such that m ≥ e ≥ 2, S = hm, m + 1, . . . , m +
e − 1i and m − 1 = q(e − 1) + r with q, r ∈ N and r ≤ e − 2. Then Ap(S, m) =
{0, m + 1, . . . , m + e − 1, 2m + (e − 1) + 1, . . ., 2m + 2(e − 1), . . . , qm + (q − 1)(e −
1) + 1, . . . , qm + q(e − 1), (q + 1)m + q(e − 1) + 1, . . . , (q + 1)m + q(e − 1) + r}.
If a, b ∈ N and b 6= 0 we denote by a mod b the remainder of dividing a by
b. If q is a rational number we denote by ⌊q⌋ = max{z ∈ Z | z ≤ q}. Note that
a = ⌊ ab ⌋b + (a mod b). From Lemma 8 and Lemma 9 we have the following
result.
Proposition 10. Let m and e be integers such that m ≥ e ≥ 2 and S =
hm, m + 1, . . . , m + e − 1i. Then,
k
j

m−1


(e
−
1)
e−1
m−1
g(S) =
+1 
+ (m − 1) mod (e − 1) .
e−1
2
Clearly hm, m+1, . . . , m+e−1i ∈ L(m, e) and therefore we have the following
result.
Corollary 11. If m and e are integers such that m ≥ e ≥ 2 then
k
j

m−1


e−1 (e − 1)
m−1
+1 
+ (m − 1) mod (e − 1) .
g(m, e) ≤
e−1
2
For many examples the equality holds. However, there are some cases where
the semigroup hm, m + 1, . . . , m + e − 1i does not have minimum genus in the
set L(m, e) as we show in the next example.
Example 12. S = h8, 9, 10i is a numerical semigroup and g(S) = 16. S̄ =
h8, 9, 11i is a numerical semigroup and g(S̄) = 14. Therefore, in this case
g(h8, 9, 10i) 6= g(8, 3).
5

Using the notation of [3], a numerical semigroup is packed 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 denote by C(m, e). The
following result is obtained from [3].
Proposition 13. If S ∈ L(m, e) then S̄ = h{m}+{x mod m | x ∈ msg(S)}i ∈
C(m, e) and g(S̄) ≤ g(S). Moreover, if S 6∈ C(m, e) then g(S̄) < g(S).
We illustrate the previous proposition with an example.
Example 14. If S = h5, 11, 17i ∈ L(5, 3) then S̄ = h{5} + {0, 1, 2}i = h5, 6, 7i ∈
C(5, 3). Therefore, g(S̄) ≤ g(S). Moreover, S 6∈ C(5, 3), so g(S̄) < g(S).
Next result is a consequence of Proposition 13.
Corollary 15. Let m and e be integers such that m ≥ e ≥ 2. Then
1. g(m, e) = min{g(s) | S ∈ C(m, e)}.
2. {S ∈ L(m, e) | g(S) = g(m, e)} = {S ∈ C(m, e) | g(S) = g(m, e)}.
Note that C(m, e) is finite and therefore the previous corollary give us another
algorithm for computing g(m, e) and {S ∈ L | g(S) = g(m, e)}. We give more
details about this method. Following result is Proposition 4 of [3].
Proposition 16. Let m and e integers such that m ≥ e ≥ 2 and A 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 has this form.
We illustrate the previous proposition with an example.
Example 17. We are going to compute C(6, 3). We start computing {A ⊆
{1, 2, 3, 4, 5} | #A = 2 and gcd(A ∪ {6}) = 1}. This set is equal to
{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {3, 5}, {4, 5}}.
Therefore,
C(6, 3) = {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}.
A simple computation shows us g(h6, 7, 8i) = 9, g(h6, 7, 9i) = 9, g(h6, 7, 10i) =
9, g(h6, 7, 11i) = 10, g(h6, 8, 9i) = 10, g(h6, 8, 11i) = 11, g(h6, 9, 10i) = 12,
g(h6, 9, 11i) = 13 and g(h6, 10, 11i) = 13.
Therefore, g(6, 3) = 9 and the set {S ∈ L(6, 3) | g(S) = 9} is equal to
{h6, 7, 8i, h6, 7, 9i, h6, 7, 10i}.

4

Elements of L(m, e) with minimum Frobenius
Number

Our aim in this section is to obtain algorithmic methods for computing F (m, e)
and {S ∈ L(m, e) | F (S) = F (m, e)}. Next result is a consequence of Theorem
2.

6

Proposition 18. If m is a positive integer and (S, T ) is an edge of G(L(m))
then F (T ) < F (S).
The following result can be deduced from [7].
Proposition 19. If m is a positive integer and (S, T ) is an edge of G(L(m))
then e(S) ≤ e(T ).
Clearly F (m, m) = m − 1 and {S ∈ L(m, m) | F (S) = m − 1} = {hm, m +
1, . . . , 2m − 1i}. It is well known (see [9] for example) that if S = hn1 , n2 i is a
numerical semigroup, then F (S) = n1 n2 − n1 − n2 . Therefore, we obtain the
following result.
Proposition 20. Let m be an integer such that m ≥ 2.
1. F (m, m) = m − 1 and {S ∈ L(m, m) | F (S) = m − 1} = {hm, m +
1, . . . , 2m − 1i}.
2. F (m, 2) = m2 − m − 1 and {S ∈ L(m, 2) | F (S) = m2 − m − 1} =
{hm, m + 1i}.
If q is a rational number we denote by ⌈q⌉ = min{z ∈ Z | q ≤ z}. Next
result is deduced from [5, Corollary §4.5].
Proposition 21. If m and e are integers such that m ≥ e ≥ 2 then F (hm, m +
1, . . . , m + e − 1i) = ⌈ m−1
e−1 ⌉m − 1.
As a consequence of the previous proposition we get the following result.
Corollary 22. If m and e are integers such that m ≥ e ≥ 2 then F (m, e) ≤
⌈ m−1
e−1 ⌉m − 1.
In the previous corollary, the equality holds plenty of times, but in some
cases F (hm, m + 1, . . . , m + e − 1i) 6= min{F (S) | S ∈ L(m, e)}. For example,
F (h4, 5, 6i) = 7 and F (h4, 5, 7i) = 6.
From the above results, we obtain the following algorithm where the projections from the cartesian product L(m) × N are denoted by π1 and π2 .
Algorithm 2 Sketch of the algorithm to compute F (m, e) and the set of semigroup with a fixed multiplicity and embedding dimension such that its Frobenius
number is F (m, e).
INPUT: m and e integers such that m ≥ e ≥ 2.
OUTPUT: F (m, e) and {S ∈ L(m, e) | F (S) = F (m, e)}.
1: A = {hm, m + 1, . . . , 2m − 1i}, I = ∅ and α = ⌈ m−1
e−1 ⌉m − 1
2: while True do
3:
C = {(S, F (S)) | S is son of some element of A and F (S) ≤ α}
4:
K = {S ∈ π1 (C) | e(S) ≥ e}
5:
if K = ∅ then
6:
return F (m, e) = π2 (I) and {S ∈ L(m, e) | F (S) = F (m, e)} =
π1 (I)
7:
A = K, B = {(S, F (S)) | S ∈ K and e(S) = e}
8:
α = min(π2 (B) ∪ {α}), I = {(S, F (S)) ∈ I ∪ B | F (S) = α}.
We illustrate with an example how this algorithm works.
7

Example 23. We compute F (4, 3) and {S ∈ L(4, 3) | F (S) = F (4, 3)} using
Algorithm 2.
• A = {h4, 5, 6, 7i}, I = ∅ and α = ⌈ 23 ⌉4 − 1 = 7.
• C = {(h4, 6, 7, 9i, 5), (h4, 5, 7i, 6), (h4, 5, 6i, 7)} and
K = {h4, 6, 7, 9i, h4, 5, 7i, h4, 5, 6i}.
• A = {h4, 6, 7, 9i, h4, 5, 7i, h4, 5, 6i}, B = {(h4, 5, 7i, 6), (h4, 5, 6i, 7)}, α =
min{6, 7} = 6 and I = {(h4, 5, 7i, 6)}.
• C = {(h4, 7, 9, 10i, 6)} and K = {h4, 7, 9, 10i}.
• A = {h4, 7, 9, 10i}, B = ∅, α = 6 and I = {(h4, 5, 7i, 6)}.
• C = ∅ and K = ∅.
Therefore, F (4, 3) = 6 and {S ∈ L(4, 3) | F (S) = 6} = {h4, 5, 7i}. Using the Mathematica package [4], running the commands MinFrob[4,3] and
FrobeniusEmbeddingDimensionMultiplicity[6,3,4], we obtain 6 and h4, 5, 7i,
respectively.
Our next goal is to give an alternative algorithm for computing F (m, e) and
{S ∈ L(m, e) | F (S) = F (m, e)}. Next result is deduced from [3].
Proposition 24. If S ∈ L(m, e) then S̄ = h{m}+{x mod m | x ∈ msg(S)}i ∈
C(m, e) and F (S̄) ≤ F (S).
As a consequence of the previous proposition we get the following result.
Corollary 25. If m and e are integers such that m ≥ e ≥ 2 then F (m, e) =
min{F (S) | S ∈ C(m, e)}.
The set C(m, e) is finite, so previous corollary give us an algorithmic method
for computing F (m, e).
Example 26. We compute F (6, 5). First, we calculate C(6, 5) by using Proposition 16 and then we apply Corollary 25. So,
C(6, 5) = {h6, 7, 8, 9, 10i, h6, 7, 8, 9, 11i,
h6, 7, 8, 10, 11i, h6, 7, 9, 10, 11i, h6, 8, 9, 10, 11i}
and therefore F (6, 5) = min{F (h6, 7, 8, 9, 10i) = 11, F (h6, 7, 8, 9, 11i) = 10,
F (h6, 7, 8, 10, 11i) = 9, F (h6, 7, 9, 10, 11i) = 8, F (h6, 8, 9, 10, 11i) = 13} = 8.
Now, we are interested in giving an algorithmic method for computing {S ∈
L(m, e) | F (S) = F (m, e)}. Next example shows us that there exist semigroups
S ∈ L(m, e) such that S 6∈ C(m, e) and F (S) = F (m, e).
Example 27. The numerical semigroups S1 = h7, 9, 10, 15i and S2 = h7, 8, 10, 19i
verify that S1 , S2 ∈ L(7, 4) \ C(7, 4) and F (S1 ) = F (S2 ) = 13 = F (7, 4).
If S ∈ L(m, e) we denote by θ(S) the numerical semigroup generated by
{m} + {x mod m | x ∈ msg(S)}. Clearly, θ(S) ∈ C(m, e).
We define in L(m, e) the following equivalence relation: SRT if and only if
θ(S) = θ(T ). We denote by [S] 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). Next
result is Theorem 3 from [3].
8

Proposition 28. Let m and e be integers such that m ≥ e ≥ 2. 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 ] = ∅.
As a consequence of the previous proposition we have that for computing
{S ∈ L(m, e) | F (S) = F (m, e)} is enough doing the following two steps:
1. Compute A = {S ∈ C(m, e) | F (S) = F (m, e)}.
2. For every S ∈ A, compute {T ∈ [S] | F (T ) = F (S)}.
We already know how to compute 1. Now, we focus on giving an algorithm that
allows us to compute 2.
Using Algorithm 12 from [3], for S ∈ C(m, e) and F ∈ N we get the set
{T ∈ [S] | F (T ) ≤ F }. Clearly if S ∈ C(m, e) then {T ∈ [S] | F (T ) = F (S)} =
{T ∈ [S] | F (T ) ≤ F (S)}. Therefore we are going to adapt Algorithm 12 from
[3] to our needs for computing 2. But before of that, we introduce some concepts
and results.
If S is a numerical semigroup, we denote by M (S) = max(msg(S)). If
S ∈ C(m, e) we define the graph G([S]) as follows: [S] is its set of vertices and
(A, B) ∈ [S] × [S] is an edge if msg(B) = (msg(A) \ {M (A)}) ∪ {M (A) − m}.
The following result is Theorem 9 from [3].
Proposition 29. 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 sons 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.
Now we give an algorithm such that for a semigroup S ∈ C(m, e) it computes
the set {T ∈ [S] | F (T ) = F (S)}.
Algorithm 3 Sketch of the algorithm to compute the semigroups of each equivalence class such that their Frobenius number is minimum
INPUT: S ∈ C(m, e).
OUTPUT: {T ∈ [S] | F (T ) = F (S)}.
1: A = {S} and B = {S}
2: while True do
3:
C = {H | H is son of an element of B and F (H) = F (S)}
4:
if C = ∅ then
5:
return A
6:
A = A ∪ C, B = C.
We finish this section with an example for illustrate the above algorithm.
Example 30. We use now Algorithm 3 for computing {T ∈ [S] | F (T ) = F (S) =
10} where S = h6, 7, 8, 9, 11i ∈ C(6, 5).
• A = {h6, 7, 8, 9, 11i} and B = {h6, 7, 8, 9, 11i}.
• C = {h6, 8, 9, 11, 13i, h6, 8, 11, 13, 15i}.
• A = {h6, 7, 8, 9, 11i, h6, 8, 9, 11, 13i, h6, 8, 11, 13, 15i} and
B = {h6, 8, 9, 11, 13i, h6, 8, 11, 13, 15i}.
9

• C = ∅.
Therefore, {T ∈ [S] | F (T ) = 10} = {h6, 7, 8, 9, 11i, h6, 8, 9, 11, 13i, h6, 8, 11, 13, 15i}.
This result is also obtained by executing the command Algorithm3[{6,7,8,9,11}]
of [4]).

References
[1] R. Apéry, Sur les branches superlinéaires des courbes algébriques, C.R.
Acad. Sci. Paris 222 (1946), 1198–2000.
[2] V. Barucci, D. E. Dobbs and M. Fontana, Maximality Properties in
Numerical Semigroups and Applications to One-Dimensional Analitycally
Irreducible Local Domains, Memoirs Amer. Math. Soc. 598 (1997).
[3] J. I. Garcı́a-Garcı́a, D. Marı́n-Aragón, M. A. Moreno-Frı́as, J.
C. Rosales and A. Vigneron-Tenorio, Semigroups with fixed multiplicity and embedding dimension, arXiv:1710.03523 (2017).

[4] J. I. Garcı́a-Garcı́a, D. Marı́n-Aragón, A. VigneronTenorio,
FrobeniusNumberAndGenus, a Mathematica package for computations in numerical semigroups.
Available at
http://departamentos.uca.es/C101/pags-personales/alberto.vigneron/frobeniusnumberandge
[5] P. A. Garcı́a-Sánchez and J. C. Rosales, Numerical Semigroups
generated by intervals, Pacific J. Math. 191 (1999), 75-83.
[6] A. M. Robles-Pérez and J. C. Rosales, Frobenius pseudo-varieties in
numerical semigroups, Ann. Mat. Pura Appl. 194 (2015), 275-287.
[7] J. C. Rosales, On numerical semigroups, Semigroup Forum 52 (1996),
307-318.
[8] J. C. Rosales and P. A. Garcı́a-Sánchez, Numerical semigroups,
Developments in Mathematics, Vol. 20, Springer, New York, 2009.
[9] J. J. Sylvester, Problem 7382, Educat. Times J. College Preceptors
New Ser. 36 (1883), 177.
[10] H. S. Wilf, A circle-of-lights algorithm for the ”money-changing problem”,
Amer. Math. Monthly 85 (1978), 562–565.
[11] Wolfram Mathematica Research, Inc., Mathematica version 10.
Champaign, Illinois (2014).

10

