On the computation of the Apéry set of numerical monoids and affine semigroups

arXiv:1907.01222v1 [math.CO] 2 Jul 2019 ON THE COMPUTATION OF THE AP´ ERY SET OF NUMERICAL MONOIDS AND AFFINE SEMIGROUPS GUADALUPE M´ ARQUEZ–CAMPOS, IGNACIO OJEDA, AND JOS´ E M. TORNERO Abstract. A simple way of computing the Ap´ery set of a numerical semigroup (or monoid) with respect to a generator, using Groebner bases, is presented, together with a generalization for affine semigroups. This computation allows us to calculate the type set and, henceforth, to check the Gorenstein condition which characterizes the symmetric numerical subgroups. 1. Introduction The most elementary structure this paper deals with is that of numerical monoid. A numerical monoid is a very special kind of semigroup that can be thought of as a set ha1, ..., aki={λ1a1+... +λkak|λi∈Z≥0},with gcd(a1, ..., ak) = 1. This object has been thoroughly studied in the last years, when a significant number of problems concerning the description of these semigroups and some of their more interesting invariants have been tackled. Unless otherwise stated, all proofs which are not included can be found in [9, 15]. Given a numerical monoid S, there are some invariants which will be of interest for us. The most relevant will be the set of gaps, noted G(S), and defined by G(S) = Z≥0\S, which is a finite set. Its cardinal will be noted g(S) and its maximumm, noted f(S), is called the Frobenius number of S. The Ap´ery set of S[2] with respect to an element s∈Scan be defined as Ap(S, s) = {0, w0, ..., ws−1} where wiis the smallest element in Scongruent with imodulo s. This set has some highly interesting properties, which we will review now. Lemma 1. With the previous notations, for all s∈S, Ap(S, s) = {x∈S|x−s /∈S} Example 1.1. Let S=h7,9,11,15i. Some of the Ap´ery sets associated to its generators are: Ap(S, 7) = {0,9,11,15,20,24,26} Ap(S, 15) = {0,7,9,11,14,16,18,20,21,23,25,27,28,32,34} In particular, for a monoid with two generators, the Ap´ery sets associated to its generators are fully determined. Date: July 3, 2019. 2010 Mathematics Subject Classification. Primary: 20M13, 11–04; Secondary: 05E40. Key words and phrases. Numerical semigroups, affine semigroups, numerical monoids, Ap´ery set, type set, Gorenstein condition, Groebner bases. First and third authors were partially supported by the grant FQM–218 and P12–FQM–2696 (FEDER and FSE). The second author is partially supported by the project MTM2012-36917- C03-01, National Plan I+D+I and by Junta de Extremadura (FEDER funds). 1 2 GUADALUPE M ´ ARQUEZ–CAMPOS, IGNACIO OJEDA, AND JOS´ E M. TORNERO Lemma 2. Let S=ha1, a2i. Then Ap(S, ai) = {0, aj,2aj, ..., (ai−1)aj} The importance of the Ap´ery set can be illustrated in the following result, where the previous numerical invariants of a numerical monoid are expressed in terms of Ap´ery sets. Proposition 3. Let Sbe a monoid, s∈S. Then: f(S) = max Ap(S, s)−s, g(S) = 1 sX w∈Ap(S,s) w+s−1 2. This expression of g(S) in terms of the Ap´ery set is known as Selmer’s formula. Our first purpose is to develop an easy algorithm to compute the Ap´ery set of a Sassociated to any of its generators. As it turns out, these are the most interesting ones. We will do that with the help of Groebner bases with respect to some monomial orderings, and more specifically in terms of the characterization of elements in (respectively, out) a monoid in terms of these bases. This characterization can be found in [12], but we will review it in the second section of the paper for the convenience of the reader (Theorem 5). It will be extensively used in the sequel as it provides an easy (not necessarily in complexity terms) and versatile characterization of elements in (or not in) S, with a quite wide choice of monomial orderings. After that, in the third section, we show how to compute (and see) the Ap´ery set associated to the generators (Theorem 6). We are interested not only on the computation, but also on the variety of choices we can make for the orderings. This will be the most important feature in the sequel. The computation can be generalized to a wider class of semigroups: the affine semigroups. This will be done in the fourth section of the paper at the cost of being more restrictive with the orderings. The computation of the Ap´ery set will prove useful in order to study a related concept: the set of pseudo–Frobenius elements (PF(S)) and the type set. We will explore this relationship in the fifth section. Precisely, if we consider, for a given S=ha1, ..., aki, with a1<···< ak, its type set T(S) = {m∈Ap(S, ak)|m+ai/∈Ap(S, ak),∀i= 1, ..., k}, then we have [13, 10] g(S) = 1 2(f(S) + 1) ⇐⇒ #T(S) = 1. This condition (#T(S) = 1) always holds for monoids with two generators [18], but in general it is not so. The condition is subsequently known as the Gorenstein condition. Concerning this, we will show how we can compute the type set by calculating the Ap´ery set Ap(S, ak) for a variety of monomial orderings (Theorem 15). We will end with a word on pseudo–Frobenius elements and how they are related with more complex algebraic structures which can be defined from S. Finally, something should be said on previous work. The Ap´ery set has been thoroughly studied in the literature [4, 5, 16, 11, 17] but its computation has not been treated so often. The work by P. Pis´on–Casares [14] used a technique close to Groebner bases (although the orderings used there were not strictly monomial orderings) to compute Ap´ery sets in the context of affine semigroups. Our third and fourth section are actually a twist of her arguments, in order to use monomial orderings. ON THE COMPUTATION OF THE AP´ ERY SET 3 In particular, our main result in section 3 (generalized in section 4) is included anyway, both for the convenience of the reader and also because it provides a detailed description of the several orderings that we can consider. This will be the most important thing in section 6 and hopefully in future applications. 2. The Groebner correspondence All the general results referred to the general theory of Groebner bases that we will use can be found in standard textbooks on the subject; for instance in [1, 6]. We will work in the polynomial ring Q[x, y1, ..., yk]. Given a polynomial g=X α=(α0,...,αk)∈Zk+1 ≥0 aαxα0yα1 1...yαk k∈Q[x, y1, ..., yk], and a monomial ordering ≺, define exp(g) = max ≺α|aα6= 0∈Zk+1 ≥0. Let then S=ha1, ..., aki ⊂ Z≥0be a numerical monoid. Consider the following binomial ideal associated to S: IS=hy1−xa1, y2−xa2, y3−xa3, ..., yk−xaki ⊂ Q[x, y1, ..., yk]. As ISis a binomial ideal (i.e., it can be generated by binomials), it has a lot of special properties [8]. In particular we are interested in the following ones: •A reduced Groebner basis of ISconsists of binomials. •The normal form of a monomial with respect to a reduced Groebner basis of ISis again a monomial. So, consider ISand let B={g1, ..., gr}be the reduced Groebner basis of ISwith respect to ≺, an elimination ordering for x, and NBthe normal form with respect to B. Let us write also: qi= exp≺(gi)∈Zk+1 ≥0, Kqi=qi+Zk+1 ≥0, E (IS) = r [ i=1 Kqi⊂Zk+1 ≥0. A preliminary elementary result is: Lemma 4. Let e φbe the ring homomorphism defined by: e φ:Q[x, y1, y2, ..., yk]−→ Q[x] yj7−→ xaj x7−→ x Then ker e φ=IS. Therefore NB(g) = NB(h)⇐⇒ g−h∈ker e φ⇐⇒ e φ(g) = e φ(h). The main result in [12] goes as follows: Theorem 5. With the previous notations, let E(IS) = Zk+1 \E(IS). Then: •The mapping F:G(S)−→ E(IS)\ {x= 0} ⊂ Zk+1 ≥0 N7−→ exp NBxN is bijective. 4 GUADALUPE M ´ ARQUEZ–CAMPOS, IGNACIO OJEDA, AND JOS´ E M. TORNERO •The mapping G:S−→ E(IS)\{x= 0} ⊂ Zk+1 ≥0 M7−→ exp NBxM is bijective. Furthermore, for any l∈Z≥0, if NBxl= (σ0, σ1, ..., σk), then l=σ0+σ1a1+... +σkak. So the mapping l7−→ NBxlseparates the non–negative integers into (or out of) E(IS)∩ {x= 0}, depending on whether they are in Sor not. Example 2.1. Let us consider an example of dimension 3(taken from [12]). Let S=h7,9,11i. The Frobenius number of this numerical semigroup is: f(S) = 26, and its set of gaps: G(S) = {1,2,3,4,5,6,8,10,12,13,15,17,19,24,26}. We can take the binomial ideal: IS=hy1−x7, y2−x9, y3−x11i ⊂ Q[x, y1, y2, y3] and find the Groebner basis B, using an elimination ordering for x. For this example, we have taken the usual lexicographic ordering x > y1> y2> y3. With this particular choice we get: B=y11 2−y9 3,−y2 2+y3y1, y9 2y1−y8 3, y7 2y2 1−y7 3, y5 2y3 1−y6 3, y3 2y4 1−y5 3, y5 1y2−y4 3,−y2y3 3+y6 1,−y2y2 1+y2 3x, −y3 1+y3y2x, y3 2x−y4 1, y2 2y2 1x−y3 3,−y2 3+y3 1x, y2x2−y3, y1x2−y2, y3x3−y2 1,−y1+x7. We have to consider then, qi= exp(gi)where giis the i–th polynomial in B, and take the corresponding set Kqi=qi+Zk+1 ≥0⊂Zk+1 ≥0, in order to establish our bijections Fand G. In this case, q1= (0,0,11,0), q2= (0,1,0,1), q3= (0,1,9,0), q4= (0,2,7,0), q5= (0,3,5,0), q6= (0,4,3,0), q7= (0,5,1,0), q8= (0,6,0,0), q9= (1,0,0,2), q10 = (1,0,1,1), q11 = (1,0,3,0), q12 = (1,2,2,0), q13 = (1,3,0,0), q14 = (2,0,1,0), q15 = (2,1,0,0), q16 = (3,0,0,1), q17 = (7,0,0,0) Let us have a closer look to F, so we are only interested in points of E(I)outside x= 0. In order to represent the points, we will consider the subcases x=λ, with λ∈Z≥0. We have then: •x= 1. In this hyperplane we find several corners qi, precisely q9= (0,0,2), q10 = (0,1,1), q11 = (0,3,0), q12 = (2,2,0), q13 = (3,0,0) These points determine the elements of E(IS)⊂Z4 ≥0, along with the point (1,1,0,1) ∈Kq2. In the following pictures we will draw square points for points in ∪Kqiand round points for points outside ∪Kqi, thus associated with a unique element of G(S)by means of F: ON THE COMPUTATION OF THE AP´ ERY SET 5 •At x= 2 these are the points which determine the set: q14 = (0,1,0), q15 = (1,0,0),(0,0,2) ∈Kq9 •At x= 3, we have these points in ∪Kqi q16 = (0,0,1),(1,0,0) ∈Kq15 ,(0,1,0) ∈Kq14 •At x= 4,x= 5 and x= 6, the only relevant point is the origin, as yi<1 for i= 1,2,3. •Last, in x= 7 we have (7,0,0,0) = q17, so this is, so to speak, the ceiling for variable x. 6 GUADALUPE M ´ ARQUEZ–CAMPOS, IGNACIO OJEDA, AND JOS´ E M. TORNERO If we compute the normal form of monomials xni, where niis the i–th gap, we get: NB(x1) = x NB(x2) = x2NB(x3) = x3 NB(x4) = x4NB(x5) = x5NB(x6) = x6 NB(x8) = xy1NB(x10) = xy2NB(x12) = xy3 NB(x13) = x2y3NG(x15) = xy2 1NB(x17) = xy1y2 NB(x19) = xy2 2NB(x24) = xy2 1y2NB(x26) = xy1y2 2 3. Computation of the Ap´ ery set: the numerical case Consider the polynomial ring Q[x, y1, ..., yk], and let us define an elimination ordering for x, written ≺j, as follows: (1) First, we take into account the exponent on x. (2) After that, we take a graded ordering in {y1, ..., yk}leaving aside yj, and determined by the generators a1, ..., ak, that is, we order by i=k X i=1,i6=j αiai, where αiis the exponent on yi. (3) Then we use any monomial ordering for all variables yi, where i= 1, ..., k and i6=j. (4) Finally, we use the exponent on yj. We will call such an ordering an Ap´ery ordering (with respect to aj). Example 3.1. If one wants to use the matrix notation for the ordering, an example of ≺jwill be given by1              1 0 0 ... (j+1) z}|{ 0... 0 0a1a2... 0... ak 0 1 0 ... 0... 0 0 0 1 ... 0... 0 . . .. . .. . .. . .. . . 0 0 0 ... 0... 1 0 0 0 ... 1... 0              This will be precisely the matrix of the Ap´ery ordering we should use if we consider in (3) the lexicographic ordering y1< ... < yj−1< yj+1 < ... < yk. Let S=ha1, ..., akibe a numerical monoid with ai6= 0, and the ideal ISdefined as in the previous section. Let Bjbe the reduced Groebner basis of ISwith respect to ≺j, and let us write Njthe normal form with respect to this basis. We define the following set: ∆≺j(S, aj) = nN∈Z≥0|exp NjxN∈ {x=yj= 0} ∩ E(IS)o. The important result in this section is the following: Theorem 6. ∆≺j(S, aj) = Ap(S, aj). 1Note that, if one needs a square matrix, as some computer algebra packages do, one can always add a numb variable or erase a row between the 3rd and the (k+ 1)–th. ON THE COMPUTATION OF THE AP´ ERY SET 7 Proof. Let us show first Ap(S, aj)⊆∆≺j(S, aj). Let n∈Ap(S, aj) other than 0 (as the zero case is trivial), which implies n∈Sand n > aj. There are x1, ..., xk∈Z≥0 such that n= k X i=1 aixi and, being in the Ap´ery set, we already know n−aj/∈S. We want to prove exp (Nj(xn)) ∈ {x= 0} ∩ {yj= 0}. But the exponent lies in {x= 0}from Theorem 5. Let us write exp (Nj(xn)) = (γ1, γ2, ..., γk). From the expression above n−aj=a1γ1+... +ajγj+... +akγk−aj =a1γ1+... +aj(γj−1) + ... +akγk. As n−aj∈G(S), the above expression must have a strictly negative coefficient. As γi∈Z≥0for i= 1, ..., k; it must be (γj−1) /∈Z≥0and therefore γj= 0, as we wanted to show. Let us prove now ∆≺j(S, aj)⊆Ap(S, aj), so take n∈∆≺j(S, aj). From the definition of ∆≺j(S, aj) we know n∈Sand exp (Nj(xn)) ∈ {yj= 0} ∩ {x= 0}. Hence there must exist γ1, ..., γj−1, γj+1, ..., γk∈Z≥0, such that Nj(xn) = yγ1 1...yγj−1 j−1·yγj+1 j+1 ...yγk k, which, from Theorem 5 yields n=γ1a1+...γj−1aj−1+γj+1aj+1 +... +γkak. Let us assume n /∈Ap(S, aj). So, either n /∈S(which is impossible as n∈ ∆≺j(S, aj)) or n > ajand besides n−aj∈S. Then there are α1, ..., αk∈Z≥0verifying n−aj= k X i=1 aiαi, that is, n= k X i=1,i6=j aiαi+aj(αj+ 1). So we have two expressions for n, and n=a1γ1+... +aj−1γj−1+aj+1γj+1 +... +akγk =a1α1+... +aj(αj+ 1) + ... +akαk, which yields k X i=1,i6=j ai(αi−γi) + aj(αj+ 1) = 0.(∗) From Lemma 4 and the definition of (γ1, ..., γk), yγ1 1·... ·yγj−1 j−1·yγj+1 j+1 ·... ·yγk k=Nj(xn) = Njyα1 1·... ·yαj+1 j·... ·yαk k 8 GUADALUPE M ´ ARQUEZ–CAMPOS, IGNACIO OJEDA, AND JOS´ E M. TORNERO So, as the normal form of a monomial must be a monomial, we know that (0, γ1, ..., γj−1,0, γj+1, ..., γk)≺j(0, α1, α2, ..., αk) which implies k X i=1,i6=j γiai≤ k X i=1,i6=j αiai=⇒ k X i=1,i6=j ai(αi−γi)≥0. This contradicts (∗), as aj(αj+ 1) must be positive.  Note that our assumptions on the monomial ordering are in fact quite sparse. This will give us a lot of elbow room to work with, and we will take advantage of this fact. Corollary 7. The set ∆≺(S, aj)does not depend on the choice of ≺(as long as it is an Ap´ery ordering). Example 3.2. Let S=h7,8,9,13i. We have IS=y1−x7, y2−x8, y3−x9, y4−x13⊂Q[x, y1, y2, y3, y4], For this monoid we have G(S) = {1,2,3,4,5,6,10,11,12,19 } and Ap(S, 13) = {0,7,8,9,14,15,16,17,18,23,24,25,32 }, T ={32 }. Let us take an Ap´ery ordering ≺1, taking the lex ordering y1< y2< y3in step (3). The Groebner basis is B1=nx7−y1, x4y3−y4, x2y2 3−y1y4, xy2−y3, xy1−y2, xy4−y2 1, y5 2−y2 1y2 4, y3 2y3−y1y2 4, y1y3 2−y2 3y4, y3 3−y2 1y4, y2y2 3−y2 4, y2 1y2−y3y4, y3 1−y2y4, y1y3−y2 2o. Let us compute ∆≺1(S, 13). In order to do that let us draw in {x=y4= 0}the integer corresponding by G−1to each element (0, α1, α2, α3,0) (that is, 7α1+ 8α2+ 9α3). The shadowed regions in the picture below are precisely E(IS)∩{x=y4= 0} (the horizontal axis is y1, the vertical is y2). At y3= 0 On the other hand, at y3= 1 ON THE COMPUTATION OF THE AP´ ERY SET 9 Finally, at y3= 3 That is, as expected, ∆≺3(S, 13) = {0,7,8,9,14,15,16,17,18,23,24,25,32 }. Mind that, although the set ∆≺j(S, aj)does not depend on the chosen ordering for {y1, ..., yk} \ {yj}, the actual arranging of the integers inside ∆≺j(S, aj)might well depend. In the same example, consider now in the step (3) the ordering ≺2, taking the lex ordering y2< y3< y1in step (3). The Groebner basis is B2=nx7−y1, x4y3−y4, x2y2 3−y1y4, xy2−y3, xy1−y2, xy4−y2 1, y3 3−y2 1y4, y2y2 3−y2 4, y2 1y2−y3y4, y3 1−y2y4, y2 2−y1y3o. Then the picture of ∆≺3(S, 13) is, at x=y4=y3= 0, At x=y4= 0, y3= 1, And at last, at x=y4= 0, y3= 2, 16 GUADALUPE M ´ ARQUEZ–CAMPOS, IGNACIO OJEDA, AND JOS´ E M. TORNERO [16] Ram´ırez–Alfons´ın, J.L.; Rodseth, O.J.: Numerical semigroups: Ap´ery sets and Hilbert series. Semigroup Forum 79 (2009) 323–340. [17] Rosales, J.C.; Garc´ıa–S´anchez, P.A.; Garc´ıa–Garc´ıa, J.I.; Branco, M. B.: Numerical semigroups with a monotonic Ap´ery set. Czechoslovak Math. J. 55 (2005) 755–772. [18] Sylvester, J.J.: Problem 7382. Educational Times 37 (1884) 26. Depto. de ´ Algebra and IMUS, Universidad de Sevilla. E– 41080 Sevilla, Spain. E-mail address:gmarq[email protected] Depto. de Matem´ aticas, Universidad de Extremadura, E–06071 Badajoz, Spain. E-mail address:ojeda[email protected] Depto. de ´ Algebra and IMUS, Universidad de Sevilla. E–41080 Sevilla, Spain. E-mail address:torne[email protected]