Some Results on Fundamental Gaps in Numerical Semigroups

Edgar Federico Elizeche and Amitabha Tripathi^{1} Department of Mathematics Indian Institute of Technology Hauz Khas New Delhi 110016 India

                         maz188235@maths.iitd.ac.in
                         atripath@maths.iitd.ac.in

Abstract

A numerical semigroup is a submonoid of ℤ_{≥0} whose complement in ℤ_{≥0} is finite. The gap set G(S) of a numerical semigroup S is the finite set ℤ_{≥0} \ S. A positive integer n is in the set FG(S) of fundamental gaps of S provided n ∉ S but kn ∈ S for each k ∈ ℤ, k > 1. We explore the set FG(S) mostly when S is generated by 2 or 3 integers, but also in some other special cases, including when S is generated by arithmetic progressions.

1 Introduction

A numerical semigroup S is a submonoid of ℤ_{≥0} whose complement ℤ_{≥0} \ S is finite. For the complement to be finite, it is necessary and sufficient that gcd(S) = 1. For a given subset A of positive integers, we write

⟨A⟩ = {a_{1}x_{1} + ⋯ + a_{k}x_{k} : a_{i} ∈ A, x_{i} ∈ ℤ_{≥0}, k ∈ ℕ}.

Note that ⟨A⟩ is a submonoid of ℤ_{≥0}, and that S = ⟨A⟩ is a numerical semigroup if and only if gcd(A) = 1.

1Corresponding author.

We say that A is a set of generators of the semigroup S, or that the semigroup S is generated by the set A, when S = ⟨A⟩. Further, A is a minimal set of generators for S if A is a set of generators of S and no proper subset of A generates S. Every semigroup has a unique minimal set of generators. The embedding dimension e(S) of S is the size of the minimal set of generators.

A very useful tool in the study of numerical semigroups is the determination of an Apéry set of the semigroup. Given a numerical semigroup S, and a ∈ S, the Apéry set of S corresponding to a is given by

Ap(S, a) = {m_{x} : x ∈ {0, 1, 2, …, a − 1}} ,

where m_{x} denotes the least positive integer in S congruent to x modulo a.

The finite set ℤ_{≥0} \ S is called the gap set of S, and is denoted by G(S). If n ∈ G(S) and d | n, d ∈ ℕ, then d ∈ G(S). This naturally leads to the set FG(S) of fundamental gaps of S, defined as

FG(S) = {n ∈ G(S) : kn ∈ S ∀ k > 1};

see Rosales et al. [9] for more details.

We describe the set FG(S) in terms of the elements in Ap(S, a), for any a ∈ S, in Lemma 1.

Lemma 1. Let A be any set of positive integers with gcd(A) = 1, and let S = ⟨A⟩ be the numerical semigroup generated by A. Let a ∈ A, and let m_{x} denote the least positive integer in S congruent to x modulo a. Then n ∈ FG(S) if and only if

n = m_{n} − λa, 1 ≤ λ ≤ \frac{1}{a} min \{m_{n} − \frac{1}{2}m_{2n}, m_{n} − \frac{1}{3}m_{3n}\} .

Proof. Note that n ∈ FG(S) if and only if n < m_{n}, 2n ≥ m_{2n}, and 3n ≥ m_{3n}. Thus, n = m_{n} − λa for some λ ≥ 1. Using this in the other two constraints gives the upper bounds λ ≤ \frac{1}{a}(m_{n} − \frac{1}{2}m_{2n}) and λ ≤ \frac{1}{a}(m_{n} − \frac{1}{3}m_{3n}).

We determine the set of fundamental gaps of some numerical semigroups in this article. We consider numerical semigroups with embedding dimension 2 in Section 2. The Apéry set in this case is well known, and we use this to determine the set of fundamental gaps, giving a simpler proof of the same result by Rosales [7]. We consider numerical semigroups with embedding dimension 3 in Section 3. The Apéry set in this case is in general difficult to compute. We consider several special cases where the Apéry set has been determined, and use that to determine the set of fundamental gaps in those cases. We consider numerical semigroups generated by arithmetic progressions in Section 4. Apéry sets for such semigroups have been determined, and we use these to determine the set of fundamental gaps.

2 The case of embedding dimension 2

Numerical semigroups with embedding dimension 2 are the simplest to study. The Apéry set of these semigroups is easy to see and part of basic number theory. Rosales [7] determined the fundamental gap of numerical semigroups S = ⟨a, b⟩, gcd(a, b) = 1, by making use of the well known fact that n ∉ S if and only if n = ab − ax − by with x, y ∈ ℕ. We use the Apéry set of S given in Lemma 2 to determine the set of fundamental gaps in S in Theorem 3.

Lemma 2. Let A = {a, b}, where gcd(a, b) = 1. Then the Apéry set for the semigroup S = ⟨a, b⟩ is given by

Ap(S, a) = {bx : 0 ≤ x ≤ a − 1}.

Theorem 3. [7, Theorem 9] Let S = ⟨a, b⟩, where gcd(a, b) = 1. The set of fundamental gaps is given by

FG(S) = \{bs − ar : 1 ≤ r ≤ \frac{b}{3}, \frac{a}{2} ≤ s < \frac{2a}{3}\} ⋃ \{bs − ar : 1 ≤ r ≤ \frac{b}{2}, \frac{2a}{3} ≤ s ≤ a − 1\}.

Proof. Recall that n = bs − ar ∉ ⟨a, b⟩ if and only if 1 ≤ s ≤ a − 1 and 1 ≤ r < \frac{bs}{a}, and that n is a fundamental gap if and only if n ∉ ⟨a, b⟩ and 2n, 3n ∈ ⟨a, b⟩.

Since 2n = 2bs − 2ar ∉ ⟨a, b⟩ if s < \frac{a}{2}, we may henceforth assume s ≥ \frac{a}{2}. If a is even and s = \frac{a}{2}, then 2n = a(b − 2r) ∈ ⟨a, b⟩ and 3n = b · \frac{a}{2} + a(b − 3r) ∈ ⟨a, b⟩ if and only if r ≤ \frac{b}{3}. Hence, n = b · \frac{a}{2} − ar is a fundamental gap if and only if 1 ≤ r ≤ \frac{b}{3}.

