# The Numerical Semigroup of Phrases' Lengths in a Simple Alphabet

Authors: Aureliano M. Robles-Pérez; José Carlos Rosales
Journal: The Scientific World Journal
 (2013)

---

## Abstract

Let𝒜 be an alphabet with two elements. Considering a particular class of words (the phrases) over such an alphabet, we connect with the theory of numerical semigroups. We study the properties of the family of numerical semigroups which arise from this starting point.


---

## Body

## 1. Introduction

Let𝒜 be a nonempty finite set called the alphabet. Elements of 𝒜 are called letters or symbols. A word is a sequence of letters, which can be finite or infinite. We denote by 𝒜* (resp., 𝒜ω) the set of all finite (resp., infinite) words over 𝒜. The sequence of zero letters is called the empty word and is denoted by ɛ. Any subset ℒ⊆𝒜* is called a language over 𝒜. The length of a word u is denoted by |u|. If u,v are words, we define their product or concatenation as the word uv. We say that a word u is a factor of a word v if there exist two words x,y such that v=xuy. If u is a factor of v with x=ɛ (resp., y=ɛ), then u is a prefix (resp., suffix) of v.We have taken these definitions from [1]. In this book (and the references given therein), the authors study problems related to Combinatorics on Words. However, we are going to consider a different point of view. We are interested in a very particular type of words (the phrases) and, more specifically, their length.Definition 1.
Let us take𝒜={a,⌣}. We say that f∈𝒜* is a phrase if it fulfills the following conditions: (1)
⌣ is not a prefix or suffix of f,(2)
⌣⌣ is not a factor of f. We denote 𝒜ℱ={f∈𝒜*∣fisaphrase}.If we consider that⌣ represents a gap between two words, then we have a suitable justification for the above definition.Let𝒞 be a language over 𝒜 such that 𝒞⊆𝒜ℱ. We will denote by ℓ(𝒞)={|c|∣c∈𝒞}. In this work we are going to deal with the structure of the set ℓ(𝒞) for particular choices of 𝒞. In fact, let {w1,…,wn}⊆𝒜* be a finite set of words such that ⌣ is not a factor of wi,1≤i≤n. Then 𝒞(w1,…,wn)⊆𝒜ℱ is the language in which each phrase f is obtained as product of factors belonging to {w1,…,wn}∪{⌣}. Moreover, in order to achieve the results of this paper, we assume that ɛ∈𝒞(w1,…,wn).Example 2.
If we take{aaaa,aaaaa}, then f1=aaaaaaaa, f2=aaaaaaaaa, and f3=aaaaa⌣aaaa belong to 𝒞(aaaa,aaaaa). However, f4=aaaa⌣aaaaaa, f5=aaa, and f6=aa⌣a do not belong to 𝒞(aaaa,aaaaa).Letℕ be the set of nonnegative integers. A numerical semigroup is a subset S of (ℕ,+) that is closed under addition, contains the zero element, and such that ℕ∖S is finite.In Section2 we will show that ℓ(𝒞(w1,…,wn)) is a numerical semigroup. We will also see that there exist numerical semigroups that cannot be obtained by this procedure. This fact allows us to give the following definition.Definition 3.
Let𝒜 be the alphabet given by the set {a,⌣}. A numerical semigroup S is the set of lengths of a language of phrases (PL-semigroup for abbreviation) if there exists 𝒞=𝒞(w1,…,wn)⊆𝒜ℱ such that S=ℓ(𝒞).The next aim of Section2 will be to characterize PL-semigroups. Concretely, we will show that a numerical semigroup S is a PL-semigroup if and only if x+y+1∈S for all x,y∈S∖{0}.LetS be a numerical semigroup. Since ℕ∖S is a finite set, we can consider two notable invariants of S (see [2]). On the one hand, the Frobenius number of S is the maximum of ℕ∖S and is denoted by F(S). On the other hand, the genus of S is the cardinality of ℕ∖S and is denoted by g(S).AFrobenius variety is a nonempty family 𝒱 of numerical semigroups that fulfills the following conditions:(1)
ifS,T∈𝒱, then S∩T∈𝒱,(2)
ifS∈𝒱 and S≠ℕ, then S∪{F(S)}∈𝒱.Let us denote𝒮PL={S∣S is a PL-semigroup}. In Section 3, we will show that 𝒮PL is a Frobenius variety. This fact, together with the results of [3], will allow us to show orderly the elements of 𝒮PL in a tree with root ℕ. Moreover, we will also characterize the sons of a vertex, in order to build recursively such a tree.Themultiplicity of a numerical semigroup S, denoted by m(S), is the minimum of S∖{0}. We will study the set 𝒮PL(m)={S∈𝒮PL∣m(S)=m} in Section 4. In particular, we will show that this set is finite and has maximum and minimum with respect to the inclusion order. Furthermore, we will determine the sets {F(S)∣S∈𝒮PL(m)} and {g(S)∣S∈𝒮PL(m)}. We will also see that the elements of 𝒮PL(m) can be ordered in a tree with root the numerical semigroup S={0,m,→} (where the symbol → means that every integer greater than m belongs to S).In Section5, we will see that a PL-semigroup is determined perfectly by a nonempty finite set of positive integers. In addition, we will show explicitly the smallest PL-semigroup that contains a given nonempty finite set of positive integers.We finish this introduction pointing out that this work admits different generalizations. Some of them are in working process and other ones have already been developed (see [4]).


