What is known about submagmas of natural numbers under addition/multiplication?

For example, all subgroups of integers under addition are of the form $~n \mathbb{Z}~$. Are there similar results for natural numbers?

Thanks in advance.

  • $\begingroup$ These are semigroups, i.e. magmas with associative operation. E.g. for any given $n$, the set $\{m\mid m\ge n\}$ is a subsemigroup (wither under $+$ or under $\cdot$). But there are many more.. $\endgroup$ – Berci Oct 25 '14 at 22:50
  • $\begingroup$ I understand that all of them are cancellative commutative semigroups but is there more exact and specific classification? $\endgroup$ – Igor Oct 25 '14 at 22:53
  • $\begingroup$ They are commutative monoids with no last element. $\endgroup$ – Doug Spoonwood Oct 25 '14 at 23:16

Essentially, this reduces to the same problem as that of Frobenius number, which is defined, for a set of natural numbers $S$ whose $\gcd$ is 1 (but which are not necessarily pairwise coprime or anything), as the largest number which cannot be written as a sum thereof. From known results, it's clear that, for any finite set $S$ such a number exists, which implies that any subsemigroup of the natural numbers will contain some set of the form $d \mathbb{N} + kd$ for integer $d$ and $k$.

A simple proof of this fact is that there must be, from the $\gcd$ of a set $S$ being $1$, some sum $a_1s_1+a_2s_2+\ldots+a_ns_n=1$ where $s\in S$ and $a\in \mathbb{Z}$. Thus, by multiplying the coefficients by $c$, it is possible to write any $c\in [1,s_1s_2\ldots s_n]$ as a sum of $S$ with integer coefficients - but this admits negative coefficients. However, if the coefficient of $s_i$ were negative, we could add $s_1s_2\ldots s_{i-1}s_{i+1}\ldots s_n$ to the coefficient thereof, increasing the total sum by $s_1s_2\ldots s_n$, and if we repeated this to every negative coefficient, eventually we would have a sum with only positive coefficients; this implies that there are only finitely many value for $k$ in any arithmetic progression $a+k s_1s_2\ldots s_n$ which cannot be written as a sum of finitely many generators from a coprime set, and, as finitely many such arithmetic progressions partition the set, there are only finitely many values not writable as a sum of some set.

From this, we get that if we take any subsemigroup $G$ and let $d=\gcd(G)$ - which is well-defined, since, if $A\subseteq B$, then $1\leq\gcd(B)\leq\gcd(A)$ - then, for some large enough $k$, every $K>k$ will have $dK$ is in $G$. Thus, every subsemigroup is generated by a finite number of elements, and has a subsemigroup $G'\subseteq G$ which is isomorphic to the natural numbers and such that $G\backslash G'$ is finite.

I don't think much more is known about the subject - the above gives a nice handle to study it further from, since it characterizes all such sets as being finitely generated, but given the fact that there is no known closed form for the Frobenius number for sets of size greater than $3$, there's not a whole lot that can be said. If you have any more specific questions about the subsemigroups, I'd be happy to think on them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.