Abstract
In this paper we introduce the concept of corner element of a generalized numerical semigroup, which extends in a sense the idea of conductor of a numerical semigroup to generalized numerical semigroups in higher dimensions. We present properties of this new notion and its relations with existing invariants in the literature, and provide an algorithm to compute all the generalized numerical semigroups with fixed corner. Besides that, we provide lower and upper bounds on the number of generalized numerical semigroups having a fixed corner element.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
Avoid common mistakes on your manuscript.
1 Introduction
Let \({\mathbb {N}}\) be the set of the positive integers and \({\mathbb {N}}_0 = {\mathbb {N}} \cup \{0\}\). A generalized numerical semigroup (GNS) is a submonoid \(S \subseteq {\mathbb {N}}_0^{d}\), where d is a positive integer, such that its complement \({\text {H}}(S)={\mathbb {N}}_0^{d} \setminus S\) is finite. The elements of \({\text {H}}(S)\) are called the gaps (or holes) of S and its cardinality \({\text {g}}(S)=|{\text {H}}(S)|\) is the so-called genus of S. Generalized numerical semigroups arise as a natural generalization to higher dimensions of the notion of numerical semigroup (case \(d=1\)), which is an active topic of research with many challenging open problems. For a detailed overview and compilation of the several ways of development on numerical semigroups, we refer the reader to [15, 16].
Generalized numerical semigroups were introduced by Failla, Peterson, and Utano in [10], where they computed the number of GNSs \(S \subseteq {\mathbb {N}}_0^{d}\) of genus g for small values of g and d and provided certain asymptotic bounds for large values of g and d. Since their work, several papers on GNSs, as well as on a wider class of submonoids in \({\mathbb {N}}_0^d\), have appeared in the literature proposing to formulate definitions, properties, results, and open problems of numerical semigroups to the general higher dimensional setting. For instance, in [4], Cisto, Failla, Peterson, and Utano investigated the property of irreducibility in GNSs, introducing also the notion of Frobenius GNSs and allowable gaps. Cisto, Faila, and Utano [3] studied the generators of GNSs. A new family of Frobenius GNSs, extending the irreducible ones, was proposed by Cisto and Tenório in [6] with the study of the property of almost-symmetry for GNSs. Singhal and Lin [17] characterized the allowable gaps in GNSs and provided estimates on the number of Frobenius GNSs with a given Frobenius number. In [2], Cisto, Delgado, and García-Sánchez provided algorithms to perform calculations on GNS and to compute the set of all GNS with a prescribed genus. Pseudo-Frobenius elements of a special class of submonoids in \({\mathbb {N}}_0^d\) that includes the GNSs were studied by García-García, Ojeda, Rosales, and Vigneron-Tenorio in [14]. Generalizations of the Wilf’s conjecture were proposed in [5, 13]. An extension of proportionally modular numerical semigroups to higher dimensions is investigated in [9, 12].
In this work, we introduce the concept of corner of a GNS (see Definition 3.1), which somehow generalizes the notion of conductor of a numerical semigroup. We explore the properties of this new concept and its relationships with the genus and other invariants in the literature on GNS, motivated by well known relations in numerical semigroups. Besides that, using the notion of tree of GNS, we present an algorithm to compute all the GNSs with fixed corner and we provide lower and upper bounds on the number of GNSs with a fixed corner.
This paper is organized as follows. In Sect. 2 we present some useful definitions and notations for the rest of the paper. The concept of corner of a GNS is introduced in Sect. 3, where we also present properties of this concept. The relation between the genus and the corner of a GNS is studied in Sect. 4. In Sect. 5 we give an algorithm to compute all the GNSs with fixed corner. We complete this work in Sect. 6 by providing lower and upper bounds on the number of GNSs having fixed corner.
2 Preliminaries and Notations
Throughout this paper, we use the following notations. For integers a and b, we denote \([a] := \{x \in {\mathbb {Z}}: 1 \le x \le a\}\) and \([a,b] := \{x \in {\mathbb {Z}}: a \le x \le b\}\). For a real number x, \(\lceil x \rceil \) stands for the smallest integer greater than or equal to x and \(\lfloor x\rfloor \) stands for the biggest integer smaller than or equal to x.
For an element \(\varvec{\alpha }\in {\mathbb {N}}_0^{d}\), the coordinates of \(\varvec{\alpha }\) will be denoted by \(\varvec{\alpha }= (\alpha _1,\ldots ,\alpha _d)\) and the product of the coordinates of \(\varvec{\alpha }\) by the symbol \(|\varvec{\alpha }|\). The all zero d-tuple \((0, \ldots , 0)\) will be denoted simply by \(\mathbf {0}\) and the vectors of the standard basis in \({\mathbb {R}}^d\) will be denoted by \({\mathbf {e}}_1, {\mathbf {e}}_2, \ldots , {\mathbf {e}}_d\). The natural partial order \(\le \) in \({\mathbb {N}}_0^d\) is defined as follows: for \(\varvec{\alpha }, \varvec{\beta }\in {\mathbb {N}}_0^{d}\), we have
For \(\varvec{\alpha }\in {\mathbb {N}}_0^d\), we consider the set \({\text {C}}(\varvec{\alpha }) := \{ {\mathbf {a}}\in {\mathbb {N}}_0^{d} \text{: } {\mathbf {a}}\le \varvec{\alpha }\}.\) Given a finite nonempty set \(\mathcal {B}\subseteq {\mathbb {N}}_0^d\), the least upper bound (\({{\,\mathrm{lub}\,}}\)) of \(\mathcal {B}\) is the element of \({\mathbb {N}}_0^d\) defined by
A monomial order \(\prec \) is a total order in \({\mathbb {N}}_0^d\) that satisfies the following conditions:
-
for \(\varvec{\alpha }, \varvec{\beta }\in {\mathbb {N}}_0^d\), if \(\varvec{\alpha }\prec \varvec{\beta }\), then \(\varvec{\alpha }+ \varvec{\gamma }\prec \varvec{\beta }+ \varvec{\gamma }\) for all \(\varvec{\gamma }\in {\mathbb {N}}_0^d\); and
-
for \(\varvec{\alpha }\in {\mathbb {N}}_0^d\), if \(\varvec{\alpha }\ne \mathbf {0}\), we have \(\mathbf {0}\prec \varvec{\alpha }\).
Monomial orders extend the natural partial order \(\le \) in \({\mathbb {N}}_0^d\) (see [4, Proposition 4.4]).
Given \(S\subseteq {\mathbb {N}}_0^d\) a GNS, we consider the partial order \(\le _S\) in \({\mathbb {N}}_0^d\) defined by:
where \(\varvec{\beta }-\varvec{\alpha }\) stands for the usual difference. Writing \(S^*=S\setminus \{\mathbf {0}\}\), the set of pseudo-Frobenius elements of S is defined as
Its elements are exactly the maximal elements of \({\text {H}}(S)\) with respect to the partial order \(\le _S\) (see [4, Proposition 1.3]). The set of special gaps of S is
When there is a unique maximal element in \({\text {H}}(S)\) with respect to the natural partial order \(\le \) of \({\mathbb {N}}_0^d\), S is said to be a Frobenius GNS. Otherwise, it is said to be a non-Frobenius GNS.
3 The Corner of a GNS
In this section, we define the corner of a GNS, which plays an important role in this paper.
Definition 3.1
Let \(S \subseteq {\mathbb {N}}_0^d\) be a GNS. An element \({\mathbf {c}}= (c_1, \ldots , c_d) \in S\) is called a corner of S if the following conditions are are satisfied:
-
(1)
for all \(i \in [d]\) and for all \(\alpha \in {\mathbb {N}}_0\) such that \(\alpha \ge c_i\) we have that \((\beta _1, \ldots , \beta _{i-1}, \alpha , \beta _{i+1}, \ldots , \beta _d) \in S\) for all \(\beta _1, \ldots , \beta _{i-1}, \beta _{i+1}, \ldots , \beta _d \in {\mathbb {N}}_0\);
-
(2)
for all \(i \in [d]\), there exist \(\gamma _1, \ldots , \gamma _{i-1}, \gamma _{i+1}, \ldots , \gamma _d \in {\mathbb {N}}_0\) such that \((\gamma _1, \ldots , \gamma _{i-1}, c_{i} - 1, \gamma _{i+1}, \ldots , \gamma _d) \notin S\).
Notice that every GNS S has a corner element since \({\text {H}}(S)\) is finite. In particular, \(\mathbf {0}\) is a corner of \({\mathbb {N}}_0^d\).
Proposition 3.2
Let \(S \subseteq {\mathbb {N}}_0^d\) be a GNS. Then the corner of S is unique.
Proof
Let \({\mathbf {c}}= (c_1, \ldots , c_d)\) and \({\mathbf {c}}'= (c_{1}' , \ldots , c_{d} ')\) be two corners of S and suppose that \({\mathbf {c}}\ne {\mathbf {c}}'\). Hence, there exists \(i \in [d]\) such that \(c_i \ne c_i'\) and we can assume, without loss of generality, that \(c_i - 1 \ge c_i'\). Item (1) of the Definition 3.1 ensures that \((\beta _1, \ldots , \beta _{i-1}, c_i - 1 , \beta _{i+1}, \ldots , \beta _d) \in S\) for all \(\beta _1, \ldots , \beta _{i-1}, \beta _{i+1}, \ldots , \beta _d \in {\mathbb {N}}_0\), because \({\mathbf {c}}'\) is a corner of S. On the other hand, item (2) of the definition guarantees that there are \(\gamma _1, \ldots , \gamma _{i-1}, \gamma _{i+1}, \ldots , \gamma _d \in {\mathbb {N}}_0\) such that \((\gamma _1, \ldots , \gamma _{i-1}, c_{i} - 1, \gamma _{i+1}, \ldots , \gamma _d) \notin S\), which leads to a contradiction. \(\square \)
Proposition 3.3
Let \(S \subseteq {\mathbb {N}}_0^d\) be a GNS with positive genus and corner \({\mathbf {c}}= (c_1, \ldots , c_d)\). Then the following properties hold:
-
i)
\(c_i \ne 0\) for all \(i \in [d]\);
-
ii)
there exists \(i \in [d]\) such that \(c_i>1\).
Proof
Suppose that \(c_i = 0\) for some \(i \in [d]\). From item (1) of Definition 3.1, if \(\beta _i\ge 0\), then \((\beta _1, \ldots , \beta _{i-1},\beta _i,\beta _{i+1},\ldots , \beta _d) \in S\) for all \(\beta _1, \ldots , \beta _{i-1}, \beta _{i+1}, \ldots , \beta _d \in {\mathbb {N}}_0\). Hence, \(S= {\mathbb {N}}_0^d\) which is a contradiction. Now, suppose that \(c_i = 1\) for all \(i \in [d]\). Item (1) of the Definition 3.1 ensures that \({\mathbf {e}}_i \in S\) for all \(i\in [d]\) and, again, we conclude that \(S = {\mathbb {N}}_0^d\), which is a contradiction. \(\square \)
We recall that the conductor c of a numerical semigroup S is an element of S such that \(c + n \in S\), for all \(n \in {\mathbb {N}}_0\) and \(c-1 \notin S\). In this way, the corner generalizes the concept of the conductor of a numerical semigroup. Indeed, for \(d= 1\), the conductor and the corner are the same.
Remark 3.4
Let \(S \subseteq {\mathbb {N}}_0^d\) be a GNS with genus \(g > 0\) and \({\mathbf {c}}\) be the corner of S. By definition, we can conclude that \({\text {H}}(S) \subseteq {\text {C}}({\mathbf {c}}- \varvec{1})\), where \(\varvec{1}\) stands for the d-tuple \((1,\ldots , 1)\). Moreover, the corner is the minimum element of the GNS (with respect to the partial order \(\le \)) with this property, i.e., \({\mathbf {c}}=\min _\le \{{\mathbf {x}}\in {\mathbb {N}}_0^d \ : \ {\text {C}}({\mathbf {x}}- \varvec{1})\supseteq {\text {H}}(S)\}\).
Next result relates the corner of a GNS with its set of gaps.
Theorem 3.5
Let \(S \subseteq {\mathbb {N}}_0^{d}\) be a GNS with genus \(g > 0\) and corner \({\mathbf {c}}\). Then,
In particular, S is a Frobenius GNS if and only if \({\mathbf {c}}-\mathbf {1}\in {\text {H}}(S)\).
Proof
Let \({\text {H}}(S)=\{\varvec{\alpha }_1, \ldots , \varvec{\alpha }_g\}\) be the set of gaps of S, where \(\varvec{\alpha }_i =(\alpha _{1}^{(i)}, \ldots , \alpha _{d}^{(i)})\) for each \(i \in [g]\). For each \(j \in [d]\), define \(c_j= 1 + \max \{\alpha _{j}^{(i)} \text{: } i \in [g]\}\) and \({\mathbf {c}}= (c_1,\ldots ,c_d)\). The definition of \({\mathbf {c}}\) ensures that it lies on S. Now we prove that \({\mathbf {c}}\) is the corner of S. If \(\alpha \ge c_j\), then the definition of \(c_j\) guarantees that \((\beta _1, \ldots , \beta _{i-1}, \alpha , \beta _{i+1}, \ldots , \beta _d) \in S\) for all \(\beta _1, \ldots , \beta _{j-1}, \beta _{j+1}, \ldots , \beta _d \in {\mathbb {N}}_0\) and the condition (1) in Definiton 3.1 is verified. Since \(c_j - 1 = \max \{\alpha _{j}^{(i)} \text{: } i \in [g]\}\), there exists \(k \in [1,g]\) such that the j-th coordinate of \(\varvec{\alpha }_{k}\) is \(c_j - 1\). Hence, the condition (2) in Definiton 3.1 is satisfied. Therefore, \({\mathbf {c}}\) is the corner of S. \(\square \)
In particular, one can also relate the corner of a GNS with its pseudo-Frobenius elements.
Corollary 3.6
Let \(S\subseteq {\mathbb {N}}_0^d\) be a GNS with genus \(g > 0\) and corner \({\mathbf {c}}\). Then
Proof
It suffices to prove that \({\text {lub}}({\text {PF}}(S))={\text {lub}}({\text {H}}(S))\). As \({\text {PF}}(S)\subseteq {\text {H}}(S)\), we have \({\text {lub}}({\text {PF}}(S))\le {\text {lub}}({\text {H}}(S))\). On the other hand, since \({\text {PF}}(S)\) are the maximal elements in \({\text {H}}(S)\) with respect to \(\le _S\), for all \({\mathbf {h}}\in {\text {H}}(S)\) there exists \({\mathbf {h}}'\in {\text {PF}}(S)\) such that \({\mathbf {h}}\le _S {\mathbf {h}}'\). In particular, for all \({\mathbf {h}}\in {\text {H}}(S)\) there exists \({\mathbf {h}}'\in {\text {PF}}(S)\) satisfying \({\mathbf {h}}\le {\mathbf {h}}'\). Hence, \({\text {lub}}({\text {H}}(S))\le {\text {lub}}({\text {PF}}(S))\). \(\square \)
4 The Relation Between the Genus and the Corner of a GNS
Motivated by the relation between the genus g and the conductor c of a numerical semigroup by the following formula \(g+1 \le c \le 2g\) (see [15]), we investigate relations between the genus of a GNS and the coordinates of its corner.
Proposition 4.1
Let \(S \subset {\mathbb {N}}_0^d\) be a GNS with genus \(g > 0\) and corner \({\mathbf {c}}= (c_1, \ldots , c_d)\). Then
Proof
Using Remark 3.4, we conclude that \({\text {H}}(S) \subseteq {\text {C}}({\mathbf {c}}- \varvec{1})\). Since \((0,0,\ldots ,0) \in S\), then \(|{\text {H}}(S)| \le \left( \prod _{i=1}^d c_i \right) - 1\) and the result follows. \(\square \)
In [5], the authors introduced the concept of GNS ordinary semigroup as follows.
Definition 4.2
A GNS \(S \subset {\mathbb {N}}_0^d\) is called ordinary if there exists some \({\mathbf {s}}\in {\mathbb {N}}_0^d\) such that \(S = \{ \mathbf {0} \} \cup ({\mathbb {N}}_0^d \setminus {\text {C}}({\mathbf {s}}))\).
Next, we show that those GNS are the unique that reach the bound presented in Proposition 4.1.
Lemma 4.3
Let \(S = \{ \mathbf {0} \} \cup ({\mathbb {N}}_0^d \setminus {\text {C}}({\mathbf {s}})) \subset {\mathbb {N}}_0^d\) be an ordinary GNS. Then the corner of S is \({\mathbf {c}}= {\mathbf {s}}+ \varvec{1}\).
Proof
Let \({\mathbf {s}}= (s_1, \ldots , s_d)\). If \(i \in [d]\) and \(\alpha \ge s_i + 1\) is an integer, then \((\beta _1, \ldots , \beta _{i-1}, \alpha , \beta _{i+1}, \ldots , \beta _d) \notin {\text {C}}({\mathbf {s}})\), for all \(\beta _1, \ldots , \beta _{i-1}, \beta _{i+1}, \ldots , \beta _d \in {\mathbb {N}}_0\), i.e., it belongs to S. Also, \({\mathbf {s}}= (s_1, \ldots , s_{i-1}, (s_{i}+1) - 1, s_{i+1}, \ldots , s_d) \in {\text {C}}({\mathbf {s}})\), for all \(i \in [d]\), hence it is not in S. Therefore, \({\mathbf {c}}= (s_1 +1, \ldots , s_d + 1)\) is the corner of S. \(\square \)
The ordinary GNS with corner \({\mathbf {c}}\) will be denoted by \(\mathcal {O}({\mathbf {c}})\).
Proposition 4.4
Let \(S \subset {\mathbb {N}}_0^d\) be a GNS with corner \({\mathbf {c}}\) and genus \(g > 0\). Then the following statements are equivalent:
-
(i)
\(S = \mathcal {O}({\mathbf {c}})\);
-
(ii)
\(\prod _{i=1}^{d} c_i = g+1\).
Proof
Let \({\mathbf {c}}= (c_1, \ldots , c_d)\).
\((i) \Rightarrow (ii)\). Suppose that S is an ordinary GNS with corner \({\mathbf {c}}\) and genus g. So, there is some \({\mathbf {s}}= (s_1, \ldots , s_d) \in {\mathbb {N}}_0^d\) such that \(S = \{ \mathbf {0} \} \cup ({\mathbb {N}}_0^d \setminus {\text {C}}({\mathbf {s}}))\). Thus, the set of gaps of S is \({\text {H}}(S) = \{\varvec{\alpha }\in {\mathbb {N}}_0^d \text{: } \mathbf {0} \ne \varvec{\alpha }\le {\mathbf {s}}\}\), and it follows that \(g=|{\text {H}}(S)| = \prod _{i=1}^{r} (s_i + 1) - 1\). Lemma 4.3 ensures that \(s_i + 1 = c_i\).
\((ii) \Rightarrow (i)\). Remark 3.4 guarantees that \({\text {H}}(S) \subseteq {\text {C}}({\mathbf {c}}- \varvec{1})\). Hence, \(g = |{\text {H}}(S)| \le |\{ \varvec{\alpha }\in {\mathbb {N}}^d_0 \text{: } \mathbf {0} \ne \varvec{\alpha }\le {\mathbf {c}}- \varvec{1}\}| = \prod _{i=1}^{d} c_i - 1\). By condition (ii), we conclude that \({\text {H}}(S) = {\text {C}}({\mathbf {c}}- \varvec{1}) \setminus \{\mathbf {0}\}\) and thus \(S = \mathcal {O}({\mathbf {c}})\). \(\square \)
Next, we investigate a lower bound for the genus of a GNS with respect to the coordinates of its corner.
Theorem 4.5
Let \(S\subset {\mathbb {N}}_0^d\) be a GNS with corner \({\mathbf {c}}=(c_1,\ldots , c_d)\), where \(c_i\ge 2\) for \(i \in [d]\). Then there exists a GNS \(S'\subset {\mathbb {N}}_0^d\) with corner \({\mathbf {c}}\) such that \({\text {H}}(S')\) is contained in the axes of \({\mathbb {N}}_0^d\) and \({\text {g}}(S')\le {\text {g}}(S)\).
Proof
If \(d = 1\), then \(S' = S\). If \(d > 1\), let \(H_{0}:=\{{\mathbf {h}}\in {\text {H}}(S) \ : \ {\mathbf {h}} \text{ is } \text{ in } \text{ the } \text{ axes } \text{ of } {\mathbb {N}}_0^d\}\) and \(H_1 := \{ (h_1,\ldots , h_d) \in {\text {H}}(S) \setminus H_0 \ : \ h_j{\mathbf {e}}_j\in {\text {H}}(S) \cup \{\mathbf {0}\} \text{ for } \text{ all } j \in [d] \}\). For \({\mathbf {h}}= (h_1,\ldots ,h_d)\in {\text {H}}(S)\setminus (H_{0} \cup H_1)\), define \({\mathbf {h}}' := h_{j_0}{\mathbf {e}}_{j_0}\), where \(j_0=\min \{j\in [d] \ : \ h_j{\mathbf {e}}_j\in S\setminus \{\mathbf {0}\}\}\). Now, taking into account the process of associating \({\mathbf {h}}\) to \({\mathbf {h}}'\) as above, consider the set
Note that \(\mathcal {H}\) is contained in the axes of \({\mathbb {N}}_0^d\). Let us show that \(S'={\mathbb {N}}_0^d\setminus \mathcal {H}\) is a GNS in \({\mathbb {N}}_0^d\) with corner \({\mathbf {c}}\). For this purpose, we will prove that if \(x{\mathbf {e}}_i\in \mathcal {H}\) with \(x{\mathbf {e}}_i=(y+z){\mathbf {e}}_i\) and \(y{\mathbf {e}}_i\in S'\), then \(z{\mathbf {e}}_i\notin S'\). Now, observe that \(y{\mathbf {e}}_i\in S'\) implies that \(y{\mathbf {e}}_i\in S\), because if \(y{\mathbf {e}}_i \notin S\), then \(y{\mathbf {e}}_i \in \mathcal {H}\). In the case that \(z{\mathbf {e}}_i\notin S\), we have that \(z{\mathbf {e}}_i\notin S'\) since \(\mathcal {H}\) contains the gaps of S in the axes of \({\mathbb {N}}_0^d\). On the other hand, if \(z{\mathbf {e}}_i\in S\), as \(x{\mathbf {e}}_i=(y+z){\mathbf {e}}_i\) and \(y{\mathbf {e}}_i\in S\), we obtain \(x{\mathbf {e}}_i\in S\). Hence, since \(x{\mathbf {e}}_i\in S\) and \(x{\mathbf {e}}_i\in \mathcal {H}\), it follows from the construction of \(\mathcal {H}\) that \(x{\mathbf {e}}_i={\mathbf {h}}'\) for some \({\mathbf {h}}\in {\text {H}}(S)\) outside the axes of \({\mathbb {N}}_0^d\). Now, let \({\mathbf {y}}\) be such that \({\mathbf {h}}=y{\mathbf {e}}_i+{\mathbf {y}}\). By the definition, we conclude that the i-th coordinate of \({\mathbf {y}}\) is z. Since \({\mathbf {h}}\notin S\) and \(y{\mathbf {e}}_i \in S\), we must have \({\mathbf {y}}\notin S\). Furthermore, because of \({\mathbf {h}}\) is outside the axes of \({\mathbb {N}}_0^d\), so is \({\mathbf {y}}\). Since all coordinates of \({\mathbf {h}}\) and \({\mathbf {y}}\), different from the i-th, are the same, \({\mathbf {h}}'\) lies in the axis \(Ox_i\) and \(z{\mathbf {e}}_i \in S\), we conclude that \({\mathbf {y}}' = z{\mathbf {e}}_i \in \mathcal {H}\). Therefore, \(S'\) is a GNS.
In order to prove that \(S'\) has corner \({\mathbf {c}}\), let us show that \({\mathbf {h}}^i=(c_i-1){\mathbf {e}}_i\in \mathcal {H}\) for all \(i \in [d]\). First, notice that \({\mathbf {h}}^1\in \mathcal {H}\) because there exists \({\mathbf {h}}\in {\text {H}}(S)\) such that \(h_1=c_1-1\), and thus we have either \({\mathbf {h}}^1\notin S\) or \({\mathbf {h}}^1={\mathbf {h}}'\). In both cases, we obtain \({\mathbf {h}}^1\in \mathcal {H}\). Now, let us consider \({\mathbf {h}}^i\) for \(i \in [2,d]\). If \({\mathbf {h}}^i\notin S\), then \({\mathbf {h}}^i\in H_0 \subset \mathcal {H}\) and we are done. If \({\mathbf {h}}^i\in S\), there exists \({\mathbf {w}}= (w_1, \ldots , w_r) \in {\text {H}}(S)\) such that \(w_i=c_i-1\). If \(w_j{\mathbf {e}}_j\notin S\) for all \(j \in [i-1]\), as \({\mathbf {h}}^i=w_i{\mathbf {e}}_i\in S\), then \({\mathbf {h}}^i={\mathbf {w}}'\) and thus \({\mathbf {h}}^i\in \mathcal {H}\). Now, suppose that \(J = \{j \ : \ w_j{\mathbf {e}}_j \in S \text{ and } j < i\}\) is a nonempty set and let \({\mathbf {x}}={\mathbf {w}}-\sum _{j \in J}w_{j}{\mathbf {e}}_{j}\notin S\). There are two possibilities: (1) if \({\mathbf {x}}\) is in the axis of \({\mathbb {N}}_0^d\), then \({\mathbf {x}}\in H_0\) and thus \({\mathbf {x}}= {\mathbf {h}}^i\); (2) if \({\mathbf {x}}\) is not in the axis of \({\mathbb {N}}_0^d\): since the i-th coordinate of \({\mathbf {x}}\) is \(w_i=c_i-1\ge 1\) and \({\mathbf {x}}\in {\text {H}}(S)\), we have that \({\mathbf {h}}^i={\mathbf {x}}'\) because \(x_i{\mathbf {e}}_i={\mathbf {h}}^i\in S\). Thus, we can conclude that \(S'\) has corner \({\mathbf {c}}\).
Since every gap of \(S'\) comes from at most one gap of S by the construction of \(\mathcal {H}\), we have the inequality \({\text {g}}(S')\le {\text {g}}(S)\). \(\square \)
Example 4.6
Consider the GNS S in \({\mathbb {N}}_0^2\) with \({\text {H}}(S) = \{(1,0), (1,1), (3,0)\}\), which has corner (4, 2). We shall construct the set \(\mathcal {H}\) following the proof of Theorem 4.5. In this case, \(H_0 = \{(1,0), (3,0)\}, H_1 = \emptyset \) and \(\mathcal {H} = \{(1,0), (3,0)\} \cup \{(1,1)'\}\). Theorem 4.5 ensures that \(S' = {\mathbb {N}}_0^2 \setminus \mathcal {H}\) is a GNS with corner (4, 2) and now we explicit it by the set of gaps. By definition, \((1,1)' = (0,1)\), since \((1,0) \notin S\) and \((0,1) \in S\). Hence, \(\mathcal {H} = \{(1,0), (3,0), (0,1)\}\) is the set of gaps of \(S'\), which is a GNS with all the gaps in the axis. Moreover, \({\text {g}}(S) = 3\) and \({\text {g}}(S') = 3\).
Example 4.7
Consider the GNS S in \({\mathbb {N}}_0^4\) with
Observe that S has corner (4, 2, 7, 4). This example also illustrates the method of obtaining \(S'\) from S as in Theorem 4.5. In this case,
and the set \(\mathcal {H}\) is
Theorem 4.5 ensures that \(S' = {\mathbb {N}}_0^2 \setminus \mathcal {H}\) is a GNS with corner (4, 2, 7, 4) and its set of gaps is
Furthermore, \({\text {g}}(S) = 15\) and \({\text {g}}(S') = 10\).
Next, we present a lower bound for the genus of a GNS in terms of the coordinates of its corner.
Proposition 4.8
Let \(S \subset {\mathbb {N}}_0^d\) be a GNS with corner \({\mathbf {c}}= (c_1, \ldots , c_d)\), with \(c_i \ge 2\) for all i. Then
Proof
We want to minimize \({\text {g}}(S)\), for S in the set of all GNS with fixed corner \({\mathbf {c}}\). By Theorem 4.5, we only have to check those GNS with all the gaps in the axes of \({\mathbb {N}}_0^d\).
Let S be a GNS with all the gaps in the axes of \({\mathbb {N}}_0^d\) and consider \(S_i := \{s \in {\mathbb {N}}_0 \ : \ s{\mathbf {e}}_i \in S\}\). One can check that \(S_i\) is a numerical semigroup with conductor \(c_i\). Let \(g_i\) be the genus of \(S_i\). By numerical semigroups properties, we obtain \(c_i \le 2g_i\), for all i and the genus of S is given by \(\sum g_i\). Hence, \(\sum c_i \le \sum 2g_i = 2{\text {g}}(S)\) and we are done. \(\square \)
Notice that both GNS given in Example 4.6 are examples that reach this last bound.
Remark 4.9
The arithmetic-geometric mean inequality guarantees that if \(S \subset {\mathbb {N}}_0^d\) is a GNS with genus g and corner \({\mathbf {c}}= (c_1, \ldots , c_d)\), with \(c_i \ge 2\), for all i, then
Next, we exhibit a GNS with corner \({\mathbf {c}}\) with the least possible genus. For this propose, we deal with irreducible numerical semigroups. Recall that a numerical semigroup with genus g and conductor c satisfies \(g \ge \left\lceil \frac{c}{2} \right\rceil \). Recall furthermore that a numerical semigroup is irreducible if, and only if, \(g = \left\lceil \frac{c}{2} \right\rceil \) (cf. [15]). Moreover, for each \(c \in {\mathbb {N}}, c \ge 2\), there exists an irreducible numerical semigroup with conductor c.
Corollary 4.10
Let \({\mathbf {c}}=(c_1,\ldots , c_d) \in {\mathbb {N}}_0^d\), where \(c_i\ge 2\) for all i. There exists a GNS T with corner \({\mathbf {c}}\), such that
Moreover, this is the least possible genus for a GNS with corner \({\mathbf {c}}\).
Proof
For each \(i \in [d]\), let \(T_i\) be an irreducible numerical semigroup with conductor \(c_i\). By taking \(\mathcal {H} := \bigcup _{i=1}^{d} \{h {\mathbf {e}}_i \ : \ h \notin T_i\}\), one can check that \(T = {\mathbb {N}}_0^d \setminus \mathcal {H}\) is a GNS with genus \(\sum _{i=1}^d \left\lceil \frac{c_i}{2}\right\rceil \).
Now, let S be a GNS with corner \({\mathbf {c}}\). From Theorem 4.5, there exists a GNS \(S'\) with all gaps in the axes such that \({\text {g}}(S') \le {\text {g}}(S)\). For each \(i \in [d]\), consider the numerical semigroup \(S'_i := \{s \in {\mathbb {N}}_0 \ : \ s{\mathbf {e}}_i \in S'\}\) with genus \(g_i\). From the construction of \(S'_i\), its conductor is \(c_i\) (since the corner of \(S'\) is \({\mathbf {c}}\)) and the genus of \(S'\) is \(\sum g_i\). Since \(g_i \ge \left\lceil \frac{c_i}{2} \right\rceil \) for each \(i \in [d]\), we conclude that
\(\square \)
To end this section, we explain the reason for the hypothesis \(c_i \ge 2\), for every i in last results. We also explain how we can obtain a relation between the sum of the coordinates of the corner and the genus of a GNS, if some of the coordinates of the corner are equal to 1. For instance, the GNS \(S = {\mathbb {N}}_0^2 \setminus \{(1,0)\}\) has genus \(g = 1\) and corner (2, 1); the sum of the coordinates of the corner is greater than twice the genus. Hence, Proposition 4.8 does not hold in this case.
Remark 4.11
Let \(S \subset {\mathbb {N}}_0^d\) be a GNS with genus \(g > 0\) and corner \({\mathbf {c}}= (c_1, \ldots , c_d)\) such that the set of indices \(\mathcal {U}({\mathbf {c}}) = \{j \ : \ c_j = 1\}\) is nonempty. We want to obtain an upper bound for the sum of the coordinates of \({\mathbf {c}}\) in terms of g, where \(|\mathcal {U}({\mathbf {c}})| = k\) is a positive number. By the definition of corner, we conclude that \(k \le d - 1\). Notice that all the gaps of S are of the form \({\mathbf {h}}= (h_1, \ldots , h_d)\), where \(h_i = 0\), if \(i \in \mathcal {U}({\mathbf {c}})\). Hence, we can look at the set H(S) as a subset of \({\mathbb {N}}_0^{d-k}\), by erasing all the coordinates that are in the j-th position, with \(j \in \mathcal {U}({\mathbf {c}})\). This new set is the set of gaps of a GNS in \({\mathbb {N}}_0^{d-k}\) with corner \(\bar{{\mathbf {c}}}\), which has all the coordinates greater than one. Moreover, the genus of this new GNS is the same as the genus of S. Hence, we can apply Proposition 4.8. In this case, the sum of the coordinates of the corner \(\bar{{\mathbf {c}}}\) is such that \(\sum _{i \notin \mathcal {U}({\mathbf {c}})} c_i \le 2g\). By summing up \(\sum _{i \in \mathcal {U}({\mathbf {c}})} c_i\) in both sides and recalling that \(c_i = 1\), for \(i \in \mathcal {U}({\mathbf {c}})\), we conclude that
which is globally bounded by \(2g + d - 1\).
5 The Tree of GNS with Fixed Corner
In this section, we give an algorithm to compute all the GNSs with fixed corner. Consider \(\mathcal {C}({\mathbf {c}})\) the family of GNSs having corner \({\mathbf {c}}\). From Proposition 3.3, we shall consider \({\mathbf {c}}\in {\mathbb {N}}^d \setminus \{\mathbf {1}\}\) and one can take the ordinary GNS \(\mathcal {O}({\mathbf {c}})\) in \(\mathcal {C}({\mathbf {c}})\). Thus, we present a procedure to obtain all elements in \(\mathcal {C}({\mathbf {c}})\) from \(\mathcal {O}({\mathbf {c}})\). In special, we show that this method allow us arranging all GNSs having fixed corner into a rooted tree.
For \({\mathbf {x}}\in {\mathbb {N}}_0^d\), recall that \({\text {C}}({\mathbf {x}})=\{{\mathbf {y}}\in {\mathbb {N}}_0^d \ : \ {\mathbf {y}}\le {\mathbf {x}}\}\). Given a GNS S and \({\mathbf {x}}\in {\mathbb {N}}_0^d\) such that \({\text {C}}({\mathbf {x}}-\mathbf {1})\supset {\text {H}}(S)\), define for each \(i\in [d]\) the sets
where \({\mathbf {h}}= (h_1, \ldots , h_d)\) and \({\mathbf {x}}= (x_1, \ldots , x_d)\). Next, we characterize GNSs with fixed corner \({\mathbf {c}}\) in terms of the sets \(\nabla _i(S,{\mathbf {c}})\).
Lemma 5.1
Let \(S\subseteq {\mathbb {N}}_0^d\) be a GNS and let \({\mathbf {c}}\in {\mathbb {N}}_0^d\) such that \({\text {C}}({\mathbf {c}}-\mathbf {1})\supset {\text {H}}(S)\). Then S has corner \({\mathbf {c}}\) if and only if \(\nabla _i(S,{\mathbf {c}})\ne \emptyset \) for all \(i\in [d]\).
Proof
If \(\nabla _i(S,{\mathbf {c}})= \emptyset \) for some \(i\in [d]\), then there is no gap of S such that its i-th coordinate is \(c_i - 1\). Hence, the i-th coordinate of \({\text {lub}}({\text {H}}(S))\) is smaller than \(c_i - 1\), contradicting Theorem 3.5. On the other hand, if \(\nabla _i(S,{\mathbf {c}})\ne \emptyset \) for all \(i\in [d]\), then \({\mathbf {c}}={\text {lub}}({\text {H}}(S))+\mathbf {1}\) is the corner of S by Theorem 3.5. \(\square \)
We now consider unitary extensions of GNSs which preserve the property of having a fixed corner \({\mathbf {c}}\). Recall that if S is a GNS and \({\mathbf {x}}\notin S\), then \(S \cup \{{\mathbf {x}}\}\) is a GNS if and only if \({\mathbf {x}}\in {\text {SG}}(S)\) (see [4] Proposition 2.3).
Proposition 5.2
Let \(S\subseteq {\mathbb {N}}_0^d\) be a GNS with corner \({\mathbf {c}}\) and \({\mathbf {x}}\in {\text {SG}}(S)\). Then \(S\cup \{{\mathbf {x}}\}\) has corner \({\mathbf {c}}\) if and only if \(\nabla _i(S, {\mathbf {c}})\ne \{{\mathbf {x}}\}\) for all \(i\in [d]\).
Proof
By Lemma 5.1, it suffices to notice that for each \(i\in [d]\) we have \(\nabla _i(S\cup \{{\mathbf {x}}\}, {\mathbf {c}})\ne \emptyset \) if and only if \(\nabla _i(S, {\mathbf {c}})\ne \{{\mathbf {x}}\}\). \(\square \)
Recall that if T is a GNS and \({\mathbf {x}}\in T\), then \(T\setminus \{{\mathbf {x}}\}\) is a GNS if and only if \({\mathbf {x}}\) is a minimal generator of T, that is, \({\mathbf {x}}\in T^*\setminus (T^* +T^*)\) (see [10] Proposition 4.1). We now look for conditions on a minimal generator of a GNS so that the new GNS obtained by taking it out has the same corner as the previous one.
Proposition 5.3
Let \(T\subseteq {\mathbb {N}}_0^d\) be a GNS with corner \({\mathbf {c}}\) and let \({\mathbf {x}}\) be a minimal generator of T. Then \(T\setminus \{{\mathbf {x}}\}\) has corner \({\mathbf {c}}\) if and only if \({\mathbf {x}}\le {\mathbf {c}}-\mathbf {1}\).
Proof
If \(T\setminus \{{\mathbf {x}}\}\) has corner \({\mathbf {c}}\), as \({\mathbf {x}}\in {\text {H}}(T\setminus \{{\mathbf {x}}\})\), then \({\mathbf {x}}\le {\mathbf {c}}-\mathbf {1}\). Conversely, if \({\mathbf {x}}\le {\mathbf {c}}-\mathbf {1}\), then \({\text {H}}(T)\cup \{{\mathbf {x}}\}\subset {\text {C}}({\mathbf {c}}-\mathbf {1})\). Since \({\text {H}}(T\setminus \{{\mathbf {x}}\})={\text {H}}(T)\cup \{{\mathbf {x}}\}\) and \(\nabla _i(T\setminus \{{\mathbf {x}}\}, {\mathbf {c}})\supseteq \nabla _i(T, {\mathbf {c}})\) for all \(i\in [d]\), the result follows from Lemma 5.1. \(\square \)
Remark 5.4
The unitary extensions of GNSs with corner \({\mathbf {c}}\) given in Propositions 5.2 and 5.3 are inverse procedures to each other in the sense that, for S and T GNSs with corner \({\mathbf {c}}\), we have:
-
if \({\mathbf {x}}\in {\text {SG}}(S)\), then \({\mathbf {x}}\) is a minimal generator of \(S\cup \{{\mathbf {x}}\}\) with \({\mathbf {x}}\le {\mathbf {c}}-\mathbf {1}\); and
-
if \({\mathbf {x}}\) is a minimal generator of T with \({\mathbf {x}}\le {\mathbf {c}}-\mathbf {1}\), then \({\mathbf {x}}\in {\text {SG}}(T\setminus \{{\mathbf {x}}\})\).
In order to obtain GNSs with a same corner by adding special gaps, motivated by Proposition 5.2, let us consider the following definition.
Definition 5.5
For \(S\subseteq {\mathbb {N}}_0^d\) a GNS with corner \({\mathbf {c}}\), define
Next, we describe a procedure to obtain all the GNSs in \(\mathcal {C}({\mathbf {c}})\). The main idea is building up GNSs with corner \({\mathbf {c}}\) from \(\mathcal {O}({\mathbf {c}})\) (the ordinary GNS with corner \({\mathbf {c}}\)) through Proposition 5.2 by considering unitary extensions \(S\cup \{{\mathbf {x}}\}\) for elements \({\mathbf {x}}\in {\text {D}}(S)\), where S is a GNS with corner \({\mathbf {c}}\). However, this method may provide redundant GNSs in \(\mathcal {C}({\mathbf {c}})\), in the sense that the same GNS can be generated more than one time in this way. To avoid this situation, we will consider a special subset of \({\text {D}}(S)\) as follows.
Definition 5.6
Let \(S\subseteq {\mathbb {N}}_0^d\) be a nonordinary GNS with corner \({\mathbf {c}}\) and let \(\prec \) be a monomial order. Considering \({\text {L}}(S):=\{{\mathbf {x}}\in S \ : \ {\mathbf {x}}\le {\mathbf {c}}-\mathbf {1}\}\), define
We also define the element
Observe that \({\text {L}}(\mathcal {O}({\mathbf {c}})) \setminus \{\mathbf {0}\} = \emptyset \). Thus, we shall consider \({\text {D}}_{\prec }(\mathcal {O}({\mathbf {c}})) = {\text {D}}(\mathcal {O}({\mathbf {c}}))\), which coincides with \({\text {SG}}(\mathcal {O}({\mathbf {c}}))\), the set of special gaps of \(\mathcal {O}({\mathbf {c}})\). Notice that, except for \(\mathcal {O}({\mathbf {c}})\), it is always ensured the existence of a such minimal generator \({\mathbf {x}}\) in a GNS with corner \({\mathbf {c}}\) as in Proposition 5.3.
Lemma 5.7
Let \(T\subseteq {\mathbb {N}}_0^d\) be a nonordinary GNS with corner \({\mathbf {c}}\). Let \(\prec \) be a monomial order and \({\mathbf {x}}={\text {low}}_{\prec }(T)\). Then \(T\setminus \{{\mathbf {x}}\}\) is a GNS with corner \({\mathbf {c}}\).
Proof
Since T is nonordinary, the set \({\text {L}}(T)\setminus \{\mathbf {0}\}=\{{\mathbf {z}}\in T^* \ : \ {\mathbf {z}}\le {\mathbf {c}}-\mathbf {1}\}\) is not empty, and thus the element \({\mathbf {x}}\) is well-defined. Notice that \({\mathbf {x}}\) is a minimal generator of T since otherwise we could write \({\mathbf {x}}={\mathbf {x}}_1+{\mathbf {x}}_2\) with \({\mathbf {x}}_1,{\mathbf {x}}_2\in T^*\), which implies that \({\mathbf {x}}_1\prec {\mathbf {x}}\), contradicting the minimality of \({\mathbf {x}}\) with respect to \(\prec \) in \({\text {L}}(S)\setminus \{\mathbf {0}\}\) because \({\mathbf {x}}_1\le {\mathbf {x}}\le {\mathbf {c}}-\mathbf {1}\). Hence, \(T\setminus \{{\mathbf {x}}\}\) is a GNS that has corner \({\mathbf {c}}\) by Proposition 5.3. \(\square \)
Lemma 5.8
Let \(S\subseteq {\mathbb {N}}_0^d\) be a nonordinary GNS with corner \({\mathbf {c}}\) and let \(\prec \) be a monomial order. Then there exists a chain \(S_{1}\supset S_{2}\supset \cdots \supset S_{n-1} \supset S_{n}\) of GNSs with corner \({\mathbf {c}}\) such that:
-
\(S_1=S\);
-
\(S_{i+1}=S_{i}\setminus \{{\text {low}}_{\prec }(S_i)\}\) for \(i \in [n-1]\); and in particular
-
\(S_{n}=\mathcal {O}({\mathbf {c}})\).
Proof
For \(S_{1}=S\), it follows from Lemma 5.7 that \(S_1\setminus \{{\mathbf {x}}_1\}\) has corner \({\mathbf {c}}\), for \({\mathbf {x}}_1 ={\text {low}}_{\prec }(S_1)\). Putting \(S_{2}=S_1\setminus \{{\mathbf {x}}_1\}\), if \(S_2\) is ordinary we conclude the procedure, and otherwise we consider \(S_3=S_2\setminus \{{\mathbf {x}}_2\}\) with corner \({\mathbf {c}}\), where \({\mathbf {x}}_2 ={\text {low}}_{\prec }(S_2)\), by Lemma 5.7. Repeating this argument for each \(i\ge 2\), we obtain a GNS \(S_{i+1}=S_{i}\setminus \{{\mathbf {x}}_i\}\) with corner \({\mathbf {c}}\), where \({\mathbf {x}}_i={\text {low}}_{\prec }(S_i)\). The procedure stops when it reaches \(S_{i}=\mathcal {O}({\mathbf {c}})\) for some i (and it occurs because \({\text {L}}(S)\) is finite). \(\square \)
Remark 5.9
It is worth to mention that, in the previous result, the element \({\text {low}}_{\prec }(S_i)\in {\text {D}}_\prec (S_{i+1})\) for each i. Indeed, as observed in Remark 5.4, \({\text {low}}_{\prec }(S_i)\in {\text {SG}}(S_{i+1})\). Furthermore, we get \(\nabla _j(S_{i+1}, {\mathbf {c}})\ne \{{\text {low}}_{\prec }(S_i)\}\) for all \(j\in [d]\), by using Proposition 5.2 with the fact that \(S_i=S_{i+1}\cup \{{\text {low}}_{\prec }(S_i)\}\) has corner \({\mathbf {c}}\). Hence, we have \({\text {low}}_{\prec }(S_i)\in {\text {D}}(S_{i+1})\). As \({\text {low}}_{\prec }(S_i)=\min _{\prec }({\text {L}}(S_{i})\setminus \{\mathbf {0}\})\), we get \({\text {low}}_{\prec }(S_i)\prec {\mathbf {y}}\) for all \({\mathbf {y}}\in {\text {L}}(S_{i+1})\setminus \{\mathbf {0}\}\) because \({\text {L}}(S_{i})\supset {\text {L}}(S_{i+1})\).
As a consequence, gathering the conclusions of Proposition 4.1, Corollary 4.10 and Lemma 5.8, we obtain the distribution of genera of GNSs with prescribed corner.
Corollary 5.10
Given a pair \((g, {\mathbf {c}})\in {\mathbb {N}} \times \{{\mathbf {x}}\in {\mathbb {N}}^d \ : \ x_i \ge 2 \text { for all } i\}\), there exists a GNS with corner \({\mathbf {c}}\) and genus g if, and only if,
In order to provide a procedure that gives all GNSs having fixed corner \({\mathbf {c}}\), without repetitions of GNSs, let us consider the following definition.
Definition 5.11
Let \(\prec \) be a monomial order, \({\mathbf {c}}\in {\mathbb {N}}^d\) and let \(\mathcal {C}({\mathbf {c}})\) be the set of GNSs having corner \({\mathbf {c}}\). Define \(\mathcal {G}_{\prec }({\mathbf {c}})=(\mathcal {C}({\mathbf {c}}), \mathcal {E}_{\prec })\) to be the graph whose set of vertices is \(\mathcal {C}({\mathbf {c}})\) and the set of edges is \(\mathcal {E}_{\prec }:=\{(T,S)\in \mathcal {C}({\mathbf {c}})\times \mathcal {C}({\mathbf {c}}) \ : \ S=T\setminus \{{\text {low}}_{\prec }(T)\}\}\). If \((T,S)\in \mathcal {E}_{\prec }\), T is called a child of S.
The following result shows us it is possible to arrange GNSs having fixed corner into a rooted tree.
Theorem 5.12
Let \(\prec \) be a monomial order and \({\mathbf {c}}\in {\mathbb {N}}^d\). Then \(\mathcal {G}_{\prec }({\mathbf {c}})\) is a rooted tree whose root is \(\mathcal {O}({\mathbf {c}})\) and the children of \(S\in \mathcal {C}({\mathbf {c}})\) are \(S\cup \{{\mathbf {x}}\}\), where \({\mathbf {x}}\in {\text {D}}_{\prec }(S)\).
Proof
Given \(S\in \mathcal {C}({\mathbf {c}})\), it follows from Lemma 5.8 that there exists a chain of GNSs \(S_{1}\supset S_{2}\supset \cdots \supset S_{n-1} \supset S_{n}\) such that \(S_1=S\), \(S_{i+1}=S_{i}\setminus \{{\text {low}}_{\prec }(S_i)\}\) and \(S_n=\mathcal {O}({\mathbf {c}})\). In particular, \((S_1,S_2),(S_2,S_3),\ldots ,(S_{n-1},S_n)\) is a path of edges of \(\mathcal {G}_{\prec }({\mathbf {c}})\) linking S to \(\mathcal {O}({\mathbf {c}})\). If another path of edges of \(\mathcal {G}_{\prec }({\mathbf {c}})\) links S to \(\mathcal {O}({\mathbf {c}})\), then for some \(i\in [n]\) there are two different GNSs \(T_1,T_2 \in \mathcal {C}({\mathbf {c}})\) such that \((S_i,T_1),(S_i,T_2)\in \mathcal {E}_{\prec }\). By the definition of \(\mathcal {G}_{\prec }({\mathbf {c}})\), we have \(T_1=S_i\setminus \{{\text {low}}_{\prec }(S_i)\}=T_2\), which contradicts \(T_1\ne T_2\). Hence, we conclude that \(\mathcal {G}_{\prec }({\mathbf {c}})\) is a rooted tree whose root is the vertex \(\mathcal {O}({\mathbf {c}})\). Now, if T is a child of S, then \(S=T\setminus \{{\text {low}}_{\prec }(T)\}\), and therefore \(T= S\cup \{{\text {low}}_{\prec }(T)\}\). In particular, following the same idea of Remark 5.9, we obtain that \({\text {low}}_{\prec }(T)\in {\text {D}}_{\prec }(S)\). On the other hand, if \({\mathbf {x}}\in {\text {D}}_{\prec }(S)\) then \(T=S\cup \{{\mathbf {x}}\}\) is a child of S, since in this case \(S= T\setminus \{{\mathbf {x}}\}\) with \({\mathbf {x}}={\text {low}}_{\prec }(T)\) because \({\text {L}}(T)={\text {L}}(S)\cup \{{\mathbf {x}}\}\) and \({\mathbf {x}}\in {\text {D}}_{\prec }(S)\). \(\square \)
Observe that different monomial orders \(\prec _1\) and \(\prec _2\) in \({\mathbb {N}}_0^d\) may provide different trees \(\mathcal {G}_{\prec _1}({\mathbf {c}})\) and \(\mathcal {G}_{\prec _2}({\mathbf {c}})\), although both sets of vertices are the same.
Example 5.13
Given \({\mathbf {c}}=(3,2)\), let us compute the rooted tree \(\mathcal {G}_{\prec }({\mathbf {c}})\) of GNSs having corner \({\mathbf {c}}\) by considering the lexicographic order. Since a such GNS S is entirely described by the set \({\text {L}}(S)\), we shall use those sets in the Fig. 1 to illustrate the GNSs in the rooted tree. In Fig. 1, the elements of an \(S\in \mathcal {C}({\mathbf {c}})\) are denoted by the black points and those of \({\text {H}}(S)\) are denoted by the red ones.
Hence, we have a procedure that computes all GNSs with corner \({\mathbf {c}}\), without repetitions, which relies on Theorem 5.12. It is presented in Algorithm 1 as follows.
6 Bounds on the Number of GNS with Fixed Corner
In this section, we provide lower and upper bounds on the number of GNSs having fixed corner. Since the notions of conductor and corner coincide for \(d=1\), the well known bounds due to Backelin [1] for the number of numerical semigroups with fixed Frobenius number give us naturally the following bounds for the number N(c) of numerical semigroups with corner c as
As the lower bound above comes up from the observation that every subset A of \(\{n\in {\mathbb {N}} \ : \ \lceil \frac{c}{2}\rceil \le n < c-1\}\) provides a numerical semigroup with conductor c by considering \(A\cup \mathcal {O}(c)\), where \(\mathcal {O}(c)=\{0, c, c+1,...\}\) is the ordinary numerical semigroup with conductor c, we will employ a generalization of this idea to give a lower bound for the number of GNSs in \({\mathbb {N}}_0^d\), with \(d\ge 2\), having fixed corner \({\mathbf {c}}\in {\mathbb {N}}^d\setminus \{\mathbf {1}\}\).
6.1 A Lower Bound on the Number of GNSs with Fixed Corner
Let \(\mathcal {P}_d\) be the power set of [d]. for all \(J \in \mathcal {P}_d\) and \({\mathbf {y}}=(y_1,\ldots , y_d)\in {\mathbb {N}}_0^d\setminus {\text {C}}(\mathbf {1})\), we define
Remark 6.1
Observe that for all two distinct \(J, J'\in \mathcal {P}_d\), the sets \(\Omega _{J}({\mathbf {y}})\) and \(\Omega _{J'}({\mathbf {y}})\) are disjoint. Furthermore, these sets \(\Omega _{J}({\mathbf {y}})\) split the region \({\text {C}}({\mathbf {y}}-\mathbf {1})\) of \({\mathbb {N}}_0^d\) into \(2^d\) disjoint subsets. The Figures 2 and 3 illustrate such decomposition in \({\mathbb {N}}_0^2\) and \({\mathbb {N}}_0^3\):
Proposition 6.2
Let \(d \ge 2\), \({\mathbf {c}}= (c_1,\ldots ,c_d) \in {\mathbb {N}}^d\), with \(c_j > 1\) for all j and let \(J \in \mathcal {P}_d\) be a nonempty set. Then, for all subset \(A \subseteq \Omega _{J}({\mathbf {c}})\),
is a GNS in \({\mathbb {N}}_0^d\) with corner \({\mathbf {c}}\).
Proof
Let \(\emptyset \ne J \in \mathcal {P}_d\) and \( A \subseteq \Omega _{J }({\mathbf {c}})\). Note that S is a GNS. In fact, \(\mathbf {0} \in S\) and \({\mathbb {N}}_0^d \setminus S\) is finite, since \(\mathcal {O}({\mathbf {c}})\) is an ordinary GNS and \(\mathcal {O}({\mathbf {c}}) \subseteq S\). Now, let \(\varvec{\alpha }, \varvec{\beta }\in S\). If \(\varvec{\alpha }\) or \(\varvec{\beta }\) lies in \(\mathcal {O}({\mathbf {c}})\), then it is clear that \(\varvec{\alpha }+ \varvec{\beta }\in S\). If \(\varvec{\alpha }, \varvec{\beta }\in A\), then \(\varvec{\alpha }+ \varvec{\beta }= (\alpha _1 + \beta _1 , \ldots , \alpha _d + \beta _d) \in \mathcal {O}({\mathbf {c}}) \subseteq S\), since \(\alpha _{j} + \beta _{j} \ge c_{j}\) for all \(j \in J\). Hence, \(A \cup \mathcal {O}({\mathbf {c}})\) is a GNS. Let us prove that S has corner \({\mathbf {c}}\). If \(i \in [d]\) and \(\alpha \ge c_i\), then \((\beta _1,\ldots ,\beta _{i-1}, \alpha , \beta _{i+1},\ldots ,\beta _d) \in \mathcal {O}({\mathbf {c}}) \subseteq S\), since \({\mathbf {c}}= (c_1,\ldots ,c_d)\) is the corner of \(\mathcal {O}({\mathbf {c}})\). Thus, the condition (1) of Definition 3.1 is verified. So, it remains to verify the part (2) of Definition 3.1. Let \(\varvec{\alpha }= (\alpha _1,\ldots , \alpha _d) \in A\). For \(J=[d]\), we have \(1 \le \alpha _i \le c_i - 1\) for all \(i \in [d]\), which implies that \((c_i - 1){\mathbf {e}}_i \notin S\), for all \(i \in [d]\). If \(J\ne [d]\), then there exists \(\ell \in [d] \setminus J\) such that \( \alpha _\ell < c_\ell - 1\), and thus \({\mathbf {c}}- \mathbf {1} \notin S\). Therefore, we conclude that \({\mathbf {c}}\) is the corner of S. \(\square \)
As a consequence, we obtain a lower bound for the number of GNSs in \({\mathbb {N}}_0^d\) with corner \({\mathbf {c}}\) as follows.
Theorem 6.3
Let \(d \ge 2\) and \({\mathbf {c}}= (c_1,\ldots ,c_d)\in {\mathbb {N}}^d\), with \(c_i > 1\) for all i, and let \(N({\mathbf {c}})\) be the number of GNSs in \({\mathbb {N}}_0^d\) with corner \({\mathbf {c}}\). Then
where
Proof
For a fixed \(J \in \mathcal {P}_d\), we have that
Note that, by Remark 6.1, if \(A \ne \emptyset \), then the GNSs of the form \(A \cup \mathcal {O}({\mathbf {c}})\) are all distinct. So, as \(\mathcal {O}({\mathbf {c}}) \in \mathcal {C}({\mathbf {c}})\), we can conclude that
Since \(a-\lceil a/2\rceil =\lfloor a/2\rfloor \) for all integer a, we obtain the stated formula. \(\square \)
Remark 6.4
Despite the idea behind the lower bound given in Theorem 6.3 is the same employed by Backelin [1], it is worth to notice why Theorem 6.3 cannot be applied to the case \(d=1\). The reason is that for \(d=1\) the set \(\Omega _{\{1\}}\) becomes \(\{n\in {\mathbb {N}} \ : \ \lceil \frac{c}{2}\rceil \le n \le c-1\}\), and hence a subset \(A\subseteq \Omega _{\{1\}}\) containing \(c-1\) does not give a numerical semigroup \(A\cup \mathcal {O}(c)\) with conductor c. On the other hand, for \(d\ge 2\), the decomposition of \({\text {C}}({\mathbf {c}}-\mathbf {1})\) into the disjoint regions \(\Omega _{J }({\mathbf {c}})\) takes into account that for each \(i\in [d]\) there are gaps of the GNSs \(A \cup \mathcal {O}({\mathbf {c}})\) with at least one coordinate equal to \(c_i-1\), for \(A\subseteq \Omega _{J}({\mathbf {c}})\) as in Proposition 6.2, no matter the choice of \(J\in \mathcal {P}_d\setminus \{\emptyset \}\).
6.2 An Upper Bound on the Number of GNSs with Fixed Corner
As in the previous subsection, let us consider for each \({\mathbf {c}}\in {\mathbb {N}}^d\setminus \{\mathbf {1}\}\) the decomposition of \({\text {C}}({\mathbf {c}}-\mathbf {1})\) into \(2^d\) subsets
where \(J\in \mathcal {P}_d\), the power set of [d]. We note that, for every \({\mathbf {x}}\in \Omega _\emptyset ({\mathbf {c}})\setminus \{\mathbf {0}\}\), there exists \(n\in {\mathbb {N}}\) such that
The following result is about configurations of points in \({\text {C}}({\mathbf {c}}-\mathbf {1})\) that do not provide GNSs.
Lemma 6.5
Let \({\mathbf {c}}= (c_1,\ldots ,c_d) \in {\mathbb {N}}^d\), with \(c_j > 1\) for all \(j \in [d]\). Then, for all nonempty subset \(A \subseteq \Omega _{\emptyset }({\mathbf {c}})\) with \(A\ne \{\mathbf {0}\}\), there are at least \(2^{|{\mathbf {c}}|-|\Omega _\emptyset ({\mathbf {c}})|-1}\) subsets B of \({\text {C}}({\mathbf {c}}-\mathbf {1})\setminus \Omega _\emptyset ({\mathbf {c}})\) such that
is not a GNS in \({\mathbb {N}}_0^d\).
Proof
If \({\mathbf {x}}\) is an element in a nonempty \(A \subseteq \Omega _{\emptyset }({\mathbf {c}})\), then \(n{\mathbf {x}}\in {\text {C}}({\mathbf {c}}-\mathbf {1}) \setminus \Omega _\emptyset ({\mathbf {c}})\) for some \(n\in {\mathbb {N}}\). Hence, for all subset B of \({\text {C}}({\mathbf {c}}-\mathbf {1}) \setminus \Omega _\emptyset \) that does not contain \(n{\mathbf {x}}\), we have that the \(A \cup B \cup \mathcal {O}({\mathbf {c}})\) is not a GNS since it is not closed to addition. As \(|{\text {C}}({\mathbf {c}}-\mathbf {1}) \setminus \Omega _\emptyset ({\mathbf {c}})|=|{\mathbf {c}}|-|\Omega _\emptyset ({\mathbf {c}})|\), there are exactly \(2^{|{\mathbf {c}}|-|\Omega _\emptyset ({\mathbf {c}})|-1}\) such subsets of \({\text {C}}({\mathbf {c}}-\mathbf {1})\setminus \Omega _\emptyset ({\mathbf {c}})\). \(\square \)
A consequence of the previous lemma is the following upper bound for \(N({\mathbf {c}})\).
Theorem 6.6
For \({\mathbf {c}}= (c_1,\ldots ,c_d)\in {\mathbb {N}}^d\), with \(c_i > 1\) for all \(i=1,\ldots ,d\), let \(N({\mathbf {c}})\) be the number of GNSs in \({\mathbb {N}}_0^d\) with corner \({\mathbf {c}}\). Then
Proof
In order to bound \(N({\mathbf {c}})\) we will count the configurations of points in \({\text {C}}({\mathbf {c}}-\mathbf {1})\) which do not provide GNSs. To begin with, we note that there are \(2^{|\Omega _\emptyset ({\mathbf {c}})|-1}-1\) possibilities of nonempty subsets A in \(\Omega _{\emptyset }({\mathbf {c}})\), different from \(\{\mathbf {0}\}\). From each one of these subsets A, there are \(2^{|{\mathbf {c}}|-|\Omega _\emptyset ({\mathbf {c}})|-1}\) possibilities of subsets B in \({\text {C}}({\mathbf {c}}-\mathbf {1})\setminus \Omega _\emptyset ({\mathbf {c}})\) such that \(A\cup B\cup \mathcal {O}({\mathbf {c}})\) is not a GNS, by the previous lemma. Hence, putting together these possibilities, there are at least \((2^{|\Omega _\emptyset ({\mathbf {c}})|-1}-1)\cdot 2^{|{\mathbf {c}}|-|\Omega _\emptyset ({\mathbf {c}})|-1}\) configurations of points in \({\text {C}}({\mathbf {c}}-\mathbf {1})\setminus \{\mathbf {0}\}\) that when joined to \(\mathcal {O}({\mathbf {c}})\) do not provide GNSs. Now, since \({\text {C}}({\mathbf {c}}-\mathbf {1})\setminus \{\mathbf {0}\}\) has \(|{\mathbf {c}}|- 1\) elements, there are \(2^{|{\mathbf {c}}|-1}\) possibilities of sets containing \(\mathbf {0}\) in \({\text {C}}({\mathbf {c}}-\mathbf {1})\). From this amount, by using the lower bound on subsets of \({\text {C}}({\mathbf {c}}-\mathbf {1})\) that do not give GNSs, we obtain that the number of GNSs with corner \({\mathbf {c}}\) is upper bounded by \(2^{|{\mathbf {c}}|-1}-(2^{|\Omega _\emptyset ({\mathbf {c}})|-1}-1)\cdot 2^{|{\mathbf {c}}|-|\Omega _\emptyset ({\mathbf {c}})|-1}\). \(\square \)
Next, we present Table 1 with the lower and upper bounds obtained in Theorems 6.3 and 6.6 and the exact values of \(N({\mathbf {c}})\), which has been computed using the Algorithm 1, implemented in GAP [11] with the package numericalsgps [8]. Observe that every permutation in the coordinates of a given \({\mathbf {c}}\) provides the same lower bound, upper bound and exact value of \(N({\mathbf {c}})\).
7 Concluding Remarks
In the preceding sections, we addressed the natural relations of the corner element with other invariants of a GNS, the problem of computing all GNSs with fixed corner, and basic estimates on the number of such GNSs. As naturally occurs when an invariant is introduced, many questions arise. We list here some of them. What is the magnitude of the number of GNSs in \({\mathbb {N}}_0^d\) with a fixed corner? We saw that these GNSs can be divided into two classes: what can be said about the proportion of Frobenius and non-Frobenius GNSs with fixed corner? Apart from some known families of Frobenius GNS, which other families of GNSs could be described in terms of the corner element? In the spirit of the recent advances in numerical semigroups (see the surveys [7, 16]), is there any approach involving the corner element for counting GNSs in \({\mathbb {N}}_0^d\) by genus or dealing with the generalized Wilf conjecture?
References
Backelin, J.: On the number of semigroups of natural numbers. Math. Scand. 66, 197–215 (1990)
Cisto, C., Delgado, M., García-Sánchez, P.A.: Algorithms for generalized numerical semigroups. J. Algebra Appl. 20(5), 2150079 (2021)
Cisto, C., Failla, G., Utano, R.: On the generators of a generalized numerical semigroup. Analele Universitatii “Ovidius” Constanta - Seria Matematica 27(1), 49–59 (2019)
Cisto, C., Failla, G., Peterson, C., Utano, R.: Irreducible generalized numerical semigroups and uniqueness of the Frobenius element. Semigroup Forum 99, 481–495 (2019)
Cisto, C., Dipasquale, M., Failla, G., Flores, Z., Peterson, C., Utano, R.: A generalization of Wilf’s conjecture for generalized numerical semigroups. Semigroup Forum 101, 303–325 (2020)
Cisto, C., Tenório, W.: On almost-symmetry in generalized numerical semigroups. Commun. Algebra 49(6), 2337–2355 (2021)
Delgado, M.: Conjecture of Wilf: a survey. In: Barucci, V., Chapman, S., D’Anna, M., Fröberg, R. (eds.) Numerical Semigroups, vol. 40. Springer, Cham (2020)
Delgado, M., M., García-Sánchez, P. A., Morais, J.: NumericalSgps, a package for numerical semigroups, Version 1.2.2. https://gap-packages.github.io/numericalsgps, Refereed GAP package
Díaz-Ramírez, J.D., García-García, J.I., Sánchez-R-Navarro, A., Vigneron-Tenorio, A.: A geometrical characterization of proportionally modular affine semigroups. Results Math. 75, 99 (2020)
Failla, G., Peterson, C., Utano, R.: Algorithms and basic asymptotics for generalized numerical semigroups in \({\mathbb{N}}^d\). Semigroup Forum 92(2), 460–473 (2016)
GAP – Groups, algorithms, and programming, Version 4.10.0. https://www.gap-system.org
García-García, J.I., Moreno-Frías, M.A., Vigneron-Tenorio, A.: Proportionally modular affine semigroups. J. Algebra Appl. 17(1), 1850017 (2018)
García-García, J.I., Marín-Aragón, D., Vigneron-Tenorio, A.: An extension of Wilf’s conjecture to affine semigroups. Semigroup Forum 96(2), 396–408 (2018)
García-García, J.I., Ojeda, I., Rosales, J.C., Vigneron-Tenorio, A.: On pseudo-frobenius elements of submonoids of \({\mathbb{N}}^d\). Collect. Math. 71, 189–204 (2020)
García-Sánchez, P.A., Rosales, J.C.: “Numerical Semigroups’’, Developments in Mathematics, vol. 20. Springer, New York (2009)
Kaplan, N.: Counting numerical semigroups. Amer. Math. Mon. 124, 862–875 (2017)
Singhal, D., Lin, Y.: Frobenius allowable gaps of generalized numerical semigroups, arXiv:2103.15983
Acknowledgements
The authors wish to thank the anonymous referee for her/his careful reading and valuable comments that helped to improve the previous version of this work.
Funding
The third author was supported by CNPq and FAPEMIG (grant numbers 307037/2019-3 and APQ-01661-17, respectively). The authors have no relevant financial or non-financial interests to disclose. All authors contributed to the study conception and design.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Competing interests
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Bernardini, M., Tenório, W. & Tizziotti, G. The Corner Element of Generalized Numerical Semigroups. Results Math 77, 141 (2022). https://doi.org/10.1007/s00025-022-01682-9
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00025-022-01682-9