## 2. PL-Semigroups

IfX is a nonempty subset of ℕ, we denote by 〈X〉 the submonoid of (ℕ,+) generated by X; that is,
(1)〈X〉={λ1x1+⋯+λnxn∣n∈ℕ∖{0},x1,…,xn∈X,λ1,…,λn∈ℕ}.
It is a well-known fact (see for instance [5, Lemma 2.1]) that 〈X〉 is a numerical semigroup if and only if gcd{X}=1 (as usual, gcd means greatest common divisor). On the other hand, every numerical semigroup S is finitely generated, and therefore there exists a finite subset X of S such that S=〈X〉. In addition, if no proper subset of X generates S, then we say that X is a minimal system of generators of S. In [5, Theorem 2.7] it is proved that every numerical semigroup S has a unique (finite) minimal system of generators. The elements of such a system are called minimal generators of S.Let𝒜 be an alphabet and let {w1,…,wn}⊆𝒜* be a finite set of words. If 𝒞=𝒞(w1,…,wn)⊆𝒜* is the language in which each word is obtained as product of factors belonging to {w1,…,wn}, then it is easy to see that ℓ(𝒞) is a submonoid of (ℕ,+). In addition, if gcd{|w1|,…,|wn|}=1, then ℓ(𝒞) is a numerical semigroup. Moreover, it is a simple exercise to show that we can get any numerical semigroup in this way.As we indicated in the introduction we are going to study the particular case in which we consider lengths of phrases. Consequently, we will focus our attention in a particular family of numerical semigroups.Proposition 4.
Let𝒜={a,⌣} be an alphabet. If 𝒞=𝒞(w1,…,wn)⊆𝒜ℱ, then ℓ(𝒞) is a numerical semigroup.Proof.
We proceed in three steps.(i)
First of all, being thatɛ∈𝒞 and |ɛ|=0, we have that 0∈ℓ(𝒞).(ii)
Now, let us see that, ifl1,l2∈ℓ(𝒞), then l1+l2∈ℓ(𝒞). In effect, let f1,f2∈𝒞 such that |f1|=l1 and |f2|=l2. Then the concatenation f1f2 (of f1 and f2) is an element of 𝒞 with |f1f2|=l1+l2.(iii)
Finally, letf∈𝒞 with |f|≠0 (i.e., f≠ɛ). Since f⌣f∈𝒞, we have that {|f|,2|f|+1}⊆ℓ(𝒞). By the previous step, we know that 𝒞 is closed under addition and, consequently, 〈|f|,2|f|+1〉⊆ℓ(𝒞). As gcd{|f|,2|f|+1}=1, we have 〈|f|,2|f|+1〉 is a numerical semigroup. Therefore, ℕ∖ℓ(𝒞) is finite. We conclude that ℓ(𝒞) is a numerical semigroup.From now on, unless another thing is stated, we take𝒜={a,⌣}. As in the introduction, we say that a numerical semigroup S is a PL-semigroup if there exists 𝒞=𝒞(w1,…,wn)⊆𝒜ℱ such that S=ℓ(𝒞). From Proposition 4, we deduce that if S is a PL-semigroup and x∈S∖{0}, then 2x+1∈S. Consequently, there exist numerical semigroups which are not of this type. For example, S=〈5,7,9〉 is not a PL-semigroup because 2·5+1=11∉S.In the next result we give a characterization ofPL-semigroups.Theorem 5.
LetS be a numerical semigroup. The following conditions are equivalent. (1)
S is a PL-semigroup.(2)
Ifx,y∈S∖{0}, then x+y+1∈S.Proof.
(
1
⇒
2
) By hypothesis, S=ℓ(𝒞(w1,…,wn)) for some nonempty finite set {w1,…,wn}⊆𝒜*. If x,y∈S∖{0}, then there exist f,g∈𝒞(w1,…,wn)∖{ɛ} such that |f|=x and |g|=y. It is clear that f⌣g∈𝒞(w1,…,wn) and |f⌣g|=x+y+1. Therefore, x+y+1∈S.
(
2
⇒
1
) Let {n1,…,np} be the minimal system of generators of S. Let us take the set {w1,…,wp∣|wi|=ni,1≤i≤p}. Our aim is to show that if 𝒞=𝒞(w1,…,wp), then S=ℓ(𝒞).
Since{n1,…,np}⊆ℓ(𝒞), by applying Proposition 4, we have S=〈n1,…,np〉⊆ℓ(𝒞). Now, let l∈ℓ(𝒞). In order to prove that l∈S, we are going to use induction over l. If l=0, then the result is trivially true. Let us assume that l>0, and let f∈𝒞 such that |f|=l. If ⌣ is not a factor of f, then the result follows immediately. In other case, there exist f1,f2∈𝒞∖{ɛ} such that f=f1⌣f2. By hypothesis of induction, |f1|,|f2|∈S. Thereby, l=|f|=|f1|+|f2|+1∈S.Remark 6.
The previous theorem leads to the concept ofnumerical semigroup that admit a linear nonhomogeneous pattern. For a general study of this family of numerical semigroups see, for instance, [6, 7].LetS be a numerical semigroup with minimal system of generators given by {n1,…,np}. Following [8], if s∈S, then we define the order of s (in S) by
(2)ord(s;S)=max{α1+⋯+αp∣α1n1+⋯+αpnp=s,maxwithα1,…,αp∈ℕ}.
If no ambiguity is possible, then we write ord(s).Remark 7.
From [5, Lemma 2.3 and Theorem 2.7], we have that if X is the minimal system of generators of S, then every system of generators of S contains X. Consequently, the definition of ord(s;S) does not depend on the considered system of generators; that is, it only depends on s and S.Lemma 8.
LetS be a numerical semigroup with minimal system of generators given by {n1,…,np} and let s∈S. (1)
Ifi∈{1,…,p} and s-ni∈S, then ord(s-ni)≤ord(s)-1.(2)
Ifs=α1n1+⋯+αpnp, with ord(s)=α1+⋯+αp and αi≠0, then ord(s-ni)=ord(s)-1.Proof.
(
1
) Assume that s-ni=β1n1+⋯+βpnp, with β1+⋯+βp=ord(s-ni). Then s=β1n1+⋯+(βi+1)ni+⋯+βpnp, and thus ord(s-ni)+1=β1+⋯+(βi+1)+⋯+βp≤ord(s).
(
2
) Since s-ni=α1n1+⋯+(αi-1)ni+⋯+αpnp, we have ord(s-ni)≥α1+⋯+(αi-1)+⋯+αp=ord(s)-1. Thereby, ord(s)-1≤ord(s-ni). Now, by applying the previous item, we conclude that ord(s-ni)=ord(s)-1.In item(2) of the next proposition, it is shown a characterization of PL-semigroups in terms of minimal systems of generators. Thus, we can decide if a numerical semigroup is a PL-semigroup in an easier way.Proposition 9.
LetS be a numerical semigroup with minimal system of generators given by {n1,…,np}. The following conditions are equivalent. (1)
S is a PL-semigroup.(2)
Ifi,j∈{1,…,p}, then ni+nj+1∈S.(3)
Ifs∈S∖{0,n1,…,np}, then s+1∈S.(4)
Ifs∈S∖{0}, then s+{0,…,ord(s)-1}⊆S.Proof.
(
1
⇒
2
) It is an immediate consequence of Theorem 5.
(
2
⇒
3
) If s∈S∖{0,n1,…,np}, then it is clear that there exist i,j∈{1,…,p} and s′∈S such that s=ni+nj+s′. Thus, s+1=(ni+nj+1)+s′∈S.
(
3
⇒
4
) We reason by induction over ord(s). If ord(s)=1, then the result is trivially true. Now, let us assume that ord(s)≥2 and that α1,…,αp are nonnegative integers such that s=α1n1+⋯+αpnp, ord(s)=α1+⋯+αp, and ai≠0 for some i∈{1,…,p}. By Lemma 8, we know that ord(s-ni)=ord(s)-1. Then, by hypothesis of induction, we have that s-ni+{0,…,ord(s)-2}⊆S. Therefore, s+{0,…,ord(s)-2}⊆S. Moreover, (s-ni+ord(s)-2)+ni+1∈S. Thereby, s+{0,…,ord(s)-1}⊆S.
(
4
⇒
1
) If x,y∈S∖{0}, then it is clear that ord(x+y)≥2. Thus, we get that x+y+1∈S. By applying Theorem 5, we can conclude that S is a PL-semigroup.Example 10.
LetS=〈4,5,6〉; that is, let S be the numerical semigroup with minimal system of generators given by {4,5,6}. It is obvious that 4+4+1=9, 4+5+1=10, 4+6+1=11, 5+5+1=11, 5+6+1=12, and 6+6+1=13 are elements of S. Therefore, by applying Proposition 9, we have that S is a PL-semigroup.


