Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

While trying to solve a somewhat bigger problem, I realized that I don't know what the subsemigroups of one of the most important semigroups, $(\mathbb N,+)$, are. (I assume $0\not\in\mathbb N$.) I've tried to characterize them but I haven't managed to do it fully. What follows are the facts I have proven so far, without most of the proofs but with lemmas, which hopefully show how the proofs go. I'm not posting all the proofs not because I'm sure my proofs are correct, but because I don't want to make this post too long. I will add the proof of anything below on request.

Notation. $\langle a_1,\ldots,a_n\rangle$ will denote the subsemigroup generated by $a_1,\ldots,a_n\in\mathbb N$. If $X\subseteq \mathbb N$, then $\langle X\rangle$ willl denote the subsemigroup generated by $X$.

Lemma 1. $\langle a_1,\ldots,a_n\rangle = \{k_1a_1+\ldots+k_na_n\,|\,k_i\geq 0,\,\sum k_i>0\}.$

Lemma 2. If $a_1,\ldots,a_n\in\mathbb N$ and $\gcd(a_1,\ldots,a_n)=1,$ then there exists $x\in \langle a_1,\ldots,a_n\rangle$ such that for every $n\geq x,\,n\in\mathbb N,$ we have that $n\in \langle a_1,\ldots,a_n\rangle.$

Notation. For $n\in\mathbb N$ and $X\subseteq \mathbb N$, $nX$ will denote $\{nx\,|\,x\in X\}.$

Lemma 3. For every finitely generated subsemigroup $S=\langle a_1\ldots,a_n\rangle$ of $\mathbb N$, there exists a finitely generated subsemigroup $T$ of $\mathbb N$ whose generators are coprime and such that $S=\gcd(a_1,\ldots,a_n)\,T$.

Proposition 4. Every finitely generated subsemigroup $S=\langle a_1,\ldots,a_n\rangle$ of $\mathbb N$ eventually becomes an infinite arithmetic progression with difference $d=\gcd(a_1,\ldots,a_n)$. That is, there exists $x\in S$ such that $S\cap\{n\in\mathbb N\,|\,n\geq x\}=\{x+kd\,|\,k\geq 0\}.$ (It has to be noted that $d|x.$)

Lemma 5. If $X\subseteq \mathbb N$, then there exists a unique $\gcd(X),$ that is a number $d\in\mathbb N$ such that for all $x\in X$ we have $d|x,$ and if for all $x\in X$ we have $c|x$, then $c|d.$ There also exists a finite subset $Y\subseteq X$ such that $\gcd (Y)=\gcd(X).$

Proposition 6. Every subsemigroup of $\mathbb N$ is finitely generated.

Proof. Let $S$ be a subsemigroup of $\mathbb N$. Let $d=\gcd (S).$ Then there exists $Y\subseteq S$ such that $\gcd(Y)=d.$ Surely $\langle Y\rangle\subseteq\mathbb N.$ There exists $x\in\langle Y\rangle$ such that $$\langle Y\rangle\cap\{n\in\mathbb N\,|\,n\geq x\}=\{x+kd\,|\,k\geq 0\}.$$

Thus, beginning from $x$, all numbers divisible by $d$ are in $\langle Y\rangle.$ Therefore, in particular, all elements of $S$ greater than or equal $x$ are in $\langle Y\rangle.$ It follows that $S=\langle Y\cup (S\cap \{n\in\mathbb N\,|\,n<x\})\rangle.$ So $S$ is finitely generated. $\square$

QUESTION. From the above facts (which are hopefully true), I know what subsemigroups of $\mathbb N$ look like eventually. They become arithmetic progressions whose difference divides its elements. But can we describe their initial behavior in a usable way? For example, this is a subsemigroup:

$$\{3,5,7,8,9,\ldots\};$$

this is a subsemigroup:

$$\{3,5,8,9,\ldots\};$$

but this is not:

$$\{3,5,7,9,\ldots\}.$$

My general question is this: can we usefully characterize subsemigroups of $\mathbb N$ among subsets of $\mathbb N$?