For the rest of this proof, suppose s > \frac{a}{2}. Now 2n = b(2s − a) + a(b − 2r) ∈ ⟨a, b⟩ if and only if r ≤ \frac{b}{2}, since 2s − a < a. To decide whether or not 3n ∈ ⟨a, b⟩, we consider the two cases (i) s < \frac{2a}{3}, and (ii) \frac{2a}{3} ≤ s ≤ a − 1. In case (i), 3n = b(3s − a) + a(b − 3r) ∈ ⟨a, b⟩ if and only if r ≤ \frac{b}{3}, since 0 < 3s − a < a. In case (ii), 3n = b(3s − 2a) + a(2b − 3r) ∈ ⟨a, b⟩ if and only if r ≤ \frac{2b}{3}, since 0 < 3s − 2a < a. Thus, in case (i), we have r ≤ min \{\frac{b}{2}, \frac{b}{3}\} = \frac{b}{3}, while in case (ii), we have r ≤ min \{\frac{b}{2}, \frac{2b}{3}\} = \frac{b}{2}.

3 The case of embedding dimension 3

Numerical semigroups with embedding dimension 3 have received a lot of attention, primarily because these are the first class of numerical semigroups that pose a challenge. By contrast to the case of numerical semigroups with embedding dimension 2, Apéry sets of numerical semigroups with embedding dimension 3 are usually quite difficult to describe. The Frobenius number F(S) = max (ℕ \ S) of a numerical semigroup S is easily computed from the Apéry set of S, since F(S) = max (Ap(S, a)) − a for each a ∈ S. Johnson [4] described an algorithm to compute F(S) in terms of minimum multiples of generators that are in the numerical semigroup generated by the other two elements, but without determining the Apéry set. Rosales and García-Sánchez [8] and, independently, Tripathi and Vijay [16], were able to describe the Apéry set in terms of the constants first determined by Johnson [4]; see Proposition 4. However, the constants determined by Johnson [4] do not lead to an algebraic expression in terms of the generators of S and, in particular, to the determination of the Apéry set of S in the desired manner.

In this section, we consider three cases of numerical semigroups with embedding dimension 3 in which the Apéry sets can be computed explicitly in terms of their generators.

We then use this to determine the set of fundamental gaps in each case. We deal with 3-term compound sequences in Subsection 3.1. These are given by c_{0} = a_{1}a_{2}, c_{1} = b_{1}a_{2}, c_{2} = b_{1}b_{2}, where a_{1}, a_{2} and b_{1}, b_{2} are pairs of positive integers such that a_{i} < b_{i} for each i and gcd(a_{i}, b_{j}) = 1 for each pair i, j, i ≥ j. We consider numerical semigroups generated by a, b, c, where a | (b + c), in Subsection 3.2. We consider numerical semigroups generated by a, b, c, where a | lcm(b, c), in Subsection 3.3.

Proposition 4. [4, 8, 16] Let A = {a_{1}, a_{2}, a_{3}} be a set of positive integers, with gcd(a_{1}, a_{2}, a_{3}) = 1. Define L_{1}, L_{2}, L_{3} by

L_{1} = min {k_{1} ∈ ℕ : k_{1}a_{1} = v_{12}a_{2} + v_{13}a_{3}, v_{12} ≥ 0, v_{13} ≥ 0},
L_{2} = min {k_{2} ∈ ℕ : k_{2}a_{2} = v_{21}a_{1} + v_{23}a_{3}, v_{21} ≥ 0, v_{23} ≥ 0},
L_{3} = min {k_{3} ∈ ℕ : k_{3}a_{3} = v_{31}a_{1} + v_{32}a_{2}, v_{31} ≥ 0, v_{32} ≥ 0}.

Then there exist nonnegative integers x_{12}, x_{13}, x_{21}, x_{23}, x_{31}, x_{32} such that

L_{1}a_{1} = x_{12}a_{2} + x_{13}a_{3}, L_{2}a_{2} = x_{21}a_{1} + x_{23}a_{3}, L_{3}a_{3} = x_{31}a_{1} + x_{32}a_{2}.

Moreover, if no element in A is dependent on the other two, then each x_{ij} ≥ 1 and each L_{i} = x_{ji} + x_{ki}. We have

Ap(S, a_{1}) = {a_{2}x+a_{3}y : 0 ≤ x ≤ x_{12}−1, 0 ≤ y ≤ L_{3}−1 or 0 ≤ x ≤ L_{2}−1, 0 ≤ y ≤ x_{13}−1}.

\begin{matrix}(0, 0) \\ (0, x_{13}) \\ (0, L_{3}) \\ (x_{12}, L_{3}) \\ (L_{2}, x_{13}) \\ (L_{2}, 0) \\ (x_{12}, 0) \\ (0, 2x_{12}) \\ (0, 2L_{3}) \\ (2x_{12}, 2L_{3}) \\ (2x_{12}, 0) \\ (2L_{2}, 0) \\ (2L_{2}, 2x_{13}) \\ (0, 3x_{12}) \\ (0, 3L_{3}) \\ (3x_{12}, 0) \\ (3L_{2}, 0) \\ (3x_{12}, 3L_{3}) \\ (3L_{2}, 3x_{13}) \end{matrix}

Figure 1: A geometric depiction of the set of fundamental gaps in numerical semigroups with embedding dimension 3.

Each lattice point (x, y) represents the integer n = a_{2}x + a_{3}y. The integers in the Apéry set A (respectively, in 2A and 3A) are those represented by lattice points inside the region given by the union of two rectangles enclosed by red lines (respectively, by blue lines and by green lines). The solid black line represents the equation a_{2}x + a_{3}y = n, whereas the dashed black line represents the equation a_{2}x + a_{3}y = n − a_{1}.