## 3. The Frobenius Variety of the PL-Semigroups

The following result is straightforward to prove and appears in [5].Lemma 11.
LetS,T be numerical semigroups. (1)
S∩T is a numerical semigroup.(2)
IfS≠ℕ, then S∪{F(S)} is a numerical semigroup.Having in mind the definition of Frobenius variety, which was given in the introduction, we get the next result.Proposition 12.
The set𝒮PL={S∣S is a PL-semigroup} is a Frobenius variety.Proof.
First of all, let us observe thatℕ∈𝒮PL and, therefore, 𝒮PL is a nonempty set.
LetS,T∈𝒮PL. In order to show that S∩T∈𝒮PL, we are going to use Theorem 5. So, if x,y∈(S∩T)∖{0}, then x,y∈S∖{0} and x,y∈T∖{0}. Therefore, x+y+1∈S∩T. Consequently, S∩T∈𝒮PL.
Now, letS∈𝒮PL such that S≠ℕ. By applying Theorem 5 again, we are going to see that S∪F(S)∈𝒮PL. Let x,y∈(S∪F(S))∖{0}. If x,y∈S, then x+y+1∈S⊆S∪F(S). On the other hand, if F(S)∈{x,y}, then x+y+1>F(S) and, thereby, x+y+1∈S⊆S∪F(S). We conclude that S∪F(S)∈𝒮PL.Agraph  G is a pair (V,E), where V is a nonempty set and E is a subset of {(v,w)∈V×V∣v≠w}. The elements of V are called vertices of G and the elements of E are called edges of G. A path (of lengthn) connecting the vertices x and y of G is a sequence of different edges of the form (v0,v1),(v1,v2),…,(vn-1,vn) such that v0=x and vn=y.We say that a graphG is a tree if there exist a vertex v* (known as the root of G) such that for every other vertex x of G, there exists a unique path connecting x and v*. If (x,y) is an edge of the tree, then we say that x is a son of y.We define the graphG(𝒮PL) in the following way:(i)
𝒮PL is the set of vertices of G(𝒮PL),(ii)
(S,S′)∈𝒮PL×𝒮PL is an edge of G(𝒮PL) if S′=S∪{F(S)}.As a consequence of [3, Proposition 24, Theorem 27], we have the next result.Theorem 13.
The graphG(𝒮PL) is a tree with root equal to ℕ. Moreover, the sons of a vertex S∈𝒮PL are S∖{x1},…,S∖{xr}, where x1,…,xr are the minimal generators of S that are greater than F(S) and such that S∖{x1},…,S∖{xr}∈𝒮PL.Let us observe that ifS is a numerical semigroup and x∈S, then S∖{x} is a numerical semigroup if and only if x is a minimal generator of S. In fact, S∖{x} is a numerical semigroup whenever x∈S∖{0} and x≠y+z for all y,z∈S∖{0}. As a consequence, if we denote by msg(S) the minimal system of generators of S, then msg(S)=(S∖{0})∖((S∖{0})+(S∖{0})) (see [5, Lemma 2.3] for other proof of this result). In the following proposition we obtain an analogous for PL-semigroups of the first commented fact in this paragraph.Proposition 14.
LetS be a PL-semigroup and let x be a minimal generator of S. Then S∖{x} is a PL-semigroup if and only if x-1∈{0}∪(ℕ∖S)∪(msg(S)).Proof.
(Necessity). If x-1∉{0}∪(ℕ∖S)∪(msg(S)), then x-1∈S∖({0}∪(msg(S))). Accordingly, there exist y,z∈S∖{0} such that x-1=y+z. In fact, it is clear that y,z∈S∖{x,0}. Therefore, by applying Theorem 5 and that S∖{x} is a PL-semigroup, we have x=y+z+1∈S∖{x}, which is a contradiction.
(Sufficiency). Let y,z∈S∖{x,0}. Since S is a PL-semigroup, by Theorem 5 we have y+z+1∈S. As x-1∈{0}∪(ℕ∖S)∪(msg(S)), we deduce that y+z+1≠x. Thus y+z+1∈S∖{x}. By applying Theorem 5 again, we conclude that S∖{x} is a PL-semigroup.As a consequence of the previous proposition, we have the next result.Corollary 15.
LetS be a PL-semigroup such that S≠ℕ, and let x be a minimal generator of S greater than F(S). Then S∖{x} is a PL-semigroup if and only if x-1∈msg(S)∪{F(S)}.By applying Theorem13 together with Corollary 15, we can get the sons of a vertex of G(𝒮PL) as is shown in the following example.Example 16.
It is clear thatS=〈4,6,7,9〉 is a PL-semigroup with Frobenius number equal to 5. From Theorem 13 and Corollary 15, we deduce that the sons of S are S∖{6}=〈4,7,9,10〉 and S∖{7}=〈4,6,9,11〉.Let us observe that we can build recursively a tree, from the root, if we know the sons of each vertex. Therefore, we can build the treeG(𝒮PL) such as it is shown in Figure 1.Figure 1In order to have an easier making of the treeG(𝒮PL), we are going to study the relation between the minimal generators of a numerical semigroup S and the minimal generators of S∖{x}, where x is a minimal generator of S that is greater than F(S). First of all, let us observe that if S is minimally generated by {m,m+1,…,2m-1} (i.e., S={0,m,→}), then S∖{m}={0,m+1,→} is minimally generated by {m+1,m+2,…,2m+1}. In other case we have the following result.Proposition 17.
LetS be a numerical semigroup with msg(S)={n1,…,np}. If m(S)=n1<np and np>F(S), then S∖{np}=〈n1,…,np-1,np+n1〉.Proof.
Let us takei∈{2,…,p}. Since np>F(S) and n1<ni, we have that np+ni-n1∈S. Thus, np+ni-n1=α1n1+⋯+αpnp for some α1,…,αp∈ℕ. Thereby, np+ni=(α1+1)n1+⋯+αpnp. By applying that {n1,…,np} is a minimal system of generators, we have that αp=0. Therefore, np+ni∈〈n1,…,np-1〉. In particular, 2np∈〈n1,…,np-1〉.
Now, lets∈S∖{np}. Then s∈S and, thus, there exist β1,…,βp∈ℕ such that s=β1n1+⋯+βpnp. Since 2np∈〈n1,…,np-1〉, we can assume that βp∈{0,1}. On the one hand, if βp=0, then s∈〈n1,…,np-1〉. On the other hand, if βp=1, then there exists i∈{1,…,p-1} such that βi≠0. If i=1, then it is obvious that s∈〈n1,…,np-1,np+n1〉. And if i≠1, since np+ni∈〈n1,…,np-1〉, we have that s∈〈n1,…,np-1〉. In any case, we conclude that S∖{np}=〈n1,…,np-1,np+n1〉.Corollary 18.
LetS be a numerical semigroup with msg(S)={n1,…,np}. If m(S)=n1<np and np>F(S), then (3)msg(S∖{np})={{n1,…,np-1},ifthereexistsi∈{2,…,p-1}suchthatnp+n1-ni∈S;{n1,…,np-1,np+n1},inothercase.Proof.
From Proposition17 we deduce that msg(S∖{np}) is {n1,…,np-1} or {n1,…,np-1,np+n1}. In addition, msg(S∖{np})={n1,…,np-1} if and only if np+n1∈〈n1,…,np-1〉.
Ifnp+n1∈〈n1,…,np-1〉, then there exist α1,…,αp-1∈ℕ such that np+n1=α1n1+⋯+αp-1np-1. Since {n1,…,np} is a minimal system of generators, we get that α1=0. Thus, there exists i∈{2,…,p-1} such that αi≠0. Consequently, np+n1-ni∈S.
Conversely, if there existsi∈{2,…,p-1} such that np+n1-ni∈S, then np+n1-ni=β1n1+⋯+βpnp for some β1,…,βp∈ℕ. Thereby, np+n1=β1n1+⋯+(βi+1)ni+⋯+βpnp. Since {n1,…,np} is a minimal system of generators, we have that βp=0 and, therefore, np+n1∈〈n1,…,np-1〉.We finish this section with an illustrative example about the above corollary.Example 19.
LetS be the numerical semigroup with msg(S)={3,5,7}. It is obvious that F(S)=4. By Proposition 17, we know that S∖{5}=〈3,7,8〉. In addition, 8-7=1∉S. Thereby, applying Corollary 18, we have that msg(S∖{5})={3,7,8}. On the other hand, applying Proposition 17 again, we have that S∖{7}=〈3,5,10〉. Finally, since 10-5=5∈S, we conclude that msg(S∖{7})={3,5}.


## 4. PL-Semigroups with a Fixed Multiplicity

Letm be a positive integer. We will denote by Δ(m)={0,m,→}. It is clear that Δ(m) is the greatest (with respect to set inclusion) PL-semigroup with multiplicity m. Our first aim in this section will be to show that there also exists the smallest (with respect to set inclusion) PL-semigroup with multiplicity m.As an immediate consequence of item(4) in Proposition 9 we have the next result.Lemma 20.
IfS is a PL-semigroup, m∈S∖{0}, and k∈ℕ∖{0}, then km+i∈S for all i∈{0,…,k-1}.Proposition 21.
Letm∈ℕ∖{0}. Then the numerical semigroup generated by {(i+1)m+i∣i∈{0,…,m-1}} is the smallest (with respect to set inclusion) PL-semigroup with multiplicity m.Proof.
LetS=〈m,2m+1,…,m2+(m-1)〉. From Lemma 20, we know that any PL-semigroup with multiplicity m has to contain S. In order to conclude the proof, we will show that S is a PL-semigroup. For this purpose, since {(i+1)m+i∣i∈{0,…,m-1}} is a system of generators of S, it will be enough to check item (2) of Proposition 9; that is, if i,j∈{0,…,m-1}, then (i+1)m+i+(j+1)m+j+1∈S. We distinguish two cases. (1)
Ifi+j+1≤m-1, then (i+1)m+i+(j+1)m+j+1=(i+j+2)m+(i+j+1)∈S.(2)
Ifi+j+1≥m, then (i+1)m+i+(j+1)m + j+1 = (i+j+2)m + (i+j+1) = (m+1)m+(i+j-m+2)m + (i+j-m+1)∈S.We will denote byΘ(m)=〈m,2m+1,…,m2+(m-1)〉 and by 𝒮PL(m) the set of all PL-semigroups with multiplicity equal to m. Let us recall that Δ(m)=max(𝒮PL(m)) and Θ(m)=min(𝒮PL(m)).As an application of the above comment, we have the next result.Corollary 22.
The set𝒮PL(m) is finite.Proof.
IfS∈𝒮PL(m), then Θ(m)⊆S⊆Δ(m). Since Δ(m) and Θ(m) are numerical semigroups, we have that Δ(m)∖Θ(m) is finite. Consequently, 𝒮PL(m) is also finite.Remark 23.
The previous result can be considered a particular case of [6, Theorem 6.6].Now we are interested in computing the Frobenius number and the genus ofΘ(m). For that, several concepts and results are introduced.IfS is a numerical semigroup and m∈S∖{0}, then the Apéry set of m in S (see [9]) is Ap(S,m)={s∈S∣s-m∉S}. It is clear (see for instance [5, Lemma 2.4]) that Ap(S,m)={ω(0)=0,ω(1),…,ω(m-1)}, where ω(i) is, for each i∈{0,…,m-1}, the least element of S that is congruent with i modulo m.The next result is [5, Proposition 2.12].Lemma 24.
LetS be a numerical semigroup and let m∈S∖{0}. Then (1)
F(S)=max(Ap(S,m))-m,(2)
g(S)=(1/m)(∑w∈Ap(S,m)‍w)-((m-1)/2).Ifa,b are integers with b≠0, we denote by amodb the remainder of the division of a by b. The following result is [5, Proposition 3.5].Lemma 25.
Letm∈ℕ∖{0} and let X={ω(0)=0,ω(1),…,ω(m-1)}⊆ℕ such that, for each i∈{1,…,m-1}, ω(i) is congruent with i modulo m. Let S be the numerical semigroup generated by X∪{m}. The following conditions are equivalent. (1)
Ap(S,m)=X.(2)
ω(i)+ω(j)≥ω((i+j)modm) for all i,j∈{1,…,m-1}.Proposition 26.
Ifm∈ℕ∖{0}, then
(4)Ap(Θ(m),m)={ω(0)=0,ω(1)=2m+1,…,ω(m-1)=m2+m-1}.Proof.
It is clear thatω(i)=(i+1)m+i is congruent with i modulo m for all i∈{1,…,m-1}. Let us see now that, if i,j∈{1,…,m-1}, then ω(i)+ω(j)≥ω((i+j)modm). Indeed, ω(i)+ω(j) = (i+1)m + i+(j+1)m + j>(i+j+1)m + (i+j)≥((i+j)modm+1)m + (i+j)modm = ω((i+j)modm). The proof follows from Lemma 25.Corollary 27.
Ifm∈ℕ∖{0,1}, then (1)
F(Δ(m))=m-1,(2)
g(Δ(m))=m-1,(3)
F(Θ(m))=m2-1,(4)
g(Θ(m))=(m-1)(m+2)/2.Proof.
Items(1) and (2) are trivial. On the other hand, items (3) and (4) are immediate consequences of Lemma 24 and Proposition 26.Remark 28.
The numerical semigroupΘ(m) can be rewritten as
(5)Θ(m)={m,m+(m+1),m+2(m+1),…,m+(m-1)(m+1)}.
Thus Θ(m) is a numerical semigroup generated by an arithmetic sequence with first term m and common difference m+1 (see [2, 10]).IfS is a numerical semigroup, then the cardinality of the minimal system of generators of S is called the embedding dimension of S and is denoted by e(S). It is well known (see [5, Proposition 2.12]) that e(S)≤m(S). We say that a numerical semigroup S has maximal embedding dimension if e(S)=m(S). It is clear that {m,m+1,…,2m-1} is the minimal system of generators of Δ(m). Therefore, Δ(m) is a numerical semigroup with maximal embedding dimension. Now we will show that Θ(m) has also maximal embedding dimension.The next result is [5, Corollary 3.6].Lemma 29.
LetS be a numerical semigroup with multiplicity m and assume that Ap(S,m)={ω(0)=0,ω(1),…,ω(m-1)}. Then S has maximal embedding dimension if and only if ω(i)+ω(j)>ω((i+j)modm) for all i,j∈{1,…,m-1}.Let us observe that, in the proof of Proposition26, we have shown that ω(i)+ω(j)>ω((i+j)modm) for all i,j∈{1,…,m-1}. Therefore, by applying Lemma 29, we get the following result.Corollary 30.
Ifm∈ℕ∖{0}, then Θ(m) is a numerical semigroup with maximal embedding dimension.As a consequence of this corollary, we have that{m,2m+1,…,m2+m-1} is the minimal system of generators of Θ(m).Now, we want to show orderly the elements of𝒮PL(m). Thus, we define the graph G(𝒮PL(m)) in the following way:(i)
𝒮PL(m) is the set of vertices of G(𝒮PL(m));(ii)
(S,S′)∈𝒮PL(m)×𝒮PL(m) is an edge of G(𝒮PL(m)) if S′=S∪{F(S)}.The next result is analogous to Theorem13.Theorem 31.
The graphG(𝒮PL(m)) is a tree with root equal to Δ(m). Moreover, the sons of a vertex S∈𝒮PL(m) are S∖{x1},…,S∖{xr}, with {x1,…,xr} = {x∈msg(S)∣x≠m,x>F(S),andS∖{x}∈𝒮PL}.By applying Theorem31 and Corollaries 15 and 18, we can get easily G(𝒮PL(m)) such as is shown in the next example.Example 32.
We are going to depictG(𝒮PL(3)), that is, the tree of the PL-semigroups with multiplicity equal to 3.IfT=(V,E) is a tree, then the height of T is the maximum of the lengths of the paths that connect each vertex with the root. Let us observe that the height of G(𝒮PL(3)) is 3. In general, the height of the tree G(𝒮PL(m)) is equal to
(6)g(Θ(m))-g(Δ(m))=(m-1)(m+2)2-(m-1)=(m-1)m2.Let us study now the possible values of the Frobenius number and the genus forPL-semigroups with multiplicity m.Proposition 33.
Ifm∈ℕ∖{0}, then (1)
{g(S)∣S∈𝒮PL(m)}={x∈ℕ∣m-1≤x≤(m-1)(m+2)/2};(2)
{F(S)∣S∈𝒮PL(m)}=(Δ(m)∖Θ(m))∪{m-1}.Proof.
Let us assume thatΔ(m)∖Θ(m)={x1>x2>⋯>xρ}.
(
1
) By Corollary 27, we know that
(7){g(S)∣S∈𝒮PL(m)}⊆{m-1,…,(m-1)(m+2)2}.
For the opposite inclusion it is enough to observe that Θ(m)∪{xi,→}∈𝒮PL(m) and that g(Θ(m)∪{xi,→})=(m-1)(m+2)/2-i.
(
2
) It is clear that Θ(m)∪{xi+1,→}∈𝒮PL(m) with Frobenius number equal to xi. Thus, (Δ(m)∖Θ(m))∪{m-1}⊆{F(S)∣S∈𝒮PL(m)}. For the other inclusion, let us take S∈𝒮PL(m) such that S≠Δ(m). Then F(S)>m and, thereby, F(S)∈Δ(m). Since Θ(m)⊆S, we have F(S)∉Θ(S). Therefore, we conclude that F(S)∈Δ(m)∖Θ(S).Example 34.
By Proposition33, {g(S)∣S∈𝒮PL(3)}={2,3,4,5}. Since Δ(3)=〈3,4,5〉 and Θ(3)=〈3,7,11〉, we have that (Δ(3)∖Θ(3))∪{2}={2,4,5,8}. Therefore, by applying Proposition 33 again, we conclude that {F(S)∣S∈𝒮PL(3)}={2,4,5,8}.


## 5. The Smallest PL-Semigroup That Contains a Given Set of Positive Integers

Let us observe that, in general, the infinite intersection of elements of𝒮PL is not a numerical semigroup. For instance, ⋂n∈ℕ‍{0,n,→}={0}. On the other hand, it is clear that the (finite or infinite) intersection of numerical semigroups is always a submonoid of (ℕ,+).LetM be a submonoid of (ℕ,+). We will say that M is a 𝒮PL-monoid if it can be expressed like the intersection of elements of 𝒮PL.The next lemma has an immediate proof.Lemma 35.
The intersection of𝒮PL-monoids is a 𝒮PL-monoid.In view of this result, we can give the following definition.Definition 36.
LetX be a subset of ℕ. The 𝒮PL-monoid generated by X (denoted by 𝒮PL(X)) is the intersection of all 𝒮PL-monoids containing X.IfM=𝒮PL(X), then we will say that X is a 𝒮PL-system of generators of M. In addition, if no proper subset of X is a 𝒮PL-system of generators of M, then we will say that X is a minimal𝒮PL-system of generators of M.Let us recall that, by Proposition12, we know that 𝒮PL is a Frobenius variety. Therefore, by applying [3, Corollary 19], we have the next result.Proposition 37.
Every𝒮PL-monoid has a unique minimal 𝒮PL-system of generators, which in addition is finite.The proof of the following lemma is also immediate.Lemma 38.
IfX⊆ℕ, then 𝒮PL(X) is the intersection of all PL-semigroups that contain X.Proposition 39.
IfX is a nonempty subset of ℕ∖{0}, then 𝒮PL(X) is a PL-semigroup.Proof.
We know that𝒮PL(X) is a submonoid of (ℕ,+). Therefore, in order to show that 𝒮PL(X) is a numerical semigroup, it will be enough to see that ℕ∖𝒮PL(X) is a finite set.
Letx∈X. If S is a PL-semigroup containing X, then (by Theorem 5) we know that {x,2x+1}⊆S and, in this way, 〈x,2x+1〉⊆S. From Lemma 38, we have that 〈x,2x+1〉⊆𝒮PL(X). Since gcd{x,2x+1}=1, we get that 〈x,2x+1〉 is a numerical semigroup and, thus, ℕ∖〈x,2x+1〉 is finite. Consequently, ℕ∖𝒮PL(X) is finite.
Now, let us see that𝒮PL(X) is a PL-semigroup. Let x,y∈𝒮PL(X)∖{0}. If S is a PL-semigroup containing X, from Lemma 38, we deduce that x,y∈S∖{0} and from Theorem 5, we have that x+y+1∈S. By applying again Lemma 38, we have that x+y+1∈𝒮PL(X). Therefore, by applying Theorem 5 once more, we can assert that 𝒮PL(X) is a PL-semigroup.Remark 40.
Let us observe that, in general, Proposition39 is not true for Frobenius varieties. In fact, let 𝒮 be the set of all numerical semigroups. It is clear that 𝒮 is a Frobenius variety. If we take X={2}, then the intersection of all elements of 𝒮 containing {2} is exactly M=〈2〉, which is not a numerical semigroup.The next result will be key for our last purpose in this section.Theorem 41.
𝒮
P
L
=
{
𝒮
P
L
(
X
)
∣
X
i
s
a
n
o
n
e
m
p
t
y
f
i
n
i
t
e
s
u
b
s
e
t
o
f
ℕ
∖
{
0
}
}.Proof.
By Proposition39, we have that
(8){𝒮PL(X)∣Xisanonemptyfinitesubsetofℕ∖{0}}⊆𝒮PL.
For the other inclusion it is enough to observe that if S∈𝒮PL, then (by Proposition 37) there exists a nonempty finite subset X of ℕ∖{0} such that S=𝒮PL(X).Since𝒮PL is a Frobenius variety, by applying [3, Proposition 24], we get the next result.Proposition 42.
LetM be a 𝒮PL-monoid and let x∈M. Then M∖{x} is a 𝒮PL-monoid if and only if x belongs to the minimal 𝒮PL-system of generators of M.As an immediate consequence of this proposition we have the following result.Corollary 43.
LetX be a nonempty subset of ℕ∖{0}. Then the minimal 𝒮PL-system of generators of 𝒮PL(X) is {x∈X∣𝒮PL(X)∖{x} is a PL-semigroup}.Example 44.
By Proposition21, S=〈3,7,11〉 is a PL-semigroup. By applying Proposition 14, we easily deduce that
(9){x∈{3,7,11}∣S∖{x}isaPL-semigroup}={3}.
Therefore, S=𝒮PL({3}) and {3} is the minimal 𝒮PL-system of generators of S.Now we want to describe𝒮PL(X) when X is a fixed nonempty finite set of positive integers. Let us observe that by Theorem 41, we know that every PL-semigroup can be obtained in this way.Letn1,…,np be positive integers. We will denote by S(n1,…,np) the set {α1n1+⋯+αpnp+r∣r,α1,…,αp∈ℕ,r<α1+⋯+αp}∪{0}. Our next purpose will be to show that S(n1,…,np)=𝒮PL({n1,…,np}).Lemma 45.
LetS be a numerical semigroup, let s1,…,st∈S∖{0}, and let α1,…,αt∈ℕ. Then ord(α1s1+⋯+αtst)≥α1+⋯+αt.Proof.
Let{n1,…,np} be the minimal system of generators of S. Then, for each i∈{1,…,t}, there exist βi1,…,βip∈ℕ such that si=βi1n1+⋯+βipnp. Moreover, since si≠0, we have that βi1+⋯+βip≥1. Thus,
(10)α1s1+⋯+αtst=α1(β11n1+⋯+β1pnp)+⋯+αt(βt1n1+⋯+βtpnp)=(α1β11+⋯+αtβt1)n1+⋯+(α1β1p+⋯+αtβtp)np.
Therefore,
(11)ord(α1s1+⋯+αtst)≥(α1β11+⋯+αtβt1)+⋯+(α1β1p+⋯+αtβtp)=α1(β11+⋯+β1p)+⋯+αt(βt1+⋯+βtp)≥α1+⋯+αt.Theorem 46.
Ifn1,…,np are positive integers, then S(n1,…,np) is the smallest (with respect to set inclusion) PL-semigroup containing {n1,…,np}.Proof.
We divide the proof into five steps.(i)
Let us see that ifx,y∈S(n1,…,np)∖{0}, then x+y∈S(n1,…,np). In effect, we know that there exist α1,…,αp,β1,…,βp,r,r′ nonnegative integers such that x=α1n1+⋯+αpnp+r, y=β1n1+⋯+βpnp+r′, r<α1+⋯+αp, and r′<β1+…+βp. Therefore, x+y=(α1+β1)n1+⋯+(αp+βn)np+r+r′ with r+r′<(α1+β1)+⋯+(αp+βn). Consequently, x+y∈S(n1,…,np).(ii)
Let us see thatℕ∖S(n1,…,np) is finite. Since n1=1·n1+0·n2+⋯+0·np+0 and 2n1+1=2·n1+0·n2+⋯+0·np+1, we have that n1,2n1∈S(n1,…,np). By applying the first step, we get that 〈n1,2n1〉⊆S(n1,…,np). Using the same reasoning as we did in the proof of Proposition 39, we have the result.(iii)
From the previous steps, we know thatS(n1,…,np) is a numerical semigroup. Let us see now that S(n1,…,np) is a PL-semigroup. In order to do that, it is enough (by Theorem 5) to show that, if x,y∈S(n1,…,np)∖{0}, then x+y+1∈S(n1,…,np). Indeed, arguing as in the first step, we have that x+y+1=(α1+β1)n1+⋯+(αp+βn)np+r+r′+1 with r+r′+1<(α1+β1)+⋯+(αp+βn). Therefore, x+y+1∈S(n1,…,np).(iv)
Following the proof of the second step, it is clear that{n1,…,np}⊆S(n1,…,np).(v)
Finally, let us see thatS(n1,…,np) is the smallest PL-semigroup that contains {n1,…,np}. In fact, we will show that if T is PL-semigroup containing {n1,…,np}, then S(n1,…,np)⊆T. Thus, let x∈S(n1,…,np)∖{0}. Then there exist α1,…,αp,r∈ℕ such that x=α1n1+⋯+αpnp+r with r<α1+⋯+αp. Since {n1,…,np}⊆T, by Proposition 9, we have that α1n1+⋯+αpnp+{0,…,ord(α1n1+⋯+αpnp)-1}⊆T. By applying Lemma 45, we have that r<ord(α1n1+⋯+αpnp) and, therefore, x∈T.
In this way, we have proved the statement.The next result is an immediate consequence of the previous theorem.Corollary 47.
Ifn1,…,np are positive integers, then 𝒮PL({n1,…,np})=S(n1,…,np).We finish this section with an example that illustrates its content.Example 48.
It is clear thatS(4,7)={0,4,7,8,9,11,→}=〈4,7,9〉. Therefore, 𝒮PL({4,7})=〈4,7,9〉.



---

*Source: 459024-2013-11-19.xml*