share|improve this question
2  
Here. And locally for example here. –  Jyrki Lahtonen Jun 28 '12 at 13:19
1  
A few references, which contain the result that every subsemigroup of $(\mathbb N,+)$ is finitely additive and may be interesting for you: Proposition 4.1 in Pierre Antoine Grillet: Commutative Semigroups, Corollary 1 in the paper Higgins: Subsemigroups of the Additive Positive Integers, Corollary 1 in the paper William Y. Sit and Man-Keung Siu: On the Subsemigroups of N. –  Martin Sleziak Jun 28 '12 at 13:21
2  
BTW there are whole books devoted to numerical semigroups, e.g. Rosales, Garcia-Sanchez: Numerical Semigroups. –  Martin Sleziak Jun 28 '12 at 13:21
1  
@Tobias Thank you for this comment. Unfortunately, I understand very little of it. I don't know what hook-lenghts and beta-sets are, and what columns you are talking about. Could you please post it as an answer and link to some explanation of the terms you are using? –  user23211 Jun 28 '12 at 13:50
1  
@TrevorWilson There is a nice characterization here on precisely what numbers are generated. If we start with more than 2 numbers, though, we do not know of a nice exact description, and the problem is significantly harder. A good reference is J. Ramírez Alfonsín (2005). The Diophantine Frobenius problem. Oxford Univ. Press. –  Andres Caicedo Jan 24 '13 at 6:51

6 Answers 6

up vote 4 down vote accepted

You are looking at what is sometimes called the Frobenius problem. The two-generator case is already interesting: if $a,b$ are coprime then the semigroup they generate has every positive integer from $N=(a-1)(b-1)$ on, and exactly half of the integers between zero and $N-1$, inclusive; moreover, it contains $m$ in that range if and only if it doesn't contain $N-1-m$. These are all good exercises to prove, if this is new to you.

The $n=3$ case is much harder, bigger values of $n$ are harder still.

share|improve this answer

There is a name for these: http://en.wikipedia.org/wiki/Numerical_semigroup

share|improve this answer
    
According to that page, numerical semigroups are semigroups which consist of all non-negative integers except finitely many. So what I'm asking about is a larger class (if we forget about $0$): for example, $\{2,4,6,\ldots\}$ is a subsemigroup of $\mathbb N$, but infinitely many numbers aren't in it. However, it can be obtained from a numerical semigroup ($\{1,2,3,\ldots\}$) by multiplication by a natural number ($2$) and so will any subsemigroup of $\mathbb N$. –  user23211 Jun 28 '12 at 13:24

Well, no. It is not as simple as you think. If there is some $n$ such that all the numbers from $n$ to $2n$ are in the set, then all numbers $n$ and larger are in the set. That is, we can add $n,$ so we get all $2n$ to $3n,$ yet again gives us $3n$ to $4n,$ and so on. So, if $2,3$ are in the set, we find $$ 2 = 2, \; 3 = 3, \; 4 = 2 + 2, $$ so everything except 1 is is this set.

For $3,5,$ we get $$ 8 = 3 + 5, \; 9 = 3 + 3 + 3, \; 10 = 5 + 5, \; 11 = 3 + 3 + 5, \; 12 = 3 = 3 + 3 + 3, \; 13 = 3 + 5 + 5, \; 14 = 3 + 3 + 3 + 5, \; 15 = 5 + 5 + 5, \; 16 = 3 + 3 + 5 + 5.$$ So this second set is everything except ${1,2,4,7}.$

Alright, with two given (relatively prime) generators $m,n,$ not only is the largest number not part of the set exactly $mn - m -n,$ but the (finite) set of numbers that are not in the set has exactly $\frac{(m-1)(n-1)}{2}$ members. See SYLVESTER_1884

I am not sure exactly what happens if you have, for example, three generators with no overall common factor but which are not pairwise coprime, as in $\{6,10,15 \}.$ Easy enough to experiment with specific triples, my comment about $n,2n$ still applies.

share|improve this answer
    
I think the problem of finding the smallest integer not generated by some set $S$ of relatively prime generators is still open, except for the $|S|=2$ case you mentioned. –  MJD Jan 24 '13 at 9:02
    
For $|S|=3$ there's a nice result stated in Hua's book Number Theory. It isn't general, but says: If $a,b,c$ are pairwise relatively prime, then the largest integer not represented by $abx+acy+bcz$ (with $x,y,z$ nonnegative) is $abc-a-b-c$. It's not general for three pairwise coprime integers, since not all such triples are of the form $(ab,ac,bc)$ with $a,b,c$ coprime. –  coffeemath Jan 24 '13 at 15:06