3.1 The case of compound sequences

Let a_{1}, …, a_{k} and b_{1}, …, b_{k} be two sequences of positive integers such that a_{i} < b_{i} for each i and gcd(a_{i}, b_{j}) = 1 for each pair i, j, i ≥ j. The compound sequence formed from these two sequences is

c_{0} = a_{1}a_{2}a_{3} ⋯ a_{k}, c_{1} = b_{1}a_{2}a_{3} ⋯ a_{k}, c_{2} = b_{1}b_{2}a_{3} ⋯ a_{k}, …, c_{k} = b_{1}b_{2}b_{3} ⋯ b_{k}.

Note that gcd(c_{0}, c_{1}, c_{2}, …, c_{k}) = 1. Two important special cases are

• The compound sequence for a_{1} = … = a_{k} = a and b_{1} = … = b_{k} = b, gcd(a, b) = 1 is

the geometric sequence

a^{k}, a^{k−1}b, a^{k−2}b^{2}, …, b^{k}.

• For pairwise coprime positive integers a_{1}, …, a_{k}, the compound sequence for a_{2}, a_{3}, …, a_{k} and a_{1}, a_{2}, …, a_{k−1} is the supersymmetric sequence

\frac{P}{a_{1}} , \frac{P}{a_{2}} , …, \frac{P}{a_{k}} ,

where P = a_{1}a_{2} ⋯ a_{k}.

Numerical semigroups generated by compound sequences were studied by Kiers et al. [5]. In their study, Kiers et al. determined an Apéry set, the Frobenius number, Betti elements, and catenary degree, and also computed bounds on the delta set. We use their result on the Apéry set of numerical semigroups to determine the set of fundamental gaps of these semigroups for the case where the embedding dimension equals 3.

Lemma 5. [5, Theorem 15] Let a_{1}, …, a_{k} and b_{1}, …, b_{k} be two sequences of positive integers such that a_{i} < b_{i} for each i and gcd(a_{i}, b_{j}) = 1 for each pair i, j, i ≥ j. Then an Apéry set for the numerical semigroup S generated by the compound sequence c_{0}, c_{1}, …, c_{k} of these two sequences is given by

Ap(S, c_{0}) = {∑_{i=1}^{k} c_{i}x_{i} : 0 ≤ x_{i} ≤ a_{i} − 1, i = 1, …, k} .

The compound sequence of a_{1}, a_{2} and b_{1}, b_{2} is a 3-term sequence c_{0}, c_{1}, c_{2}. We study the set of fundamental gaps of numerical semigroups generated by c_{0}, c_{1}, c_{2}.

Theorem 6. Let a_{1}, a_{2} and b_{1}, b_{2} be two sequences of positive integers such that a_{i} < b_{i} for each i and gcd(a_{i}, b_{j}) = 1 for each pair i, j, i ≥ j. Let c_{0} = a_{1}a_{2}, c_{1} = b_{1}a_{2}, and c_{2} = b_{1}b_{2}, and let S = ⟨c_{0}, c_{1}, c_{2}⟩. Let b_{2} = qa_{1} + r, 0 ≤ r < a_{1}, and δ = ⌊\frac{2r}{a_{1}} ⌋. Let n = c_{1}x + c_{2}y − c_{0}z ∈ G(S).

(I)

2n ∈ S ⟺ \begin{cases}\frac{a_{1}}{2} & ≤ x < a_{1}, & 0 & ≤ y < \frac{a_{2}}{2} , & 1 & ≤ z ≤ \frac{b_{1}}{2} , & or, \\ 0 & ≤ x < \frac{a_{1}−r}{2}, & \frac{a_{2}}{2} & ≤ y < a_{2}, & 1 & ≤ z ≤ \frac{qb_{1}}{2} , & or, \\ \frac{a_{1}−r}{2} & ≤ x < \frac{2a_{1}−r}{2}, & \frac{a_{2}}{2} & ≤ y < a_{2}, & 1 & ≤ z ≤ \frac{(q+1)b_{1}}{2} , & or, \\ \frac{2a_{1}−r}{2} & ≤ x < a_{1}, & \frac{a_{2}}{2} & ≤ y < a_{2}, & 1 & ≤ z ≤ \frac{(q+2)b_{1}}{2} . \end{cases}

3n ∈ S ⟺ \begin{cases}\frac{a_{1}}{3} & ≤ x < \frac{2a_{1}}{3} , & 0 & ≤ y < \frac{a_{2}}{3} , & 1 & ≤ z ≤ \frac{b_{1}}{3} , & or \\ \frac{2a_{1}}{3} & ≤ x < a_{1}, & 0 & ≤ y < \frac{a_{2}}{3} , & 1 & ≤ z ≤ \frac{2b_{1}}{3} , & or \\ 0 & ≤ x < \frac{a_{1}−r}{3}, & \frac{a_{2}}{3} & ≤ y < \frac{2a_{2}}{3} , & 1 & ≤ z ≤ \frac{qb_{1}}{3} , & or \\ \frac{a_{1}−r}{3} & ≤ x < \frac{2a_{1}−r}{3}, & \frac{a_{2}}{3} & ≤ y < \frac{2a_{2}}{3} , & 1 & ≤ z ≤ \frac{(q+1)b_{1}}{3} , & or \\ \frac{2a_{1}−r}{3} & ≤ x < \frac{3a_{1}−r}{3}, & \frac{a_{2}}{3} & ≤ y < \frac{2a_{2}}{3} , & 1 & ≤ z ≤ \frac{(q+2)b_{1}}{3} , & or \\ \frac{3a_{1}−r}{3} & ≤ x < a_{1}, & \frac{a_{2}}{3} & ≤ y < \frac{2a_{2}}{3} , & 1 & ≤ z ≤ \frac{(q+3)b_{1}}{3} , & or \\ 0 & ≤ x < \frac{(1+δ)a_{1}−2r}{3}, & \frac{2a_{2}}{3} & ≤ y < a_{2}, & 1 & ≤ z ≤ \frac{(2q+δ)b_{1}}{3} , & or \\ \frac{(1+δ)a_{1}−2r}{3} & ≤ x < \frac{(2+δ)a_{1}−2r}{3}, & \frac{2a_{2}}{3} & ≤ y < a_{2}, & 1 & ≤ z ≤ \frac{(2q+δ+1)b_{1}}{3} , & or \\ \frac{(2+δ)a_{1}−2r}{3} & ≤ x < \frac{(3+δ)a_{1}−2r}{3}, & \frac{2a_{2}}{3} & ≤ y < a_{2}, & 1 & ≤ z ≤ \frac{(2q+δ+2)b_{1}}{3} , & or \\ \frac{(3+δ)a_{1}−2r}{3} & ≤ x < a_{1}, & \frac{2a_{2}}{3} & ≤ y < a_{2}, & 1 & ≤ z ≤ \frac{(2q+δ+3)b_{1}}{3} . \end{cases}

