# On the Multiplicity of a Proportionally Modular Numerical Semigroup

Authors: Ze Gu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

A proportionally modular numerical semigroup is the setSa,b,c of nonnegative integer solutions to a Diophantine inequality of the form axmodb≤cx, where a,b, and c are positive integers. A formula for the multiplicity of Sa,b,c, that is, mSa,b,c=kb/a for some positive integer k, is given by A. Moscariello. In this paper, we give a new proof of the formula and determine a better bound for k. Furthermore, we obtain k=1 for various cases and a formula for the number of the triples a,b,c such that k≠1 when the number a−c is fixed.


---

## Body

## 1. Introduction and Preliminaries

Given two integersm and n with n≠0, we denote by mmodn the remainder of the division of m by n. A proportionally modular Diophantine inequality is an expression of the form axmodb≤cx, where a,b, and c are positive integers. In [1, 2], it is shown that the set Sa,b,c of nonnegative integer solutions of the former inequality is a numerical semigroup; that is, it is a subset of the set ℕ of the nonnegative integers that is closed under addition, contains 0, and whose complement in ℕ is finite. This type of numerical semigroups is known as proportionally modular numerical semigroups. If S is a numerical semigroup and d is a positive integer, then we denote by S/d the set x∈ℕ|dx∈S. It is clear that S/d is a numerical semigroup containing S. We say that S/d is the quotient of S by d. Given two relatively prime positive integers a1 and a2, we denote by a1,a2 the numerical semigroup generated by them, that is, a1,a2=s1a1+s2a2|s1,s2∈ℕ. From Theorem 6.18 in [1], we know that a1,a2/d is a proportionally modular numerical semigroup, and every proportionally modular numerical semigroup can be represented in this form. Let S be a numerical semigroup. We say that S has a Toms decomposition if there exist q1,…,qn,m1,…,mn and L such that (1) gcdqi,mi=gcdL,qi=gcdL,mi=1 for all i∈1,…,n and (2) S=1/L∩i=1nqi,mi. Let a,b, and c be positive integers. We say that the numerical semigroup a,b/c is a Toms block if gcda,b=gcda,c=gcdb,c=1. Observe that 1/L∩i=1nqi,mi=∩i=1nqi,mi/L. So, a numerical semigroup admits a Toms decomposition if and only if it can be expressed as an intersection of finitely many Toms blocks with the same denominator. In [1, 3], it is shown that numerical semigroups having a Toms decomposition are precisely those numerical semigroups that can be expressed as a finite intersection of proportionally modular numerical semigroups.As usual, for a rational numberr, r denotes the least integer not smaller than r and r denotes the greatest integer not bigger than r. If S is a numerical semigroup, then the least positive integer that belongs to S is an important invariant of S called the multiplicity of S, and we denote it by mS (see, for example, [1]). Some partial results on the invariant of a proportionally modular numerical semigroup are given in [4, 5]. In particular, a formula, that is, mSa,b,c=kb/a where k is some positive integer, is given by Moscariello in [6].The contents of this paper are organized as follows. In Section2, we give a clearer proof on the formula given in [6] and the bound of k. In Section 3, we obtain k=1 for various cases and a formula for the number of the triples a,b,c such that k≠1 when the number a−c is fixed. In Section 4, we describe an algorithm that allows us to calculate the multiplicity of Sa,b,c and apply the algorithm to some questions.


## 2. A Formula formSa,b,c

