Let \(k, b, n\) be positive integers such that \(b\geq 2\). Denote by \(S(k,b,n)\) the numerical semigroup generated by \(\left\{b^{k+n+i}+\frac{b^{n+i}-1}{b-1}\mid i\in\mathbb{N}\right\}\). In this paper, we give formulas for computing the embedding dimension and the Frobenius number of \(S(k,b,n)\).
Let \(\mathbb{N}\) be the set of nonnegative integers. A numerical semigroup is a submonoid \(S\) of \(\mathbb{N}\) under addition such that \(\mathbb{N}\backslash S\) is finite. The elements of \(G(S)=\mathbb{N}\backslash S\) are called the gaps of \(S\). An important invariant of \(S\) is the largest integer in \(G(S)\), known as the Frobenius number of \(S\) and denoted by \(F(S)\).
Given a nonempty subset \(A\) of \(\mathbb{N}\), we denote by \(\langle A\rangle\) the submonoid of \((\mathbb{N},+)\) generated by \(A\), that is, \(\langle A\rangle=\{\lambda_{1}a_{1}+\cdots+\lambda_{n}a_{n}\mid n\in \mathbb{N}\backslash\{0\}, a_{1},\cdots,a_{n}\in A, \lambda_{1},\cdots,\lambda_{n}\in \mathbb{N}\}\). If \(M=\langle A\rangle\), then we say that \(A\) is system of generators of \(M\). In addition, if no proper subset of \(A\) generates \(M\), then we say that \(A\) is a minimal system of generators of \(M\). It is shown that every submonoid of \((\mathbb{N},+)\) has a unique minimal system of generators and such a system is finite [8]. Moreover, \(\langle A\rangle\) is a numerical semigroup if and only if \(\gcd(A)=1\). The cardinality of the minimal system of generators of a numerical semigroup \(S\) is called the embedding dimension of \(S\) and is denoted by \(e(S)\).
The Frobenius problem (see [4, 8]) is to find formulas for computing the Frobenius number and the genus of a numerical semigroup. The problem was solved by Sylvester in [9] for numerical semigroups with embedding dimension two. Recently, this problem for numerical semigroups with embedding dimension three was solved by Tripathi in [10]. However, this problem remains open for numerical semigroups with embedding dimension greater than three.
A repunit is a number like \(11, 111,\) or \(1111\) that contains only the digit \(1\). The set of repunits in base \(b\) is \(\{\frac{b^{n}-1}{b-1}\mid n\in\mathbb{N}_{+}\}\). In particular, repunits in binary is well-known Mersenne numbers. A positive integer \(x\) is a Thabit number if \(x=3\cdot 2^{n}-1\) for some \(n\in\mathbb{N}\). The concept of Mersenne [7] (repunit [6], Thabit [5]) numerical semigroups was introduced by Rosales, Branco and Torrão. Moreover, they gave the formulas for the Frobenius number, the genus and the embedding dimension of the three kinds of numerical semigroups. In [3], we generalized Thabit numerical semigroups to the class of numerical semigroups generated by \(\{(2^k-1)\cdot 2^{n+i}-1\mid i\in\mathbb{N}\}\), where \(k, n\) are positive integers such that \(2\leq k\leq 2^n\). In [2], we generalize Thabit numerical semigroups along another line to the class of numerical semigroup generated by \(\{b^{n+1+i}+\frac{b^{n+i}-1}{b-1}\mid i\in\mathbb{N}\}\), where \(b\geq 2\) is an integer. In this paper, we further generalize to the numerical semigroup generated by \(\{b^{k+n+i}+\frac{b^{n+i}-1}{b-1}\mid i\in\mathbb{N}\}\) and denote it by \(S(k,b,n)\), where \(k,b,n\) are positive integers such that \(b\geq 2\). The main purpose of the remainder of this paper is to give the formulas for the the embedding dimension and the Frobenius number of \(S(k,b,n)\).
Let \(k, b, n\) be positive integers such that \(b\geq 2\). Then \(S(k,b,n)\) is a submonoid of \((\mathbb{N},+)\). Denote by \(s_{i}\) the integer \(b^{k+n+i}+\frac{b^{n+i}-1}{b-1}\) for all \(i\in\mathbb{N}\). It is clear that \(s_{i+1}=bs_{i}+1\) for all \(i\in\mathbb{N}\). Hence \(\gcd(s_{i},s_{i+1})=1\) and so \(S(k,b,n)\) is a numerical semigroup.
Lemma 2.1 (Lemma 2 [5]). Let \(s, t\) be integers and let \(A\) be nonempty set of integers such that \(M=\langle A\rangle\). Then the following conditions are equivalent:
(1) \(sa+t\in M\) for all \(a\in A\);
(2) \(sm+t\in M\) for all \(m\in M\backslash\{0\}\).
Let \(T(k,b,n)\) be a submonoid of \((\mathbb{N},+)\) generated by \(\{(b-1)\cdot b^{k+n+i}+b^{n+i}-1\mid i\in\mathbb{N}\}\). Denote \((b-1)\cdot b^{k+n+i}+b^{n+i}-1\) by \(t_{i}\) for all \(i\in\mathbb{N}\). It is easy to see that \(s_{i}=\frac{t_{i}}{b-1}\). Define a map \(f: T(k,b,n)\rightarrow S(k,b,n)\) by \(f(t)=\frac{t}{b-1}\) for all \(t\in T(k,b,n)\). Then \(f\) is a monoid isomorphism. Consequently, if \(A\) is the minimal system of generators of \(T(k,b,n)\), then \(\{\frac{a}{b-1}\mid a\in A\}\) is the minimal system of generators of \(S(k,b,n)\).
Lemma 2.2. \(T(k,b,n)=\langle\{t_{i}\mid i=0,1,\ldots,n+k\}\rangle\).
Proof. Denote \(M=\langle\{t_{i}\mid i=0,1,\ldots,n+k\}\rangle\). Then \(M\subseteq T(k,b,n)\). Next we prove another inclusion. If \(i\in\{0,1,\ldots,n+k-1\}\), then \(bt_{i}+b-1=t_{i+1}\in M\). If \(i=n+k\), then \(bt_{i}+b-1=t_{n+k+1}=(b-1)\cdot b^{2k+2n+1}+b^{k+2n+1}-1=(t_{0}-b^{k}+2)t_{0}+t_{k}+(b^{k}-1)t_{n}\in M\). From Lemma 2.1, we obtain that \(bt+b-1\in M\) for all \(t\in M\backslash\{0\}\). By induction, we can easily show that \(t_{i}\in M\) for all \(i\geq n+k+1\). Therefore, we complete our proof. ◻
Theorem 2.3. The set \(\{t_{i}\mid i=0,1,\ldots,n+k\}\) is the minimal system of generators of \(T(k,b,n)\).
Proof. By Lemma 2.2, we know that \(\{t_{i}\mid i=0,1,\ldots,n+k\}\) is a system of generators of \(T(k,b,n)\). Next we need only prove that \(t_{j}\notin\langle\{t_{0},t_{1},\ldots,t_{j-1}\}\rangle\) for any \(j\in\{1,2,\ldots,n+k\}\). Suppose that there exists \(j\in\{1,2,\ldots,n+k\}\) such that \(t_{j}\notin\langle\{t_{0},t_{1},\ldots,t_{j-1}\}\rangle\). Then \(t_{j}=\sum\limits_{i=0}^{j-1}a_{i}t_{i}=\sum\limits_{i=0}^{j-1}a_{i}[(b-1)\cdot b^{k+n+i}+b^{n+i}]-\sum\limits_{i=0}^{j-1}a_{i}\) for some \(a_{0},\ldots,a_{j-1}\in\mathbb{N}\). Hence \(\sum\limits_{i=0}^{j-1}a_{i}\equiv 1\pmod{(b-1)\cdot b^{k+n}+b^{n}}\) and so \(\sum\limits_{i=0}^{j-1}a_{i}=1+s[(b-1)\cdot b^{k+n}+b^{n}]\) for some \(s\in\mathbb{N}_{+}\). Thus \(\sum\limits_{i=0}^{j-1}a_{i}\geq 1+(b-1)\cdot b^{k+n}+b^{n}\). Consequently, \((b-1)\cdot b^{k+n+j}+b^{n+j}-1=t_{j}\geq\sum\limits_{i=0}^{j-1}a_{i}t_{0}\geq[1+(b-1)\cdot b^{k+n}+b^{n}][(b-1)\cdot b^{k+n}+b^{n}-1]=(b-1)^{2}\cdot b^{2k+2n}+2(b-1)\cdot b^{k+2n}+b^{2n}-1\), which is impossible. Therefore, we obtain our conclusion. ◻
As a consequence of the previous statement and theorem, we have the following result.
Corollary 2.4. The minimal system of generators of \(S(k,b,n)\) is \(\{s_{i}\mid i=0,1,\ldots,n+k\}\) and so \(e(S(k,b,n))=n+k+1\).
Let \(S\) be a numerical semigroup and \(m\in S\backslash\{0\}\). The Apéry set (see [1, 8]) of \(m\) in \(S\) is \(Ap(S,m)=\{s\in S\mid s-m\notin S\}\). It is well known from [8] that \(Ap(S,m)=\{w(0),w(1),\cdots,w(m-1)\}\), where \(w(i)\) is the least element of \(S\) congruent with \(i\) modulo \(m\) for all \(i \in\{0,1,\cdots,m-1\}\). Our aim purpose is to give an explicit description of the elements in the set \(Ap(S(k,b,n),s_{0})\).
Lemma 3.1. Let \(Ap(S(k,b,n),s_{0})=\{w(0),w(1),\cdots,w(s_{0}-1)\}\). Then \(w(0)<w(1)<\cdots<w(s_{0}-1)\).
Proof. We show that \(w(i)<w(i+1)\) for all \(i\in \{0,1,\cdots,s_{0}-2\}\). Since \(w(i+1)\in S(k,b,n)\), there exist \(a_{0},a_{1},\cdots,a_{n+k}\) such that \(w(i+1)=\sum\limits_{j=0}^{n+k}a_{j}s_{j}\). Moreover, \(w(i+1)\not\equiv 0\pmod{s_{0}}\) and so there exists \(j\in\{1,2,\cdots,n+k\}\) such that \(a_{j}\neq 0\). Therefore, \[\begin{aligned} w(i+1)-1 =& a_{0}s_{0}+\cdots+(a_{j}-1)s_{j}+\cdots+a_{n+k}s_{n+k}+s_{j}-1 \\ =& a_{0}s_{0}+\cdots+(a_{j}-1)s_{j}+\cdots+a_{n+k}s_{n+k}+bs_{j-1} \\ =& a_{0}s_{0}+\cdots+(a_{j-1}+b)s_{j-1}+(a_{j}-1)s_{j}+\cdots+a_{n+k}s_{n+k} \\ \in& S(k,b,n). \end{aligned}\]
As \(w(i+1)-1\equiv i\pmod{s_{0}}\), we have \(w(i)\leq w(i+1)-1\). ◻
Lemma 3.2. \(\max Ap(S(k,b,n),s_{0})\leq s_{n}+(b-1)s_{n+k}\).
Proof. For all \(i\in \mathbb{N}\), it is easy to show that \(s_{i}=b^{i}s_{0}+\frac{b^{i}-1}{b-1}\). Therefore, we can obtain that \[\begin{aligned} s_{n}+(b-1)s_{n+k} =& b^{n}s_{0}+\frac{b^{n}-1}{b-1}+(b-1)\left(b^{k+n}s_{0}+\frac{b^{k+n}-1}{b-1}\right) \\ =& [b^{n}+(b-1)b^{k+n}]s_{0}+b^{k+n}+\frac{b^{n}-1}{b-1}-1 \\ =& [b^{n}+(b-1)b^{k+n}]s_{0}+(s_{0}-1). \end{aligned}\]
Hence, \(s_{n}+(b-1)s_{n+k}\equiv s_{0}-1\pmod{s_{0}}\). Consequently, \(w(s_{0}-1)\leq s_{n}+(b-1)s_{n+k}\) and by Lemma 3.1 we complete our proof. ◻
Let \(r\) be a positive integer. We define the set \(A(r)=\{(a_{1},a_{2},\cdots,a_{r})\in\{0,1,,\ldots,b\}^{r}\mid \mbox{if}~1\leq i<j\leq r~\mbox{and}~a_{j}=b,~\mbox{then}~a_{i}=0.\}\) and a relation \(\leq_{r}\) on \(A(r)\) as follows: \[\begin{aligned} & & (x_{1},x_{2},\cdots,x_{r})\leq_{r}(y_{1},y_{2},\cdots,y_{r}) \\ &\Leftrightarrow& (\forall m>0)~x_{m}=y_{m}~\mbox{or}~(\exists m>0)(\forall i>m)~x_{m}<y_{m}, x_{i}=y_{i}. \end{aligned}\]
It is well known that \(\leq_{r}\) is a colexicographic order and a total order on \(A(r)\). Similarly, we can define the strict order \(<_{r}\) on \(A(r)\). We denote \(R(n+k)=\{(x_{1},x_{2},\cdots,x_{n+k})\in A(n+k)\mid (x_{1},x_{2},\cdots,x_{n-1},x_{n},x_{n+1},\cdots,x_{n+k-1},x_{n+k})\leq_{n+k}(0,0,\cdots,0,1,0,\cdots,0,b-1)\}\) and its cardinality by \(\sharp R(n+k)\).
Lemma 3.3. \(Ap(S(k,b,n),s_{0})\subseteq\left\{\sum\limits_{i=1}^{n+k}a_{i}s_{i}\mid (a_{1},a_{2},\cdots,a_{n+k})\in A(n+k)\right\}\).
Proof. Let \(x\in Ap(S(k,b,n),s_{0})\). We need only show that \(x=\sum\limits_{i=1}^{n+k}a_{i}s_{i}\) for some \((a_{1},\cdots,a_{n+k})\in A(n+k)\). By induction over \(x\), if \(x=0\) then the result holds obviously. Suppose that \(x>0\) and \(j=\min\{i\in\{1,2,\ldots,n+k\}\mid x-s_{i}\in S(k,b,n)\}\). Since \(x\in Ap(S(k,b,n),s_{0})\), we have \(x-s_{j}\in Ap(S(k,b,n),s_{0})\). By induction hypothesis, there exists \((y_{1},y_{2},\cdots,y_{n+k})\in A(n+k)\) such that \(x-s_{j}=\sum\limits_{i=1}^{n+k}y_{i}s_{i}\). Hence \(x=y_{1}s_{1}+\cdots+(y_{j}+1)s_{j}+\cdots+y_{n+k}s_{n+k}\). Next we check that \((y_{1},\cdots,y_{j}+1,\cdots,y_{n+k})\in A(n+k)\).
(1) To prove \((y_{1},\cdots,y_{j}+1,\cdots,y_{n+k})\in \{0,1,\ldots,b\}^{n+k}\), it is suffices to show that \(y_{j}+1\neq b+1\). If \(y_{j}+1=b+1\), then \((y_{j}+1)s_{j}=(b+1)s_{j}=bs_{j-1}+s_{j+1}\). Thus \(x-s_{j-1}\in S(k,b,n)\) which contradicts the minimality of \(j\).
(2) From the minimality of \(j\), we obtain that \(y_{i}=0\) for all \(1\leq i<j\). Moreover, \(y_{l}\neq b\) for all \(j<l\leq n+k\). In fact, if there exists \(j<l\leq n+k\) such that \(y_{l}=b\), then \(s_{j}+y_{l}s_{l}=s_{j}+bs_{l}=bs_{j-1}+s_{l+1}\). Hence \(x-s_{j-1}\in S(k,b,n)\) which is impossible. ◻
Lemma 3.4. \(\sharp R(n+k)=b^{k+n}+\frac{b^{n}-1}{b-1}\).
Proof. We define a mapping \(\phi: R(n+k) \to \mathbb{N}\) by \(\phi(x_1, \dots, x_{n+k}) = \sum\limits_{i=1}^{n+k} x_i\frac{b^i – 1}{b – 1}\).
(1) \(\phi\) is strictly increasing.
Let \(\mathbf{x} = (x_1, \dots, x_{n+k})\) and \(\mathbf{y} = (y_1, \dots, y_{n+k})\) be two distinct elements of \(R(n+k)\) with \(\mathbf{x} <_{n+k} \mathbf{y}\) in the colexicographic order. Then there exists an index \(m \in \{1, \dots, n+k\}\) such that \(x_m < y_m\) and \(x_i = y_i\) for all \(i > m\). Then \[\phi(\mathbf{y}) – \phi(\mathbf{x}) = (y_m – x_m) \cdot \frac{b^m – 1}{b – 1} + \sum\limits_{i=1}^{m-1} (y_i – x_i) \cdot \frac{b^i – 1}{b – 1}.\] We consider the worst-case scenario for the difference
\(y_m – x_m = 1\),
For \(i < m\), we take \(y_i = 0\) and \(x_i\) as large as possible (i.e., \(x_i = b-1\) for all \(i < m\)).
Then \(\phi(\mathbf{y}) – \phi(\mathbf{x}) \geq \frac{b^m – 1}{b – 1} – \sum\limits_{i=1}^{m-1} (b – 1) \cdot \frac{b^i – 1}{b – 1} = \frac{b^m – 1}{b – 1} – \sum\limits_{i=1}^{m-1} (b^i – 1)=\frac{b^m – 1}{b – 1}-\left[\frac{b^m – b}{b – 1}-(m-1)\right] =\frac{b – 1}{b – 1} + (m – 1) = m > 0\). Hence, \(\phi\) is strictly increasing.
(2) The image of \(\phi\) is \([0, s_0 – 1]\).
It is obvious that the minimum element in \(R(n+k)\) is \(\mathbf{o}=(0, \dots, 0)\), and the maximum element in \(R(n+k)\) is \(\mathbf{a}^* = (0, \dots, 0, 1, 0, \dots, 0, b – 1)\), where the \(1\) is at position \(n\) and \(b – 1\) is at position \(n + k\). Then \(\phi(\mathbf{o}) = 0\), and \(\phi(\mathbf{a}^*) = \frac{b^n – 1}{b – 1} + (b – 1) \cdot \frac{b^{n+k} – 1}{b – 1} = b^{n+k} + \frac{b^n – 1}{b – 1} – 1 = s_0 – 1\). Since \(\phi\) is strictly increasing and \(R(n+k)\) is finite, \(\phi\) maps \(R(n+k)\) bijectively onto the integer interval \([0, s_0 – 1]\).
Therefore \(\sharp R(n+k) = s_0 = b^{k+n} + \frac{b^n – 1}{b – 1}\). ◻
Theorem 3.5. \(Ap(S(k,b,n),s_{0})=\{\sum\limits_{i=1}^{n+k}a_{i}s_{i}\mid (a_{1},\cdots,a_{n+k})\in R(n+k)\}\).
Proof. From Lemma 3.2, 3.3 and 3.4, we have \[\mathrm{Ap}(S(k,b,n), s_0) \subseteq \left\{ \sum_{i=1}^{n+k} a_i s_i \mid (a_1, \ldots, a_{n+k}) \in R(n+k) \right\}.\]
Now consider the mapping \(\psi: R(n+k) \to \mathbb{N}\) by \(\psi(a_1, \ldots, a_{n+k})=\sum\limits_{i=1}^{n+k} a_i s_i\).
We show that \(\psi\) is injective on \(R(n+k)\). Suppose \(\sum\limits_{i=1}^{n+k} a_i s_i = \sum\limits_{i=1}^{n+k} a_i' s_i.\) Since \(s_i = b^i s_0 + \frac{b^i – 1}{b – 1}\), we have \[\sum_{i=1}^{n+k} a_i \frac{b^i – 1}{b – 1} \equiv \sum\limits_{i=1}^{n+k} a_i' \frac{b^i – 1}{b – 1} \pmod{s_0}.\]
But both sides are in \([0, s_0 – 1]\) by the proof of Lemma 3.4, so they must be equal. The injectivity of \(\phi\) in Lemma 3.4 implies \(a_i = a_i'\). Hence, \(\psi\) is injective.
By Lemma 3.4, the set on the right has cardinality \(s_0\), and \(Ap(S(k,b,n),s_{0})\) also has cardinality \(s_0\). Therefore, the two sets are equal. ◻
Let \(S\) be a numerical semigroup and \(m\in S\backslash\{0\}\). It is well known from [8] that \(F(S)=\max Ap(S,m)-m\). Hence, we have the following formula for the Frobenius number of \(S(k,b,n)\).
Corollary 3.6. \(F(S(k,b,n))=(b^{k+1}-b^{k}+2)\cdot b^{k+2n}+\left(\frac{b^{n}-1}{b-1}-b^{k}\right)\cdot b^{n}-1\).
Proof. By Theorem 3.5, the maximum element of \(\mathrm{Ap}(S(k,b,n), s_0)\) is \(\psi(a^*)\), where \(a^* = (0, \ldots, 0, 1, 0, \ldots, 0, b – 1)\) is the maximum element in \(R(n + k)\). We compute \[\psi(a^*) = s_n + (b – 1)s_{n+k}.\]
The Frobenius number is then \[F(S(k,b,n)) = s_n + (b – 1)s_{n+k} – s_0 = (b^{k+1}-b^{k}+2)\cdot b^{k+2n}+\left(\frac{b^{n}-1}{b-1}-b^{k}\right)\cdot b^{n}-1.\]
This completes the proof. ◻
The research was supported by the Guangdong Basic and Applied Basic Research Foundation (No. 2022A1515011081), the Cultivation Program for High-level Project of Zhaoqing University (No. GCCZK202403) and the Innovative Research Team Project of Zhaoqing University.