Proof. By Lemma 5, n ∈ G(S) if and only if n = c_{1}x + c_{2}y − c_{0}z, where 0 ≤ x < a_{1}, 0 ≤ y < a_{2}, and z ∈ ℕ.

(I) We derive conditions on n for which 2n ∈ S by considering five cases. The argument in each case is similar, so we present the first two cases in detail and give only the result in the remaining three cases.

(i) For 0 ≤ x < \frac{a_{1}}{2} and 0 ≤ y < \frac{a_{2}}{2} , 2n = 2c_{1}x + 2c_{2}y − 2c_{0}z ∉ S, since 2c_{1}x + 2c_{2}y ∈ Ap(S, c_{0}).

(ii) For \frac{a_{1}}{2} ≤ x < a_{1} and 0 ≤ y < \frac{a_{2}}{2} , 2n = c_{1}(2x − a_{1}) + 2c_{2}y − c_{0}(2z − b_{1}) and c_{1}(2x − a_{1}) + 2c_{2}y ∈ Ap(S, c_{0}). Therefore, 2n ∈ S ⇔ z ≤ \frac{b_{1}}{2} .

(iii) For 0 ≤ x < \frac{a_{1}−r}{2} and \frac{a_{2}}{2} ≤ y < a_{2}, we have 2n ∈ S ⇔ z ≤ \frac{qb_{1}}{2} .

(iv) For \frac{a_{1}−r}{2} ≤ x < \frac{2a_{1}−r}{2} and \frac{a_{2}}{2} ≤ y < a_{2}, we have 2n ∈ S ⇔ z ≤ \frac{(q+1)b_{1}}{2} .

(v) For \frac{2a_{1}−r}{2} ≤ x < a_{1} and \frac{a_{2}}{2} ≤ y < a_{2}, we have 2n ∈ S ⇔ z ≤ \frac{(q+2)b_{1}}{2} .

(II) We derive conditions on n for which 3n ∈ S by considering eleven cases. Again, the argument in each case is similar, so we present the first two cases in detail and give only the result in the remaining nine cases.

(i) For 0 ≤ x < \frac{a_{1}}{3} and 0 ≤ y < \frac{a_{2}}{3} , 3n = 3xc_{1} + 3yc_{2} − 3zc_{0} ∉ S, because 3c_{1}x + 3c_{2}y ∈ Ap(S, c_{0}).

(ii) For \frac{a_{1}}{3} ≤ x < \frac{2a_{1}}{3} and 0 ≤ y < \frac{a_{2}}{3} , 3n = c_{1}(3x − a_{1}) + 3c_{2}y − c_{0}(3z − b_{1}) and c_{1}(3x − a_{1}) + 3c_{2}y ∈ Ap(S, c_{0}). Therefore, 3n ∈ S ⇔ z ≤ \frac{b_{1}}{3} .

(iii) For \frac{2a_{1}}{3} ≤ x < a_{1} and 0 ≤ y < \frac{a_{2}}{3} , we have 3n ∈ S ⇔ z ≤ \frac{2b_{1}}{3} .

(iv) For 0 ≤ x < \frac{a_{1}−r}{3} and \frac{a_{2}}{3} ≤ y < \frac{2a_{2}}{3} , we have 3n ∈ S ⇔ z ≤ \frac{qb_{1}}{3} .

(v) For \frac{a_{1}−r}{3} ≤ x < \frac{2a_{1}−r}{3} and \frac{a_{2}}{3} ≤ y < \frac{2a_{2}}{3} , we have 3n ∈ S ⇔ z ≤ \frac{(q+1)b_{1}}{3} .

(vi) For \frac{2a_{1}−r}{3} ≤ x < \frac{3a_{1}−r}{3} and \frac{a_{2}}{3} ≤ y < \frac{2a_{2}}{3} , we have 3n ∈ S ⇔ z ≤ \frac{(q+2)b_{1}}{3} .

(vii) For \frac{3a_{1}−r}{3} ≤ x < a_{1} and \frac{a_{2}}{3} ≤ y < \frac{2a_{2}}{3} , we have 3n ∈ S ⇔ z ≤ \frac{(q+3)b_{1}}{3} .

(viii) For 0 ≤ x < \frac{(1+δ)a_{1}−2r}{3} and \frac{2a_{2}}{3} ≤ y < a_{2}, we have 3n ∈ S ⇔ z ≤ \frac{(2q+δ)b_{1}}{3} .

(ix) For \frac{(1+δ)a_{1}−2r}{3} ≤ x < \frac{(2+δ)a_{1}−2r}{3} and \frac{2a_{2}}{3} ≤ y < a_{2}, we have 3n ∈ S ⇔ z ≤ \frac{(2q+δ+1)b_{1}}{3} .

(x) For \frac{(2+δ)a_{1}−2r}{3} ≤ x < \frac{(3+δ)a_{1}−2r}{3} and \frac{2a_{2}}{3} ≤ y < a_{2}, we have 3n ∈ S ⇔ z ≤ \frac{(2q+δ+2)b_{1}}{3} .