As the inequalityaxmodb≤cx has the same set of integer solutions as amodbxmodb≤cx, we do not lose generality by supposing that a<b. If c≥a, then Sa,b,c=ℕ; thus, we may also suppose that c<a. In this paper, unless otherwise stated, we suppose that a,b, and c are positive integers satisfying c<a<b.Lemma 1 (Proposition 1 [7]).
Sa,b,c=Sb+c−a,b,c.The following lemma has as a consequence that we may also suppose thata≤b+c/2.Remark 1.
(1)
Under the above notations, we havemSa,b,c<b. In fact, for any positive integer x, if cx≥b−1, then x∈Sa,b,c. It follows that mSa,b,c≤b−1/c≤b−1<b.(2)
Leta and b be positive integers such that a<b. Then, for each integer k there exists exactly one integer αk such that kb≤aαk<kb+a. Moreover, αk=kb/a. Indeed, since 0≤−kbmoda<a, we have kb≤kb+−kbmoda<kb+a. Therefore, kb≤akb/a<kb+a. Uniqueness follows from the fact that the set kb,kb+1,…,kb+a−1 consists of a consecutive integers and therefore contains exactly one multiple of a.As a consequence of the uniqueness ofαk in Remark 1 (2), we obtain the following result.Lemma 2.
Leta and b be positive integers such that a<b, and let k be an integer. Then, akb/a is the least multiple of a in the set kb,kb+1,…,kb+b−1.Remark 2.
For an integerx, if kb≤ax<k+1b, then ax/b=k. Thus, axmodb=ax−kb.Now, we are ready to prove the result given in [6] concerning the form of the multiplicity of Sa,b,c.Theorem 1 (Proposition 3 in [6]).
Under the above hypothesis and notations, we havemSa,b,c∈kb/a|k∈1,2,…,a−1.Proof.
Letm=mSa,b,c, then m<b by Remark 1 (1). Thus, there exists k∈0,1,…,a−1 such that kb≤am<k+1b, i.e., m≥kb/a. If m>kb/a, then m−1≥kb/a, and we have kb≤am−1<k+1b. By Remark 2, we have am−1modb=am−1−kb=am−kb−a=ammodb−a. Since m∈Sa,b,c,we haveammodb≤cm. Thus am−1modb=ammodb−a≤cm−a<cm−c=cm−1. Consequently, m−1∈Sa,b,c. From the fact that m is the multiplicity of Sa,b,c, we have m−1=0 and so m=1. Thus, a=amodb≤c which contradicts that c<a. Hence, m=kb/a.
Finally, ifk=0, then m=0b/a=0 which contradicts the definition of m. Therefore, k must not be 0, and this completes the proof.From the preceding theorem, it follows thatmSa,b,c=ξb/a, where ξ=mink∈1,2,…,a−1|kb/a∈Sa,b,c. The following three lemmas will allow us to reformulate this fact.Lemma 3.
Letk∈1,2,…,a−1. Then, kb/a∈Sa,b,c if and only if −kbmoda≤kbc/a−c.Proof.
Our conclusion can be obtained from the following deduction:(1)kba∈Sa,b,c⇔akbamodb≤ckba,⇔akbamodb=akba−kb≤ckba⇔a−ckba≤kb⇔a−ckb+−kbmodaa≤kb⇔−kbmoda≤kbca−c.Lemma 4.
Under the above notations, we haveξ≤a1−1/b/c.Proof.
According to Remark1 (1), we know that mSa,b,c≤b−1/c. It follows that ξb/a≤b−1/c and so ξb/a≤b−1/c. Thus, ξ≤a1−1/b/c. Since ξ is a positive integer, we have ξ≤a1−1/b/c.Lemma 5.
a1−1/b/c≤a−1, where the equality holds if and only if c=1.Proof.
Observing thata1−1/b/c≤a1−1/b/c<a, we have a1−1/b/c≤a−1. If c=1, then a1−1/b/c=a1−1/b=a−a/b=a−1. Conversely, if the equality holds, a−1≤a1−1/b/c. Thus, c≤a−a/b/a−1=1+b−a/ba−1. Since c is a positive integer, we have c≤1+b−a/ba−1=1 and so c=1.Therefore, we can reformulate the fact in Theorem1 as follows.Corollary 1.
Under the above notations, we havemSa,b,c=ξb/a, where ξ=mink∈1,2,…,a1−1/b/c|−kbmoda≤kbc/a−c.


## 3. The Cases ofmSa,b,c=b/a and mSa,b,c≠b/a