Consider the additive closure of a finite set (everything you can possibly make by adding together generators):

  • If all the generators share a common divisor so will the elements of the closure (so divide it through)
  • If any pair of elements are coprime, then eventually every number will be expressible.

So the structure of these sets will always be some randomness at the start then after some point all multiples of a common divisor (possibly 1).

Now take any additively closed set (not just a finitely generated one), consider the additively closed subset generated by the first two elements of it.. this will have the same structure as in the finite case and there are only finitely many gaps to put new elements in.. so they all have the same type of structure.

share|improve this answer
    
So could you prove that if $A \subset \mathbb N$ is additively closed then there is an $n$ such that $A_n=\{k \in A \mid k>n\}=\{k \in t \mathbb Z \mid k>n\}$ for some $t$?. So every additively closed subset is "eventually" an ideal of $\mathbb Z$? –  JSchlather Jan 24 '13 at 6:22
    
Apart from the empty set, sure. –  André Nicolas Jan 24 '13 at 6:27
1  
@JacobSchlather, I just said how to prove that –  user58512 Jan 24 '13 at 6:31

Here is an expansion of my comments about partitions. If $\lambda = (\lambda_1,\dots,\lambda_k)$ is a partition of $n$ then we associate to $\lambda$ its Young diagram, which is described at http://en.wikipedia.org/wiki/Young_tableau#Diagrams (easier to link to it there as the drawings help). To each square in the diagram is associated a hook length, which is the number of squares directly below and directly to the right of the given square, including the square itself. For example, for the partition $(5,4,1)$, the hook lengths are (when starting from the top left and taking one row at a time) 7, 5, 4, 3, 1, 5, 3, 2, 1, 1. Of particular interest are the hook lengths in the first column (so here those are 7, 5, 1), since we can reconstruct the partition from those alone. In general, a $\beta$-set for a partition is a set of natural numbers $X = \{x_1,\dots, x_k\}$ with $x_1\geq x_2\geq\cdots\geq x_k$ and such that the partition is $(x_1 + k - 1, x_2 + k - 2,\dots, x_k + k - k)$ (hence, the partition will have exactly the $\beta$-set as the hook lengths in the first column).

Now for the connection to subsemigroups of $\mathbb{N}$ with finite complement. It turns out that if we start with the complement of such a subsemigroup and let this be the $\beta$-set of a partition, then that partition will have all its hook lengths in the first column, and this gives a bijection between such subsemigroups and partition with that property (the inverse given by simply taking the complement of the set of hook lengths).

Finally, some musings on this problem: If the above can be helpful in determining those subsemigroups with finite complement, then maybe this can be extended as follows: If $A$ is any subsemigroup, then as noted above, from a certain point it becomes an arithmetic progression. Let's say it does so from the $k$'th smallest element $a_k$ and no sooner. Then we can look at those elements in the complement which are at most $a_k$. This is now a finite set, and its complement is indeed a subsemigroup of $\mathbb{N}$, so it can be described as above. The new problem is then to determine what possible arithmetic progressions can be tagged on as a "tail" on the set $\{a_1,\dots,a_k\}$.

Edit: As an extra note, if $A$ is a subsemigroup with finite complement and that complement contains $k$ elements, then the largest elements in the complement is at most $2k-1$ (easy exercise). If $X$ is some arbitrary subset of $k$ elements where the largest element happens to equal $2k-1$ (say $X = \{x_1,\dots,x_k\}$ with $x_1 < x_2 < \cdots < x_k$), then the above correspondence to partitions can be used to show that the complement of $X$ is a subsemigroup iff for all $1 \leq i\leq k$ and for all $k - x_i + i \leq j\leq k$ we have $x_i + x_j - x_k \in X$.

share|improve this answer
    
Thank you very much, Tobias. I will be thinking about these things, and perhaps ask another question in the near future. –  user23211 Jun 29 '12 at 22:55

I don't think there is a simple answer. First, look for a common factor of your generators. If there is one, everything will be a multiple of that, so divide it out and multiply it in at the end. If you have two generators, $m,n$, there is a simple answer. There are finitely many numbers that cannot be expressed and the greatest is $mn-m-n$

share|improve this answer
1  
Ross, your number is the beginning of those that must be represented. The largest one missed is your number minus 1. en.wikipedia.org/wiki/Coin_problem#n_.3D_2 –  Will Jagy Jan 24 '13 at 6:37
    
@WillJagy: thanks. –  Ross Millikan Jan 24 '13 at 14:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.