(xi) For \frac{(3+δ)a_{1}−2r}{3} ≤ x < a_{1} and \frac{2a_{2}}{3} ≤ y < a_{2}, we have 3n ∈ S ⇔ z ≤ \frac{(2q+δ+3)b_{1}}{3} .

3.2 The case A = {a, b, c}, where a | (b + c)

Lemma 7. [14, Theorem 1] Let A = {a, b, c}, where gcd(a, b, c) = 1 and a | (b + c). Then the Apéry set for the semigroup S = ⟨a, b, c⟩ is given by

Ap(S, a) = { min{bx, c(a − x)} : 0 ≤ x ≤ a − 1}

= \begin{cases}bx & if 0 ≤ x ≤ \frac{ac}{b+c}; \\ c(a − x) & if \frac{ac}{b+c} < x ≤ a − 1. \end{cases} .

Theorem 8. Let S = ⟨a, b, c⟩, where gcd(a, b, c) = 1. If a | (b + c) and q = ⌊\frac{ac}{b+c}⌋, then n ∈ FG(S) if and only if

(I) q < \frac{2a}{3} and

n = bx − az,  \frac{q}{2} < x < \frac{a}{3},  1 ≤ z ≤ \frac{b+c}{a}x − \frac{c}{2},
or n = bx − az,  \frac{a}{3} ≤ x < \frac{a}{2},  1 ≤ z ≤ min \{\frac{b+c}{a}x − \frac{c}{2}, \frac{b}{3}\} ,
or n = bx − az,  \frac{a}{2} ≤ x < \frac{a+q}{3},  1 ≤ z ≤ \frac{b}{3},
or n = bx − az,  \frac{a+q}{3} ≤ x ≤ q,  1 ≤ z ≤ min \{\frac{b+c}{a}x − \frac{2c}{3}, \frac{b}{2}\} ,
or n = c(a − x) − az,  q < x < \frac{2a}{3},  1 ≤ z ≤ min \{\frac{b+2c}{2} − \frac{b+c}{a}x, \frac{c}{3}\} ,
or n = c(a − x) − az,  \frac{2a}{3} ≤ x ≤ \frac{a+q}{2},  1 ≤ z ≤ \frac{b+2c}{2} − \frac{b+c}{a}x.

(II) q ≥ \frac{2a}{3} and

n = bx − az,  \frac{q}{2} < x < \frac{a}{2},  1 ≤ z ≤ min \{\frac{b+c}{a}x − \frac{c}{2}, \frac{b}{3}\} ,
or n = bx − az,  \frac{a}{2} ≤ x < \frac{a+q}{3},  1 ≤ z ≤ \frac{b}{3},
or n = bx − az,  \frac{a+q}{3} < x < \frac{2a}{3},  1 ≤ z ≤ min \{\frac{b+c}{a}x − \frac{2c}{3}, \frac{b}{2}\} ,
or n = bx − az,  \frac{2a}{3} ≤ x ≤ q,  1 ≤ z ≤ \frac{b}{2},
or n = c(a − x) − az,  q < x ≤ \frac{a+q}{2},  1 ≤ z ≤ \frac{b+2c}{2} − \frac{b+c}{a}x.

Proof. We assume, without loss of generality, that b < c. Let q = ⌊\frac{ac}{b+c}⌋. Since ⌊\frac{ab}{b+c}⌋ + ⌊\frac{ac}{b+c}⌋ = a − 1 or a according as (b + c) ∤ ac or (b + c) | ac, we have q ≥ \frac{a−1}{2} if (b + c) ∤ ac and q > \frac{a}{2} if (b + c) | ac. By Lemma 7, n ∉ S if and only if n = bx − az > 0, 1 ≤ x ≤ q, z ≥ 1 or n = c(a − x) − az > 0, q + 1 ≤ x ≤ a − 1, z ≥ 1. Case I. (q < \frac{2a}{3})

(i) For 1 ≤ x ≤ \frac{q}{2}, m_{bx} = bx and m_{2bx} = 2bx. Hence, n = bx − az, so that 2n < m_{2bx}. Therefore, n ∉ FG(S) in this case.

(ii) For \frac{q}{2} < x < \frac{a}{3}, m_{bx} = bx, m_{2bx} = c(a−2x), and m_{3bx} = c(a−3x). Hence, n = bx−az, and 2n ≥ m_{2bx} and 3n ≥ m_{3bx} translate to z ≤ \frac{b+c}{a}x− \frac{c}{2} and z ≤ \frac{b+c}{a}x− \frac{c}{3}, respectively. Thus, n ∈ FG(S) ⇔ z ≤ \frac{b+c}{a}x − \frac{c}{2}.

(iii) For \frac{a}{3} ≤ x < \frac{a}{2}, m_{bx} = bx, m_{2bx} = c(a − 2x), and m_{3bx} = b(3x − a). Thus, n ∈ FG(S) ⇔ z ≤ min \{\frac{b+c}{a}x − \frac{c}{2}, \frac{b}{3}\}.

(iv) For \frac{a}{2} ≤ x < \frac{a+q}{3}, m_{bx} = bx, m_{2bx} = b(2x − a), and m_{3bx} = b(3x − a). Thus, n ∈ FG(S) ⇔ z ≤ \frac{b}{3}.

(v) For \frac{a+q}{3} ≤ x ≤ q, m_{bx} = bx, m_{2bx} = b(2x − a), and m_{3bx} = c(a − (3x − a)). Thus, n ∈ FG(S) ⇔ z ≤ min \{\frac{b+c}{a}x − \frac{2c}{3}, \frac{b}{2}\}.

(vi) For q < x < \frac{2a}{3}, m_{bx} = c(a − x), m_{2bx} = b(2x − a), and m_{3bx} = c(a − (3x − a)). Thus, n ∈ FG(S) ⇔ z ≤ min \{\frac{b+2c}{2} − \frac{b+c}{a}x, \frac{c}{3}\}.