In this section, we study the cases ofk=1 and the number of the triples a,b,c such that k≠1 if the number a−c is fixed.As a consequence of Corollary1 and the proof of Lemma 3, we have the following result.Theorem 2.
mSa,b,c=b/a if and only if −bmoda≤bc/a−c if and only if b/a≤b/a−c.Corollary 2.
Ifa,b, and c satisfy one of the following conditions:(1)
a−c≤ab/a+b−1,(2)
a−c≤c+1,then mSa,b,c=b/a.Proof.
(1)
Ifa−c≤ab/a+b−1, then bc≥a−1a−c. Thus, bc/a−c≥a−1≥−bmoda. By Theorem 2, we have mSa,b,c=b/a.(2)
Ifa−c≤c+1, then bc/a−c≥bc/c+1. Since a<b, we have b≥a+1. Thus, bc/c+1≥a+1c/c+1=a−a−c/c+1≥a−1≥−bmoda. It follows from Theorem 2 that mSa,b,c=b/a.Remark 3.
Sincec is a positive integer, c+1≥2. If a−c=1 or 2, then mSa,b,c=b/a.Example 1.
(1)
Leta=13,b=70, and c=4. Then, Sa,b,c=0,6,7,11,12,13,14,15∪x∈ℕ|x≥17. As a−ca+b−1=9×82=738≤910=13×70=ab, it follows that mSa,b,c=b/a=70/13=6.(2)
Leta,b,c=5,42,2. Then, Sa,b,c=0,9,10,11,12,13,14∪x∈ℕ|x≥17. Since a−c=3=c+1, we have that mSa,b,c=b/a=42/5=9.Theorem 3.
Leta−c=d. Then, the number Nd of the triples a,b,c such that mSa,b,c≠b/a is given by(2)Nd=12∑i=1d−2d−1id−1−i+d−1modi.Proof.
Ifa−c=d, then a≥d+1. By Corollary 2 (2), if mSa,b,c≠b/a, then a<2d−1. Thus, a∈d+1,d+2,…,2d−2. Let a=d+i (i.e., c=i) for some i∈1,2,…,d−2 and ni be the number of b such that mSa,b,c≠b/a. By Theorem 2, we know that mSd+i,b,i=b/a if and only if b/d+i≤b/d, that is, mSd+i,b,i≠b/a if and only if jd+i<b<j+1d for some positive integer j (notice that b>d+i). For a positive integer j, we obtain the number d−1−ij of b satisfying this condition between jd+i and j+1d. Since d−1−ij is a natural number, we have j≤d−1/i. Thus, ni=∑j=1d−1/id−1−ij. Therefore,(3)Nd=∑i=1d−2ni,=∑i=1d−2∑j=1d−1/id−1−ij=d−1∑i=1d−2d−1i−∑i=1d−2∑j=1d−1/iij=d−1∑i=1d−2d−1i−∑i=1d−2id−1/id−1/i+12=∑i=1d−2d−1id−1−12id−1i+1=12∑i=1d−2d−1id−1−i+d−1modi.
This completes our proof.Remark 4.
By the formula in Theorem3, we obtain that N3=1 and the triple a,b,a−3 satisfying mSa,b,a−3≠b/a is exactly 4,5,1. Moreover, N4=4,N5=9,N6=17,andN7=27. This gives the integer sequence A078567 (see [8]) 1,4,9,17,27,41,57,77,…. In fact, we know from [8] that an=∑i=1n−1∑j=1n−1/in−ij is one of the formulations of the integer sequence A078567. If i|n, then n/i=n/i=n−1/i+1 and n−in/i=n−in/i=0. Otherwise, n/i=n−1/i. Thus, an=∑i=1n−1∑j=1n/in−ij, which is consistent with the formula of Nd from the second equality in the proof of Theorem 3.


## 4. The Algorithm and Some Applications

