What are the subsemigroups of $(\mathbb N,+)?$

Solution 1:

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.

Solution 2:

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

Solution 3:

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.

Solution 4:

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.