(vii) For \frac{2a}{3} ≤ x ≤ \frac{a+q}{2}, m_{bx} = c(a − x), m_{2bx} = b(2x − a), and m_{3bx} = b(3x − 2a). Thus, n ∈ FG(S) ⇔ z ≤ \frac{b+2c}{2} − \frac{b+c}{a}x.

(viii) For \frac{a+q}{2} < x ≤ a−1, m_{bx} = c(a−x) and m_{2bx} = c(a−(2x−a)). Hence, n = c(a−x)−az, so that 2n < m_{2bx}. Therefore, n ∉ FG(S) in this case.

Case II. (q ≥ \frac{2a}{3}) There are seven subcases to consider, of which subcases (i), (iii), and (vii) are the subcases (i), (iv), and (viii) from Case I. We only consider the four remaining subcases, listed as (ii), (iv), (v), and (vi).

(ii) For \frac{q}{2} < x < \frac{a}{2}, m_{bx} = bx, m_{2bx} = c(a − 2x) (since q < 2x < a), and m_{3bx} = b(3x − a) (since a < 3x < a + q). Hence, n = bx − az, and 2n ≥ m_{2bx} and 3n ≥ m_{3bx} translate to z ≤ \frac{b+c}{a}x − \frac{c}{2} and z ≤ \frac{b}{3}, respectively. Thus, n ∈ FG(S) ⇔ z ≤ min \{\frac{b+c}{a}x − \frac{c}{2}, \frac{b}{3}\}.

(iv) For \frac{a+q}{3} < x < \frac{2a}{3}, m_{bx} = bx (since \frac{2a}{3} ≤ q), m_{2bx} = b(2x − a) (since a < 2x < a + q), and m_{3bx} = c(a − (3x − a)) (since a + q < 3x < 2a). Hence, n = bx − az, and 2n ≥ m_{2bx} and 3n ≥ m_{3bx} translate to z ≤ \frac{b}{2} and z ≤ \frac{b+c}{a}x − \frac{2c}{3}, respectively. Thus, n ∈ FG(S) ⇔ z ≤ min \{\frac{b+c}{a}x − \frac{2c}{3}, \frac{b}{2}\}.

(v) For \frac{2a}{3} ≤ x ≤ q, m_{bx} = bx, m_{2bx} = b(2x − a), and m_{3bx} = b(3x − 2a). Thus, n ∈ FG(S) ⇔ z ≤ \frac{b}{2}.

(vi) For q < x ≤ \frac{a+q}{2}, m_{bx} = c(a − x), m_{2bx} = b(2x − a), and m_{3bx} = b(3x − 2a). Thus, n ∈ FG(S) ⇔ z ≤ \frac{b+2c}{2} − \frac{b+c}{a}x.

3.3 The case A = {a, b, c}, where a | lcm(b, c)

Lemma 9. [15, Theorem 8] Let A = {a, b, c}, where gcd(a, b, c) = 1 and a | lcm(b, c). Then the Apéry set for the semigroup S = ⟨a, b, c⟩ is given by

Ap(S, a) = {bx + cy : 0 ≤ x ≤ s − 1, 0 ≤ y ≤ r − 1},

where r = gcd(a, b) and s = gcd(a, c).

Theorem 10. Let S = ⟨a, b, c⟩, where gcd(a, b, c) = 1 and a | lcm(b, c). Let r = gcd(a, b) and s = gcd(a, c). Then bx + cy − az ∈ FG(S) if and only if z ≥ 1 and

0 ≤ x < \frac{s}{3},  \frac{r}{2} ≤ y < \frac{2r}{3},  z ≤ \frac{c}{3s},
or \frac{s}{3} ≤ x < \frac{s}{2},  \frac{r}{2} ≤ y < \frac{2r}{3},  z ≤ min\{\frac{c}{2s}, \frac{b}{3r} + \frac{c}{3s}\},
or 0 ≤ x < \frac{s}{2},  \frac{2r}{3} ≤ y < r,  z ≤ \frac{c}{2s},
or \frac{s}{2} ≤ x < \frac{2s}{3},  0 ≤ y < \frac{r}{3},  z ≤ \frac{b}{3r},
or \frac{s}{2} ≤ x < \frac{2s}{3},  \frac{r}{3} ≤ y < \frac{r}{2},  z ≤ min\{\frac{b}{2r}, \frac{b}{3r} + \frac{c}{3s}\}
or \frac{2s}{3} ≤ x < s,  0 ≤ y < \frac{r}{2},  z ≤ \frac{b}{2r},
or \frac{s}{2} ≤ x < \frac{2s}{3},  \frac{r}{2} ≤ y < \frac{2r}{3},  z ≤ \frac{b}{3r} + \frac{c}{3s},
or \frac{s}{2} ≤ x < \frac{2s}{3},  \frac{2r}{3} ≤ y < r,  z ≤ min\{\frac{b}{2r} + \frac{c}{2s}, \frac{b}{3r} + \frac{2c}{3s}\},
or \frac{2s}{3} ≤ x < s,  \frac{r}{2} ≤ y < \frac{2r}{3},  z ≤ min\{\frac{b}{2r} + \frac{c}{2s}, \frac{2b}{3r} + \frac{c}{3s}\},
or \frac{2s}{3} ≤ x < s,  \frac{2r}{3} ≤ y < r,  z ≤ \frac{b}{2r} + \frac{c}{2s}.

Proof. We make repeated use of Lemma 9. Note that a = rs and that n ∉ S if and only if n = bx + cy − az > 0, where 0 ≤ x ≤ s − 1, 0 ≤ y ≤ r − 1 and z ≥ 1.

To determine conditions on x, y, z under which 2n ∈ S, we consider nine cases with (x, y) ∈ [\frac{λs}{2}, \frac{(λ+1)s}{2}) × [\frac{μs}{2}, \frac{(μ+1)s}{2}), with λ, μ ∈ \{0, 1\}. Fix the ordered pair (λ, μ). Then

