ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 17 (2019) 397-417 https://doi.org/10.26493/1855-3974.1937.5ea (Also available at http://amc-journal.eu) Semigroups with fixed multiplicity and embedding dimension* * Juan Ignacio García-Garcíaf Dpto. de Matemáticas/INDESS (Instituto Universitario para el Desarrollo Social Sostenible). Universidad de Cadiz, E-11510, Puerto Real (Cadiz, Spain) Daniel Marín-Aragon t Dpto. de Matematicas. Universidad de Cadiz, E-11510, Puerto Real (Cadiz, Spain) María Angeles Moreno-Frías * Dpto. Matematicas, Universidad de Cadiz, E-11510, Puerto Real (Cadiz, Spain) Jose Carlos Rosales § Dpto. de Algebra, Universidad de Granada, E-18071, Granada (Spain) Alberto Vigneron-Tenorio 1 Dpto. de Matemciticas/INDESS (Instituto Universitario para el Desarrollo Social Sostenible). Universidad de Cadiz, E-11406 Jerez de la Frontera (Cadiz, Spain) Received 15 February 2019, accepted 11 September 2019, published online 4 November 2019 Given m G N, a numerical semigroup with multiplicity m is called a 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 build the set of numerical semigroups with a given multiplicity and embedding dimension, and to create a partition of this set. Wilf's conjecture is verified in the tree associated to some packed numerical semigroups. Furthermore, given two positive integers m and e, some algorithms for computing the minimal Frobenius number and minimal genus of the set of numerical semigroups with * The authors would like to thank the referee and the editor for their useful comments and suggestions to help improving this paper. t Partially supported by MTM2017-84890-P and by Junta de Andalucía group FQM-366. t Partially supported by MTM2017-84890-P and by Junta de Andalucía group FQM-298. § Partially supported by MTM2017-84890-P and by Junta de Andalucía group FQM-343. ^ Partially supported by MTM2015-65764-C3-1-P (MINECO/FEDER, UE), by MTM2017-84890-P and by Junta de Andalucía group FQM-366. Abstract ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 397 Ars Math. Contemp. 17 (2019) 349-368 multiplicity m and embedding dimension e are provided. We also compute the semigroups where these minimal values are achieved. Keywords: Embedding dimension, Frobenius number, genus, multiplicity, numerical semigroup. Math. Subj. Class.: 20M14, 20M05 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 under addition, such that 0 G S and N \ S is finite. If S is a numerical semigroup, we define the multiplicity of S, denoted by m(S), to be the least positive integer in S, the Frobenius number (F(S)) to be the greatest integer that is not in S, and the genus, g(S), to be the cardinality of N \ S. Given a non-empty subset A of N we denote by (A) the submonoid of (N, +) generated by A, that is, (A) = {Aiai +-----+ A„an | n G N, ai,..., an G A, Ai,..., An G N}. It is well known (for example, see Lemma 2.1 from [11]) that (A) is a numerical semigroup if and only if gcd(A) = 1. If S is a numerical semigroup and S = (A), we say that A is a system of generators of S. Moreover, A is a minimal system of generators of S if S = (B) for every B C A. In Theorem 2.7 from [11] 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. If m and e are positive integers we use the following notation: L(m, e) = {S | S is a numerical semigroup, m(S) = m, e(S) = e}. In this work, one of our aims is to present a procedure that allows us to recursively construct the set L(m, e). We say that a numerical semigroup S is a packed numerical semigroup if msg(S) C {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. For each S G L(m, e) we denote by [S], the equivalence class of S. We show that if S G L(m, e) then [S] nC(m, e) has cardinality 1, so {[S] | S G C(m, e)} is apartition of L(m, e). Hence, for computing all the elements of the set L(m, e) it is only necessary to perform the following steps: 1. Compute C(m, e). 2. For every S G C(m, e) compute [S]. E-mail addresses: ignacio.garcia@uca.es (Juan Ignacio García-García), daniel.marin@uca.es (Daniel Marín-Aragón), mariangeles.moreno@uca.es (María Angeles Moreno-Frías), jrosales@ugr.es (Jose Carlos Rosales), alberto.vigneron@uca.es (Alberto Vigneron-Tenorio) J. I. Garcia-Garcia et al.: Semigroups with fixed multiplicity and embedding dimension 399 We see that it is possible to compute C(m, e), since this problem is equivalent to computing all the subsets A of {1,2,..., m - 1} such that A has cardinality e - 1 and gcd(A U {m}) = 1. For computing [S], we order its elements by making a tree whose root is S, and describing the children of each of the vertices. In this way, we can recursively build the elements of [S] by adding in at each step the children of the vertices that were obtained in the previous step. This procedure is not algorithmic because [S] is infinite so we can not build it in a finite number of steps. The Frobenius number and genus have been widely studied (see [7]) and they, together with the embedding dimension, are the background of one the most important problems in this theory: Wilf's conjecture which asserts that if S is a numerical semigroup then e(S)g(S) < (e(S) - 1)(F(S) + 1) (see [15]). At present, it is still open. In this work, we show that if we go along through a branch of the tree associated to [S], the numerical semigroups have a greater Frobenius number and genus. These facts enable 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 on [3]. We would like to note that these new algorithms enable us to study the tree of numerical semigroups with a given multiplicity and embedding dimension and with Frobenius number and/or genus up to any given bound. In some works, there appear algorithms for the computation of the tree of numerical semigroups up to a certain genus (see for example [4]). In our work, there can also be a bound on the Frobenius number. In addition, the computation of the complete tree of numerical semigroups up to a certain genus is not a practical method to obtain the numerical semigroups with a fixed multiplicity and embedding dimension, since it performs unnecessary calculations and does not obtain as large a genus as we can get with our algorithms. We are also interested in giving algorithms for computing g(m, e) = min{g(S) | S G L(m, e)}, F(m, e) = min{F(S) | S G L(m, e)}, {S G e) 1 g(S) = g(m e)} and {S G L(m, e) | F(S) = F(m, e)}. These methods are illustrated with several examples. To accomplish this, we have used the library FrobeniusNumberAndGenus developed by the authors in Mathematica ([16]). This library is freely available online at [5]. The content of this work is organized as follows. In Section 2, a partition of the set L(m, e) is studied and we construct a map ^: L(m, e) ^ C(m, e) such that [S] n C(m, e) is equal to {^(S)} for every S G L(m, e). Theorem 3.3, in Section 3, is used to recursively compute 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 bounds. In Section 5, we show how the Apery set of the elements of [S] is used to compute their Frobenius number and genus. We also check that Wilf's conjecture is satisfied for some elements of [S]. Section 6 illustrates the preceding section and Section 7 contains some known results on Frobenius pseudo-varieties which allow us to construct the tree of all numerical semigroups with any given multiplicity. In Section 8 and Section 9, the minimal genus and minimal Frobenius number of the set of numerical semigroups with fixed multiplicity and embedding dimension are studied, giving some algorithms for computing them and obtaining the semigroups with these minimal values. 400 Ars Math. Contemp. 17 (2019) 349-368 2 A partition of L(m, e) If A and B are subsets of N we denote by A + B = {a + b | a e A and b e B}. It is well known (for example see Proposition 2.10 from [11]) 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 e L(m, e) we denote by ¿(S) the numerical semigroup generated by {m} + {x mod m | x e msg(S)}. Clearly, ¿(S) is a packed numerical semigroup and therefore we have the following result. Lemma 2.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: S R T if ¿(S) = ¿(T). Given S e L(m, e), [S] denotes the set {T e L(m, e) | S R T}. Therefore, the quotient set L(m, e)/R = {[S] | S e L(m, e)} is a partition of L(m, e). Lemma 2.2. If S e L(m, e), then [S] n C(m, e) = {¿(S)}. Proof. By Lemma 2.1, we know that ¿(S) e C(m, e). Moreover, it is clear that ¿(¿(S)) = ¿(S). Therefore, S R ¿(S) and ¿(S) e [S] n C(m, e). If T e [S] n C(m, e), then ¿(T) = ¿(s) and ¿(T) = T, so T = ¿(S). □ The following result is a consequence of the previous lemmas. Theorem 2.3. Let m and e be integers such that 2 < e < m. Then {[S] | S e C(m, e)} is a partition of L(m, e). Moreover, if {S, T} C C(m, e) and S = T then [S] n [T] = 0. Therefore, as a consequence of Theorem 2.3, for computing all the elements of the set L(m, e) it is only necessary to do the following steps: 1. Compute C(m, e). 2. For every S e C(m, e) compute [S]. C(m, e) is easy to compute using the following result. Proposition 2.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 U {m}) = 1. Then S = ({m} + (A U{0})) e 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 U {0})) = gcd(A U {m}) = 1. It is straightforward to prove that msg(S) = {m} + (A U {0}), so S e C(m, e). If S e C(m, e) then msg(S) = {m, m + ri,..., m + re_i} with {ri,..., re_i} C {1..., m — 1}. Moreover, since gcd{m, m + ri,..., m + re-i} = 1, gcd{m, ri,. .., re_i} = 1. □ J. I. Garcia-Garcia et al.: Semigroups with fixed multiplicity and embedding dimension 401 We illustrate the content of the previous proposition with an example. Example 2.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 2.4, it is enough computing the subsets A of {1,2,3,4, 5} of cardinality 2 such that gcd(A U {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) = {(6, 7, 8), (6, 7, 9), (6, 7,10), (6, 7,11), (6, 8, 9), (6, 8,11), (6, 9,10), (6, 9,11), (6,10,11)}. Note that if m is a prime number then every subset A of {1,..., m -1} with cardinality e - 1 verifies that gcd(A U {m}) = 1. Therefore, we have the following result. Proposition 2.6. If m is a prime number and e is an integer number such that 2 < e < m then C(m, e) has cardinality (^—1). Our next goal in this work is to show a recursive procedure 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 x V | v = 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 exists 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 3.1. 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 — ni} + (ni,. .. ,nfc_i,nfc+i,. .., ,ne_i,n — ni). 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): • So = S, • Sn+1 = ((msg(Sn) \ {M(Sn)}) U {M(S„) — m}) if M(S„) — m > m. Because of Lemma 3.1, there exists a sequence: S = S0 C S1 C • • • C Sk = ^(S) € C(m, e). 402 Ars Math. Contemp. 17 (2019) 349-368 Example 3.2. Let S G 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 = (5,13, 21) C Si = (5,13,16) C S2 = (5,11,13) C S3 = (5, 8,11) C S4 = (5, 6, 8) = ^(S) G 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) g [S] x [S] is an edge if msg(B) = (msg(A) \ {M(A)}) U {M(A) - m}. Theorem 3.3. If S G C(m, e) then G([S]) is a tree with root S. Moreover, if P G [S] and msg(P) = {n1 < n2 < • • • < ne} then the children of P in G([S]) are the numerical semigroups of the form (({n1,... , ne} \ {nk}) U {nk + n1}) such that k G {2,..., e}, nk + ni > ne and nk + ni G ({ni, ...,ne}\ {nk}). Proof. From the definition and the comment after Lemma 3.1, 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 G ({n1,..., ne} \ {nk}). If H = (({n1,..., ne} \ {nk}) U {nk + n1}) is clear that msg(H) = ({n1, ...,ne}\ {nk }) U {nk + nj and msg(P) = (msg(H) \ {M(H)}) U {M(H) - m}. Therefore H is a child of P. Conversely, if H is a child of P then (H, P) is an edge of G([S]) and we obtain that H is as the theorem describes. □ The previous theorem provides us with a method to recursively build the elements of [S] as it is shown in the next example. Example 3.4. Figure 1 shows some levels of the tree G([(5,6,8)]). 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. 4 Frobenius number and genus Let P be a numerical semigroup with minimal generating set {n1 < n2 < • • • < ne}, k G {2,..., e} and H be the numerical semigroup generated by ({n1,..., ne }\{nk}) U {nk + n1}. Then H c P, F(P) < F(H) and g(P) < g(H). We can formulate the following result. Proposition 4.1. If S G C(m, e), P G [S] and (H, P) is an edge of G([S]) then F(P) < F(H) and g(P) < g(H). As a consequence of the previous proposition, we have that if we go along through the branches of the tree G([S]), the numerical semigroups that we are finding have greater or equal Frobenius number, and also a greater genus. This fact enables us to formulate the Algorithms 1 and 3 in order to compute 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, respectively. J. I. Garcia-Garcia et al.: Semigroups with fixed multiplicity and embedding dimension 403 (5, 6, 8) (5, 8, 11) (5, 11, 13) (5, 6, 13) (5, 13, 16) (5, 16, 18) (5, 11, 18) (5, 13, 21) (5, 11, 23) (5, 18, 21) (5, 16, 23) (5, 11, 28) (5, 21, 23) (5, 18, 26) (5, 16, 28) (5, 23, 26) (5, 21, 28) (5, 18, 31) (5, 16, 33) Figure 1: Seven levels of the tree of the packed numerical semigroup (5, 6, 8}. Algorithm 1 An algorithm to determinate the elements T G [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 G [S] | F(T) < F}. 1: if F(S) > F then 2: return 0 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 = 0 then 7: return A 8: A = A U C, B = C. The following example illustrates how the previous algorithm works. Example 4.2. We compute all the elements of [(5,6, 8}] with Frobenius number less than or equal to 25. • A = {(5,6,8}}, B = {(5, 6,8}} and C = {(5,8,11}, (5,6,13}}. • A = {(5,6,8}, (5,8,11}, (5, 6,13}}, B = {(5,8,11}, (5, 6,13}} and C = {(5,11,13}}. 404 Ars Math. Contemp. 17 (2019) 349-368 • A = {(5,6, 8), (5,8,11), (5, 6,13), (5,11,13)}, B = {(5,11,13)} and C = {(5,11,18)}. • A = {(5,6, 8), (5,8,11), (5, 6,13), (5,11,13), (5,11,18)}, B = {(5,11,18)} and C = 0. Therefore, the set {T G [(5, 6,8)] | F(T) < 25} is equal to {(5,6,8), (5, 8,11), (5, 6,13), (5,11,13), (5,11,18)}. The 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 = N then m(S) - 1 G S and then m(S) - 1 < F(S). Algorithm 2 An algorithm to determinate the numerical semigroups with a fixed embedding dimension and multiplicity, 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 2.4. 2: for all S G C(m, e) do 3: compute A(S) = {T g [S] | F(T) < F}, using Algorithm 1. 4: return USec(m,e)A(S). Now, we change Frobenius number by the genus in Algorithm 1 and Algorithm 2. Algorithm 3 An algorithm to determinate the elements T G [S] such that g(T) < g for a fixed integer g. INPUT: (S, g) where S is a packed numerical semigroup and g is a positive integer. OUTPUT: {T G [S] | g(T) < g}. 1: if g(S) > g then 2: return 0 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 = 0 then 7: return A 8: A = A U C, B = C. We illustrate now the above algorithm. Example 4.3. We compute all the elements of [(5,6, 8)] with genus less than or equal to 15. • A = {(5,6, 8)}, B = {(5,6,8)} and C = {(5, 8,11), (5,6,13)}. • A = {(5,6, 8), (5,8,11), (5, 6,13)}, B = {(5,8,11), (5, 6,13)} and C = {(5,11,13)}. • A = {(5,6, 8), (5,8,11), (5, 6,13), (5,11,13)}, B = {(5,11,13)} and C = {(5,11,18)}. J. I. Garcia-Garcia et al.: Semigroups with fixed multiplicity and embedding dimension 405 • A = {(5,6,8), (5,8,11), (5, 6,13), (5,11,13), (5,11,18)}, B = {(5,11,18)} and C = 0. Algorithm 3 returns {(5,6,8), (5,8,11), (5, 6,13), (5,11,13), (5,11,18)}. Note that if S is a numerical semigroup such that S = N then {1,..., m(S) - 1} C N \ S and then m(S) - 1 < g(S). Combining the above results, we obtain Algorithm 4. Algorithm 4 An algorithm to compute 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 2.4. 2: for all S G C (m, e) do 3: compute A(S) = {T g [S] | g(T) < g}, using Algorithm 3. 4: return USec(m,e)A(S). Note that applying Algorithms 1 and 2 we have to compute the Frobenius number and the genus, respectively, of the numerical semigroups we recursively obtain when we build [S]. Results of the next section enable us to easily compute 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 G S \ {0}. The Apery set (named by [1]) of n in S is Ap(S, n) = {s G S | s - n G S}. The next result is a consequence of Lemma 2.4 from [11]. Lemma 5.1. Let S be a numerical semigroup and n G 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 least element in S congruent with i modulo n. The set Ap(S, n) gives us a lot of information of S. The following result is found in [13]. Lemma 5.2. Let S be a numerical semigroup and n G S \ {0}. Then: • F (S) = max(Ap(S, n)) — n. • g(S) = nn (EwEAp(s,n) w) — ^. The following result is a consequence of Lemma 5.1. Lemma 5.3. Let S be a numerical semigroup with minimal system of generators {ni, n2, ..., ne} and Ap(S, n1) = {0, w(1),..., w(n1 — 1)}. Then w(i) = min{a2n2 + • • • + aene | (a2,..., ae) G Ne-i and a2n2 + • • • + aene = i (mod ni)}. 406 Ars Math. Contemp. 17 (2019) 349-368 Note that the set j(a2,..., ae) G Ne-1 | a2n2 + • • • + aene = i (mod ni)} has a finite number of minimal elements (using the usual ordering in Ne-1) by Dickson's Lemma (Theorem 5.1 from [10]). We denote the set of these minimal elements by M((n1,..., ne), i). The following result is obtained from Lemma 5.3. Proposition 5.4. 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{a2n2 + • • • + aene | (a2,. .., ae) G M((n1, .. ., ne), i)}. We illustrate the above proposition with an example. Example 5.5. In this example we try to compute the Apery set of the numerical semigroups of [(5, 6,8}] that we obtained in Example 3.4. For every i G {1, 2, 3,4} let A(i) be the set {(a2, a3) G 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 [(5,6, 8}], for example S = (5, 21,13}, and we want to compute Ap(S, 5) = {0, w(1), w(2), w(3), w(4)}, by applying Proposition 5.4 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 G {1, 2,3,4}. Now, our next goal is to give an algorithm for computing M((n1,..., ne), i). In order to do it, we introduce the following sets: C(1) = {(x2, .. ., Xe) G Ne-1 | n2X2 +-----+ neXe = i (mod n1)}, C (2) = {(x1, X2, ...,Xe) G Ne | (—n1)x1 + n2X2 +-----+ neXe = i}, C(3) = {(X1,X2,...,Xe,Xe+1) G Ne+1 | (—n1)X1 + n2X2 +----+ neXe + (—i)Xe+1 = 0}. Lemma 5.6. If (a2,..., ae) G C(1) then there exists a1 G N such that (a1, a2,..., ae) G C(2). Proof. It is enough to note that if n2a2 + • • • + neae = i (mod n1) then, there exist a1 G N such that n2a2 + • • • + neae = i + a1 n1. □ Thanks to [12] we know that C(3) is a finitely generated submonoid of Ne+1. The next result can be deduced from Lemma 2 of [12]. Lemma 5.7. Let A be the set {a1,..., at} with a = (ai1, ai2,..., aie, aie+1) a system of generators of C(3). If we suppose that a1,..., ad are the elements in A with the last coordinate equal to zero and ad+1,..., aq are the elements of S with the last coordinate equal to 1, then C(2) = { 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, = (m, m +1, ..., 2m - 1). So, as a consequence of Proposition 7.1, we have the following result which is fundamental in this work. Theorem 7.2. The graph G(L(m)) is a tree rooted in (m, m + 1,..., 2m — 1). Moreover, the set formed by the children of a vertex S G L(m) is {S \ {x} | x G msg(S), x > F(S) and x = m}. The previous theorem allows us to recursively construct L(m) from its root by recursively adding its children to the computed vertices. We illustrate this with an example. Example 7.3. We show some levels of the tree G(L(4)) giving its vertices and edges, and the minimal removed generators for obtaining the children. (4, 5, 6, 7) (4,9, 10, 11) (4,7, 10, 13) (4,7, 9) (4,6, 11, 13) (4,6, 9) (4, 5) J. I. Garcia-Garcia et al.: Semigroups with fixed multiplicity and embedding dimension 411 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 G N, we denote by N(k, G) = {v G G | v has level k}. So in Example 7.3 we have: N(0, L(4)) = {(4, 5, 6, 7)}, N(1, L(4)) = {(4, 6, 7, 9), (4, 5, 7), (4, 5, 6)}, N(2, L(4)) = {(4, 7, 9,10), (4, 6, 9,11), (4, 6, 7), (4, 5,11)}, N(3, L(4)) = {(4, 9,10,11), (4, 7,10,13), (4, 7, 9), (4, 6,11,13), (4, 6, 9), (4, 5)}. 8 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 G L(m, e) and g(S) = g(m, e)}. The following result is a consequence of Theorem 7.2. Proposition 8.1. 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 8.2. Let us fix m, e G N. If P = min{k G N | N(k, G(L(m))) n L(m, e) = 0} then {S G L(m, e) | g(S) = g(m, e)} = N(P, G(L(m))) n L(m, e). Moreover, g(m, e) = m — 1 + P. It is clear that if m > e > 2 then (m, m + 1,..., m + e — 1) G L(m, e). In this way, we have the following result. Proposition 8.3. Let m and e be positive integers. 1. If m < e then L(m, e) = 0. 2. If e = 1 and L(m, e) = 0 then m =1 and L(m, e) = {N}. 3. If m > e > 2 then L(m, e) = 0. We now give an algorithm to compute g(m, e) and {S G L(m, e) | g(S) = g(m, e)}. Algorithm 5 An 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 G L(m, e) and g(S) = g(m, e)}. 1: Set k = 0 and A = {(m, m + 1,..., 2m — 1)}. 2: while True do 3: if A n L(m, e) = 0 then 4: return m — 1 + k and A n L(m, e) 5: for S G A do 6: C(S) = {T | T is a child of S}. 7: A = USeA C(S), k = k + 1. 412 Ars Math. Contemp. 17 (2019) 349-368 We illustrate the above algorithm in the following example. Example 8.4. We compute g(5,3) and {S G L(5,3) | g(S) = g(5,3)} using Algorithm 5. • k = 0 and A = {(5,6,7,8, 9)}. • k =1 and A = {(5, 7, 8, 9,11), (5, 6, 8, 9), (5, 6, 7, 9), (5, 6, 7, 8)}. • k = 2 and A = {(5, 8, 9,11,12), (5, 7, 9,11,13), (5, 7, 8,11), (5, 7, 8, 9), (5, 6, 9,13), (5, 6, 8), (5, 6, 7)}. It returns g(5,3) = 6 and {S G L(5,3) | g(S) = 6} = {(5,6,8), (5,6,7)}. In the package FrobeniusNumberAndGenus ([5]), we can run the command ComputeMinimumGenusLme[5,3] to obtain this result. If S is a numerical semigroup, n G S \ {0} and Ap(S, n) = {w(0) = 0, w(1),..., w(n — 1)} (see [11, Lemma 2.4, Lemma 2.6]), then w(i) = kjn + i for some k G N and kn + i G S if and only if k > kj. Therefore, using Lemma 5.2, we have the following (see the proof of [11, Proposition 2.12]). Lemma 8.5. Let S be a numerical semigroup, n G S \ {0} and Ap(S, n) = {0, kin + 1, ..., kn-in + n — 1}. Then g(S) = ki + • • • + kn-i. The next result is easily deduced from Corollary 4 of [6]. Lemma 8.6. Let m, e, q, r be integers such that m > e > 2, S = (m, m+1,..., m+e—1), and m — 1 = q(e — 1) + r, with q, r G 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 G N and b = 0 we denote by a mod b the remainder of dividing a by b. If q is a rational number we denote by |_qj = max{z G Z | z < q}. Note that a = Lf J b + (a mod b). From Lemma 8.5 and Lemma 8.6 we have the following result. Proposition 8.7. Let m and e be integers such that m > e > 2 and S = (m, m +1, ..., m + e — 1). Then, g(S) = m — 1 e - 1 +1 m— i e-1 (e — 1) + (m — 1) mod (e — 1) Clearly (m, m +1, ...,m + e — 1} G L(m, e) and therefore we have the following result. Corollary 8.8. If m and e are integers such that m > e > 2 then g(m,e) < m — 1 e - 1 +1 m— 1 e-1 (e — 1) + (m — 1) mod (e — 1) J. I. Garcia-Garcia et al.: Semigroups with fixed multiplicity and embedding dimension 413 For many examples the equality holds. However, there are some cases where the semigroup (m, m + 1,..., m + e - 1) does not have minimum genus in the set L(m, e) as we show in the next example. Example 8.9. S = (8, 9,10) is a numerical semigroup and g(S) = 16. S = (8,9,11) is a numerical semigroup and g(5) = 14. Therefore, in this case g((8, 9,10)) = g(8, 3). The following result is a consequence from Proposition 2.4. Proposition 8.10. If S G L(m, e) then S = ({m} + {x mod m | x G msg(S)}) G C(m, e) and g(<§) < g(S). Moreover, if S G C(m, e) then g(S) < g(S ). We illustrate the previous proposition with an example. Example 8.11. If S = (5,11,17) G L(5,3) then S = ({5} + {0,1, 2}) = (5,6, 7) G C(5,3). Therefore, g(S) < g(S). Moreover, S G C(5,3), so g(S) < g(S). The next result is a consequence of Proposition 8.10. Corollary 8.12. Let m and e be integers such that m > e > 2. Then 1. g(m, e) = min{g(S) | S G C(m, e)}. 2. {S G L(m, e) | g(S) = g(m, e)} = {S G C(m, e) | g(S) = g(m, e)}. Note that C (m, e) is finite and therefore the previous corollary gives us another algorithm for computing g(m, e) and {S G L | g(S) = g(m, e)}. We give more details about this method using Proposition 2.4 and the calculations which appear in Example 2.5. Example 8.13. From the calculations of Example 2.5, we have C(6, 3) = {(6, 7, 8), (6, 7, 9), (6, 7,10), (6, 7,11), (6, 8, 9), (6, 8,11), (6, 9,10), (6, 9,11), (6,10,11)}. A simple computation shows us g((6, 7, 8)) = 9, g((6, 7, 9)) = 9, g((6, 7,10)) = 9, g((6, 7,11)) = 10, g((6, 8, 9)) = 10, g((6, 8,11)) = 11, g((6,9,10)) = 12, g((6,9,11)) = 13 and g((6,10,11)) = 13. Therefore, g(6, 3) = 9 and the set {S G L(6, 3) | g(S) = 9} is equal to {(6,7, 8), (6,7,9), (6,7,10)}. 9 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 G L(m, e) | F (S) = F (m, e)}. The next result is a consequence of Theorem 7.2. Proposition 9.1. If m is a positive integer and (S, T) is an edge of G(L(m)), then F (T ) < F (S). 414 Ars Math. Contemp. 17 (2019) 349-368 The following result can be deduced from [9]. Proposition 9.2. 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 G L(m, m) | F(S) = m — 1} = {(m, m + 1,.. ., 2m — 1}}. It is well known (see [14] for example) that if S = (ni, n2} is a numerical semigroup, then F(S) = n1n2 - n1 - n2. Therefore, we obtain the following result. Proposition 9.3. Let m be an integer such that m > 2. 1. F(m, m) = m - 1 and {S G L(m, m) | F(S) = m - 1} = {(m, m + 1,..., 2m - 1}}. 2. F(m, 2) = m2 - m - 1 and {S G L(m, 2) | F(S) = m2 - m - 1} = {(m, m +1}}. If q is a rational number we denote by [q] = min{z G Z | q < z}. The next result is deduced from Corollary 5 of [6]. Proposition 9.4. If m and e are integers such that m > e > 2, then m - 1 e - 1 As a consequence of the previous proposition we get the following result. Corollary 9.5. If m and e are integers such that m > e > 2, then m1 F((m, m + 1, .. ., m + e - 1}) m — 1. F(m, e) < m — 1. e - 1 In the previous corollary, equality often holds, but in some cases F((m, m + 1,..., m + e - 1}) = min{F(S) | S G L(m, e)}. For example, F((4,5,6}) = 7 and F((4,5,7}) = 6. From the above results, we obtain the following algorithm where the projections from the cartesian product L(m) x N are denoted by n1 and n2. Algorithm 6 An algorithm to compute F(m, e) and the set of semigroups 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 G L(m, e) | F(S) = F(m, e)}. 1: A = {(m, m + 1,..., 2m - 1}}, I = 0 and a = [^—t]m - 1. 2: while True do 3: C = {(S, F(S)) | S is child of some element of A and F(S) < a}. 4: K = {S G n1(C) | e(S) > e}. 5: if K = 0 then 6: return F(m, e) = ^(Z) and {S G L(m,e) | F(S) = F(m,e)} = ) 7: A = K, B = {(S, F(S)) | S G K and e(S) = e}. 8: a = min(n2(B) U {a}), I = {(S, F(S)) G I U B | F(S) = a}. We illustrate how this algorithm works with an example. J. I. Garcia-Garcia et al.: Semigroups with fixed multiplicity and embedding dimension 415 Example 9.6. We compute F(4, 3) and {S G L(4,3) | F(S) = F(4,3)} using Algorithm 6. • A = {(4,5,6, 7)}, I = 0 and a = \§]4 - 1=7. • C = {((4, 6,7,9), 5), ((4,5, 7), 6), ((4, 5,6), 7)} and K = {(4, 6, 7, 9), (4, 5, 7), (4, 5, 6)}. • A = {(4, 6, 7, 9), (4, 5, 7), (4, 5, 6)}, B = {((4, 5, 7), 6), ((4, 5, 6), 7)}, a = min{6, 7} = 6 and I = {((4, 5, 7), 6)}. • C = {((4, 7,9,10), 6)} and K = {(4,7, 9,10)}. • A = {(4,7,9,10)}, B = 0, a = 6 and I = {((4, 5,7), 6)}. • C = 0 and K = 0. Therefore, F(4,3) = 6 and {S G L(4,3) | F(S) = 6} = {(4,5,7)}. Using the Math-ematica package [5], we obtain 6 and (4, 5, 7), running the commands MinFrob[4,3] and FrobeniusEmbeddingDimensionMultiplicity[6,3,4], respectively. Our next goal is to give an alternative algorithm for computing F(m, e) and {S G L(m, e) | F(S) = F(m, e)}. The next result is deduced from Proposition 2.4. Proposition 9.7. If S G L(m, e) then S = ({m} + {x mod m | x G msg(S)}) G C(m, e) and F(S) < F(S). As a consequence of the previous proposition we get the following result. Corollary 9.8. If m and e are integers such that m > e > 2, then F(m, e) = min{F(S) | S G C(m, e)}. The set C(m, e) is finite, so previous corollary give us an algorithmic method for computing F(m, e). Example 9.9. We compute F(6, 5). First, we calculate C(6, 5) by using Proposition 2.4 and then we apply Corollary 9.8. So, C(6, 5) = {(6, 7, 8, 9,10), (6, 7, 8, 9,11), (6, 7, 8,10,11), (6, 7, 9,10,11), (6, 8, 9,10,11)} and therefore F(6, 5) = min{F((6, 7, 8, 9,10)) = 11, F((6, 7, 8, 9,11)) = 10, F((6, 7, 8,10,11)) = 9, F((6, 7, 9,10,11)) = 8, F((6, 8, 9,10,11)) = 13} = 8. We are now interested in giving a method for computing {S G L(m, e) | F(S) = F(m, e)}. The next example shows us that there exist semigroups S G L(m, e) such that S G C(m, e) and F(S) = F(m, e). Example 9.10. The numerical semigroups Si = (7, 9,10,15) and S2 = (7,8,10,19) verify that Si,S2 G L(7,4) \C(7,4) and F(Si) = F(S2) = 13 = F(7,4). 416 Ars Math. Contemp. 17 (2019) 349-368 If S G L(m, e) we denote by 0(S) the numerical semigroup generated by {m} + {x mod m | x G msg(S)}. Clearly, 0(S) G C(m, e). Using the partition given in Section 2 and Theorem 2.3, the following two steps are sufficient for computing {S G L(m, e) | F(S) = F(m, e)}. 1. Compute A = {S G C(m, e) | F(S) = F(m, e)}. 2. For every S G A, compute {T G [S] | F(T) = F(S)}. We already know how to compute 1. We now focus on giving an algorithm that allows us to compute 2. Using Algorithm 1, for S G C(m, e) and F G N we get the set {T G [S] | F(T) < F}. Clearly if S G C(m,e) then {T G [S] | F(T) = F(S)} = {T G [S] | F(T) < F(S)}. We are going to adapt Algorithm 1 to our needs for computing 2. We now recall some definitions of Section 3. If S is a numerical semigroup, M(S) = max(msg(S)). If S G C(m, e) the graph G([S]) was defined as follows: [S] is its set of vertices and (A, B) g [S] x [S] is an edge if msg(B) = (msg(A) \ {M(A)}) U {M(A) - m}. Now, using the Theorem 3.3, we give an algorithm which for a semigroup S G C(m, e) computes the set {T g [S] | F(T) = F(S)}. Algorithm 7 An algorithm to compute the semigroups of each equivalence class such that their Frobenius number is minimum._ INPUT: S G 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 child of an element of B and F(H) = F(S)}. 4: if C = 0 then 5: return A 6: A = A U C, B = C. We finish this section with an example to illustrate the above algorithm. Example 9.11. We use now Algorithm 7 for computing {T G [S] | F(T) = F(S) = 10} where S = (6,7, 8, 9,11) G C(6, 5). • A = {(6,7, 8, 9,11)} and B = {(6,7,8,9,11)}. • C = {(6, 8, 9,11,13), (6, 8,11,13,15)}. • A = {(6,7, 8, 9,11), (6,8, 9,11,13), (6,8,11,13,15)} and B = {(6, 8, 9,11,13), (6, 8,11,13,15)}. • C = 0. Thus, {T G [S] | F(T) = 10} = {(6, 7, 8, 9,11), (6, 8, 9,11,13), (6, 8,11,13,15)}. This result is also obtained with the package FrobeniusNumberAndGenus ([5]) by executing the command ComputeEquivalenceClass[{6,7,8,9,11}]. J. I. Garcia-Garcia et al.: Semigroups with fixed multiplicity and embedding dimension 417 References [1] R. Apéry, Sur les branches superlinéaires des courbes algébriques, C. R. Acad. Sci. Paris 222 (1946), 1198-1200. [2] V. Barucci, D. E. Dobbs and M. Fontana, Maximality Properties in Numerical Semigroups and Applications to One-Dimensional Analytically Irreducible Local Domains, Memoirs of the American Mathematical Society, American Mathematical Society, Providence, RI, 1997, doi:10.1090/memo/0598. [3] E. Contejean and H. Devie, An efficient incremental algorithm for solving systems of linear Diophantine equations, Inform. and Comput. 113 (1994), 143-172, doi:10.1006/inco.1994. 1067. [4] J. Fromentin and F. Hivert, Exploring the tree of numerical semigroups, Math. Comp. 85 (2016), 2553-2568, doi:10.1090/mcom/3075. [5] J. I. García-García, D. Marin-Aragon and A. Vigneron-Tenorio, FrobeniusNumberAndGenus, a Mathematica package for computations in numerical semigroups, 2019, http://hdl. handle.net/104 98/21658. [6] P. A. García-Sanchez and J. C. Rosales, Numerical semigroups generated by intervals, Pacific J. Math. 191 (1999), 75-83, doi:10.2140/pjm.1999.191.75. [7] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, volume 30 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2005, doi:10. 1093/acprof:oso/9780198568209.001.0001. [8] A. M. Robles-Peírez and J. C. Rosales, Frobenius pseudo-varieties in numerical semigroups, Ann. Mat. PuraAppl. 194 (2015), 275-287, doi:10.1007/s10231-013-0375-1. [9] J. C. Rosales, On numerical semigroups, Semigroup Forum 52 (1996), 307-318, doi:10.1007/ bf02574106. [10] J. C. Rosales and P. A. García-Sanchez, Finitely Generated Commutative Monoids, Nova Science Publishers, Commack, New York, 1999, https://books.google.com/books? id=LQsH6m-x8ysC. [11] J. C. Rosales and P. A. García-Sanchez, Numerical Semigroups, volume 20 of Developments in Mathematics, Springer, New York, 2009, doi:10.1007/978-1-4419-0160-6. [12] J. C. Rosales, P. A. García-Sanchez, J. I. García-García and M. B. Branco, Systems of inequalities and numerical semigroups, J. London Math. Soc. 65 (2002), 611-623, doi: 10.1112/s0024610701003052. [13] E. S. Selmer, On the linear Diophantine problem of Frobenius, J. Reine Angew. Math. 1977 (1977), 1-17, doi:10.1515/crll.1977.293-294.1. [14] J. J. Sylvester, Problem 7382, Educat. Times J. College Preceptors New Ser. 36 (1883), 177. [15] H. S. Wilf, A circle-of-lights algorithm for the "money-changing problem", Amer. Math. Monthly 85 (1978), 562-565, doi:10.2307/2320864. [16] Wolfram Research, Inc., Mathematica, Version 11.2, Champaign, Illinois, 2017, https:// www.wolfram.com/mathematica.