If \(S\) is a numerical semigroup, we will denote by \({\mathrm F}(S),\) \({\mathrm g}(S)\) and \({\mathrm t}(S),\) the Frobenius number, the genus and the type of \(S,\) respectively. We will also denote by \({\mathrm n}(S)\) and \({\mathrm i}(S)\) the cardinality of the sets \(\{s\in S\mid s<{\mathrm F}(S)\}\) and \(\{x\in \mathbb{N}\backslash S\mid x-1\in S\},\) respectively. In this paper we will study the \(\mathrm{PTT}\)-semigroups. That is, perfect numerical semigroups with type two. In particular, we will see that if \(S\) is a numerical semigroup, then the following conditions are equivalent: 1) \(S\) is a \(\mathrm{PTT}\)-semigroup; 2) The set of pseudo-Frobenius numbers of \(S\) is \(\{{\mathrm F}(S),{\mathrm F}(S)-1\}\); 3) \(S\) is maximal in the set \(\{T\mid T \mbox{ is a numerical semigroup } T\cap \{{\mathrm F}(S),{\mathrm F}(S)-1\}=\emptyset \mbox{ and } {\mathrm t}(T)=2\}\); and 4) \({\mathrm F}(S)-1\notin S\) and \({\mathrm n}(S)={\mathrm g}(S)-{\mathrm i}(S).\) As an application of these characterizations, we will provide several algorithms for calculating all the \(\mathrm{PTT}\)-semigroups with a given Frobenius number.
Denote by \(\mathbb{Z}\) the set of integer numbers and \(\mathbb{N}=\{z\in \mathbb{Z}\mid z\ge 0\}\). A subset \(M\) of \(\mathbb{N}\) is a submonoid of \((\mathbb{N},+),\) if \(x+y \in M\) for all \(x,y \in M\) and \(0\in M.\) A numerical semigroup is a submonoid \(S\) of \((\mathbb{N},+)\) such that \(\mathbb{N}\backslash S\) has finite cardinality.
If \(S\) is a numerical semigroup, then \({\mathrm m}(S)=\min(S\backslash \{0\}),\) \({\mathrm F}(S)={\mathrm{max}}(\mathbb{Z}\backslash S)\) and \({\mathrm g}(S)=\#(\mathbb{N}\backslash S)\), where \(\#A\) denotes the cardinality of a set \(A,\) are three important invariants of \(S\) called multiplicity, Frobenius number and genus of \(S\), respectively.
If \(A\) is a non-empty subset of \(\mathbb{N}\), then we denote by \(\langle A \rangle\) the submonoid of \((\mathbb{N},+)\) generated by \(A\), that is, \[\langle A \rangle=\{\alpha_1a_1+\dots+\alpha_na_n \mid n\in \mathbb{N}\backslash\{0\}, \, \{a_1,\dots, a_n\}\subseteq A \;\mbox{ and }\; \{\alpha_1,\dots,\alpha_n\}\subseteq \mathbb{N}\}.\] In [12, Lemma 2.1] it is shown that \(\langle A \rangle\) is a numerical semigroup if and only if \({\mathrm{gcd}}(A)=1.\)
If \(M\) is a submonoid of \((\mathbb{N},+)\) and \(M=\langle A \rangle\), then we say that \(A\) is a system of generators of \(M\). Moreover, if \(M\neq \langle B \rangle\) for all \(B \varsubsetneq A\), then we will say that \(A\) is a minimal system of generators of \(M\). In [12, Corollary 2.8] it is shown that every submonoid of \((\mathbb{N},+)\) has a unique minimal system of generators, which in addition is finite. We denote by \({\mathrm{ msg }}(M)\) the minimal system of generators of \(M\). The cardinality of \({\mathrm{ msg }}(M)\) is called the embedding dimension of \(M\) and will be denoted by \({\mathrm e}(M).\)
If \(S\) is a numerical semigroup, the set of elements in \({\mathrm G}(S)=\mathbb{N}\backslash S\) is known as the set of gaps of \(S.\) An element \(x\) of \({\mathrm G}(S)\) is called an isolated gap of \(S\) if \(\{x-1,x+1\}\subset S.\) Following the notation introduced in [5], a numerical semigroup is perfect if it does not have isolated gaps.
An integer \(z\) is a pseudo-Frobenius number of a numerical semigroup \(S\), if \(z\notin S\) and \(z+s\in S\) for all \(s\in S\backslash \{0\}.\) We will denote by \({\mathrm {PF}}(S)\) the set of pseudo-Frobenius numbers of \(S.\) The cardinality of \({\mathrm {PF}}(S)\) is an important invariant of \(S\) (see [3] and [1]) called the type of \(S\) and denoted by \({\mathrm t}(S).\)
A \(\mathrm{PTT}\)–semigroup is a perfect numerical semigroup of type two. The main goal of this paper is to study this kind of semigroups.
The paper is structured as follows. In Section 2, we will prove that a numerical semigroup \(S\) is a \(\mathrm{PTT}\)-semigroup if and only if \({\mathrm {PF}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\}.\) This fact will allow us to give a first algorithm to compute the set of all \(\mathrm{PTT}\)-semigroups with a fixed Frobenius number.
If \(S\) is a \(\mathrm{PTT}\)-semigroup, then \({\mathrm F}(S)-1\notin S.\) Given a positive integer, denote by \(\mathscr{C}(F)=\{S\mid S \;\mbox{ is a numerical semigroup, }\; {\mathrm F}(S)=F \;\mbox{ and }\; F-1\notin S\}.\) In Section 3, we will see that \(\mathscr{C}(F)\) is a covariety. This fact, together with the results of [7], allows us to present an algorithm which computes all the elements of \(\mathscr{C}(F).\) From this algorithm, we easily deduce another, to compute all the \(\mathrm{PTT}\)-semigroups with Frobenius number \(F.\)
Following the notation introduced in [7], an \({\mathrm{ANI}}\)-semigroup is an atomic numerical semigroup which is not irreducible. In Section 4, we will see that the maximal elements (with respect to inclusion order) of \(\mathscr{C}(F)\) are the \({\mathrm{ANI}}\)-semigroups with Frobenius number \(F.\) Besides, we prove that every \(\mathrm{PTT}\)-semigroup with Frobenius number \(F\) is a maximal element in \(\mathscr{C}(F).\) As a result of all of the above, we will present a third algorithm that calculates all \(\mathrm{PTT}\)-semigroups with Frobenius number \(F\).
An element \(x\) from a numerical semigroup \(S\) is called small if \(x< {\mathrm F}(S).\) Denote by \({\mathrm N}(S)\) (respectively \({\mathrm n}(S)\)) the set formed by all the small elements of \(S\) (respectively the cardinality of \({\mathrm N}(S)\)).
A gap \(x\) of a numerical semigroup \(S\) is initial if \(x-1\in S.\) Denote by \({\mathrm I}(S)\) (respectively, \({\mathrm i}(S)\)) the set consisting of the initial gaps of \(S\) (respectively, the cardinality of \({\mathrm i}(S)\)). In Section 5, we show that if \(S\) is a numerical semigroup such that \({\mathrm F}(S)-1\notin S,\) then \({\mathrm n}(S)\leq {\mathrm g}(S)-{\mathrm i}(S).\) Moreover, we prove that \(S\) is a \(\mathrm{PTT}\)-semigroup if and only if \({\mathrm n}(S)={\mathrm g}(S)-{\mathrm i}(S).\)
If \(a\) and \(b\) are integers, then we denote by \([a,b]=\{x\in \mathbb{Z}\mid a\leq x\leq b\}.\) Let \(A\) be a set. An interval of \(A\) is an interval \([a,b]\) such that \([a,b]\subseteq A.\) We will say that an interval is maximal, if it is not properly included in any other interval of \(A.\) Denote by \({\mathrm {MI}}(A)\) the set formed by the maximal intervals of \(A.\) In Section 6, we will see that if \(S\) is a numerical semigroup, then \(\#({\mathrm {MI}}({\mathrm N}(S)))=\#{\mathrm {MI}}({\mathrm G}(S)).\) In addition, we prove that an element \(S\) from \(\mathscr{C}(F)\) is a \(\mathrm{PTT}\)-semigroup if and only if there is a bijective map \(f:{\mathrm {MI}}({\mathrm G}(S))\longrightarrow {\mathrm {MI}}({\mathrm N}(S))\) verifying that \(\#f(X)=\#X-1\) for all \(X\in {\mathrm {MI}}({\mathrm G}(S)).\)
It is clear that \({\mathrm {PF}}(\mathbb{N})=\{-1\}\) and so \({\mathrm t}(S)=1.\) Consequently, if \(S\) is a \(\mathrm{PTT}\)-semigroup, then \(S\neq \mathbb{N}.\)
Let \(S\) be a perfect numerical semigroup, then \({\mathrm F}(S)\) is not an isolated gap of \(S\) and so \({\mathrm F}(S)-1\notin S.\)
If \(S\) is a numerical semigroup, then over \(\mathbb{Z}\) we define the following order relation: \(a\leq_S b\) if and only if \(b-a\in S.\) The following result is [12, Proposition 2.19].
Lemma 2.1. If \(S\) is a numerical semigroup, then the following conditions are verified:
(i) \({\mathrm {PF}}(S)=\mathrm{Maximals}_{\leq_S}(\mathbb{Z}\backslash S).\)
(ii) \(x\in \mathbb{Z}\backslash S\) if and only if \(f-x\in S\) for some \(f\in {\mathrm {PF}}(S).\)
The next result appears in [6, Theorem 6].
Theorem 2.2. Let \(S\) be a numerical semigroup such that \({\mathrm t}(S)=2.\) Then, \(S\) is perfect if and only if \({\mathrm F}(S)-1\notin S.\)
As a consequence, we can characterize the \(\mathrm{PTT}\)-semigroups.
Corollary 2.3. Let \(S\) be a numerical semigroup. Then \(S\) is a \(\mathrm{PTT}\)-semigroup if and only if \({\mathrm {PF}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\}.\)
Proof. (Necessity). If \(S\) is a \(\mathrm{PTT}\)-semigroup, then \({\mathrm t}(S)=2\) and \(S\) is perfect. Thus, \({\mathrm F}(S)-1\notin S.\) By Lemma 2.1, we assert that \({\mathrm {PF}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\}.\)
(Sufficiency). If \({\mathrm {PF}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\},\) then \({\mathrm t}(S)=2\) and \({\mathrm F}(S)-1\notin S.\) By Theorem 2.2, we have that \(S\) is perfect. Hence, \(S\) is a \(\mathrm{PTT}\)-semigroup. \(\square\)
Our next objective in this section will be to see what conditions a positive integer \(F\) must satisfy in order for there to be a \(\mathrm{PTT}\)-semigroup with Frobenius number \(F.\)
The following result is [11, Theorem 2.10].
Lemma 2.4. Let \(f_1\) and \(f_2\) be positive integers such that \(f_1<f_2\) and we will denote by \[\alpha(f_1,f_2)=\left\{\begin{array}{lcl} 2f_1-f_2 & & \mbox{ if } f_2 \mbox{ is odd, }\\ f_1-\frac{f_2}{2} & & \mbox { if } f_2 \mbox{ is even.} \end{array}\right.\]
Then there exists a numerical semigroup \(S\) such that \({\mathrm {PF}}(S)=\{f_1,f_2\}\) if and only if \(\frac{f_2}{2}<f_1\) and \(\alpha(f_1,f_2)\) does not divide any element of the set \(\{f_1,f_2, f_2-f_1\}.\)
By applying Corollary 2.3 and Lemma 2.4, we deduce the following result.
Proposition 2.5. We have that \(\{{\mathrm F}(S)\mid S \mbox{ is a }\mathrm{PTT}\mbox{-semigroup}\}=\{5,7,\rightarrow\},\) where the symbol \(\rightarrow\) means that every integer greater than or equal to\(7\) belongs to the set.
It is easy to see that \(\langle 3,7,8 \rangle\) is the unique \(\mathrm{PTT}\)-semigroup with Frobenius number \(5.\) Our next aim in this section will be to show an algorithm that given an integer \(F\) greater or equal to \(7\), computes the set \[{\mathscr{P}}(F)=\{S\mid S \mbox{ is a } \mathrm{PTT}\mbox{-semigroup and }{\mathrm F}(S)=F \}.\]
In the semigroup literature, there are numerous algorithms that, given a positive integer \(F\), compute the set \(\{S\mid S \mbox{ is a numerical semigroup and } {\mathrm F}(S)=F \}\) (see for instance [2] or [7]). Proposition 2.2 from [12], provides us an algorithm that, given a numerical semigroup \(S\), calculates \({\mathrm {PF}}(S).\)
We are now ready to present the announced algorithm.
Algorithm 2.6. Input: An integer \(F\) greater or equal to \(7.\)
Output: \({\mathscr{P}}(F)=\{S\mid S \mbox{ is a } \mathrm{PTT}\mbox{-semigroup and }{\mathrm F}(S)=F \}.\)
(1) Compute \(A=\{S\mid S \mbox{ is a numerical semigroup and }{\mathrm F}(S)=F \}.\)
(2) Compute \(B=\{S\in A \mid F-1\notin S \}.\)
(3) Return \(\{S\in B \mid {\mathrm {PF}}(S)=\{F, F-1\} \}.\)
Next, we illustrate how the previous algorithm works with an example.
Example 2.7. We are going to compute the set \[{\mathscr{P}}(7)=\{S\mid S \mbox{ is a } \mathrm{PTT}\mbox{-semigroup and }{\mathrm F}(S)=7 \}.\]
(1) By using Algorithm 1 from [7], we obtain \(A=\{\{0,8, \rightarrow\}, \{0,4,8, \rightarrow\}, \{0,5,8, \rightarrow\}, \{0,6,8, \rightarrow\},\{0,4,5,8, \rightarrow\},\) \(\{0,4,6,8, \rightarrow\}, \{0,3,6,8, \rightarrow\}, \{0,2,4,6,8, \rightarrow\} \}.\)
(2) \(B=\{\{0,8, \longrightarrow\}, \{0,4,8, \longrightarrow\}, \{0,5,8, \longrightarrow\}, \{0,4,5,8, \longrightarrow\}\}.\)
(3)\({\mathscr{P}}(7)=\{ \{0,4,5,8, \longrightarrow\}\}.\)
A covariety is a non-empty family \(\mathscr{C}\) of numerical semigroups that satisfies the following conditions:
1.\(\mathscr{C}\) has a minimum element, with respect to inclusion order. It will be denoted by \(\Delta(\mathscr{C}).\)
2. If \(\{S,T\}\subseteq \mathscr{C},\) then \(S\cap T \in \mathscr{C}.\)
3. If \(S\in \mathscr{C}\) and \(S\neq \Delta(\mathscr{C}),\) then \(S\backslash \{{\mathrm m}(S)\}\in \mathscr{C}.\)
The following result has an easy proof.
Proposition 3.1. If \(F\) is an integer greater than or equal to two, then \[\mathscr{C}(F)=\{S\mid S \mbox{ is a numerical semigroup, }{\mathrm F}(S)=F \mbox{ and }F-1\notin S\},\] is a covariety and its minimum is \(\Delta(\mathscr{C}(F))=\{0,F+1,\rightarrow \}.\)
A graph is a pair \(G = (V, E)\), where \(V\) is a non-empty set whose elements are called vertices and \(E\) is a subset of \(\{(u,v)\in V \times V \mid u\neq v\},\) whose elements are called edges. A path of length \(n\) connecting the vertices \(u\) and \(v\) of \(G\), is a sequence of different edges of the form \((v_0,v_1), (v_1,v_2),\ldots,(v_{n-1},v_n)\) such that \(v_0=u\) and \(v_n=v\).
A graph \(G\) is a tree, if there exists a vertex \(r\) (known as the root of \(G\)) such that for any other vertex \(u\) of \(G\) there is a unique path connecting \(u\) and \(r\). If\((u,v)\) is an edge of \(G\), we say that \(u\) is a child of \(v\).
Define the graph \({\mathrm G}(\mathscr{C}(F))\) as follows: \(\mathscr{C}(F)\) is its set of vertices and \((S,T)\in \mathscr{C}(F)\times \mathscr{C}(F)\) is an edge if \(T=S\backslash \{{\mathrm m}(S)\}.\)
The following result can be obtained by applying Proposition 3.1 and Proposition 2.3 from [7].
Proposition 3.2. If \(F\) is an integer greater than or equal to two, then \({\mathrm G}(\mathscr{C}(F))\) is a tree with root \(\Delta(\mathscr{C}(F))=\{0,F+1,\rightarrow \}.\)
If we know the children of each vertex, then we can recursively construct a tree as follows: we start at the root and connect each vertex already constructed with all its children using one edge. Thus, it is essential to know the children of an arbitrary vertex of the tree \({\mathrm G}(\mathscr{C}(F))\). To show a characterization of these, we need to introduce some concepts and results.
We say that an integer \(z\) is a special gap of a numerical semigroup \(S\), if \(z\notin S\) and \(S\cup \{z\}\) is a numerical semigroup. Denote by \({\mathrm {SG}}(S)\) the set consisting of all special gaps of \(S.\)
The following result can be deduced from [12, Proposition 2.4].
Proposition 3.3. If \(F\) is an integer greater than or equal to two and \(S\in \mathscr{C}(F)\), then the set formed by the children of \(S\) in the tree \({\mathrm G}(\mathscr{C}(F))\) is \(\{S\cup \{x\}\mid x\in {\mathrm {SG}}(S),\, x<{\mathrm m}(S) \mbox{ and } x\notin \{F,F-1\}\}.\)
From [12, Proposition 4.33], follows the next result which shows a characterisation of the set of special gaps of a numerical semigroup.
Lemma 3.4. If \(S\) is a numerical semigroup, then \({\mathrm {SG}}(S)=\{x\in {\mathrm {PF}}(S)\mid 2x\in S\}.\)
As we have already indicated in the comment before Algorithm 2.6, we have an algorithm for calculating \({\mathrm {PF}}(S).\) Thus, applying Lemma 3.4, we now have an algorithm for computing the set \({\mathrm {SG}}(S).\)
The following result is easily obtained from Proposition 3.1 and [7, Proposition 2.1].
Lemma 3.5. If \(F\) is an integer greater than or equal to two, then \(\mathscr{C}(F)\) is a finite set.
Given a tree \(G=(V,E)\) and \(x\in V,\) we define the depth of \(x\), denoted by \(\mathrm{d}(x)\) as the length of the only path that exists connecting \(x\) with the root of \(G.\) If \(k\in \mathbb{N},\) let \({\mathrm N}(G,k)=\{x\in V\mid \mathrm{d}(x)=k\}.\)
The proof of the next result is immediate.
Lemma 3.6. Let \(G=(V,E)\) be a tree and \(k\in \mathbb{N}.\) Then \({\mathrm N}(G,k+1)=\{x\in V\mid x \mbox{ is a child of an element of }{\mathrm N}(G,k)\}.\)
We are now in a position to show an algorithm that, based on the results of [7], calculates \(\mathscr{C}(F).\)
Algorithm 3.7. Input: An integer \(F\) greater or equal to \(2.\)
Output: \(\mathscr{C}(F).\)
(1) \(A=B=\{\Delta(\mathscr{C}(F))\}.\)
(2) For all \(S\in B\) compute \(\gamma(S)=\{x\in {\mathrm {SG}}(S)\mid x<{\mathrm m}(S) \mbox{ and } x\notin \{F, F-1\} \}.\)
(3) If \(\displaystyle \bigcup_{S\in B} \gamma(S)= \emptyset,\) then return \(A.\)
(4) \(C=\displaystyle \bigcup_{S\in B} \{S\cup \{x\}\mid x\in \gamma(S)\}.\)
(5) \(A:=A\cup C,\) \(B:=C\) and go to Step \((2).\)
The following example illustrates how the previous algorithm works.
Example 3.8. We are going to compute \(\mathscr{C}(7)\), by using Algorithm 3.7.
\(A=B=\{\{0,8,\rightarrow\}\}.\)
\(\theta(\{0,8,\rightarrow\})=\{4,5\}.\)
\(C=\{\{0,4,8,\rightarrow\}, \{0,5,8,\rightarrow\} \}.\)
\(A=\{\{0,8,\rightarrow\}, \{0,4,8,\rightarrow\}, \{0,5,8,\rightarrow\}\}\) and \(B=\{\{0,4,8,\rightarrow\},\{0,5,8,\rightarrow\}\}.\)
\(\theta(\{0,4,8,\rightarrow\})=\emptyset\) and \(\theta(\{0,5,8,\rightarrow\})=\{4\}.\)
\(C=\{\{0,4,5,8,\rightarrow\}\}.\)
\(A=\{\{0,8,\rightarrow\}, \{0,4,8,\rightarrow\}, \{0,5,8,\rightarrow\}, \{0,4,5,8,\rightarrow\}\}\) and \(B=\{\{0,4,5,8,\rightarrow\}\}.\)
\(\theta(\{0,4,5,8,\rightarrow\})=\emptyset.\)
Therefore, Algorithm 3.7 returns \[\mathscr{C}(7)= \{\{0,8,\rightarrow\}, \{0,4,8,\rightarrow\}, \{0,5,8,\rightarrow\}, \{0,4,5,8,\rightarrow\}\}.\]
Below we show an alternative algorithm to Algorithm 2.6 for calculating \({\mathscr{P}}(F).\)
Algorithm 3.9. Input: An integer \(F\) greater or equal to \(7.\)
Output: \({\mathscr{P}}(F)=\{S\mid S \mbox{ is a } \mathrm{PTT}\mbox{-semigroup and }{\mathrm F}(S)=F \}.\)
(1) By using Algorithm 3.7, compute \(\mathscr{C}(F).\)
(2) Return \(\{S\in \mathscr{C}(F) \mid {\mathrm {PF}}(S)=\{F, F-1\} \}.\)
In the following example, we can see how the above algorithm is executed.
Example 3.10. We are going to compute \({\mathscr{P}}(7)\), by using Algorithm 3.9.
\(\mathscr{C}(7)= \{\{0,8,\rightarrow\}, \{0,4,8,\rightarrow\}, \{0,5,8,\rightarrow\}, \{0,4,5,8,\rightarrow\}\}.\)
\({\mathscr{P}}(7)=\{ \{0,4,5,8,\rightarrow\}\}.\)
Given \(X\subseteq \mathbb{N},\) we denote by \({\mathscr{L}}(X)=\{S\mid S\mbox{ is a numerical semigroup and } X\cap S=\emptyset\}\) and \({\mathrm M}(X)=\mathrm{Maximals}({\mathscr{L}}(X))\) with respect to the inclusion order.
The next result is deduced from [13, Proposition 12].
Lemma 4.1. Let \(S\) be a numerical semigroup, \(X\subseteq \mathbb{N}\) and \(S\cap X=\emptyset.\) Then \(S\in {\mathrm M}(X)\) if and only if \({\mathrm {SG}}(S)\subseteq X.\)
The following result has an immediate proof.
Lemma 4.2. Let \(S\) be a numerical semigroup and \(F\) an integer greater than or equal to \(3.\) Then \(S\) is a maximal element of \(\mathscr{C}(F)\) if and only if \(S\in {\mathrm M}(\{F,F-1\}).\)
Theorem 4.3. Let \(S\) be a numerical semigroup and \(F\) an integer greater than or equal to \(3.\) Then \(S\) is a maximal element of \(\mathscr{C}(F)\) if and only if \({\mathrm {SG}}(S)=\{F,F-1\}.\)
Proof. (Necessity). If \(S\) is a maximal element of \(\mathscr{C}(F),\) then by applying Lemma 4.2, we have that \(S\in {\mathrm M}(\{F,F-1\}).\) Therefore, Lemma 4.1 asserts that \({\mathrm {SG}}(S)\subseteq \{F,F-1\}.\) As clearly \(\{F,F-1\}\subseteq {\mathrm {SG}}(S),\) then we can say that \({\mathrm {SG}}(S)=\{F,F-1\}.\)
(Sufficiency). If \({\mathrm {SG}}(S)=\{F,F-1\},\) then by Lemma 4.1, we have that \(S\in {\mathrm M}(\{F,F-1\}).\) By applying now, Lemma 4.2, we conclude that \(S\) is a maximal element of \(\mathscr{C}(F).\) \(\square\)
Lemma 4.4. Let \(S\) be a numerical semigroup such that \({\mathrm F}(S)\ge 3.\) If \({\mathrm {PF}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\},\) then \({\mathrm {SG}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\}.\)
Proof. If \({\mathrm {PF}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\},\) then by using Lemma 3.4, we can easily deduce that \({\mathrm {SG}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\}.\) \(\square\)
The reciprocal of the previous lemma is false, as shown in the following example.
Example 4.5. Let \(S=\{0,5,6,9,\rightarrow\}.\) Then it is clear that \({\mathrm {PF}}(S)=\{4,7,8\}\), nevertheless \({\mathrm {SG}}(S)=\{7,8\}.\)
Proposition 4.6. If \(F\) is an integer greater than or equal to \(3,\) then \[{\mathscr{P}}(F)=\{S\in {\mathrm M}(\{F,F-1\})\mid {\mathrm t}(S)=2\}.\]
Proof. If \(S\in {\mathscr{P}}(F),\) then \({\mathrm t}(S)=2\) and by Corollary 2.3, we know that \({\mathrm {PF}}(S)=\{F,F-1\}.\) By applying Lemma 4.4, we have that \({\mathrm {SG}}(S)=\{F,F-1\}.\) By using now, Lemma 4.2 and Theorem 4.3, we obtain that \(S\in {\mathrm M}(\{F,F-1\}).\)
Let us now consider the other inclusion. If \(S\in {\mathrm M}(\{F,F-1\})\) and \({\mathrm t}(S)=2,\) then by applying Lemma 4.2 and Theorem 4.3, we have that \({\mathrm {PF}}(S)=\{F,F-1\}.\) So, Corollary 2.3 allows us to conclude that \(S\in {\mathscr{P}}(F).\) \(\square\)
Following the terminology introduced in [10], a numerical semigroup is irreducible if it cannot be expressed as the intersection of two numerical semigroups that contain it properly. In [10], it is shown that a numerical semigroup is irreducible if and only if it is maximal in the set of all numerical semigroups with Frobenius number \({\mathrm F}(S).\) The results of [3] (respectively [1]) allow us to state that the irreducible numerical semigroups with odd Frobenius number (respectively even)are the symmetric numerical semigroups (respectively pseudo-symmetric numerical semigroups). These last two kinds of numerical semigroups have been extensively studied and are of great interest in Ring Theory (see [4] and [1]).
According to the terminology established in [9], a numerical semigroup \(S\) is atomic if it cannot be expressed as the intersection of two numerical semigroups with Frobenius number \({\mathrm F}(S)\) that properly contain it. It is clear that every irreducible numerical semigroup is an atomic numerical semigroup. As we mentioned in Introduction, an \({\mathrm{ANI}}\)-semigroup is an atomic numerical semigroup that is not irreducible.
The following result is Corollary 2.3 from [8].
Proposition 4.7. A numerical semigroup \(S\) is an \({\mathrm{ANI}}\)-semigroup if and only if \(\#{\mathrm {SG}}(S)=2.\)
Corollary 4.8. If \(S\) is a \(\mathrm{PTT}\)-semigroup, then \(S\) is an \({\mathrm{ANI}}\)-semigroup.
Proof. If \(S\) is a \(\mathrm{PTT}\)-semigroup, then by Proposition 4.6, we know that \(S\in {\mathrm M}(\{F(S),F(S)-1\}).\) By applying now Lemma 4.2 and Theorem 4.3, we obtain that \({\mathrm {SG}}(S)=\{{\mathrm F}(S),{\mathrm F}(S)-1\}.\) Finally, Proposition 4.7 allows us to state that \(S\) is an \({\mathrm{ANI}}\)-semigroup. \(\square\)
In [11], an algorithm is shown for calculating \({\mathrm M}(\{F,F-1\}).\) Therefore, by using Proposition 4.6, we can design the following algorithm which computes \({\mathscr{P}}(F)\).
Algorithm 4.9. Input: An integer \(F\) greater or equal to \(7.\)
Output: \({\mathscr{P}}(F)=\{S\mid S \mbox{ is a } \mathrm{PTT}\mbox{-semigroup and }{\mathrm F}(S)=F \}.\)
(1) Computes \({\mathrm M}(\{F,F-1\}).\)
(2) Return \(\{S\in {\mathrm M}(\{F,F-1\}) \mid {\mathrm t}(S)=2 \}.\)
Let us consider an example to illustrate the execution of the above algorithm.
Example 4.10. We will use Algorithm 4.9 to obtain \({\mathscr{P}}(7).\)
\({\mathrm M}(\{7,6\})=\{\{0,4,5,8,\rightarrow\}\}.\)
\({\mathscr{P}}(7)=\{\{0,4,5,8,\rightarrow\}\}.\)
Let us recall that if \(S\) is a numerical semigroup then \({\mathrm N}(S)=\{x\in S\mid x<{\mathrm F}(S)\}\) and \({\mathrm I}(S)=\{x\in {\mathrm G}(S)\mid x-1\in S\}.\) Let us also remember that \({\mathrm n}(S)\) and \({\mathrm i}(S)\) denote the cardinality of \({\mathrm N}(S)\) and \({\mathrm I}(S),\) respectively.
Example 5.1. If \(S=\langle 5,7,9 \rangle=\{0,5,7,9,10,12,14,\rightarrow\},\) then \({\mathrm N}(S)=\{0,5,7,9,10,12\},\) \({\mathrm n}(S)=6,\) \({\mathrm I}(S)=\{1,6,8,11,13\}\) and \({\mathrm i}(S)=5.\)
Proposition 5.2. If \(S\) is a numerical semigroup such that \({\mathrm F}(S)-1\in {\mathrm G}(S),\) then \({\mathrm n}(S)\leq {\mathrm g}(S)-{\mathrm i}(S).\)
Proof. If \(x\in {\mathrm N}(S),\) then \(\{{\mathrm F}(S)-x, {\mathrm F}(S)-1-x\}\subseteq {\mathrm G}(S)\) and so \({\mathrm F}(S)-x\in {\mathrm G}(S)\backslash {\mathrm I}(S).\) Therefore, the map \(f:{\mathrm N}(S)\longrightarrow {\mathrm G}(S)\backslash {\mathrm I}(S)\) defined by \(f(x)={\mathrm F}(S)-x\) is injective. Therefore, \(\#{\mathrm N}(S)\leq \#({\mathrm G}(S)\backslash {\mathrm I}(S)).\) Consequently, \({\mathrm n}(S)\leq {\mathrm g}(S)-{\mathrm i}(S).\) \(\square\)
Note that the numerical semigroup \(S=\langle 5,7,9 \rangle\) from Example 5.1, does not verify the inequality of Proposition 5.2. Observe also that \({\mathrm F}(S)-1=12\in S.\)
If \(S\) is a numerical semigroup, then \({\mathrm N}(S)\cup {\mathrm G}(S)=\{0,1,\cdots,{\mathrm F}(S)\}.\) Therefore, we have the following result.
Lemma 5.3. If \(S\) is a numerical semigroup, then \({\mathrm g}(S)+{\mathrm n}(S)={\mathrm F}(S)+1.\)
From Proposition 5.2 and Lemma 5.3, the following can easily be deduced.
Proposition 5.4. If \(S\) is a numerical semigroup such that \({\mathrm F}(S)-1\notin S,\) then \({\mathrm F}(S)+1\leq 2{\mathrm g}(S)-{\mathrm i}(S).\)
Our next aim in this section, will be to prove that the numerical semigroups for which the inequality in the previous proposition is an equality are precisely the \(\mathrm{PTT}\)-semigroups.
Lemma 5.5. If \(S\) is a \(\mathrm{PTT}\)-semigroup and \(x\in {\mathrm G}(S)\backslash {\mathrm I}(S),\) then \({\mathrm F}(S)-x\in {\mathrm N}(S).\)
Proof. If \({\mathrm F}(S)-x\notin {\mathrm N}(S),\) then by applying Lemma 2.1 and Corollary 2.3, we have that \(\{{\mathrm F}(S)-({\mathrm F}(S)-x),{\mathrm F}(S)-1-({\mathrm F}(S)-x)\}\cap S\neq \emptyset.\) That is, \(\{x,x-1\}\cap S\neq \emptyset\) and so, \(x-1\in S,\) which contradicts the fact that \(x \in {\mathrm G}(S)\backslash {\mathrm I}(S).\) \(\square\)
Theorem 5.6. If \(S\) is a \(\mathrm{PTT}\)-semigroup, then the correspondence \[f:{\mathrm G}(S)\backslash {\mathrm I}(S)\longrightarrow {\mathrm N}(S),\] defined by \(f(x)={\mathrm F}(S)-x\) is a bijective map.
Proof. By Lemma 5.5, we say that \(f\) is a map. Clearly \(f\) is injective. Now, let us see that \(f\) is surjective. If \(x\in {\mathrm N}(S),\) then reasoning as at the beginning of Proposition 5.2, we have that \({\mathrm F}(S)-x\in {\mathrm G}(S)\backslash {\mathrm I}(S).\) As \(f({\mathrm F}(S)-x)=x,\) then we assert that \(f\) is surjective. Consequently, \(f\) is a bijective map. \(\square\)
As a consequence, we show a characterization of a \(\mathrm{PTT}\)-semigroup.
Corollary 5.7. Let \(S\) be a numerical semigroup such that \(S\neq \mathbb{N}.\) Then \(S\) is a \(\mathrm{PTT}\)-semigroup if and only if \({\mathrm N}(S)=\{{\mathrm F}(S)-x\mid x\in {\mathrm G}(S)\backslash {\mathrm I}(S) \}.\)
Proof. (Necessity). It is an immediate consequence of Theorem 5.6.
(Sufficiency). As \(0\in S,\) then \(1\in {\mathrm I}(S)\) and so \({\mathrm F}(S)-1\notin S.\) To prove that \(S\) is a \(\mathrm{PTT}\)-semigroup by applying Corollary 2.3, it will be enough to show that if \(x\in {\mathrm G}(S),\) then \(\{{\mathrm F}(S)-x, {\mathrm F}(S)-1-x \}\cap S\neq \emptyset.\) If we assume the opposite, then \(\{{\mathrm F}(S)-x, {\mathrm F}(S)-1-x \}\cap S= \emptyset.\) Therefore \({\mathrm F}(S)-x\in {\mathrm G}(S)\backslash {\mathrm I}(S).\) Thus, \(x={\mathrm F}(S)-({\mathrm F}(S)-x)\in {\mathrm N}(S)\) which contradicts the fact that \(x\in {\mathrm G}(S).\) \(\square\)
Now we prove that the \(\mathrm{PTT}\)-semigroups are precisely those semigroups that reach the bound established in Proposition 5.2.
Proposition 5.8. Let \(S\) be a numerical semigroup such that \({\mathrm F}(S)-1\in {\mathrm G}(S).\) Then \(S\) is a \(\mathrm{PTT}\)-semigroup if and only if \({\mathrm n}(S)={\mathrm g}(S)-{\mathrm i}(S).\)
Proof. (Necessity). It is an immediate consequence of Theorem 5.6.
(Sufficiency). We are going to prove that \({\mathrm N}(S)=\{{\mathrm F}(S)-x\mid x\in {\mathrm G}(S)\backslash {\mathrm I}(S) \}.\) Indeed, if \(a\in {\mathrm N}(S),\) then following the same reasoning as in the proof of Proposition 5.2, we have that \({\mathrm F}(S)-a\in {\mathrm G}(S)\backslash {\mathrm I}(S).\) Therefore, \({\mathrm N}(S)\subseteq \{{\mathrm F}(S)-x\mid x\in {\mathrm G}(S)\backslash {\mathrm I}(S) \}.\) As \({\mathrm n}(S)={\mathrm g}(S)-{\mathrm i}(S),\) then the previous inclusion is an equality and so \({\mathrm N}(S)= \{{\mathrm F}(S)-x\mid x\in {\mathrm G}(S)\backslash {\mathrm I}(S) \}.\) Thus, Corollary 5.7 allows us to conclude that \(S\) is a \(\mathrm{PTT}\)-semigroup. \(\square\)
By combining the previous result with Lemma 5.3, we finally get the following.
Corollary 5.9. Let \(S\) be a numerical semigroup such that \({\mathrm F}(S)-1\notin S.\) Then \(S\) is a \(\mathrm{PTT}\)-semigroup if and only if \({\mathrm F}(S)+1= 2{\mathrm g}(S)-{\mathrm i}(S).\)
Note that if we join Algorithm 3.7 with Corollary 5.9, we have another algorithm that calculates \({\mathscr{P}}(F)\), because \[{\mathscr{P}}(F)=\{S\in \mathscr{C}(F)\mid {\mathrm F}(S)+1= 2{\mathrm g}(S)-{\mathrm i}(S) \}.\]
Let \(a\) and \(b\) be integers. Denote \([a,b]=\{x\in \mathbb{Z}\mid a\leq x \leq b\}.\)
Let \(A\) be a set. An interval of \(A\) is a set \([a,b]\) such that \([a,b]\subseteq A.\) We will say that an interval \([a,b]\) of \(A\) is maximal if \([a,b]\neq \emptyset\) and \(\{a-1,b+1\}\cap A=\emptyset.\)
Note that \([a,b]\neq \emptyset\) if and only if \(a\leq b.\)
Lemma 6.1. Let \(S\) be a numerical semigroup such that \({\mathrm F}(S)-1\notin S.\) If \([a,b]\) is a non-empty interval of \({\mathrm N}(S),\) then \([{\mathrm F}(S)-b-1,{\mathrm F}(S)-a]\) is a non-empty interval of \({\mathrm G}(S).\)
Proof. If \([a,b]\) is a non-empty interval of \({\mathrm N}(S),\) then it is clear that \([{\mathrm F}(S)-b,{\mathrm F}(S)-a]\) and \([{\mathrm F}(S)-1-b,{\mathrm F}(S)-1-a]\) are non-empty intervals of \({\mathrm G}(S).\) Therefore, \([{\mathrm F}(S)-1-b,{\mathrm F}(S)-a]\) is a non-empty interval of \({\mathrm G}(S).\) \(\square\)
The next result is straightforward to prove.
Lemma 6.2. If \(S\) is a numerical semigroup and \([a,b]\) is a non-empty interval of \({\mathrm G}(S),\) then there is a unique maximal interval of \({\mathrm G}(S)\) containing \([a,b].\)
We will denote by \({\mathscr{S}}([a,b])\) the unique maximal interval of previous lemma, which contains \([a,b].\)
Recall that \({\mathrm {MI}}({\mathrm N}(S))\) and \({\mathrm {MI}}({\mathrm G}(S))\) denote the set formed by the maximal intervals of \({\mathrm N}(S)\) and \({\mathrm G}(S)\) respectively.
By applying Lemmas 6.1 and 6.2, we can announce the following.
Lemma 6.3. Let \(S\) be a numerical semigroup such that \({\mathrm F}(S)-1\in {\mathrm G}(S).\) Then the correspondence \(\varphi:{\mathrm {MI}}({\mathrm N}(S))\longrightarrow {\mathrm {MI}}({\mathrm G}(S))\) defined by \(\varphi([a,b])={\mathscr{S}}([{\mathrm F}(S)-b-1,{\mathrm F}(S)-a])\) is a map.
The map of the previous lemma, in general, is neither injective nor surjective, as shown in the following example.
Example 6.4. Let \(S=\{0,7,9,14,\rightarrow\}.\) Then it is clear that \({\mathrm {MI}}({\mathrm N}(S))=\) \(\{[0,0], [7,7],[9,9]\}\) and \({\mathrm {MI}}({\mathrm G}(S))=\{[1,6],[8,8],[10,13]\}.\) Moreover, \(\varphi([0,0])={\mathscr{S}}([12,13])=[10,13],\) \(\varphi([7,7])={\mathscr{S}}([5,6])=[1,6]\) and \(\varphi([9,9])={\mathscr{S}}([3,4])=[1,6].\) Therefore, \(\varphi\) is neither injective nor surjective.
Notice that in the previous example, it is verified that \(\#{\mathrm {MI}}({\mathrm N}(S))=\#{\mathrm {MI}}({\mathrm G}(S)).\) This fact is true for every numerical semigroup, as we will demonstrate in the following result.
Lemma 6.5. If \(S\) is a numerical semigroup, then \(\#{\mathrm {MI}}({\mathrm N}(S))=\#{\mathrm {MI}}({\mathrm G}(S)).\)
Proof. It is enough to note that \([0,{\mathrm F}(S)]=\displaystyle \bigcup_{X\in {\mathrm {MI}}({\mathrm N}(S))}X\cup \bigcup_{Y\in {\mathrm {MI}}({\mathrm G}(S))}Y\) and also if \({\mathrm {MI}}({\mathrm N}(S))=\{[a_1,b_1],\cdots,[a_n,b_n] \}\) with \(a_1<a_2<\cdots <a_n\) then \({\mathrm {MI}}({\mathrm G}(S))=\{[b_1+1,a_2-1],[b_2+1,a_3-1],\cdots,[b_n+1,{\mathrm F}(S)] \}.\) \(\square\)
Theorem 6.6. Let \(S\) be a \(\mathrm{PTT}\)-semigroup. If \([a,b]\) is a maximal interval of \({\mathrm G}(S),\) then \([{\mathrm F}(S)-b, {\mathrm F}(S)-a-1]\) is a maximal interval of \({\mathrm N}(S).\)
Proof. If \([a,b]\) is a maximal interval of \({\mathrm G}(S),\) then \(\{a-1,b+1\}\subset S.\) As \(S\) is a perfect numerical semigroup, then \(a\) is not an isolated gap of \(S\) and so \(b\ge a+1.\) By Corollary 5.7, we obtain that \([{\mathrm F}(S)-b,{\mathrm F}(S)-a-1]\) is a non-empty interval of \({\mathrm N}(S).\) To prove that this interval is maximal, we will see that \(\{F(S)-b-1,{\mathrm F}(S)-a\}\cap S=\emptyset.\) But this is true, because \(b+1\in S\) and therefore \({\mathrm F}(S)-b-1\notin S\); and as \(a-1\in S,\) then \({\mathrm F}(S)-a={\mathrm F}(S)-1-(a-1)\notin S.\) \(\square\)
By applying Lemma 6.5 and Theorem 6.6, we obtain the following result.
Corollary 6.7. Let \(S\) be a \(\mathrm{PTT}\)-semigroup. Then the correspondence \(\varphi:{\mathrm {MI}}({\mathrm G}(S))\longrightarrow {\mathrm {MI}}({\mathrm N}(S))\) defined by \(\varphi([a,b])=[{\mathrm F}(S)-b,{\mathrm F}(S)-a-1]\) is a bijective map. Moreover, \(\#\varphi([a,b])=\#[a,b]-1=b-a\ge 1.\)
Theorem 6.8. Let \(S\) be a numerical semigroup such that \({\mathrm F}(S)-1\notin S.\) Then \(S\) is a \(\mathrm{PTT}\)-semigroup if and only if there is a bijective map \(h:{\mathrm {MI}}({\mathrm G}(S))\longrightarrow {\mathrm {MI}}({\mathrm N}(S))\) verifying that \(\#h(X)=\#X-1\) for all \(X\in {\mathrm {MI}}({\mathrm G}(S)).\)
Proof. (Necessity). It is a consequence of Corollary 6.7.
(Sufficiency). It is clear that \({\mathrm i}(S)=\#{\mathrm {MI}}({\mathrm G}(S)).\) Therefore, \({\mathrm n}(S)={\mathrm g}(S)-{\mathrm i}(S).\) By applying Proposition 5.8, we have that \(S\) is a \(\mathrm{PTT}\)-semigroup. \(\square\)
This research is framed within the line of investigation of numerical semigroups. It focuses on the study of \(\mathrm{PTT}\)-semigroups (perfect numerical semigroups of type two), exploring their combinatorial, algebraic, and computational properties.
Specifically, we present three characterizations of these semigroups based on: their set of pseudo-Frobenius numbers, their structure as a covariety, and the maximal elements of this covariety.
As an application of these characterizations, we have designed three algorithms to compute all \(\mathrm{PTT}\)-semigroups for a given Frobenius number. Furthermore, we have proven that S is a \(\mathrm{PTT}\)-semigroup with Frobenius number F if and only if there exists a bijective map between the set of maximal intervals of the small elements (\({\mathrm N}(S)\)) and the set of maximal intervals of the gaps (\({\mathrm G}(S)\)).
The first author is supported by the Junta de Andalucía group FQM-298.
The authors would like to thank the referees for their comments which have helped to improve the initial version of the paper.