2n = b(2x − λs) + c(2y − μr) + a(\frac{λb}{r} + \frac{μc}{s} − 2z) ∈ S if and only if 2z ≤ \frac{λb}{r} + \frac{μc}{s}. (1)

To determine conditions on x, y, z under which 3n ∈ S, we consider nine cases with (x, y) ∈ [\frac{λs}{3}, \frac{(λ+1)s}{3}) × [\frac{μs}{3}, \frac{(μ+1)s}{3}), with λ, μ ∈ \{0, 1, 2\}. Fix the ordered pair (λ, μ). Then

3n = b(3x − λs) + c(3y − μr) + a(\frac{λb}{r} + \frac{μc}{s} − 3z) ∈ S if and only if 3z ≤ \frac{λb}{r} + \frac{μc}{s}. (2)

We must consider only those pairs (λ, μ) ∈ \{0, 1\}×\{0, 1\} in eqn. (1) for which \frac{λb}{r} + \frac{μc}{s} ≥ 2 and simultaneously only those pairs (λ, μ) ∈ \{0, 1, 2\}×\{0, 1, 2\} in eqn. (2) for which \frac{λb}{r} + \frac{μc}{s} ≥ 3. Therefore, n = bx + cy − az ∈ FG(S) according to Table 1 below.

\frac{2r}{3} ≤ y < r min \{\frac{c}{2s}, \frac{2c}{3s}\} min \{\frac{c}{2s}, \frac{b}{3r} + \frac{2c}{3s}\} min \{\frac{b}{2r} + \frac{c}{2s}, \frac{b}{3r} + \frac{2c}{3s}\} min \{\frac{b}{2r} + \frac{c}{2s}, \frac{2b}{3r} + \frac{2c}{3s}\}
= \frac{c}{2s} = \frac{c}{2s} = \frac{b}{2r} + \frac{c}{2s}
\frac{r}{2} ≤ y < \frac{2r}{3} min \{\frac{c}{2s}, \frac{c}{3s}\} min \{\frac{c}{2s}, \frac{b}{3r} + \frac{c}{3s}\} min \{\frac{b}{2r} + \frac{c}{2s}, \frac{b}{3r} + \frac{c}{3s}\} min \{\frac{b}{2r} + \frac{c}{2s}, \frac{2b}{3r} + \frac{c}{3s}\}
= \frac{c}{3s}  = \frac{b}{3r} + \frac{c}{3s}
\frac{r}{3} ≤ y < \frac{r}{2} X X min \{\frac{b}{2r}, \frac{b}{3r} + \frac{c}{3s}\} min \{\frac{b}{2r}, \frac{2b}{3r} + \frac{c}{3s}\}
= \frac{b}{2r}
0 ≤ y < \frac{r}{3} X X min \{\frac{b}{2r}, \frac{b}{3r}\} min \{\frac{b}{2r}, \frac{2b}{3r}\}
= \frac{b}{3r}  = \frac{b}{2r}
0 ≤ x < \frac{s}{3}  \frac{s}{3} ≤ x < \frac{s}{2}  \frac{s}{2} ≤ x < \frac{2s}{3}  \frac{2s}{3} ≤ x < s

Table 1: Upper bounds for z

4 The case of arithmetic progressions

Numerical semigroups generated by arithmetic progressions have been extensively studied; see [1, 3, 6, 10, 11, 12], for instance. By AP(a, d; k), we mean the k-term arithmetic progression {a, a + d, …, a + (k − 1)d}, with gcd(a, d) = 1 and k ≥ 2. The Apéry set for the semigroup S = ⟨AP(a, d; k)⟩ is given as Lemma 11. We use this to determine the set of fundamental gaps in S in Theorem 12.

Lemma 11. [11, Lemma 2] Let a, d, k be positive integers, with gcd(a, d) = 1. Let AP(a, d; k) = {a+id : 0 ≤ i ≤ k−1}. Then the Apéry set for the semigroup S = ⟨AP(a, d; k)⟩ is given by

Ap(S, a) = \{a (1 + ⌊\frac{x−1}{k−1}⌋) + dx : 0 ≤ x ≤ a − 1\} .

Theorem 12. Let a, d, k be positive integers, with gcd(a, d) = 1. Let AP(a, d; k) = {a + id : 0 ≤ i ≤ k − 1}. Then ax + dy ∈ FG(AP(a, d; k)) if and only if

\frac{1}{3} (⌊\frac{3y−a}{k−1}⌋ − (d − 1)) ≤ x ≤ ⌊\frac{y−1}{k−1}⌋ ,  \frac{a}{2} ≤ y < \frac{2a}{3},
or  \frac{1}{2} (⌊\frac{2y−a}{k−1}⌋ − (d − 1)) ≤ x ≤ ⌊\frac{y−1}{k−1}⌋ ,  \frac{2a}{3} ≤ y ≤ a − 1.

Proof. Recall that n is a fundamental gap of the numerical semigroup S if and only if n ∉ S and 2n, 3n ∈ S. Let S = ⟨AP(a, d; k)⟩. We make repeated use of Lemma 11.

Fix y ∈ \{1, …, a−1\}, and suppose n = ax+dy > 0. Then n ∉ S if and only if x ≤ ⌊\frac{y−1}{k−1}⌋. To determine conditions on x under which 2n ∈ S, we consider two cases: (i) y ≤ \frac{a−1}{2},

and (ii) y > \frac{a−1}{2}. In case (i), 2n = 2ax + 2dy ∈ S if and only if 2x ≥ 1 + ⌊\frac{2y−1}{k−1}⌋. Since 1 + ⌊\frac{2y−1}{k−1}⌋ > 2 ⌊\frac{y−1}{k−1}⌋, the necessary and sufficient condition requires x > ⌊\frac{y−1}{k−1}⌋, in contradiction to the requirement for n ∉ S. Hence, there is no fundamental gap in case (i). In case (ii), y ≥ \frac{a}{2}, so 2n = a(2x + d) + d(2y − a) ∈ S if and only if 2x + d ≥ 1 + ⌊\frac{2y−a}{k−1}⌋.

