# What are the n-ary subsemigroups of $\mathbb{N}$?

There is a well-known result about the subsemigroups of $$\mathbb{N}$$ stating that the additive subsemigroup generated by a (finite) set $$A$$ of $$\mathbb{N}$$ is cofinite in $$\mathbb{N}$$ if and only if $$\gcd(A)=1$$, or equivalently that the subsemigroup generated by $$A$$ is cofinite in the non-negative part of the subgroup generated by $$A$$.

I am curious, whether a similar theorem exists for $$n$$-ary subsemigroups.

An $$n$$-ary subsemigroup of $$\mathbb{N}$$ is a subset which is closed under $$n$$-fold addition, thus, for $$n\geq 3$$, it is a weaker requirement than being a subsemigroup, thus in general, stronger requirements than the $$\gcd$$-condition are necessary.

• The 3-ary subsemigroup generated by 1 consists of odd positive numbers, so the statement should be modified in any case.
– YCor
Commented Jul 21, 2022 at 8:49
• I did not mean that the same theorem applies. It should be clearer now. Commented Jul 21, 2022 at 9:05

A description is given by:

Proposition. Let $$L$$ be a nonempty $$n$$-ary subsemigroup of $$\mathbf{N}$$, and generating $$\mathbf{Z}$$ as a subgroup. Then there exists $$k\ge 1$$ dividing $$n-1$$ and $$0<\ell coprime to $$k$$ such that $$L$$ is a cofinite subset of the arithmetic progression $$k\mathbf{N}+\ell$$.

(The condition that $$L$$ generates $$\mathbf{Z}$$ is not serious: in general $$L$$ generates a subgroup of $$r\mathbf{Z}$$ of $$\mathbf{Z}$$ and we deduce that $$L$$ is a cofinite subset in $$r(k\mathbf{N}+\ell)$$ for some $$k$$ dividing $$n-1$$ and $$0<\ell coprime to $$k$$.)

Lemma 1 Let $$L$$ be an $$n$$-ary subsemigroup of $$\mathbf{N}$$. Then $$L$$ is ultimately periodic: there exists $$k$$ such that the symmetric difference of $$k$$ and $$L+k$$ is finite, and the projection of $$L$$ modulo $$k$$ is an $$n$$-ary subsemigroup of $$\mathbf{Z}/k\mathbf{Z}$$. Moreover, if $$k$$ is chosen minimal and $$L$$ generates $$\mathbf{Z}$$ as a subgroup, then $$k$$ divides $$n-1$$.

Hence, the classification "modulo finite subsets" reduces to the classification of $$n$$-ary subsemigroups of $$\mathbf{Z}/(n-1)\mathbf{Z}$$.

Proof of Lemma 1. If $$L$$ is empty the result is clear; assume otherwise. Choose $$k_0$$ in $$L$$. Then $$L+(n-1)k_0\subset L$$. Hence the sequence indexed by $$m$$ of projections modulo $$n-1$$ of $$L\cap\{m(n-1)+1,m(n-1)+2,\dots,m(n-1)+n-1\}$$ is an ascending sequence of subsets of $$\mathbf{Z}/(n-1)\mathbf{Z}$$ and hence stabilizes. So $$L$$ is eventually $$(n-1)$$-periodic. If $$k,k'$$ are eventual periods, then clearly so is $$\gcd(k,k')$$. Let $$k$$ be the smallest eventual period (so $$k$$ divides $$n-1$$). For large enough $$m$$, the subset $$L\cap\{m(n-1)+1,m(n-1)+2,\dots,m(n-1)+n-1\}$$ doesn't depend on $$m$$ and is a $$n$$-ary subsemigroup $$L_k$$ of $$\mathbf{Z}/k\mathbf{Z}$$. Moreover if $$L$$ generates $$\mathbf{Z}$$, the $$L_k$$ generates $$\mathbf{Z}/k\mathbf{Z}$$. (Indeed otherwise it would mean that for some prime $$p$$, $$L\smallsetminus p\mathbf{Z}$$ is finite. But choosing $$n-1$$ large elements in $$L\cap p\mathbf{Z}$$ and one element in $$L\smallsetminus p\mathbf{Z}$$ yields a large element in $$L\smallsetminus p\mathbf{Z}$$, contradiction.)