In this section, our aim is to give an algorithm to compute the multiplicity of a proportionally modular numerical semigroup and apply this algorithm to solve some questions on numerical semigroups.Lemma 6 (Proposition 2 (2) in [6]).
Ifa|b, then ma,b,c=b/a.Remark 5.
The observations made at the beginning of Section2 and the fact mℕ=1 justify the steps (1), (2), and (3). Step (4) is a consequence of Lemma 6. Finally, steps (5), (6), and (7) are consequences of Corollary 1. Also by Corollary 1, we know that the Algorithm 1 stops after a finite number of steps.Algorithm 1:INPUT: positive integers a,b, and c.
OUTPUT:mSa,b,c.INSTRUCTIONS:(1)a:=amodb.(2) Ifa>b+c/2, then a:=b+c−a.(3) Ifa≤c, then return 1.(4) Ifa|b, then return b/a.(5)k:=1.(6) while−kbmoda>kbc/a−c do k:=k+1.(7) returnkb/a.At last, we apply the given algorithm to three questions on numerical semigroups. Given two relatively prime positive integersa1 and a2, we know from Lemma 18 in [5] that a1,a2=x∈ℕ|a2−1a2xmoda1a2≤x, where a2−1∈i∈ℕ|0≤i<a1,ia2≡1moda1. Given two relatively prime positive integers a1 and a2 and a positive integer d, it is an open problem (see [1]) to find a formula for the smallest multiple of d that belongs to a1,a2.Remark 6.
Consider the quotienta1,a2/d=x∈ℕ|dx∈a1,a2=x∈ℕ|a2−1a2dxmoda1a2≤dx whose multiplicity is ma1,a2/d=mSa2−1a2d,a1a2,d, and therefore it can be calculated by applying Algorithm 1.Given a nonempty subsetA of ℚ0+ (here, ℚ0+ is the set of nonnegative rational numbers), we denote by A the submonoid of ℚ0+,+ generated by A, that is, A=λ1a1+⋯+λnan|n∈ℕ+,λ1,…,λn∈ℕanda1,…,an∈A. Clearly, SA=A∩ℕ is a submonoid of ℕ. Let p and q be two positive rational numbers with p<q. We use the notations p,q=x∈ℚ|p≤x≤q and p,q=x∈ℚ|p<x<q. It is known that Sp,q and Sp,q are proportionally modular numerical semigroups. If S is a numerical semigroup, then the greatest integer that does not belong to S is called the Frobenius number of S and denoted here by FS. In [9], a relationship between FSa,b,1 and mSb/a,b/a−1 is given by the following three lemmas.Lemma 7 (Proposition 1 in [9]).
(1)
Sb/a,b/a−c=Sa,b,c(2)
Conversely, ifa1,b1,a2, and b2 are positive integers such that b1/a1<b2/a2, then Sb1/a1,b2/a2=Sa1b2,b1b2,a1b2−a2b1Lemma 8 (Theorem 9 in [9]).
Sb/a,b/a−1=S2b2+1/2ab,2b2−1/2ba−1.Lemma 9 (Theorem 18 in [9]).
LetS=Sb/a,b/a−1 and T=Sb/a,b/a−1. Then, FS=b−mT.By Lemma7 (1), we have Sa,b,1=Sb/a,b/a−1. Moreover, Lemmas 8 and 9 assert that Sb/a,b/a−1=S4ab3−2ab,4b4−1,4b3−4ab+2b. Therefore, FSa,b,1=b−mS4ab3−2ab,4b4−1,4b3−4ab+2b. Next, we generalize the result to Sa,b,c.Theorem 4.
Letc|a and c|b. Then, FSa,b,c=b/c−mS4ab3−2abc,4b4−c2,4b3c−4abc+2bc2.Proof.
Leta=ca1 and b=cb1. Then, axmodb≤cx if and only if a1xmodb1≤x. It follows that Sa,b,c=Sa1,b1,1=Sa/c,b/c,1. Therefore, FSa,b,c=b/c−mS4ab3−2abc,4b4−c2,4b3c−4abc+2bc2.Remark 7.
From Theorem4, we can apply Algorithm 1 to compute FSa,b,c if c is a common divisor of a and b.LetS be a numerical semigroup minimally generated by n1,n2. Sylvester proved in [10] that FS=n1n2−n1−n2. If S is minimally generated by n1,n2,…,np, with p>2, then it is still an open problem to find a formula for FS. Next, we apply our algorithm to compute the Frobenius number of a numerical semigroup minimally generated by n1,n2,n3.Letn1,n2, and n3 be three positive integers such that gcdn1,n2,n3=1 and n1>n2>n3, denoted by S the numerical semigroup S:=n1,n2,n3. In the study of FS, we can assume that gcdni,nj=1, for i≠j with i,j∈1,2,3. This is due to the following result.Lemma 10 (Theorem 3 in [11]).
Letn1,n2,n3∈ℕ+ and dij=dji=gcdni,nj for every i,j⊂1,2,3 with i≠j. Define m1,m2,m3∈ℕ+ such that ni=midijdik for every i,j,k=1,2,3. Then,(4)Fn1,n2,n3=d12d23d31Fm1,m2,m3.Remark 8.
Denote byLi the positive integer minx∈ℕ+|xni∈nj,nk, with i,j,k=1,2,3. In Theorem 3.4 in [12], it is proved that(5)FS=L1n1+maxL2n2n3−1modn1n3,L3n3n2−1modn1n2−n1−n2−n3.
Observe that, by applying Algorithm1, we obtain L1,L2, and L3. Thus, we have Fn1,n2,n3 by the previous formula.



---

*Source: 3982297-2021-09-08.xml*