To determine conditions on x under which 3n ∈ S, we consider three cases: (i) y ≤ \frac{a−1}{3}, (ii) \frac{a−1}{3} < y < \frac{2a}{3}, and (iii) \frac{2a}{3} ≤ y ≤ a − 1. In order that n be a fundamental gap, we must have y ≥ \frac{a}{2}. Hence, there is no fundamental gap in case (i). In case (ii), 3n = a(3x + d) + d(3y−a) ∈ S if and only if 3x+d ≥ 1+⌊\frac{3y−a}{k−1}⌋. In case (iii), 3n = a(3x+2d)+d(3y−2a) ∈ S if and only if 3x + 2d ≥ 1 + ⌊\frac{3y−2a}{k−1}⌋.

Therefore, n = ax + dy > 0 is a fundamental gap for the set S if and only if one of the following holds:

• for \frac{a}{2} ≤ y < \frac{2a}{3},

x ≥ max \{\frac{1}{2} (⌊\frac{2y−a}{k−1}⌋ − (d − 1)) , \frac{1}{3} (⌊\frac{3y−a}{k−1}⌋ − (d − 1))\} ,

• for \frac{2a}{3} ≤ y ≤ a − 1,

x ≥ max \{\frac{1}{2} (⌊\frac{2y−a}{k−1}⌋ − (d − 1)) , \frac{1}{3} (⌊\frac{3y−2a}{k−1}⌋ − (2d − 1))\} .

In the first case, we have

2 (⌊\frac{3y−a}{k−1}⌋ − (d − 1)) − 3 (⌊\frac{2y−a}{k−1}⌋ − (d − 1)) = 2 ⌊\frac{3y−a}{k−1}⌋ − 3 ⌊\frac{2y−a}{k−1}⌋ + (d − 1)
≥ (⌊\frac{2(3y−a)}{k−1}⌋ − 1) − ⌊\frac{3(2y−a)}{k−1}⌋ + (d − 1)
≥ ⌊\frac{a}{k−1}⌋ + (d − 2) since ⌊x⌋ − ⌊y⌋ ≥ ⌊x − y⌋
≥ 0.

In the second case, we have

3 (⌊\frac{2y−a}{k−1}⌋ − (d − 1)) − 2 (⌊\frac{3y−2a}{k−1}⌋ − (2d − 1)) = 3 ⌊\frac{2y−a}{k−1}⌋ − 2 ⌊\frac{3y−2a}{k−1}⌋ + (d + 1)

≥ (⌊\frac{3(2y−a)}{k−1}⌋ − 2) − ⌊\frac{2(3y−2a)}{k−1}⌋ + (d + 1)

≥ ⌊\frac{3(2y−a)}{k−1}⌋ − ⌊\frac{2(3y−2a)}{k−1}⌋

≥ 0.

Thus, n = ax + dy > 0 is a fundamental gap if and only if

\frac{1}{3} (⌊\frac{3y−a}{k−1}⌋ − (d − 1)) ≤ x ≤ ⌊\frac{y−1}{k−1}⌋ ,  \frac{a}{2} ≤ y < \frac{2a}{3},
or  \frac{1}{2} (⌊\frac{2y−a}{k−1}⌋ − (d − 1)) ≤ x ≤ ⌊\frac{y−1}{k−1}⌋ ,  \frac{2a}{3} ≤ y ≤ a − 1.

5 Acknowledgment

The authors gratefully acknowledge the suggestions of the anonymous referee. The authors also thank Aman Kumar for his assistance in editing this manuscript.

References

[1] P. T. Bateman, Remark on a recent note on linear forms, Amer. Math. Monthly 65 (1958), 517–518.

[2] A. Brauer and J. E. Shockley, On a problem of Frobenius, J. Reine Angew. Math. 211 (1962), 215–220.

[3] D. D. Grant, On linear forms whose coefficients are in arithmetic progression, Israel J. Math. 15 (1973), 204–209.

[4] S. M. Johnson, A linear diophantine problem, Canad. J. Math. 12 (1960), 390–398.

[5] C. Kiers, C. O’Neill, and V. Ponomarenko, Numerical semigroups on compound sequences, Comm. Algebra 44 (2016), 3842–3852.

[6] J. B. Roberts, Note on linear forms, Proc. Amer. Math. Soc. 7 (1956), 465–469.

[7] J. C. Rosales, Fundamental gaps of numerical semigroups generated by two elements, Linear Algebra Appl. 405 (2005), 200–208.

[8] J. C. Rosales and P. A. García-Sánchez, Numerical semigroups with embedding dimension three, Arch. Math. (Basel) 83 (2004), 488–496.

[9] J. C. Rosales, P. A. García-Sánchez, J. I. García-García, and J. A. Jiménez Madrid, Fundamental gaps in numerical semigroups, J. Pure Appl. Algebra 189 (2004), 301–313.

[10] E. S. Selmer, On the linear diophantine problem of Frobenius, J. Reine Angew. Math. 293/294 (1977), 1–17.

[11] A. Tripathi, The coin exchange problem for arithmetic progressions, Amer. Math. Monthly 101 (1994), 779–781.

[12] A. Tripathi, On a variation of the coin exchange problem for arithmetic progressions, Integers 3 (2003), Article A01, 1–5.

[13] A. Tripathi, On a linear diophantine problem of Frobenius, Integers 6 (2006), Article A14, 1–6.

[14] A. Tripathi, A note on a special case of the Frobenius problem, Indian J. Pure Appl. Math. 44 (2013), 375–381.

[15] A. Tripathi, On a special case of the Frobenius problem, J. Integer Seq. 20 (2017), Article 17.7.2, 1–12.

[16] A. Tripathi and S. Vijay, On a generalization of the coin exchange problem for three variables, J. Integer Seq. 9 (2006), Article 06.4.6, 1–8.

2020 Mathematics Subject Classification: Primary 20M13; Secondary 20M14, 20M30. Keywords: numerical semigroup, fundamental gap, Apéry set.