So for each $$n$$ and $$k$$ dividing $$n-1$$, we are reduced to finding the non-empty $$n$$-ary subsemigroups of $$\mathbf{Z}/k\mathbf{Z}$$ that generate $$\mathbf{Z}/k\mathbf{Z}$$ (call this $$n$$-templates), which have no smaller period (i.e. for no strict divisor $$\ell$$ of $$k$$ are inverse image of an $$n$$-template in the quotient $$\mathbf{Z}/\ell \mathbf{Z}$$.

Lemma 2. Every $$n$$-template in $$\mathbf{Z}/k\mathbf{Z}$$ is reduced to a singleton $$\{\ell\}$$ with $$\ell$$ coprime to $$k$$.

Proof: endow $$\mathbf{Z}/k\mathbf{Z}$$ with the obvious distance ($$d(\ell,\ell')$$ is the minimum absolute value of a representative of $$\ell-\ell'$$). Suppose by contradiction that a template $$T$$ is not reduced to a singleton and let $$a,b$$ be at minimal distance, say $$k'$$ (so $$k'\le k/2$$). Considering all possible $$n$$-ary sums of $$a$$ and $$b$$, we see that $$T$$ contains the arithmetic progression of period $$b-a$$ $$\{a,b,2b-a,3b-2a,\dots ,2a-b\}$$. Since $$k$$ is the minimal period for $$T$$, $$T$$ cannot be $$(b-a)$$-periodic and hence there is another element in $$T$$. But this contradicts the minimality of the distance.

Proof of the proposition: Combining the lemmas shows that $$L$$ eventually coincides with $$k\mathbf{N}+\ell$$ for some $$k$$ dividing $$n-1$$ and $$\ell\in\{0,\dots,k-1\}$$ coprime to $$k$$ (I use the convention $$0\in\mathbf{N}$$). It remains to show that $$L\subset k\mathbf{N}+\ell$$. Indeed otherwise there's in $$L$$ an element of the form $$km+\ell'$$ with $$\ell'\neq \ell$$ mod $$k$$. Taking with $$n$$-ary sum with $$n-1$$ large elements in $$L\cap (k\mathbf{N}+\ell)$$ yields a contradiction.

Examples:

$$n$$ arbitrary, $$k=1$$: the only $$n$$-template in $$\mathbf{Z}/1\mathbf{Z}$$ is $$\mathbf{Z}/1\mathbf{Z}$$. This corresponds to the case when $$L$$ is cofinite. For $$n=2$$, $$k$$ divides $$n-1=1$$ so there is no other case.

$$n=2$$: here $$n-1=1$$ so $$k=1$$ and the only $$2$$-template in $$\mathbf{Z}/1\mathbf{Z}$$ is $$\mathbf{Z}/1\mathbf{Z}$$. It means $$L$$ is a cofinite subset (classical case).

For $$k\neq 1$$:

$$n=3$$: the only nonempty 3-template in $$\mathbf{Z}/2\mathbf{Z}$$ is $$\{1\}$$. It corresponds to the case when $$L$$ eventually consists of all odd numbers.

$$n=4$$: the only nonempty 4-templates in $$\mathbf{Z}/3\mathbf{Z}$$ are $$\{1\}$$ and $$\{2\}$$. They correspond to the case when $$L$$ eventually consists of all numbers equal to 1, resp. 2, modulo 3.

$$n=5$$: either $$k=2$$ and then $$L$$ eventually consists of all odd numbers, or $$k=4$$ and then $$L$$ eventually consists of all numbers that equal $$i$$ modulo $$4$$ (for some fixed $$i=1$$ or $$i=3$$).

Etc.

• This is pretty insightful. Thank you very much. Commented Jul 21, 2022 at 9:52
• In other words, the general case is that $L$ is a cofinite subset of $k\mathbb N+l$ for some $k,l$ such that $k\mid(n-1)l$. Commented Jul 21, 2022 at 11:55
• @EmilJeřábek it's not a 100% complete solution, because conversely an arbitrary cofinite subset in such an arithmetic progression need not be an $n$-ary subsemigroup. But this is indeed a better way to state the remark following the proposition.
– YCor
Commented Jul 21, 2022 at 12:00
• Yes, that’s what I meant. Commented Jul 21, 2022 at 12:29