Arithmetic Varieties of Numerical Semigroups

Results Math (2024) 79:171 Online First c 2024 The Author(s) https://doi.org/10.1007/s00025-024-02212-5 Results in Mathematics Arithmetic Varieties of Numerical Semigroups Manuel B. Branco , Ignacio Ojeda ,andJos´e Carlos Rosales Abstract. In this paper we present the notion of arithmetic variety for numerical semigroups. We study various aspects related to these varieties such as the smallest arithmetic that contains a set of numerical semigroups and we exhibit the rooted tree associated with an arithmetic variety. This tree is not locally finite; however, if the Frobenius number is fixed, the tree has finitely many nodes and algorithms can be developed. All algorithms provided in this article include their (non-debugged) implementation in GAP. Mathematics Subject Classification. Primary 20M14, 20M07; Secondary 05C05. Keywords. Numerical semigroup, varieties, rooted tree, Frobenius number, multiplicity, depth. 1. Introduction Let Zbe the set of integer numbers and let Nbe the set of non-negative integer numbers. A submonoid of (N,+) is a subset of Ncontaining 0 that is closed under addition. A numerical semigroup is a submonoid Sof (N,+) such that #(N\S)<∞,thatis,N\Shas finite cardinality. If Sis a numerical semigroup, then m(S) = min(S\{0}),F(S) = max(Z\S) and g(S)=#(N\S) are relevant invariants of Scalled multiplicity,Frobenius number and genus of S, respectively. If Ais a non-empty subset of N, then we write Afor the submonoid of (N,+) generated by A,thatis, A={u1a1+···+unan|n∈N\{0},{a1,...,a n}⊆Aand {u1,...,u n}⊂N}. 0123456789().: V,-vol 171 Page 2 of 17 M. B. Branco et al. Results Math In [18, Lemma 2.1] it is shown that Ais a numerical semigroup if and only if gcd(A)=1. If Mis a submonoid of (N,+) and M=Afor some non-empty subset A of N, then we say that Ais a system of generators of M. Moreover, if M=B for every BA, then we say that Ais a minimal system of generators of M. In [18, Corollary 2.8] it is shown that every submonoid of (N,+) has a unique minimal system of generators which, moreover, is finite. We write msg(M) for the minimal system of generators of M. The cardinality of msg(M)isthe embedding dimension of Mand is the denoted by e(M). The Frobenius problem for numerical semigroups (see [1]) is to find formulas for the Frobenius number and the genus of a numerical semigroup in terms of its minimal system of generators. Nowadays this problem is widely open for numerical semigroups of embedding dimension greater than or equal to three. Let Sand Tbe numerical semigroups. Following the notation introduced in [11], we say that Tis an arithmetic extension of Sif there exist positive integers d1,...,d nsuch that T={x∈N|{d1x, d2x,...,d nx}⊂S}. Notice that, in this case, we have that S⊆T. Definition 1. An arithmetic variety is a non-empty family Aof numerical semigroups such that (a) if {S, T }⊆A, then S∩T∈A; (b) if S∈Aand Tis an arithmetic extension of S, then T∈A. In this case, we say that Ais a finite arithmetic variety when Ahas finite cardinality. Notice that L:= {S⊆N|Sis a numerical semigroup} is an arithmetic variety and F⊆Lfor every family Fof numerical semigroups. In the second section we prove that the intersection of arithmetic varieties is an arithmetic variety (Proposition 3). Moreover, we emphasize that the intersection of all arithmetic varieties containing a given family Fof numerical semigroups is an arithmetic variety, too (Proposition 4). This arithmetic variety is denoted by A(F). We prove that A(F) is finite if and only if F has finite cardinality (Corollary 11). Also, in this case, we give an algorithm (Algorithm 12) to calculate all the elements of A(F). In the third section we introduce the notion of A−monoids and the minimal A−system of generators of a A−monoid, where Ais an arithmetic variety. Also, given e∈N\{0}, we write ED(e) for the set of numeric semigroups of the embedding dimension e. The results of the third section, combined with those of [4], allow us to determine whether a numeric semigroup belongs to Arithmetic Varieties of Numerical Semigroups Page 3 of 17 171 A(ED(2)). We propose the generalization to A(ED(e)) for e≥3asanopen problem. If Sis a numerical semigroup then S 2:= {x∈N|2x∈S}is a numerical semigroup (see [18, Proposition 5.1]); in particular, it is an arithmetic extension of S. We write D2(S) for set of numerical semigroups Tsuch that S=T 2.By [16, Corollary 3], this set is infinite and contains infinitely many symmetric numerical semigroups (see also [19, Theorem 5]). In the fourth section, we show that the elements in an arithmetic variety Acan be arranged in the form of a tree GAwith root Nand such that the set of all the children of S in the tree GAis equal to D2(S)∩A(Theorem 22). Furthermore, we outline the description of D2(S) given in [12] (Theorem 26), because of its usefulness in the following sections. If Ais an arithmetic variety and Fis a positive integer, we define AF:= {S∈A|F(S)≤F}. In the fifth section, we will see that AFis a finite arithmetic variety (Proposition 28); moreover, we give an algorithm (Algorithm 35) to compute {T∈ D2(S)|F(T)≤F}. The depth of a numerical semigroup S, denoted depth(S), is equal to F(S)+1 m(S), where qis the ceiling function (the smallest integer greater than q). The depth of a numerical semigroup was recently introduced in [8] where evidences are given that support the Bras-Amor´os conjecture ( [2]). Also, it is proved that numerical semigroups of depth less than or equal to three are Wilf (see [6] for further details on Wilf’s conjecture). Moreover, following [9, Corollary 21] and the terminology introduced therein, one can see that the complexity of a numerical semigroup is equal to its depth. If q∈N, then we write Cqfor the set of numerical semigroups with depth less than or equal to q. In the sixth section, we prove that Cqis an arithmetic variety (Theorem 39). Furthermore, taking advantage of the results of the third Section, we formulate an algorithm (Algorithm 40) to compute the subset of Cqconsisting of numerical semigroups with Frobenius number F. 2. The Smallest Arithmetic Variety Containing a Family of Numerical Semigroups Let Sbe a numerical semigroup and d∈N\{0}. As mentioned in the introduction, we write S dfor the set {x∈N|dx∈S}.In [18, Proposition 5.1] it is shown that S dis a numerical semigroup. This semigroup is called the quotient of Sby d. Notice that S d=Nif and only if d∈S. Also, by definition, Tis an arithmetic extension of Sif and only if there exists {d1,...,d n}⊂N\{0}such 171 Page 4 of 17 M. B. Branco et al. Results Math that T=S d1∩···∩ S dn. With these remarks, the proof of the following result is straightforward. Proposition 2. Let Abe a non-empty family of numerical semigroups. Then Ais an arithmetic variety if and only if the following hold: (a) if {S, T}⊂A, then S∩T∈A; (b) if S∈Aand d∈N\{0}, then S d∈A. Since all arithmetic varieties contains {N}, we have that the intersection of arithmetic varieties is a non-empty set of numerical semigroups. Proposition 3. The intersection of arithmetic varieties is an arithmetic variety. Proof. Let {Ai}i∈Ibe an arbitrary family of arithmetic varieties. From the previous observation, it follows that N∈∩ i∈IAi.Thus,theset∩i∈IAiis non-empty; let us see that it is an arithmetic variety. On the one hand, if {S, T}⊆∩ i∈IAi, then {S, T}⊆Aifor every i∈I, therefore S∩T∈Ai for every i∈Iand, consequently, S∩T∈∩ i∈IAi. On the other hand, if S∈∩ i∈IAiand d∈N\{0}, then, by Proposition 2, we have that S d∈Ai for every i∈I; hence S d∈∩ i∈IAi. So, applying Proposition 2again, we are done.  Recall that, if Fis a family of numerical semigroups, then we write A(F) to denote the intersection of all arithmetic varieties containing F. Therefore, by Proposition 3, we have the following. Proposition 4. If Fis a family of numerical semigroups, then A(F)is the smallest arithmetic variety containing F. The following result is technical and its proof is carried out by direct verification. Lemma 5. If S, T are numerical semigroups and a, b are positive integers, then S a b=S ab and S∩T a=S a∩T a. Lemma 6. If Sis a numerical semigroup, then A=n  i=1 S di |n∈N\{0}and {d1,...,d n}⊂N\S∪{N} is an arithmetic variety containing {S}. Proof. Clearly, the intersection of any two elements in Abelongs to Aand, by Lemma 5, we have that S d∈Afor every S∈Aand d∈N\{0}. Thus, by Proposition 2,Ais an arithmetic variety. Moreover, since S=S 1, we conclude that {S}⊆A. Arithmetic Varieties of Numerical Semigroups Page 5 of 17 171 Proposition 7. If Sis a numerical semigroup, then A({S})=n  i=1 S di |n∈N\{0}and {d1,...,d n}⊂N\S∪{N}.(1) Proof. Let Abe the right hand side of (1) and let Abe an arithmetic variety containing {S}.From Proposition 2it follows that A⊆A. Therefore, by Lemma 6, we have that Ais the smallest arithmetic variety containing {S}. Now, by Proposition 4, we conclude that A=A({S}).  The following result is an immediate consequence of Propositions 2and 7(see also [11, Proposition 1]). Corollary 8. If Sis a numerical semigroup, then A({S})={T∈L|Tis an arithmetic extension of S}. Proposition 9. If Sis a numerical semigroup, then A({S})is a finite arithmetic variety. Proof. By Proposition 4, we have that A({S}) is an arithmetic variety and, by Proposition 7, we have that A({S})⊆F:= {T∈L|S⊆T}.Now,since N\Shas finite cardinality, because Sis a numerical semigroup, we conclude that Fis a finite set and our claim follows.  Notice that, by Proposition 7, we can use Algorithm 23 in [11] to compute A({S})fromS. Theorem 10. If Fis a non-empty family of numerical semigroups, then A(F)=n  i=1 Ti|n∈N\{0}and Ti∈A({Si})for some Si∈F,i=1,...,n . (2) Proof. Let Abe the right hand side of (2). Clearly, we have that F⊆A⊆A, for every arithmetic variety Acontaining F. Thus, by Proposition 4,tosee that A(F)=Ait suffices to prove that Ais an arithmetic variety. Of course, if {S, T}⊆A, then S∩T∈Aand, by Lemma 5, it is easy to check that S d∈A, for every S∈Aand d∈N\{0}. Therefore, by Proposition 2,we conclude that Ais an arithmetic variety.  Corollary 11. Let Fbe a family of numerical semigroups. Then A(F)is a finite arithmetic variety if and only if Fhas finite cardinality. Now, by combining [11, Algorithm 23] and Theorem 10, we obtain an algorithm to compute A(F), provided that Fis a finite family of numerical semigroups. Algorithm 12. Computation of A(F). Input: A finite set F={S1,...,S n}of numerical semigroups. Output: A(F). 171 Page 6 of 17 M. B. Branco et al. Results Math (1) Set A(F)={N}. (2) For each i∈{1,...,n},setAi=A({Si}). (3) For each (T1,...,T n)∈A1×···×An,do A(F)=A(F)∪{T1∩···∩Tn}. (4) Return A(F). Example 13. Let F={2,5,3,5,7}.By[11, Algorithm 23], we have that A({2,5} ={N,2,3,2,5} and that A({3,5,7} ={N,2,3,3,4,5,3,5,7}. Therefore, by Algorithm 12, we conclude that A(F)={N,2,3,2,5,3,4,5,3,5,7,4,5,6,7,5,6,7,8,9}. The function ArithmeticExtensions, given by the second and third authors in [11, pp. 3714–3715], uses the package NumericalSpgs ([7]) of GAP ([20]) to calculate A({S}) with Sbeing a numerical semigroup. Therefore, by Algorithm 12, we can compute A(F), with Fbeing a family of numerical semigroup, by the following code: SmallestArithmeticVariety:=function(F) local AF,A,S; AF:=[NumericalSemigroup(1)]; A:=[]; forSinFdo Append(A,[ArithmeticExtensions(S)]); od; Append(AF,List(Cartesian(A),i->Intersection(i))); return Set(AF); end; For example, if F={2,5,3,5,7} we write F:=[[2,5],[3,5,7]]; F:=List(F,i->NumericalSemigroup(i)); SmallestArithmeticVariety(F); provided that the package NumericalSgps and the function Arithmetic Extensions have already been loaded into GAP. 3. A-System of Generators Throughout this section, Adenotes an arithmetic variety. By Proposition 2, the intersection of finitely many elements in Ais an element of A. This does not occur at the intersection of infinitely many elements, as the following example evidences. Arithmetic Varieties of Numerical Semigroups Page 7 of 17 171 Example 14. The set A={{0,n,n+1,...}|n∈N\{0}} is an arithmetic variety; however, n∈N\{0}{0,n,n+1,...}={0} ∈ A. Despite the previous example, the arbitrary intersection of elements in Ais always a submonoid of (N,+). This fact gives meaning to the following definition. Definition 15. Given an arithmetic variety A.AnA−monoid is a submonoid of (N,+) that can be written as an intersection of elements of A. Thus, given X⊆N, we have that the intersection of all elements in Acontaining Xis the smallest A−monoid containing Xthat we denote by A[X]. Now, if Mis an A−monoid such that M=A[X], then we say that X is a A−system of generators of M. Moreover, if M=A[Y], for every YX, then we say that Xis a minimal A−system of generators of M. Let us see that there are A−monoids having non-unique minimal A– systems of generators, for a given arithmetic variety A; but let us first recall the notion of fundamental gap and a result from [11]. Definition 16. Let Sbe a numerical semigroup. An element x∈N\{S}is a fundamental gap of Sif {kx|k∈N\{1}} ⊆ S. We write FG(S) for the set of fundamental gaps of S. By Corollary 8, the following result is nothing more than a reformulation of [11, Proposition 6], we include it here for complete exposition and ease of reading. Proposition 17. If S=Nis a numerical semigroup, then the following hold: (a) max⊆(A({S})) = N, (b) min⊆(A({S})) = S, (c) max⊆(A({S})\{N})=2,3, (d) min⊆(A({S})\{S})=S∪FG(S). Corollary 18. Let S=Nbe a numerical semigroup. Then A({S})[{x}]= S∪FG(S), for every x∈FG(S). Proof. If x∈FG(S), then x∈ S. So, by Proposition 17, the smallest element of A({S}) that contains {x}is S∪FG(S).  Example 19. Let S=5,7,9. By direct computation, one can check that FG(S)={6,8,11,13}. Therefore, by Corollary 18, we have that {6},{8},{11} and {13}are minimal A({S})−systems of generators of S∪FG(S)=5,6,7, 8,9. Despite the previous example, there are arithmetic varieties, A,inwhich all A−monoids have unique minimal A−system of generators. To show one of them, we first recall several notions and results on proportionally modular numerical semigroups and their generalizations. 171 Page 8 of 17 M. B. Branco et al. Results Math Let a, b and cbe positive integers. If ax mod bdenotes the remainder of the Euclidean division of ax by b, the set {x∈N|ax mod b≤cx} is a numerical semigroup called proportionally modular numerical semigroup (see [13,14] for more details). Recall that ED(e)={S∈L|e(S)=e}is the set of numerical semigroups of embedding dimension e. The following results follow from [4,Proposition 41] and [4, Theorem 12], respectively. Proposition 20. The arithmetic variety A(ED(2)) is equal to the set of intersections of finitely many proportionally modular numerical semigroups. Corollary 21. Every A(ED(2))−monoid has a unique minimal A(ED(2))– system of generators. We finish this section by recalling and proposing some open problems. Some Open Problems In [15, Theorem 5], it is proved that a numerical semigroup is proportionally modular if and only if it is the quotient of a numerical semigroup of embedding dimension 2 by a positive integer. So, [17, Theorem 31] provides an algorithm to decide whether a numerical semigroup belongs to S d|S∈ED(2) and d ∈N\{0}. In [5], the problem of finding a numerical semigroup that cannot be written as the quotient of a element of ED(3) by a positive integer is proposed. In [10], it is proved its existence; however no example is given. Recently, in [3], some examples are exhibited. Have an algorithm to decide whether a numerical semigroup belongs to S d|S∈ED(3) and d∈N\{0}is still an open problem. By Proposition 20 and the results in [4], one can deduce an algorithm to decide whether a numerical semigroup belongs to A(ED(2)). We propose as an open problem to formulate the corresponding algorithm for A(ED(3)) and, being optimistic, for A(ED(e)),e≥4. 4. The Tree Associated with an Arithmetic Variety If Ais an arithmetic variety, then we define the directed graph GA,whose vertex set is A,havinganedgefromT∈Ato S∈A\{N}if and only if T=S 2; equivalently, such that the set of children of S∈A\{N}is D2(S)∩A, where D2(S)={T∈L|S=T 2}. Theorem 22. If Ais an arithmetic variety, then GAis a directed rooted tree with root N. Arithmetic Varieties of Numerical Semigroups Page 9 of 17 171 Proof. Recall that a directed rooted tree is a directed graph such that for each vertex there is a unique directed path from or towards a single vertex called root. First, we notice that GAhas no loops. Indeed, if S=N, then F(S)∈S 2 which implies SS 2. Now, given S∈A\{N}, consider the sequence {Sn}n∈N such that S0=Sand Sn+1 =Sn 2,for every n∈N. Since, by Lemma 5, Sn=S 2n,wehavethatSn∈A, for every n∈N, by Proposition 2.Moreover, since SnSn+1, whenever Sn=Nand N\Shas finite cardinality, we conclude that there exists k∈Nsuch that Sk=Nand Sk−1Sk.Thisprovesthe existence of a directed path in GAfrom Nto S∈A, the uniqueness follows by the own definition of GA. In [16], it is shown that D2(S) is an infinite set for every S∈L\{N} which implies that GAis not locally finite. Therefore, it is not possible to give a general algorithm for the computation of the tree GAstarting from the root nor from any other parent. Nevertheless, according to [12, Theorem 7], one can describe what the elements of D2(S) are like in terms of the so-called upper m−-sets of S.Let us remember this construction, which will be useful in the next sections. First of all, we notice that D2(N)={2,2n+1|n∈N}. So, we only need to describe D2(S)forS=N. Definition 23. Let SNbe a numerical semigroup and let mbe an odd element of S.Anupper m−set of Sis a subset Hof N\Ssuch that (C1) {h+m|h∈H}⊆S; (C2) {h1+h2+m|h1,h 2∈H}⊆S; (C3) h∈H=⇒{x∈N\S|x−h∈S}⊆H. Given a triplet (S, m, H), where S=Nis a numerical semigroup, mis an odd element of Sand H⊆N\S, the following the GAP function decides whether His an upper m−set of S. IsUppermSetOfNumericalSemigroup:=function(S,m,H) local C1,C2,C3,h; C1:=Intersection(H+m,Gaps(S)); if IsEmpty(C1) = false then return(false); fi; C2:=Intersection(Set(Cartesian(H,H),i->Sum(i)+m),Gaps(S)); if IsEmpty(C2) = false then return(false); fi; forhinHdo C3:=Filtered(Gaps(S),i->BelongsToNumericalSemigroup(i-h,S)); if not(Intersection(C3,H)=C3) then return(false); fi; od; return(true); end; 171 Page 16 of 17 M. B. Branco et al. Results Math Open Access. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons. org/licenses/by/4.0/. References [1] Alfons´ın, J.L.R.: The Diophantine Frobenius problem. Oxford Lecture Ser. Math. Appl., 30. Oxford University Press, Oxford (2005) [2] Amor´os, M.B.: Fibonacci-like behavior of the number of numerical semigroups of a given genus. Semigroup Forum 76(2), 379–384 (2008) [3] Bogart, T., O’Neill, C., Woods, K.: When is a numerical semigroup a quotient. Bull. Aust. Math. Soc. (2024). https://doi.org/10.1017/S0004972723000035 [4] Delgado, M., S´anchez, P.A.G., Rosales, J.C., Blanco, J.M.U.: Systems of proportionally modular Diophantine inequalities. Semigroup Forum 76(3), 469–488 (2008) [5] Delgado, M., S´anchez, P.A.G., Rosales, J.C.: Numerical semigroups problem list. CIM Bull. 33, 15–26 (2013) [6] Delgado, M.: Conjecture of Wilf: A Survey. In: Semigroups, Numerical (ed.) Springer INdAM Series, vol. 40, pp. 39–62. Cham, Springer (2020) [7] Delgado, M., S´anchez, P.A.G., Morais, J.: NumericalSgps, A package for numerical semigroups, Version 1.3.1 (2022). Available at https://gap-packages.github. io/numericalsgps [8] Eliahou, S., Fromentin, J.: Gapsets and numerical semigroups. J. Combin. Theory Ser. A 169, 105129 (2020) [9] Garc´ıa-Garc´ıa, J.I., Moreno-Fr´ıas, M.A., Rosales, J.C., Vigneron-Tenorio, A.: The complexity of a numerical semigroup. Quaest. Math. 46(9), 1847–1861 (2023) [10] Moreno, M.A., Nicola, J., Pardo, E., Thomas, H.: Numerical semigroups that are not intersections of d−squashed semigroups. Can. Math. Bull. 52(4), 598–612 (2009) [11] Ojeda, I., Rosales, J.C.: The arithmetic extensions of a numerical semigroup. Commun. Algebra 48(9), 3707–3715 (2020) [12] Robles-P´erez, A.M., Rosales, J.C., Vasco, P.: The doubles of a numerical semigroup. J. Pure Appl. Algebra 213(3), 387–396 (2009) [13] Rosales, J.C., S´anchez, P.A.G., Garc´ıa-Garc´ıa, J.I., Blanco, J.M.U.: Proportionally modular Diophantine inequalities. J. Number Theory 103(2), 281–294 (2003) Arithmetic Varieties of Numerical Semigroups Page 17 of 17 171 [14] Rosales, J.C., S´anchez, P.A.G., Blanco, J.M.U.: Modular Diophantine inequalities and numerical semigroups. Pacific J. Math. 218(2), 379–398 (2005) [15] Rosales, J.C., Blanco, J.M.U.: Proportionally modular Diophantine inequalities and full semigroups. Semigroup Forum 72(3), 362–374 (2006) [16] Rosales, J.C., S´anchez, P.A.G.: Every numerical semigroup is one half of a infinitely many symmetric numerical semigroup. Commun. Algebra 36, 2910–2916 (2008) [17] Rosales, J.C., S´anchez, P.A.G., Blanco, J.M.U.: The set of solutions of a proportionally modular Diophantine inequality. J. Number Theory 128(3), 453–467 (2008) [18] Rosales, J.C., S´anchez, P.A.G.: Numerical semigroups, Developments in Mathematics, Vol. 20, Springer, New York (2009) [19] Swanson, I.: Every Numerical Semigroup is One Over dof Infinitely Many Symmetric Numerical in Commutative Algebra and its Applications, pp. 383–386. Walter de Gruyter GmbH & Co. KG, Berlin (2009) [20] The GAP Group. GAP—Groups, Algorithms, and Programming, Version 4.12.2; (2022). https://www.gap-system.org Manuel B. Branco Departamento de Matem´aticas Universidade de ´ Evora 7000-671 ´ Evora Portugal e-mail: [email protected] Ignacio Ojeda Departamento de Matem´aticas Universidad de Extremadura 06071 Badajoz Spain e-mail: [email protected] Jos´e Carlos Rosales Departamento de ´ Algebra Universidad de Granada 18010 Granada Spain e-mail: [email protected] Received: November 23, 2023. Accepted: May 7, 2024. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.